Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The paper suggests a new graph neural network architecture that can be seen as a gradient descent minimization of a learnable energy function. The authors use channel-mixing matrices with mixed eigenvalues to infuse high frequencies into the architecture dynamics. Many existing architectures fall into this framework. Three variants of the new architecture are presented. 
strengths_and_weaknesses: Strengths
1) The paper is rich in theoretical insights. 
2) Unlike previous works, this is the first work that analyzes the channel mixing matrix. 

Weaknesses: 
1) The experiments are rather limited. The authors show only node classification, where it is customary to show more experiments. The work of GCNII, for example, shows PPI, and two cases of node classification (semi and fully supervised).  Also, an example on a large dataset (e.g., OGBN-Arxiv) is also important. Most importantly, it is not clear how well the method works on graph classification tasks (e.g., the TUD data sets), without the non-linearities in the layers. Given the strong claims made by the authors regarding those non-linearities (see below), showing these experiments is essential in my opinion.

2) I find only a single data set where GRAFF yields the best performance. Overall, this method does not improve the SOTA. 

3) There is very little discussion about over-smoothing in this work (only in the paragraph in line 249). At the end, the authors do not show if their method is over-smoothing or not. Ideally, the authors would provide accuracies for a variety of number of layers and show that the accuracy does not degrade (e.g., see GCNII). 

4) There are questionable choices for the architecture (e.g., no non-linearities) that are accompanied by too strong statements without backing them up. See details in the questions section. In particular, the authors do not show that indeed adding and removing the non-linearity has no influence on the accuracy. 

5) The writing of the paper is hard to follow. I would say that the presentation (i.e., notation and language) can be simplified to make this paper more reader-friendly. 

6) I could not find how many layers were used in Table 1.

7) Missing citation from the previous Neurips: 
Zhou, K., Huang, X., Zha, D., Chen, R., Li, L., Choi, S.-H., and Hu, X. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
This paper also discusses the Dirichlet energy throughout the layers.

8) Missing citation from ICLR 2022:
How attentive are graph attention networks? (GATv2)
The conclusion of this paper is that having a more non-linear (in some sense) attention matrix improves the accuracy and training stability over GAT. How does the conclusion in this work align with the findings in GATv2? Note that there are additional data sets in GATv2, which may be more challenging and require non-linearities in the layers.


questions: - The gradient of Eq (4) looks like Grad^TW^TWGrad(F). Why is Eq (5) the way it is? Please clarify in the text. 

- I am confused by the derivation from (6) to (7). First, if the rest of the paper uses the energies in (7), why introduce the energies in (4)-(6)? How do (6) and (7) relate? This is not clear. More importantly, is it the same W in both equations? It does not seem so. This is very confusing. Please consider revising. 

- Line 202-203: Are the authors saying that there is no role for the non-linearities in graph neural networks? But that is the most important aspect of a neural network’s definition (otherwise, the whole network collapses to a single linear operator). It does not make sense. Maybe try other experiments? CNNs, for example, sure require non-linearities for image classification. Maybe test this hypothesis on graph classification? Maybe shape classification (ModelNet40)?  

- Line 209: by linearized GNNs, do the authors mean with identity activation? Because there are no activations in the following equations. But - this is not the traditional use of the word "linearized", which is traditionally used for a Taylor approximation. Please revise. 

- Line 228 – why do the authors introduce tilde{W}, and then set it as identity? Can’t tilde{W} be chosen better? And if so - why introduce this matrix? 

- Line 230 – Why are Omega and W shared across the layers? Traditionally, at least in CNNs, one learns a variety of channel-mixing convolution operators. What is different here? This negates the common practice of neural networks and requires explanation and evaluation.

Line 235 – the authors have T, tau, and the number of layers. How do we choose T or tau? Is it a hyperparameter? Do the authors choose tau to be small enough to ensure the stability of the Euler scheme? 

Line 236 – The authors state that they can include the non-linearities in the encoder and decoder layers only. Will that be the equivalent to having a non-linearity in Eq. (12)? I do not understand why. Again, that is against the fundamental aspect of neural networks – the use of non-linear activations to express complex functions.

Lines 244-245: Symmetry being a key requirement. When other works learn the channel-mixing operators, they do not enforce symmetry. So – this is important only for looking at architectures as a gradient flow. Further, in lines 247-248: indeed (13) can be seen as a generalization of the mentioned methods (with identity activation), but none of these learn symmetric matrices. Also, as the authors note, GAT does not have a symmetric attention matrix. So, is symmetry really important? Will we get better networks if we enforce symmetry in the learning?  

In continuation to the previous point: the symmetrization in lines 304. In my opinion, this whole concept of symmetry or not should be evaluated in extensive experiments, but I do not see such experiments in the paper.  

