Research map / Graph learning / GNN architectures
Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Delaunay Rewiring, which discards the input graph and rebuilds it by Delaunay-triangulating UMAP-reduced node features, to mitigate over-squashing and over-smoothing in GNN node classification.
Problem
GNN message passing suffers from over-squashing and over-smoothing, and existing rewiring methods depend on the input graph structure, need costly grid-searched hyperparameters, and are inapplicable when only node features are available.
Approach
Rebuild the graph entirely from node features: reduce features (or GCN embeddings) to 2D with UMAP and connect nodes via Delaunay triangulation, yielding a sparse, hyperparameter-free graph with bounded clique size (3) and fewer negatively curved edges.
Key results
- Delaunay Rewiring (DR) gives the best accuracy on all 7 heterophilic and 3 homophilic datasets with GCN backbone, e.g. Cornell 67.22 vs 47.73 for the best baseline (GTR), and Texas 70.46.
- On average DR yields about a 21.8% accuracy increase over base GCN and GAT.
- Against a 3-NN graph built from the same features, DR wins on 6 of 7 heterophilic datasets (e.g. Chameleon 74.28 vs 72.69).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Delaunay rewiring | GCN · Chameleon | accuracy: 65.35±0.54 -> 74.28 ±0.48 | Helped |
| Apply Delaunay rewiring | GCN · Squirrel | accuracy: 51.30±0.38 -> 65.25 ±0.26 | Helped |
| Apply Delaunay rewiring | GCN · Actor | accuracy: 30.02±0.22 -> 41.36 ±0.20 | Helped |
| Apply Delaunay rewiring | GCN · Texas | accuracy: 56.19 ±1.61 -> 70.46 ±1.61 | Helped |
| Apply Delaunay rewiring | GCN · Wisconsin | accuracy: 55.12±1.51 -> 70.98±1.50 | Helped |
| Apply Delaunay rewiring | GCN · Cornell | accuracy: 44.78 ±1.45 -> 67.22 ±1.48 | Helped |
| Apply Delaunay rewiring | GCN · Roman-empire | accuracy: 51.66 ±0.17 -> 61.99 ±0.14 | Helped |
| Apply Delaunay rewiring | GCN · Cora | accuracy: 87.73 ±0.25 -> 91.39 ±0.24 | Helped |
| Apply Delaunay rewiring | GCN · Citeseer | accuracy: 76.01 ±0.25 -> 81.14 ±0.34 | Helped |
| Apply Delaunay rewiring | GCN · Pubmed | accuracy: 88.20 ±0.10 -> 88.69 ±0.10 | Helped |
| Apply Delaunay rewiring | GAT · Chameleon | accuracy: 65.07 ±0.41 -> 72.04 ±0.37 | Helped |
| Apply Delaunay rewiring | GAT · Squirrel | accuracy: 50.87 ±0.56 -> 61.47 ±0.29 | Helped |
Surprising findings
- Triangulating raw features gave poor results on Chameleon and Squirrel (GCN 27.82 and 22.73), showing that feature quality strongly determines the Delaunay graph's usefulness.
- On Roman-empire the 3-NN graph beats DR (63.01 vs 61.99).
Limitations
- Performance depends on the quality of input features; poor features produce a poor triangulation.
- Evaluated only on node classification; long-range graph benchmarks left for future work.
- Some baselines (BORF, GTR) hit time limits (>=24h) on Squirrel, and some runs ran out of memory.
Experimental setup
Datasets: Chameleon Squirrel Actor Texas Wisconsin Cornell Roman-empire Cora Citeseer Pubmed
Benchmarks: Chameleon Squirrel Actor Texas Wisconsin Cornell Roman-empire Cora Citeseer Pubmed
Metrics: accuracy edge homophily Ollivier curvature distribution effective resistance
Baselines: GCN GAT DIGL FA SDRF FOSR BORF GTR 3-NN graph
Builds on: GCN GAT BORF SDRF FOSR GTR DIGL UMAP
Closest papers by meaning
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.87)
- The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited (ICLR 2025 · similarity 0.87)
- Over-squashing in Spatiotemporal Graph Neural Networks (NeurIPS 2025 · similarity 0.86)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.86)
- Graph Neural Networks Do Not Always Oversmooth (NeurIPS 2024 · similarity 0.86)
- Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.