Flood and Echo: Algorithmic Alignment of GNNs with Distributed Computing

We thank the reviewer for his review and address the raised concerns in the following comments.

It is not clear to me how the computation graph of a single node is constructed in this case. In ordinary GNN, the computation graph is a tree structure, first layer is 1-hop neighbors, second layer is 2-hop neighbors, etc. But I cannot tell how the representation of a single node is computed. If we want the node representation of a node that is not the chosen start node, what is its node representation's computaiton graph?

Indeed, the computation graph of a single node is not straightforward to define as it is in a regular MPNN. In the flooding phase, the update of a single node is influenced by all nodes that lie on the direct path between the node and the starting node. Similarly, in the echo phase, the node embedding is influenced by all nodes for which the node in question lies on the direct path to the root. We have added two more figures in Appendix A which should visualise this and highlight the differences between the two mechanisms.

The flood and echo mainly focused on the forward propagation part. But how its gradient are computed? To compute the gradient for weight parameters, we have to use the “gradient with respect to hidden representations output” and “the input node representation that multiplied to the weight parameters”. In flood and echo, it seems like we have to save the hidden embeddings for each node to compute gradient?

Note that the main difference lies in the node activations order, but the graph convolutions and computations still stay the same in principle. The main difference is that they happen more sparsely and in a fashion that follows the flooding and echo wave pattern. In practice, the mechanism is implemented in pyg which then makes use of automatic differentiation to get the gradients. The embeddings which need to be stored to compute the gradients are the same as for the regular MPNNs.

Compared to ordinary message passing GNN, the major difference if the selection of neighbors and the number of propagation steps (aka the number of layers in GNN). In order to propagate information to the full graph, the proposed “flood and echo” requires twice the propagation steps of ordinary message passing GNN due to echo back. I am not sure I understand this correctly and how this can benefit in terms of efficiency.

So if information should be propagated throughout the entire graph and back, then also a regular GNN would need the same number of propagation steps. The Flood and Echo Net only activates a subset of nodes at each propagation step, so even though the number of propagation steps (in terms of layers) is the same, the number of node updates is significantly less (each node is activated a constant number of times instead of O(D) times) and so is the number of messages required to achieve this.

The "flood" part seems to me is the forward propagation of ordinary GNN, where this GNN's depth is the diameter of the graph? Both the flood and echo are always part of the computation - we have added a new figure in the Appendix A which shows how nodes are activated in the forward pass for both the flood and echo part. A GNN which executes diameter many layers would have a similar reach but with a completely different computation tree (with more updates to every node). We hope this clarification was already helpful, we are not entirely certain what causes the confusion.

What is FloodConv and FloodCrossConv on line 7 & 8 in Algorithm 1?

In the flood and in the echo parts graph convolutions are applied (the FloodConv), in the implementation, we actually differentiate between edges that connect nodes at a different distance from the starting point (edge from a node at distance d to a node at distance d+1) and nodes at the same distance. Edges which connect nodes that remain at the same distance execute the crossconv convolutions.

What is phases stands for on line 5 in Algorithm 1?

One execution of a flood followed by an echo is seen as one phase. The Flood and Echo Net could execute multiple such phases.

We thank the reviewer for his review and address the raised concerns in the following comments.

Regarding W1. Q1) Would the authors be able to give further motivation for the specific design of the message-passing scheme, beyond specific solutions to certain algorithmic problems?

The main inspiration for the architecture is the flooding and echo design pattern often used in the design of distributed algorithms. On a more conceptual level we believe this pattern to be important as it aligns well with searching (flood) for specific information (in the whole graph when the location is unknown) and then gathering (echo) the specific piece of information back to where the search originated. With the main advantage being that the location does not have to be known in advance or be close as the whole graph can be explored. The motivation is that this searching and gathering pattern would be more generally applicable for settings where nodes are reliant on information exchange which could be done in such a query-like fashion.

Regarding W2. Q2) Would the authors be able to provide some comments regarding the over-squashing effect of their model?

Thank you for pointing out this issue - We have included such a discussion on over-squashing in our Appendix. We believe that our objective for information exchange is slightly different from the mentioned over-squashing phenomena. In our work, we try to analyse if information can be facilitated through the graph even if it is far away - where the focus lies on the distance that has to be overcome. Here we implicitly assume that there is no topological bottleneck and the main issue for standard GNNs would be that they have to execute many rounds to even distribute the information in question. We are aware that distance and depth are factors that are important for over-squashing. However, as we understand it, over-squashing mainly becomes an issue if there are (topological) bottlenecks in the graph. In this case, the Flood and Echo Net would also struggle and one probably would have to consider some sort of graph rewiring to alleviate the issue - on this modified (rewired) graph, one could then deploy the Flood and Echo Net.

Regarding W3. Q3) Would the authors be able to provide a reason for why they did not evaluate on existing algorithmic benchmarks such as CLRS-30?

Thank you for pointing out the CLRS-30 benchmark. We would like to test and compare our architecture on the NAR problems that they study in future work. However, currently we see some issues on why we can not apply the Flood and Echo Net. The main obstacle we see is the graph representation of the problems in CLRS. They utilise fully connected graphs as base for their computation, which one side defeats the purpose of Flood and Echo which tries to scale the number of messages sub quadratically. On the other hand, in a fully connected graph, the flood and echo would perform a single activation of all nodes and then echo back. The strengths of the Flood and Echo Net are to exchange information to far away nodes and the mechanism still efficiently generalises to larger graphs - this just does not really make sense if the graph is fully connected as nodes are directly connected and if the graph grows quadratically for larger sizes it cannot be efficient anyway. Lastly, we do hope that we can incorporate some comparisons in the future, as certainly the graph problems which are part of CLRS could be adjusted to make appropriate comparisons. However, as of now there are both conceptual and technical hurdles to overcome in order to perform comparisons in a straightforward way.

