Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911126855352320 |
|---|---|
| author | Attali, Hugo Papastergiou, Thomas Pernelle, Nathalie Malliaros, Fragkiskos D. |
| author_facet | Attali, Hugo Papastergiou, Thomas Pernelle, Nathalie Malliaros, Fragkiskos D. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19071 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks Attali, Hugo Papastergiou, Thomas Pernelle, Nathalie Malliaros, Fragkiskos D. Machine Learning Artificial Intelligence 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. |
| title | Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2508.19071 |