Lines 282-284: Essentially, when choosing negative eigenvalues for W, you indeed reverse the time integration. But then, the Euler method that is used is known to become unstable. Isn’t that a problem with the whole approach?

Lines 290: The authors state that linear GNNs achieve competitive performance on real-world data sets. Again, having linear layers negates the whole concept of NNs. This cannot be a conclusion that holds for all data sets and tasks. Given the rather limited scope of experiments, I would say that this is a too strong statement here. 

Lines 301-302: The authors choose W to be diagonal and random and do not train over it. Why is that? Won’t we get better results if we train over W? This means that there are no non-linearities in the network, and there are no learnable channel-mixing parameters. So, except the encoding and decoding layers, it’s essentially a classical algorithm. How do the authors explain that?

Lines 301: the random W. How does the choice of a random W influence the results? Are the achieved accuracies stable? Or do the authors see large deviations between different runs?

Line 375: This is yet another strong sentence, given the rather limited experimental study in the paper. 

limitations: yes.
review_title: null

final_score: 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.
review_content: summary: In this work, authors present GRAFF, a gradient flow based graph neural network in which the evolution of GNN is represented as minimizing the combination of attractive and repulsive interactions of a multi-particle system. Detailed theoretical characterization in terms of a parametric Dirichlet energy, a general parametric energy and spectral analysis is performed. 
strengths_and_weaknesses: The work is well-written and clearly presented. It builds on similar ideas as outlined in several previous works such as, for instance, [27]. While the presentation in the work is good, the idea in itself is fairly intuitive and simple and has been discussed in contexts of neural networks and physics (related works, see: Landscape and training regimes in deep learning, M. Geiger; L. Petrini; M. Wyart, Physics Reports. 2021-04-16. Vol. 924, p. 1-18. DOI : 10.1016/j.physrep.2021.04.001.). Further, the empirical experiments reveal that the results are comparable with the existing approaches, but not necessarily better. 
questions: It has been shown by earlier works that energy formulation results in a loss landscape that has a large number of local minima and hence gradient based minimization results in a poor solution. In contrast, deep neural networks with large number of parameters have flat minima and the loss landscape is connected by level set. Reading these together, it is unclear whether the energy-based formulation with simpler formulation loses the advantages of the landscape that a deep-learning architecture has. Could this also be the reason why the performance of the GRAFF is not superior in comparison to other SOTA models? Authors should investigate this.
limitations: The experiments has primarily focussed on one aspect while studying on several datasets with varying hetero/homophily. To evaluate the true performance of the approach, several other experiments on varying downstream tasks are required. in addition, a closer analysis on the loss landscape is required to understand the nature of the minima and saddle points.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the evolution of the GNN is explained as learning attractive and repulsive forces in feature space by the positive and negative eigenvalues of a symmetric 'channel-mixing' matrix. According to the spectral analysis of the solutions, gradient flow graph convolutional models result in a dynamic dominated by graph high frequencies, which is desirable for heterophilic datasets. Moreover, the authors present structural constraints on common GNN architectures, allowing them to be interpreted as gradient flows. We perform extensive ablation studies to verify our theoretical analysis and demonstrate the comparative performance of simple and lightweight models on real-world homophilic and heterophilic datasets. 
strengths_and_weaknesses: Strengths:

In this paper, the author gives a new perspective on GNN in terms of the particle system, which explain why the original GNN does not work well on heterophilic datasets and also analysis Dirichlet energy change in the dynamic system.

The whole paper's structure is clear and easy to follow. Several adequate experiments are used to verify the author's statement.

Weaknesses:

When the graph size is increasing, is this GNN also computation feasibly? As this model needs to compute the eigendecomposition of the graph Laplacian, when the graph size is increasing, it should be hard to compute.
questions: If two particle (two nodes) is repulsive to each other, will both feature blow up (going to infinity) as the time of the dynamic system increases? How can you ensure all the feature on every node is bounded with the system is evolving?



limitations: The authors discussed the limitation of their works and their social impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a new family of models, GRAFF, on graphs wherein graph features are transformed according to a dynamical system given by the negative gradient of an *energy functional*, which is parameterized and learned.  This amounts to a re-parameterization to focus on an energy function describing a discretized iterative update, instead of parameterizing the iterative update itself, as the most widely used GNN architectures do. This relation is properly studied in Section 4, where they show that GRAFF still includes many prior GNN model (up to the perhaps critically important matter of the non-linearity). However, this re-parameterization appears to offer more than just a reinterpretation of existing models. The primary value added explored in this work is to the analysis (and empirics) of the ability to handle heterophilious graphs. 
strengths_and_weaknesses: First, a congratulations to the authors on a nice piece of work that offers some new perspectives, and promising new directions. I enjoyed reading your work and certainly felt that I learned something in the process. 

