Rethinking Message Passing for Algorithmic Alignment on Graphs

Authors: Joël Mathys, Florian Grötschla, Kalyan Varma Nadimpalli, Roger Wattenhofer
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Algorithm Learning, Message Passing

Abstract:
Most Graph Neural Networks are based on the principle of message-passing, where all neighboring nodes exchange messages with each other simultaneously. We want to challenge this paradigm by introducing the Flood and Echo Net, a novel architecture that aligns neural computation with the principles of distributed algorithms. 
In our method, nodes sparsely activate upon receiving a message, leading to a wave-like activation pattern that traverses the graph. Through these sparse but parallel activations, the Net becomes more expressive than traditional MPNNs which are limited by the 1-WL test and also is provably more efficient in terms of message complexity.
Moreover, the mechanism's ability to generalize across graphs of varying sizes positions it as a practical architecture for the task of algorithmic learning. We test the Flood and Echo Net on a variety of synthetic tasks and find that the algorithmic alignment of the execution improves generalization to larger graph sizes. Moreover, our method significantly improves generalization and correct execution in terms of graph accuracy on the SALSA-CLRS benchmark.

Decision: reject
Reviewer scores: 5, 3, 6, 5

Reviews and discussion:
<thread>
creation date:
1729511894278

thread_type:
official_review

<thread_object>
creator: reviewer_tssr

<content>
summary:
The authors propose a novel mechanism where messages are propagated outwards from an origin node and then back to the node. This is shown to be more expressive than 1-WL and have less memory complexity than standard MPNNs. The authors then demonstrate through experiments that the method can generalize better to larger graph sizes on some tasks.

strengths:
To my knowledge, the mechanism is novel and using an origin node relates to other methods (eg. Subgraph GNNs) whilst the propagation mechanism is more efficient. Seeing this approach will be beneficial to the community and could impact other areas outside algorithmic alignment such as improving long-range interactions. 

The paper is well-written and the memory complexity and expressivity improvements are argued with diagrams, text and theorems. It is very clear what the contributions and goals of the method are and many experiments have been run to ablate the model.

weaknesses:
[Enhanced Expressiveness]

The paper says that the enhanced expressiveness comes from the ‘unique message propagation strategy’ and the ‘structured activations of the nodes’. However, Theorem 4.3 suggests that the expressivity improvements comes purely from marking a node. Therefore, the expressivity advantages from the actual propagation scheme is not actually shown. Could you clarify or provide evidence for how the propagation scheme itself contributes to enhanced expressiveness? Additionally, the choice of node to mark can effect expressivity and randomly choosing a node can be suboptimal [1] - this may be an issue when the task doesn't align with a specific choice of node. 



[Generalize to large graph sizes]

Firstly, the theoretical argument for improved generalization isn’t convincing. You argue that the new message-passing scheme is more natural ‘as the computation inherently involves the entire graph’. You could increase the neighbourhood size of standard message-passing to the whole graph (eg. Graph Transformers). It is not clear that this would improve generalization (it should perform worse without positional encodings), so what specific aspects of the architecture contribute to improved generalization, beyond just involving the entire graph? Secondly, the experimental section isn’t convincing. For example, your method improves on PrefixSum (this is a path graph which means all nodes interact in your scheme) but [all, random] are worse than RecGNN on the other two tasks. Additionally, your method is only better than **old baselines** on **some** of the SALSA-CLRS tasks. This is in contrast to concurrent work [2] that seems to solve these tasks [I don’t expect a comparison to concurrent work but it does suggest that the improvement of your method is not substantial].

[Minor Weaknesses]

- Paper is limited to size generalization and does not account for other factors such as change in connectivity distributions.
- Time comparisons to RecGNN would improve the paper, given that it outperforms your approach on some tasks.
- The benchmarks chosen seem to have a natural ordering of nodes. Your method breaks symmetries through the origin node and so may be less beneficial for tasks without this ordering.

questions:
- GIN will struggle to solve tasks that require long-range interactions due to over-squashing and under-reaching. For example, for path graphs of size 100, you may need a large number of layers so that two nodes interact. If your method improves over GIN on unseen larger graphs - does that actually imply that it is better at generalizing?  (Given that GIN won’t be able to solve the task on these larger graphs even when they are in the training set). To me, it is less about generalization and more about efficient long-range interactions.
- Is your method easily parallelizable? Although message complexity may be less it is not clear to me that this method would have a favorable runtime.
- How would your method work with directed or disconnected graphs? Wouldn’t this mean that some nodes will never receive information from other nodes. Additionally for Theorem 4.2, as well as being connected, do you not also need the graphs to be undirected? For example, a path graph where the direction of the edges is the same way. If I pick the last node as the origin node then would I be less expressive (I guess depends on the implementation)?

[1] Efficient Subgraph GNNs by Learning Effective Selection Policies. Bevilacqua et al. ICLR 2024. 

