Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

A new rewiring method, TRIGON, learns which triangles to add to a graph and beats eight baselines on 9 of 10 node-classification benchmarks.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

A learned triangle-selection module rewires graphs for GNNs, improving node classification over prior rewiring methods on 9 of 10 benchmarks.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection Likely label leakage in the contrastive loss undermines the headline results, but the triangle-selection idea is worth a closer look. the 4 major comments →

arxiv 2508.19071 v2 pith:GU4FGZGH submitted 2025-08-26 cs.LG cs.AI

Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks

Hugo Attali , Thomas Papastergiou , Nathalie Pernelle , Fragkiskos D. Malliaros This is my paper
classification cs.LG cs.AI
keywords graph neural networksgraph rewiringtriangle selectionoversquashingoversmoothingheterophilynode classificationDelaunay triangulation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that the best way to rewire a graph for a message-passing GNN is to learn which triples of nodes, or triangles, deserve to be connected, rather than to fix edges by a static rule. The proposed method, TRIGON, collects candidate triangles from the original graph, a feature-based k-nearest-neighbor graph, and a Delaunay triangulation, scores each triangle with a learned encoder, and selects a subset through a differentiable Gumbel-Softmax gate while jointly training the downstream classifier. On ten node-classification benchmarks spanning homophilic and heterophilic regimes, and with both GCN and GAT backbones, TRIGON reports the best accuracy on nine of them, with structural diagnostics showing lower effective resistance on critical edges, smaller diameter, and a larger spectral gap than existing rewiring methods. The finding matters because it suggests that oversquashing and oversmoothing can be addressed at the level of which higher-order motifs to add, not only which individual edges to add or remove.

Core claim

The central claim is that a graph rewired by task-selected triangles is structurally better for GNN message passing than graphs rewired by curvature, spectral, diffusion, or static triangulation heuristics. TRIGON scores each candidate triangle—drawn from three complementary views: existing edges, feature-space proximity via k-NN, and Delaunay triangulation of learned embeddings—and keeps those whose selection helps classification, using Gumbel-Softmax to make the choice differentiable. The selected triangles are reassembled into a new edge set at every training step, so the topology co-evolves with the GNN. The paper supports the claim with an upper bound on effective resistance in terms of

What carries the argument

The central object is the candidate triangle set and the differentiable selection gate. Each triangle is represented by concatenated node features, embedded by a shared MLP, scored by a second MLP into binary logits, then relaxed with Gumbel-Softmax; selected triangles' edges form the rewired graph. Its work is to convert graph rewiring from a heuristic edge-edit problem into a learned higher-order motif-selection problem in which structural objectives (resistance, diameter, spectral gap, class balance) are optimized together with classification.

Load-bearing premise

For TRIGON to find a useful shortcut, that shortcut must already be an edge of at least one candidate triangle in the union of three starting views; if the only triangles that would help a given graph lie outside those views, TRIGON cannot create them.

What would settle it

