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

1. Time complexity comparison

$T$ is the steps of ODE, $L$ is the number of layers. GBN has the same time complexity as GraphNormv2.

2. On Lemma 5.3

Lemma 5.3 claims that there exists some source term to combat over-smoothing, so that we can learn such source term with an MLP, supporting our design.

3. Link prediction performance comparison to traditional MPNNs

We show the link prediction results in terms of AUC (%).

The proposed GBN consistently achieves the best link prediction results on Cora, Citeseer and CS datasets, and receives at least 5% performance gain compared to traditional MPNNs.

4. Boundary nodes and the connection to GCN

We specify that the proposed GBN does not need to explicit identify the boundary nodes, but it is equipped with a neural boundary indicator adopting the soft assignment. That is, the boundary nodes are jointly learned with the model.

There exist special cases of graphs without boundary nodes, e.g., a complete graph where each node is connected to all the other nodes. The soft indicator approaches to $0$ for all the nodes.

We emphasize that GBN is applicable to any graphs, regardless of the existence of boundary nodes, since we locally adjust the message-passing at the boundary nodes with soft assignment. Also, the proposed GBN recovers the vanilla GCN when $\gamma$ and $\beta$ are eliminated.

5. Computational overhead against the vanilla GCN

The computational complexity of the proposed GBN is $\mathcal O(\|\mathcal V\|+\|\mathcal E\|)$, which is the same as the vanilla GCN, where $\mathcal O(\|\mathcal V\|)$ is for feature transformation and $\mathcal O(\|\mathcal E\|)$ for aggregation. $\mathcal V$ and $\mathcal E$ denote the node set and edge set, respectively.

That is, we jointly mitigate over-smoothing and over-squashing via a new message-passing paradigm grounded on Riemannian boundary condition with no computational overhead.

6. Implementation details

1. For the initial values of boundary condition coefficients, $\gamma$ and $\beta$ are given as 2-layer MLPs. We do not need to explicitly construct $\alpha$, since $\alpha$ is nonzero, and can be divided by both $\gamma$ and $\beta$. Thus, $\gamma$ and $\beta$ are randomly initialized and jointly learned with the model.

2. For the neural architecture of the indicator, the indicator is a learnable function to determine whether or not the node is on the boundary, and it needs the neighborhood information for the boundary judgment. Accordingly, we conduct feature mapping and aggregation. Then, a sigmoid function is utilized to get the soft assignment values to identify the boundary nodes. This indicator only computes once in the beginning.

1. Manifold interpretation of benchmark graphs

The benchmark graphs are inherently connected to a Riemannian manifold. Theoretically, a graph is regarded as the discrete analogy to a certain Riemannian manifold [1]. It motivates us to study MPNN with Riemannian geometry. As an empirical observation, we take the Computer dataset for instance. Rather than Euclidean, it can be decomposed as a -1.15-curvature hyperbolic component of weight 0.61, a 0-curvature component of weight 0.18, and a +0.72-curvature hyperbolic component of weight 0.21.

Note that we do not focus on the optimal embedding space or curvature distribution of the graphs, but explore the functional space over the manifold to combat over-smoothing and over-squashing.

[1] Chung, F.R.K. Spectral Graph Theory. AMS, 1997.

2. The term of GBN

We will improve the presentation. The term comes from Graph Boundary Conditioned Message Passing Neural Network as in Line 228. We will explain GBN in Abstract in Line 13 as follows: “We design a Graph Boundary conditioned message passing Neural network (GBN) with local bottleneck adjustment”

3. Scalability on large graphs and long-range graph benchmark

For large graphs, we do the experiment on NVIDIA GeForce RTX 4090, and 16 vCPU Intel Xeon Gold 6430.

OOM is short for Out-Of-Memory. We achieve the best node classification results on ogbn-arXiv and ogbn-product, and promising graph-level task performance on peptides-func.

4. Updating rule in Sec. 6

