Re-Think and Re-Design Graph Neural Networks in Spaces of Continuous Graph Diffusion Functionals

Summary

This paper focuses on devising a new inductive bias for cutting-edge graph application and present a general framework through the lens of variational analysis. To this end, the authors first introduce a new selective mechanism that can be easily integrated into existing GNNs and effectively address the trade-off between model depth and over-smoothing, and then devise a novel generative adversarial network to predict the spreading flows in the graph through a neural transport equation. Extensive experiments show that the proposed GNN models can achieve state-of-the-art performance on graph learning benchmarks such as Cora, Citeseer, and Pubmed.

Strengths

1. The perspective of the article is innovative, as it creatively utilizes heuristic problems from traditional physics to inspire the design of GNN structures. 2. The description of the proposed GNN architecture is clear, and the experimental setup is well-defined. 3. The experimental results validate the superiority of the method proposed by the author and demonstrate the rationality of the proposed theory.

Weaknesses

1. The majority of the content in the article is based on the Euler-Lagrange (E-L) equation of the heat kernel. However, I don't believe that the detailed knowledge of the EL equation is familiar to every graph neural network researcher. Therefore, I think it is important to briefly introduce it when it first appears (Line 74) or mention it in the appendix. This is crucial for maintaining the readability and coherence of the article. In fact, it took me a lot of time to consult relevant materials for the subsequent introduction of the Euler-Lagrange (E-L) equation to LaGrangian Mechanics. 2. The issue of over-smoothing in GNNs has been extensively studied since 2020, but the theoretical reasons behind this problem have not been conclusively determined [1, 2, 3]. In line 135-136, the authors claim that after connecting the GNN inductive bias to the function of the graph diffusion process, we can postulate that the root cause of over-smoothing is the isotropic regularization mechanism encoded by the ℓ2-norm. Treating this theory as a conclusion is certainly not a problem. However, due to the fact that many subsequent formula derivations are based on this theory, I have to consider whether this theory has been somewhat hasty and overclaimed. I think the authors should provide some deductions before presenting this theory to maintain logical rigor. 3. In line 166, the authors claim that Eq. 1 is the dual formulation with min-max property for the TV distillation problem. It is well known that the dual problem is strictly mathematically defined. I do not fully understand how the duality problem here is derived. Please provide further explanation. 4. In line 185-186, I am confused about how the recursive min-max solution for Eq. 1 is obtained by disentangling the building block in vanilla GNN into the feature representation learning and graph diffusion underling TV. I do not intuitively perceive the connection between the two. Please explain. reference: 1. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. ICLR 2020 2. Towards Deeper Graph Neural Networks. KDD 2020 3. Beyond Low-frequency Information in Graph Convolutional Networks. AAAI 2021

Questions

Please see the weak points.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

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

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Please see the weak points.

Summary

This work studies a novel design of GNN leveraging the connection with graph diffusion. Specifically, this work considers the discrete GNN model in view of continuous graph diffusion functional formulated as the Euler-Lagrange equation. This work proposes a new design of GNN with selective inductive bias which alleviates the over-smoothing in GNNs. Further, this work proposes a new approach for predicting the flow dynamics in the graph via a neural transport equation using the GAN model to predict the spreading flow.

Strengths

- The paper is well-written with clear motivation and justification. The writing is easy to follow with summarized questions and the paper's approach (re-think and re-design) helps to understand this work. - The proposed architecture is novel yet simple based on theoretical justifications leveraging the connection with the graph diffusion (although this was studied widely in other papers). Further, the GAN model for flow prediction is also new, using neural transport equations. - The experimental results show superior performance compared to the baselines in node classification, and the results in node classification demonstrate that the proposed architecture mitigates the over-smoothing issue.

Weaknesses

- Related work section could greatly help the readers for understanding this work as it deals with new GNN as well as flow prediction in graphs. I assume that the related work section was omitted due to the page limit, and recommend adding it if possible. - The reason for the superior performance of the GAN model is not clear.

Questions

- What is the purpose of using total variation? Is it simply from the inspiration explained in line 151? - Although the extra training time is described in section S2.4, comparing it with the training time without DC layer would show that the computational burden is not significant.

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

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The limitations are discussed in the supplementary file section S2.4.

Summary

The authors connects graph neural networks with discretizations of PDEs and connects their limiting behavior with E-L equations. By changing regularization / smoothing term from second order to first order, the authors designed a new E-L equation and its corresponding GNN. The author then present numerical experiments to show their improvement in performance.

