Chakib Fettal
email: chakib.fettal@etu.u-paris.fr

Lazhar Labiod
email: lazhar.labiod@u-paris.fr

Mohamed Nadif
email: mohamed.nadif@u-paris.fr

Subspace Co-clustering with Two-Way Graph Convolution

Keywords: Information systems → Clustering Co-clustering, Subspace Clustering, Subspace Co-clustering, Attributed Graphs, Text mining

INTRODUCTION AND BACKGROUND

Subspace clustering [START_REF] Parsons | Subspace clustering for high dimensional data: a review[END_REF] is an unsupervised problem where one wishes to group points according to the subspaces in which they lie. There have been a variety of approaches to solve the problem, a lot of which consider the self-expressive formulation where it is assumed that each element can be written as a linear combination of Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. CIKM '22, October 17-21, 2022, Atlanta, GA, USA © 2022 Association for Computing Machinery. ACM ISBN 978-1-4503-9236-5/22/10. . . $15.00 https://doi.org/10.1145/3511808.3557706 the elements in the that subspace. Typically, the generic formulation is given as

min R ∥ X -RX ∥ 2 + Ω (R) s.t. R ∈ R (1)
where X ∈ R 𝑛×𝑑 is a matrix of 𝑑-dimensional data points, R ∈ R 𝑛×𝑛 is called the self-representation matrix, Ω(R) serves as a regularization term to induce desirable properties on R and avoid trivial solutions (such as R = I), and R is the feasible region.

After finding an optimal solution R * , an affinity matrix is generated based on the magnitudes of the entries of R * , usually using |R * + R * ⊤ |/2, and a partition of the points is then generated using a graph clustering method e.g. the spectral clustering algorithm [START_REF] Shi | Normalized cuts and image segmentation[END_REF].

Subspace clustering methods based on the self-expressive property [START_REF] Zhang | Learning a self-expressive network for subspace clustering[END_REF] have been widely used to cluster image datasets due the assumption that image datasets are often drawn from multiple low-dimensional subspaces. One of the earlier approaches was the least-square regression (LSR) subspace clustering [START_REF] Lu | Robust and efficient subspace segmentation via least squares regression[END_REF] that leverages a grouping effect based on the correlation of the data to do the segmentation. More sophisticated approaches that make up the state-of-the-art for proposed were later proposed such as the Elastic-net Subspace Clustering (EnSC) [START_REF] You | Oracle based active set algorithm for scalable elastic net subspace clustering[END_REF] and the subspace clustering through the orthogonal matching pursuit (SSC-OMP) [START_REF] You | Scalable sparse subspace clustering by orthogonal matching pursuit[END_REF]. However, despite text data also fulfilling this assumption, to the best of our knowledge, no self-expressive subspace clustering approach specifically tailored to text has been proposed. This can perhaps be explained by the fact that document-term datasets are usually much larger and sparser than image datasets and thus each individual data point could potentially lie in a unique subspace.

In this paper we propose a subspace clustering model tailored for document-term matrices through the concept of co-clustering i.e. using the interplay between rows and columns, or in the context of text, the interplay between documents and terms to generate a segmentation for both of them. We also propose a way to overcome the possible problem of each document/term lying in a unique subspace through using a two-way graph convolution that consists of a weighted Laplacian smoothing preprocessing step inspired by the simple graph convolutional network [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF][START_REF] Thomas | Semi-supervised classification with graph convolutional networks[END_REF][START_REF] Wu | Simplifying graph convolutional networks[END_REF].

PROPOSED METHOD

Notation. Matrices are denoted with boldface uppercase and vectors with boldface lowercase letters. Given a matrix X, its 𝑖-th row is denoted by x 𝑖 and its 𝑗-th column by x ′ 𝑗 . I 𝑛 is the identity matrix of size 𝑛. The Frobenius norm is denoted by ∥.∥. 𝑘 and 𝑔 denote the number of row and column clusters. Function [U, Σ, V] = SVD(X) gives the singular value decomposition of matrix X where U and V are the left and right singular vectors and Σ is the diagonal matrix containing the singular values, sorted in decreasing order.

Self-Expressive Subspace Co-clustering

The advantage of co-clustering [START_REF] Govaert | Co-clustering: models, algorithms and applications[END_REF] is that it makes use of the inherent duality between the rows and columns of data tables which can lead to improvement in partitioning along both dimensions. For example, in the case of the document term matrices [START_REF] Affeldt | Ensemble block co-clustering: a unified framework for text data[END_REF][START_REF] Affeldt | Regularized Dual-PPMI Co-clustering for Text Data[END_REF][START_REF] Govaert | Mutual information, phi-squared and model-based co-clustering for contingency tables[END_REF][START_REF] Nadif | Unsupervised and self-supervised deep learning approaches for biomedical text mining[END_REF][START_REF] Salah | Word co-occurrence regularized non-negative matrix tri-factorization for text data co-clustering[END_REF], co-clustering incorporates term space information to do the document partitioning and vice-versa. Motivated by this observation, given a document-term matrix X ∈ R 𝑛×𝑑 + , we formulate the subspace co-clustering problem as min

R,C ∥ X -RXC ∥ 2 + Ω(R, C) s.t. R ∈ R, C ∈ C (2)
where R ∈ R 𝑛×𝑛 and C ∈ R 𝑑×𝑑 are respectively the row and column self-representation matrices, Ω(R, C) is the regularization term where the regularization of R and C can either be independent i.e. Ω(R, C) = Ω R (R) + Ω C (C) or dependant, R and C are the feasible regions.

Promoting the Grouping Effect Through a Two-way Graph Convolution

Some subspace clustering methods [START_REF] Hu | Smooth representation clustering[END_REF][START_REF] Lu | Correlation adaptive subspace segmentation by trace lasso[END_REF][START_REF] Lu | Robust and efficient subspace segmentation via least squares regression[END_REF] ascribe the performance of their clustering to the grouping effect. Definition (Grouping Effect): Given a data matrix X, a selfrepresentation matrix R has a grouping effect if

∀𝑖 ≠ 𝑗, ∥x 𝑖 -x 𝑗 ∥ 2 → 0 =⇒ ∥r 𝑖 -r 𝑗 ∥ 2 → 0.
This could pose a problem in the case of text because of its high dimensionality and sparsity as data points may not be sufficiently "close" in the sense of the self-expressive property to be grouped in a meaningful way. This means data points need some sort of smoothing to help subspace clustering algorithms to find common subspaces. We propose to solve this problem through a two-way graph convolution. This requires two similarity matrices that will act as graphs on the rows S R and columns S C . These matrices can either be constructed through some similarity measure on the data or be provided a priori, e.g. in the case of attributed graphs.

An intuition can be drawn from the fact that the rows and columns of S 𝑝 R XS 𝑞 C , as propagation orders 𝑝, 𝑞 grow, are getting smoother by being averaged up to their 𝑝-th and 𝑞-th neighbors respectively akin to Laplacian smoothing. This operation thus makes the rows and columns more and more similar. Trough the grouping property this implies that the self-representation vectors should also be getting more similar, leading to a more meaningful partitioning.

The challenge is to choose suitable propagation orders since large values can cause over-smoothing and make all data points look similar. Our problem becomes min

R,C S 𝑝 R XS 𝑞 C -R S 𝑝 R XS 𝑞 C C 2 + Ω(R, C) s.t. R ∈ R, C ∈ C. (3)
In what follows, we will refer to the smoothed matrix S 𝑝 R XS 𝑞 C using H since this operation can be considered as a sort of data preprocessing step, independent from the clustering model. Note that the complexity of this operation is in O (𝑝 ∥S R ∥ 0 + 𝑞∥S C ∥ 0 ) where ∥.∥ 0 is the 0-norm that gives the number of non-zero entries of its input.

Subspace Co-clustering through LSR

We propose an initial variant based on the LSR subspace clustering model where we define the regularization term as follows Ω(R, C) = 𝜆 R ∥R∥ 2 + 𝜆 C ∥C∥ 2 where 𝜆 R and 𝜆 C are parameters that regulate the trade-off between the reconstruction term and the regularizer. The formulation of the problem becomes min

R,C ∥H -RHC∥ 2 + 𝜆 R ∥R∥ 2 + 𝜆 C ∥C∥ 2 . ( 4
)
By fixing R and solving for C and inversely, a closed form solution can be obtained for both matrices where we can explicitly see how our model uses information from the columns for the row space partitioning and vice-versa

R = HC ⊤ H ⊤ HCC ⊤ H ⊤ + 𝜆 R I -1 C = H ⊤ R ⊤ RH + 𝜆 C I -1 H ⊤ R ⊤ H. (5)
However, solving the problem requires an iterative process where we alternatively fix one of R and C and update the other until convergence. The overall computational complexity is

O (𝑛 3 + 𝑑 3 + 𝑡𝑛𝑑 2 + 𝑡𝑛 2 𝑑),
where 𝑡 is the number of iterations, and the spatial complexity is O (𝑛 2 +𝑑 2 ), which is prohibitive for a lot of real world applications.

A More Efficient Formulation Through Orthogonality Constraints

To address the issue of complexity we propose to introduce the following constraints R = ZZ ⊤ and C = WW ⊤ where Z ∈ R 𝑛×𝑘 and W ∈ R 𝑑×𝑔 are semi-orthogonal i.e. Z ⊤ Z = I 𝑘 and W ⊤ W = I 𝑔 . With these constraints the problem becomes simpler due to fact that ∥Z∥ 2 = rank(Z) and ∥W∥ 2 = rank(W). The new formulation of the problem is min

Z,W ∥H -ZZ ⊤ HWW ⊤ ∥ 2 s.t. Z ⊤ Z = I 𝑘 , W ⊤ W = I 𝑔 (6)
At first glance this problem also requires an alternating solving scheme using two update rules that we obtain by fixing W and solving for Z and vice versa

