Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks
This work addresses performance limitations in GNNs for graph-structured data, offering a novel rewiring method that is incremental but shows strong gains.
The paper tackled the problem of oversquashing and oversmoothing in Graph Neural Networks (GNNs) by introducing TRIGON, a graph rewiring framework that constructs enriched triangulations, resulting in improved structural properties and outperforming state-of-the-art methods on node classification tasks across homophilic and heterophilic benchmarks.
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.