Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an interesting idea on designing a novel graph neural network to capture the long-range dependency, which is the lack of ability of most existing works. A linear model that extends SGC with implicit infinite layers, EIGNN, is proposed to mitigate this issue. A closed form of the infinite sequences is used to define the layer-wise update rule and eigendecomposition is combined to achieve more efficient training. Experimental results on both synthetic and real-world datasets demonstrate the effectiveness of the proposed EIGNN for capturing the long-range dependency.
main_review: Strengths:

S1: It is important for the GNN models to obtain the ability for capturing the long-range dependency.
S2: The idea to extend the linear model SGC into infinite layers is interesting, since it could help the community rethink the representational ability of linear models on graphs. The theoretical analysis on convergence and training of the model has merits. 
S3: The paper is easy to follow with a clear motivation and comprehensive experimental analysis.

Weaknesses:

W1: The design of extending SGC (from Equation 1) to EIGNN (from Equation 3) is somehow implicit and ad-hoc without clear justifications. The authors should explain this more in details for better understanding by general audiences that not very familiar with implicit models.

W2: During the time complexity analysis, only the complexity of training is analyzed, but it seems like the computation of eigendecomposition of S, the normalized adjacency matrix with self-loops, (Line 176) is not added, which usually requires the cost of $\mathcal{O}(n^{3})$. If this is true, a full eigendecomposition of a large sparse S could make EIGNN an impractical approach for prohibiting the scalability in terms of large number of nodes $n$ for huge real-world graphs.

W3: Several concerns upon experiments include:
1)	The discussion on arbitrary hyperparameter $\gamma$ is missing, including how to set it in practice for a given graph and analyzing on the sensitivity of this hyperparameter， otherwise it will be hard for the researchers to follow.
2)	As the weakness on the analysis of complexity, why the author chooses not to evaluate the long-range dependency on the standard dataset Amazon Co-purchase as used in IGNN. Amazon Co-purchase dataset has another benefit that it can also reflect the scalability of proposed method since it is a large dataset with ~33k nodes, while the experiments on real-world dataset are all conducted on graphs that less than 10k.
3)	For the evaluation on over-smoothing, it would be interesting to see how the EIGNN performs with respect to over-smoothing under standard setting on real-world datasets, especially in comparison with variants focusing on dealing with over-smoothing, such as the setting used in GCNII.
4)	The evaluation on robustness is not very convincing since structural attack is known to be more powerful and appreciative when we attack on graph-structured data. Thus, the authors are suggested to defend their proposed model against several popular structural attack methods such as Nettack for better demonstration rather than attacks on features used in experiments.

limitations_and_societal_impact: Yes, the authors have discussed in the conclusion part.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes an infinite-depth GNN which captures long-range dependencies in the graph while avoiding iterative solvers by deriving a closed-form solution. The eigendecomposition method is introduced to further improve efficiency. Experiments on several datasets shows improved performance.


main_review: 1. The paper proposes the EIGNN in Section 4. The model is formulated in Equations (2), (3), and (4) but didn't provide any explanation for this model itself. Therefore, the motivation of the model is unclear. 

2. Instead, Section 4 focuses on introducing the forward and backward computation. In section 4.1, it is clear that the computation and memory cost is not acceptable because it requires dealing with the inverse of a very large matrix and the inversed matrix is dense. 

3. In section 4.2, an eigendecomposition method is introduced to improve efficiency. However, it still requires the eigendecomposition on the matrix $S$ whose size is the number of nodes. This is still very expensive for a reasonably large graph, and the result of the decomposition are dense matrices that require significantly large memory and costly computation.

4. The paper tries to avoid iterative solvers that cause approximation errors. However, there is no convincing evidence to show how the approximation error impacts the performance. Therefore, the advantages of using a closed-form solution are unclear while the drawbacks are obvious. More ablation study would be helpful.

5. The datasets in the experiments are very small graphs, it is unclear how the model performs in large graphs in terms of both efficiency and effectiveness. The efficiency comparison with iterative solvers will be helpful.

6. In the experiments on the synthetic chain data, there is a huge performance gap between EIGNN and IGNN. Considering that IGNN is able to capture long-range dependencies, it is unclear where the improvements of EIGNN come from. In the experiments on real-world data, the performance gap between EIGNN and H2GCN is very small while the gap between EIGNN and IGNN is huge. It is a bit confusing and again raises the concern -- where do the improvements of EIGNN come from.

