Scalable Attributed-Graph Subspace Clustering

Chakib Fettal, Lazhar Labiod, Mohamed NadifAAAI 2023 · DOI

Abstract

Clustering nodes in attributed graphs is a critical task with widespread applications, yet traditional subspace clustering methods fail to scale due to quadratic complexity. This paper proposes SAGSC (Scalable Attributed-Graph Subspace Clustering), a framework that combines graph convolutional smoothing with a factored matrix approach. By utilizing an implicit affinity mapping via a quadratic kernel, SAGSC achieves linear complexity relative to the number of nodes. Experimental results on large-scale datasets, including OGBN-arXiv, demonstrate that SAGSC significantly outperforms existing methods in both accuracy and computational efficiency.

Introduction

Attributed graph clustering involves grouping nodes based on both their features and their structural connections. While Graph Convolutional Networks (GCNs) are powerful, they can be computationally intensive for unsupervised tasks. Subspace clustering, which assumes data points lie in a union of low-dimensional subspaces, offers a mathematically elegant alternative. However, its requirement to learn an $n \times n$ coefficient matrix makes it impractical for graphs with hundreds of thousands of nodes. SAGSC addresses this scalability gap, providing a model that captures the benefits of subspace clustering without the $O(n^2)$ bottleneck.

The SAGSC Framework

The SAGSC pipeline consists of four primary stages designed to ensure efficiency and accuracy:

  1. Graph Smoothing: A linear propagation step ($H = S^p X$) averages node features with their neighbors. This "pre-conditioning" makes nodes within the same community more similar and self-expressive.
  2. Factored Subspace Clustering: The coefficient matrix $C$ is constrained as a product of smaller latent factor matrices ($C = UU^\top$). This turns a massive optimization problem into a simple Singular Value Decomposition (SVD) of the smoothed features.
  3. Implicit Affinity Mapping: To handle negative values in the coefficient matrix, a quadratic kernel feature map ($\Phi$) projects latent factors into a space where the affinity matrix is guaranteed to be non-negative and symmetric, without explicit construction.
  4. Efficient Spectral Clustering: Clustering is performed via k-means on the singular vectors of the mapped space, maintaining linear complexity.
The SAGSC framework overview, illustrating the transition from graph representation learning to implicit subspace clustering with linear complexity.

Experimental Evaluation

The model was evaluated on diverse real-world datasets, including citation networks (ACM, DBLP, PubMed), knowledge graphs (Wiki), and the large-scale OGBN-arXiv benchmark, which contains over 169,000 nodes.

Performance and Efficiency

SAGSC consistently achieved superior results across all primary metrics. On the OGBN-arXiv dataset, it delivered a 14% improvement in clustering accuracy over the next best state-of-the-art model. Crucially, it was also the fastest model tested; on OGBN-arXiv, it was 16% faster than the second-fastest competitor and orders of magnitude faster than traditional subspace methods like LSR or EnSC.

Comparison of clustering accuracy versus execution time, showing that SAGSC (Ours) achieves the highest accuracy with the lowest computational overhead.

Key Insights and Conclusion

The success of SAGSC stems from treating neighborhood smoothing as a mechanism to satisfy the self-expressivity property of subspace clustering. By moving to a factored $n \times k$ representation, spatial complexity is reduced from quadratic to linear. Furthermore, the use of the kernel trick allows for "implicit" spectral clustering, gaining the benefits of high-dimensional affinity without the associated storage costs. While the model requires tuning the propagation power ($p$), it represents a significant step forward in making subspace clustering viable for massive real-world graphs.

Summary updated

BibTeX
@inproceedings{fettal2023scalable,
  author = {Chakib Fettal and Lazhar Labiod and Mohamed Nadif},
  title = {{Scalable Attributed-Graph Subspace Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i6.25918},
}
Figure