# Provable Filter for Real-world Graph Clustering

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 82 references that are in the map.
- First posted on arXiv 6 Mar 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [GraphMAE: Self-Supervised Masked Graph Autoencoders](https://mlsanity.com/paper/2205.10803/) (2022)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [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)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Symmetric Graph Convolutional Autoencoder for Unsupervised Graph Representation Learning](https://mlsanity.com/paper/1908.02441/) (2019)
- [Adaptive Graph Encoder for Attributed Graph Embedding](https://mlsanity.com/paper/2007.01594/) (2020)
- [Learning Graph Embedding with Adversarial Training Methods](https://mlsanity.com/paper/1901.01250/) (2019)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Multi-view Contrastive Graph Clustering](https://mlsanity.com/paper/2110.11842/) (2021)
- [Deep Fusion Clustering Network](https://mlsanity.com/paper/2012.09600/) (2020)
- [Cluster-guided Contrastive Graph Clustering Network](https://mlsanity.com/paper/2301.01098/) (2023)
- [Simple Contrastive Graph Clustering](https://mlsanity.com/paper/2205.07865/) (2022)
- [A Unified Transformer Framework for Group-based Segmentation: Co-Segmentation, Co-Saliency Detection and Video Salient Object Detection](https://mlsanity.com/paper/2203.04708/) (2022)
- [Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings](https://mlsanity.com/paper/2101.03091/) (2021)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)

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

- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)
- [On the Benefits of Attribute-Driven Graph Domain Adaptation](https://mlsanity.com/paper/2502.06808/) (2025)
- [Homophily Enhanced Graph Domain Adaptation](https://mlsanity.com/paper/2505.20089/) (2025)
- [Attention Beyond Neighborhoods: Reviving Transformer for Graph Clustering](https://mlsanity.com/paper/2509.15024/) (2025)
- [Beyond Missing Rates: Rethinking Incomplete Multi-View Clustering with Protocol Divergence](https://mlsanity.com/paper/2606.04857/) (2026)

## Abstract (arXiv)

Graph clustering, an important unsupervised problem, has been shown to be more resistant to advances in Graph Neural Networks (GNNs). In addition, almost all clustering methods focus on homophilic graphs and ignore heterophily. This significantly limits their applicability in practice, since real-world graphs exhibit a structural disparity and cannot simply be classified as homophily and heterophily. Thus, a principled way to handle practical graphs is urgently needed. To fill this gap, we provide a novel solution with theoretical support. Interestingly, we find that most homophilic and heterophilic edges can be correctly identified on the basis of neighbor information. Motivated by this finding, we construct two graphs that are highly homophilic and heterophilic, respectively. They are used to build low-pass and high-pass filters to capture holistic information. Important features are further enhanced by the squeeze-and-excitation block. We validate our approach through extensive experiments on both homophilic and heterophilic graphs. Empirical results demonstrate the superiority of our method compared to state-of-the-art clustering methods.