On a held-out heterophilic benchmark, run TRIGON against a variant whose candidate triangle set also includes triangles from the 2-hop or random-walk closure of the original graph; if the enlarged candidate set lifts accuracy by a non-trivial margin, or if TRIGON no longer beats random selection of the same number of triangles, the claim that the three fixed views supply all useful rewiring vocabulary fails.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Rewiring can be formulated as learning over triples rather than pairs, so any method that ranks missing edges can be upgraded to rank the triangles that contain them.
  • Because the rewired graph is rebuilt every epoch, the topology adapts as embeddings change; this dynamic property is what lets the method preserve discriminability at much greater depth.
  • Adding non-local triangles is enough to improve global connectivity: diameter drops and spectral gap rises on all datasets tested, so shortcuts between distant nodes are a sufficient mechanism for better propagation.
  • The gains transfer across backbone architectures: a standard GCN or GAT benefits without changing the message-passing rule.
  • Features are essential: ablating k-NN or original-graph triangles hurts, so rewiring should use both topology and feature views.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same triangle-selection gate could be reused for link prediction or graph generation: a model that already learns which triples are task-relevant can emit them as predicted higher-order structure. This is an extension, not something the paper tests.
  • Because Delaunay triangles in the paper are computed over learned embeddings, a natural variant is to rebuild the k-NN view from current embeddings too, instead of only raw features; the paper's dynamic argument suggests this could further enlarge the useful candidate set.
  • The effective-resistance bound suggests a cheap ablation: count triangles per edge in the final rewired graph and correlate that count with per-edge resistance; if the correlation is weak, the selection losses, not the triangle count, are doing the work.
  • The method's ceiling is set by the three fixed candidate views; on graphs where useful shortcuts are non-local in both topology and feature space, adding a fourth view (e.g., random-walk proximity or spectral embedding coordinates) would directly test that ceiling.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes TRIGON, a graph rewiring method that constructs a new graph by selecting triangles from a candidate set obtained from the original graph, a k-NN graph over raw features, and a Delaunay triangulation over learned embeddings. Triangle selection is trained with a Gumbel-Softmax relaxation and a multi-part loss, and the resulting graph is used to train a GNN (GCN or GAT) for node classification. The authors report performance gains over eight rewiring baselines on nine of ten benchmarks, improved structural metrics such as reduced diameter and higher spectral gap, and greater robustness to oversmoothing at increased depth.

Significance. If the empirical claims are valid, TRIGON would be a practically useful rewiring method: it combines explicit higher-order (triangle) structure with a learned, feature-aware selection mechanism, and it is evaluated on a broad set of homophilic and heterophilic graphs under two backbone architectures. The paper also releases code and includes ablations of the loss components and triangle sources. The central concern is whether the reported accuracy gains are attributable to the rewiring mechanism itself or to leakage of validation/test labels into the triangle selector through Lcontr; this must be resolved before the contribution can be assessed.

major comments (4)
  1. [Section 4.2, Lcontr definition] The contrastive loss Lcontr is summed over all candidate triangles T and uses y^triangle_ijk = 1 if at least two of the three nodes share the same class label. Under the 60/20/20 split in Section 5.2, T includes triangles containing validation and test nodes, so the selector is trained with validation and test labels. Because the selected triangles determine E* used for GNN training and evaluation, test labels can leak into the topology and inflate the reported accuracies in Tables 2 and 3. This directly affects the paper's central 9/10 claim. Please restrict Lcontr to triangles whose vertices are all in Vtrain (or otherwise remove any dependence on non-training labels), rerun the experiments, and report whether the accuracy gains persist.
  2. [Section 4.2, Eq. (5) and graph reconstruction] The paper claims 'joint optimization of triangle selection and downstream classification', but the described pipeline does not support this. The rewired graph is reconstructed by thresholding p_ijk at 0.5 (Section 4.1), so the GNN loss LGNN cannot backpropagate into the selector. The selector loss Lselector = Lcontr + Lpart + Lstruct (Eq. 5) contains no classification term. Moreover, Lstruct and Lpart are computed over the discrete set Tsel and appear non-differentiable with respect to p_ijk unless a straight-through or soft-count estimator is used, which is not specified. The only differentiable supervision for the selector is Lcontr, which is the same loss that uses test/validation labels. Please clarify the actual optimization path, or implement a differentiable relaxation (e.g., soft edge weights from p_ijk) and state explicitly whether LGNN updates the selector.
  3. [Tables 2 and 3, Roman-Empire row] The JDR baseline is reported as 71.23±0.18 with GCN (Table 2) but 62.09±0.18 with GAT (Table 3) on Roman-Empire, a difference of 9.14 accuracy points for the same upstream rewiring method. TRIGON itself changes from 66.52 to 64.36 between the same two tables. This large inconsistency needs explanation; if JDR is retrained per backbone, the protocol should be stated, otherwise the comparison is not reliable. The claim of 9/10 wins 'regardless of backbone' depends on this point being resolved.
  4. [Table 1 and Fig. 2] Structural properties are reported without any measure of variability. TRIGON's triangle selection is stochastic (Gumbel-Softmax) and depends on training runs, so the diameter, spectral gap, and effective resistance values in Table 1 and Fig. 2 should be accompanied by means and standard deviations over the same number of seeds used for accuracy, with the exact protocol (which epoch's graph is analyzed) stated. This is necessary to support the 'markedly improved structural properties' claim.