7. While it is possible to verify the benefits of capturing long-range dependencies in the synthetic graph, it is unclear whether this property helps in real-world graphs and how to confirm it. 

Overall, this paper proposes an infinite-depth GNN with a closed-form solution. However, the computation and memory cost is still very high. Moreover, without an explanation for the model, the reason for the performance improvement is unclear.

--------------------------
During the discussion, I have raised my rating from 3 to 5.
limitations_and_societal_impact: The limitation of EIGNN should be discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an efficient method for infinite-depth GNN model that allows learnable transformations in each layer. A more efficient computation (eigen-decomposition) of the close-form solution is discussed and proved in the paper. In the experiments, EIGNN shows superior performance on both synthetic and real datasets which requires long-range dependencies capture. The robustness of the method is evaluated by perturbation of node features as well.
main_review: Overall, the paper is clear and easy to follow. The result presented in the paper is both significant and efficient, which aligns well with the original claims made in the paper.

Weakness and Questions:
1. Some of the interesting work at long-range dependencies are neglected in both related work and experiments. For example, the author mentions APPNP/PPNP in the experiment, while I think this one is quite related with the main contribution of the paper and author should discuss this one in related work. Also, another work called "Continuous Graph Neural Networks" [1] is worth discussing in the paper. In its 4.2, it also applies learnable parameters in an infinite-layer GNNs and conduct solution. The author should consider discuss and compare with this method as well.
2. The dataset selected might be biased towards to the long-range dependencies on node classification. I notice the proposed method yield a large margin to the selected dataset. However, these datasets are both small and not well-known for node classification (see OGB for large benchmarks). Why not you do graph classification instead like the original IGNN paper? 
3. The scalability of the method. As far as I understand, although eigen-decomposition is way more efficient than inverse computation. But in a large network with millions nodes, can you still handle it via eigen-decomposition?

[1] Xhonneux, Louis-Pascal, Meng Qu, and Jian Tang. "Continuous graph neural networks." International Conference on Machine Learning. PMLR, 2020.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a linear infinite-depth GNN, whose forward pass is a convergent series whose limit can be written in closed-form. Since the series involves the powers of the normalised adjacency matrix, the resulting model captures interactions between all pairs of connected nodes. At the same time, the existence of a closed-form expression makes the gradients easy to compute and provides an easy way to train the model. The authors show how the computational complexity of the model can be improved by diagonalising some of the matrices involved in the computation. The paper validates the hypothesis that the model can capture long-range interactions better than existent models in a synthetic setting and also on small real-world heterophilic graphs. 
main_review: ## Strong points

- The authors introduce a model that has many attractive properties: (1) It has residual connections, which have been shown to play an important role in a graph setting, (2) it involves powers of the adjacency matrix which in the limit allows all connected pairs of nodes to interact (3) The series has a nice closed-form expression in the limit that allows the model to be easily trained, (3) the model does not require solvers, which are generally slow or suffer from instabilities.
-  The only inconvenience of the model is that the complexity of computing the closed-form expression is not practical. The authors also offer a (partial) solution for this by proposing various approximations based on the eigendecomposition of certain matrices. 
- The chain dataset is a great synthetic setting for testing the theoretically justified ability of the model to capture long-range interactions and the authors compare the model carefully against IGNNs in this setting. They also perform a reasonably convincing ablation for IGNN to better understand its limitations. 
- The authors also consider a real-world setting formed of heterophilic graphs, which is indeed an appropriate class of graphs for testing to some extent the long-range interactions that the model can capture. 

## Improvements and Questions

