mlsanityData to 14 Oct 2026

Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax

arXiv 2508.17531 ↗First posted 24 Aug 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Graph homophily has been considered an essential property for message-passing neural networks (MPNN) in node classification. Recent findings suggest that performance is more closely tied to the consistency of neighborhood class distributions. We demonstrate that the MPNN performance depends on the number of components of the overall neighborhood distribution within a class. By breaking down the classes into their neighborhood distribution components, we increase measures of neighborhood distribution informativeness but do not observe an improvement in MPNN performance. We propose a Gumbel-Softmax-based rewiring method that reduces deviations in neighborhood distributions. Our results show that our new method enhances neighborhood informativeness, handles long-range dependencies, mitigates oversquashing, and increases the classification performance of the MPNN. The code is available at https://github.com/Bobowner/Gumbel-Softmax-MPNN.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 43 of its 54 references that are in the map. First posted on arXiv 24 Aug 2025.

Builds on

43 of 54 references.

References · 43

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,739
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  6. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  7. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  8. 2020Simple and Deep Graph Convolutional Networkscited by 860
  9. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  10. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  11. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  12. 2019Multi-scale Attributed Node Embeddingcited by 548
31 more
  1. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  2. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 362
  3. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  4. 2019Learning Discrete Structures for Graph Neural Networkscited by 231
  5. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 214
  6. 2020Graph Neural Networks with Heterophilycited by 202
  7. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  8. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  9. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  10. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  11. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  12. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  13. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 90
  14. 2020Differentiable Graph Module (DGM) for Graph Convolutional Networkscited by 86
  15. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 85
  16. 2021GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophilycited by 84
  17. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 82
  18. 2022Towards Robust Graph Neural Networks for Noisy Graphs with Sparse Labelscited by 63
  19. 2022Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyondcited by 60
  20. 2021Simplifying approach to Node Classification in Graph Neural Networkscited by 56
  21. 2023Locality-Aware Graph-Rewiring in GNNscited by 56
  22. 2021Block Modeling-Guided Graph Convolutional Neural Networkscited by 32
  23. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  24. 2022Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approachcited by 23
  25. 2023From Latent Graph to Latent Topology Inference: Differentiable Cell Complex Modulecited by 19
  26. 2021Powerful Graph Convolutioal Networks with Adaptive Propagation Mechanism for Homophily and Heterophilycited by 14
  27. 2023On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networkscited by 13
  28. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9
  29. 2022Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processescited by 7
  30. 2024Layer-diverse Negative Sampling for Graph Neural Networkscited by 7
  31. 2024Disambiguated Node Classification with Graph Neural Networkscited by 4

Built on by

Not cited yet.