Strengths

- The authors tackles the problem of oversmoothing in GNN, which is an essential problem GNN cannot get as deep as other neural networks. - The authors provided solid mathematical support on their method and great experimental performance. - It is an original work connecting TV-minimization from the old school machine learning, with the SOTA design of GNNs.

Weaknesses

- The authors should do an table outlining the steps of their algorithm. It will make it easier for audience who prefer testing model before going through the math. - The infomation in figure 5 is too dense. It would be better if the authors could split it into two figures.

Questions

- Equation 3 sounds similar to the MBO scheme, which is basically diffusion + clip. Are there any connections in between? - Does your model transfer to other types of neural networks like convolutional neural networks? - Does your model requires more computation time? How much more compared to the origional run time of GCN, GAT, and GRAND?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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

3 good

Contribution

4 excellent

Limitations

N/A

Summary

The authors propose a framework based on the Euler-Lagrange equation to derive specialized GNNs by discretizing continuous diffusion functionals. By deriving a new GNN layer from the Total Variation functional, they manage to control the oversmoothing problem in existing GNN architectures and improve node classification performance of six existing architectures with up to 128 layers. Additionally, the authors introduce a new GAN to learn flow problems on graphs and evaluate it on longitudinal data from Alzheimer's disease.

Strengths

The prominent strengths of this paper are the thorough evaluation and the great results on node classification showing that the proposed DC layer can improve different architectures and enable deeper graph neural networks. The proposed GAN also performs very well on flow prediction in an Alzheimer's disease dataset though I cannot judge the subject-specific interpretation of those results. In the derivation of their method, the authors combine many techniques though it is in parts difficult to follow (see Weaknesses).

Weaknesses

The one major weakness of this paper is its (lack of) clarity in writing. Many ideas are insufficiently explained and notation is often inconsistent and confusing. In particular, I refer to the following: 1. Line 90: The numbers for Cora and Citeseer are not in Table 1. 1. Line 110: Graph divergence operator is never defined and no reference is given. 1. Line 111-121: Unclear writing that mixes two different ideas. The first two sentences talk about an often-used (citations missing) regularization term and its effect, but the remainder of the paragraph is about interpreting GNN structures as neural ODEs on graphs. 1. Line 127-130: Drawing the conclusion that you have established this mapping requires either further explanation or at least a citation. 1. Line 136: Which L2 norm does this refer to? The one in the functional in line 127? 1. Line 158-159: The definition of $J_{\mathrm{TV}}$ is completely unclear. $x$ is triple bound (parameter of $J_{\mathrm{TV}}$, parameter of $\min$ operator and integrated over) and $z$ is double bound. 1. Line 160-161: What exactly does this "trick" consist of and in which sense is "degree" used in this sentence? 1. Equation (1): Same issue as line 158-159. 1. Equation (3): Is the clipping elementwise? 1. Line 190: Why are the $x_i$ being clipped when Equation (3) referes to the $z_i$? 1. Line 191: How does large degree increase $z_i$? An arbitrary number of edges of identical nodes would leave $z_i$ still unchanged, wouldn't it? 1. Line 192-193: What does it mean to "shift the diffusion pattern"? Which cases of the case distinction in Equation (3) correspond to "heat-diffusion within community" and "penalizing inter-community exchange"? 1. Line 211: How is future predictability related to the Brachistochrone problem that asks about the shortest path? 1. Section 2.2.2: The whole section is difficult to follow because it introduces yet another problem and solution in little space. While I understand the importance of this section as an example for an alternative GNN architecture derived from the proposed method, for the overall clarity of the paper the space might be better used to clarify the main method. 1. Overall, the importance of the Brachistochrone problem is overemphasized and diverts attention from the main contribution of the paper. It is a nice example application of the E-L equation but even in Figure 1 the analogy between the mechanics and ML case is weak. This paper leaves the impression of solid work, though the opaque presentation prevents me from saying so with any certainty. A thorough rewrite of Section 2 with a focus on the reader could make this a great paper.

Questions

1. In how far does GNN-PDE-COV rely on the homophily assumption? Part of the problem illustrated in Figure 1 is that the strong connection between nodes of separate classes breaks the homophily assumption of many GNN models. 1. How does the runtime of your model scale in the number of nodes $N$ and number of edges $E$?

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

1 poor

Contribution

3 good

Limitations