Z = [u ′ 1 , . . . , u ′ 𝑘 ] s.t. [U, Σ, V] = SVD(HW) W = [u ′ 1 , . . . , u ′ 𝑘 ] s.t. [U, Σ, V] = SVD(H ⊤ Z). (7)
This entails that 𝑔 = 𝑘. The detailed pseudo-code for this method is given in algorithm 1, its spatial complexity is the same as for LSR but the computational complexity is in O (𝑛 3 +𝑑 3 + 𝑡𝑛𝑑 log(𝑘)), which is faster. All in all, the approach still remains quite inefficient.

Efficient computation of Z * and W * . The previous problem can be efficiently solved using a single truncated SVD. This is a consequence of the following proposition.

Proposition 1. The alternating process defined in system of [START_REF] Fettal | Efficient Graph Convolution for Joint Node Representation Learning and Clustering[END_REF] converges to Z and W being the left and right truncated singular vectors of H respectively. This results in a more efficient algorithm since we circumvent the iterative step. However, the interaction between rows and columns implicitly remains since the resulting solution is also a solution to the aforementioned alternating optimization problem where the interaction is explicit.

; W ← W 𝑖𝑛𝑖𝑡 ; while not converged do Z ← [u ′ 1 , . . . , u ′ 𝑘 ] s.t. [U, _, _] ← SVD(HW); W ← [u ′ 1 , . . . , u ′ 𝑘 ] s.t. [U, _, _] ← SVD(H ⊤ Z); end R, C ← ZZ ⊤ , WW ⊤ ;
Generate 𝜋 R , 𝜋 C through spectral clustering on |R| and |C|;

Proof. Suppose, without loss of generality, that 𝑘 ≤ rank(H). We have that 𝑘 = rank(Z) = rank(W) implying rank ZZ ⊤ HWW ⊤ ≤ 𝑘.

This means that we are looking for the best 𝑘-rank approximation.

Given [U, Σ, V] = SVD(H), by setting Z = U 𝑘 = [u ′ 1 , . . . , u ′ 𝑘 ] and W = V 𝑘 = [v ′ 1 , . . . , v ′ 𝑘 ]. We have that ∥H -ZZ ⊤ HWW ⊤ ∥ 2 = ∥H -U 𝑘 U ⊤ 𝑘 UΣV ⊤ V 𝑘 V ⊤ 𝑘 ∥ 2 = ∥H -[U 𝑘 , 0]Σ[V 𝑘 , 0] ⊤ ∥ 2 = ∥H -U 𝑘 Σ 𝑘 V ⊤ 𝑘 ∥ 2 (8)
which according to the Eckart-Young-Mirsky theorem is the optimal value of the rank-𝑘 approximation problem of H. □ From the previous result, we can show that our approach has an approximate grouping effect Proposition 2. Given matrix H, the solutions R and C display a grouping effect on matrix H, the best rank-𝑘 approximation of H,

since z 𝑖 = Σ -1 𝑘 W ⊤ h𝑖 and w 𝑖 = Σ -1 𝑘 Z ⊤ h′ ⊤ 𝑖 .
Efficient Spectral Clustering from R * and C * . The optimal coefficient matrix R * = Z * Z * ⊤ is symmetric by construction, however its entries are not necessarily nonnegative which implies having to use element-wise absolute value to obtain a valid affinity matrix. This would destroy all information we already have on the decomposition of R * into Z * Z * ⊤ since generally there is no relation between the spectrum of a matrix and its spectrum after applying an entrywise function. We circumvent this problem by instead considering affinity matrix K R = (𝑟 𝑖 𝑗 + 1) 2 𝑖 𝑗 . We thus have that K R = ⟨𝜑 (Z * ), 𝜑 (Z * )⟩ where 𝜑 is a the feature map for the second degree polynomial kernel K R applied on the row vectors of Z i.e.

𝜑 (z) = ⟨𝑧 2 𝑘 , . . . , 𝑧 2 1 , √ 2𝑧 𝑘 𝑧 𝑘-1 , . . . , √ 2𝑧 𝑘 𝑧 1 , √ 2𝑧 𝑘-1 𝑧 𝑘-2 , . . . , √ 2𝑧 𝑘-1 𝑧 1 , . . . , √ 2𝑧 2 𝑧 1 , √ 2𝑧 𝑘 , . . . , √ 2𝑧 1 , 1⟩ (9)
with 𝜑 : R 𝑘 → R 𝑘+2 2 . Any feature map for an entrywise nonnegative kernel is a possible alternative. We chose the simplest exact feature map possible here since the transformation does not result in too much of a dimensionality increase for the inputs as 𝑘 << 𝑛, 𝑑.

Approximations can be used in order to work with otherwise infinite dimensional feature map kernels e.g. the RBF kernel. We then propose to perform the spectral clustering directly on the affinity matrix instead of the Graph Laplacian as in [START_REF] Sarkar | Quantitative measures of change based on feature organization: Eigenvalues and eigenvectors[END_REF]. Since the eigenvectors of K R are the same as the left singular vectors of 𝜑 (Z * ) the process is much faster since 𝑘 << 𝑑. To obtain a clustering from C * , the operations are the same. The overall computation complexity is then in O (𝑛𝑑 + 𝑛𝑘 2 + 𝑑𝑘 2 ) log(𝑘) while the spatial one is in O 𝑛𝑘 2 + 𝑑𝑘 2 .

EXPERIMENTS 3.1 Experimental Setup

Datasets. We use four attributed graph citation networks, which are graphs characterized by an adjacency matrix A and a node features matrix X. The summary statistics are available in table 2. Comparative models. We compare our model to clustering and co-clustering models that either use only the input node feature matrix X or that use both A and X i.e. attributed graph clustering/coclustering models.

• Vanilla clustering models. The 𝑘-means algorithm is our baseline.

• Subspace clustering models. We also use the aforementioned subspace clustering LSR, EnSC and SSC-OMP models. • Attributed graph clustering models. We use GIC [START_REF] Mavromatis | Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs[END_REF] where clustering is done by maximizing the mutual information between nodes contained in the same cluster, AGE [START_REF] Cui | Adaptive graph encoder for attributed graph embedding[END_REF] proposes a Laplacian smoothing filter that acts as a low-pass filter applied in adaptive learning scheme, S2GC [START_REF] Zhu | Simple Spectral Graph Convolution[END_REF] proposes a method for the aggregation of K-hop neighborhoods that is a trade-off of low-and high-pass filter bands, and GCC [START_REF] Fettal | Efficient Graph Convolution for Joint Node Representation Learning and Clustering[END_REF] which proposes a simultaneous representation learning and clustering scheme for nodes. • Vanilla co-clustering models. We compare the model to the spectral co-clustering algorithm [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] and the DCC [START_REF] Salah | Model-based von mises-fisher coclustering with a conscience[END_REF] which is based on a regularized von Mises-Fisher mixture model. • Attributed graph co-clustering Models. The only such model is CFOND [START_REF] Guo | CFOND: consensus factorization for co-clustering networked data[END_REF], a consensus factorization model that simultaneously factorizes information from three aspects: network topology structures, instance-feature content relationships, and feature-feature correlations.

Experimental settings. For our method, we use as our row graph, the adjacency matrix provided in the datasets S R = A.

For the columns, we use

S C = max log C .. C 𝑖. C .𝑗 𝑐 𝑖 𝑗 , 0 𝑖 𝑗
where C = X ⊤ X, which is the nonnegative pointwise mutual information [START_REF] Church | Word association norms, mutual information, and lexicography[END_REF] matrix of the terms; Intuitively 𝑠 C𝑖 𝑗 gives the semantic relatedness of term 𝑖 and 𝑗, the larger the value, the more these terms are related. Both matrices are then added self-loops and normalized as in [START_REF] Fettal | Efficient Graph Convolution for Joint Node Representation Learning and Clustering[END_REF]. The row propagation order 𝑝 is selected using the selection rule proposed in [START_REF] Fettal | Efficient Graph Convolution for Joint Node Representation Learning and Clustering[END_REF], while for the column one we set 𝑞 = 1. We perform ten runs for each model. We use the author provided implementation and parameters when available. For models that use a parameter 𝑝 like ours, we run their proposed selection rule until convergence with no maximum 𝑝 specified, for fairness. All experiments were performed on the same machine.

Document Clustering

We compare the methods on document clustering using the Clustering Accuracy (Acc), Normalized Mututal Information (NMI) and Adjusted Rand Score (ARI) metrics. Table 1 shows the performance of the different models. Methods that use both graph structure and features outperform methods that use the node features only except on ACM where the graph is not informative (most entries are set to one), we used this dataset to show the robustness of our model in the face of uninformative graph structure compared to state of the art attributed graph clustering models. We see that our approach is competitive and outperforms other models on all datasets in terms of accuracy. It also has near zero standard deviation on most metrics which is a sign of robustness. We report in table 3 the training times of our algorithm compared to other subspace clustering models. We can see that our subspace clustering approach is faster in the different datasets by significant margins even though it generates a clustering for both rows and columns.

Term Clustering

Co-clustering models additionally generate a clustering for the terms. Since the PubMed dataset is the only one for which we 4 presents the most frequent terms for each topic found by our model. The PubMed dataset contains scientific papers concerning diabetes. We see that topic 𝑎 contains terms that are related to a presentation of diabetes, e.g, insulin, glucos, type, etc. Topic 𝑏 has terms that are related to the microscopic effects of diabetes such as cell, islet, gene, betacel, and so on. Finally, topic 𝑐 seems to concern terms that are associated with medical experimentation and analysis of results such as control, increas, signific, etc. We note the coherence of these term clusters since they cluster the PubMed paper contents according to three topics. This term clustering can then be used to help characterize document clusters to facilitate interpretation (for more details, see [START_REF] Marcotorchino | Block seriation problems: A unified approach. Reply to the problem of H. Garcia and JM Proth[END_REF]).

CONCLUSION

We proposed SCC, a new approach to leverage subspace clustering for text data through co-clustering and two-way graph convolution. It circumvents the computational and spatial complexity issues of subspace clustering through using factor matrices and nonnegative kernel feature maps. Experiments showed that our model is competitive with the state of the art for attributed graph node clustering in terms of performance and robustness.

