Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In graph neural networks, convolutional layers operate by aggregating information about local neighborhood structures. This paper extends to hypo-elliptic diffusions and the derived tensor valued graph operator. 

In short, this paper builds the operators by using random walks but instead of taking only the endpoints of random walks, takes averages over path-dependent functions. Here the ordering of vertices visited in a random walk matters. Using random walks to build feature vectors for graphs is a classical idea (e.g., Deepwalk), which has also been extended to other local graph features such as breadth-first trees etc (e.g., Node2Vec). This paper uses the entire path rather than the endpoint and build an algebraic operator. 



strengths_and_weaknesses: Strength: The approach of extension from using only endpoint of a random walk to the entire path of the random walk is natural. The paper presented a theorem (Theorem 2) which says that two labelled graphs are the same if and only if the distribution of k-step random walks of the two graphs are the same. The authors use diffusion over tensor transition matrix and introduce an attention mechanism. The paper explained how to efficiently calculate the operator on a graph.  

Weaknesses: see next box on questions.
questions: There are a few issues that the authors can possibly address/discuss:

	1. About descriptive power, is there theoretical understanding that the hypo-elliptic diffusion is strictly more powerful than just using regular heat diffusion on graphs? 
	2. There seems to be a tradeoff between computational cost vs results of the model via parameters such as k, the length of random walks, and R the rank of the functionals. Could the authors discuss the influence of these parameters in model performance?
	3. The results are comparable to earlier work that uses a Transformer model with graph neural networks (GraphTrans), which captures long-term interactions. The discussion at the end of section 5 regarding the performance comparison of this method and Transformer is a bit wishful. Can the authors provide more solid results backing up the discussion here (e.g., the summaries in this paper can also help Transformer submodule)? 

limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors present a novel version of the graph Laplacian which instead of capture information focused on start/end of a path, it emphasizes information along paths. This is inspired on previous notions of the hypo-elliptic Laplacian. Moreover, since the hypo-elliptic graph laplacian is a tensor-valued graph operator, the authors provide low-rank approximations which allow numerical computations, is it scales linearly with the number of edges, contrary to the standard case which grows quadratically with the number of nodes.

Together with the Hypo-elliptic Laplacian another key ingredient is the perspective of free algebras, which is relevant since the order in which nodes visited in a path is relevant, and free algebras induce algebra multiplication that are non-commutative.


strengths_and_weaknesses: The paper does a great job to briefly introduce the basic notions related to the hypo-elliptic graph and the corresponding free algebra notions that are required to grasp the basic intuitions of the concepts here considered. Further, supporting material is presented in the supplementary material that helps to grasp basic concepts related to this paper.

The presents an interesting modeling approach by showing/motivating that the proposed Laplacian indeed has certain properties that might be appealing in the context of learning long dependencies for GNNs. The analysis of the path, and not only relying on where it starts and where it ends has already been suggested, for instance (in a different context) by the non-back tracking operator (or the corresponding Bethe Hessian), even in the context of spectral clustering, where the graph Laplacian plays a crucial role [A].

Bibliography
[A]. Saade, Alaa, Florent Krzakala, and Lenka Zdeborová. "Spectral clustering of graphs with the bethe hessian." Advances in Neural Information Processing Systems 27 (2014).
questions: I understand that the proposed numerical scheme is presented in Theorem 3, but I would suggest to introduce a pseudo code. In general that would allow the readers to have a specific module where one can focus on explicit programatic steps, rather than having to follow non-programmatic terminology that naturally corresponds to a theorem.

Further, the authors describe the complexity to be O(K · M^2 · N_E + M · N_E · d) where $M$ is the maximum tensor degree, $N_E$ is the number of edges, $d$ is the dimension of node attributes. Given all these terms in complexity, would it be possible for the authors to report the execution time? I think this would be relevant for the reader, as for instance, the number of edges in the datasets ($N_E$) is not reported in the paper. Further, it is not that straight forward to track the values for the remaining parameters involved in the algorithm complexity. Providing the parameter values of the algorithm complexity, potentially in the supplementary material,  per dataset and model would be of great benefit.
limitations: It seems the authors do not provide potential negative societal impacts.
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 work the authors present a formalism where a tensor valued version of the graph laplacian, which they call the hypo-elliptic graph laplacian, is used to model the distribution of node attribute propagation via random walks as a diffusion process. They show how the solutions for the state of the resulting system after length k walks can be computed via low rank approximation algorithms and compare a concrete realization of their method to other common architectures for graph modeling. They argue that their method excels in representing long range dependencies while scaling more favorably than other approaches in the size of the graph.
strengths_and_weaknesses: ###  Strengths

**Quality/Clarity**: Sections 1-3 (along with the relevant appendices) are very well written, and do a remarkable job at providing an understanding of the background machinery required to understand the proposed method. In particular, the punchline results through Eq. 11 and 12 about the theoretical expressivity in node and graph representation extractable from the solution to the hypo-elliptic graph diffusion equation are exciting. 

**Originality**: Benefit of the doubt is granted on the overall presentation of the formalism being novel (reviewer is not a theorist), though I assume novelty is mostly concentrated on the tensor valued version of the diffusion equation, Eq 11.

### Weaknesses

**Clarity**: The work is remarkably readable, but there are a couple points:
- At the moment one reads line 105, it _is not_ immediately clear that we have built the map between $Seq(\mathbb{R}^d)$ and $H$, rather it should cite Appendix lines 612-618 as these are sort of the final step of that construction.
- The section on the low rank approximation of the functionals and the "Building Neural Networks" section is much harder to understand than the sections that precede it.

