Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose the asynchronous message passing (AMP) framework to enhance the expressiveness of graph neural networks. In the AMP framework, nodes receive messages from their neighbors individually. The authors try to show that AMP is more powerful than the 1-WL test and can even compute graph isomorphism. Experiments demonstrate that the AMP-based model outperforms powerful synchronous GNNs on several GNN expressiveness benchmarks in terms of accuracy.
strength_and_weaknesses: **Strengths:**
1. This proposed AMP framework is interesting. 
2. Experiments demonstrate that the AMP-based model outperforms powerful synchronous GNNs on several GNN expressiveness benchmarks in terms of accuracy. 

**Weaknesses:**
1. The authors may want to provide a rigorous proof for Theorem 4.7. Some weaknesses are as follows.
    1. In the proof, the authors make the assumption of GNN's width and depth, which is not mentioned in Theorem 4.7.
    2. Corollary 3.1 in [1] assumes that the width of GNNs is unbounded, which is not equivalent to the assumption of a sufficiently wide GNN.
    3. The authors may want to provide the lower bound of the depth of GNNs.
    4. The application of Corollary 3.1 is confusing. What is the definition of Turing computable function in Corollary 3.1 in [1]? If a GNN can compute any Turing computable function, how to show that it can separate any pair of graphs?
2. From Table 3, we can see that the accuracy of AMP is clearly lower than existing powerful GNNs (e.g., ESAN). The authors claim that the low accuracy is due to little investigation into AMP architectures and hyperparameters, but it is not the key reason in my opinion, as more AMP architectures with more hyperparameters are available to ensure a fair comparison for the authors.
3. The authors may want to compare the time complexity and runtimes of AMP with those of synchronous GNNs.
4. The authors claim that AMP can propagate messages over large distances in graphs without the corresponding theoretical analysis.

[1] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations (ICLR), 2020.

clarity,_quality,_novelty_and_reproducibility: **Clarity:** This paper is hard to follow. 
I have some questions as follows.
1. How does the reaction block distinguish the neighbors with the same node feature and rooted subtree? Assume that node $v_1$ receives the messages from its neighbors $v_2$ and $v_3$ with the same node feature and rooted subtree. For an asynchronous GNN, node $v_1$ first receives message $m_1$ from $v_2$ and then sends the same message $m_2$ to $v_2, v_3$ according to Steps 8,9 in Algorithm 1. The updated node embeddings of $v_2$ and $v_3$ (denoted by $z_2$ and $z_3$ respectively) are still the same due to the same received message. Next, nodes $v_2, v_3$ generate the messages $m_3$ and $m_4$ with $m_3=\mu(z_2, m_2)= \mu(z_3, m_2)=m_4$, where $\mu$ is the message function (Step 9 in Algorithm 1). If node $v_1$ sequentially receives messages $m_3, m_4$ from $v_2, v_3$, how does the reaction block discard $m_3$ and keep $m_4$ in the proof for Theorem 3.1, such that AMP simulates synchronous GNNs, for which node $v_1$ receives and keeps a single message from $v_2, v_3$ respectively?
2. What is the meaning of "taking" in Table 6? Is it a state or message?
3. What is the expression of the delay distribution $\mathcal{D}$ in the experiments? 
4. In the third paragraph of the proof for Theorem 3.1 (A.1), the number of messages that the node is waiting on may be "w".
5. In the proof for Lemma 4.2 (A.2), "FOUND-(j+k)" may be "FOUND-(j+i)". 

**Quality:** The authors may want to provide a rigorous theoretical analysis.

**Novelty:** This proposed AMP framework is interesting.

**Reproducibility:** The authors provide the codes for reproducibility.

summary_of_the_review: I recommend weak reject due to the concern about the theoretical analysis, the experiments, and the writing (See Weaknesses and Clarity). If the authors can properly address my concerns, I am willing to raise my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new framework, asynchronous message passing (AMP), for graph learning. To be specific, each message passed along the edges is treated individually, which differs from the widely used message passing GNNs. Also, the expressiveness of AMP has been characterized. Experiments on synthetic datasets and real benchmarks are performed to evaluate AMP.
strength_and_weaknesses: 
Strengths:

1. The motivation and analysis of proposing AMP is inspiring and novel.

2. Treating messages individually is a novel and reasonable idea to go beyond the widely used message aggregation schema. This idea is novel and could be inspiring to the community.

3. The expressive analysis of AMP can answer the question why we should use AMP compared to message passing GNNs.

4. The empirical performance on the expressiveness synthetic benchmarks are compelling and can support the main claim well.