Below I discuss some of the things I especially liked in this work, as well as some of the concerns I have about certain aspects. Overall, I think this work contains some great conceptual components, but leaves open so quite important questions, particularly revolving around expressive power. The empirical evaluation is also relatively weak, and leaves me uncertain whether gradient flow models would enjoy widespread adoption. I will explain why I came to each of these beliefs in more detail below.

---

**Strong aspects:**

The community is moving towards a number of candidate approaches for circumnavigating the weaknesses of message passing networks. Although many ideas have already been given, the debate remains open. The idea of models following gradient flows is creative, and immediately prompted an “aha!” feeling. The community is in need of creative ideas like this, as you never know which will end up having a decisive impact.

On a technical level, it was pleasing to see the amenability of gradient flows to analysis of smoothing properties. The result in Section 3 on the Dirichlet energy functional were particularly interesting. It is quite unfortunate, however unfortunately typical, that the analysis doesn’t extent to non-linear activations (line 201). 

--- 

**Weak aspects:**

A major missing piece of the picture is an understanding of the expressive power of the proposed gradient flow models. I found it particularly perplexing that line 202 mentions that no non-linearity is used in experiments. This raises a number of questions: are these models then of comparable expressive power to linear GNNs? Given that having no non-linearity doesn’t hurt performance does this just suggest that the empirical benchmarks considered just aren’t that challenging? 

The paper claims several times that GRAFF models are “explainable”. The basis for this is that the model predictions can be understood by probing property of the energy functional. While this may turn out to be a useful point, the paper does not properly substantiate the claim. Indeed, there are no examples of any such “explanation” in practice. I would ask the author to either drop the “explainable” claim entirely (which isn’t critical in any-case, despite it’s prominent position in the explanation of ”why a gradient flow?”) or to clearly substantiate it, probably via an example. 

Experimental evaluation is fairly limited. Table 1 is the main seat of comparisons to other models on node level classification tasks for varying levels of homophily. As billed, the strengths of GRAFF seem to emerge primarily in low homophily (high heterphily) graphs. However, the heterophilic graphs are very small: half only have a few hundred nodes, and the biggest graph considered—“Films”- has 7,600 nodes, and an MLP is a fairly competitive baseline on Films. All this means that the possible benefits to empirical methodology in the immediate future from seem unclear. 

---

To conclude, although the empirics leave a number of question marks over the immediate empirical viability, the idea of graph models via gradient flows along an energy functional is elegant and thought provoking for me. The idea itself, plus the good exploration of the connection to smoothing, is enough to put me on the side of acceptance, but the limitations mentioned keep it only marginally so.


---

**Miscellaneous:**

- Clarity in certain places could be improved. For instance, Propositions 2.4 and 3.1 give explicit rates for the energy functional. Since (unless I am missing something!) the key point in both cases is that the models are high-frequency dominant, the rate itself seems to be more of an intermediate step towards this final HFD conclusion. Maybe it is a matter of personal taste but I would have hidden the gory details I the appendix. 
- More generally, the paper is pretty notation heavy

questions: - What component(s) of GRAFF explain the inference speedup vis-à-vis GCN? Is it due to parameter sharing? Also, no details are given as to how this comparison was decided. Right now I cannot be sure that the comparison is apples to apples; maybe the GCN is a really massive model and the GRAFF is much smaller. More details on this would be great.
- Why just compare inference time? What about comparison of training time? It seems remiss not to include this, especially since the main paper simply mentions “run-time smaller than GCN” (line 359).
- The connection to spectral GNNs is interesting. Perhaps this suggests a path to developing expressive power results. 
limitations: Yes.
review_title: null

Meta-review: metareview: The authors present a graph neural network for heterophilic data using gradient flows. The proposed architecture is quite simple...large sections of the architecture are fully linear dynamical systems rather than neural networks, and still achieve roughly SotA results on standard graph learning benchmarks. There was a significant amount of disagreement between the reviewers. Some seemed to think the strength of mostly linear methods meant that the benchmarks were too easy, but these are standard graph neural network benchmarks. A simple model performing well is not a negative, and can often be useful for puncturing hype (e.g. https://arxiv.org/abs/2206.13211). Simple architectures can also be useful for providing analytic insights which might get obscured in more complex models. Some reviewers seemed concerned about the scaling of certain tools (e.g. graph Laplacian eigenvectors), but these tools are only used for analysis, not for training. Nevertheless, I feel that there were enough general concerns around the paper that I have a difficult time recommending acceptance. Even if the purpose of the paper is primarily to drive analytic insights rather than achieve SotA results on big benchmarks, I would recommend the authors to show how these analytic insights can be used to improve models on big datasets to strengthen the paper.
confidence: Less certain
Decision: Reject