mlsanityData to 7 Oct 2026

Joint Graph Rewiring and Feature Denoising via Spectral Resonance

arXiv 2408.07191 ↗First posted 13 Aug 2024cs.LG cs.SI stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

When learning from graph data, the graph and the node features both give noisy information about the node labels. In this paper we propose an algorithm to jointly denoise the features and rewire the graph (JDR), which improves the performance of downstream node classification graph neural nets (GNNs). JDR works by aligning the leading spectral spaces of graph and feature matrices. It approximately solves the associated non-convex optimization problem in a way that handles graphs with multiple classes and different levels of homophily or heterophily. We theoretically justify JDR in a stylized setting and show that it consistently outperforms existing rewiring methods on a wide range of synthetic and real-world node classification tasks.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 57 of its 84 references that are in the map. First posted on arXiv 13 Aug 2024.

Builds on

57 of 84 references.

References · 57

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  5. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  6. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  7. 2018Link Prediction Based on Graph Neural Networkscited by 829
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  9. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  10. 2015Image-based Recommendations on Styles and Substitutescited by 702
  11. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  12. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
38 more
  1. 2020A Generalization of Transformer Networks to Graphscited by 653
  2. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  3. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  4. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  5. 2019Multi-scale Attributed Node Embeddingcited by 543
  6. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  7. 2019Diffusion Improves Graph Learningcited by 414
  8. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 368
  9. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  10. 2017Community Detection and Stochastic Block Modelscited by 317
  11. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 309
  12. 2020Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddingscited by 212
  13. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  14. 2023Exphormer: Sparse Transformers for Graphscited by 166
  15. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  16. 2021Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Predictioncited by 137
  17. 2018Contextual Stochastic Block Modelscited by 134
  18. 2020A Unified View on Graph Neural Networks as Graph Signal Denoisingcited by 110
  19. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  20. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  21. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  22. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  23. 2022Expander Graph Propagationcited by 75
  24. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  25. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 63
  26. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  27. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  28. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 39
  29. 2020Rethinking Graph Regularization for Graph Neural Networkscited by 36
  30. 2021Neural Link Prediction with Walk Poolingcited by 36
  31. 2019Optimizing Generalized PageRank Methods for Seed-Expansion Community Detectioncited by 35
  32. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 35
  33. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  34. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  35. 2023A Neural Collapse Perspective on Feature Evolution in Graph Neural Networkscited by 19
  36. 2022Simplified Graph Convolution with Heterophilycited by 17
  37. 2023Grounding Graph Network Simulators using Physical Sensor Observationscited by 15
  38. 2022Rewiring Networks for Graph Neural Network Training Using Discrete Geometrycited by 14

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 8.

11 papers.

  1. 2024Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 8
  2. 2025Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networkscited by 4
  3. 2025GraphTorque: Torque-Driven Rewiring Graph Neural Networkcited by 0
  4. 2026Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 0
  5. 2026RAwR: Role-Aware Rewiring via Approximate Equitable Partitioncited by 0
  6. 2026Learn When and Where to Connect: Adaptive Virtual Nodes for Dynamic Message Passing on Graphscited by 0
  7. 2026Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learningcited by 0
  8. 2026Ramanujan Graph Rewiring with Non Negative Resistance Curvaturecited by 0
  9. 2026Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignmentcited by 0
  10. 2026Beyond Observed Auxiliary Relations: Environment-Conditioned Modeling for Multi-Behavior Recommendationcited by 0
  11. 2026Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classificationcited by 0