Venue: NeurIPS 2022 Conference

Reviews:

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 proposes a new topological perspective of GNN. In the first part of the paper, the authors introduce the concept of “cellular sheaf” and “sheaf Laplacian” which allows defining a diffusive process over the graph. Interestingly, the ability of the diffusive process to correctly classify the nodes in the input labelled graph is strictly related to the class of the sheaves considered to define the process itself.

The continuous sheaf diffusion can be discretised using the Euler method to solve PDE, obtaining the sheaf convolution. The properties of the sheaf convolution are studied by observing how it affects the Dirichlet energy of the process.

In practice, the convolution sheaf operator is not known and should be learned from data. To this end, the authors propose three different convolution models that can learn the sheaf operator. In particular, the three alternatives are diagonal sheaf operators, orthogonal sheaf operators and general sheaf operators.

The experimental results show competitive performances against standard GNN models.

strengths_and_weaknesses: The paper is interesting since it applies topological concepts in the context of graph learning. To the best of my knowledge, the application of the sheaf theory in this context is novel. I believe that the most interesting result is the connection between the sheaf structure and the classification ability of the diffusion process associated with that structure.

The paper is well written and easy to follow. The only part that I found not clear is Section 5 (see questions). Also, I believe that more words could be spent explaining the experimental setting (see questions). 

Finally, it is hard to conclude that the proposed models outperform the baseline models due to the variance of the results. I do not believe that this reduces the impact of the paper, but I would change sentences such as “the models achieve state-of-the-art results” and similar ones.

questions: 1) Why are we interested in studying the Dirichlet energy of the sheaf convolutional network?
2) From my understanding, it seems that we prefer sheaf convolutional networks that do not converge fast to the equilibrium (the zero-energy point). On the contrary, the property of the sheaf diffusion process is studied in the time infinite limit (that should be the equilibrium). Why is there this difference?
3) How X(0) is computed? From my understanding, the node features are stored in a matrix N x F. Nevertheless, X(0) should be ND x F. Is an MLP used for this goal? Is the same MLP for all input features?
4) How is the parametric matrix-valued function \phi used? Is it used to build the sheaf Laplacian explicitly? Is the cost of evaluating \phi considered in the computational complexity (I think it should be O(d^2) in the diagonal case)?
5) The \phi defined in the paper allows building only symmetric sheaf operators. While this allows to speed up the computation, it reduces the separation power. Are there any other options that could be considered to find a trade-off between complexity and power?

Minors:
1) In proposition 1, maybe W should have subscript 1.
2) I suggest another capital letter (W is already used) to denote the parameter of the MLP which learns the sheaf operator.

limitations: Yes, the authors discuss the limitations of their work.
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 authors define a study a notion of graph neural networks that involves a notion of "sheafs" on graphs, which are vector spaces and linear operators attached to the nodes and edges of the graph. A givencellular sheaf thus defines a particular notion of message passing, where messages are transformed by the linear maps during propagation. This defines a generalized notion of Laplacian, as a block matrice involving the linear operators. The authors perform a basic harmonic study of this Laplacian, whose dominant eigenvector determines the infinite-time limit of the corresponding diffusion process. They study different classes of restricted sheafs, and their power to separate data by this diffusion process. Finally, a sheaf learning procedure is presented, similar to a generalized attention process.
strengths_and_weaknesses: Strength:
- an original notion, grounded in algebraic geometry and topology, with an original instanciation on graphs
- a quite complete investigation

Weaknesses:
- the paper could be more explicit regarding the relationship with the proposed model and existing ones. In particular, when the sheaf must be learned, unless I am wrong the proposed model falls under the classical paradigm of message-passing (but with a generalized notion of "attention" that compute matrices between nodes). So, all the Weisfeiler Lehman analysis still applies (for instance), and statements like the end of Sec 5 "SCNs are more expressive than GCNs" are a bit misleading.
- Regarding this, the proposed architecture probably brings some implicit bias to the training, but it is difficult to which extent this really is more "powerful" than classical MPNNs (it seems SCNs could be, for instance, simulated with enough layers and MLPs). Moreover, in practice a different "sheaf" is learned at each layer, so it is not clear how the limit diffusion analysis is really observed in practice.
questions: - in practice, there is no guarantee to learn effectively the right sheaf that will separate the data, is your asymptotic analysis robust to perturbed sheaf?
- if you learn only a single for all layers to simulate the diffusion process, do you learn what is expected in your analysis? Eg on simple two-communities graphs?
limitations: Discussion is appropriate.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper uses cellular sheaf theory to study the oversmoothing behavior of GCNs and their limitations in heterophilic graphs. Additionally, it proposes a novel deep convolutional model, the SCN, and extension of Kipf and Welling's GCN where one simultaneously learns the sheaf and the convolution weights.
strengths_and_weaknesses: Strengths:

- The paper is clear, well-written, and easy to understand (especially given the complexity of the topic).