**Significance**: Despite the theoretical expressivity of the proposed model class, the particular setting evaluated only explores a max tensor degree of 2. This seems like a severely restricted realization of the model based on my understanding that $m$ sort of represents the dimension of the "summary capturing" capacity of the lifted form of the diffusion solution. The method only performs _competitively_ with GraphTrans. Ideally, since it's being proposed as an alternative to the family of available GNNs, the implementation results will be more developed in future work to more convincingly demonstrate the benefits in practice that the framework argues that it offers in theory.
questions: 1. Is there a reason why $m$ and $k$ are not used a bit more interchangeably? It seems like that dimension of cross product space and the sequence lengths we are lifting are practically the same? 
2. Can you describe the meaningful difference if any of thinking of elements of H as the m-dimensional cross of the node attributes along the path, rather than each sequence element individually as lifted to $(\mathbb{R}^{d})^{\otimes m}\$? (I think no, this is part of the elegance of the setup?)
limitations: 1. Somewhat duplicated from above, I am concerned about the $m=2$ restriction of the implementation results presented. It seems like this may take the power out of the method in some sense by barely maintaining the added depth/tensorial nature beyond the classical diffusion equation using the normal graph laplacian. Further, and this is _just a conjecture_, but it is possible that this limitation on $m$, plus the rank-1 approximation scheme is responsible for the shakeout of the results wrt the GraphTrans competitive baseline. Interested to hear the authors discuss this further.

2. The scalability of the approach may be problematic given that the complexity analysis already relies on the Rank-1 approximation and also contains an $M^2$ term suggesting that the small M setting may be a requirement for practical implementations. Without demonstration on graphs of realistic scales (well beyond 30 nodes), as well as the resultant larger graph diameters and path lengths, it's unclear whether the approach has to always be nearly reduced to the classical setting in order to applied to graphs of non-trivial sizes.
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: The paper introduces hypo-elliptic graph Laplacians -- a generalization of classical graph Laplacians to higher order tensors -- that are capable of storing the entire history of a given random-walk. This is studied in the context of attributed graphs where each node is equipped with vector information. Theoretical analysis is carried over to demonstrate that 1) the analogous tensor-like diffusion process retains the probabilistic interpretation of standard scalar random walks and 2) graph feature maps can be defined on these processes w/o losing expressive power. A low-rank approximation is provided to make the approach scalable and experiments are conducted on datasets that present long-range dependencies. 
strengths_and_weaknesses: Contribution and novelty: To my knowledge -- I am not an expert in the field of hypo-elliptic operators on non-Euclidean domains -- the contribution of the paper is original. This applies to both the theoretical analysis in Theorem 1,2 and the low-rank approximation in Theorem 3 that builds on previous work in [56].

Presentation: The paper is very well-presented and the organisation does not require main modifications. On a minor side, some of the paper is quite technical and potentially obscure to a significant part of the community.

Strengths (in random order):

- The exposition is clear.
- The problem at hand is of interest, given that standard MPNNs are known to struggle on tasks with long-range dependencies, mainly due to the problem of over-squashing.
- The theoretical analysis in Theorem 3 is of relevance in the context of the tools and techniques introduced, given that it provides a scalable approach.
- The implementation/experiment section has detailed explanation with sufficient ablation studies that strengthen the message and indeed highlight the robustness of the method.


Weaknesses (in random order) -- I reserve some unanswered points to the Questions paragraph below; depending on the rebuttal such points could be solved or become weaknesses with consequent adjusting of the score.

- Theorem 3 inevitably leads to a loss in expressive power and it is not entirely clear how the loss would depend on M, and R (minor point).
- The proposed method is not (significantly) better than faster/standard GNN methods on task like node-classification where long-range dependencies may not be crucial. This is somewhat expected but it limits the impact of the approach. 
questions: - While the problem is relevant, the solution is somewhat not surprising. If we store more information directly via tensors, then this will avoid aggregating information from distant nodes along the 1-hops only hence alleviating the over-squashing phenomenon. A perhaps more interesting analysis should entail what this higher-order approach is effectively accomplishing. Is it `just' a matter of storing higher-order (i.e. non-local) information? Do we actually need random walks exactly or a higher-order approach that store information without leveraging the algebra representation is going to accomplish similar results? What does such method give us when compared to more standard MPNNs like, say GIN, when augmented with JK connections for example? I don't expect a specific answer here but some speculation might improve the message.
- In the proof of Theorem 3 I believe there is a typo in the proof of the case for $f_{1,m}$ where we should have $\frac{1}{d_{i}m!}\prod_{r= M - m +1}^{M}\langle u_{r},f(j)-f(i)\rangle$.
- Some analysis of the number of parameters might be relevant here. How do you compare to baselines?
-  A clock experiment comparing running time of GT2N/GT2(A)N with baselines would also be important here. 
- The size of the random walk is chosen to be 5 on the molecular datasets: how would that compare to the average diameter of the graphs? Is in fact this quite a `global' approach already?
- Why in the experiment section you only compare with [64] on some of the datasets used in [64] and not all of them? A comparison with Table 2 in [64] would appear meaningful here.


Conclusions: The paper is novel and the idea of relying on the algebra representations to memorize the full history of the attributed random walk is an elegant formalization of an idea that has entered existing `tricks' one way or another. Of relevance the proposed approximation in Theorem 3. There are a few questions partly left-unanswered. As mentioned above, how the questions are addressed may affect the final score (in both ways). 
limitations: Societal impact is not reported. Limitations are partly addressed in the paper.
review_title: null

Meta-review: metareview: This paper proposes a new principled graph learning method to aggregate information local neighborhood. The proposed method essentially aggregates information from random walk but not only w.r.t. end points but also w.r.t. the paths. All reviewers agree that the idea is novel and the idea is well founded. Valid questions regarding expressive power, computational expense, etc. were raised and were addressed reasonably during rebuttal period. 
confidence: Certain
Decision: Accept