Algorithm 1 :

 1 Naive SCC Input : X data matrix, S R and S C row and column prop. matrices, 𝑝 and 𝑞 row and column prop. orders, 𝑘 number of co-clusters Output : R and C the row and column self-representation matrices, 𝜋 R and 𝜋 C row and columns partitions H ← S 𝑝 R XS 𝑞 C

Table 2 :

 2 Dataset statistics.

	Dataset	#Nodes #Edges #Features #Classes
	ACM [24]	3025 9150593	1870	3
	CiteSeer [22] 3327	4732	3703	6
	PubMed [22] 19717 44338	500	3
	Wiki [26]	2405	17981	4973	17

Table 1 :

 1 Clustering performance on the datasets averaged over ten runs. The best results are highlighted in bold. Our model is competitive with the state-of-the-art as it has the best results on most datasets while having small standard deviations.

	Method	Input		ACM			CiteSeer			PubMed			Wiki
			Acc	NMI	ARI	Acc	NMI	ARI	Acc	NMI	ARI	Acc	NMI	ARI
	𝑘-means	X	62.8±4.8 37.2±9.2 34.5±10.4 62.5±1.6 36.7±1.9 35.5±2.5 60.1±0.0 31.4±0.0 28.1±0.0 47.3±6.0 46.3±6.9 26.4±8.1
	LSR	X	80.3±0.0 47.0±0.0 51.9±0.0 21.1±0.0 0.2±0.1 0.0±0.0		OOM		21.1±3.3 9.0±5.9 2.6±2.0
	EnSC	X	79.5±0.0 46.8±0.0 50.3±0.0 55.6±0.0 14.8±0.0 14.6±0.0 55.6±0.0 14.8±0.0 14.7±0.0 45.5±2.0 45.7±1.7 28.8±1.3
	SSC-OMP X	78.8±0.1 43.4±0.1 48.3±0.1 24.0±1.1 3.5±0.4 1.8±0.1 60.4±0.0 22.3±0.0 19.4±0.0 52.7±4.4 48.1±2.3 33.3±1.5
	Spectral	X	80.6±0.1 48.4±0.1 52.3±0.1 30.3±1.7 10.0±1.3 5.5±1.6 61.2±0.0 24.7±0.0 21.8±0.0 37.8±1.2 38.2±0.3 20.8±0.4
	DCC	X	40.5±3.3 7.8±5.1 2.1±2.2 35.1±3.8 11.5±2.4 8.9±2.9 54.3±3.6 16.5±2.9 13.4±4.1 48.3±3.6 47.5±2.6 30.6±3.0
	GIC	A, X 34.3±0.4 0.1±0.1 0.0±0.0 68.8±0.8 43.8±1.0 44.6±1.0 64.3±0.4 26.0± 0.5 23.6±0.5 46.5±1.4 48.2±0.5 30.2±1.4
	S2GC	A, X 40.5±3.4 1.7±1.2 1.8±1.3 68.1±0.3 42.3±0.2 43.5±0.3 70.8±0.0 32.5±0.0 33.2±0.0 52.7±1.0 49.0±0.3 29.6±0.9
	GCC	A, X 35.4±0.0 0.3±0.0 0.0±0.0 69.4±0.1 45.0±0.2 45.4±0.1 70.8±0.0 32.3±0.0 33.2±0.0 54.1±0.8 55.0±0.2 33.3±0.5
	CFOND	A, X 71.8±0.6 37.2±0.5 38.2±0.7 63.0±1.1 36.6±1.3 36.2±1.2 60.1±0.0 31.4±0.0 28.1±0.0 47.8±3.0 49.5±2.1 30.3±2.5
	SCC	A, X 81.4±0.0 50.0±0.0 53.9±0.0 69.5±0.0 43.5±0.0 43.7±0.0 70.9±0.0 31.7±0.0 33.2±0.0 59.3±0.6 53.9±0.9 32.7±1.4

Table 3 :

 3 Training times in seconds of the different subspace clustering models averaged over ten runs. Ours is the fastest one on all datasets.

	Method	ACM CiteSeer PubMed Wiki
	ENSC	1395.9 405.2	1416 1447.2
	SSC-OMP 168.0	263.4	1447	237.5
	LSR	21.5	157.7	OOM	21.1
	SCC	9.7	7.4	28.9	8.8

Table 4 :

 4 The three topics found by SCC characterized by their top ten most frequent terms. the actual terms, we performed the term clustering solely on it. Table

	Topic a Topic b Topic c
	patient	cell	rat
	insulin	mice control
	glucos	islet	activ
	type	iddm	level
	group	gene	increas
	subject	diseas respons
	lt	develop signific
	risk	nod	effect
	associ children express
	treatment betacel plasma
	managed to find


Chakib Fettal

Lazhar Labiod

Mohamed Nadif

Boosting Subspace Co-Clustering via Bilateral Graph Convolution

Boosting Subspace Co-clustering via Bilateral Graph Convolution

Chakib Fettal, Lazhar Labiod, and Mohamed Nadif

Abstract-Subspace clustering seeks to cluster high-dimensional data lying in a union of low-dimensional subspaces. It has achieved state-of-the-art results in image clustering, but text clustering of document-term matrices, has proved more impervious to advances with this approach, even though text data satisfies the assumptions of subspace clustering. We hypothesize that this is because such matrices are generally sparser and higher-dimensional than images. This, combined with the complexity of subspace clustering, which is generally cubic in the number of inputs, makes its use impractical in the context of text. Here we address these issues with a view to leveraging subspace clustering for networked (or not) text data. We first extend the concept of subspace clustering to co-clustering, which is suitable to deal with document-term matrices because of the interplay engendered between the document and word representations. We then address the sparsity problem through bilateral graph convolution, which promotes the grouping effect that has been credited for the effectiveness of some subspace clustering models. The proposed formulation results in an algorithm that is computationally/spatially efficient. Experiments using real-world datasets demonstrate the superior performance, in terms of document clustering, word clustering, and computational efficiency, of our proposed approach over the baselines and comparable methods.

Index Terms-Co-clustering, Subspace Clustering, Attributed Graphs ✦

INTRODUCTION

As the datasets become more and more larger and can be in addition more sparse, adaptations to existing clustering algorithms are required to maintain cluster quality. In fact, this quality can greatly suffer in the high dimensional data where many of dimensions are often irrelevant. This appears in many applications including recommendation systems, microarray or even textual data represented as documentterm matrices. In the text area, the task of text clustering is always important and has many use cases including fake news detection, sentiment analysis information retrieval and so on; see for instance [START_REF] Aggarwal | A survey of text clustering algorithms[END_REF] for more applications. Thereby subspace clustering [START_REF] Parsons | Subspace clustering for high dimensional data: a review[END_REF] and biclustering/co-clustering [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], [START_REF] Riverain | Semi-supervised latent block model with pairwise constraints[END_REF] techniques have shown that can leveraged to uncover the complex relationships found in such data. Subspace clustering is an unsupervised learning method in which points are to be grouped according to the subspaces in which they lie. A variety of approaches have been used to solve this problem, and a number of these approaches are based on a self-expressive formulation where it is assumed that each element can be written as a linear combination of the elements in the subspace. Based on a selfexpressive formulation, subspace clustering methods have been widely used to cluster image datasets, given that image datasets will often be drawn from multiple low-dimensional subspaces, and state-of-the-art clustering results have in many cases been obtained. Regarding text data, however, to the best of our knowledge no self-expressive subspace clustering approaches have been proposed that are specifically tailored to text, although the assumption made in relation to image data applies equally to text data. We argue that this discrepancy between image and text stems from two causes:

• Complexity. Document-term datasets are usually very large, much more so than images, which makes it pro-hibitive to use subspace clustering algorithms whose computational complexity is usually in O(n 3 ), and whose spatial complexity is in O(n 2 ). • Sparsity. Document-term datasets are sparser than image datasets, and each individual data point may thus potentially lie in a unique subspace, making it difficult for subspace clustering algorithms to group points meaningfully.

In this paper we propose a subspace clustering model tailored for networked (and non-networked) text data based on the principle of co-clustering (or biclustering), that is to say using the interplay between rows and columns [START_REF] Govaert | Co-clustering: models, algorithms and applications[END_REF]. In the context of text, this consists in harnessing the interplay between the set of documents and the set of terms to jointly generate a partitioning for both of them. This leads to reorganize the initial data matrix into a new one that is reorganized into homogeneous co-clusters/biclusters. The choice of the co-clustering approach is justified for at least four reasons a) co-clustering overcomes the curse of dimensionality and sparsity; by alternatingly updating the row partition given the column partition and vice versa the clustering can be performed in lower dimensional space and therefore more parsimonious than one-sided clustering performed on the row or column sets separately [START_REF]Block clustering with bernoulli mixture models: Comparison of different approaches[END_REF] b) the clusters/co-clusters tend to be more easily interpretable, allowing the user to better direct further study [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], [START_REF] Salah | Word co-occurrence regularized non-negative matrix tri-factorization for text data coclustering[END_REF], [START_REF] Fettal | Efficient and effective optimal transport-based biclustering[END_REF] c) fuzzy co-clustering can be easily deduced from many coclustering methods [START_REF] Govaert | Co-clustering: models, algorithms and applications[END_REF] allowing, for instance, to assign a document/term to several classes, and finally d) in terms of topic modelling, the obtained results from co-clustering are in line with the human judgment, outperforming, in general, the conventional LDA (Allocation Dirichlet Allocation) method [START_REF] Jelodar | Latent dirichlet allocation (lda) and topic modeling: models, applications, a survey[END_REF]; see for instance [START_REF] Ailem | Model-based co-clustering for the effective handling of sparse data[END_REF]. In this regard, other researchers emphasize that sparse datasets are not suitable for LDA [START_REF] Chen | Experimental explorations on short text topic mining between lda and nmf based schemes[END_REF].

