Rethinking Message Passing for Algorithmic Alignment on Graphs

Thank you very much for your responses to my questions! I still have a couple of outstanding clarifications based on my initial points.

My initial comment: "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"

I am not sure that your answer is related to this, but to my point after where I say "Additionally, the choice of node to mark can effect expressivity". My point was that I don't see how the message propagation strategy itself improves expressivity, just that the node marking does (as suggested by Theorem 4.3.). Could you clarify or provide evidence for how the propagation scheme itself contributes to enhanced expressiveness?

Initial comment: "Your method breaks symmetries through the origin node and so may be less beneficial for tasks without this ordering."

Sorry, I think there may be some confusion about what I mean here. I am not saying that "this aspect of the mechanism should be helpful" for the tasks which you use but that for tasks where there is no ordering, it may be harmful. For instance, you can cause two isomorphic graphs to be distinguished by randomly marking nodes in each. The results for "Flood and Echo random" (which seems more relevant for tasks without an ordering?) are underwhelming and don't seem to improve on RecGNN whilst being more computational complex. This led me to wonder about the suitability of the approach for tasks without a fixed ordering.

Your response: "We believe that the FE Net should improve generalisation due to multiple factors. On one side, there is the involvement of the entire graph, without relying on external inputs such as scaling the number of rounds."

Are you saying that you can use "m" rounds of message-passing in the train set to cover the full graph but if the graphs are larger in the test set then you may not cover the full graph with standard MPNN approaches. So you have some dependence on the number of rounds for generalisation? This also relates to my long-range interactions point where I state that we may have under-reaching between two nodes in a large graph if we don't use enough layers for the small training graphs. Have I understood this point correctly? If so, are there practical scenarios where we need to generalise to graphs with vastly different diameters?

"Are there any direct applications for direct graphs that you are considering?"

Not particularly, I was just considering the generality of the approach to a wide range of different graph types. I can see how this method can be adapted in these cases now - thank you.

We thank the reviewer for his insights and will go into the raised points and questions in the following.

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...

In general it is true that a randomised selection policy might not be optimal. One could think of other heuristics (sample upon some graph statistics) or even learn a policy as in the paper you suggested. In our studied context, we found that many tasks yield a natural starting point or tiebreak for an appropriate selection - this might be related to the fact that for many (attributed) graphs the 1-WL expressiveness already suffices. But it would be an interesting future direction to explore if learning the start can improve performance in general.

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’...

We believe that the FE Net should improve generalisation due to multiple factors. On one side, there is the involvement of the entire graph, without relying on external inputs such as scaling the number of rounds. Note that essentially RecGNN does exactly this, but seems to perform worse in comparison. Moreover, FE net only updates the nodes sparsely with few messages throughout the computation - this can allow it to find and redistribute information using fewer updates to the graph, always using O(m) messages to do so.

The mentioned variants of the FE Net don’t perform as good as fixed - this is likely due to the fact that training them is more difficult. We have conducted an ablation to assess this in Appendix G.3 where we find that different models can differ, but within a model there is not as much randomness. However, for many tasks you can find an appropriate choice as a starting node, so this is why we put more emphasis on the fixed variant, and put less emphasis on stabilising the other two modes.

Regarding the reference to [2]: As far as we understood, in this paper they also consider the SALSA-CLRS tasks, however the actual data that is used is not the same. Recall that the FE-Net does not use any hints throughout training. DNAR on the other side cannot do that (outlined in section 6) as they heavily rely on hints during training. Moreover, if we understood the description and code correctly they actually use custom hints closer to their formulation instead of the hints that are included with CLRS/SALSA-CLRS. Whereas we propose an algorithmic alignment of the general message passing architecture and train without any tailored supervision. Therefore, I don’t think the results are at all comparable.

Time comparisons to RecGNN would improve the paper, given that it outperforms your approach on some tasks.

We do provide some timing results in the Appendix. However, keep in mind that the fixed variant of FE Net consistently outperforms RecGNN.

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.

