Graph neural networks (GNNs) have shown state-of-the-art performances in various applications. However, GNNs often struggle to capture long-range dependencies in graphs due to oversmoothing. In this paper, we generalize the concept of oversmoothing from undirected to directed graphs. To this aim, we extend the notion of Dirichlet energy by considering a directed symmetrically normalized Laplacian. As vanilla graph convolutional networks are prone to oversmooth, we adopt a neural graph ODE framework. Specifically, we propose fractional graph Laplacian neural ODEs, which describe non-local dynamics. We prove that our approach allows propagating information between distant nodes while maintaining a low probability of long-distance jumps. Moreover, we show that our method is more flexible with respect to the convergence of the graph's Dirichlet energy, thereby mitigating oversmoothing. We conduct extensive experiments on synthetic and real-world graphs, both directed and undirected, demonstrating our method's versatility across diverse graph homophily levels. Our code is available at https://github.com/RPaolino/fLode .
Paper
References (72)
Scroll for more · 38 remaining
Similar papers
Peer review
Summary
The authors propose two novel Fractional Graph Laplacian (FGL)-based neural Ordinary Differential Equations (ODEs): the fractional heat equation and the fractional Schrödinger equation. These solutions provide enhanced flexibility in the convergence of the Dirichlet energy and make the exponent of the fractional graph Laplacian a learnable parameter. This allows the network to adaptively decide the optimal exponent for a specific task and graph. The fractional graph Laplacian operator generalizes the Laplacian operator. The experimental results highlight the improvements of using fractional graph Laplacians, but the benefit is limited.
Strengths
1. The proposed FGL Neural ODE can be $\lambda-FD$ which extends the Neural ODE-based GNNs that are limited to being either LFD or HFD. 2. This paper generalizes the concepts related oversmoothing from undirected graphs to directed graphs.
Weaknesses
1. The application of the fractional graph Laplacian operator results in the loss of the graph's sparse property, transforming it into a dense even complete graph. 2. The paper's primary contribution appears to target oversmoothing issues, as suggested by the title. However, the evidence supporting the claim that the fractional graph Laplacian can mitigate oversmoothing in GNN is insufficient.The paper posits that the theory and experimental results presented counteract the issue of oversmoothness. However, based on [1], oversmoothness can still occur even when node features exist within an invariant space that has a rank greater than one. In this context, the paper's conclusions about oversmoothness mitigation defined using Dirichlet energy appear quite constrained. How would the proposed model fare with 256 layers stacked? How does it measure against the ODE-based methods (some are also designed to address oversmoothing), such as the recent work like GRAND[2], GraphCON [3], GRAFF [4], GRAND++[5] and GREAD [6]? 3. While the paper introduces concepts pertaining to directed graphs, the significant Theorem 5.3 only applies to undirected graphs, and Theorem 5.5 is solely restricted to the standard Laplacian where $\alpha=1$. Although it seems that the Fractional Graph Laplacian (FGL) may bridge the gap between homophilic and heterophilic graphs, the benefits of using FGL for directed graphs aren't clearly established. 4. The authors introduce several definitions, notably the Dirichlet energy for a directed graph (equation 1), but fail to provide solid justification for their choice. For instance, one could question why the energy is not defined in the following way: $$\sum_{i, j=1}^N a_{i, j}\left(\left\|\frac{\mathbf{x}_i}{\sqrt{d_i^{\text {in }}}}-\frac{\mathbf{x}_j}{\sqrt{d_j^{\text {in }}}}\right\|_2^2 +\left\|\frac{\mathbf{x}_i}{\sqrt{d_i^{\text {out }}}}-\frac{\mathbf{x}_j}{\sqrt{d_j^{\text {out }}}}\right\|_2^2\right).$$ The experimental results provided do not sufficiently substantiate these definitions or the theoretical assertions made in the paper. 5. Very poor experimental results: While the paper focuses on directed graph Laplacian, the enhancements it introduces seem to be quite narrow, especially when considering Table 2, the only table for directed graphs. The inclusion of several definitions and theories seems to add complexity to the paper without providing a substantial contribution to the GNN community. The authors also need to include the SOTA results on those datasets. 6. The usage of complex numbers, as in equation (5), should be justified convincingly. While this may be commonplace in pure mathematics or physics, it needs to be shown why such a model is necessary for tackling oversmoothness in GNNs. Recent developments, such as Pytorch's support for complex numbers, do not automatically warrant their use in all contexts. If equation (5) is utilized, it only increases the model's complexity and memory consumption. Therefore, a robust justification is needed. [1] Oono, Kenta, and Taiji Suzuki. "Graph neural networks exponentially lose expressive power for node classification." arXiv preprint arXiv:1905.10947 (2019). [2] Chamberlain, Ben, et al. "Grand: Graph neural diffusion." International Conference on Machine Learning. PMLR, 2021. [3] Rusch, T. Konstantin, et al. "Graph-coupled oscillator networks." International Conference on Machine Learning. PMLR, 2022. [4] Di Giovanni, F., Rowbottom, J., Chamberlain, B. P., Markovich, T., and Bronstein, M. M. (2022). Graph Neural Networks as Gradient Flows: Understanding Graph Convolutions via Energy. arXiv: 2206.10991 [cs, stat]. [5] Thorpe, Matthew, et al. "GRAND++: Graph neural diffusion with a source term." International Conference on Learning Representations. 2021. [6] Choi, Jeongwhan, et al. "GREAD: Graph Neural Reaction-Diffusion Networks." (2023).
Questions
1. In Table 1, could you provide the learned values for $\lambda_{K}(W)$ and $\lambda_{1}(W)$ for each dataset? Moreover, could you offer a detailed analysis of how these results relate to Theorem 5.3? Also, all the learned $\alpha$ values in Table 4 are greater than 0, so according to part(i) of Theorem 5.3, the FGL-ODE is still either L-FD or H-FD. Could you clarify under which circumstances the proposed $\lambda$-FD could be applied? 2. The paper doesn't clearly illustrate how the fractional Laplacian operator mitigates the oversmoothing issue, both from theoretical and experimental perspectives. More in-depth explanations and experiments are needed. 3. Is the FGL-based Neural ODE applicable to large-scale graph datasets, such as those in references [1] and [2]? 4. The results for the Cora dataset presented in Table 1 are inferior to MLP. Could you also display the results for the homophilic dataset using the data split method from reference [5]? 5. Table 1 seems to miss important baselines for heterophilic graphs, such as ACM-GNN[3] and ACMP[4]. It would be beneficial to include these. 6. The paper lacks ablation studies. Could you provide the node classification results for $\alpha=1$ in equations (4) and (5) of FLODE? As the main contribution appears to be the FGL, are there any ablation studies that use layer-wise FGL-based GNNs instead of the FGL Neural ODE? 7. Other questions please refer to weakness part. [1].Hu W, Fey M, Zitnik M, et al. Open graph benchmark: Datasets for machine learning on graphs[J]. Advances in neural information processing systems, 2020, 33: 22118-22133. [2].Lim D, Hohne F, Li X, et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods[J]. Advances in Neural Information Processing Systems, 2021, 34: 20887-20902. [3].Luan S, Hua C, Lu Q, et al. Revisiting heterophily for graph neural networks[J]. arXiv preprint arXiv:2210.07606, 2022. [4].Wang Y, Yi K, Liu X, et al. ACMP: Allen-Cahn Message Passing for Graph Neural Networks with Particle Phase Transition[J]. arXiv preprint arXiv:2206.05437, 2022. [5]. Shchur O, Mumme M, Bojchevski A, et al. Pitfalls of graph neural network evaluation[J]. arXiv preprint arXiv:1811.05868, 2018.
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
Yes, the authors addressed the limitations.
Summary
The paper extends the notion of Dirichlet energy to define oversmoothing in directed graphs. It introduces a fractional Laplacian operator that is used to create graph neural ODE architectures. The resulting designs are non-local and can alleviate oversmoothing. The paper provides empirical results (accuracy) on nine real-world benchmarks for node classification.
Strengths
* Overall, the paper is well-written and easy to follow. Also, the proposed framework (FLODE) is simple; * The proposed method works relatively well for both directed and undirected graphs (flexibility).
Weaknesses
- Novelty: I rank the novelty as moderate. First, directed symmetrically normalized laplacian has been previously used. Moreover, it seems that the advantages come mainly from the choice of diffusion operator. However, it is clear that the choice of diffusion operator impacts oversmoothing, and we can design, for instance, high-pass (or non-local) graph filters to alleviate oversmoothing. Last, there is no novelty in the evaluation setup. - Theory: Some theoretical results focus on the properties of the fractional Laplacian, which appears only complementary to the paper. As a result, the paper does not discuss empirical results in light of the theoretical ones. - Experiments: The empirical results are not strong. Except for Squirrel, the performance gains (over the second-best baseline) do not seem to be statistically significant. Also, the proposed model is the best-performing model only in 4 out of 9 datasets. In addition, the paper does not consider large-scale datasets from OGB, for instance.
Questions
**Questions and comments** 1. Why is it called Fractional graph laplacian if it is based on the decomposition of the normalized adjacency (SNA)? 2. Do the authors have any intuition to explain why the proposed method works so well on the Squirrel dataset? 3. Some parts could be improved for precision and clarity, e.g., - In the paragraph 'Homophily and Heterophily', the paper uses $i \in V$ to denote the distribution used in the expectation. What does it mean (e.g., uniform dist. over the nodes)? - In the introduction, the paper says: "a GNN that minimizes the Dirichlet energy is expected to perform well on homophilic graphs...". However, there is no dependency on the GNN --- x is defined as initial node features. 5. Running the ablation study on Appendix F3 to more datasets would be interesting and helpful to validate some intuitions behind the proposal. 6. There is a vast literature on methods for tackling oversmoothing in GNNs (DropEdge, etc.), enabling such approaches for heterophilic datasets. Shouldn't these approaches also be considered as baselines for comparison? 7. Have you tried employing an NN instead of using just a channel mixing matrix?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
The authors discuss the limitations of the proposal, mainly mentioning the computation cost associated with SVD.
Summary
The authors consider the problem of classification on attributed graphs with a geometrical approach. They introduce a fractional graph Laplacian for undirected and directed graphs. They generalize the notion of Dirichlet energy to directed graphs. They study the ODEs based on this Laplacian and prove that their solutions converge to high-, low- or middle-frequency patterns, for undirected graphs and for directed graphs in a particular case. Finally they implement these ODEs as GNNs and assess their performances.
Strengths
I do not know well this topic and can hardly evaluate how significant are the improvements this article brings.
Weaknesses
To my understanding a main point of this article is fractional Laplacian for directed graphs, but theorem 5.5 is restricted to the SNL.
Questions
On formatting: in the current state of the manuscript many intra-links are broken. Some figures of interest for understanding are not in the main text (I did not look at them). Maybe for table 1 the authors could use font formatting (bold, italic, ...) instead of colors. L. 245 « In accordance with the results in Section 5, we select W as a diagonal matrix. » could the authors develop? Part 6, for the directed SBM, what are the features? Out of curiosity: what happens if W is untied, i.e. taken time-dependent or different at each layer? Does one have the learned alpha small (or negative) for heterophilic datasets?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
2 fair
Limitations
The authors address a main limitation of their model, its computational complexity. They may conduct an experiment showing that truncating the SVD is correct.
Summary
The authors propose a neural ODE (FLODE) that uses a fractional graph Laplacian as an alternative to GNNs, which famously suffers from oversmoothing after a few layers. The heat equation $x'(t) = -L^{\alpha}x(t)W$ is shown to possess nice qualities wrt Dirichlet energy such that it does not always end up with a low frequency solution (i.e. oversmoothing as $t \to \infty$). Several experiments are done with synthetic, real, directed, and undirected graphs, and the proposed method are shown to perform comparably with existing method.
Strengths
Even though I am not an expert in neural-ODE based GNNs, I found the paper clearly written and easy to follow. The strength of this paper is in its theoretical analysis of the spectral values of their solutions. Based on a cursory reading of Di Giovanni et al (2022), and given that the learned $\alpha$s are often not 1 (Appendix Table 4), this does not seem to be a trivial extension of existing work.
Weaknesses
Please see questions below.
Questions
1. If Film is a heterophilic graph, I expected the learned exponent to be closer to 0, which is the case with Squirrel and Chameleon. Do the authors have a hypothesis about why this might be the case? 2. Similarly, do the authors have a hypothesis about why FLODE was not in the top three performing models for Film, Pubmed and Cora? 3. Have the authors actually inspected the eigenvalues and singular values of their models and compared them to the theoretical results? 4. I recommend using boldface and italics in addition to color in Table 1. In Figure 3, the line for FLODE should be thicker or have a different line style.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
Yes.
Thank you for the authors' response. Here is my feedback: Regarding Q1: However, Figure 2 showcases a synthetic cycle graph. Are there any realistic graphs where applying the $\lambda-FD$ would be necessary? **The gap between your theoretical framework and empirical results is evident**. For Q3: I find the response insufficiently persuasive. In my view, **the limitations of your method when applied to large-scale graphs are apparent**. For Q4: The results of your methods are **worse than GCN/GAT** on all Cora/Citeseer/Pubmed Datasets. For W2/Q2: Referring to Figure 1 in the provided PDF, it's essential to compare your results with other state-of-the-art deep GNNs. Moreover, as highlighted in [1], the squirrel and chameleon datasets contain a significant number of duplicate nodes. Evaluating your model's efficacy primarily based on these two datasets significantly does not provide a comprehensive assessment. You need to refer to the experiment settings in other deep GNN papers. [1]. Platonov, Oleg, et al. "A critical look at the evaluation of GNNs under heterophily: are we really making progress?." arXiv preprint arXiv:2302.11640 (2023).
We appreciate the feedback from the Reviewer. To address the raised points, we would like to emphasize two critical aspects: 1. We did not expect to achieve state-of-the-art performance on Cora or other homophilic graphs where node features with low Dirichlet Energy show promising results. 2. The essence of our work lies in introducing the fractional Laplacian, its theoretical advantages over standard Laplacians, and its demonstrable improvement over the standard Laplacian and flexibility across various graph datasets. Therefore, our emphasis is not solely on our performance metrics on Cora but instead on the broader contributions we present. --- Regarding Q1: We kindly but strongly disagree with the Reviewer's statement: "The gap between your theoretical framework and empirical results is evident." Our theoretical analysis is verified by the experiments, and vice versa, the experiments are fully backed up by our theoretical analysis, as shown in our general response (Point 2) and the supplementary pdf (Tab. 2, Fig. 1). We also back this up with Figs. 6 and 7 in our appendix and our ablation studies (see Point 1 in our general response). We have conducted a complete analysis w.r.t. the exponent since, in our model, $\alpha$ is an unconstrained learnable parameter. Hence, it could also be negative. The synthetic cycle graph serves as one illustrative example. Another example is Squirrel (e.g., Fig. 1 in the supplementary pdf), where the learned exponent is negative at depth 2. **The fact that the model only sometimes learns negative exponents does not change our alignment of theory and practice.** --- Regarding Q3: The limitations of our method are indeed clear, as stated in the "Limitation" section of the main paper. However, our model already comfortably accommodates medium size graphs of 20,000 nodes. Handling large-scale graphs is currently beyond the scope of our work. We would like to highlight that **before our work, the application of fractional Laplacians was restricted to tiny graphs (a few hundred nodes) due to the computation of Jordan decompositions.** --- Regarding Q4: Please note that in the main paper, our model performs better than GCN/GAT on both Citeseer and Pubmed. As of Cora, we perform slightly better than GAT but slightly worse than GCN. As previously clarified, we did not hyperparameter tune for that particular experiment. We rather followed the request of the Reviewer and demonstrated that in a low-labeling regime, our model substantially outperforms MLPs. The experiment was not meant to chase SOTA in this new split scenario, as it would have required more time for hyperparameter tuning. It is crucial to understand that **we do not assert superiority over smoothing models like GAT or GCN on Cora, where node features with low Dirichlet Energy show promising results.** At the same time, our model breaks down to GCN (with skip connection and shared weights) if $\alpha=1$. We thus expect that, given the correct hyperparameters, FLODE does not perform significantly worse. --- For W2/Q2: Fig. 1 is an **ablation study** on the effect of different update rules on the test accuracy. More specifically, we wanted to show how the choice of learnable exponent and skip connections influence the performance. Therefore, the comparison with SOTA GNNs is not pertinent. Please note that we compare against SOTA GNNs in Tab. 1 and 2 in the main paper, and in the general response. Chameleon, Squirrel, and Actor are widely accepted as standard heterophilic datasets in the GNN field, often used in studies at top-tier conferences like [1] and [2]. Even if there are duplicate nodes, these datasets are still challenging due to their heterophilic nature. It is worth noting that none of the papers the Reviewer suggested for comparison consider the alternative datasets that the Reviewer proposes in their most recent answer. --- [1] Di Giovanni, F., Rowbottom, J., Chamberlain, B. P., Markovich, T., and Bronstein, M. M. (2022). Graph Neural Networks as Gradient Flows: Understanding Graph Convolutions via Energy. arXiv: 2206.10991 [cs, stat]. [2] Choi, Jeongwhan, et al. "GREAD: Graph Neural Reaction-Diffusion Networks." (2023).
Part 1/2
Thank you for the response. Regarding Q4 in your response, it is noted that the accuracy of your model is lower than that of GCN/GAT across all three small datasets in your response table. While you mentioned that "The experiment was not meant to chase SOTA in this new split scenario," it should be clarified that this is not a new split scenario. In fact, it is a common method for evaluating GNN models, as evidenced by its use in models such as GCN, GAT, and SGC. For W2/Q2: The paper [4] I cited was published at top-tier conferences and has been cited by other papers such as [5] from top-tier conferences. My intention was to suggest that adding more datasets to support your claims, rather than relying solely on the two datasets currently included in the study. For "The gap between your theoretical framework and empirical results is evident." : # ``I suspect that this paper is solely playing a definition game about oversmoothness.`` Besides the above strong practical concerns about whether it fits the large datasets, etc., upon careful scrutiny of the manuscript, I am compelled to express significant concerns regarding its core contentions and proposed methodologies. I am deeply skeptical about the veracity of the paper's primary claims and urge the authors to provide a thorough clarification. # Let's first be clear about the definition of oversmooth in GNN: oversmoothing means that after sufficient time or layers, the initial node features states have been forgotten. ## Clarify about oversmoothness in GCN and oversmoothness in other GNNs I acknowledge that exponential decay of Dirichlet Energy towards 0 signifies oversmoothness in **``GCN``** as highlighted in [3]. However, a pertinent question that arises is whether this universally holds true for all GNNs, ``especially across the spectrum of graph ODE models``. ``Is it accurate to assert that the only metric for oversmoothness is the Dirichlet Energy and its``**``exponential decay to 0``** in Definition 5.1?
part 2/2
### I highly suspect that the authors are playing a definition game here: In Definition 5.1., they define the oversmoothness as the Dirichlet Energy decays exponentially fast to $\lambda_{min}$. **This definition itself is ridiculous if we think carefully here. If Dirichlet Energy decays exponentially fast to $\lambda_k$ that is different to $\lambda_{min}$, can we claim there is no oversmoothness or the oversmoothness has been mitigated?** A counter-example to ponder upon: If all node features converge to the eigenspace associated with $\lambda_k$ (the $k$-th eigenvalue of the graph Laplacian), can we claim that this is no oversmoothness or the oversmoothness has been mitigated? **``But please note that the features are still converging to something that only depends on the graph topology!``** Definition 5.1's claim, wherein oversmoothness is quantified as the Dirichlet Energy's exponential decay to $\lambda\_{\text{min}}$, appears problematic. **``If the Dirichlet Energy exhibits an exponential decay to ``** $\lambda_k$,**`` distinct from``** $\lambda\_{min}$, **``it is imprudent to assert that oversmoothness is nullified or mitigated.``** I have serious doubts about the definitions in Section 5.1. How can the term "Frequency-Dominant" be an indicator of oversmooth mitigation? The datasets, either homophilic or heterophilic, should depend more on the features of the graph input states besides the graph topology. But your definition only touches on the graph topology finally. **``This is already a potential indicator of oversmoothness.``** Theorem 5.4 in this paper is another perplexing point. It suggests that given some conditions on the graph structure, the Dirichlet energy will converge to a value linked to certain eigenvalues of the graph topology. This doesn't add up. The node features can still converge to states independent of their original features. **``But if the final states depend only on graph topology, it is still oversmoothing!``** Moreover, the ODE model introduced here doesn't convincingly back up the authors' claims. The skip connections in ODE solvers might indeed help maintain node classification accuracy across many layers [1][2]. But there's no comparison with other oversmoothness ODE models. This glaring omission makes it extremely hard to judge the paper's true contribution. One glaring weakness: after reading the rebuttal and the further explanations by the authors, I'm left thinking the authors might be biting off more than they can chew. They dabble in directed graphs, but this is **only weakly addressed in relation to oversmoothing in Section 5.2.** The entire paper feels like it's based on a **toy model with just small datasets.** The reliance on singular value decomposition restricts the model from tackling large graph datasets. More seriously, I highly suspect that the authors are just playing a math definition game here instead of truly trying to mitigate oversmoothness. More experiments need to be done to demonstrate the over-smoothness mitigation as I suggested early. I do not have any idea about how this paper offers any real value to the GNN community. Between the shaky theoretical discussion on oversmoothness, the limited scope of experiments on just small datasets, and the lackluster dive into directed graphs, the paper is in a very weak form, and it is fundamentally not ready for publication on NeurIPS. [1] Li, G., Xiong, C., Thabet, A. and Ghanem, B., 2020. Deepergcn: All you need to train deeper gcns. [2] Li, G., Muller, M., Thabet, A. and Ghanem, B., 2019. Deepgcns: Can gcns go as deep as cnns?. [3] Cai, Chen, and Yusu Wang. "A note on over-smoothing for graph neural networks." [4]. Platonov O, Kuznedelev D, Diskin M, et al. A critical look at the evaluation of GNNs under heterophily: are we really making progress? [5]. Zhao K, Kang Q, Song Y, et al. Graph neural convection-diffusion with heterophily[J].
Oversmoothing and Missunderstandings of Reviewer Clarified
The phenomenon of oversmoothing, as its name suggests, describes a scenario where node features become overly smooth, too quickly. When this occurs, nodes features of nodes connected by an edge converge to the same feature if we let the depth of the underlying GNN go to infinity. This phenomenon is not unique to GNNs; in other pre-machine learning methods, like Laplacian smoothing [1], the same phenomenon occurs. The concept of oversmoothing was then observed in GNN architectures like GCN, GAT and GRAND. This is a serious limitation, as oversmoothing hinders GNNs to perform well on graphs where long-range dependencies exist, e.g., heterophilic graphs. Oversmoothing's formal definition has evolved over time. One well-accepted definition relates to the convergence of node features towards the null space of the graph's SNL [2]. Other definitions link to the exponential decay of Dirichlet Energy towards zero [3,4] or the convergence of random walks to its stationary distribution [5]. These definitions, while varying in phrasing, capture the same essence: node features converge rapidly to similar values for connected nodes. In our study, we analyze oversmoothing within the mathematical framework of the Dirichlet Energy. In undirected graphs, the smoothest possible node features of a connected graph correspond to zero Dirichlet Energy. A fact supported by spectral graph theory results that confirm the SNL will always have a zero eigenvalue when the graph is connected. Directed graphs do not necessarily follow this pattern, leading us to select the smoothest possible node features: the energy corresponding to the minimum eigenvalue $\lambda_{\mathrm{min}}$. Our claim that oversmoothing is mitigated if the output node features do not converge to $\lambda_{\mathrm{min}}$ is firmly grounded in both theory and intuition: when increasing the depth the underlying GNN will not output overly smooth node features. Our work goes a step further by demonstrating that the limit of our model is not strictly $\lambda_{\mathrm{min}}$ both theoretically and empirically, see, e.g. Sec. 5 and Point 1 in the general response. This fact, by definition, shows mitigation of oversmoothing. It’s also worth highlighting that eigenspaces of other eigenvalues than $\lambda_{\mathrm{min}}$ might convey non-trivial information, both for undirected and directed graphs. Yet, this implies our model has the capacity to retain high Dirichlet Energy, making it apt for heterophilic graphs, be they directed or not. We want to highlight once again, while we chose the mathematical framework of the Dirichlet energy, it is equivalent to the other (less used) definitions in [2] or [5]. For a survey, we refer to [7], which defines oversmoothing in their first sentence: „Node features of graph neural networks (GNNs) tend to become more similar with the increase of the network depth“, and links it to the Dirichlet energy as we do. **To conclude, the standard definition of oversmoothing and its underlying intuition differs from the reviewer's perspective.** We hope this clarification assures that we are not „playing a definition game.“ [1] Zhou, D., & Schölkopf, B. (2005, August). Regularization on discrete spaces. In Joint Pattern Recognition Symposium (pp. 361-368). [2] Oono, K., & Suzuki, T. (2019). Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv:1905.10947. [3] Cai, C., & Wang, Y. (2020). A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13318. [4] Rusch, T. K., Chamberlain, B., Rowbottom, J., Mishra, S., & Bronstein, M. (2022, June). Graph-coupled oscillator networks. In International Conference on Machine Learning [5] Thorpe, M., Nguyen, T. M., Xia, H., Strohmer, T., Bertozzi, A., Osher, S., & Wang, B. (2021, October). GRAND++: Graph neural diffusion with a source term. In International Conference on Learning Representations. [6] Di Giovanni, F., Rowbottom, J., Chamberlain, B. P., Markovich, T., & Bronstein, M. M. (2022). Graph neural networks as gradient flows. arXiv preprint arXiv:2206.10991. [7] Rusch, T. K., Bronstein, M. M., & Mishra, S. (2023). A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993.
Addressing Reviewer PWaE’s Concerns
We address the concerns. > „I highly suspect that the authors are playing a definition game here [...]“ Our clarification on the definition and intuition behind oversmoothing should respond to this concern. **Our definition is grounded in established literature** (refer to the previous comment) and aligns with both theoretical and intuitive understandings of oversmoothing. Notably, convergence to certain graph topologies doesn't inherently signify oversmoothing. Oversmoothing specifically pertains to the exponential decay of the Dirichlet Energy to zero — a state where node features become indistinguishable for connected nodes. The primary idea behind advocating model flexibility in Frequency-Dominance is straightforward and intuitive: homophilic graphs benefit from low energy, heterophilic graphs benefit from high energy, and graphs between homophilic and heterophilic extremes may benefit from mid-energy levels. > „Is it accurate to assert that the only metric for oversmoothness is the Dirichlet Energy and its exponential decay to 0 in Definition 5.1?“ Regarding this query, we again refer to our previous comment, showcasing that oversmoothing is not about a "definition game", but is mathematically defined. **We consequently prove mathematically that we mitigate oversmoothing.** Moreover, we also use accuracy as an indicator to demonstrate that oversmoothing is mitigated. As shown in Fig. 1 of our supplementary pdf, our method's performance remains stable for up to 256 layers. > „But if the final states depend only on graph topology, it is still oversmoothing!“ Please see our previous comments. Let's summarize: **if we effectively mitigate the energy's convergence to zero, we are provably mitigating oversmoothing**. Moreover, results on oversmoothing, including our findings, often focus on limit behaviors. Thus, while the limit may be solely dependent on the graph topology, **the output from a finite GNN relies on both the initial node features and the graph topology**. Plus, the eigenspace corresponding to other eigenvalues than $0$ may carry non-trivial information. For example, the second eigenvector is a relaxation of the Cheeger vector, and the largest eigenvector gives a highly non-smooth vector, suitable for classification in heterophilic graphs (see Sec. 5.1). > „ But there's no comparison with other oversmoothness ODE models.“ We have compared our method with various models in our experiments, as evident in Tab. 1 and the supplementary pdf. Our method stands out in terms of flexibility, especially concerning directed graphs. For instance, our work is the only work that shows a) that oversmoothing is mitigated for fractional Laplacian-based ODEs in undirected graphs, b) possible mid-frequencies dominance, c) that our method mitigates oversmoothing on directed graphs with normal SNA, and d) if $\alpha=1$ for all directed graphs. We're open to adding short survey about other ODE-based models that *provably* mitigate oversmoothing in a revised version of the paper, including GRAFF, GraphCON, and GRAND++. > „How can the term "Frequency-Dominant" be an indicator of oversmooth mitigation?“ We hope that our previous responses answer this query. The notion of "Frequency-Dominant" as oversmoothing mitigation indicator stems from [6], and our incorporation of it is consistent with its original intent. We would like to gently remind the Reviewer to consider the broader context rather than getting overly fixated on specific terminology. **The essence lies not in the label "Frequency-Dominant" per se, but in the associated literature, the theoretical insights, and the practical implications we bring forth.** > „I'm left thinking the authors might be biting off more than they can chew.“ Please refer to Sec 4, 5, and 6 and our general response, which discusses directed graphs. > „The entire paper feels like it's based on a toy model with just small datasets.“ We have tested our model on both real-world and synthetic directed graphs, encompassing up to 20K nodes. These datasets are not small or toy datasets; they are standard in the GNN literature. > "More experiments need to be done to demonstrate the over-smoothness mitigation as I suggested early.“ **See the general response or Fig. 7 in the appendix for many such experiments. More importantly, we *provably* mitigate oversmoothing**. >Regarding the inclusion of other splits. We acknowledge that the suggested split is common. Still, we employed standard splits for the considered graphs. Hyperparameter tuning for different splits is beyond our work's scope. Note that we already consider 10 different splits per dataset, and it's uncommon to analyze various split methods, see .e.g, [5-7]. >Regarding the inclusion of new datasets. Although we have evaluated over 20 datasets, we value this feedback. Given the time constraints for the rebuttal, we're prepared to include more datasets in a potential final version of the paper.
Summary
We thank the reviewer for their comments. We hope that our answers clarify the definition of oversmoothing and our contributions to mitigating it. Furthermore, we will include a short survey (see first reply "Oversmoothing Clarified") on oversmoothing and related works in a revised paper to make our work more accessible. We are also happy to include more datasets for a revised paper as only one working day is left for the discussion phase, and are open to further questions.
Thank you for the additional experiments and details addressing my and other reviewers' comments. I don't have any further questions.
Thanks for taking the time to answer my questions. I have no further questions/comments. I have read the other reviews and authors' responses and would like to keep my initial score.
I thank the authors for their detailed answers and additional experiments. > Regarding the Figs. you've mentioned, we would greatly appreciate if you could specify which ones you are referring to... I had in mind fig. 4 which is mentionned twice in the main text.
Decision
Accept (poster)