# A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 70 references that are in the map.
- First posted on arXiv 10 Aug 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [HDMI: High-order Deep Multiplex Infomax](https://mlsanity.com/paper/2102.07810/) (2021)
- [Multi-view Contrastive Graph Clustering](https://mlsanity.com/paper/2110.11842/) (2021)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited](https://mlsanity.com/paper/1312.5179/) (2013)
- [Hypergraph Random Walks, Laplacians, and Clustering](https://mlsanity.com/paper/2006.16377/) (2020)
- [Hypergraph Clustering Based on PageRank](https://mlsanity.com/paper/2006.08302/) (2020)
- [Effective and Scalable Clustering on Massive Attributed Graphs](https://mlsanity.com/paper/2102.03826/) (2021)
- [High-Quality Hypergraph Partitioning](https://mlsanity.com/paper/2106.08696/) (2021)
- [Clustering of Diverse Multiplex Networks](https://mlsanity.com/paper/2110.05308/) (2021)
- [Hybrid Clustering based on Content and Connection Structure using Joint Nonnegative Matrix Factorization](https://mlsanity.com/paper/1703.09646/) (2017)
- [A Comparative Study of Matrix Factorization and Random Walk with Restart in Recommender Systems](https://mlsanity.com/paper/1708.09088/) (2017)
- [Unsupervised Multiplex Graph Learning with Complementary and Consistent Information](https://mlsanity.com/paper/2308.01606/) (2023)
- [Towards Understanding and Demystifying Bitcoin Mixing Services](https://mlsanity.com/paper/2010.16274/) (2020)
- [Orthogonal Trace-Sum Maximization: Applications, Local Algorithms, and Global Optimality](https://mlsanity.com/paper/1811.03521/) (2018)
- [Hypergraph Clustering: A Modularity Maximization Approach](https://mlsanity.com/paper/1812.10869/) (2018)

## 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)
- [Knapsack Optimization-based Schema Linking for LLM-based Text-to-SQL Generation](https://mlsanity.com/paper/2502.12911/) (2025)
- [Spectral Subspace Clustering for Attributed Graphs](https://mlsanity.com/paper/2411.11074/) (2024)
- [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)

## Abstract (arXiv)

Attributed networks containing entity-specific information in node attributes are ubiquitous in modeling social networks, e-commerce, bioinformatics, etc. Their inherent network topology ranges from simple graphs to hypergraphs with high-order interactions and multiplex graphs with separate layers. An important graph mining task is node clustering, aiming to partition the nodes of an attributed network into k disjoint clusters such that intra-cluster nodes are closely connected and share similar attributes, while inter-cluster nodes are far apart and dissimilar. It is highly challenging to capture multi-hop connections via nodes or attributes for effective clustering on multiple types of attributed networks. In this paper, we first present AHCKA as an efficient approach to attributed hypergraph clustering (AHC). AHCKA includes a carefully-crafted K-nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, a joint hypergraph random walk model to devise an effective AHC objective, and an efficient solver with speedup techniques for the objective optimization. The proposed techniques are extensible to various types of attributed networks, and thus, we develop ANCKA as a versatile attributed network clustering framework, capable of attributed graph clustering (AGC), attributed multiplex graph clustering (AMGC), and AHC. Moreover, we devise ANCKA with algorithmic designs tailored for GPU acceleration to boost efficiency. We have conducted extensive experiments to compare our methods with 19 competitors on 8 attributed hypergraphs, 16 competitors on 6 attributed graphs, and 16 competitors on 3 attributed multiplex graphs, all demonstrating the superb clustering quality and efficiency of our methods.