Multi-View Spectral Clustering for Graphs with Multiple View Structures
Yorgos Tsitsikas, Evangelos E. Papalexakis · 2025
Read Multi-View Spectral Clustering for Graphs with Multiple View Structures by Yorgos Tsitsikas, Evangelos E. Papalexakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11422.txt.
Introduction
Yorgos Tsitsikas and Evangelos Papalexakis set out, in a 2025 paper, a shared frame for graph clustering that holds many past methods in one view. Clustering splits data into like groups, yet its base is still murky: schools do not agree on what a cluster is. Graphs add a twist when each view of the links can group the same nodes in a new way. Their frame takes in a run of past methods, the spectral family most of all. In that view they build GenClus, a method that widens spectral clustering and sits close to k-means as well.
Tests show GenClus runs faster than past methods for such multi-view graphs. Its groups were as good or better on the same tests. A real-world case shows it can find groups with clear sense. The frame may help the field agree on terms.
Catalog record
| CREATOR | Yorgos Tsitsikas, Evangelos E. Papalexakis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-11422
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-View Spectral Clustering for Graphs with Multiple View Structures Yorgos Tsitsikas, Evangelos E. Papalexakis Abstract Despite the fundamental importance of clustering, to this day, much of the relevant research is still based on ambiguous foundations, leading to an unclear understanding of whether or how the various clustering methods are connected with each other. In this work, we provide an additional stepping stone towards resolving such ambiguities by presenting a general clustering framework that subsumes a series of seemingly disparate clustering methods, including various methods belonging to the widely popular spectral clustering framework. In fact, the generality of the proposed framework is additionally capable of shedding light to the largely unexplored area of multi-view graphs where each view may have differently clustered nodes. In turn, we propose GenClus: a method that is simultaneously an instance of this framework and a generalization of spectral clustering, while also being closely related to k-means as well. This results in a principled alternative to the few existing methods studying this special type of multi-view graphs. Then, we conduct in-depth experiments, which demonstrate that GenClus is more computationally efficient than existing methods, while also attaining similar or better clustering performance. Lastly, a qualitative real-world case-study further demonstrates the ability of GenClus to produce meaningful clusterings. Keywords— Multi-graph; Multi-modal graph; Multi-view graph; Multi-layer graph; Multi-aspect graph; Multi-plex graph; Spectral clustering; Clustering; Tensor Decomposition; Tensor Factorization introduction 1 Proposed Unifying Framework. Symbol Definition x , X Scalar \mathbf{x} Column vector \mathbf{X} Matrix \bm{\mathcal{X}} Tensor {\mathcal{X}} Set \left|\left|\cdot\right|\right| Frobenious norm \nnzop\left(\cdot\right) Number of non-zero elements \mathbf{I} Identity matrix \mathbf{0} All zeros column vector/matrix/tensor \mathbf{1} All ones column vector/matrix/tensor \diagonalize\left(\mathbf{x}\right) Diagonal matrix with \mathbf{x} as its diagonal \diagonalize\left(\mathbf{X}\right) Vector consisting of the diagonal elements of \mathbf{X} \mathbf{D}_{\mathbf{X}}^{(k)} \diagonalize\left(\mathbf{X}_{k:}\right) \trace\left(\mathbf{X}\right) Trace of \mathbf{X} \mathbf{X}^{T} Transpose of \mathbf{X} \mathbf{x}\succeq\mathbf{y} \forall i\ \mathbf{x}_{i}\geq\mathbf{y}_{i} \llbracket\mathbf{U}{},\mathbf{V}{},\mathbf{W}{}\rrbracket PARAFAC with factor matrices \mathbf{U} , \mathbf{V} and \mathbf{W} [\mathbf{U},\mathbf{V},\mathbf{W}] Horizontal concatenation of \mathbf{U} , \mathbf{V} and \mathbf{W} \odot Column-wise Khatri–Rao product \times_{n} Mode- n product \mathbf{X}_{(n)} Mode- n matricization of \bm{\mathcal{X}} Table 1 : Table of Symbols. See [ 51 ] for further details on tensor notation and operations. {forest} Figure 1 : For each arrow the method on its right can be seen as a special case of the method on its left. Consider K adjacency matrices, \{\mathbf{X}^{(k)}\}_{k=1}^{K} , where each is of size I\times I and corresponds to a different view of a multi-view graph. Additionally, assume that these views can be clustered into M groups, with each group corresponding to a different clustering of nodes. For convenience, we will refer to such a node clustering structure as a view structure. Given these, in this section we present an overview of existing methods designed to model and extract such clusterings. Due to space limitations, we will only discuss the embedding generation stage of these methods, but a more thorough discussion on obtaining the final clusterings is available in . Then, we demonstrate that all these methods can be expressed as special cases of a unifying framework, as illustrated in Figure 1 . Specifically, we show that they can be expressed as variants of PARAFAC [ 45 ] , [ 49 ] , where the third factor matrix is constrained to be the product of two matrices. Please note that the goal of this unifying framework is not necessarily to precisely encapsulate the exact optimization problems of these methods. Rather, its goal is to abstract their essence. For example, we will assume that a method is conceptually aiming to calculate the same model, independent of whether it algorithmically imposes a constraint as a hard constraint or as a soft constraint. Similarly, we will assume that it conceptually remains the same, independent of whether it imposes constraints like non-negativity or sparsity. 1.1 ComClus. ComClus [ 79 ] can be expressed as (1.1) \inf_{\mathbf{U},\mathbf{W},\mathbf{A},\mathbf{B}\geq 0}\sum_{k=1}^{K}\left|\left|\mathbf{X}^{(k)}-\mathbf{O}^{(k)}\mathbf{U}\mathbf{D}_{\mathbf{W}}^{(k)}(\mathbf{O}^{(k)}\mathbf{U})^{T}\right|\right|^{2}+\\ r(\mathbf{U},\mathbf{W},\mathbf{A},\mathbf{B}) where r(\mathbf{U},\mathbf{W},\mathbf{A},\mathbf{B}):=\beta||\mathbf{W}-\mathbf{A}\mathbf{B}||^{2}+\rho(||\mathbf{U}||_{1}+||\mathbf{A}||_{1}+||\mathbf{B}||_{1}) , each \mathbf{O}^{(k)} is a user-defined indicator matrix, and \beta and \rho are user-defined penalty parameters. By making the closed-world assumption [ 80 ] , the first term becomes equal to \sum_{k=1}^{K}\left|\left|\mathbf{X}^{(k)}-\mathbf{U}\mathbf{D}_{\mathbf{W}}^{(k)}\mathbf{U}^{T}\right|\right|=\left|\left|\bm{\mathcal{X}}-\llbracket\mathbf{\mathbf{U}}{},\mathbf{\mathbf{U}}{},\mathbf{\mathbf{W}}{}\rrbracket\right|\right| where \bm{\mathcal{X}}_{::k}:=\mathbf{X}^{(k)} . Therefore, ComClus can be interpreted as aiming to approximate \bm{\mathcal{X}} by \llbracket\mathbf{U}{},\mathbf{U}{},\mathbf{W}{}\rrbracket such that \mathbf{W}\approx\mathbf{A}\mathbf{B} , where \mathbf{U},\mathbf{A},\mathbf{B} are sparse and non-negative, and \mathbf{W} is non-negative. 1.2 Richcom. Richcom [ 73 ] can be expressed as (1.2) \inf_{\begin{subarray}{c}\mathbf{U}^{(m)},\mathbf{V}^{(m)},\\ \mathbf{a}^{(m)}\end{subarray}}\left|\left|\bm{\mathcal{X}}-\sum_{m=1}^{M}\left(\mathbf{U}^{(m)}{\mathbf{V}^{(m)}}^{T}\right)\times_{3}\mathbf{a}^{(m)}\right|\right|^{2}+\\ \sum_{m=1}^{M}r\left(\mathbf{U}^{(m)},\mathbf{V}^{(m)},\mathbf{a}^{(m)}\right) where r\left(\mathbf{U}^{(m)},\mathbf{V}^{(m)},\mathbf{a}^{(m)}\right) encodes the sparsity and non-negativity constraints. We notice that \begin{split}\sum_{m=1}^{M}\left(\mathbf{U}^{(m)}{\mathbf{V}^{(m)}}^{T}\right)\times_{3}\mathbf{a}^{(m)}&=\sum_{m=1}^{M}\llbracket\mathbf{U}{{}^{(m)}},\mathbf{V}{{}^{(m)}},\mathbf{a}{{}^{(m)}\mathbf{1}^{T}}\rrbracket\\ &=\llbracket\mathbf{U}{},\mathbf{V}{},\mathbf{AB}{}\rrbracket\end{split} where \mathbf{U}:=\begin{bmatrix}\mathbf{U}^{(1)},\cdots,\mathbf{U}^{(M)}\end{bmatrix} , \mathbf{V}:=\begin{bmatrix}\mathbf{V}^{(1)},\cdots,\mathbf{V}^{(M)}\end{bmatrix} , \mathbf{A}:=\begin{bmatrix}\mathbf{a}^{(1)},\cdots,\mathbf{a}^{(M)}\end{bmatrix} and \mathbf{B} is an appropriate indicator matrix. The constraints of Richcom are then equivalent to requiring \mathbf{U} , \mathbf{V} , and \mathbf{A} to be sparse and non-negative. Notice that, as opposed to ComClus, \mathbf{B} here is a fixed matrix that needs to be defined by the user. 1.3 Centroid-based Multilayer Network Clustering (CMNC). CMNC [ 69 ] is similar to Richcom with their differences being that for CMNC \mathbf{U}^{(m)}=\mathbf{V}^{(m)} for all m , \sum_{m=1}^{M}\mathbf{a}^{(m)}_{i}=1 for all i , no sparsity is imposed and each view of the data tensor is preprocessed as {\mathbf{D}^{(k)}}^{-\frac{1}{2}}\mathbf{X}^{(k)}{\mathbf{D}^{(k)}}^{-\frac{1}{2}} where \mathbf{D}^{(k)}:=\diagonalize\left(\sum_{i=1}^{I}\mathbf{X}^{(k)}_{:i}\right) . 1.4 Spectral Clustering. In spectral clustering [ 85 ] , [ 78 ] , [ 88 ] , [ 75 ] , an important quantity is the Laplacian, \mathbf{L} , defined as \mathbf{D}-\mathbf{X} , with \mathbf{D}:=\diagonalize\left(\sum_{i=1}^{I}\mathbf{X}_{:i}\right) . In turn, the symmetric normalized Laplacian, \mathbf{L}_{sym} , is defined as {\mathbf{D}}^{-\frac{1}{2}}\mathbf{L}{\mathbf{D}}^{-\frac{1}{2}} . Note that the eigenspace of \mathbf{L}_{sym} corresponding to its eigenvalue \lambda\in[0,2] is also the eigenspace of \mathbf{S}:=\mathbf{I}-\mathbf{L}_{sym}={\mathbf{D}}^{-\frac{1}{2}}\mathbf{X}{\mathbf{D}}^{-\frac{1}{2}} corresponding to its eigenvalue 1-\lambda\in[-1,1] . 1.4.1 Single-View Spectral Clustering. Single-view spectral clustering can be formulated as \inf_{\mathbf{U}^{T}\mathbf{U}=\mathbf{I}}\left|\left|-\mathbf{L}_{sym}-\mathbf{U}\mathbf{U}^{T}\right|\right| , and notice that \mathbf{U}\mathbf{U}^{T}=\llbracket\mathbf{U}{},\mathbf{U}{},\mathbf{\mathbf{1}^{T}}{}\rrbracket=\llbracket\mathbf{U}{},\mathbf{U}{},\mathbf{\mathbf{A}\mathbf{B}}{}\rrbracket , where \mathbf{A}:=1 and \mathbf{B}:=\mathbf{1}^{T} . 1.4.2 Multi-View Spectral Clustering. In [ 77 ] the authors proposed the MC-TR-I-EVDIT method which models multi-view spectral clustering as (1.3) \sup_{\begin{subarray}{c}\mathbf{U}^{T}\mathbf{U}=\mathbf{I}\\ \mathbf{a}\succeq\mathbf{0},\left|\left|\mathbf{a}\right|\right|=1\end{subarray}}\sum_{k=1}^{K}\trace\left(\mathbf{U}^{T}\mathbf{a}_{k}\mathbf{S}^{(k)}\mathbf{U}\right). They also proposed the MC-TR-I-EVD method which can be seen as a variant of MC-TR-I-EVDIT where all elements of \mathbf{a} are further constrained to be identical. Then, in [ 76 ] the authors propose two forms of co-regularized spectral clustering with one utilizing a centroid-based co-regularization as (1.4) \sup_{\begin{subarray}{c}{\mathbf{U}^{(k)}}^{T}\mathbf{U}^{(k)}=\mathbf{I}\\ {\mathbf{U}^{*}}^{T}\mathbf{U}^{*}=\mathbf{I}\end{subarray}}\sum_{k=1}^{K}\trace\left({\mathbf{U}^{(k)}}^{T}\mathbf{S}^{(k)}\mathbf{U}^{(k)}\right)+\\ \lambda_{k}\trace\left(\mathbf{U}^{(k)}{\mathbf{U}^{(k)}}^{T}\mathbf{U}^{*}{\mathbf{U}^{*}}^{T}\right) and the other utilizing the pairwise co-regularization \lambda\sum_{i\neq j}\trace\left(\mathbf{U}^{(i)}{\mathbf{U}^{(i)}}^{T}\mathbf{U}^{(j)}{\mathbf{U}^{(j)}}^{T}\right) instead. Note that both of these formulations can be seen as relaxed versions of MC-TR-I-EVD where the embeddings from different views are forced to only be similar to each other instead of exactly equal. Specifically, the regularization terms force the columnspaces of all \mathbf{U}^{(k)} to become more similar with each other as \lambda and \lambda_{k} take larger values. In the limit, their columnspaces become identical and the rows of \mathbf{U}^{(k)} will be just orthogonally rotated versions of the rows of any other \mathbf{U}^{(i)} . Therefore, applying k-means, as suggested by the authors, on the rows of any \mathbf{U}^{(k)} will lead to the same node clusters. Now notice that ( 1.3 ) has the same optimal set as (1.5) \arginf_{\begin{subarray}{c}\mathbf{U}^{T}\mathbf{U}=\mathbf{I}\\ \mathbf{A}\succeq\mathbf{0},\left|\left|\mathbf{A}\right|\right|=1\end{subarray}}\left|\left|\bm{\mathcal{S}}-\llbracket\mathbf{U}{},\mathbf{U}{},\mathbf{AB}{}\rrbracket\right|\right| where \bm{\mathcal{S}}_{::k}:=\mathbf{S}^{(k)} , \mathbf{A}:=\mathbf{a} and \mathbf{B}:=\mathbf{1}^{T} (see for proof). Similarly, we can show that MC-TR-I-EVD has the same optimal set as \inf_{\mathbf{U}^{T}\mathbf{U}=\mathbf{I}}\left|\left|\bm{\mathcal{S}}-\llbracket\mathbf{U}{},\mathbf{U}{},\mathbf{AB}{}\rrbracket\right|\right| where \bm{\mathcal{S}}_{::k}:=\mathbf{S}^{(k)} , \mathbf{A}:=\mathbf{1} and \mathbf{B}:=\mathbf{1}^{T} . Lastly, note that due to the close connection of ( 1.4 ) and its variant with MC-TR-I-EVD, one can argue that the same reformulation captures the essence of these problems as well. 2 Proposed Method. In this section, we develop GenClus, a principled