# Scalable and Adaptive Spectral Embedding for Attributed Graph Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 11 Aug 2024.

## Builds on (most cited first, 12 of 12)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Deep Graph Contrastive Representation Learning](https://mlsanity.com/paper/2006.04131/) (2020)
- [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)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [Cluster-guided Contrastive Graph Clustering Network](https://mlsanity.com/paper/2301.01098/) (2023)
- [Rethinking Graph Auto-Encoder Models for Attributed Graph Clustering](https://mlsanity.com/paper/2107.08562/) (2021)

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

- [Bridging Academia and Industry: A Comprehensive Benchmark for Attributed Graph Clustering](https://mlsanity.com/paper/2602.08519/) (2026)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)

## Abstract (arXiv)

Attributed graph clustering, which aims to group the nodes of an attributed graph into disjoint clusters, has made promising advancements in recent years. However, most existing methods face challenges when applied to large graphs due to the expensive computational cost and high memory usage. In this paper, we introduce Scalable and Adaptive Spectral Embedding (SASE), a simple attributed graph clustering method devoid of parameter learning. SASE comprises three main components: node features smoothing via k-order simple graph convolution, scalable spectral clustering using random Fourier features, and adaptive order selection. With these designs, SASE not only effectively captures global cluster structures but also exhibits linear time and space complexity relative to the graph size. Empirical results demonstrate the superiority of SASE. For example, on the ArXiv dataset with 169K nodes and 1.17M edges, SASE achieves a 6.9% improvement in ACC and a 5.87× speedup compared to the runner-up, S3GC.