The method does introduce a component of symmetry breaking as nodes are able to figure out the distance to the origin node. As the nodes already have an order, there should be no more symmetries that can be broken. Therefore, we do not see how this aspect of the mechanism should be helpful. But it is likely that we misunderstood the question and we would be glad if the reviewer could clarify their intentions if this is the case.

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.

Long-range interactions certainly are an important aspect, as we involve the entire graph instead of executing a constant number of graph convolutions. However, even if the computation is scaled appropriately for GIN (i.e. RecGNN or on SALSA) the FE Net seems to perform better on these tasks. We would argue that it is more about generalisation as you apply it on larger unseen graphs rather than efficient long-range, which you could study without size generalisation during testing. Moreover, learning general long-range interactions on large graphs might be its own challenge, whereas you could learn a principle on small and generalise the same principle to larger instances and incorporate some long range effects.

We thank the reviewer for his insights and will go into the raised points and questions in the following.

One concern of FENet is over-squashing problem...

Our work does not explicitly aim to address the over-squashing problem, as this is primarily a property of the underlying graph topology rather than the message-passing architecture itself. We also include a statement about over-squasing in the Appendix. Recent work (Giovanni et al., 2023) shows that graph topology is the dominant factor in over-squashing, with architecture choices having a marginal effect compared to bottlenecks in the graph structure. The FE Net's wave-like propagation pattern offers a different approach to information flow, but we acknowledge that fundamental topological bottlenecks would still affect performance. The architecture could potentially be combined with existing approaches that modify graph structure to address over-squashing, but this was beyond the scope of our current investigation which focused on algorithmic alignment of the message-passing mechanism itself.

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.

There is a tradeoff between involving the entire graph and sequential operations. In order to facilitate information exchange across the entire graph, sequential operations are required for our approach. Note that this impacts any approach - even MPNNs require more sequential multiple rounds to achieve similar reach. As a benefit, our wave-like pattern activates only relevant nodes at each step, potentially reducing memory usage compared to simultaneous updates of all nodes. Most importantly, this structured approach with fewer messages enables performance improvements in tasks, as demonstrated by our results on PrefixSum, which aren't achievable with standard (parallel) message passing.

One minor point, please make the tables more readable... We will adjust this, thank you for the input.

Why do you pick FCrossConv to exchange messages between nodes at the same distance?

We include FCrossConv to include the entire graph structure and all edges. While the model could function without these cross-connections (equivalent to FCrossConv having no effect), including them provides flexibility. This allows the model to learn whether and how to utilise these additional connections based on the task requirements.

Why the FConv and FCrossConv are reversed in the echo phase?

We reverse the order in the echo phase to maintain consistency with the overall information flow pattern. Since the echo phase represents information flowing back toward the origin, we thought it to be more natural to first process nodes at the same distance level (ECrossConv) before passing messages inward (EConv), mirroring but reversing the outward flow pattern of the flooding phase.

For fixed mode, how exactly do you design which node to be the origin node?

For the fixed mode, the origin node is determined by the task. In the SALSA-CLRS experiments, we use the starting node provided by the task (e.g., source node in BFS or Dijkstra). When no special node is specified by the task, we default to using the node with id 0 as the origin.

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.

At each individual computation step you have less updates/messages with the FE Net. If you consider an entire phase the number of messages is the same as one round in a standard MPNN. However information has propagated throughout the entire graph - and not just the origin node is influenced by this, but all other nodes (through their update) as well.

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.

As of now we have primarily focused on the setting of algorithm learning on graphs. We thought the generalisation to larger graphs while performing computation throughout the entire graph could be best illustrated in that setting. However, it is true that one could use it in other settings as well instead of regular MPNNs. It is possible that for molecular predictions that have long-range interactions, reducing message complexity through alignment could be of interest. However, how such interactions could be learned directly on large systems (whereas in our setting they are always smaller during training) is still a challenging open research question, so it might not yet be directly applicable.

We thank the reviewer for his insights and will go into the raised points and questions in the following.

I recommend revising the introduction ...