In our approach, we address the two major issues that are inherent to subspace clustering on text data: complexity and sparsity. To this end, we use factorized representation matrices and nonnegative kernel feature maps, as well as a bilateral graph convolution that includes a weighted Laplacian smoothing preprocessing step, having similarities with a simple graph convolutional network [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF], [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF], [START_REF] Wu | Simplifying graph convolutional networks[END_REF]. Second, combining subspace and co-clustering, we propose an efficient extension to [START_REF] Fettal | Scalable attributed-graph subspace clustering[END_REF] to co-clustering and expand the proposal presented in [START_REF]Subspace co-clustering with two-way graph convolution[END_REF]. This makes our model particularly well suited to clustering attributed graphs whose nodes and/or edges have attributes or features. This leads to tackle networked text data/text attributed graphs that are used to model a wide variety of real-world networks such as in recommender systems [START_REF] Fan | Graph neural networks for social recommendation[END_REF], citation networks [START_REF] Sen | Collective classification in network data[END_REF] and so on. We summarize our contributions as follows:

• We study how the Laplacian smoothing operation boosts the grouping effect of subspace clustering approaches that possess this property. • Unlike the iterative process generally adopted in coclustering, we show here that in our formulation of the self-expressive subspace co-clustering problem the optimal solution can be derived from a single truncated singular value decomposition, which makes it efficient (linear complexity in the number of nodes). • We carry out extensive experimentation on text attributed graphs where the graphs exist on the one hand and when the graphs are generated from the node features on the other using k-nearest neighbor graphs. This allows to demonstrate the flexibility and value of the proposed model, in terms of document /word clustering capability and computational efficiency. • Making the code available for download to ensure reproducibility of the results 1 . The remainder of this paper is structured as follows. Section 2 discusses related works. Section 3 develops our proposed method SC 3 , and section 4 discusses the algorithm and its complexity. Section 5 contains a detailed description of our experiments. Finally, we give our conclusion in section 6.

RELATED WORKS

Our contributions can be seen as being at the intersection between subspace clustering, co-clustering, and attributed graph clustering.

Self-expressive Subspace Clustering

Among the earliest approaches was Least Squares Regression (LSR) subspace clustering [START_REF] Lu | Robust and efficient subspace segmentation via least squares regression[END_REF], which leverages a grouping effect based on the correlation of data. More sophisticated approaches that represent today's state of the art were later proposed, such as Elastic-net Subspace Clustering (EnSC) [START_REF] You | Oracle based active set algorithm for scalable elastic net subspace clustering[END_REF], subspace clustering by Orthogonal Matching Pursuit (SSC-OMP) [START_REF] You | Scalable sparse subspace clustering by orthogonal matching pursuit[END_REF], the ℓ 0 -norm regularized subspace clustering (ℓ 0 -SCC) [START_REF] Yang | Subspace learning by l0-induced sparsity[END_REF] and its recent extension that deals with noisy data (Noisy-DR-ℓ 0 -SCC-LR) [START_REF] Yang | Noisy l0-sparse subspace clustering on dimensionality reduced data[END_REF]. Some 1. https://github.com/chakib401/sc3 recent works have proposed efficient methods such as K-Factorization Subspace Clustering (K-FSC) [START_REF] Fan | Large-scale subspace clustering via k-factorization[END_REF] and others were created to deal with multi-view data [START_REF] Wang | Unsupervised metric fusion over multiview data by graph random walk-based cross-view diffusion[END_REF], [START_REF] Wang | Multiview spectral clustering via structured low-rank matrix factorization[END_REF], [START_REF] Wang | Beyond low-rank representations: Orthogonal clustering basis reconstruction with optimized graph structure for multi-view spectral clustering[END_REF]. Some models like the GAN-Based Enhanced Deep Subspace Clustering Networks [START_REF] Yu | Gan-based enhanced deep subspace clustering networks[END_REF] explicitly make the assumption of dealing with image data. Note that deep self-expressive subspace clustering models have received criticism over the necessity of a neural network component [START_REF] Haeffele | A critique of self-expressive deep subspace clustering[END_REF].

Co-clustering

Co-clustering seeks to form co-clusters which are sets of homogeneous sets of rows and columns. It harnesses the inherent duality between the rows and columns of data tables, which can lead to improvements in partitioning for both dimensions. For example, in the case of document-term matrices, co-clustering incorporates term space information that is used in the document partitioning, and vice versa. A popular method is by alternatingly finding a clustering for the rows while taking into consideration the current clustering of columns, and inversely. One of the first coclustering approaches was the spectral co-clustering algorithm [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF]. Directional Co-clustering with Constraints (DCC) [START_REF] Salah | Model-based von mises-fisher coclustering with a conscience[END_REF] is based on a regularized von Mises-Fisher mixture model that makes it suitable for balanced text datasets. Regularized Dual-PPMI Co-clustering (RDPCo) [START_REF] Affeldt | Regularized dual-ppmi coclustering for text data[END_REF] extends DCC to incorporate both word-word semantic relationships and document-document similarities into the procedure (see [START_REF] Govaert | Co-clustering: models, algorithms and applications[END_REF] for a review). Finally, Consensus Factorization for Co-Clustering Networked Data (CFOND) [START_REF] Guo | Cfond: consensus factorization for co-clustering networked data[END_REF] is a consensus factorization model that factorizes information simultaneously from three sources: network topology structures, instance-feature content relationships, and feature-feature correlations.

Attributed Graph Clustering

Attributed Graph clustering involves grouping nodes into clusters depending on the structure of the graph and nodelevel features. In Graph-InfoClust (GIC) [START_REF] Mavromatis | Graph infoclust: Maximizing coarse-grain mutual information in graphs[END_REF] clustering is done by maximizing the mutual information between nodes contained in the same cluster. Simple Spectral Graph Convolution (S²GC) [START_REF] Zhu | Simple spectral graph convolution[END_REF] is a method for the aggregation of K-hop neighborhoods that is a trade-off between low-and highpass filter bands. Graph Convolutional Clustering (GCC) [START_REF] Fettal | Efficient graph convolution for joint node representation learning and clustering[END_REF] is a procedure that simultaneously clusters and learns clustering-friendly representations of nodes. In addition, CFOND, mentioned above in relation to co-clustering, is also considered to be an attributed graph clustering model.

PRELIMINARIES AND BACKGROUND

Matrices are denoted using boldface uppercase, and vectors using boldface lowercase letters. Given a matrix X, its ith row is denoted as x i and its j-th column as x ′ j . I n is the identity matrix of size n. The Frobenius norm is denoted as ∥.∥. rk gives the rank of a matrix. Function [U, Σ, V] = SVD(X) gives the compact singular value decomposition of matrix X ∈ R n×d , where U ∈ R n×rk(X) and V ∈ R d×rk(X) have the left and right singular vectors in their columns and Σ ∈ R rk(X)×rk(X) is the diagonal matrix containing the singular values, sorted in decreasing order.

We also define function [U, Σ, V] = TruncatedSVD(X, k) that returns the first (largest) k singular values, and the left and right singular vectors. Function diag creates a diagonal matrix from a vector input, while 1 denotes a vector of ones.

Self-Expressive Subspace Clustering

Given a X ∈ R n×d a matrix of d-dimensional data points. The self-expressive subspace clustering is typically formulated as

min R ∥ X -RX ∥ 2 + Ω (R) such that R ∈ R (1)
where R ∈ R n×n is known as the self-representation matrix, Ω(R) serves as a regularization term designed to establish certain properties for R so as to avoid trivial solutions (such as R = I), and R is the feasible region. After an optimal solution R * has been obtained, an affinity matrix is first generated based on the magnitudes of the entries in R * , usually using |R * + R * ⊤ |/2, and a partition of the points is then generated using a graph clustering method such as the spectral clustering algorithm [START_REF] Shi | Normalized cuts and image segmentation[END_REF].

Block seriation