Q4) Is the technique designed specifically with only algorithmic tasks in mind or do the authors envision the technique to work on non-algorithmic tasks?

For now we have focused our analysis of the Flood and Echo Net on its ability to be applied in the setting of extrapolation and information exchange. While algorithmic problems might be the most interesting and easily available setting to study these two properties, we could see future work for applying Flood and Echo Net for the benefit of information exchange in other settings. For now, we have focused on the presented problems in our work because they allow rigorous control which allows us to gain theoretical insights on the mechanism of the Flood and Echo Net, i.e. the comparison against the theoretical best performance in Section 5.

If any open questions remain, please do not hesitate to contact us again. We hope we could properly address and incorporate your suggestions. If this is the case, we would be happy if you could consider raising the score.

We thank the reviewer for his review and address the raised concerns in the following comments.

The underlying idea is not new in many perspectives. First, it is studied in rooted subgraph based GNNs, along with distance-to-root feature usage. One can refer to Bohang Zhang's ICML 23 paper. Second, it shares certain similarity to "Agent-based Graph Neural Network". In principle, I feel the author mainly provide another angle of viewing it as kind of execution mechanism of GNNs.

We had a closer look at the mentioned paper, which defines Subgraph GNNs the following way: Subgraph GNNs unifiy the view of GNNs which not only rely on their immediate neighbourhood but across different elements, i.e. which one can capture with subgraphs (multi hop neighbourhood or incorporating distance information). However, I fail to see how exactly one could express the Flood and Echo Net in this framework. Note that in our work, at each given timestep, only a subset of nodes is currently active and updates their node embeddings. Because these activations happen one after another based on the distance to the starting point, this is similar to a wave pattern. Moreover, because these activations (and node updates) happen one after another, information can propagate through the graph following the pattern. The mechanism of a node A which is closer to the starting point updating itself before a node B that is farther away (the updated A embedding might even have an influence on B) is central to the idea of the Flood and Echo Net. We have added an additional Figure in the Appendix A to highlight the execution mechanism more clearly.

Currently we do not see any way of expressing the same dynamics in the framework of subgraph GNNs - and therefore, I believe they are not that closely related. However, we have added an extended paragraph about the connection in the Appendix which discusses subgraph GNNs.

We agree that the paper shares some similarity to Agent-based Graph Neural Networks (AgentNet) in the sense that we propose a different computation mechanism compared to more standard GNNs. Which is also a reason why we mention the paper in our related work section. However, there are important key differences between the two proposed methods. In AgentNet there are a fixed number of agents which traverse the graph structure similar to a learned random walk - whereas in Flood and Echo Net, all nodes (not only where an agent is currently active) perform computations determined by the wave activation pattern.

We think thatFlood and Echo Net goes beyond “another angle of viewing” as it defines a very specific computation flow which is inherently different from standard MPNNs and other execution paradigms such as the aforementioned AgentNet.

The expressivity study/proof is technique-wise simple. Also the author need to discuss the expressivity comparison inside permutation equivalent setting. We don't discuss expressivity for permutation sensitive model as it can achieve universality easily. Hence here the author should focus on Flood And Echo All when discussing expressivity.

We understand the concerns of this particular point. Note, that the execution mechanism for the Flood and Echo Net always stays the same, regardless of the chosen operation mode and our analysis still holds. Moreover, the proposed scheme does not break permutation equivariance, but introduces an additional tie-break in distinguishing the starting node, which is a lot weaker than universality (i.e. by including random features). Finally, note that we provide the expressivity experiments for the Flood and Echo All mode in Table 1. Even in the “all” mode it is more expressive - you can consider the example in Figure 2 where every node (no matter the starting node) can distinguish the two graphs.

We thank the reviewer for his review and address the raised concerns in the following comments.

The implementation of the proposed framework might be complex as it is not supported by the existing graph learning frameworks such as DGL and PyG.

The implementation of the proposed Flood and Echo Net might seem more complex at first than it actually is. The non-trivial part is to ensure the correct message flow, which can be done using proper masking so that the entire model can still run efficiently on the GPU. We have implemented the architecture in PyG and will release the entire code base upon publication.

The computation is more expensive than GNN. Each round of full-graph traverse can only compute one node's embedding.

Note that for all presented modes the execution of a Flood and Echo Net always computes embeddings for all nodes. The difference lies in the chosen starting point and what embeddings you want to keep for the final prediction. For some mode, such as the “all” mode, it might make sense to run an execution for every node as the start once and only keep its own embedding after the run. However, we want to stress that just from a computational point of view an entire phase of the Flood and Echo net is as expensive as a single round of a standard MPNN (using O(m) messages).

This is a curious question. The idea of Flood and Echo is borrowed from distributed computing. Can we apply it to distributed GNN training/inference? What are the benefits we can expect?

The Flood and Echo execution pattern only ever activates a few nodes at a time, maybe this could be leveraged during inference time for more efficiency. If you want to focus on distributed training/inference in the sense of scaling to multiple machines we do not see an immediate connection. In this work, we are mainly inspired by the algorithm design done in distributed computing. For distributed execution on multiple machines we think this concerns a different area of distributed computing.

If any open questions remain, please do not hesitate to contact us again. We hope we could properly address and incorporate your suggestions. If this is the case, we would be happy if you could consider raising the score.