minor comments (4)
  1. [Section 3.1, Eq. (3)] The notation is inconsistent: the paper first writes diam(G) = Ω(√N), then remarks 'writing diam(G) ∈ Ω(N) indicates...'. The latter should refer to Ω(√N). Please correct.
  2. [Section 5.3] The sentence 'classification accuracy improvement exceeding 25% compared to the original graph' is ambiguous (relative vs. absolute improvement). Since several baselines are within a few points of TRIGON, please state whether 25% is relative or absolute and give the supporting numbers.
  3. [Figures 4 and 5] The ablation plots do not show error bars or significance information. Given the small accuracy differences in some panels (e.g., Cora), please add runs/error bars or state that differences are within noise.
  4. [References] There are several typographical issues in the bibliography (e.g., 'Fan rk chung' in [48], duplicated [12]/[13]). Please clean up the reference list.

Circularity Check

1 steps flagged

TRIGON's selector is trained with validation/test labels via Lcontr, leaking test labels into the rewired topology; the reported SOTA accuracy is partly an artifact of this leakage.

specific steps
  1. fitted input called prediction [Section 4.2, 'Contrastive triangle label loss' (Lcontr) and Section 5.2 data split]
    "for each (i,j,k)∈T, we define: y^triangle_ijk = 1 if at least two nodes among {i,j,k} share the same label, 0 otherwise. We then apply a contrastive loss function ... Lcontr = 1/|T| ∑_{(i,j,k)∈T} (1−y^triangle_ijk)·p^2_ijk + y^triangle_ijk·(1−p_ijk). ... For all datasets, we follow the same data split: 60% of nodes are used for training, 20% for validation, and the remaining 20% for testing."

    Lcontr is computed over all candidate triangles T without a Vtrain mask, while y^triangle uses the class labels of every node in the triangle. Under the 60/20/20 split, this includes validation and test nodes. The selector's probabilities p_ijk determine Tsel and hence the rewired edge set E★ = ∪_{Tsel}{(i,j),(j,k),(k,i)} that the GNN is trained and evaluated on. Therefore test labels are used to construct the very topology on which test accuracy is measured. The reported 9/10 SOTA claim is not an out-of-sample evaluation of TRIGON: the triangle selector has been fit to the test labels, so the accuracy gain is partly a label-reconstruction artifact. This is load-bearing because removing Lcontr (Fig. 5) degrades accuracy.

full rationale

The paper's theoretical motivation (Section 3) uses standard external bounds (effective-resistance bound, planar diameter lower bound, Cheeger inequality) and does not fit those targets, so it is not circular. The use of the authors' previous Delaunay-rewiring paper [2] is as a baseline and motivation, not as an unsupported uniqueness/load-bearing justification. However, the empirical central claim is compromised by the contrastive triangle loss: Lcontr is minimized over all nodes' labels, not just Vtrain. Since the selected triangles define the rewired graph used by the GNN, validation and test labels leak into the training of the topology. The paper even contrasts LGNN, which is explicitly averaged over Vtrain, with Lcontr, which is summed over |T|, making the missing mask conspicuous. This makes the reported accuracy improvements partially circular in an evidential sense: the 'prediction' on the test set is influenced by the test labels through the selector. The structural property comparisons (diameter, spectral gap, effective resistance) are reported after training and are not used to set constants, so they are not circular. The 'joint optimization' wording is also overstated because LGNN is not part of Lselector and the threshold-based reconstruction is non-differentiable, but that is a consistency issue rather than a circular derivation. Overall, one load-bearing evaluation step is circular/leaky, so the score is 6 rather than a full 8-10.