The appendix mentions briefly limitations of the mode of evaluation. I would be interested in a point on how feasible it is to derive specialized architectures based on the GNN-PDE-COV framework given that the optimization problem in the proposed GAN is completely different from the optimization problem in Section 2.2.1.

Summary

The authors develop a framework for linking discrete (message passing) GNNs to continuous graph diffusion functional networks using Euler-Lagrange equations of heat kernels. Via this framework, they analyze the causes of oversmoothing in current GNNs. By noting that the main cause of oversmoothing is the minimization of the quadratic graph smoothness term in the diffusion equation, their main contribution is to replace this by a Total Variation (TV) term (as used in image reconstruction, restoration etc.), yielding a new objective function. Further since the $l_1$ norm term of TV is non-differentiable at 0, they develop a dual min-max approach for solving this objective function iteratively by first minimizing for X and then maximizing for Z. This solution technique then results in a new GNN architecture with a separate feature learning layer (Fully Connected layer) for $l^{th}$ layer embeddings $X^l$ followed by a diffusion clip layer for generating the Z terms. They then apply their method for a specific application of predicting spreading flow dynamics. Experimental results are presented on 3 benchmark citation datasets and 6 GNN models including Vanilla GCN and one other diffusion GCN (GRAND). TL;DR takeaway of the problem setup/motivation is how to preserve community/contextual embeddings of adjacent (dissimilar) boundary nodes in different labeled communities by preventing oversmoothing through localized message passing. The proposed solution is via the Total Variation parameter Z that should penalize inter community information diffusion.

Strengths

1. Avoiding local oversmoothing by replacing the quadratic graph smoothness term in the diffusion equation by an $l_1$ norm regularize which is the TV term. This seems to be a novel application of TV to diffusion GNNs. 2. Formal derivation of an iterative dual min-max method for solving the non-differentiable objective function with the TV term. While this type of iterative technique has gained increasing popularity starting with ADMM, the detailed derivation is a good contribution. 3. For small layers (2 layers), their method shows performance improvement over the other baselines. This might be due to ameliorating the oversmoothing process due to the TV Z parameter.

Weaknesses

1. I am surprised the authors do not have references to classic papers that analyze the root causes of oversmoothing in GNNs, for example, the DropEdge paper [1] “Tackling Over-Smoothing for General Graph Convolutional Networks”, W Huang∗ , Yu Rong∗ et al.. IEEE TPAMI Aug. 2015. This paper analyzes oversmoothing by looking at a spectral analysis of the underlying adjacency matrix. It would be interesting to see if there is a connection between the $beta$ parameter and degree connectivity of equation (3) and results from [1]. 2. The baseline model comparisons are too limited - vanilla GCN, GAT, one diffusion GNN (GRAND). a. There have been several papers that either explicitly focus on deep sampling while mitigating oversmoothing e.g., [2] “Decoupling the Depth and Scope of Graph Neural Networks”, H. Zeng, M. Zhang et al. Neurips 21. b. They test their model on citation networks which are considered highly homophilic. However, dissimilar nodes (as they illustrate in fig. 1) that would ideally prove their oversmoothing claims are adjacent to each other primarily in heterophilic networks. It would be useful if they can show their results on heterophilic graphs. There needs to be an extended comparison with GNN models such as [2] as well as others that look at heterophilic graphs e.g., $H_2GCN$ [3] “Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs,” J. Zhu, Y. Yan et al, Arxiv. As they claim their method prevents over-smoothing, it would be very valuable to see comparative results on heterophilic graphs and if they can show improvements over other models. 3. Experimental Results: [3] $H_2GCN$, [4] GeomGCN [5] GPRGNN seem to show better results. For instance, accuracy of this paper on Pubmed is 80% while H2GCN, GeomGCN, GPRGNN show 90% accuracy. Similar results for Cora and Citeseer . [4] Geom-GCN: “Geometric Graph Convolutional Networks. In International Conference on Learning Representations”, Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. ICLR 2020. [5] GPRGNN: “Adaptive Universal Generalized PageRank Graph Neural Network”, ICLR2021. 4. There may be some typos in experimental results - published results are not consistent with published tabular data in the previous works. E.g. GCNII results for Pubmed are 90% in Table 1 in the following nips 22 paper: https://papers.nips.cc/paper_files/paper/2022/file/75c45fca2aa416ada062b26cc4fb7641-Paper-Conference.pdf but Table 1 in this paper only shows around 79% for GCNII on Pubmed. Similarly please check Table 5 in the following nips 20 paper: https://arxiv.org/pdf/2006.11468.pdf for other discrepancies. I suggest rerunning experiments and checking for typos or otherwise undertanding why numbers are different. In general, the margin of improvement is around 2-4 points over vanilla GCNs for $H_2GCN$ and GPRGNN while the margin is also in that range for this paper, even though they show lower scores for vanilla GNN and GAT. It would definitely improve this paper if you added these papers as baselines for direct comparison. 5. The diffusion flow application that is used in the paper to validate the diffusion model seems to a very niche application. It would greatly add value to the paper if you validated the model over a realistic flow model such as a traffic flow problem. 6. The authors note that their iterative solution technique is not computationally intensive (appendix). However, the method was tried only on 4 limited datasets that are all citation networks. In general, for any iterative solution process the tradeoff between convergence time and accuracy requires more sophisticated and detailed evaluation. Can you improve accuracy on Pubmed (see above) at the cost of increased computation time?

