# On Learning the Structure of Clusters in Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 101 references that are in the map.
- First posted on arXiv 29 Dec 2022.

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

- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs](https://mlsanity.com/paper/2006.11468/) (2020)
- [Higher-Order Spectral Clustering of Directed Graphs](https://mlsanity.com/paper/2011.05080/) (2020)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Hypergraph Clustering Based on PageRank](https://mlsanity.com/paper/2006.08302/) (2020)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (2017)
- [Improved Analysis of Spectral Algorithm for Clustering](https://mlsanity.com/paper/1912.02997/) (2019)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Image Segmentation Based on Multiscale Fast Spectral Clustering](https://mlsanity.com/paper/1812.04816/) (2018)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Natural Scales in Geographical Patterns](https://mlsanity.com/paper/1704.01036/) (2017)

## Abstract (arXiv)

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.