- Some of the motivations behind the work are slightly incorrectly stated and do injustice to classic GNNs. Therefore, these could be rephrased: 
  - In the abstract (and other places) the authors claim that "finite layers" -> "unable to capture long-range interactions". This is not correct. For all practical purposes, the long-range interactions that can be found in practice are bounded by some constant $L$ and a GNN with $L$ layers will be able to capture them. 
  - In line 34 "GNN models with numerous layers require excessive computational cost in practice". The complexity of a message passing GNN with $k$ layers in a graph with $E$ edges is $\mathcal{O}(kE)$. Even assuming that $k ~ \mathcal{O}(V)$ (the number of vertices), this is still $\mathcal{O}(VE)$, which I would not call "excessive". Note that for the eigendecomposition of $S$ in line 176, the complexity is $\mathcal{O}(V^3)$, which is worse when the graph is sparse (I also have a question about this below). 
  - In line 30: "... poor empirical performance when stacking more than a few layers, which has been referred to as oversmoothing". Oversmoothing is only one of the causes of why Deep GNNs often have problems and it is more common among convolutional models (https://arxiv.org/abs/1905.10947). There is also over squashing (https://arxiv.org/abs/2006.05205) and it is also likely related to optimisation issues as well. 
- Regarding the complexity of the method, the $\mathcal{O}(V^3)$ eigendecomposition of $S$ from line 176 does not seem to be included in the reported computational complexity. Why is that the case? That is very problematic for many applications where the number of nodes is well beyond $1$ million. Is this why the authors evaluate only on extremely small graphs (see my next point)? The authors might argue that the eigendecomposition of $S$ is not such a big problem because it is a one-time pre-processing step, but this could still limit its applicability in a real-world setting where the graph is often changing in time. 
- As mentioned above, the real-world benchmarks used by the authors are extremely small. While including small-sized graphs is totally justified, I would expect to see at least some medium-sized graphs in the evaluation as well (e.g. from https://ogb.stanford.edu/ or https://arxiv.org/abs/2003.00982).  Based on this and my point above, I have doubts about the scalability of the model in a practical setting. 
- Another limitation that is not mentioned is that using the eigendecomposition of $S$ in the model makes the model inapplicable to multiple graphs because the eigenbasis changes from one graph to another and even for isomorphic graphs, it is not uniquely defined (for more details see e.g. https://arxiv.org/abs/1611.08097). This can be a problem for many practical settings where we want to classify nodes from multiple graphs or maybe we want to perform pre-training on another graph. 
- The limitations of the model have not been properly addressed. The authors have included only a sentence in the conclusion on this. For instance, my point on the $\mathcal{O}(V^3)$ complexity or the transferability across different graphs could have been mentioned. Are there any other limitations that the authors could mention?   
- All the figures in the experimental section are missing standard deviations. All experiments should be run over multiple weight initialisations for all the models. Without error bars around the curves in the figures, the reported results could just be lucky runs. 
- While I appreciate the experiments on noise robustness, they only show results on a synthetic graph where the proposed model was already performing better in the first place. At the same time, no justification is offered as to why the proposed model would be more robust to noise. An intuitive justification (if not theoretical) should be presented and validated at least. 
- The paper does not comment at all on the closed-form expression from Proposition 1 to provide a deeper understanding. The expression looks very interesting and the authors could attempt to provide an intuition about what it actually does. For instance, how is the information from different hops around a source node weighted by this expression? 
- A Question: What is the purpose of Proposition 3 and Equation (9)? Since the forward pass has a trivial closed-form expression, the gradient can be trivially computed by an automatic differentiation package. Furthermore, the authors do not seem to use the gradient in their follow-up analysis and, therefore, it could be simply added to the appendix since it does not seem to provide any essential information to the reader. Or is the computation of the derived gradient more efficient than what automatic differentiation would compute? I do not believe that is the case, but if it is, then it should be proven. 

EDIT: After the rebuttal, I have increased my score from 5 to 6. 
limitations_and_societal_impact: The authors have not addressed this in sufficient detail.
review_title: null

Meta-review: 3 of 4 ratings were "accept". The lowest rating (a 5) was most concerned about insufficient experimental evaluation of speed/accuracy tradeoffs, which was echoed by other reviewers as well.

Through the rebuttal/discussion period the authors were very responsive and caused several reviewers to raise their ratings. My view is that the original submission was somewhat confusing and incomplete in a few ways, but that the core of the method and results are solid, and through the discussion period the authors have improved the paper enough to warrant publication. The confusion could also stem from the fairly high technical complexity in the work, which I'd encourage the authors to explain as clearly as possible in the final text.

I do agree with the concern about speed/accuracy analysis, and I'd encourage the authors to do anything they can to address this for camera-ready (if the paper is accepted), however I don't anticipate any surprises.

Decision: Accept (Poster)