Co-clustering can be posed as a block seriation problem [START_REF] Marcotorchino | Block seriation problems: A unified approach. reply to the problem of h. garcia and jm proth (applied stochastic models and data analysis[END_REF] whose objective is finding a block diagonal matrix R ∈ R n×d that identifies co-clusters.

The block seriation problem can be stated as this integer program:

max R ij x ij r ij (2)
subject to:

∀ i, j r ij ∈ {0, 1} Binarity ∀ i, j, i ′ , j ′ r ij + r ij ′ + r i ′ j ′ -r i ′ j ≤ 2 r i ′ j ′ + r i ′ j + r ij -r ij ′ ≤ 2 r i ′ j + r ij + r ij ′ -r i ′ j ′ ≤ 2 r ij ′ + r i ′ j ′ + r i ′ j -r ij ≤ 2          No triads ∀ j i r ij ≥ 1 ∀ i j r ij ≥ 1    Assignment
The solution R is always block diagonal up to a permutation of the rows and columns. An equivalent formulation consists in factorizing R using two assignment matrices Z and W:

max Z,W ij x ij z ⊤ i w j ≡ trace(Z ⊤ XW) (3)
s.t. Z ∈ {0, 1} n×k , Z1 = 1 (4) W ∈ {0, 1} d×k , W1 = 1 (5)
For example, a simple heuristic for solving this problem consists in using block coordinate descent, to iteratively solve for the row assignments while the column assignments, and vice versa. This approach shows, how given a clustering of the rows and columns, it is possible to obtain a diagonal co-clustering of the data matrix [START_REF] Laclau | Diagonal latent block model for binary data[END_REF].

Neighborhood Propagation & Graph Convolutional Networks

let G = (A, X) be an input attributed graph, with A the adjacency and X the node features. The graph convolutional network (GCN) consists of the following step repeated for each layer

H (l+1) ← σ SH (l) W such that H (0) ← X
where σ is some activation function, W are learnable weights that depend on the task at hand, and S is a normalized version of A with self-loops added. The simplified version, on the other hand, uses a GCN with linear activations and no weights. For example, the simple equivalent of a GCN with p-layers is

H ← S p X
These representations can then be used for some downstream task.

PROPOSED METHOD

Here, we derive a model that combines the concepts of selfexpressive subspace clustering, co-clustering and neighborhood propagation. The resulting model surpasses the performance of state of the art methods for all three categories on document-term matrices.

Self-Expressive Subspace Co-clustering

Based on the Block Seriation model for co-clustering, given a document-term matrix X ∈ R n×d + , the self-expressive subspace co-clustering problem can be formulated as min

R,C ∥ X -RXC ∥ 2 + Ω(R, C) such that R ∈ R, C ∈ C. ( 6
)
where R ∈ R n×n and C ∈ R d×d are respectively the row and column self-representation matrices, Ω(R, C) is the regularization term where the regularization of R and C can be either independent (i.e., Ω(R, C) = Ω R (R) + Ω C (C)) or dependent, and R and C are the feasible regions. Note that unlike the Block Seriation model, the generic case of our problem does not require k and g, the numbers of row and column clusters respectively, to be equal.

Promoting the Grouping Effect Through a Bilateral Graph Convolution

The performance of subspace clustering methods [START_REF] Lu | Robust and efficient subspace segmentation via least squares regression[END_REF], [START_REF] Hu | Smooth representation clustering[END_REF], [START_REF] Lu | Correlation adaptive subspace segmentation by trace lasso[END_REF] is due to the grouping effect. While the authors in [START_REF] Lu | Robust and efficient subspace segmentation via least squares regression[END_REF], [START_REF] Lu | Correlation adaptive subspace segmentation by trace lasso[END_REF] optimized this property implicitly, [START_REF] Hu | Smooth representation clustering[END_REF] sought to enforce it explicitly through the regularization term Ω(R). We use the definition of the grouping effect given in [START_REF] Hu | Smooth representation clustering[END_REF].

Definition 1. (Grouping Effect) Given a data matrix X, a self- representation matrix R has a grouping effect if ∀i, j, ∥x i -x j ∥ → 0 =⇒ ∥r i -r j ∥ → 0. (7)
In the case of text, the grouping effect will not necessarily be beneficial, because of its high dimensionality and sparsity. Data points may not be sufficiently "close" (as regards the self-expressive property) to be grouped in a meaningful way. This means that even if a subspace clustering approach has the grouping effect, in practice ∥x i -x j ∥ → 0 is not likely, making the property useless. The implication is that data points need some sort of smoothing to make some of the points closer and consequently to help subspace clustering algorithms find common subspaces.

Here, we propose to solve this problem through a bilateral graph convolution preprocessing step, based on simple graph convolution. This requires two similarity matrices to act as graphs on the rows S R and columns S C . These matrices can either be constructed through some similarity measure on the data, e.g. using the k-nn approach using the Euclidean or cosine distance, or be provided a priori such as in the case of attributed graphs (on the rows at least).

The reasoning, intuitively, is that the rows and columns of S p R XS q C , as propagation orders p, q grow, become smoother by being averaged up to their p-th and q-th neighbors respectively, analogously to Laplacian smoothing. The rows and columns therefore become more similar as powers increase. An illustration of this is shown in figure 1.

Proposition 1. Given a row-normalized adjacency matrix S on the rows of X, we have that S is a non-expansive mapping on the columns of

X ∀i ̸ = j, ∥Sx ′ i -Sx ′ j ∥ ≤ ∥x ′ i -x ′ j ∥
The same holds for the rows of X for S an adjacency matrix over the columns of X.

∀i ̸ = j, ∥x i S -x j S∥ ≤ ∥x i -x j ∥ (8)
Proof. Since S1 = 1 and s ij ≥ 0, by the Gershgorin circle theorem, the spectral radius of S is ρ(S) = 1. We therefore have

∥Sx ′ i -Sx ′ j ∥ = ∥S(x ′ i -x ′ j )∥ ≤ ∥S∥ 2 ∥x ′ i -x ′ j ∥ = ∥x ′ i -x ′ j ∥ (9)
since ||S|| 2 = ρ(S) where ||.|| 2 is the spectral norm. The proof is the same for the rows.

The grouping property also implies that in addition to the features X, the self-representation vectors, i.e., the rows (or, by symmetry, the columns) of R and C should also be getting more similar, leading to a more meaningful partitioning when applying spectral clustering on |R| and |C| where the absolute value is applied element-wise. In figure 2 we show how propagating the features using a row k-nn graph generated from the data using the Euclidean distance impacts the learned self-representation matrix using LSR subspace clustering. We see how the matrix obtained after 10-hop propagation has more nonzero entries than the matrix with no propagation, which indicates, if the self-representation matrix is seen as a graph, that there are more adjacent nodes. The difficulty is identifying the appropriate propagation order, since large values can cause over-smoothing. As we can see from figure 2, the selfrepresentation matrix after 1000-hop propagation is entirely uniform, since node features have converged to uninformative representations.

Proposition 2. Given a row-normalized adjacency matrix with added self-loops S, lim p→∞ S p exists and its rank is the same as that of the number of connected components of A.

Proof. Since S is row-stochastic, we have that ρ(S) = 1. Furthermore, since it has added self-loops it cannot be the adjacency matrix of a bipartite graph, and consequently -1 / ∈ σ(S) the spectrum of S.

lim p→∞ S p = lim p→∞ UΣ p U -1 = lim p→∞ Udiag([1 p , . . . , 1 p , r p 1 , ..., r p n-c ])U -1 = Udiag([1, . . . , 1, 0..., 0])U -1 (10)
It follows that rk(lim p→∞ S p ) = c, where ∀i r i ∈ σ(S), |r i | < 1 and c is the number of connected components.

Regarding the bilateral graph convolution of rows and columns of order p and q respectively, we define the generic self-expressive subspace co-clustering with bilateral graph convolution problem as

min R,C ∥ S p R XS q C -R (S p R XS q C ) C ∥ 2 + Ω(R, C) such that R ∈ R, C ∈ C. (11)
In what follows, we will refer to the row-and columnsmoothed matrix as

H = S p R XS q C
since this operation can be considered as a sort of preprocessing step, independent of the co-clustering model that we are about to introduce.

Subspace Co-clustering through LSR

We propose an initial variant based on the LSR subspace clustering model, where the regularization term is defined as follows:

Ω(R, C) = λ R ∥R∥ 2 + λ C ∥C∥ 2
, where λ R and λ C are parameters that regulate the trade-off between the reconstruction term and the regularizer. We formulate the LSR subspace co-clustering problem as

min R,C ∥H -RHC∥ 2 + λ R ∥R∥ 2 + λ C ∥C∥ 2 . ( 12
)
Fixing R and solving for C and inversely, a closed form solution can be obtained for both matrices, providing a clear illustration of how our model uses information from the columns for the row space partitioning, and vice versa

R = HC ⊤ H ⊤ HCC ⊤ H ⊤ + λ R I -1 C = H ⊤ R ⊤ RH + λ C I -1 H ⊤ R ⊤ H. (13)
However, solving the problem requires an iterative process where, in alternation, one of R and C is fixed and the other updated, until convergence. The overall computational complexity is roughly in O(n 3 + d 3 + tnd 2 + tn 2 d) due to the inversion and the necessary spectral clustering step, where t is the number of iterations, and the spatial complexity is O(n 2 + d 2 ), which is very often prohibitive for realworld applications, especially those pertaining to text. We therefore try to improve the efficiency of the solving scheme by adding further constraints, as described below.

SC 3 : A More Efficient Formulation Through Orthogonality Constraints

To address the issue of complexity we introduce factor matrices Z ∈ R n×k and W ∈ R d×g , which we constrain to be semi-orthogonal, i.e., Z ⊤ Z = I k and W ⊤ W = I g , such that R = ZZ ⊤ and C = WW ⊤ . With these constraints the LSR co-clustering problem becomes simpler, since ∥Z∥ 2 = rk(Z)

and ∥W∥ 2 = rk(W) are constant. The new formulation of the problem, that we have termed SC 3 , is

min Z,W ∥H -ZZ ⊤ HWW ⊤ ∥ such that Z ⊤ Z = I k W ⊤ W = I g (14)
At first glance this problem also requires an alternating solving scheme using two update rules that we obtain by fixing W and solving for Z, and vice versa :

Z = U such that [U, Σ, V] = TruncatedSVD(HW, k) W = U such that [U, Σ, V] = TruncatedSVD(H ⊤ Z, g).
This entails that g = k, making this a block clustering problem reminiscent of the block seriation co-clustering model. The detailed pseudo-code for this method is given in algorithm 1, whose spatial complexity is the same as for LSR, but the computational complexity is in O(n 3 + d 3 + tndk). Although this method is faster, it remains inefficient owing to bottlenecks, to the iterative nature of the algorithm and, more importantly, because of the spectral clustering step.

Algorithm 1: Naive SC 3

Input : X feature matrix, S R row propagation matrix, S C column propagation matrix, k number of co-clusters, p, q row and column propagation orders, ϵ tolerance. Output: Z, W row and column factors, π R , π C row and columns partitions.

H ← S p R XS q C ; [ , , V] = TruncatedSVD (H, k); W (0) ← V; while ∥Z (k) -Z (k-1) ∥ + ∥W (k) -W (k-1) ∥ > ϵ do [Z (k) , , ] = TruncatedSVD(HW (k-1) , k); [W (k) , , ] = TruncatedSVD(H ⊤ Z (k) , k); end R, C ← ZZ ⊤ , WW ⊤ ; π R ← spectral_clustering(|R|); π C ← spectral_clustering(|C|);
Optionally deduce a block diagonal bicluster matrix from π Z and π W ;

Efficiently Solving for Z * and W * The problem stated above can be solved efficiently using a single truncated SVD. This is a consequence of the following proposition: Proposition 3. The alternating process defined in system of equations 4.4 converges to Z and W containing the k left and right singular vectors of H respectively corresponding to the largest k singular values.

Proof. Suppose, without loss of generality, that k ≤ rk(H). We have that k = rk(Z) = rk(W), implying that

rk ZZ ⊤ HWW ⊤ ≤ min{rk(Z), rk(W), rk(H)} = k.
This means that we are looking for the best k-rank approximation of H for the Frobenius norm. Given [U, Σ, V] = SVD(H), and setting

Z = U k = [u ′ 1 , . . . , u ′ k ] and W = V k = [v ′ 1 , . . . , v ′ k ], we have ∥H -ZZ ⊤ HWW ⊤ ∥ 2 = ∥H -U k U ⊤ k UΣV ⊤ V k V ⊤ k ∥ 2 = ∥H -U k [I k , 0]Σ[I k , 0] ⊤ V ⊤ k ∥ 2 = ∥H -[U k , 0]Σ[V k , 0] ⊤ ∥ 2 = ∥H -U k Σ k V ⊤ k ∥ 2 . ( 15
)
From the Eckart-Young-Mirsky theorem we have that

H = U k Σ k V ⊤ k is the best rank-k approximation of H.
This leads to a more efficient algorithm because the iterative step is circumvented. The interplay between the rows and columns is still implicitly present, however, since this solution is also the analytic solution to the alternating optimization problem referred to above, in which the rowcolumn interaction is explicit.

The above result enables us to show that our approach has a grouping effect. Proposition 4. Given matrix H, the solutions R and C in SC 3 display a grouping effect on the rows and columns respectively of matrix H. Proof. To this end, we show that R and C display a grouping effect on H. We give the proof for R only since it is similar for C. Let the full singular value decomposition of H be H = UΣ k V ⊤ . We have that

Z = I k 0 0 0 U and that u i = Σ -1 V ⊤ h i .
Given these two equations, it is possible to write

∥z i -z j ∥ = I k 0 0 0 u i - I k 0 0 0 u j = I k 0 0 0 Σ -1 V ⊤ h i - I k 0 0 0 Σ -1 V ⊤ h j ≤ ∥ h i -h j ∥ I k 0 0 0 Σ -1 V ⊤ = ∥ h i -h j ∥ const. ( 16
)
We also have that since R = ZZ ⊤ , then r i = Zz i . Therefore, it holds that

∥r i -r j ∥ = ∥ Z(z i -z j )∥ (17) = ∥ z i -z j ∥ . since Z ⊤ Z = I
From equations 16 and 17, we have ∀i, j ∥h i -h j ∥ → 0 =⇒ ∥r i -r j ∥ → 0 implying that there is a grouping effect on the rows of H for R.

This gives us an efficient way to obtain Z * and W * , together with theoretical guarantees regarding the quality of these solutions. The main remaining complexity bottleneck is the spectral clustering step with its cubic computational complexity and its quartic space complexity in the number of rows and columns. However, using the structure of our R and C we may obtain a spectral clustering algorithm.

Efficient Spectral Clustering of the Kernel Self Representation Matrices

Nonnegative feature map

The optimal self-representation matrix R * = Z * Z * ⊤ is symmetric by construction, but its entries are not necessarily nonnegative. An element-wise absolute value would therefore be required in order for us to obtain a valid affinity matrix. However, this would remove all the information already held on the decomposition of R * into Z * Z * ⊤ , since generally there is no relation between the spectrum of a matrix and its spectrum after applying an entry-wise function. We circumvent this problem by instead considering an affinity matrix constructed through some nonnegative kernel, i.e.,

K R = ⟨φ(Z * ), φ(Z * )⟩ such that k ij ≥ 0
where φ is the feature map of the kernel applied row-wise that we need to calculate explicitly. Two possible approaches are available: Exact feature maps. The kernel trick can provide a means of operating in a high-dimensional, implicit feature space without ever computing the coordinates of the data in that space. Computing explicit feature maps is challenging for most commonly used kernel functions, which tend to increase the dimensionality of the original inputs to such an extent that it becomes impossible to use them in realistic scenarios. For instance, in the case of the second degree polynomial kernel k(z i , z j ) = (z ⊤ i z j + c) 2 where c is some constant that we can see as a bias term. For example, when c = 1 then the feature map is

φ : R k → R ( k+2 2 ) z → ⟨z 2 k , . . . , z 2 1 , √ 2z k z k-1 , . . . , √ 2z k z 1 , √ 2z k-1 z k-2 , . . . , √ 2z k-1 z 1 , . . . , √ 2z 2 z 1 , √ 2z k , . . . , √ 2z 1 , 1⟩
More generally, for a polynomial kernel of degree d the feature map is a function φ : R k → R ( k+d k ) . The other possibility is that the explicit feature map is infinitedimensional and thus impossible to compute, such as in the case of the Radial Basis Function (RBF) kernel. Approximate feature maps A number of methods using approximations of the feature maps of the desired kernel have been proposed over the years. These include the Nystr öm method [START_REF] Drineas | On the nystr öm method for approximating a gram matrix for improved kernelbased learning[END_REF], Tensor Sketch [START_REF] Pham | Fast and scalable polynomial kernels via explicit feature maps[END_REF], and the use of random features [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF].

Efficient Spectral Clustering

Since the eigenvectors of K R are the same as the left singular vectors of φ(Z * ), the process of spectral clustering becomes much faster, since the affinity matrix does not need to be computed explicitly. For our purposes we adapt the spectral algorithm proposed in [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF] as follows: 1) We efficiently compute the diagonal matrix D containing the sums of the rows of K R . 2) We construct matrix Ẑ = D -1/2 φ(Z), on which we do an SVD yielding the eigenvectors of D -1/2 K R D -1/2 , referred to as U.