We do appreciate the careful review on Appendix/Code for the derivation and implementation of the GBN’s updating rule.

In addition, we would like to provide more explanation of the proposed updating rules:

1. We first describe the behavior of the interior nodes and boundary nodes behavior in heat diffusion together. Without loss of generality, we first assume that the boundary nodes are recognized, then by reordering the nodes, we have the blocked Laplacian matrix and equation system as in Eq. (14). Then, the heat diffusion proceeds on the interior subgraphs, influenced by boundary condition, which form a linear equation in matrix form in Eq. (100), Appendix B.9.
2. Then we use the numerical method (e.g., Jacobi method) to iteratively solve the linear equation in Eq. (100), the details are in Lemma 6.2. The results in Eq. (18) exactly meets the form the traditional MPNNs but has different essential and more favorable properties that prevents over-smoothing and over-squashing.
3. To adopt learning ability, we fix the results in Lemma 6.2 with nonliear activation functions and learnable MLPs, so that we obtain the updating rules Eq. (18) which still have nice properties that prevents over-squashing by Theorem 6.3 and over-smoothing by nonhomogeneous boundary condition in Lemma 5.3 and Theorem 5.4.
4. Now, under above framework, we need to determine which or how which a node being a boundary nodes. Since boundary condition affects a lot on its neighborhood, so we adopt a simple GCN layer (only include aggregation and MLP) and a sigmoid function to compute soft weights of indicators in Eq. (17) at the beginning phase of GBN architecture. This allows gradients to flow through the boundary detection mechanism, enabling end-to-end adaptation.
5. To make the boundary condition more flexible and be able to learn complex graph structures, we assign different $(\alpha, \beta, \gamma)$ to each boundary node. The values are computed by 2-layer MLPs.
6. The model name GBN comes from the important tool, the boundary condition, we use to solve the over-smoothing and over-squashing problem in GNN. The complete name is Graph Neural Network with Boundary Condition.

5. On Eq. 18

It is interesting to view Eq. (18) as a graph filter. From the lens of graph signal processing, the matrix $\mathbf{D}^{-1}(\mathbf{V}+\mathbf{U})$ can be treated as a local graph shift operator, which adaptively interpolates between a low-pass filter and a high-pass filter. The filter's property is controlled by Robin boundary condition, i.e., each pair $(\alpha_i, \beta_i)$ or $p_i=\frac{\beta_i}{\alpha_i}$:

• It tends to act as a low-pass filter as $p_i$ increase, while shifting to high-pass filter if $p_i$ approaches 0.
• For $p_i \in (0,1)$, it is a band-pass filter that chooses intermediate frequencies to flow by.

6. Visualization of Boundary Assignment

We use the synthetic graph in the Case Study for elaboration. As shown in Fig. 1 in the supplementary material, the synthetic graph consists of two 10-node complete graphs (i.e., the source on the left of nodes 14-23 and the target on the right of nodes 0-9) with a line connecting them (nodes 10-13). Owing to the NeurIPS policy, we present the visualization of boundary assignment as in the table below.

Note that, the joint node 9 of the line and the right complete graph is labelled as the boundary of 100%, which lies in the topological bottleneck where the message passing should be locally adjusted. Note that, the nodes in the right complete graph are marked as 99.9%, since they are topologically equivalent and affected by node 9. Also, the nodes 10-13 at the bottleneck need to adjust the information flow, and they are softly assigned as the boundary nodes.

7. Related Work of NeurIPS’24 paper (Unitary convolutions for learning on graphs and groups).

We will include the discussion of the NeurIPS’24 paper, which is an interesting work to mitigate over-smoothing with the solid theory of unitary group convolution.

We will cite it in Sec. of Related Work-Over-smoothing as follows:

[NeurIPS’24] present 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.

Dear Reviewer QJWv,

Thanks again for your time and constructive comments! We are so glad to address your concerns.

First, we would like to specify the empirical settings of Long-range Graph Benchmark in the rebuttal. GCN follows the original setting as (Long Range Graph Benchmark. Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, Dominique Beaini. NeurIPS 2022), which is untuned.

