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: In this paper, the authors propose implicit GNN with an effective range concept.

While previous implicit GNNs can be treated as neural networks with infinite layers sharing the same weights, MGNNI can exploit long-range dependencies capturing multi-scale information.

The $\gamma$ control can constrain the expressiveness of GNNs via effective range.

For multi-scale information, they exploit a set of scales $M$ and corresponding equilibriums $Z$.

The model is optimized in an iterative manner, not a closed-form solution because of the slow training speed over large graphs or a large number of node features.

MGNNI has comparable time complexity with IGNN and CGS because of the iterative method for convergence but it is more efficient than EIGNN which exploits eigendecomposition.
strengths_and_weaknesses: Implicit GNNs are getting more and more attention as one of the ways to complement the existing message-passing paradigm.

However, the researches for implicit GNNs are not plentiful that much compared to other explicit architectures.

The concept of effective range and the corresponding set of multiple scales with equilibriums might be akin to multi-hop aggregation of existing message passing GNNs such as ChebNet and SGC.

Using multiple propagation modules for multi-scale information may seem a bit naive, but I think it's well worth a try.

questions: -
limitations: The authors adequately addressed the limitations. While MGNNI can capture multi-scale information, there is a limitation from potential approximation error as other iteration-based methods such as IGNN and CGS.
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: The paper points out a main draw back of existing implicit graph neural network — its limited effective range. Although implicit graph neural network has implicitly infinite depth and infinite large reception field, the influence between two nodes decays exponentially with distance along the graph, so it still cannot capture long range information well. The paper propose to alleviate the problem by multi-scale propagation, which utilize adjacency matrix with different powers to propagate info, and finally fuse propagation results of different scales by attention mechanism.  
strengths_and_weaknesses: Strength:
1. the paper is well motivated, well written and easy to follow. 
2. The drawback of IGNN is demonstrated by both theoretical analysis and experimental proofs.
3. The effectiveness of proposed method is also demonstrated by both theoretical analysis and experimental proofs.

Weakness:
1. The modification does not thoroughly overcome the drawback, but just alleviate it instead. Although effective range becomes $m$ times larger, the influence between two nodes still decays exponentially with distance along the graph in the proposed method. 
2. The proposed methods outperforms EIGNN by a large margin only in synthesized data, and behaves similarly as EIGNN in real world dataset.
3. I doubt the correctness and meaningfulness of some theorem, and expect explanations from authors. See my questions below. 
questions: ## About theorem 3:
1. eq. (11) has nothing to do with function $f(X, \mathcal{G})$ in eq. (4), which is strange. If I am correct, only when $f(X, \mathcal{G})=X$, theorem 3 holds.
2. If we replace $S$ in Theorem 1 by $S^m$, we can get following upper bound: 
$$\lVert\Delta Z^*_{:,q}\rVert \le \frac{\gamma^h}{1-\gamma}\lVert g^h(F)\Delta X_{:,P} S^{hm}_{p,q}\rVert$$ 
- It seems to be a tighter bound than theorem 3 (I am not sure), because $\gamma, g(F)$ and $S_{p,q}$ are less than 1, above formula has higher power on them, and thus the upper bound is tighter.
- If above upper bound is tighter, then Corollary 2 will become same as Corollary 1, and thus the effective range remains unchanged even with multi-scale propagation. If am wrong, please correct me.

## About motivation:

Do we really need so called "long range information" in real world applications? 
- In my opinion, locality is is not a drawback of Graph Neural Networks, or more generally, it is not a drawback of convolutional neural networks, including both CNN in image domain and GCN in graph domain. Instead, it is the key why CNN outperforms MLP and why GCN works. Nearby neighbourhood always has much more importance than nodes/pixels far away, because they are the nodes that closely related to the centre nodes/pixels. 
- Even if someone take it as a drawback, their methods still assign more importance to nearby neighbourhood. Nobody tries to give more importance to nodes far away than nearby ones, because that is not reasonable. Take the proposed method as an example, the influence between two nodes still decays exponentially with distance. 
- Experimental results also favours my opinion. In real word dataset, the proposed method performs similar as EIGNN, which does not consider multi-scale propagation. Only in handcrafted dataset designed for long range information, the proposed method outperforms EIGNN by a large margin.