[2] Discrete Neural Algorithmic Reasoning. Rodionov et al.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729606711579

thread_type:
official_review

<thread_object>
creator: reviewer_o8qp

<content>
summary:
This work proposes a framework, Flood and Echo network (FENet), which breaks the synchronous limit of MPNNs. Theoretically they prove that FENet has higher expressivity than 1WL. Empirically they show great performance of FENet on three algorithmic alignment tasks.

strengths:
- Overall, the idea is pretty interesting and highly novel. 
- The writing is clear and good, also the illustrations make sense for understanding the framework. 
- The theory is sound.
- The performance of FENet is validated in experiment part.

weaknesses:
- One concern of FENet is over-squashing problem. The sensitivity of a node to the original node is unclear, the message from the origin node pass out to the furthest nodes, then gathered back, the over-squashing issue on large graph may not be solved, even aggravated. 
- Though the theoretical runtime complexity is the same as MPNN, the messages are executed in sequence, while in MPNN it is in parallel. Modern GPUs can handle large batches of data executed in parallel, but this sequential property of FENet might make it super slow on GPU, especially with a lot of phases. 
- One minor point, please make the tables more readable, for example, highlight the best candidate in the table, so it is clearer to readers. 
- Some design details are not quite clear to me. See questions below.

questions:
- Why do you pick FCrossConv to exchange messages between nodes at the same distance?
- Why the FConv and FCrossConv are reversed in the echo phase?
- For _fixed_ mode, how exactly do you design which node to be the origin node? 
- The authors claim FENet message passing is more efficient. If I understand correctly, in a whole phase, the number of node updates as well as messages conveyed are not reduced. It's just the origin node is able to reach further neighbors in a phase. 
- Is there a reason why you evaluate the framework on algorithmic alignment? Certainly it performs well, but it can also be a general framework for other tasks, say molecular prediction etc.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730582075101

thread_type:
official_review

<thread_object>
creator: reviewer_9tnp

<content>
summary:
This paper introduces a message-passing graph neural network called Flood and Echo Network (EF Net). The message-passing structure mimics a breadth-first traversal (BFS) starting from a source node. The authors demonstrate that EF Net is more expressive than traditional MPNNs, which are limited by the 1-WL test, and is also provably more efficient in terms of message complexity. Applied to the SALSA-CLRS benchmark, EF Net shows improvements in generalization and correct execution, achieving higher accuracy on this benchmark.

strengths:
1.	This paper introduces a message-passing neural network that operates similarly to a breadth-first traversal, requiring O(m) messages, where m is the number of edges in the graph. For many tasks evaluated, FE Net requires fewer messages compared to several other APNN models.
2.	The authors demonstrate that FE Net can be more expressive than standard APNN models, particularly in the context of the Weisfeiler-Lehman (WL) test performance.
3.	The paper evaluates FE Net on a subset of tasks from the SALSA-CLRS benchmark using randomly generated ER graphs. According to this benchmark, FE Net shows improved generalization compared to GIN and other APNN models.

weaknesses:
1.	I recommend revising the introduction to clarify that the paper specifically focuses on "neural algorithmic reasoning on graphs." While the title mentions this, the introduction could be clearer, as it currently suggests a focus on general graph learning. Additionally, there is no evidence provided that FE Net outperforms MPNNs on typical supervised or semi-supervised tasks, such as node classification and link prediction.
2.	The exact aggregation and update operations used in FE Net are not clearly discussed. For instance, GIN has been shown to be more expressive with sum pooling as the message aggregator. To establish the expressiveness of FE Net, it would be beneficial to specify these operators explicitly. Furthermore, Theorem 4.2 could be strengthened by showing that FE Net does not fail in cases where the 1-WL test succeeds, in addition to distinguishing graphs where the 1-WL test fails.
3.	Some assumptions in the paper require further clarification. For instance, it seems to assume that a typical MPNN exchanges O(m) messages per layer, where m is the number of edges. However, the actual number of messages depends on the computational graph. If there is a batch of k nodes with an average degree of d, a 2-layer GCN will involve O(kd^2) messages. Additionally, models like GraphSAGE use sampling to reduce message volume, so O(m) messages per layer may not apply to most APNNs.
4.	FE Net operates similarly to a BFS traversal, where nodes at the same distance from the source are processed together. Given that the algorithms studied also use BFS-like traversal, it is unsurprising that FE Net outperforms some other GNN models. It is unclear, however, how FE Net would perform with algorithms that don’t resemble BFS, as FE Net (and other GNNs) struggled with generalizing to tasks like DFS and MST.
5.	Most of the experiments in the paper are conducted with Erdős-Rényi (ER) graphs, which may not fully represent practical graph structures. Showing results on scale-free graphs or real-world graphs could provide more comprehensive insights into FE Net’s performance.
6.	Since FE Net begins from a source node and reaches all nodes in a connected component, it is unclear how it would handle graphs with multiple connected components. Providing a discussion on this aspect would improve understanding of FE Net's applicability to such cases.

