# Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 47 references that are in the map.
- First posted on arXiv 3 May 2023.

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

- [Barlow Twins: Self-Supervised Learning via Redundancy Reduction](https://mlsanity.com/paper/2103.03230/) (2021)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [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)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [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)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [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)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (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)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [Multi-view Contrastive Graph Clustering](https://mlsanity.com/paper/2110.11842/) (2021)
- [Deep Fusion Clustering Network](https://mlsanity.com/paper/2012.09600/) (2020)
- [Attention-driven Graph Clustering Network](https://mlsanity.com/paper/2108.05499/) (2021)
- [Rethinking Graph Auto-Encoder Models for Attributed Graph Clustering](https://mlsanity.com/paper/2107.08562/) (2021)
- [Tree Decomposed Graph Neural Network](https://mlsanity.com/paper/2108.11022/) (2021)
- [Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach](https://mlsanity.com/paper/2209.08264/) (2022)

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

- [Multi-Domain Graph Foundation Models: Robust Knowledge Transfer via Topology Alignment](https://mlsanity.com/paper/2502.02017/) (2025)
- [PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering](https://mlsanity.com/paper/2312.14438/) (2023)
- [Efficient Heterogeneous Graph Learning via Random Projection](https://mlsanity.com/paper/2310.14481/) (2023)
- [CDC: A Simple Framework for Complex Data Clustering](https://mlsanity.com/paper/2403.03670/) (2024)
- [Upper Bounding Barlow Twins: A Novel Filter for Multi-Relational Clustering](https://mlsanity.com/paper/2312.14066/) (2023)
- [When Heterophily Meets Heterogeneous Graphs: Latent Graphs Guided Unsupervised Representation Learning](https://mlsanity.com/paper/2409.00687/) (2024)
- [Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning](https://mlsanity.com/paper/2409.17386/) (2024)
- [Bridged-GNN: Knowledge Bridge Learning for Effective Knowledge Transfer](https://mlsanity.com/paper/2308.09499/) (2023)
- [Balanced Multi-Relational Graph Clustering](https://mlsanity.com/paper/2407.16863/) (2024)
- [Cooperation of Experts: Fusing Heterogeneous Information with Large Margin](https://mlsanity.com/paper/2505.20853/) (2025)
- [Provable Filter for Real-world Graph Clustering](https://mlsanity.com/paper/2403.03666/) (2024)
- [Structure-Centric Graph Foundation Model via Geometric Bases](https://mlsanity.com/paper/2605.08689/) (2026)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [Simplified PCNet with Robustness](https://mlsanity.com/paper/2403.03676/) (2024)
- [Adaptive Homophily Clustering: Structure Homophily Graph Learning with Adaptive Filter for Hyperspectral Image](https://mlsanity.com/paper/2501.01595/) (2025)
- [Graph Domain Adaptation via Homophily-Agnostic Reconstructing Structure](https://mlsanity.com/paper/2602.07573/) (2026)
- [Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspective](https://mlsanity.com/paper/2412.09805/) (2024)
- [ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion](https://mlsanity.com/paper/2504.15920/) (2025)
- [Effective Clustering for Large Multi-Relational Graphs](https://mlsanity.com/paper/2508.17388/) (2025)
- [Topology Reorganized Graph Contrastive Learning with Mitigating Semantic Drift](https://mlsanity.com/paper/2407.16726/) (2024)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [HC-GAE: The Hierarchical Cluster-based Graph Auto-Encoder for Graph Representation Learning](https://mlsanity.com/paper/2405.14742/) (2024)
- [Probability Passing for Graph Neural Networks: Graph Structure and Representations Joint Learning](https://mlsanity.com/paper/2407.10688/) (2024)
- [Boolean Product Graph Neural Networks](https://mlsanity.com/paper/2409.14001/) (2024)
- [Aggregation-aware MLP: An Unsupervised Approach for Graph Message-passing](https://mlsanity.com/paper/2507.20127/) (2025)
- [Attention Beyond Neighborhoods: Reviving Transformer for Graph Clustering](https://mlsanity.com/paper/2509.15024/) (2025)
- [Weighted Graph Clustering via Scale Contraction and Graph Structure Learning](https://mlsanity.com/paper/2601.17307/) (2026)
- [Modeling Heterophily in Multiplex Graphs: An Adaptive Approach for Node Classification](https://mlsanity.com/paper/2605.12699/) (2026)
- [Unsupervised Graph Representation Learning with Complementary View Alignment](https://mlsanity.com/paper/2607.24338/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) based methods have achieved impressive performance on node clustering task. However, they are designed on the homophilic assumption of graph and clustering on heterophilic graph is overlooked. Due to the lack of labels, it is impossible to first identify a graph as homophilic or heterophilic before a suitable GNN model can be found. Hence, clustering on real-world graph with various levels of homophily poses a new challenge to the graph research community. To fill this gap, we propose a novel graph clustering method, which contains three key components: graph reconstruction, a mixed filter, and dual graph clustering network. To be graph-agnostic, we empirically construct two graphs which are high homophily and heterophily from each data. The mixed filter based on the new graphs extracts both low-frequency and high-frequency information. To reduce the adverse coupling between node attribute and topological structure, we separately map them into two subspaces in dual graph clustering network. Extensive experiments on 11 benchmark graphs demonstrate our promising performance. In particular, our method dominates others on heterophilic graphs.