We will revise our introduction and put more emphasis on neural algorithmic reasoning, our intention was to outline the proposed architecture first and then dive into nar on graphs. While our novel take on the message-passing mechanism that could be relevant for general graph learning, this work specifically investigates algorithmic reasoning and size generalisation. As such, application to semi-supervised tasks remains an interesting direction for future work (possibly in the context of NAR), but is not the current focus of this paper

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.

We provide details in Appendix F or in the attached code base, the FE net intends to do a GIN like update step including a GRU. During the experiments the same aggregation was used consistently among the baselines. Regarding expressivity, we believe that Theorem 4.1 should already provide the suggested strengthening. Namely, that FE Net can simulate any MPNN, thus preserving 1-WL expressivity. As such, if the WL test distinguishes two graphs, so should our method. In the case of testing the same graph twice, the origin node needs to be chosen the same in order for the test to succeed.

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.

The reviewer raises an important point about message complexity. Our analysis assumes the standard MPNN setting where messages are passed along in the entire graph, including all edges, leading to O(m) complexity per round. While sampling techniques like in GraphSAGE can reduce this by redefining the graph in question to be limited to a specific subgraph, our comparison focuses on architectures operating on the full graph topology to ensure fair evaluation of algorithmic capabilities. Note, that in principle you could also use the FE Net in combination with these subsampling techniques, then there would be O(m’) messages where m’ = k*d^2 the number of edges in the subgraph.

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.

Extrapolation is a very hard objective and a fundamental challenge in neural algorithmic reasoning. Our results demonstrate that architectural alignment is a viable option to significantly improve generalisation. Another promising indicator of this are the results on MIS (maintaining >80% accuracy at 160 nodes) and the consistent improvement in performance when increasing the number of phases (Figure 7). These findings suggest that our approach of aligning neural architectures with algorithmic principles is a promising direction for improving generalisation, even for tasks not directly aligned.

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.

While our evaluation primarily uses ER graphs following the SALSA-CLRS and CLRS benchmark setup, the full results in Appendix I also include performance across WS and Delaunay graphs. Besides, Distance and PrefixSum is evaluated on Trees and Line graphs, where the latter has very high diameter. As such, we think we already provide a reasonably general and challenging family of graphs. Is there a particular reason to include scale-free networks in the ablations, which might even apply to NAR in general?

Thank you for your detailed rebuttal. I have reviewed it carefully and have decided to maintain my original score.

The paper has several limitations that require further experimental validation. For instance, the use of ER and other small random graphs in the experiments is problematic, as it does not adequately represent a wide range of graph types. Additionally, the proposed method is limited to undirected and connected graphs, which significantly restricts its applicability.

Thank you again for your thoughtful responses.

We thank the reviewer for his insights and will go into the raised points and questions in the following.

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

The architecture seems to perform better where the algorithmic tasks are aligned with the flooding/echo patterns. However, we would like to point out that extrapolation is a very hard objective and a fundamental challenge in neural algorithmic reasoning. Our results demonstrate that architectural alignment is a viable option to significantly improve generalisation. Another promising indicator of this are the results on MIS (maintaining >80% accuracy at 160 nodes) and the consistent improvement in performance when increasing the number of phases (Figure 7). These findings suggest that our approach of aligning neural architectures with algorithmic principles is a promising direction for improving generalisation, even for tasks not directly matching the flooding/echo pattern.

The impact of the algorithm is not clear, which real world use-cases would the proposed approach be the most beneficial for?

While we focus on leveraging algorithmic alignment on algorithmic tasks due to our interest in size generalisation, the concepts of sparse but parallel computation patterns involving the entire graph efficiently could be of independent interest for other applications across graph learning. Especially in dealing with long-range interaction systems, reducing message complexity through alignment could be of interest. However, how such interactions could be learned directly on large systems (whereas in our setting they are always smaller during training) is still a challenging open research question.

What is the dependency of the proposed method to the chosen origin node?

We have conducted an experiment in Section G.3, Table 8 to assess the effect of the origin node. Our analysis shows that while random starts lead to some training instability, as not all models achieve perfect accuracy. However, individual trained models show consistent performance with narrow deviations across 50 runs on 1000 graphs.