Axiom & Free-Parameter Ledger

5 free parameters · 6 axioms · 0 invented entities

The method is a standard supervised learning pipeline. The main assumptions are the richness of the candidate triangle set and the validity of the Gumbel-Softmax surrogate. No new physical or conceptual entities are introduced.

free parameters (5)
  • Gumbel-Softmax temperature τ = not reported
    Hand-chosen hyperparameter controlling the hardness of the differentiable triangle selection; no sensitivity analysis is provided.
  • Triangle selection threshold = 0.5
    Arbitrary cutoff for defining T_sel; no justification and the inference-time procedure is not specified.
  • kNN parameter k = 10 or 20 depending on dataset
    Grid-searched per dataset; determines the candidate triangle set from feature space.
  • Per-class participation scalars π_c = learned
    Introduced in the class-wise participation regularization; learned to balance triangle participation per class.
  • Triangle encoder and selector MLP weights = learned
    Standard trained parameters of f_MLP and f_sel; listed for completeness as they are fitted to the training data.
axioms (6)
  • standard math Cheeger inequality and diameter-spectral bound (Eq. 1)
    Used to argue that a smaller graph diameter implies a larger spectral gap, connecting structural properties to message passing.
  • standard math Effective resistance bound R_eff(i,j) ≤ 2/(t(i,j)+2)
    Used to justify that edges with many triangles support low-resistance communication.
  • standard math Planar graphs have Ω(√N) diameter and vanishing spectral gap
    Used to motivate the need for non-planar triangulations to improve global connectivity.
  • domain assumption Gumbel-Softmax is a valid differentiable surrogate for discrete triangle selection
    The paper relies on this relaxation to train through the selection mechanism; no formal guarantee is given.
  • domain assumption The three candidate graph views provide a sufficient triangle vocabulary
    Central to the method: any useful new edge must be part of at least one candidate triangle; otherwise TRIGON cannot create it.
  • domain assumption Alternating optimization between selector and GNN converges to a good solution
    The two-stage training (selector loss, then GNN loss) is not analyzed; the paper assumes it works in practice.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks." pith.science (2026). https://pith.science/paper/GU4FGZGH

@misc{pith2026250819071,
  author       = {Pith},
  title        = {Pith review of: Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GU4FGZGH}},
  note         = {Machine review of arXiv:2508.19071}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Graph Neural Networks (GNNs) have emerged as the leading paradigm for learning over graph-structured data. However, their performance is limited by issues inherent to graph topology, most notably oversquashing and oversmoothing. Recent advances in graph rewiring aim to mitigate these limitations by modifying the graph topology to promote more effective information propagation. In this work, we introduce TRIGON, a novel framework that constructs enriched, non-planar triangulations by learning to select relevant triangles from multiple graph views. By jointly optimizing triangle selection and downstream classification performance, our method produces a rewired graph with markedly improved structural properties such as reduced diameter, increased spectral gap, and lower effective resistance compared to existing rewiring methods. Empirical results demonstrate that TRIGON outperforms state-of-the-art approaches on node classification tasks across a range of homophilic and heterophilic benchmarks.

Figures

Figures reproduced from arXiv: 2508.19071 by Fragkiskos D. Malliaros, Hugo Attali, Nathalie Pernelle, Thomas Papastergiou.