3) We obtain the final assignments of the rows of H according to the assignment of vectors [u 1 , ...u n ] ⊤ using the k-means algorithm. This is equivalent to doing the spectral clustering on the normalized Laplacian of K R i.e. L = I -D -1/2 K R D -1/2 rendering the complexity of the spectral clustering linear in the number of samples instead of cubic. To obtain a spectral clustering of the affinity matrix of C * , the operations are the same.

ALGORITHM AND COMPLEXITY

The pseudo-code for the efficient version of our algorithm is given in algorithm 2. We now discuss the computational complexity in detail.

Algorithm 2: Efficient SC 3

Input : X feature matrix, S R row propagation matrix, S C column propagation matrix, k number of co-clusters, p, q row and column propagation orders. Output: Z, W row and column factors, π R , π C row and columns partitions.

H ← S p R XS q C ; [Z, , W] = TruncatedSVD (H, k); M φ ← φ(Z); D ← diag(Z φ (Z ⊤ φ 1)); Ẑφ ← D -1 2 Z φ ; U ← TruncatedSVD Ẑφ , k ; π Z ← k-means(U); M φ ← φ(W); D ← diag(W φ (W ⊤ φ 1)); Ŵφ ← D -1 2 W φ ; U ← TruncatedSVD
O(p∥S R ∥ 0 + q∥S C ∥ 0 )
, where ∥.∥ 0 is the 0-norm that gives the number of non-zero entries of its input. Truncated SVD on H The computational complexity of this step using randomized SVD [START_REF] Halko | Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions[END_REF] is O(nd log(k)). Truncated SVD on φ(Z) and φ(W) This depends on the dimensionality of the feature map. Since we consider the affine kernel feature map as the main choice, the complexity using a randomized SVD on it is O(nk log(k) + dk log(k)). Efficient spectral clustering. This operation has a complexity in O(tnk 2 +tdk 2 ), where t is the number of iterations of k-means. Overall computational complexity The overall computational complexity of the proposed SC 3 algorithm is thus in

O p∥S R ∥ 0 + q∥S C ∥ 0 + nd log(k) + tnk 2 + tdk 2 .

Overall spatial complexity

The space taken by the created matrices is in O (nk + dk).

As seen in Algorithm 2, k-means is used to propose a hard clustering. Instead of k-means the user can perform any other clustering method including fuzzy clustering method such as soft k-means. This implies that each data point can belong to more than one cluster; for each of them a set of coefficients gives the degree of being in each cluster. It is also the case of the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] where in E-step posterior probabilities of each data point are computed.

EXPERIMENTS

In this section we present the experimental setup and results. We consider two tasks which are co-clustering and document clustering. We start by introducing the models used for comparison and the overall experimental settings. Then, for each task we present the datasets and evaluation metrics as well as the results that were obtained. We follow with some comparisons between the different possible nonnegative kernels, and finally present the results for neighborhood propagation when a k-nn graph is used instead of the ground truth graph.

Experimental Setup

Baselines

We compare our model against clustering and co-clustering models that either use only the input node feature matrix X or that use both A and X, that is to say attributed graph clustering/co-clustering models.

Clustering models :

• Vanilla models: We take k-means as the simplest baseline for our comparison. • Subspace Clustering Models: We compare our model against the subspace clustering models previously mentioned: LSR, EnSC, ℓ 0 -SCC and Noisy-DR-ℓ 0 -SCC-LR, SSC-OMP and the mini-batch version of K-FSC. • Attributed graph clustering models: We use the GIC, S²GC and GCC models.

Co-clustering models :

• Vanilla models: We compare our model against the spectral co-clustering algorithm (SpecCo), DCC and RDPCo. • Attributed graph co-clustering Models: The only existing model of this kind is CFOND.

Experimental Settings

For our method, we normalize the word count datasets using tf-idf and unit-normalize across the the rows. We use the official implementation (with the recommended or default parameters) for each of them, apart from CFOND (ρ = β = α = 1), LSR (λ = 1), and RDPCo (with S r and S c ), ℓ 0 -SCC and Noisy-DR-ℓ 0 -SCC-LR (see [START_REF] Yang | Subspace learning by l0-induced sparsity[END_REF], [START_REF] Yang | Noisy l0-sparse subspace clustering on dimensionality reduced data[END_REF] for parameter setting) which, to the best of our knowledge, have not been made publicly available. We also use the recommended parameters for each dataset whenever possible. For models that use a parameter p like ours, we run their selection rule until convergence with a maximum p of 100 for fairness. All models were run on the same machine with 12GB memory GPU and a RAM of 12GB. All experiments for the different models were run on the same machine with 12GB of RAM and a 2.3Ghz Xeon Processor. We perform 20 runs for each model. Fig. 3: Synthetic datasets before and after rearrangement with respect to the true partitions.

Algorithm 3: Propagation Order Selection Rule

