Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: I have read the authors' responses, comments from the other reviewers, and the discussion here. The authors have answered my questions satisfactorily. Hence, I am increasing my score to 7.


This paper derives a new class of GNN using ideas from differential geometry. It proposes discretization of the PDE associated with the Beltrami flow for the design of the GNN. Although the explicit discrete approximation of the Beltrami flow on a graph has many interesting similarities to existing attention mechanisms, this framework can be more general with the use of sophisticated differential equation solvers, as presented by the authors. The paper also brings out interesting connections between their model and existing GNN architectures, which in itself, is a nice contribution of this work.


main_review: The paper is generally well written except for some typos (possibly), for example,

1) In eq. 4, should there be a $(4\pi t)^{-d/2}$ in the RHS? Without it, if $\alpha \rightarrow 0$, eq.4 does not become the convolution in line 74.

2) In the same equation, should $x(\mathbf{x}, 0) \rightarrow x(v, 0)$, and $x(u), x(v) \rightarrow x(u, 0), x(v, 0)$?

3) In eq. 6, should $U(0)= \alpha U$ be $U(0)= U$ based on the description in section 2? 

4) In section 4, should $Y = \psi(Z(T))$ be $Y = \zeta(Z(T))$ based on the subsequent discussion?

5) In eq. 8, $Q^{(k)} \neq A^{(k)} - I$, it's actually $Q^{(k)} = \tau A^{(k)} - (\tau -1) I$. However, the definition of $q_{ij}^{(k)}$ is correct.

6) In line 153, \ref to a section is not working.

Other questions/ comments:

1) Is $\alpha$ learned or treated as a hyperparameter? If it is learned, how is the criterion $\alpha \geq 0$ satisfied? If it is a hyperparameter, what is its effect on the classification accuracy?

2) Can the authors compare the explicit scheme in sec. 3.2 with their implementation using numerical solver? This will allow the readers to understand the actual source of the performance improvements.

3) Can the authors discuss the novelty in this work in comparison to existing ODE-based GNN models (reference 69, 96, 100). I appreciate that they conduct experimental comparisons with these related works, but some comments about the methodology as well would be welcome.

4) In the supplementary material, the authors discuss several choices for the diffusivity function modeling but do not report any experimental comparisons. 

Overall, my impression is that this work has some novelty in terms of methodology and strong numerical results. But the writing could be significantly improved and the current version is not entirely satisfactory to be published.
limitations_and_societal_impact: The authors discuss the limitations and societal impacts adequately.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new graph neural network based on a continuous time flow. Each node is given a pre-processed position from an off-line node embedding method, then both the position and a vector of node features (together called Z) are changed during the flow. The flow changes Z by the average difference of Z of adjacent nodes, weighted by a scaled dot product attention. Additionally, a node-wise initial encoder and final decoder is used. The flow is computed via explicit adaptive or fixed integration and the backward pass via the adjoint method. The authors propose various extensions, including having dynamic adjacency via kNN and using hyperbolic positional space. The authors claim their method is motivated as a discrete analogue of a Beltrami flow.
main_review: ### Strengths:
- The method performs well on smaller data sets with a small number of parameters.
- The method explores some interesting new ideas for graph neural networks.

### Weaknesses:
- I am not quite convinced by the motivation of the proposed method as a discrete analogue of the continuous Beltrami flow. The “structural assumptions on the diffusivity” $a$ seem to not be satisfied scaled dot product attention in BLEND. What is the point of all the theoretical motivation if the actual construction violates the assumptions of the theory?
- Currently, I find it unclear which aspect of the proposed method makes it perform well. Is it the position that is added as a pre-processing step, the continuousness of the flow, the particular integrator, or the particular flow equation (6)? The ablation analysis in the appendix only partially answers this question. Further experiments could include: augmenting GAT with positional encodings; using BLEND with Euler steps; using GAT with continuous integration.
- The method does not seem to get state-of-the-art results on larger sized data sets. The GAT baseline uses more parameters, but would BLEND improve if it used as many? I expect that BLEND has much higher training and inference time than GAT, even with the smaller model, because of the continuous integration. Concrete run-times are not given, so I can’t say for sure.

### Further suggestions for improvement:
- I’d be very interested in the performance of including channel mixing in the flow, referred to as Onsager diffusion, as currently, the fact that the channels only interact via the attention seems limiting. The same holds for time-dependent diffusivity.
- Include (some idea of) the structural assumptions in thm 1 in the main paper.
- Include results on BLEND-kNN on ogb-arxiv or explain why this result is missing.
- Include some actual run-times of BLEND(-kNN) vs other methods.
- In the appendix clarify why (9, suppl mat) is the obvious discrete analogue of (6, suppl mat). I see some notational similarity between (10, suppl mat) and (6, suppl mat), but that looks rather superficial, besides it being one possible generalization of the classic Dirichlet energy. In fact, the paper doesn’t seem to be using this additional generality and only shows the classic example in which $\tilde\psi$ is constant. What does this additional $\psi$ generality add?
- Could the authors clarify the step from (8, suppl mat) to (1)? Where does the time come from?

