mlsanityData to 14 Oct 2026

Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective

arXiv 2402.04621 ↗First posted 7 Feb 2024cs.LG cs.SIcited by 9

Not on the map. Why?

Abstract (arXiv)

How would randomly shuffling feature vectors among nodes from the same class affect graph neural networks (GNNs)? The feature shuffle, intuitively, perturbs the dependence between graph topology and features (A-X dependence) for GNNs to learn from. Surprisingly, we observe a consistent and significant improvement in GNN performance following the feature shuffle. Having overlooked the impact of A-X dependence on GNNs, the prior literature does not provide a satisfactory understanding of the phenomenon. Thus, we raise two research questions. First, how should A-X dependence be measured, while controlling for potential confounds? Second, how does A-X dependence affect GNNs? In response, we (i) propose a principled measure for A-X dependence, (ii) design a random graph model that controls A-X dependence, (iii) establish a theory on how A-X dependence relates to graph convolution, and (iv) present empirical analysis on real-world graphs that align with the theory. We conclude that A-X dependence mediates the effect of graph convolution, such that smaller dependence improves GNN-based node classification.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 39 of its 53 references that are in the map. First posted on arXiv 7 Feb 2024.

Builds on

39 of 53 references.

References · 39

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  3. 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
  4. 2019Simplifying Graph Convolutional Networkscited by 1,477
  5. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  6. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 976
  7. 2020Simple and Deep Graph Convolutional Networkscited by 860
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  9. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  10. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  11. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  12. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
27 more
  1. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 335
  2. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  3. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 261
  4. 2020Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networkscited by 260
  5. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 214
  6. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  7. 2021Identity-aware Graph Neural Networkscited by 198
  8. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  9. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  10. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  11. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  12. 2018Contextual Stochastic Block Modelscited by 134
  13. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  14. 2020A Unified View on Graph Neural Networks as Graph Signal Denoisingcited by 110
  15. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  16. 2022Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyondcited by 60
  17. 2022Anti-Symmetric DGN: a stable architecture for Deep Graph Networkscited by 60
  18. 2022GraphWorld: Fake Graphs Bring Real Insights for GNNscited by 56
  19. 2021On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphscited by 49
  20. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  21. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  22. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  23. 2023Towards Deep Attention in Graph Neural Networks: Problems and Remediescited by 24
  24. 2019On Node Features for Graph Neural Networkscited by 21
  25. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  26. 2024Understanding Heterophily for Graph Neural Networkscited by 15
  27. 2023When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishabilitycited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 3; 2026: 1.

9 papers.

  1. 2024The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challengescited by 29
  2. 2024A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guidecited by 23
  3. 2024Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedycited by 13
  4. 2024What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networkscited by 9
  5. 2024Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphscited by 8
  6. 2025Curriculum Guided Personalized Subgraph Federated Learningcited by 4
  7. 2025Gumbel-MPNN: Graph Rewiring with Gumbel-Softmaxcited by 0
  8. 2025Feature-Centric Unsupervised Node Representation Learning Without Homophily Assumptioncited by 0
  9. 2026Not All Nodes Are Created Equal: Homophily-Aware Stratification for Stable GNN Evaluationcited by 0