Next, we show the performance comparison following [1], where Laplacian positional encoding is adopted by both GCN and the proposed GBN. We train GBN with 1400 iterations, and show the results as follows,

We will specify the term of GBN at its first occurrence, improve the elaboration in Sec. 6, and include the visualization in the one additional page in the camera-ready version.

Also, we are dedicated to completing the experiment of all the baselines with the tuned setups, and including a detailed discussion.

Your endorsement is important to us!

Best regards,

All authors of submission 6779

1. On novelty and local Riemannian geometry

The novelty of our work lies in that we introduce the local adjustment to message passing paradigm from the perspective of Riemannian geometry. The notion of “local” emphasizes that we locally adjust message passing via boundary condition, rather than any global criteria, e.g., spectral gap. Also, we clarify that: our theoretical contribution is not the introduction of geometric notion but the establishment of nonhomogeneous boundary condition.

Ricci curvature is defined on the edges and describes the connectivity over the graph. According to the definition (Eq. 4 in [1]), calculating Ricci curvature necessitates finding shortest paths between all node pairs (or sampled neighborhoods), inherently traversing the entire graph.

We recognize the effectiveness of (curvature-guided) graph rewriting methods, and consider that they are the natural solution as over-squashing is related to the topological bottlenecks in the graph structure. However, our work is inherently different from this research line:

• Graph rewriting focuses on altering the original graph structure so that over-smoothing/over-squashing is mitigated under traditional message-passing.
• We maintain the original graph structure but refine the message-passing paradigm to jointly mitigate over-smoothing and over-squashing.

We will paraphrase this sentence for clarity as follows:

We introduce the local adjustment to the message passing paradigm with nonhomogeneous boundary conditions of Riemannian geometry.

2. On ICML’24 (PANDA)

Node Classification Performance in terms of ACC on 7 Datasets

The proposed GBN consistently achieves better classification results than PANDA.

Performance on Long-range Dependence in terms of MSE

The proposed GBN presents superior information transfer ability on Line, Ring, and Cross-Ring datasets. It shows the ability to capture long-range dependence.

We will include the discussion of this insightful paper in Sec. of Related Work, and cite it as follows:

To combat over-squashing, [PANDA] present a novel approach to select nodes with high centrality to expand in width to encapsulate the growing influx of signals from distant nodes.

In addition, we would like to specify the difference between PANDA and the proposed GBN: PANDA changes the way of neighborhood aggregation without topological considerations, but GBN combines the (topological) boundary condition with functional behavior.

3. Difference between external input and initial residual connection

On the formulation: The domain of definition is different. Concretely, the initial residual connection is uniformly applied to all nodes. In contrast, the proposed external input (the $\gamma$-term) is exclusively defined for boundary nodes as in Definition 6.1 and Eq. 14. The formulation of external input in Eq. 14 is derived from the nonhomogeneous Robin boundary condition, which is inherently different from that of previous MPNN residual connections.

On the theory and guarantees: Residual connections are primarily heuristic additions (e.g., identity mappings), whereas our $\gamma$-term arises rigorously from Riemannian boundary condition in Theorem 5.4. The proposed external input has theoretical guarantee. Concretely, the polynomial decay constraint for Dirichlet energy in Lemma 5.3 holds only at boundary nodes and vanishes in the interior (Remark B.6). Thus, applying external input at boundary nodes ensures the mitigation of over-smoothing.

4. The sentence in Line 160

We sincerely appreciate your comment, and will paraphrase this sentence for clarity as follows: “Edge deletion without careful consideration may hinder the information flow in message passing.”

Indeed, we recognize the sophisticated graph rewriting techniques, and have cited [1], [2], and [4] in the Related Work as follows:

In the line of graph rewriting, [1, 2, WWW’23] introduce edge addition-deletion algorithms in light of oversmoothing; [4] increases the spectral gap via edge deletion.