Questions

Please consider different graph setups to validate your oversmoothing diffusion models such as heterophilic graphs in which dissimilar nodes are close by and similar nodes can be far away. More extensive evaluation of tradeoffs between convergence time and accuracy would be helpful, especially to improve accuracy on the 4 datasets as compared to the newer baselines suggested above. Consider a more realistic diffusion flow application to validate your diffusion model such as a traffic flow problem.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

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

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors have addressed the limitations of this work in the appendix, primarily the lack of diversity in evaluation datasets. In general, as pointed earlier, paper could be improved with more extensive comparisons on diverse datasets and models. The authors have stated that the proposed topic doesn't have any negative societal impacts. To the contrary they state that "From the application perspective, the new deep model for uncovering the in-vivo propagation flows has great potential to establish new underpinning of disease progression and disentangle the heterogeneity of diverse neurodegeneration trajectories." While technical correct, this comment in general applies to any work on sensitive datasets in the medical field.

Comment by the AC

Dear Authors, Thank you for your detailed answers and the effort that you put in your rebuttal. Could the reviewers who haven't responded to the authors please do this as soon as possible.

Comments

Thank the author for the detailed rebuttals about Q1, Q2 and Q4. The authors have added more details and relevant work in the Supplementary and provided a brief summary of the pioneering contributions. I notice that Eq1 is important for the coherence of the article. However, for Q3, what I am curious about is the derivation process of the duality problem in Eq. 1 (line 166), since the authors claim that Eq. 1 is the dual formulation with min-max property for the TV distillation problem. I would like to emphasize that the dual problem is strictly mathematically defined clearly. Hence the derivation process is necessary. The author’s response is just the motivation. So I would keep my score.

Requires deeper analysis than in the 1-page addendum

I sincerely appreciate the additional information provided by the authors in their rebuttal. They have definitely put in major efforts in response to my and other reviewer comments. However the nature of the results provide in the 1-page addendum raise several deeper question as outlined below. Papers along the lines of [1][2] DropEdge, ShadowGNN etc. attempt to provide some theoretical basis for their oversmoothing claims in terms analyzing variance in embeddings. Eq. (3) in this paper is quite crucial in terms of intuition for preventing oversmoothing, however unlike [1][2] and similar others, results based on Eq. (3) are primarily heuristic and intuitive. Since reduction of oversmoothing is the major claim in this paper, an important question to readers will be whether the TV method adopted in this paper leading to (3) can be analyzed in a similar manner to provide some theoretical basis for the reduction in oversmoothing. The new results presented in the 1-page addendum show a rather remarkable outperformance of node classification of this work on heterophilic datasets compared to ${\bf every}$ other baseline which makes some theoretical basis for oversmoothing even more needed. The new table of results in the 1-page addendum are appreciated but too succinct in terms of experimental details and raise several deep question on how this overperformance is achieved (while not the authors fault since the rebuttal is page limited, but too important since they consider a complete independent area of heterophilic graphs – it would have been great if the authors had given this full treatment with the proper analysis in the expanded version, not just an additional table). An important exceptional result like this should be analyzed comprehensively with explanations, ablation studies, and comparative analysis, the current submission does not provide the means to do so. I have a similar comment for the new graph on traffic flow prediction. What was the input setup, any simplifying assumptions, any specific engineering of meta-parameters etc., what are the limitations of using the proposed method of flow diffusion for such an important problem space. How does the TV method work so well for traffic flow? I think the community will be better served if the paper is resubmitted with the proper treatment of these important applications.