This part about motivation is not a question, but a discussion. It is OK for you not to response. 
limitations: No special negative societal 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: In this paper, the authors analyze the "infinite effect" in implicit GNNs, and give the theoretical bound of the "effective range". Additionally, the authors extend the implicit GNNs with multi-scale ability plus the "effective range" analysis. The whole paper is complete, and the experiment results are promising.
strengths_and_weaknesses: Strengths
1. The flow of the paper is clear and well-written.
2. This paper gives a solid analysis of the implicit GNNs for their effective range. For dealing with the multi-scale problem for implicit GNNs, this paper proposes the MGNNI model with theoretical analysis.
3. The experiments are extensive.

Weaknesses
1. Some parts of paper can be reconsidered like the definition, derivation, and the experiments. For details and improvement suggestions, please refer to the following "Limitations" section.
questions: 1. For the first question, please refer to the first bullet point in the Limitations section.

2. In experiments, when a single scale is executed in MGNNI, is the attention mechanism in Eq. (7) - (10) still applied?
limitations: 1. The definition of multi-scale is not clear and needs to be specified. In the current version, from lines 48 to 57, the authors listed four related works and illustrated two of them. Just describing them could not lead to a clear understanding of multi-scale, and more especially, why [8] is a multi-scale method? A more straightforward question here can be like: does stacking GNN layers qualify as a multi-scale method? Or the scale of each node feature aggregation needs to be personalized could qualify as a multi-scale method?

2. Authors may want to be more careful about the statements from lines 38 to 47. A suggestion here is to highlight and well-define the term "effective". Because of the Theorem 1 and its proof, the effect still exists even though it is bounded by a small value, and the threshold $\theta$ is hand-crafted.

3. I am wondering about the role of the attention mechanism in outstanding experimental performance. The ablation studies could better consider removing the attention part.
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 proposes a new variant of implicit graph neural network MGNNI, which is a new type of graph neural networks that captures the long-range dependencies in underlying graphs. The authors first conduct theoretical analysis on the two weaknesses of previous implicit graph neural networks, namely limited effective range for capturing distant information and constrained ability of capturing multiscale information. They then show that MGNNI with multiscale propagation could expand the effective range and capture various-scale graph information. Experiments on both synthetic dataset and real-world graphs demonstrate the effectiveness of MGNNI.
strengths_and_weaknesses: Strength:
- The paper is easy to follow with a clear motivation and closely related to the NeurIPS community with comprehensive experimental and theoretical analysis.
- Theoretical analysis comparison on the effective range of previous implicit GNNs and MGNNI are important and sufficient.
- The current paper might have certain impact as it further explores a mild trend in the literature, which investigates the theoretical analysis of implicit graph neural networks.

Weakness:
- The theoretical analysis has the assumption that a contraction factor \gamma is used to ensure convergence in the aggregation step, which is not used in all implicit graph neural networks. This should be highlight in limitations. 
- The computational complexity for IGNN and CGS should be included for clearer comparison. How the multiscale propagation and attention mechanism used in MGNNI affects its computational analysis is missed.
- While the implicit graph neural networks are also known for effectively alleviate the over-smoothing problem for many GNNs, how MGNNI handles this over-smoothing problem should be discussed.
- For experiments, I noticed that the benchmarks used for evaluation are relatively small graphs with nodes less than 10K. While the efficiency of MGNNI is claimed as an advantage over many other SOTA implicit graph neural networks, I am curious about how the performance is on larger datasets such as OGB.
- Only four small-scale bioinformatics datasets are used in the graph classification evaluation and it is a known problem with those small and noisy datasets. It is encouraged to include other types of graphs such as social networks for more convincing.
questions: - Could IGNN/EIGNN/CGS with jumping knowledge connection effectively capture multiscale information on graphs? This is a interesting baseline to further demonstrate the effectiveness of the design of MGNNI.
- How do implicit graph neural networks such as IGNN that don’t rely on contraction factor \gamma to ensure convergence be included in the theoretical analysis framework?
- How do the multiscale propagation and attention mechanism used in MGNNI affects its computational analysis?
- Does MGNNI face the over-smoothing problem?
- How does MGNNI perform on massive graphs and other types of graphs such as social networks?

limitations: Limitations are addressed in the Conclusion, but the assumption that used in theoretical analysis should be also highlighted.

No potential negative societal impact is discussed, which is fair for a methodological contribution to a well-studied problem.
review_title: null

Meta-review: metareview: The paper points out the limited effective range problem of existing implicit graph neural networks and proposes to use multi-scale propagation (i.e., use adjacency matrix with different powers) to alleviate the problem. All the reviewers vote towards an accept after the author rebuttal. The authors are encouraged to include content from the rebuttal into the camera ready version.
confidence: Less certain
Decision: Accept