### Typos:
-	Eqn 4, $x(x,0)$ should be $x(v, 0)$
-	In Table 3, the score for GCN on CiteSeer is bold.
-	The colouring in Table 3 seems incorrect. The BLEND-kNN performs on par with CGNN.
-	The eqn under line 48 in the suppl mat would be clearer if parenthesis would be added to indicate that the partial derivative only applies to Z.
-	Line 153, missing reference


### Conclusion:
- Originality: The work is original. It tries to connect differential geometry to continuous flows in graphs in a way I hadn’t seen before.
- Quality: I have doubts about the correctness, as I question whether the presented theory applies to the proposed model. Additionally, important ablations are missing.
- Clarity: The paper is clearly written.
- Significance: The paper can be significant to all people researching graph neural nets and open exploration into continuous flows on this domain.
- Score: 5, marginally below acceptance threshold. If the authors can convince me the theory does apply to their model, I will increase my score.
- Confidence: 4. I read the paper in detail.

limitations_and_societal_impact: The fact that their theory does not seem to be applicable to the used model, is not honestly mentioned in the limitations. To the contrary, the vagueness of unspecified 'structural assumptions', that are only given in the appendix, makes this theoretical limitation hard to find.

I think the authors underestimate the current use of graph neural networks in industry. They are used widely. As such, some more elaboration on potential negative societal impact of graph neural networks in general could be given.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: ** score updated 6->7 after rebuttal**

The paper proposes an interpretation of various GNN related architectures as Beltrami flows on a 2-manifold of position and feature embeddings, using this perspective to formulate a GNN architecture which uses feature encoders to create starting points in the 2-manifold and learned attention kernels (in their experiments, shared across time/layers) to give the update of the embeddings. The authors propose that this unifies various architectures as well as graph-rewiring techniques developed in the literature, evalaute against GCN,GAT,GAT-ppr,MoNet,GS-{mean/maxpool},CGNN and G(O)DE on cora,citeseer,pubmed,coauthor-CS,computer,photo and ogb-arxiv, showing their method matches or outperforms all other methods when taking into account parameter efficiency.
main_review: The authors follow the NODE approach of viewing residual layers as ODE steps, allowing a continuous depth when training with differential equation solvers and parametrizing an implicit layer. 

The paper is well written (except for some typos, see below) and the perspective of graph rewiring through a continuous  process is intriguing. However, I have some questions before I can give  a higher rating

-  you present various extensions in 3.4, what would be the expressive power hierarchy? I assume it goes deepsets \subset Beltrami with time independent attention(w.t.i.a)  \subset Onsager w.t.i.a \subset Onsager Onsager w.t.d.a \subset onsager with generic time dependent nonlinear equation == full attention network with enough layers?
- how does this work compare with e.g.  https://arxiv.org/abs/1909.12790 and  G(O)DE/CGNN specifically? I think it's worth highlighting commonalities and differences, especially since G(O)DE/CGNN seem competetive with your method in table2  and 3 
-  since you are using attention on the node embeddings, this means this method will be quadratic in cost w.r.t to number of nodes? as opposed to the sparsity amortization afforded by e.g. MPGNN?
- you highlight the expressive power in the abstract, but if I undertand correctly, your method can only ever be equivalent to MPGNNs with rewiring techniques/full attention right? Or do you have a proof/example that says otherwise?
- did you perform tuning with raytune for *all* methods not taken from the Pitfalls of GNN paper? It might be worth marking which is taken from the paper with a cross or something, and state explicitly whether the others were tunes fairly
- following up on the complexity question, I think adding training curves or some details about training costs and parameter counts to the appendix would be beneficial to putting the work in context. in general, NODEs offer a tradeoff, not a free lunch
- did you apply the jacobian/kinetic regularisation to G(O)D/CGNN as well? how does your method perform without the regularisation? 

Typos:
I assume in the equation between 212 and 213 Y is meant to be decoded with \xi, not with \psi, which is referred to as encoder in 213?

limitations_and_societal_impact: I think the authors are understating the negative effect  social network analysis can have in terms of surveillance and manipulation, as well as understating the benefit that can come from better architectures for relational tasks expressible as graphs.  VLSI,logic programming etc. can all benefit from this, as can the design of automated propaganda techniques, LAWs and police states. 

As for limitations, as I said, computational expense should be discussed in the paper as well, or noted as a bottleneck.
review_title: null

Meta-review: The paper proposes a novel class of GNNs based on non-Euclidean diffusion PDEs, i.e., Beltrami flows on 2-manifolds of position and feature embeddings, and can be seen to generalize various existing GNN architectures. The paper is well written and relevant to the NeurIPS community. All reviewers and the AC support acceptance for its contributions, especially due to the novel and interesting ideas that provide a new perspective for graph learning methods as well as the promising empirical results. The authors' rebuttal, including additional experiments, further increased the confidence of reviewers and resolved concerns related to the empirical analysis. When preparing the camera ready version, please incorporate the overall feedback of reviewers into the new revision (e.g., motivation, theoretical discussion of Thm 1 and limitation, ablation).
Decision: Accept (Poster)