# Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 59 references that are in the map.
- First posted on arXiv 6 Jun 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [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)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (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)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Graph Neural Networks with convolutional ARMA filters](https://mlsanity.com/paper/1901.01343/) (2019)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations](https://mlsanity.com/paper/2108.01938/) (2021)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Understanding and Improving Graph Injection Attack by Promoting Unnoticeability](https://mlsanity.com/paper/2202.08057/) (2022)

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

- [GraphEdit: Large Language Models for Graph Structure Learning](https://mlsanity.com/paper/2402.15183/) (2024)
- [What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networks](https://mlsanity.com/paper/2406.18854/) (2024)
- [Clarify Confused Nodes via Separated Learning](https://mlsanity.com/paper/2306.02285/) (2023)
- [Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily](https://mlsanity.com/paper/2511.06608/) (2025)
- [Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networks](https://mlsanity.com/paper/2312.16418/) (2023)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [CAT: A Causally Graph Attention Network for Trimming Heterophilic Graph](https://mlsanity.com/paper/2312.08672/) (2023)
- [Heterophilous Distribution Propagation for Graph Neural Networks](https://mlsanity.com/paper/2405.20640/) (2024)
- [Beyond Homophily: Community Search on Heterophilic Graphs](https://mlsanity.com/paper/2601.01703/) (2026)

## Abstract (arXiv)

While a growing body of literature has been studying new Graph Neural Networks (GNNs) that work on both homophilic and heterophilic graphs, little has been done on adapting classical GNNs to less-homophilic graphs. Although the ability to handle less-homophilic graphs is restricted, classical GNNs still stand out in several nice properties such as efficiency, simplicity, and explainability. In this work, we propose a novel graph restructuring method that can be integrated into any type of GNNs, including classical GNNs, to leverage the benefits of existing GNNs while alleviating their limitations. Our contribution is threefold: a) learning the weight of pseudo-eigenvectors for an adaptive spectral clustering that aligns well with known node labels, b) proposing a new density-aware homophilic metric that is robust to label imbalance, and c) reconstructing the adjacency matrix based on the result of adaptive spectral clustering to maximize the homophilic scores. The experimental results show that our graph restructuring method can significantly boost the performance of six classical GNNs by an average of 25% on less-homophilic graphs. The boosted performance is comparable to state-of-the-art methods.