Input : X document-term matrix, S R row propagation matrix, S C column propagation matrix, q column propagation order, k number of co-clusters. Output: Propagation order p * . p ← 1; while p * not found do Z, W, , ← SC 3 (X, S R , S C , p, q, k);

loss p ← S p R X -ZZ ⊤ S p R XWW ⊤ ; if | loss p -loss p-1 | < d n⌈ √
k⌉ or p = 100 then p * ← p end p ← p + 1 end

Choice of Propagation Matrices

In our model, we use a k-nn graph generated from the rows of matrix X using the euclidean distance with k = 3. We use a propagation order of ten, p = 10. For the columns, we do not use a k-nn graph, but rather a graph based on NNPMI, which is nonnegative version of Pointwise Mutual Information (PMI) traditionally used to quantify word-relatedness. The column propagation order is set to q = 1. The column NNPMI graph is defined as

S C =(s Cij ) = max log y .. y i. y .j y ij , 0 ij (18)
where y ij = x ⊤ i x j . We use the nonnegative version so that the resulting matrix after propagation can still be seen as a document-term matrix. Both matrices are then normalized using the normalization proposed in [START_REF] Fettal | Efficient graph convolution for joint node representation learning and clustering[END_REF].

Co-clustering

Synthetic Datasets

Due to the absence of datasets with labels along both rows and columns. We propose to use synthetic datasets for the evaluation of the co-clustering performance of our model. The five datasets are depicted in figure 3 before and after rearrangement with respect to the ground truth partition. The characteristics of these datasets are available in table 1. These datasets have one of two possible types of structures, checkerboard [START_REF] Kluger | Spectral biclustering of microarray data: coclustering genes and conditions[END_REF] and block diagonal [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF].

Evaluation Metrics

To compare our algorithms we rely on the clustering accuracy that is computed by rearranging the rows of the confusion matrix so as to obtain the greatest possible trace using the Hungarian method. Clustering accuracy then corresponds to this trace divided by the number of elements. However, here we use a metric that simultaneously quantifies the clustering accuracy over rows and columns which we call co-clustering accuracy. Given c(π r ), the accuracy over the rows; and c(π c ), the accuracy over the columns. The coclustering accuracy cca [START_REF]Block clustering with bernoulli mixture models: Comparison of different approaches[END_REF] is given by

cca(π r , π c ) = c(π r ) + c(π r ) -c(π r ) × c(π r )

Performance

Table 2 shows the co-clustering results of our algorithm with respect to other co-clustering algorithms. We see that the models that use a topological information generally outperform the other models. Our model finds the ground truth partition in four out of five cases and has the best performance (or is tied for best) over the five datasets.

Document Clustering

Datasets

We use four attributed graph citation networks, which are graphs characterized by an adjacency matrix A and a node document-term matrix X. The summary statistics are given in table 3. The nodes in ACM and Citeseer correspond to word count vectors, and those in PubMed and Wiki to tfidf weighted word vectors. We use the ACM dataset, whose graph is not very informative, to compare the robustness of the models that use this information.

Evaluation Metrics

To assess the performance of different algorithms on the document clustering task, we use three commonly used clustering performance metrics: clustering accuracy (Acc), Adjusted Rand Index (ARI) [START_REF] Hubert | Comparing partitions[END_REF], and normalized mutual information (NMI) [START_REF] Cai | Non-negative matrix factorization on manifold[END_REF].

Choice of Propagation Matrices

Here, we set the row graph to be the adjacency matrix provided in each attributed graph dataset S R = A, but later we will test our model with a k-nn graph generated from the rows of matrix X. The row propagation order p is selected using the selection rule given in algorithm 3. The column propagation matrix and normalizations used are the same as for the synthetic data.

Performance

We consider three versions for our method corresponding to three different nonnegative kernel functions, linear, quadratic and radial basis (rbf) functions. Note that the linear kernel does not really result in a proper affinity matrix but is has a similar behaviour to the other valid kernels when using a bias term, so it can be a more efficient surrogate for them. Tables 4,5 show the row/document clustering performance of the different models. We report results for the power selected using rule 3. Overall, we see that methods using both graph structure and features outperform methods using features only; this is the case for all datasets, with the exception of ACM, where the graph is nearly strongly connected. We included the ACM dataset to show the robustness of our model in the face of an uninformative graph structure when compared with stateof-the-art attributed graph clustering models. Our model is seen to be competitive on all five datasets, and to have the best performances on all five datasets. SC 3 has either the best or the second best performance with respect to most metrics on each dataset, while having near-zero standard deviation, which shows that the proposed approach is robust. The performance gap is most striking on Wiki, where our model is seven points ahead of the closest model in terms of accuracy. We also see that the performance of the three variants of our model is similar.

For statistical significance, we perform a Nemenyi posthoc test [START_REF] Nemenyi | Distribution-free multiple comparisons[END_REF] with a confidence level of 95% on the ranks of each model in terms of Acc, NMI, and ARI, for each dataset and for each run (20 runs for each dataset) to compare our model with the other best performing models, namely SGC, S²GC, GIC, GCC and CFOND. This allows us to group models with similar performances. The results are shown in figure 4. The best group consisting of the SC 3 variants is seen to have the best performances by a wide margin, followed by the group containing only GCC.

Compared to co-clustering methods applied on X, note that sometimes, with certain some methods we have zero values for NMI and ARI. This is explained by the fact that we are facing the recurrent problem of empty classes when dealing with sparse and unbalanced data. The problem is, however, overcome by SC 3 as illustrated for ACM. a confidence level of 95%. We see that SC 3 variants perform similarly while being better than other models.

Efficiency

In figure 5 we plot the accuracy of the subspace clustering models in relation to their training times, comparing their performance on four datasets to that of linear SC 3 . The results correspond to an average over 20 runs. The time required by the propagation step is included in the overall running time of our algorithm. The fastest model on all datasets is linear SC 3 , it also achieves the best accuracy score. Note that while the other models give a partition for the rows exclusively, ours gives one for both rows and columns while remaining significantly more efficient.

Term Clustering

Since co-clustering models additionally generate a clustering for the terms. We use the PubMed dataset which is the only dataset for which we managed to find the actual terms. Table 6 presents the most frequent terms for each topic found by our model. The PubMed dataset contains scientific papers concerning diabetes. We see that topic a contains terms that are related to a presentation of diabetes, e.g, insulin, glucos, type, etc. Topic b has terms that are related to the microscopic effects of diabetes such as cell, islet, gene, betacel, and so on. Finally, topic c seems to concern terms that are associated with medical experimentation and analysis of results such as control, increas, signific, etc. We note the coherence of these term clusters since they cluster the PubMed paper contents according to three topics. This term clustering can then be used to help characterize document clusters to facilitate interpretation.

In order to quantitatively evaluate the semantic coherence of topics, we use an internal metric [START_REF] Mimno | Optimizing semantic coherence in topic models[END_REF] to measure the level of association between terms within each cluster. Essentially, if a majority of the words within a term cluster are interconnected, it can be inferred that the cluster is semantically coherent from a statistical standpoint. Topic coherence measures the degree of semantic similarity between the top words within a topic or term cluster. It takes into account both the intrinsic coherence of the words themselves, as well as their coherence within the context of the topic or cluster as a whole. This metric has been shown to be effective in assessing the quality of topic models and identifying topics that are most representative of the underlying data. We consider the top 10 terms when computing this metric. We also report the sizes of the topics which are considered as a good metric for assessing topic quality.

Convolution Using k-nn Graphs

Unless we are working with attributed graphs, no ground truth adjacency matrix on the rows is provided, but only the feature matrix. Consequently, we need to generate an adjacency matrix on the rows ourselves. A popular choice is the k-nearest neighbors graph, based on some metric. In table 7 we compare results on the five datasets using k-nn graphs generated based on the Euclidean and cosine dissimilarity with a number of neighbors k ∈ {3, 5, 10}. We symmetrize the obtained k-nn matrix A as follows: (A + A ⊤ )/2. We see that even without using the ground truth graph, our model continues to outperform subspace clustering and coclustering models, including CFOND, which uses the actual ground truth graph on all datasets. It also outperforms attributed graph clustering models on Wiki and ACM. On ACM, the results obtained by our model results are better when using the k-nn graph than when using the ground truth graph, since the ACM ground truth graph is not very informative. To sum up, we note that whatever the number of neighbors k ∈ {3, 5, 10} and the similarity measure used, SC 3 remains profitable for data even without ground truth adjacency matrix on the data points.

CONCLUSION

We proposed SC 3 , a new approach to leverage subspace clustering for text data through co-clustering and a bilateral graph convolution. SC 3 circumvents the computational and spatial complexity issues inherent in subspace clustering by using factor matrices and nonnegative kernel feature maps. We showed that the simple model that we propose has a grouping effect, and we demonstrated how the bilateral convolution helps to put this grouping property to good use. Experiments on synthetic and real datasets showed that our model is competitive with the state of the art on the tasks of document and word clustering in the context of document-term attributed graphs, while also being efficient (linear complexity in the number of nodes) and robust in the face of uninformative graph topologies. Even when no ground truth graph is available, the bilateral convolution operation improves performance in comparison to classical subspace clustering approaches.

Fig. 1 :

 1 Fig. 1: Mean pairwise euclidean distance of the columns of S p X as p increases on DBLP. The columns get mutually closer as more information propagates over the rows.

  (a) No propagation. (b) 10-hop propagation with a k-nn graph. (c) 1000-hop propagation with a k-nn graph.

Fig. 2 :

 2 Fig. 2: The resulting self-representation matrices using different levels of propagation over synthetic data with the LSR subspace clustering algorithm.

Fig. 4 :

 4 Fig.4: Visualization of the results of the Nemenyi test with a confidence level of 95%. We see that SC 3 variants perform similarly while being better than other models.

CFOND

  64.7±0.0 54.3±0.0 48.5±0.0 65.5±0.0 52.2±0.0 45.7±0.0 S²GC A, X 70.7±0.0 32.9±0.0 33.5±0.0 58.3±0.0 54.6±0.0 40.1±0.0 GCC A, X 70.8±0.0 32.3±0.0 33.2±0.0 67.6±0.0 56.0±0.0 46.5±0.0