Though the advanced methods of carefully rewriting the graph structure are effective, it is still challenging to study the edge addition-deletion strategy. Thus, we explore an alternative direction – refine the message passing paradigm while maintaining the original structural topology and the computational complexity of traditional MPNNs.

5. Parameter sensitivity on MLP

In GBN, we utilize a 2-layer MLP with a hidden layer dimension of 256 by default. We conduct a sensitivity analysis on the hyperparameters of the layer and the hidden layer dimension, and GBN is generally robust to these hyperparameters.

1. Add explicit comparison to the related work in Line 83

References 17, 34, 35 and 47 are curvature-guided graph rewriting methods, which mitigate over-squashing through adding and/or deleting edges guided by curvature. Different from this line of work altering the original graph structure, we maintain the original graph structure while mitigating over-squashing with theoretical guarantees.

References 5, 10, 30, 33 and 53 extends MPNNs to certain Riemannian manifolds, following the traditional message-passing mechanism. In contrast, we propose a new, adaptive message-passing with nonhomogeneous boundary condition to jointly mitigate over-squashing and over-smoothing.

2. On the consistency of increasing spectral gap and adding edges w.r.t. over-squashing

Note that the topological bottleneck leads to over-squashing, but there exist other reasons resulting in over-squashing as well. (Indeed, a topological bottleneck is a sufficient but not necessary condition for causing over-squashing.) Also, both over-squashing and over-smoothing affect the effectiveness of message-passing (MPNNs).

• Adding edges, which enlarges the topological bottleneck, can be beneficial for mitigating over-squashing.
• The increase of the spectral gap $\lambda$ enlarges the topological bottleneck, as given in Theorem 4.1. However, the increase of spectral gap $\lambda$ also tends to accelerate gradient vanishing (Theorem 4.2) and over-smoothing (Theorem 4.3). Accordingly, we state that the increase of spectral gap $\lambda$ also has negative impacts on the expressiveness of MPNNs. The two statements are indeed consistent, and the key point here is that the topological bottleneck is not the only reason for over-squashing.

Hence, over-squashing cannot be mitigated by merely increasing $\lambda$ without considering other factors, e.g., gradient vanishing. It motivates our design of local adjustments taking into account both factors.

3. Relationship between graph rewriting and adjusting the spectral gap

On the one hand, graph rewriting directly alters the spectral gap $\lambda$: As in line 138 and Theorem 4.1, the spectral gap relates to the most bottlenecked region (characterized by Cheeger's constant) in a manifold or graph. The graph rewriting expands the bottlenecks to enlarge the spectral gap.

On the other hand, adjusting the spectral gap does not necessarily require graph rewriting: The message bottleneck is related to the graph topology and the strategy of message passing over the topology. Also, the spectral gap can be regulated without modifying the graph topology, and we leverage such fact in our work.

As proved in Sec. 5, GBN achieves this by introducing boundary conditions, the adaptive Robin condition (Eq. 13).

4. On $\gamma$ and $\beta$

In the ablation study, the fixed values $\gamma_0$ and $\beta_0$ were determined through a grid search on the validation set, $\gamma_0 \in [0,1]$, $\beta_0 \in [0,2]$. This process required significant computational effort to identify the optimal values. In addition, we observe that the optimal values vary across different graphs. Graphs are diverse, and the optimal boundary conditions are inherently related to the structural patterns. Therefore, we let \gamma and \beta be learnable in GBN.

1. The comparison to the related work in your rebuttal is good. Please consider adding it to the camera-ready version.
2. "both over-squashing and over-smoothing affect the effectiveness of message-passing (MPNNs)." should be stated explicitly in your paper.
3. Thanks for clarifying the relationship between graph rewriting and adjusting the spectral gap for me.
4. Compared to determining $\gamma$ and \beta using grid search, learning $\gamma$ and $\beta$ through a learning approach indeed involves less computational effort, which is a good design. I will keep my score.