- The technical contributions are timely and significant: Proposition 10 and Theorem 18 provide a possible explanation for why GCNs do poorly in node classification problems on heterophilic graphs, and Proposition 12 and Theorem 18 for why they do poorly in problems with more than two classes. In contrast, Proposition 13 and Theorem 16 show that general SCNs do not have these limitations because neural sheaf diffusion can achieve linear class separation, and that this separation can be achieved exponentially fast. At the same time, Proposition 17 shows that in SCNs the Dirichlet energy is not constrained to decrease (unlike in GCNs).

Weaknesses:

- The paper (specifically, Sections 4 and 5) lacks a more precise link between the specific theoretical results (propositions, theorems) and the specific problems (limitations associated with heterophily, oversmoothing) that they help explain. In particular, the link between the Dirichlet energy and oversmoothing can be made clearer. Another suggestion is to indicate, in the introduction or in the gray inserts, which theorems/propositions explain the heterophily and oversmoothing problems respectively.

- The numerical experiments are convincing but limited.

     - Synthetic experiments: in the main body of the paper, it would be more interesting to see results for $d>1$. The benefits of 
       asymmetric Laplacians and negative weights have been previously observed in the literature. Moreover, considering $d>1$ would 
       provide a better illustration of the generality of the model, as SCNs with $d>1$ cannot be reduced to GCNs. One suggestion is to 
       compare the ability of SCNs and GCNs to perform node classification on graphs with more than two classes.

     - Real-world experiments: the gains in performance (w.r.t. to other GNN models) in Table 1 are not very significant, but the results are 
       competitive and the main contribution of the paper are its theoretical results.
questions: - Per the theorem statement, Theorem 18 only holds for the Leaky ReLU and ReLU nonlinearities. Would other nonlinearities (e.g., the sigmoid or the tanh) significantly change its result?
- To improve the readability of the paper, a minor suggestion is to make the conclusions in lines 239-242 (that GCNs cannot linearly separate heterophilic bipartite graphs and graphs with more than two classes respectively) corollaries, or to highlight them somehow.
limitations: The main limitation of the paper is that its analysis only holds for the asymptotic case where $L\to\infty$ ($L$ is the number of layers). In well-connected graphs, using many message-passing layers leads to redundancy, so it is not hard to see how a deep architecture might exhibit oversmoothing. The authors should discuss this limitation more thoroughly (both in Section 8 and in the introduction), especially considering the fact that, in practice, many of the GCN architectures that exhibit good performance are not very deep.
review_title: null

final_score: 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.
review_content: summary: This paper investigates the heterophily and oversmoothing problems in graph neural networks through the lens of cellular sheaf theory, and reveals that these problems can be avoided by building a proper sheaf model upon graph that is suitable for the task. It also proposes NSD model based on the theory, which is latter verified effective in heterophilic graphs.
strengths_and_weaknesses: In general, the idea of building a connection of sheaf theory and graph neural networks is somehow intriguing, and perhaps also fruitful in the sense that it provides a new perspective to understand heterophily and oversmoothing problems. The corresponding theoretical results about how a proper choice of the sheaf structure can help to solve these problems may greatly benefit our community. The mathematical analysis seem extensive and sound though I didn’t check the proof in the supplementary material. Experimental results also show that the proposed NSD model performs better especially in heterophilic graphs, which is in alignment with the theoretical findings. 

I think the downside of this paper is the readability. Since it is very likely that most of the interested readers from the graph learning community are not familiar with sheaf theory (or differential geometry and algebraic topology), the readability of this paper would improve greatly to add more intuitive explanations on abstract theoretical results, e.g., regarding why change of sheaf structure can affect model’s separation power. In addition, it appears that the theoretical results in Section 3 about the properties of harmonic space are only of analysis interest and their connection with rest of the paper is somehow loose. I suggest the authors to move some of the details to appendix or explain more about their connections if they are indeed crucial. 

I also have some concerns or questions regarding the implementation and experiments. 
1. The computation complexity seems to be large, which scales with the stalk dimension as O(d^3). Though one can use batched GPU computations for training as the authors pointed out, the scalability problem may still remain when in comes to making predictions in the inference stage.
2. The paper seems to be missing a baseline, i.e., SheafNN [1], the predecessor of the proposed NSD. The authors also claimed that the proposed NSD is more powerful than SheafNN, so to what extent can NSD empirically outperform SheafNN?
3. The authors claimed in Section 4 that higher stalk dimension and more complex restriction maps indicate better separation power. But does better separation power necessarily translate into better ability to handle heterophily? If this is the case, how does the performance of NSD change with increasing d and restriction map complexity?
4. Table 4 shows the results of adding positional encodings, but what does it have to do with stalk dimension in the table captions? (p.s., ‘3.51 ± 5.05’ in the table seems to be wrong?)

[1] Sheaf neural networks. In NeurIPS 2020 Workshop.
questions: See above.
limitations: I don’t think this paper has any negative societal impact.
review_title: null

Meta-review: metareview: All reviewers agree that this paper deserves to be published in NeurIPS 2022, with some minor concerns that are (mostly) adressed in the rebuttal. Please incorporate the remaining reviewers' feedback for the camera-ready version.
confidence: Certain
Decision: Accept