Fig. 5 :

 5 Fig.5: Clustering accuracy plotted against training times on a logarithmic scale of subspace clustering algorithms on the different datasets. Linear SC 3 timing is used as the reference; for instance, on ACM, LSR ×13 means that it is approximately 10 times slower than SC 3 . Linear SC 3 consistently gives the best results and training times. PubMed is left out due to OOMs.

TABLE 1 :

 1 Synthetic datasets' characteristics.

	Dataset	Rows	Columns	Biclusters	Proportions	Structure
	A	500	500	10	equal	Block diagonal
	B	800	1000	6	unequal	Block diagonal
	C	800	800	8	equal	Checkerboard
	D	2000	1200	7	unequal	Checkerboard
	E	2500	2500	15	unequal	Checkerboard

TABLE 2 :

 2 Co-clustering performance on the synthetic datasets averaged over 20 runs of the different co-clustering models. Our model finds the ground truth partition in almost all cases and has the best performance (or is tied for best) over all datasets.

	Dataset	A	B	C	D	E
	SpecCo	89.53±1.39	99.54±0.0	94.32±0.0	99.95±0.02	78.43±1.5
	DCC	98.61±1.0	99.96±0.1	45.0±15.0	72.06±14.1	98.87±1.0
	RDpCo	85.1±6.3	86.74±6.7	28.18±0.0	64.19±14.9	22.5±0.0
	CFOND	100.0±0.0	97.9±2.0	100.0±0.0	99.25±0.7	98.16±0.8
	SC 3	100.0±0.0	100.0±0.0	100.0±0.0	100.0±0.0	99.87±0.2

TABLE 3 :

 3 Document datasets' statistics.

	Dataset	#Nodes	#Edges	#Features #Classes
	ACM [48]	3025	9150593	1870	3
	CiteSeer [18]	3327	4732	3703	6
	PubMed [18]	19717	44338	500	3
	Wiki [49]	2405	17981	4973	17
	Computers [50]	13381	259159	767	10

TABLE 6 :

 6 The three topics found by SC 3 characterized by their top ten most frequent terms, their size and coherence.

	Topic	a	b	c
		patient	cell	rat
		insulin	mice	control
		glucos	islet	activ
	Most	type	iddm	level
	Frequent	group	gene	increas
	Terms	subject	diseas	respons
		lt	develop	signific
		risk	nod	effect
		associ	children	express
		treatment	betacel	plasma
	Coherence	-403.4	-365.5	-387.5
	Size	280	63	157

TABLE 4 :

 4 Clustering results on ACM, Citeseer and Wiki.

	Method	Input	Co-	Subspace		ACM			CiteSeer			Wiki
			clustering	clustering	Acc	NMI	ARI	Acc	NMI	ARI	Acc	NMI	ARI
	k-means	X			62.8±4.8 37.2±9.2 34.5±10.4 62.5±1.6 36.7±1.9 35.5±2.5 47.3±6.0 46.3±6.9 26.4±8.1
	LSR	X			80.3±0.0 47.0±0.0	51.9±0.0	21.1±0.0	0.2±0.1	0.0±0.0	21.1±3.3	9.0±5.9	2.6±2.0
	EnSC	X			79.5±0.0 46.8±0.0	50.3±0.0	55.6±0.0 14.8±0.0 14.6±0.0 45.5±2.0 45.7±1.7 28.8±1.3
	SSC-OMP	X			78.8±0.1 43.4±0.1	48.3±0.1	24.0±1.1	3.5±0.4	1.8±0.1	52.7±4.4 48.1±2.3 33.3±1.5
	ℓ 0 -SSC	X			80.7±0.0 48.4±0.0	52.8±0.0	55.4±0.0 26.3±0.0 24.5±0.0 45.1±0.0 43.8±0.0 25.6±0.0
	DR-ℓ 0 SCC-LR	X			75.8±2.1 42.4±2.7	41.5±4.0	58.1±0.6 27.1±0.3 26.2±0.6 45.8±0.1 45.2±0.4 25.3±0.7
	K-FSC	X			56.2±7.5 17.1±6.3	18.0±5.7	35.3±6.9 12.4±3.5 10.6±4.0 38.2±5.1 35.6±3.9 17.7±4.4
	SpecCo	X			80.6±0.1 48.4±0.1	52.3±0.1	30.3±1.7 10.0±1.3	5.5±1.6	37.8±1.2 38.2±0.3 20.8±0.4
	DCC	X			40.5±3.3	7.8±5.1	2.1±2.2	35.1±3.8 11.5±2.4	8.9±2.9	48.3±3.6 47.5±2.6 30.6±3.0
	RDPCo	X			35.1±0.0	0.0±0.0	0.0±0.0	46.3±3.2 12.6±6.3	8.3±4.2	18.8±3.1	5.6±7.7	1.4±2.3
	GIC	A, X			34.3±0.4	0.1±0.1	0.0±0.0	68.8±0.8 43.8±1.0 44.6±1.0 46.5±1.4 48.2±0.5 30.2±1.4
	SGC	A, X			83.7±0.0 55.7±0.0	58.8±0.0	64.9±0.1 39.4±0.0 38.8±0.0 51.9±0.8 49.6±0.2 28.6±0.1
	S²GC	A, X			40.5±3.4	1.7±1.2	1.8±1.3	68.1±0.3 42.3±0.2 43.5±0.3 52.7±1.0 49.0±0.3 29.6±0.9
	GCC	A, X			35.4±0.0	0.3±0.0	0.0±0.0	69.4±0.1 45.0±0.2 45.4±0.1 54.1±0.8 55.0±0.2 33.3±0.5
	CFOND	A, X			71.8±0.6 37.2±0.5	38.2±0.7	63.0±1.1 36.6±1.3 36.2±1.2 47.8±3.0 49.5±2.1 30.3±2.5
	SC 3 linear SC 3 quad	A, X A, X			88.4±0.1 62.0±0.2 88.4±0.0 62.0±0.1	68.6±0.1 68.6±0.1	69.3±3.8 43.7±2.7 43.9±3.8 59.7±1.9 53.9±1.5 31.2±3.1 70.7±1.3 44.7±1.0 45.5±2.0 58.2±3.2 53.4±1.8 30.5±4.2
	SC 3 rbf	A, X			88.4±0.1 62.0±0.2	68.6±0.1	70.4±1.1 44.4±0.9 44.8±1.8 57.0±3.0 52.9±2.1 28.4±3.8

TABLE 5 :

 5 Clustering results on PubMed and Amazon Computers.

	Method	Input	Co-	Subspace		PubMed			Computers
			clustering clustering	Acc	NMI	ARI	Acc	NMI	ARI
	k-means	X			60.1±0.0 31.4±0.0 28.1±0.0 36.4±1.6	7.0±8.5	-0.2±1.4
	LSR	X				OOM		31.6±0.5 22.3±0.5 11.0±0.2
	EnSC	X			55.6±0.0 14.8±0.0 14.7±0.0 32.5±1.0 32.7±2.6 15.9±1.1
	SSC-OMP	X			60.4±0.0 22.3±0.0 19.4±0.0 46.6±1.3 29.1±0.3 30.0±3.1
	ℓ 0 -SCC	X				OOM		41.2±0.0 44.5±0.0 22.0±0.0
	DR-ℓ 0 SCC-LR	X				OOM		38.4±0.4 38.1±0.2 20.3±0.2
	K-FSC	X			49.5±9.8 14.8±5.9 12.1±7.1 41.1±2.5 28.9±3.2 16.5±3.5
	SpecCo	X			61.2±0.0 24.7±0.0 21.8±0.0 31.2±1.2 29.9±1.5 10.6±1.8
	DCC	X			54.3±3.6 16.5±2.9 13.4±4.1 34.3±1.9	3.0±1.5	-2.2±1.4
	RDPCo	X			21.4±0.2	1.0±0.5	0.2±0.1	37.1±0.0	0.0±0.0	0.0±0.0
	GIC	A, X			64.3±0.4 26.0±0.5 23.6±0.5 46.8±2.2 47.5±0.9 31.3±3.5
	SGC	A, X

TABLE 7 :

 7 Performance of SC 3 with a quadratic kernel using different column propagation matrices averaged over 20 runs. Best results are highlighted in bold font.

	Graph	k		ACM			Citeseer			Wiki			Pubmed		Computers
			Acc	NMI ARI	Acc	NMI ARI	Acc	NMI ARI	Acc	NMI ARI	Acc	NMI ARI
		3	88.7	62.8	69.2	68.0	42.8	43.8	52.9	50.3	19.0	71.3	33.4	34.2	70.5	58.7	50.3
	k-nn (euclidean)	5	88.7	63.1	69.3	68.3	43.6	44.3	56.7	51.4	24.5	71.2	33.2	34.1	70.8	59.2	48.9
		10 88.8	63.3	69.5	68.6	44.2	44.8	58.4	52.7	26.4	71.2	33.3	34.2	72.6	60.5	52.6
		3	88.0	61.1	67.7	67.3	42.3	42.7	54.7	51.7	24.0	71.2	33.0	34.0	71.3	60.2	49.7
	k-nn (cosine)	5	87.9	61.0	67.3	67.2	42.8	42.8	55.7	52.0	23.8	71.1	32.9	33.9	72.4	60.5	52.2
		10 87.9	60.9	67.4	67.3	42.8	43.0	55.4	51.6	25.3	71.0	32.8	33.8	72.5	60.6	52.4
		3	88.6	62.7	69.0	67.3	42.4	43.1	58.8	53.3	27.3	71.2	33.1	34.2	72.6	60.5	52.6
	k-nn (correlation)	5	88.7	62.9	69.2	68.1	43.4	43.9	55.7	51.1	26.6	71.1	32.9	34.0	72.6	60.5	52.5
		10 88.3	62.2	68.5	68.1	43.8	44.2	57.1	52.5	26.2	71.1	32.9	34.0	72.5	60.5	52.4