Weakness:

1. The empirical comparison on more and lager real benchmarks should be provided. In the current experimental results, only Table 3 is for real graphs. However, the size and number of the graphs are limited and cannot support the method strongly. I highly recommend performing more experiments on larger graph datasets.

2. The proposed new framework seems to be inefficient. The theoretical and/or empirical analysis of the complexity should be included.

clarity,_quality,_novelty_and_reproducibility: I found it a little bit difficult to follow the paper. It would be more easier to be followed if more intuitive description and direct mathematical equations can be provided.
summary_of_the_review: Overall, I think this work has merits in terms of the motivation and method. On the other hand, more analysis and experiments should be added.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to improve shortcomings of GNNS by updating the messages in an asynchronous manner. The paper shows how this relates to the standard GNN and argue how it can be used for testing graph isomorphism.
strength_and_weaknesses: The strength of the paper is that it proposes a potential remedy against certain problems of GNNs as over smoothing and underreaching. This is done by a relatively straightforward and intuitive algorithm

Yet, there are certain limitations to the work in its current form:
* The literature is not conclusive and a more focused presentation would improve the paper overall (see clarity,... below)
* As the authors say themselves, the proposed approach is not quite state-of-the-art. While this is not a problem as such (if the underlying idea is promising) it does not scale well because of the runtime. Overall, I have the feeling that AMP is a neat idea that, however, is not yet ready and would still require significant work.
* The theoretical contribution is overstated; i.e., it is not clear that AMP is at least as powerful as a GNN. Just because it can represent the same things in principle, it is not clear if and how this representation can be obtained.
* I really miss an honest and thorough discussion of the experiments and see this as a largely missed opportunity to understand AMP better. Many statements seem to come out of the air and are not corroborated. E.g., 
** It is claimed that AMP/R produces mediocre results because of unstable gradients. Why are the gradients unstable, what could be done against it, what is special for AMP in that respect?
** It is claimed that further improvements in AMP will reach a competitive performance. How can you be so sure? Which aspects limit the performance right now?. How could these aspects be improved?
** There are nice plots regarding the effect of underreaching and oversmoothing in the Appendix. Unfortunately, these sections do not actually analyze the experiments, but only state the results.



clarity,_quality,_novelty_and_reproducibility: I find that the paper lacks clarity in that it discusses various arguments for asynchronous message passing at length (human communication, recurrent architectures, GNNs, etc.) without making a point and giving a clear and concise motivation. Therefore it is also hard to gauge the actual contribution. The fact that the proofs are only presented in the appendix (without any summary of the main proof idea) does not help either. Even going through the proof of Theorem 3.1 it does not become obvious which parts are actual contributions of the paper and which ones of Awerbuch (1985).
It also seems that the references are not comprehensive. Asynchronous message passing has for example been successfully applied in traditional message passing algorithms (see e.g., [1,2,3]). The work in [4] shows the benefits of asynchronous event-based GNNs and is closely related.

Minor edit: "We hypothesize lies in better algorithmic alignment" is not a complete sentence

[1] Elidan, Gal, et al. "Residual belief propagation: Informed scheduling for asynchronous message passing." arXiv preprint arXiv:1206.6837 (2012).

[2] Knoll, Christian, et al. "Message scheduling methods for belief propagation." Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Cham, 2015.

[3] Aksenov, Vitalii, Dan Alistarh, and Janne H. Korhonen. "Scalable belief propagation via relaxed scheduling." Advances in Neural Information Processing Systems 33 (2020): 22361-22372.

[4] Schaefer, Simon, Daniel Gehrig, and Davide Scaramuzza. "AEGNN: Asynchronous Event-based Graph Neural Networks." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.
summary_of_the_review: The paper makes an interesting contribution from a conceptional point of view. It does not make a good argument for the proposed approach though, since a) the literature is not conclusive, b) it does not scale to larger graphs, c) the amount of theoretical contribution is not clear, and d) a thorough discussion and interpretation of the experiments (and thus the potential benefits and problems) is missing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose an asynchronous message passing (AMP) framework which is theoretically more powerful than the standard message passing framework. The experiments demonstrate its superior performance on synthetic datasets and moderate performance on graph classification benchmark datasets with small sizes.
strength_and_weaknesses: ### Strengths

- The idea of AMP is interesting, especially its various variants of designs.

- The results on the synthetic datasets are impressive.

- The provided experimental code is well-documented. The environment, package dependency, and the steps to reproduce the results are all stated.

### Weaknesses