questions:
1.	Do the authors have any insights on how EF Net performs on scale-free graphs?
2.	Can EF Net be applied to semi-supervised learning tasks, such as node classification?
3.	Is EF Net suitable for non-BFS style algorithms, like clustering or triangle counting?
4.	What specific aggregation and update operations are employed in EF Net?
5.	How is it ensured that EF Net does not fail in cases where the 1-WL test succeeds?
6.	In the experiments with GIN, how many layers were used?
7.	Does EF Net's performance decline when applied to high-diameter graphs, such as road networks?
8.	How does EF Net handle graphs with multiple connected components?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730704231847

thread_type:
official_review

<thread_object>
creator: reviewer_hdvf

<content>
summary:
The paper proposes the flood and echo algorithm, that simply works by selecting an origin node, sending messages outward from this node. When the messages reach the end of the graph when centered at the origin node, they reflect back and trace the same path back to the origin node. It is theoretically proven that for the distance, path-finding and prefix sum tasks, the proposed model is a perfect fit.

strengths:
* The proposed approach is theoretically and empirically validated.
* The paper is well written.
* There are other algorithmic tasks in the experiments than the ones tailored to the proposed approach.

weaknesses:
* The proposed algorithm does not generalize to other algorithmic tasks as well as the tasks it is designed for.

questions:
* The impact of the algorithm is not clear, which real world use-cases would the proposed approach be the most beneficial for?
* What is the dependency of the proposed method to the chosen origin node?
</content>
</thread_object>

</thread>


Metareview:
metareview:
**(a) Scientific Claims and Findings:**
The paper introduces the Flood and Echo Net, a novel architecture that aligns neural computation with distributed algorithm principles. Unlike traditional Graph Neural Networks (GNNs) that rely on simultaneous message-passing among neighboring nodes, this method employs sparse activations upon message receipt, creating a wave-like activation pattern that traverses the graph. This approach enhances expressiveness beyond the limitations of the 1-WL test and improves message-passing efficiency. The architecture's ability to generalize across graphs of varying sizes makes it suitable for algorithmic learning tasks. Empirical evaluations on synthetic tasks demonstrate that the Flood and Echo Net's algorithmic alignment improves generalization.

**(b) Strengths:**
* Innovative Approach: The introduction of sparse, wave-like activations in GNNs offers a novel method for information propagation, potentially overcoming limitations of traditional message-passing mechanisms. Multiple reviewers appreciate the high novelty.
* Enhanced Expressiveness: By aligning neural computation with distributed algorithm principles, the Flood and Echo Net demonstrates increased expressiveness, surpassing the constraints of the 1-WL test.
* Scalability: The architecture's ability to generalize across graphs of varying sizes positions it as a practical solution for algorithmic learning tasks involving diverse graph structures.
* Validation: The method's effectiveness is supported by empirical results on synthetic tasks and the SALSA-CLRS benchmark.
* Presentation: The paper is well written and understandable.

**(c) Weaknesses:**
* Computational Efficiency: The paper does not provide a detailed analysis of the runtime of the Flood and Echo Net, particularly concerning large-scale graphs. 
* Theoretical Justification: While the paper introduces a novel architecture, it lacks a comprehensive theoretical analysis explaining why the sparse, wave-like activation pattern leads to improved generalization performance (beyond just using the whole graph according to Reviewer ), which would strengthen the understanding of the method's advantages.
* Comparative Analysis: The paper would benefit from a more detailed comparison with existing GNN architectures to clearly highlight the advantages and potential limitations of the proposed approach.
* Real world impact/application relevance: The real world application use cases are unclear. The authors have proposed long-range benchmarks but have not conducted related experiments. The experiments are limited to unrealistic graph structures (mostly ER graphs).
* (Minor) Limitations: The approach is limited to undirected and connected graphs.
* Parallelisation potential and potential of memory reduction should be discussed and quantified/analyzed in the paper (and not only the rebuttal).
* Raised concern (Reviewer tssR): Performance of method unclear on tasks where an origin node is not easily defined.

**(d) Reasons for Rejection:**
After careful consideration, the decision to reject the paper is based on the following reasons:
1. Insufficient Computational Analysis: The lack of a detailed examination of the Flood and Echo Net raises concerns about its practical applicability to large-scale graphs and the generalization performance on real world tasks.
2. Need for Comparative Evaluation: A more thorough comparison with existing state-of-the-art GNN models is necessary to substantiate the claimed improvements and to position the proposed method within the current research landscape. In particular, a comparison with other approaches that are more expressive than 1-WL would support the story of the paper.
Addressing these concerns would enhance the paper's contribution to the field and its potential for acceptance.