# Spectral Subspace Clustering for Attributed Graphs

arXiv: https://arxiv.org/abs/2411.11074 · HTML: https://mlsanity.com/paper/2411.11074/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 105 references that are in the map.
- First posted on arXiv 17 Nov 2024.

## Builds on (most cited first, 30 of 32)

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Structural Deep Clustering Network](https://mlsanity.com/paper/2002.01633/) (2020)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Deep Subspace Clustering Networks](https://mlsanity.com/paper/1709.02508/) (2017)
- [Adaptive Graph Encoder for Attributed Graph Embedding](https://mlsanity.com/paper/2007.01594/) (2020)
- [Deep Fusion Clustering Network](https://mlsanity.com/paper/2012.09600/) (2020)
- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Robust and Efficient Subspace Segmentation via Least Squares Regression](https://mlsanity.com/paper/1404.6736/) (2014)
- [A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource](https://mlsanity.com/paper/2211.12875/) (2022)
- [Community detection in node-attributed social networks: a survey](https://mlsanity.com/paper/1912.09816/) (2019)
- [PANE: scalable and effective attributed network embedding](https://mlsanity.com/paper/2009.00826/) (2020)
- [DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization](https://mlsanity.com/paper/2312.12697/) (2023)
- [Clustering attributed graphs: models, measures and methods](https://mlsanity.com/paper/1501.01676/) (2015)
- [Large-Scale Subspace Clustering via k-Factorization](https://mlsanity.com/paper/2012.04345/) (2020)
- [Towards Clustering-friendly Representations: Subspace Clustering via Graph Filtering](https://mlsanity.com/paper/2106.09874/) (2021)
- [CaEGCN: Cross-Attention Fusion based Enhanced Graph Convolutional Network for Clustering](https://mlsanity.com/paper/2101.06883/) (2021)
- [Efficient High-Quality Clustering for Large Bipartite Graphs](https://mlsanity.com/paper/2312.16926/) (2023)
- [Effective and Scalable Clustering on Massive Attributed Graphs](https://mlsanity.com/paper/2102.03826/) (2021)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)

## Built on by (most cited first, 6 of 6)

- [Cross-Contrastive Clustering for Multimodal Attributed Graphs with Dual Graph Filtering](https://mlsanity.com/paper/2511.20030/) (2025)
- [Leveraging Large Language Models for Effective Label-free Node Classification in Text-Attributed Graphs](https://mlsanity.com/paper/2412.11983/) (2024)
- [Effective Clustering for Large Multi-Relational Graphs](https://mlsanity.com/paper/2508.17388/) (2025)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [CLUBench: A Clustering Benchmark](https://mlsanity.com/paper/2605.29933/) (2026)
- [ComNetX: Local Hierarchical Adaptation for Dynamic Community Detection](https://mlsanity.com/paper/2608.16906/) (2026)

## Abstract (arXiv)

Subspace clustering seeks to identify subspaces that segment a set of n data points into k (k<<n) groups, which has emerged as a powerful tool for analyzing data from various domains, especially images and videos. Recently, several studies have demonstrated the great potential of subspace clustering models for partitioning vertices in attributed graphs, referred to as SCAG. However, these works either demand significant computational overhead for constructing the nxn self-expressive matrix, or fail to incorporate graph topology and attribute data into the subspace clustering framework effectively, and thus, compromise result quality. Motivated by this, this paper presents two effective and efficient algorithms, S2CAG and M-S2CAG, for SCAG computation. Particularly, S2CAG obtains superb performance through three major contributions. First, we formulate a new objective function for SCAG with a refined representation model for vertices and two non-trivial constraints. On top of that, an efficient linear-time optimization solver is developed based on our theoretically grounded problem transformation and well-thought-out adaptive strategy. We then conduct an in-depth analysis to disclose the theoretical connection of S2CAG to conductance minimization, which further inspires the design of M-S2CAG that maximizes the modularity. Our extensive experiments, comparing S2CAG and M-S2CAG against 17 competitors over 8 benchmark datasets, exhibit that our solutions outperform all baselines in terms of clustering quality measured against the ground truth while delivering high efficiency