- The clarity of the paper can be greatly improved. A pictorial illustration of the proposed framework would help a lot. I cannot understand how AMP works on the entire graph/graphs.

- The clarity of the pseudo-code (Algorithm 1) can be improved. Please specify the input and output of the algorithms. Also, what is $n$ in the for loop? Does Algorithm 1 works for one node or the entire graph?

- The running time of AMP is poor as it can only run on a single CPU. I do appreciate the authors pointing this limitation out.

- The AMP performance on real-world graph classification benchmark datasets still falls behind the state-of-the-art methods by a large margin. Also, the reported results for baseline methods seem to contradict the previous works.

### Detail comments

While I really want to learn what AMP is and how it can separate any pair of graphs in the optimal case, the clarity of the paper prevents me to understand AMP thoroughly. For example, I can understand how the asynchronous works for an isolated node from Figure 1. However, I cannot understand how it works for the entire graphs. When the constant delay is used, does the initial message simply the node features for each node? Do these initial messages happens at the same time or do we start the propagation from one node? The description of the AMP framework is too vague for me to understand. I suggest the authors add a pictorial example of the AMP framework on a simple graph. On the other hand, Algorithm 1 should state the inputs, outputs and hyperparameters. I am not sure what $n$ stands for in the for loop, where I suspect it to be the current node. I hope the authors can elaborate more about the AMP framework. 

Although the authors show that AMP is very powerful and expressive, it does not have time complexity analysis nor demonstrates a reasonable running time. Note that the brute force method can also resolve the graph isomorphism test, it just takes beyond polynomial times. Hence, merely demonstrating the expressiveness of the method is not satisfactory, especially with the claim of being able to solve a notoriously hard problem (i.e. graph isomorphism test). I would suggest the authors report the running time compared with baseline GNNs. I also wish the authors can compare the time complexity of AMP against the standard message passing framework.

Regarding the experiment section, I find it awkward that there is no single model under AMP framework that can simultaneously do well on all three experiments. In section 5.1 the authors compare AMP-C and AMP-R with baseline methods, where the tasks are synthetic node and graph classifications. However, the authors compare different variants AMP-RNN, AMP-ACT, AMP-Iter…etc with baseline methods in section 5.2 when predicting whether the shortest path of the graph is even or odd. Then on real-world benchmark datasets, the authors only show the result of AMP-RNN. Why do we need so many variants? How do we know that the superior performance of the result indeed mainly comes from AMP instead of these sophisticated and specialized variant designs? Finally, according to the ESAN paper by Bevilacqua et al. 2022, the state-of-the-art results on five tested benchmark datasets are close to ESAN. However, the authors show that GCN can significantly outperform ESAN. I wonder why such an inconsistency exists.

clarity,_quality,_novelty_and_reproducibility: - Clarity: The paper needs an illustrative example to explain how AMP works on the entire graph. The overall clarity can be improved.

- Quality: The method seems to work with improved expressiveness against 1-WL test.

- Novelty: The idea is novel.

- Reproducibility: The authors provide their experimental code which is well-documented. I believe the results can be reproduced.

summary_of_the_review: The authors propose the asynchronous message passing (AMP) framework which seems to resolve many existing issues of standard message passing based methods. The experiment results on synthetic data demonstrate the superior performance of AMP and moderate performance on real-world benchmark datasets. My major concerns of the paper are its clarity and time complexity. Some other concerns pertaining to the experiments are also listed. I hope the authors can elaborate more about the AMP framework and address my concerns listed above. I am happy to raise my score if my concerns are well addressed.

==================post rebuttal========================

I thank the authors' rebuttal. My major concerns are addressed and hence I increase my rating from 5 to 6.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a framework for neural networks on graphs with asynchronous message passing. 

* Strengths are the proposition of an interesting new idea of asynchronous message passing. 
* Weaknesses are high computation cost and inaccuracy of the proposed methods, insufficient experiments, insufficient writing quality. 

During the discussion period the authors could clarify several of the initial reviewer concerns while other items persisted. 

The final reviewer recommendations were mixed borderline with two 6 and two 5. In the final discussion one of the 6 agreed with some of the items from one of the 5 and found significant weaknesses on the computational cost, lack of larger benchmarks, and writing. The authors also acknowledged that the method suffers from computational bottlenecks and that meaningful ranges of hyper parameter values are not yet known. 

I conclude that the paper makes promising advances in an interesting direction but that it still needs to be developed. 



justification_for_why_not_higher_score: The reviewers have suggested several items that could be improved. 
justification_for_why_not_lower_score: NA
Decision: Reject