Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models

Message Passing Neural Networks (MPNNs) is the building block of graph foundation models, but fundamentally suffer from oversmoothing and oversquashing. There has recently been a surge of interest in fixing both issues. Existing efforts primarily adopt global approaches, which may be beneficial in some regions but detrimental in others, ultimately leading to the suboptimal expressiveness. In this paper, we begin by revisiting oversquashing through a global measure -spectral gap λ -and prove that the increase of λ leads to gradient vanishing with respect to the input features, thereby undermining the effectiveness of message passing. Motivated by such theoretical insights, we propose a local approach that adaptively adjusts message passing based on local structures. To achieve this, we connect local Riemannian geometry with MPNNs, and establish a novel nonhomogeneous boundary condition to address both oversquashing and oversmoothing. Building on the Robin condition, we design a GBN network with local bottleneck adjustment, coupled with theoretical guarantees. Extensive experiments on homophilic and heterophilic graphs show the expressiveness of GBN. Furthermore, GBN does not exhibit performance degradation even when the network depth exceeds 256 layers. Recently, [47] demystifies how they affect the expressive power of MPNNs, while [3] develops a principled explanation via gradient vanishing, and bridges MPNNs and recurrent networks. 3 ⃝ Gating mechanism [8; 75; 76; 46] modulates gradient updates in the layers, and allows for different rates of message passing. 4 ⃝ Graph sparsification [11; 44] combats this issue from the structural perspective, given that some subgraphs, such as cliques, increase the risk of oversmoothing [39] . A theoretical review is provided in [31] . 5 ⃝ [32] presents a novel idea to transform the global spectral distribution in each layer of MPNN, while we focus on local adjustment of MPNN via boundary conditions. Different from designing additional modules or structural refinement, we focus on refining MPNN mechanism, not susceptible to oversmoothing. Oversquashing. 1 ⃝ It strongly depends on the graph structure, and thus a natural solution is graph rewriting, which typically adds edges to enlarge the topological bottlenecks, guided by Ricci curvature [64; 2; 18] or spectral analysis [30] . Also, graph transformers can be regarded as their generic form with learnable attentional weights [70; 21; 49]. [7] understands graph rewriting from the lens of effective resistance. Recently, it has been shown that incorporating virtual nodes is effective [45; 50]. [23] provides the theoretical aspects of oversquashing on depth, width, and topology of graphs. 2 ⃝ Recent studies jointly address oversmoothing via global treatments. In the line of graph rewriting, [39; 38; 20] introduce edge addition-deletion algorithms in light of oversmoothing; [28] increases the spectral gap via edge deletion; [4] conducts the feature rewriting with Delaunay triangulation. Recently, [27] considers the polynomial bases for the graph Fourier transform, while [42] designs an auxiliary module to prevent heterophily mixing. To combat over-squashing, [16] presents a novel approach to select nodes with high centrality to expand in width to encapsulate the growing influx of signals from distant nodes. In contrast to the previous global treatments, we introduce the local adjustment to message-passing paradigm with nonhomogeneous boundary conditions.