Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation

Hugo Attali, Davide Buscaldi, Nathalie Pernelle
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:1992-2008, 2024.

Abstract

GNNs rely on the exchange of messages to distribute information along the edges of the graph. This approach makes the efficiency of architectures highly dependent on the specific structure of the input graph. Certain graph topologies lead to inefficient information propagation, resulting in a phenomenon known as over-squashing. While the majority of existing methods address over-squashing by rewiring the input graph, our novel approach involves constructing a graph directly from features using Delaunay Triangulation. We posit that the topological properties of the resulting graph prove advantageous for mitigate oversmoothing and over-squashing. Our extensive experimentation demonstrates that our method consistently outperforms established graph rewiring methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-attali24a, title = {Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation}, author = {Attali, Hugo and Buscaldi, Davide and Pernelle, Nathalie}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {1992--2008}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/attali24a/attali24a.pdf}, url = {https://proceedings.mlr.press/v235/attali24a.html}, abstract = {GNNs rely on the exchange of messages to distribute information along the edges of the graph. This approach makes the efficiency of architectures highly dependent on the specific structure of the input graph. Certain graph topologies lead to inefficient information propagation, resulting in a phenomenon known as over-squashing. While the majority of existing methods address over-squashing by rewiring the input graph, our novel approach involves constructing a graph directly from features using Delaunay Triangulation. We posit that the topological properties of the resulting graph prove advantageous for mitigate oversmoothing and over-squashing. Our extensive experimentation demonstrates that our method consistently outperforms established graph rewiring methods.} }
Endnote
%0 Conference Paper %T Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation %A Hugo Attali %A Davide Buscaldi %A Nathalie Pernelle %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-attali24a %I PMLR %P 1992--2008 %U https://proceedings.mlr.press/v235/attali24a.html %V 235 %X GNNs rely on the exchange of messages to distribute information along the edges of the graph. This approach makes the efficiency of architectures highly dependent on the specific structure of the input graph. Certain graph topologies lead to inefficient information propagation, resulting in a phenomenon known as over-squashing. While the majority of existing methods address over-squashing by rewiring the input graph, our novel approach involves constructing a graph directly from features using Delaunay Triangulation. We posit that the topological properties of the resulting graph prove advantageous for mitigate oversmoothing and over-squashing. Our extensive experimentation demonstrates that our method consistently outperforms established graph rewiring methods.
APA
Attali, H., Buscaldi, D. & Pernelle, N.. (2024). Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:1992-2008 Available from https://proceedings.mlr.press/v235/attali24a.html.

Related Material