Figure 1
Figure 1. Figure 1: Overview of the TRIGON pipeline. (1) Triangles from the complementary input graphs are aggregated to capture [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Mean resistance among top high-resistance edges across four datasets. TRIGON achieves the lowest resistance in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Effect of GCN model depth on classification accuracy across Chameleon, Cora, and Citeseer. TRIGON outperforms [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: Impact of each loss component on classification [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey

    cs.LG 2026-05 unverdicted novelty 2.0

    A survey reviewing graph rewiring methods that modify topology to mitigate over-squashing and over-smoothing in GNNs.

Reference graph

Works this paper leans on

64 extracted references · 49 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Uri Alon and Eran Yahav. 2021. On the bottleneck of graph neural networks and its practical implications. InInternational Conference on Learning Representations

    work page 2021

  2. [2]

    Hugo Attali, Davide Buscaldi, and Nathalie Pernelle. 2024. Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation. In Forty-first International Conference on Machine Learning . https://openreview. net/forum?id=uyhjKoaIQa

    work page 2024

  3. [3]

    Hugo Attali, Davide Buscaldi, and Nathalie Pernelle. 2024. Rewiring techniques to mitigate oversquashing and oversmoothing in GNNs: A survey. arXiv preprint arXiv:2411.17429 (2024)

    Pith/arXiv arXiv 2024

  4. [4]

    Hugo Attali, Davide Buscaldi, and Nathalie Pernelle. 2025. Curvature constrained MPNNs: Improving message passing with local structural properties. Data & Knowledge Engineering 156 (2025), 102382

    work page 2025

  5. [5]

    Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. 2022. Oversquashing in GNNs through the lens of information con- traction and graph expansion. In 2022 58th Annual Allerton Conference on Com- munication, Control, and Computing (Allerton) . IEEE, 1–8

    work page 2022

  6. [6]

    Bronstein, and Francesco Di Giovanni

    Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, and Francesco Di Giovanni. 2024. Locality-Aware Graph Rewiring in GNNs. In The Twelfth International Conference on Learning Representations. https://openreview. net/forum?id=4Ua4hKiAJX

    work page 2024

  7. [7]

    Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. 2023. Un- derstanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning . PMLR, 2528–2547

    work page 2023

  8. [8]

    Chen Cai and Yusu Wang. 2020. A note on over-smoothing for graph neural networks. Graph Representation Learning (2020)

    work page 2020

  9. [9]

    Castro-Correa, Jhony H

    Jhon A. Castro-Correa, Jhony H. Giraldo, Mohsen Badiey, and Fragkiskos D. Malliaros. 2024. Gegenbauer Graph Neural Networks for Time-Varying Signal Reconstruction. IEEE Transactions on Neural Networks and Learning Systems 35, 9 (2024), 11734–11745

    2024

  10. [10]

    Ashok K Chandra, Prabhakar Raghavan, Walter L Ruzzo, and Roman Smolensky

    work page

  11. [11]

    Jeff Cheeger. 1970. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis: A Symposium in Honor of Salomon Bochner (PMS-31) . Princeton University Press

    work page 1970

  12. [12]

    Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. 2020. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 34. 3438–3445

    work page 2020

  13. [13]

    Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. 2020. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence , Vol. 34

    work page 2020

  14. [14]

    Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing 14, 1 (1985), 210–223

    work page 1985

  15. [15]

    Fan RK Chung and Fan Chung Graham. 1997. Spectral graph theory . American Mathematical Soc

    work page 1997

  16. [16]

    Andreea Deac, Marc Lackenby, and Petar Veličković. 2022. Expander graph propagation. In Learning on Graphs Conference . PMLR, 38–1

    work page 2022

  17. [17]

    Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. 2023. On over-squashing in message passing neural networks: The impact of width, depth, and topology. InICML. PMLR, 7865–7885

    work page 2023

  18. [18]

    Mathis, Chaitanya K

    Alexandre Duval, Simon V. Mathis, Chaitanya K. Joshi, Victor Schmidt, Santiago Miret, Fragkiskos D. Malliaros, Taco Cohen, Pietro Lio, Yoshua Bengio, and Michael M. Bronstein. 2023. A Hitchhiker’s Guide to Geometric GNNs for 3D Atomic Systems. CoRR abs/2312.07511 (2023)

    Pith/arXiv arXiv 2023

  19. [19]

    Malliaros, Yoshua Bengio, and David Rolnick

    Alexandre Duval, Victor Schmidt, Alex Hernández-García, Santiago Miret, Fragkiskos D. Malliaros, Yoshua Bengio, and David Rolnick. 2023. FAENet: Frame Averaging Equivariant GNN for Materials Modeling. In International Conference on Machine Learning, ICML

    work page 2023

  20. [20]

    Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. 2022. Long range graph benchmark. Advances in Neural Information Processing Systems 35 (2022), 22326–22340

    work page 2022

  21. [21]

    Herbert Edelsbrunner. 2000. Triangulations and meshes in computational geom- etry. Acta numerica 9 (2000), 133–213

    work page 2000

  22. [22]

    Lukas Fesser and Melanie Weber. 2023. Mitigating Over-smoothing and Over- squashing using Augmentations of Forman-Ricci Curvature. InThe Second Learn- ing on Graphs Conference

    work page 2023

  23. [23]

    Robin Forman. 2003. Bochner’s Method for Cell Complexes and Combinatorial Ricci Curvature

    work page 2003

  24. [24]

    Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. In International conference on machine learning . PMLR, 1263–1272

    2017

  25. [25]

    Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros. 2023. On the trade-off between over-smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM international CIKM . 566–576

    work page 2023

  26. [26]

    Christoph Goller and Andreas Kuchler. 1996. Learning task-dependent dis- tributed representations by backpropagation through structure. In Proceedings of International Conference on Neural Networks (ICNN’96) , Vol. 1. IEEE, 347–352

    work page 1996

  27. [27]

    Chenghua Gong, Yao Cheng, Jianxiang Yu, Can Xu, Caihua Shan, Siqiang Luo, and Xiang Li. 2024. A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions. arXiv preprint arXiv:2401.09769 (2024)

    Pith/arXiv arXiv 2024

  28. [28]

    Marco Gori, Gabriele Monfardini, and Franco Scarselli. 2005. A new model for learning in graph domains. InProceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. , Vol. 2. IEEE, 729–734

    work page 2005

  29. [29]

    Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Gio- vanni. 2023. DRew: Dynamically Rewired Message Passing with Delay. In Inter- national Conference on Machine Learning . PMLR, 12252–12267

    work page 2023

  30. [30]

    Zhangjin Huang, Yuxin Wen, Zihao Wang, Jinjuan Ren, and Kui Jia. 2024. Surface reconstruction from point clouds: A survey and a benchmark. IEEE transactions on pattern analysis and machine intelligence (2024)

    work page 2024

  31. [31]

    Eric Jang, Shixiang Gu, and Ben Poole. 2017. Categorical Reparameterization with Gumbel-Softmax. In International Conference on Learning Representations . https://openreview.net/forum?id=rkE3y85ee

    2017

  32. [32]

    Jürgen Jost and Shiping Liu. 2014. Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs. Discrete & Computational Geometry 51, 2 (2014), 300–322

    work page 2014

  33. [33]

    Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montúfar. 2023. FoSR: First- order spectral rewiring for addressing oversquashing in GNNs. In International Conference on Learning Representations (ICLR)

    work page 2023

  34. [34]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the International Conference on Learning Representations (ICLR)

    work page 2017

  35. [35]

    Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. 2019. Dif- fusion improves graph learning. In Advances in neural information processing systems (NeurIPS)

    work page 2019

  36. [36]

    Jonas Linkerhägner, Cheng Shi, and Ivan Dokmanić. 2025. Joint Graph Rewiring and Feature Denoising via Spectral Resonance. In The Thirteenth International Conference on Learning Representations . https://openreview.net/forum?id= zBbZ2vdLzH

    work page 2025

  37. [37]

    Richard J Lipton and Robert Endre Tarjan. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 2 (1979), 177–189

    work page 1979

  38. [38]

    Larsen Louder and Juan Souto. 2012. Diameter and spectral gap for planar graphs. arXiv preprint arXiv:1204.4435 (2012)

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  39. [39]

    Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. 2021. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.05641 (2021)

    Pith/arXiv arXiv 2021

  40. [40]

    Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, Vol. 33. 4602–4609

    work page 2019

  41. [41]

    Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. 2023. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning . PMLR, 25956–25979

    work page 2023

  42. [42]

    Yann Ollivier. 2007. Ricci curvature of metric spaces. Comptes Rendus Mathema- tique 345, 11 (2007), 643–646

    work page 2007

  43. [43]

    Kenta Oono and Taiji Suzuki. 2020. Graph neural networks exponentially lose ex- pressive power for node classification. Proceedings of the International Conference on Learning Representations (2020)

    work page 2020

  44. [44]

    Malliaros

    George Panagopoulos, Nikolaos Tziortziotis, Michalis Vazirgiannis, Jun Pang, and Fragkiskos D. Malliaros. 2024. Learning graph representations for influence maximization. Social Network Analysis and Mining 14, 1 (2024), 203

    work page 2024

  45. [45]

    Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang

  46. [46]

    Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. 2023. A critical look at the evaluation of GNNs under het- erophily: are we really making progress?. In International Conference on Learning Representations

    work page 2023

  47. [47]

    Chendi Qian, Andrei Manolache, Kareem Ahmed, Zhe Zeng, Guy Van den Broeck, Mathias Niepert, and Christopher Morris. 2023. Probabilistically rewired message- passing neural networks. arXiv preprint arXiv:2310.02156 (2023)

    Pith/arXiv arXiv 2023

  48. [48]

    Fan rk chung and Fan Chung Graham. 199è. spectral graph theory (American Mathematical)

    work page

  49. [49]

    Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2021. Multi-scale attributed node embedding. Journal of Complex Networks 9, 2 (2021), cnab014

    2021

  50. [50]

    Areejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost

    work page

  51. [51]

    Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29, 3 (2008), 93–93

    2008

  52. [52]

    Nicholas Sharp and Maks Ovsjanikov. 2020. Pointtrinet: Learned triangulation of 3d point sets. In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXIII 16 . Springer, 762–778

    work page 2020

  53. [53]

    Konstantinos Sotiropoulos and Charalampos E Tsourakakis. 2021. Triangle-aware spectral sparsifiers and community detection. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining . 1501–1509

    work page 2021

  54. [54]

    Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. 2009. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining . 807–816

    2009

  55. [55]

    Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. 2022. Understanding over-squashing and bot- tlenecks on graphs via curvature. Proceedings of the International Conference on Learning Representations (2022)

    work page 2022

  56. [56]

    Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. Proceedings of the International Conference on Learning Representations

    work page 2018

  57. [57]

    Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang. 2024. Understanding heterophily for graph neural networks. arXiv preprint arXiv:2401.09125 (2024)

    Pith/arXiv arXiv 2024

  58. [58]

    Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. In IEEE transactions on neural networks and learning systems , Vol. 32. IEEE, 4–24

    work page 2020

  59. [59]

    Lingxiao Zhao and Leman Akoglu. 2019. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint arXiv:1909.12223 (2019)

    Pith/arXiv arXiv 2019

  60. [60]

    Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. 2022. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082 (2022)

    Pith/arXiv arXiv 2022

  61. [61]

    Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems

    work page 2020

  62. [1989]

    In Proceedings of the twenty-first annual ACM symposium on Theory of computing

    The electrical resistance of a graph captures its commute and cover times. In Proceedings of the twenty-first annual ACM symposium on Theory of computing . 574–586

    work page

  63. [2018]

    Scientific reports 8, 1 (2018), 8650

    Comparative analysis of two discretizations of Ricci curvature for complex networks. Scientific reports 8, 1 (2018), 8650. Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks CIKM ’25, November 10–14, 2025, Seoul, Republic of Korea

    work page 2018

  64. [2020]

    In Advances in neural information processing systems (ICLR)

    Geom-gcn: Geometric graph convolutional networks. In Advances in neural information processing systems (ICLR)

    work page

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.