This paper presents TRIGON, a novel graph reconstruction technique, to address the oversquashing and oversmoothing problems that hinder the performance of graph neural networks (GNNs), which have emerged as a leading method for learning graph-structured data. TRIGON is a framework that constructs rich, non-planar triangulations by selecting relevant triangles from various graph perspectives. By jointly optimizing triangle selection and classification performance, it generates reconstructed graphs with significantly improved structural properties, including a smaller diameter, larger spectral spacing, and lower effective resistance, compared to existing methods. Experimental results on node classification tasks across various homogeneous and heterogeneous benchmarks demonstrate that TRIGON outperforms state-of-the-art techniques.
