Asynchronous Message Passing: A new Framework for Learning in Graphs
Authors: Lukas Faber
Roger Wattenhofer
Venue: Submitted to ICLR 2023 (2023)

Abstract: This paper studies asynchronous message passing (AMP), a new framework for applying neural networks to graphs. Existing graph neural networks (GNNs) use the message passing framework which is based on the synchronous distributed computing model. In traditional GNNs, nodes aggregate their neighbors in each round, which causes problems such as oversmoothing and expressiveness limitations. On the other hand, our AMP framework is based on the \textit{asynchronous} model, where nodes react to messages of their neighbors individually. We prove (i)  AMP is at least as powerful as the message passing framework, (ii) AMP is more powerful than the $1-$WL test for graph isomorphism, an important benchmark for message passing GNNs, and (iii) conceptually, AMP can even separate any pair of graphs and compute graph isomorphism. We experimentally validate the findings on AMP's expressiveness, and show that AMP might be better suited to propagate messages over large distances in graphs. We also demonstrate that AMP performs well on several graph classification benchmarks.

Under review as a conference paper at ICLR 2023
ASYNCHRONOUS MESSAGE PASSING: A NEW FRAMEWORK FOR LEARNING IN GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper studies asynchronous message passing (AMP), a new framework for applying neural networks to graphs. Existing graph neural networks (GNNs) the message passing framework which is based on the synchronous distributed com- puting model. In traditional GNNs, nodes aggregate their neighbors each round, which causes problems such as oversmoothing and expressiveness limitations. On the other hand, our AMP framework based on the asynchronous model, where nodes react to messages of their neighbors individually. We prove: (i) AMP is at least as powerful as the message passing framework, (ii) AMP more powerful than the 1-WL test for graph isomorphism, important benchmark for message passing GNNs, and (iii) in theory AMP can even separate any pair of graphs and compute graph isomorphism. We experimentally validate the findings on AMP's expressiveness, and show that AMP might be better suited to propagate messages over large distances in graphs. We also demonstrate that AMP performs well several graph classification benchmarks.
INTRODUCTION
Graph Neural Networks (GNNs) have become the de-facto standard model for applying neural networks to graphs in many domains (Bian et al. 2020 Gilmer et al., 2017 Hamilton et al.) 2017]] Jumper et al. 2021 Kipf & Welling 2017/ et 20118 Wu al.) 2020). Internally, nodes in GNNs use the message passing framework, i.e., nodes communicate with their neighboring nodes for multiple synchronous rounds. We believe that this style of communication not always ideal. In
GNNs, all nodes speak concurrently, and node does not listen to individual neighbors but only to an aggregated message of all neighbors.
In contrast, humans politely listen when neighbor speaks, then decide whether the information was relevant, and what information to pass on. The way humans communicate in line with the asynchronous communication model (Peleg) 2000). In the asynchronous model, nodes do not communicate concurrently. In fact, node only acts when it receives a message (or when initialized). If a node receives new message from one of its neighbors, it updates its state, and then potentially sends message on its own. This allows nodes to listen to individual neighbors and not only to aggregations. Iillustratte how this interaction can play out.
am an H
H
An H? Not interesting to me
I am an
H
OH! have noighhor
H
Then this is an alcobol
Figure 1: Detection of an alcohol (a C atom with OH group) with AMP. H atoms learned to initially send a message to their neighbors. Every node can choose to ignore the message or react to it. The C atom is not interested in H neighbors and discards the message. On the other hand, the O atom reacts and sends a message on its own. This message is now relevant to the C atom.

---

Under review as a conference paper at ICLR 2023
We make the following contributions.
We introduce AMP, a new framework for learning neural architectures in graphs. Instead of nodes acting synchronously in rounds, nodes in AMP interact asynchronously by exchanging and reacting to individual messages.
We theoretically examine AMP and prove that the AMP framework least as powerful as the synchronous message passing network. Furthermore, we show that AMP can separate graphs beyond the I-WL. test; conceptually AMP can solve graph isomorphism.
We examine how AMP can transmit information to far-away nodes. Since AMP handles messages individually and is not limited by the number of communication rounds, AMP can combat the underreaching, oversmoothing, and oversquashing problems that traditional GNNs encounter when propagating information over long distances (many layers).
We run experiments on (i) established GNN expressiveness benchmarks to demonstrate that AMP outperforms all existing methods in distinguishing graphs beyond the 1-WL algorithm. We introduce (ii) synthetic datasets to show that AMP is well suited to propagate information over large distances. Finally, we study (iii) established graph classification benchmarks to show that AMP performs comparably to existing GNNs.
2 RELATED WORK
Apart from some domains with special graph families (for example processing directed acyclic graphs sequentially (Amizadeh et al. (0188), virtually all GNNs follow the synchronous message passing framework of distributed computing, first suggested by Gilmer et al. (017)) and [Bttagha et al. (2018). The underlying idea is that nodes have an embedding and operate in rounds. In each round, every node computes a message and passes the message to every adjacent node. Then, every node aggregates the messages it receives and uses the aggregation to update its embedding. There exist variations of this framework. For example, edges can also have embeddings, or one can add global sharing node allow far away nodes to directly share information (Battaglia et al. 2018). Following the initial work of Scarselli et al. (2008), different implementations for the individual steps in the message passing framework exist, e-g.. (Brody et al., 2022] Hamilton al. 2017 Kipf &
Welling, 2017 7 Niepert et al.) 2016) Veličković et al. 2018 Xu et al. 2018 2019). However, these
GNN architectures all experience common problems:
Oversmoothing, A problem that quickly emerged with GNNs is that we cannot have many GNN layers (Li et al. 2019 2019) Each layer averages and hence smooths the neighborhood information and the node's s features. This effect leads to features converging after some layers (Oono & Suzuki
2020), which is known as the oversmoothing problem. Several works address the oversmoothing problem, for example by sampling nodes and edges to use in message passing (Feng et al. 2020
Hasanzadeh et al. 2020; Rong et al., 2020), leveraging skip connections (Chen et al. 2020b Xu
et al. 2018), additional regularization terms (Chen et al. 2020a Zhao & Akoglu 2020 Zhou
et al. 2020). Thanks to its asynchrony, AMP does not average over neighborhood messages. This
helps preserving the identity of individual messages and makes AMP more resilient against the oversmoothing problem.
Underreaching, Using normal GNN layers, a GNN with layers only learns about nodes at most hops away. A node cannot act correctly if it would need information that is k + hops away. This problem is called underreaching (Barceló et al. 2020). There exist countermeasures, for example, having global exchange of features (Gimer et al. 2017 Wu et al. 2021) or spreading information using diffusion processes (Klicpera et al.) 2019: Scarselli et al. 2008). Methods that help against oversmoothing are usually also applied against underreaching since we can use more layers and increase the neighborhood size. In AMP, because of asynchrony, some nodes can be involved in the computattin//ommmuicaaii much more often than others; this helps AMP to gather information from further away, which is a countermeasure against underreaching.
O Oversquashing, In many graphs, the size of hohop neighborhoods grows substantially with k. This requires squashing more and more information into a node embedding of static size. Eventually, this leads to the congestion problem (too much information having pass through bottleneck) that is well known in distributed computing (c.g. (Sarma et al. 22012) and goes by the name of oversquashing for GNNs (Alon& & Yahav 2021 Topping al. 2022). One approach to solve oversquashing is
2

---

Under review as a conference paper at ICLR 2023
introducing additional edges that function shortcuts to non-direct neighbors (Brüel Saaiel--bbrelssoon et al., 2022). Dropping- baaen methods (Feng et al., 2020; Hasanzadeh et al. 2020 Rong et al. also reduce oversquashing by reducing the size of the neighborhoods. AMP is more resilient than synchronous GNNs. The GNN aggregation step is prone to bury a relevant message in background noise, whereas AMP will see this message in isolation.
2020 that help against oversmoothing
1 1-WL Limit. Xu et al. 2019) and Morris et al. (0019) show that GNNs are limited in their expressiveness by the Weisfeiler-Lehman test (1 WL), heuristic algorithm to evaluate graph isomorphism (Shervashidze et al. 2011). However, there exist simple structures that the 1 1-WL test cannot distinguish that we want to detect with GNNs (Garg et al.] 2020). Therefore, several augmentations to GNNs exist that include additional features, such as ports. IDs. or angles between edges for chemistry datasets (Gasteiger et al. 2020; Loukas 2020; Sato et al. 2019: 2021), run multiple rounds over slight perturbations of the same graph (Bevi lacqua et al. [022 Papp et al. [02T]] Vignac al. 2020), or use higher-orde information (Chen et al. 2019 Maron et al. [209 Morris iet al., 2019). Since in AMP, nodes do not act at the same time, they can be distinguished more easily, We show that AMP can handle 1- WL and higher order WL, in principle even graph isomorphism.
We believe these four classic GNN problems have their root cause in the synchronous aggregation of (almost) all neighbors. The aggregation smooths the neighborhood features, and nodes are exposed to all the information in their increasing k hop neighborhood. This limits the number of rounds, causing underreaching. If nodes with identical neighbors act synchronously, they stay identical and within WL expressiveness. A recent work by [Schaefer et al. (2022) employs some asynchrony to decide which nodes in the graph require processing but node updates are still done in a synchronous fashion. We believe that only full asynchrony with individual processing of messages can yield all the advantages.
Interestingly. a similar observation was made the field of probabilistic graphical models. Elidan et al. (2012) discuss that one method, called belief propagation, often does not converge or converges slowly when every node in the graphical model communicates synchronously. The authors then show that asynchronous computation, processing one node at time can lead to better results. Knoll et al. (2015) and Aksenov et al. (2020) build on these results and improve the asynchronous model with improved message scheduling.
There are two main approaches for distributed computing (Peleg) 2000 Wattenhofer 2020). In the synchronous approach, all nodes operate in synchronous rounds, and in each round every node sends a message to every neighbor. |Sato et al. (2019) and Loukas (2020) show that current graph neural networks using message passing as in Gilmer et al. (2017) follow this approach. The antipodal paradigm in distributed computing is the asynchronous model Peleg (2000). In the asynchronous model, nodes do not act at the same time. Instead, nodes act on receiving single message. If receiving a message, a node may change its internal state and potentially create new messages itself. Currently, all GNN approaches follow the synchronous message passing model. In this paper, we want to explore the efficacy of asynchronous message passing. So we ask a natural question: Is it possible, and is it worthwhile for GNNs to handle messages asynchronously and individually?
3 THE ASYNCHRONOUS FRAMEWORK
We outline the asynchronous framework through the pscudo algorithm in Algorithm 1 The algorithm describes how AMP computes representations for each node in given graph G and node features X. AMP treats every message individually, and as such (in principle) no information is lost in aggregation. However, asynchronous messages can be scheduled in different ways, which is a challenge for the learning process. Generally messages incur a delay before they arrive. We track all messages that are sent but not yet received with their delay in a priority heap. From here, messages are processed on at time. AMP delivers the message to the receiving node which executes three steps: (i) The receiving node can decide that the message is not interesting and discard it; (ii) The receiving node updates its state and computes new message; (iii) The message is sent to each neighbor, by sending the messages with a delay sampled from a distribution D.
There are three major turning knobs in the AMP framework. First, we can vary heap initialization. For example, we can send an initial message to just one node (c.g., when finding shortest paths from this node), send an initial message all nodes, or execute one run for each node, where this node is
3

---

Under review as a conference paper at ICLR 2023
the sole starting node. Second, choose from different delay distributions D: The two main cases are constant versus random delays. Third, we can choose how to implement the three neural blocks: (i) the reaction block p whether to discard a message; (ii) the state transition function 6; and (iii) the message function ja.
Algorithm 1: AMP representation learning with single run and single starting node.
Input: Graph G, node features matrix m.X, bool poolNodes
Output: Graph representation if poolNodes, otherwise node representations.
# Triples (delay: message, node), sorted by delay # Sa Sageurdd against infinite loop g. a message to all node, one single node while not heap.empty() and receivedCount < k do delay, message, receiver gheap.extratMMing if receiver)) message) then receivedCount++
heap MinHeap()
receivedCount 0
initializeHeapO)
# for constant k
# p does not discard message
state[receiver] ((state(receiver) message)
# update node state
new Message p pu(state(receiier), message) for (.neighborr((recevvver) do heap.insert(delay + d~ D, newMessage. v)
11
At this point, states contains representation per node 12 H StackToMarrixssateee) if poolNodes then
Combine node states to matrix
14
H == (H)
Pool for graph classification.
Otherwise use H as is for node classification.
18 return H
3.1 AN AMP EXAMPLE RUN
want to illustrate the pseudocode of Algorithm a an example. We are picking up the example graph from Figure I in the introduction. This time make communication follow the AMP framework closely, each frame depicts one iteration the while loop. The left side of each frame shows the current status of the heap of unreceived messages. The top message in the heap is processed. In our example, node C receives the initial mesage. In the top left picture, C' reacts to the starting message each of its neighbors. The first one receive this message is the
message and sends Il on the top in the second frame and replies. Next, the O atom receives the message from C' in the top right frame. As part of the state update this O can remember it received message from a C. Since COH groups form alcohols, O now needs to find out if its other neighbor is an H. However, the next received message the bottom left frame is receiving the reply from H. This does not give any important information to C and it discards the message. In the next frame, the rightmost H receives the message from O. This H already knows that there a COH group. the next frame the O also learns. At this point the while loop keeps iterating until some point. This example is graph classification problem, so the states of and the right H can contribute to classifying the graph as alcohol, while other nodes might not know, In Appendix A we give some more intuition about AMP by comparing to soaueenc-to-sqqueee models from NLP and show some concrete example architectures, i.e., how one could realize p. μl and 8.
3.2 COMPARING AMP TO GNNS
Complexity. Let analyze complexity on the directed graph G' with n nodes. We compare the complexity of a GNN with | layers and AMP with a limit of k messages. These are usually constant size so we will skip them in our analysis. Computing messages to send and node updates is usually done through constant-sized neural functions. Therefore, we measure complexity by the total number of messages and node updates. For this analysis we investigate GNNs with a fixed number of layers (unlike BerGNN(Tang al. 20200) and AMP variants without message discarding (unlike AMP-iter)
4

---

Under review as a conference paper at ICLR 2023
Daay Snake Revevvrr
Daky Soake Rocever
Delr Soaka Rociver
D
15
Duka
i
Doka
You, Lanan
13
14
Oi the da knaelebee)
Figure 2: Step-by-step example of AMP the detection of a COH group. The Figure shows six frames, each showing the processing of a different message. The left hand side of each frame shows the current message queue, while the right hand side show the recipient reacts to the current message. The current message is the top message on the left.
To compute forward pass in the GNN every layer computes one message per edge and one node update per node. If maa is the maximum degree of a node, we compute O(nAmar) max) many messages and ((n) node updates. Some GNNs, such as ESAN (Bevilacqua al. 2022). computes [S] many runs, where |S| is possibly Onn). The total complexity of ESAN is O n man).
). On the other hand DropGNN (Papp et al., 2021), performs r many runs with a complexity of O(rnAmaz).
In a single AMP run, we compute k messages and each message leads to node update. As part of the node update a node sends up to Amaz many messages to its neighbors. However, to produce expressive representations,
usually do (n) (comparable to SMP(Vignac et al. 2020 or (Bevilacqua et al., 2022)) such runs which originate form different nodes. Overall, AMP sends
O(n moz messages and does (n) node updates.
Expressiveness. AMP and GNNs both compute latent representations for nodes that we can use for
learning a downstream task through a readout function. Instead running AMP as in Algorithm [ we also could have used message passing graph neural network to learn representation of the
nodes or graph. The question lends itself when we should use AMP and when a GNN. For the GNN, assume& message passing neural network following the framework of Gilmer et al. (2017) that operates in rounds and computes the following in each round: Nodes compute message based on their current representation and send these to all their neighbors. Then, nodes update their state based on the aggregation of the received messages and their previous state.
m. MESSAGE(bw)
hut1 UPDATE
(
Σ m.)
vEN(u)
Our first main result is that AMP can compute every node representation that the message passing framework can compute.
Theorem 3.1. Let G be a graph with node features X. Let G be a message passing neural network that produces node representations 2 for every node v at every layer I. We can create an AMP network Ag that, for every G, X,,,, can compute the exact same representations that does. AMP also consciously reaches these representations and use them. We say that Ag simulates G since we could plug AMP into any task requiring the message passing GNN and use AMP its stead.
We attach the proof in Appendix B.I We start from the a synchronizer from Awerbuch (1885) and show that we can create a similar synchronizer in the framework of Algorithm While we did not consider edge features and or embeddings here, the proof can easily be extended to allow these as well. Similarly, by the framework of Battaglia et al. (2018). Similarly AMP can also simulate GNNs that use other permutation invariant aggregation functions.
can include global node. Therefore AMP can also simulate GNNs captured
5

---

Under review as a conference paper at ICLR 2023
4 EXPRESSIVENESS OF AMP
4.1 GENERAL ANALYSIS OF AMP'S EXPRESSIVENESS
Lemma 4.1. AMP is at least as powerful as the 1 WL test.
Proof. This observation follows from Theorem 3.1 GIN (Xu et al. 2019) is message passing neural network that is exactly as powerful as the 1- WL test. This means that GIN can compute representations to separate 1 WL separable graphs. We now know that AMP can simulate GIN and compute the same representations and use them to separate the same graphs.
Lemma 4.2. Let u be a node in cycle of length k starting an AMP execution. All nodes in the cycle can learn that they are in cycle and its length k.
We supply the proof in Section B.2 Basically, AMP searches from both ends of the cycle and counts until the searches meet. The cycle length is the sum of the counts. As a consequence, AMP can separate the two constructions from Garg et al. (2020) that we depict in Figure Bbyby deciding whether or not the graph has cycle of length 8. By learning the graph has a 3- cycle using only one blue node, AMP can also separate the graph in Figure 3c
Lemma 4.3. Let e be a node in k + clique with nodes W1, "2,.... Wik starting an AMP execution. All nodes can learn that they are in a k clique.
We supply the proof in Section B.3 In the proof, the nodes iteratively find out that they are in 1, 2. + cliques by waiting for confirmations at each step. As a consequence, AMP can separate the rook and shrikande graphs (rook graphs have 4-clique while shrikande graphs do not), which are not even separable by 3 WL (Chen et al. 2019).
Corollary 4.4. AMP can separate graphs that are harder than the 1W V-- test.
(a) Taken from Xu al. 2019)
(b) Taken from Garg et al. 2020
(c) From (Papp et al. 2021 added node.
Figure 3: a) Graphs that cannot be distinguished by WI. GNNs using max aggregation. However, the both graphs have a different number of blue nodes responding when the central white node sends message. AMP handles messages separately and can separate the graphs. Graphs in b) and c) cannot be separated by any I GNN but by AMP which can count cycle lengths (Lemma
4.2 AMP WITH RANDOM MESSAGE DELAYS
Let us revisit the example in Figure 3c and suppose we start on the red node. Therefore, we cannot use Lemma 4.2 since the node is not part of the cycle. In case of constant message delays, both blue neighbors receive messages at the same time. Then all white nodes receive messages at the same time and ultimatively we cannot separate the graphs. On the other hand, if delays random, one blue node can receive and send a message to the other blue node while that node has not yet received a message from the red node. This "slower" blue node will not act, and the "faster" blue node checks for 3- cycle. This example illustrates that delays can act as a symmetry breaker and benefit expressiveness. Let us understand the benefits in a star graph:
Lemma 4.5. AMP with random message delays can create unique identifiers (IDs) for every node in a star graph.
We provide a proof Lemma 4.5 in Appendix B.4 In principle, the central node auctions IDs to the star nodes and restarts offering ID when two more nodes claim the ID at the same time. We can generalize this proof from star graphs to arbitrary connected graphs. We start with an arbitrary node that assigns IDs in its 1- hop neighborhood (a star graph). Next, the node with the next-highest ID repeats the process - skipping nodes that already have an ID. Eventually every node adjacent to a center node and received an IDD. The algorithm stops when every node tried assigning IDs and finding

---

Under review as a conference paper at ICLR 2023
successor is not possible. We can further extend this scheme to unconnected graphs by adding master node that is connected to every node. We can conclude:
Corollary 4.6, AMP with random message delays can create IDs in arbitrary graphs.
We can now define the expressiveness of AMP with random message delays.
Theorem 4.7. Given two connected graphs G1, G2 that connect via node to a graph G and diameter 8g, AMP with random message delays that has a width in O(+!) can solve graph isomorphism for any graphs G2, G2 simulating an appropriate GNN for 8g many rounds.
We proof this theorem in Appendix B3.5 We use Lemma 4.5 to assign IDs and Theorem 3. to
simulate a powerful GNN from Loukas| (2020). Despite this theoretical results, we found that AMP with constant delays works practically better and is casier to train. With constant delays, nodes receive the same messages in the same order across different runs, making for stable gradients. On the other hand, random message delays can produce different embeddings for the same graph, so it takes many representative distribution of embeddings to produce a stable gradient signal.
5
EXPERIMENTS
5.1 BEYOND 1-WL CLASSIFICATION
We experiment with AMP's ability to classify graphs that the 1 WL test cannot distinguish. We compare on existing GNN expressiveness benchmarks for node classification (Limitsl (Garg et al.
2020), Limit2 (Garg et al. 2020), Triangles (Sato et al. 202T), and L.CC (Sato et al. 2021) and graph
classification (4-cycles (Loukas 2020), Skip-Cycles (Chen al. 2019). Rook- Sook-Shrikande (Chen et al.
2019) Furthermore, we test models if they can separate certain graphs from Xu et al. 2019) if we
limit aggregation max mean. We compare AMP-RNN with several powerful GNN extensions 2019). SMP (Vignac et al. 2020 DropGNN (Papp et al.
from literature: PPGN (Maron et al.
2021 P
and ESAN (Bevilacqua et al.
2022 plus a simple GIN (u al. 2019) for control. We
needed to slightly modify all codebases. For training, we follow the setup by PPapp et al. (2021).
GNNs have layers. for Skip-Cycles, we additionally try layers and take the better result. For
AMP, we allow total of 5n messages, with n being the size of the graph. We try both constant (AMP-C) and random message delays (AMP-R). We experiment with the simple recurrent form of AMP that uses just linear layer for 5 and μ.. Figure shows that the starting node matters, so we execute multiple runs for AMP, one for every node with that node being the starting node. Each run computes the final embedding for the starting node. We use 16 hidden units for Limitsl, Limits2, Triangles, LCC, and 4-cycles and 32 units for MAX, MEAN, and Skip-Cycles. Training uses the Adam Kingma & Ba 2015) optimizer with learning rate of 0.01.
Dataset
GNN
PPGN
SMP
DropGNN
ESAN
AMP-C
AMP-R
Limitsl
0.50 #0.00
0.60=0.21
0.95=0.16
1.00=0.00
1.000.000
1.00=0.00
0,89=0.11
Limits2
0.50=0.00
0.85+00.24
1.00=0.00
1.00=0.00
1.00=0.00
1.00=0.00
0.98::0.01
Triangles
0.52:0.15
1.00:0.02
0.9720.11
0.9320.13
1.00
1.00
0.88:0.15
LCC
0.38 10.08
0.80.0.26
0.9510.17
0.9910.02
0.96-0.06
0.96
0.80-0.04
MAX
0.05=0.00
0.36#0.16
0.74+0.24
0.27=0.07
0.05=0.00
1.00=0.00
0.37 #0.10
MEAN
0.28+0.31
0.39=0.21
0.91+0.14
0.58=0.34
0.18=0.08
1.00=00000
0.71=0.11
4-cycles
0.50=0.00
0.80=0.25
0.60=0.17
1.00=0.01
0,50=0.00
1.00=0.000
0.99=0.02
Skip-Cycles
0.10:00.00
0.04:0.07
0.27=0.05
0.82+0.28
0.40=0.16
1.00=00.00
0.56:10.18
Rook-Shi Shrikande
0.50=0.00
0.50=0.00
0.50=0.00
0.50=0.00
0.00
1.00
0.50=0.50
Table 1: Test set accuracy on GNN expressiveness benchmarks that require beyond W- expres- siveness to solve. AMP solves all benchmarks quasi- pursieee even the challenging ones that restrict the aggregation (MAX, MEAN) or require long-range propagation (skip-Cycles)
Table [ shows the test graph results. AMP-C performs better than all other methods and consistently solves all datasets (close to) perfectly. Many methods perform very well on the node classification
Cooee for SMP and PPGN from hoomm//tpp/////thbb...ooo/o/enno
*Code for GIN and
sMart /tttrr/rrrNN
CCode for ESAN htommtttsss///ttttbbbcc///e//ee
7

---

Under review as a conference paper at ICLR 2023
tasks. On the graph classification tasks, all methods but AMP-C struggle. This is particularly true for the two datasets with restrictions on the aggregation. However, sometimes it is desirable not to use sum aggregation function. Other aggregations, such max might offer better algorithmic alignment (Xu et al. 2020, 202T). Moreover, AMP-C solves the Skip-Cycles dataset perfectly which requires long-range information propagation as well as the rook/shrikande graphs that need power beyond 3 - WL. On the other hand, AMP-R suffers from unstable gradients and produces only mediocre results.
5.2 LONG-RANGE INFORMATION PROPAGATION
In this section, we investigate the long-range information propagation of AMP. We experiment with simplified version of finding shortest paths in graphs. Finding shortest paths is interesting for long-range information propagation since it requires reading the entire graph in the worst case and has been used in previous works (Tang et al. 2020 Veliekovie al.] 2020: Xu et al.] (02T). We simplify the shortest path setting: instead of regressing the cxact distance, we classify if the shortest path is even or odd. We do this to abstract from the need do accurate computations of distances. Neural networks struggle with precise arithmetic computations in general (Faber & Wattenholer 2020; Heim et al., 2020; Madsen Johansen 20200 Trask et al. 2018). We compare AMP with several synchronous GNNs (IterGNNs (Tang et (0020) 2 Universal Transformers (Dehghani et al. 2018), and NEG (Neural Execution of Graph Algorithms (Velickovic et al., 2020 For GNNs, we mark the starting node by giving it distinct features, for AMP, we sent this node the initial message.
We train on 25 randomly created graphs with 10 trees. Graphs are based on a random spanning tree to which we add 5 extra edges. Training runs for 1000 iterations and uses the Adam optimizer with a learning rate of 0.01. The hidden size dimension is 30, We train on graphs with size 10, then
follow previous work (Tang et al.] 2020 Velickovic al. 2020 Xu et al. 2021) to test the ability to extrapolate the solution to larger graphs. We test with graphs of sizes 10, 15, 25, 50, 100, 250, 500, 1000. Larger graphs are also more challenging since the shortest paths grow in length. We report the classification accuracy per graph size in Table
We can see that all AMP versions perform better than the synchronous baseline GNNs. AMP-Ite performs especially well. We hypothesize lies in better algorithmic alignment (Xu et al. 2020 2021 )
between the asynchronous architecture and the task. that this is because the asynchronous model aligns better with the given task. Algorithmic aligmment has been shown to both learn with fewer samples and extrapolate better to unseen and harder instances. The better aligmment in this task is that nodes in AMP only need to act when there might be relevant information. On the other hand, nodes in the synchronous GNNs need to stay ready over many rounds until the information from the starting node finally reaches them. Furthermore, the transformer-based architecture AMP-ATT seems to be misaligned with the dataset and possibly the experimental setup that trains for rather few epochs on little data (usually transformers excel on large datasets with plenty of training time).
To give some intuition why AMP works generally better on propagating information over long distances. Consider a node u with degree ö that needs to receive information the shortest way from a node that has distance d to e. In a GNN, v needs to receive dõ many messages to receive the one message. In AMP, v will have received the message after hearing from every neighbor at most once, which ares many messages in the worst case (independent of d, which is often dependent on the graph size). We discuss this idea in more detail in Appendix Cad relate to the problems of Underreaching, Oversmoothing, and Oversquashing.
5.3 GRAPH CLASSIFICATION
Last, train AMP on several graph classification benchmarks. Our AMP implementation runs single CPU since the sequential nature limits GPU potential and python's Global--nterpreter-LLooo prevents multithreading. This makes training larger datasets prohibitively slow for now (for example, PROTEINS takes around - 2 days to train). Therefore we limit the comparison to the smaller datasets MUTAG, PTC, PROTEINS, IMDB-B, IMDB-M (Yanardag & Vishwanathan) 2015). Further, we do a single pass in each training epoch instead of 50 batches of 50 graphs. We run AMP-RNN
*Code from httpa//wwwwtttaaaaeee/t/tttt//tt hhttps://wik ki wwtphtotoooooo..pp http://www......oooooo/oooaaaaa.
8

---

Under review as a conference paper at ICLR 2023
Model
10
25
50
100
255
500
1000
2500
NEG
0.68=0.16
0.56=0.08
0.52=00.3
0.49#0.02
0.49=0.01
0.49=0.01
0.50=0.01
0.49=0.00
Universal
0.91=0.05
0.73+0.05
0.62:00.33
0.5710.02
0.53:0.01
0.51=0.00
0.50=0.00
0.50=0.00
IterGNN
0.85=0.11
0.68=0.06
0.58=0.03
0.55+0.02
0.52+0.00
0.51=0.00
0.50=0.00
0.50=0.00
AMP-RNN
0.81=0.16
0.73+0.17
0.65
0.6140.14
0.54
0.54=0.08
0.54=0.07
0.53=0.04
AMP-GRU
0.98=0.01
0.90=0.05
0.83=0.07
0.75
0.63
0.57=0.14
0.54=0.10
0.52=0.08
AMP-LSTM
0.98=0.02
0.89=0.10
0.8=0.10
0.74+0.12
0.66#0.12
0.63=0.11
0.61=0.07
0.58=0.06
AMP-ATT
0.48=0.01
0.50=0.01
0.49=0.01
0.50+0.00
0.50=0.00
0.49=0.00
0.49=0.00
0.49=0.00
AMP-ACT
1.00=0.00
0.99=0.01
0.98=0.01
0.97+0.02
0.96=0.03
0.95=0004
0.95=0.05
0.94=0.05
AMP-Iter
1.00
0.99-0..0
0.083
0.9710.04
0.9610.05
0.96
0.95-0.07
0.94
Table 2: Accuracy for predicting the parity of shortest paths to a starting node. The table head contains the number of nodes in the test graph while training is always on 10 nodes. AMP-Iter learns to extrapolate almost perfectly. Also other AMP variants extrapolate better than the GNN baselines.
which does short run from every node. We do small grid search over the number of messages (15 or 25) per run, the size of the message embeddings (10 or half the node embedding size), and whether AMP-RNN uses skip connections previous states. The remaining setup is taken from Xu et al.) (2019): We run on 10 different splits and report the accuracy of the best performing epoch. We use hidden node states of 64 for social datasets and 16 or 32 for biological datasets. We further compute results for GraphS AGE (Hamilton et al. 2017), GCN (Kipf & Welling, 2017), and GAT (Velickovid al., 2018) and take results for more GNNs. Table 3 shows all results. Even with little investigation into AMP architectures and hyperparameters, AMP achieves comparable results to existing GNNs but not quite state-of-the-an We believe that further improvements AMP will reach a competitive performance.
Model
MUTAG
PTC
PROTEINS
IMDB-B
IMDB-M
PatchySan NNiepert et al. 2016
92.6 +4,2
62.3 +5.7
75.9 +2.8
71.0 +2.2
45.2 +2.8
DGCNN (Zhang el al. 2018
85.8 11.7
58.6 12.5
75.5 10.9
70.0 10.9
47.8 10.9
GraphSAGR Hamilion el al.
2017)
90.47.88
63.7=9.7
75.6+5.5
76.0=3.3
51.9+4.9
GCN Kipf & Welling
2017
88.9 17.6
79.1
76.9
83.4
57.5+2.6
GAT Velckovic ci al. 2018
+9.3
64.5=7.0
75.4+3.8
74.9+3.8
52.0+3.0
GIN ex al. 2019
89.4.15.
66.6 16.9
76.2 12.6
15.1
52.3 12.8
1-2-3 GNN (Morris et al. 2019
86.1
60.9
75.5
74.2
49.5
DropGNN (Papp el al. 2021
90.4 17.0
66.0-9.8
76.3 16.1
14,2
12.8
PPGN (Marn et 2019
90.6 +8.7
66.5
74.7
73.5.8
50.5 +3.6
ESAN (Bevilaquua et al. 2022
92.0=5.0
69.2=6.5
77.3 +3.8
77.1+2.6
53.7+2.1
AMP-RNN (ours)
90.4#4.1
63.7 +9.1
76.7+7.1
74.6#3.6
52.1+3.6
Table 3: Graph classification accuracy (%). First block are 1 WL. GNNs, second block are beyond 1- WL GNNs. AMP produces results that are comparable both GNN variants. *We report the result achieved by the best model version.
CONCLUSION
We presented a new framework, AMP, for learning neural networks on graphs AMP can treat every message individually, and as such (in principle) no information is lost in aggregation. This benefits AMP to tackle problems such as underreaching or oversquashing and makes AMP not limited to the W- test. We theoretically investigate its expressiveness and empirically evaluate its ability to distinguish hard graphs, propagate information over long distances, and classify common benchmarks. AMP might also be more interpretable if we investigate when nodes react or ignore message. This makes us believe that AMP is a promising paradigm that warrants further exploration. GNNs have improved considerably over the last years and we believe AMP will similarly. However, before can apply AMP to most real-world problems, we need to improve tooling to allow parallelism to reduce the problematic runtimes for larger graphs.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Vitalii Aksenov, Dan Alistarh, and Janne H Korhonen. Scalable belief propagation via relaxed scheduling. Advances in Neural Information Processing Systems, 2020.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations (ICLR), 2021.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. In International Conference on Learning Representations (ICLR), 2018.
Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 1985.
Pablo Barceló, Egor Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In International Conference Learning Representations (ICLR), 2020.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 180.008006 2018.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations (ICLR), 2022.
Tian Bian, Xi Xiao, Tingyang Xu, Peilin Zhao, Wenbing Huang, Yu Rong, and Junzhou Huang. Rumor detection on social media with bi-directional graph convolutional networks. In AAAI conference on artificial intelligence (AAAI), 2020.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- tional Conference on Learning Representations (ICLR), 2022.
Rickard Gabries,,,,,,sson,, Mikhail Yurochkin, and Justin Solomon. Rewiring with positional encodings for graph neural networks. arXiv preprint arXiv:2201. /2674, 2022.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In AAAI Conference Artificial Intelligence (AAAI), 2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning (ICML), 2020b.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In Empirical Methods in Natural Language Processing (EMNLP), 2014.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In International Conference Learning Representations (ICLR), 2018.
Gal Elidan, Ian McGraw, and Daphne Koller. Residual belief propagation: Informed scheduling for asynchronous message passing, arXiv preprint arXiv: 1206.6837, 2012.
Lukas Faber and Roger Wattenhofer. Neural status registers. arXiv preprint arXiv:2004.07085 2020.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han. Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. In Conference Newral Information Processing Systems (NeurIPS), 2020.
10

---

Under review as a conference paper at ICLR 2023
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), 2020.
Johannes Gasteiger, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs. International Conference on Learning Representations (ICLR), 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv: 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Conference on Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In International Conference on Machine Learning (ICML), 2020.
Niklas Heim, Tomas Pevny, and Vasek Smidl. Neural power units. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1997.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
Christian Knoll, Michael Rath, Sebastian Tschiatschek, and Franz Pernkopf. Message schedul- ing methods for belief propagation. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD, 2015.
Guohao Li, Mathhis Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In IEEE international conference on computer vision (ICCV), pp. 9267-9276, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI Conference Artificial Intelligence (AAAI), 2018.
Andreas Loukas What graph neural networks cannot Iearn: depth vs width. International
Conference Learning Representations (ICLR), 2020.
Andreas Madsen and Alexander Rosenberg Johansen. Neural arithmetic units. International
Conference on Learning Representations (ICIR), 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Conference on Neural Information Processing Systems (NeurIPS). 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence (AAAI), 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference machine learning (ICMI.), 2016.
11

---

Under review as a conference paper at ICLR 2023
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations (ICLR), 2020.
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: random dropouts increase the expressiveness of graph neural networks. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations (ICLR), 2020.
Halsey Lawrence Royden and Patrick Fitzpatrick. Real analysis. Macmillan New York, 1988.
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Panduran- gan, David Peleg. and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 2012.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In SIAM International Conference on Data Mining (SDM), 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 2008
Simon Schaefer, Daniel Gehrig, and Davide Scaramuzza. Aegnn: Asynchronous event-based graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-tehman graph kernels. Journal of Machine Learning Research, 2011.
Iyya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence sequence learning with neural networks. In Conference on Neural Information Processing Systems (NeurIPS), 2014.
Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liang Lu, and Hao Su. Towards scale-invariant graph- related problem solving by iterative homogeneous gnns. Conference on Neural Information Processing Systems (NeurIPS), 2020.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over over-squashin and bottlenecks on graphs via curvature. In International Conference Learning Representations (ICLR), 2022.
Andrew Trask, Felix Hill, Scott Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. In Conference on Neural Information Processing Systems (NeurIPS), 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Conference on Neural Information Processing Systems (NeurIPS), 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018
Petar Veliekovic, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference Learning Representations (ICLR), 2020.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing In Conference on Neural Information Processing Systems (NeurIPS), 2020.
12

---

Under review as a conference paper at ICLR 2023
Roger Wattenhofer. Mastering Distributed Algorithms. Inverted Forest Publishing, 2020.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and lon Stoica. Representing long-range context for graph neural networks with global attention. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning graphs with jumping knowledge networks, In International Conference on Machine Learning (ICML), 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations ICLR), 2019.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference Learning Representations (ICLR), 2020.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: from feedforward to graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD). 2015.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen, An end-to-end deep learning architecture for graph classification. In AAAI Conference Artificial Intelligence (AAAI), 2018.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations (ICLR), 2020.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In Conference Neural Information Processing Systems (NeurIPS), 2020.
13

---

Under review as a conference paper at ICLR 2023
A MORE DETAILS ON AMP
A.1 ANOTHER PERSPECTIVE ON AMP
Rather than looking at all nodes at the same time, let us view the AMP execution from the perspective of a single node (Figure Zp. This node receives sequence of messages and transitions through a series of states and produces new messages. In cases learnt through p. the node skips the input (for example for message m The behavior mimics that of sequence-to-sequene to-sequence models that have seen great success in Natural Language Processing (Sutskever et al. 2014). Compared to NLP tesueeec---sseueecce models, the AMP must overcome two additional challenges.
Unknown input sequences. In most sequence-to-sequeree a known input sequence into an output sequence. In NLP, input sequences are often sentences and the sequence elements are words, for example, when we want to translate sentences. In such cases, the input sequence is entirely known the start. In the context of Figure learn to optimize the sequence of h; while the sequence of m, is constant. In AMP, the messages are not constant but need be jointly optimized with the state update function. This makes the gradient signals noisier and the training process more difficult.
language models, we want to transform
language model can
Partial information accessible. natural language processing, the input sequence contains all the needed information to produce the target prediction. Consider again the translation setting, where sentences are inputs and words are sequence elements. Every word has access to the entire input sequence and thus all the information it nceds. However, most nodes in graphs do not have access to all information they need. Figure [ iillustattes the problem with a simple example. The node on the right needs to know if there is red node in the graph. There is one such node, However, in between those two nodes are nodes / and u. For both / and u, the red node s is not important since I and are only interested in the number of blue nodes. Therefore, if either L or decide to forward information about the red node, the information that & exists never reaches v and v cannot classify correctly. The takeaway from this example is that nodes not only need to understand what messages are important to them and how to use these messages, but nodes also need to identify the messages that are important to other nodes and propagate these messages.
m4-1
m
mi+11
m2+2
14-1
Pos
Re5+1
Ri442
m
m
m4+2
Figure 4: AMP dynamics for one node in isolation. The node receives sequence of messages which it can use to update its state and emit a sequence of messages.
Figure 5: Node needs message from s but needs the unrelated and to forward the message.
A.2 CONCRETE MODELS IN THE AMP FRAMEWORK.
The analogy to recurrent architectures lens ideas for several implementations of the AMP framework. Probably among the simplest is the equivalent of recurrent neural network: we skip P and use linear layers for 8 and Other feedforward layers such as multilayer perceptrons or other neural architectures are equally possible. Upon receiving messages mi, m2.. m, we compute the hidden states = 5(2;-1, m.) with zp being the initial features and m, = pu22,,
We can also instantiate the AMP framework with other recurrent architectures. For example, we can create GRU cell to model 8 and input received messages they come in over time (Cho) ctt al., 2014). The gating of the GRU cell also implicitly models the p function since can learn to ignore certain messages. Hidden states are computed 2; GRU(2;-11 m,). We make the message computation a linear transformation of 2,, Analogously, we can create a version of AMP using an LSTM cell (Hochreiter & Schmidhuber 1997).
Another version of AMP could use the attention mechanism of transformers Vasswan et al. 2017) to compute node states based on the history of messages received so far. When receiving message
14

---

Under review as a conference paper at ICLR 2023
my compute:
2; 8
Σ a(z)-1.mm)) k=1.,
The function a a parametrized dot-product attention function that computes an attention score for every previous message and normalizes them to sum up to 1. We use linear readout for the new message. This model can also implicitly model p by assigning very small attention values to unimportant messages.
Let us now look at two example architectures that explicitly model p. The first idea is based on idea of Adaptive Computation Time by Graves (2016). Upon every received message, the receiver computes a termination probability that this message should be its last. When the sum over all termination probabilities is at least computes final embedding based on a message we compute:
the node stops being interested in further messages and average. Upon receiving
Pi+1 = min(1
Σ kEl..f
Pk: p( m))
Where we have óg as the initial node state. We compute the final representation after n steps as:
8
Σ Pk 6F
kE
The second idea follows Tang et al. (2020) and also uses termination probabilities. However, probabilities combined multiplicatively instead of additively:
= II (1 Pi) p(o;, m) R 1..
Again, we can compute the final representation as a termination-probabilii weighted average of all intermediate values. Both ideas for p make no assumption about or p.
15

---

Under review as a conference paper at ICLR 2023
B PROOFS
B.1 PROOF FOR THEOREM 3.1
The underlying proof idea the a synchronizer from asynchronous distributed computing by Awerbuch (1985). In this synchronizer, nodes are only allowed to send messages when they are "safe". node is safe when received an acknowledgment from every neighbor for its previous message. The authors show that the synchronizer allows asynchronous models to mimic distributed models such as LOCAL (Peleg 2000
We will give a constructive proof of Ag- Let G be message passing GNN with MESSAGE and UPDATE functions. Let us further assume that every layer in G has the same dimension (for simplicity, handle different embedding sizes later) and messages have size m. Let L be the total number layers in 9 and D be the degree for node
We construct Ag follows: Ae will have states of size 2d + that represent tuples (s, a, w, u, i, 1) with the following semantics: The number of the last layer of g that we have simulated, The number of "unacked" neighbors of node, The number of messages that node waiting on, i, whether the node acted at least once (only true until the first update), 8: The actual state of the node. This will always correspond to the representation in 9 at the layer mapped by of the node, and a: An accumulator to collect the messages of the node's 's neighbors. We initialize to (xx 0, 1, D, A,D.D.0.. L) with X in G.
Furthermore, A sends messages of size m + 4 which we represent as tuples (m, ack, pulse, origin, noop). The last four positions one-hot encode which kind of mes- sage we send. For Ag. we choose = MESSAGE and set = p(s). We set p to ignore messages of type "noop" or we when simulated all I. many layers of G. We provide and which message type to send in Table Image the function in the table as cascade of conditional assignments which we evaluate from top to bottom and stop on the first matching one. We will show that whenever a node emits a "pulse" message, its current state maps the message passing embedding =f-1, Nodes will emit such "pulse" messages when (i) they received "pulse" message from every neighbor (ii) they received an "ack" message from every neighbor (when they are safe).
Condition
a²
w
u
i
message type
hoop=1
1
1
1
T
1=0
1
1
I
I
1
1
origin=l
D
1
pulse
i=1
a+m
w-1
1
pulse
pulse=1 A w=0
UPDATE((s(arm))
0
D-1
u-1
1-1
ack
pulse=1
a+m
w-1
1
noop
ack=l A u=0
a
1
pulse
ack=l
a
u-1
noop
Table 4: Update function 8 and message type to send (part of μ used by every node in AMP to simulate synchronous GNN.
Lemma B.1. When a node executes the condition received pulse message.
Proof. There are four possible messages or origin, pulse, noop, and ack. Every noop message ignored, and the origin message is handled differently and only sent once. Let us assume that node e receives neighbor u received one message from every neighbor once, includeing v. However u did not act yet since just received its first message so cannot have sent such message.
ack message before pu se message. This would require that of v's
Lemma B.2. When node emits its i- pulse message, must have already received (i (i- D+ pulse messages
We take the node degree given which simplifies the proof but does not leak information Ag. Nodes AMP can their degree by flooding network once storing the count in an additional state entry that never modified again.
'There is one exception to this lemma, which is the node receiving the "origin" in place for one pulse message.
16

---

Under review as a conference paper at ICLR 2023
Proof. We prove by induction. The lemma is true after initialization when all nodes are about to send their 1 pulse messages. Nodes send a pulse message when they receive one themselves, thus, after 1 total.
Suppose the lemma is true for and node v has received (i 1) D + 1 and just sent its i- pulse se message. For i > this is only possible by the seventh condition in Table 4 which also sets u = D. Before we can send another pulse via this condition u must be decremented to O. This requires an "ack" message from every neighbor and also executing the fifth condition, which requires to = O. Decrementing w to zero is only possible by receiving D - pulse message in the sixth condition and then one more message in the fifth condition. At this point, has received (i 1--1) D + 1+ D 1 + i. D + pulse messages.
Corollary B.3. If nodes require D pulse messages between their own pulses, it receives one pulse each from every neighbor.
Lemma B.4. When a node v emity i-th pulse message, it's state a equals the synchronous GNN representation z!-i-1
Proof. We proof by induction. Because of the way nodes are initialized, the moment they receive their first message (condition 2 or 3 nodes emit their first pul se). this point, the node state equal the initial features aka zq.
Assume the lemma holds for node v just send it's i- pulse message. We know from Lemma B 2 that e now needs to receive D pulse messages before it can send pulse - 1. One pulse will come from each neighbor following B.3 According to the induction hypothesis, node receives z from every neighbor in their ith pulse message. Upon receiving the last of these messages (fifth condition), v computes locally UPDATE(2) ----E ''e 21-i-1 zp -))). This state is unchanged until emits its 1st pulse.
We can gather all representations that G can compute by listening to each node and recording its state when it emits a pulse message.
Disconnected graphs The proof assumes a connected graph but we can extend it to arbitrary graphs. We can either (i) send one origin message to each connected component or (ii) introduce a master node that connects every node (thus connecting the graph) and does nothing but forward pulse messages while ignoring all other messages. This master node does not count into a node's degree.
Differing layer sizes Let us relax the assumption that we have a uniform width d over all layers and instead different widths d1, d2.... dd....dy dz. We can still use the above construction, but the AMP model will have state space consisting of su, ag, $1, a1,... $L, a,, w, u, l. Furthermore, the update in the sixth condition does not overwrite the state but writes in the next layer's state. Similarly, can support different message sizes and different message functions per layer.
Skip connections The construction for different layer sizes computes and stores the embeddings for every layer. If we modify 5 to not overwrite correctly computed values (for example by only updating state vectors with matching value of 1), also simulate skip connections.
Other aggregation functions Other associative aggregation functions work out of the box with the above construction. But For mean aggregation, we do not only keep track of the sum but also the count of messages in the aggregator. Then we compute the UPDATE function the count divided by the sum. Similarly, can extend, for example, to the GCN Kipp & Welling 2017) model.
also other aggregations work, for example, mean aggregation.
Learning the function in Table 4 According to the universal approximation theorem (Royden & Fitzpatrick] 1988), using a sufficiently wide 2 layer neural network can approximate any function. Therefore, choose 5 and y to be such networks model the function shown by Table 4
17

---

Under review as a conference paper at ICLR 2023
B.2 PROOF FOR LEMMA 4.2
Proof. Let the computation start from node v which is part of the cycle and every node executes the following protocol. If a node receives a message COUNT-i and it never received message before, it stores i and messages COUNT- + 1). If the same node then receives COUNT-j message with j > i the node ignores the message. Node starts the computation by sending COUNT-O. The nodes on both paths in the cycle now start storing numbers mapping to a BFS. Eventually, the two BFS branches meet. This happens when one node w that first received a COUNT message receives a COUNT-j j message with 2 j. Then knows that the circle is closed and sends F FOUND-G (j + that every node forwards once. Thus, all nodes become aware of the cycle and its length.
B.3 PROOF FOR LEMMA
Proof. v and its neighbors will iteratively find out that they are in 3. ...... ++ 1 cliques. The starting node will coordinate the other nodes. Initially, every node stores that they in 1-clique. To find a clique of size j, node u sends a CLIQUE-j message, which every neighbor of u forwards once. If neighbors of receive they send a CLIQUE--3 -JACKK ACK message to all neighbors (including v) and update their state to be in a j j-clique. If receives & many CLIQUE-3 j-CS-jjACKKKK messages, it sends out a CLIQUE -jj + message. Upon receiving k many CLIQUE- (k - 1) -CCK messages, v knows there exists (k + 1) clique and can propagate this information to its neighbors.
1 such messages and they are in a
clique according their state,
B.4 PROOF FOR LEMMA
We show that AMP with random delays can create unique identifiers for every node in a star graph with central node and i outer nodes. The problem we need to solve is bringing order in the equal neighbors of v, which we do by exploiting the random delays: We connect the neighbors of F When "offers" an ID, nodes without an ID will reply to try to cl claimii it. Some nodes will receive this reply before they receive the message from v. These nodes will surzender this ID. After some attempts to offer the ID, all but one node will surrender. Then gives the ID to the one non non-surrendering node (implicitly by starting to offer the next ID). Then the protocol restarts for the next ID (minus the nodes that are done and have ID).
We prove the Lemma constructively by transforming this idea into a network. We have four states, of effering (which is only used by v), claiming and surrendering (which are used by the outer nodes), and done used by all nodes that no longer need to participate. We have five message types of fer, con f firm, cla iim, surrender, origin gin, i, and noop.
Nodes have states that are tuples (state, try, ID, c, w, x): state is one of above states, try identifies different ID assignment attempts from each other, and ID is the ID of the node. The next three entries are only used by central node v: a binary feature if the ID was already claimed in the current attempt, w contains the number of neighbors in the current attempt that did not reply yet, x contains the number of neighbors that do not have an ID yet. Initially, every node starts in state (surrendering) -1, -1, 0, 0, 0).
Messages are tuples (type, CTD, attempt)): type is one of above messages types, CTD is candidate ID that e tries currently assign, atteeppt is the current attempt to assign an II).
Table 5 shows the node update and message functions in AMP for the center node, of the outer nodes. Practically there of course only one function and nodes can judge by their state if they are the center node or node. For readability, we split them here. If the reaction function p decides to ignore a message, the tables show a row of blanks (L).
Proof. Let us now prove that his algorithm assigns valid identifiers, namely (i) that no two nodes receive the same identifier and (ii) every node receives an identifier.
(i) The center node takes ID ( for itself and only proposes IDs of 1 and above to its neighbors. If a neighbor does not change its ID, stays with 11. Thus ID unique. Let us suppose that two
*These edges not necessary since could propagate messages between outer nodes, but they make the idea more concise and the algorithm faster
18

---

Under review as a conference paper at ICLR 2023
nodes W1, W2 received the same ID. Since IDs are increasing W1 and w2 must receive the ID the same time. Since the confi rm message is only sent when there was one node left, w1 and wy must have received the ID via the second to last condition in Table ba This is only possible if they were in state c imim ng, which means that they both send a c message. However, in such cases, v starts another try with the same ID before. This contradicts the requirement that IDACID.
(ii) The center node receives ID O. We have to show all other nodes also receive an ID. Node v counts internally how many IDs it could offer successfully and only stops when this counter reaches 0. The counter is initialized with e degree so u will try to hand out enough IDs. Let us suppose that w did receive an ID. Unless will always try claim an unless it already surrendering this ID. Therefore u surrenders for all IDs, even the last one. However, this is not possible since there is only left and no node could have sent cla message make w surrender.
Condition
state
try
ID
W
X
type
CID
attempt
noop
T
1
1
1
I
done
1
1
1
1
1
1
I
try # attempt origin
1
1
I
1
offering
0
0
0
D-1
D-1
offer
(
claim A c
offering
try
w-1
X
noop
claim A >>> 0
offering try+1
X-1
offer
CID
try+1
surrender
offering
try
W-1
X
noop
A x 0
offering
try+1
X-2
X-1
offer
CID+I
try+1
X =
done
0
0
confirm
1
1
(a)
(b)
Table 5: Node update function (a) and message function μ (b) for the central node in AMP to assign unique IDs in star graph.
Condition
state
try
ID
type
CID
attempt
noop
T
1
done
1
I
surrendering offer CID=ID offer A attempt > try claiming A attempt try claiming offer ID & CID claiming A confirm
surrendering claiming attempt surrendering
attempt
ID
1
surrender
CID
attempt
CID
1
claim
CID
attempt
attempt
CID
1
surrender
CID
attempt
done
0
ID
1
noop
1
done
0
ID
1
1
noop
I
(a)
(b)
Table Node update function (a) and message function μ (b) for the outer nodes AMP assign unique IDs in star graph.
B.5 PROOF FOR THEOREM 4.7
Proof. We are reducing Theorem 4.7 to Corollary 3.1 from Loukas 2020). The authors show that we have (i) unique identifiers for every node in a graph and (ii) we have a message passing GNN that has no bound in width and is least as deep the graph's diameter dg, this GNN is Turing universal and can compute any function on this graph (including graph isomorphism).
Let G1, G2 be two connected graphs for which want to test graph isomorphism. We create the graph by adding unique node 2 that we connect to a random node from G₁ and G2 each. Further, let be GNN of unbounded width that has at least & many layers. If the GNN has access IDs, this GNN is Turing universal and can compute any computable function. Therefore, this GNN can compute if G and 22 isomorphic. Let consider an AMP model with unbounded width, which can compute graph isomorphism on G as follows: First, we employ Lemma 4.5 to assign every node
Without loss of generality, can also start the ID assignment in AMP at node u, this node would always
have ID O.
19

---

Under review as a conference paper at ICLR 2023
unique identifier. Then we leverage Theorem 3.1 and simulate G with the identifiers for ôg many rounds. Whatever representations G finds to able to compute graph isomorphism between G1 and G2. AMP can compute them as well through simulation. Thus AMP can also compute graph isomorphism on any graph G.
Finally, let tackle the unbounded width requirement. We not interested in any algorithm on G, but only in determining graph isomorphism. We can estimate the required width for this problem follows: One example algorithm to compute graph algorithms complete representation of in every node. If we use adjacency matrices this requires width O(n²). Now we enumerate all possible assignments x from nodes in G1 G2 of which there are O many. For each candidate we write the permuted adjacency matrix, requiring O(a!) space. If any permuted adjacency matrix equals that of G1, the graphs are isomorphie, otherwise they are not. We can find out, by checking if their subtraction equals 0 which requires constant width for each of the
use the &G layers build
!!5!) candidates. We can conclude that the GNN can solve graph isomorphism on with O width. This is the same bound for AMP that needs only constant factor in state and message size to simulate a GNN.
20

---

Under review as a conference paper at ICLR 2023
C ANALYSIS OF RESULTS IN SECTION 5.2
C.I UNDERREACHING
To better understand the improvements of AMP, we analyze the exposure of all models to underreach- ing, oversmoothing, and oversquashing. To estimate underreaching, we break down the accuracy by distance from the starting node. If accuracy decreases with increasing distance suggests exposure to underreaching. Practically, since the label flips in every step we merge odd and an even pair into one bucket. For example, the scores for distances and are combined. Figure shows the results broken down by distance. We can that almost no architecture except AMP-IIee and AMP-ACT can extrapolate to much larger distances than the training set. This contributes largely to the decrease in accuracy since the larger graphs become, the more nodes have large distances to the starting node.
To gain some mathematical intuition into the results, let us understand the task a bit better: A node v with degree 8 and distance d to the starting node, only neds to know the parity of its predecessor the shortest path from s to v. If u has an even parity, v has odd parity and vice versa. Therefore, v needs exactly one message (assuming shortest paths are unique, otherwise there might be multiple useful messages). However, e will receive at least d many messages in synchronous GNN before can classify. Here, 5 grows with increasing graph size which means the useful message lost in more and more unimportant messages. On the other hand, nodes in AMP can decide after they received a message for each neighbor once, in other words after 6. In the simpler AMP-RNN, the same neighbors might send multiple messages which they do not need to do in AMP-Iter (nodes ignore unimportant messages and terminate after the message from w). This might explain the performance difference between those two architectures.
AMPACT-AMPA AMP-Iter
0.8
0.7
AMP-RNN
AMP-GRU
Universal
AMP:LSTM
9.8
NEG
IterGNN
AMP-ATT
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Figure Caption
Distance
NFG
Universal
TterGNN
AMP-RNN
AMP-GRU
AMP-I.TM
AMP-ATT
AMP-ACT
AMP-Iter
0-1
0,50:0.04
1.010.0
0.9510.07
0.69
0.8910.07
0.86:0.08
0.50:0.00
1.0:0.0
1.000.0
2-3
0.47:0.05
1.0+0.0
0.95+0.07
0.70:0.10
0.89:0.07
0.85=0009
0.49:0.00
1.0:0.0
1.0:0.0
4.5
0.4910.01
0.510.0
0.5=0..0
0.70:0.10
0.84:0.08
0.81:0.11
0.4910.01
1.0:0.0
1.0+0.0
6-7
0.51
0.5+0.0
0.5-0.0
0.60=0.10
0.66:s.117
0.77=0.11
0,49:0.00
0.98+0.01
0.99+0.00
8-9
0.49=0.01
0.5+0.0
0.5=0.0
0.55=0.11
0.55#0.11
0.69=0.10
0.50=0.01
0.96+0.02
0.96+0.03
10-11
0.49:0.01
0.5+0.0
0.5-0.0
0.48=00033
0.51+0.02
0.53+0002
0.5+0.0
0.94+0.02
0.94+0.04
0.49=0.01
0.5+0.0
0.50=0.00
0,50=0..0
0.49=0.00
0.5=0.0
0.93+0.03
0.93+0.04
14-15
0.49=0.00
0.5+0.0
0,5=0.0
0.5+0.0
0.5+0.0
0.5+0.0
0,5+0.0
0,90=0.05
0.92+0.06
16-17
0.49:0.00
0.5+0.0
0.5=0.0
0.5
0.5:0.0
0.5+0.0
0.5:0.00
0.88:0.06
0.90:0.07
18-19
0.4910.00
0.5.0.0
0.5=0.0
0.5
0.5.0.0
0.510.0
0.5.0.0
0.8610.08
0.9010.07
20-21
0.49:0.00
0.5+0.0
0.5=0.0
0.5
0.5+0.0
0.5+0.0
0.5:0.0
0.88+00.8
0. 0.90+0.07
Table 7: Investigation of the underreaching effect. Table columns show the accuracy per metric for nodes with increasing distance the starting node. If loss in accuracy occurs, the model has trouble transmitting the information to larger distances. AMP-hased approaches are better equipped to transmit information long distances, in particular AMP-ACT and AMP-Iter.
21

---

Under review as a conference paper at ICLR 2023
C.2 OVERSMOOTHING
To estimate oversmoothing, we restrict the accuracy measurement towards nodes whose distance to the starting node is in the training set. If the accuracy decreases, the presence of far away nodes in larger graphs impacts close-by nodes, which indicates oversmoothing. Figure 7 shows the results of this analysis. In principle, all models combat oversmoothing well except AMP-ATT and NEG and to a lesser extent AMP-RNN.
To gain some intuition into the oversmoothing results let us look messages sent after node received the message it needed to classify. In GNNs the node can decide to participate in L - more rounds (where L is an upper limit on the number of layers). However, does not learn any new information in these layers, they can only disturb the signal already gathered. In IterGNN and Universal the node can learn to stop listening thus avoiding this effect. Similarly, AMP-ACT and AMP-Iter stop avoid oversmoothing.
AMP-GRU and AMP-LSTM can also learn to ignore later messages but they need to learn for every possible message ignore the message via gating. This is harder than AMP-ACT or AMP-Iter, which use up a budget so any later message is ignored. Last, AMP-RNN has no such mechanism so see it slowly degrading.
1.0
AMP-ACT
AMP-Iter
AMP-GRU
0.8
Universal
AMP-LSTM
IterGNN
AMP-RNN
0.6
NEG
AMP-ATT
10
25
50
100
250
500
1000
2500
Figure 7: Caption
Model
10
25
50
100
250
500
1000
2500
NEG
0.68=0.17
0.57=0.09
0.51=0.05
0.48+0.11
0.45=0.08
0.46=0.08
0.45=0.10
0.46=0.08
Universal
0.8210.03
0.7810.06
0.7810.06
0.7810.06
0.7810.06
0.7810.06
0.7810.06
0.78-0.06
TterGNN
0.78=0.10
0.73=0.06
0.73=0.06
0.73+0.06
0.73+0.06
0.73=0.06
0.73=0.06
0.73=0.06
AMP-RNN
0,80=0.17
0.75+0.19
0.70=0.24
0.68+0.24
0.66#0.25
0.69=0.22
0.66=0.20
0.63=0.15
AMP-GRU
0.9610.05
0.93
0.9410.07
0.9210.09
0.8610.23
0.8010.28
0.78
0.76
AMP-LSTM
0.96=0.06
0.91=0.11
0.88=0.15
0.85+0.18
0.79=0.24
0.78=0.28
0.78=0.28
0.77=0.28
AMP-ATT
0.50=0.03
0.48=0.04
0.47=0.03
0.46+0.03
0.46#0.03
0.46=0.03
0.47=0.03
0.46=0.03
AMP-ACT
1.0+0.0
1.0=0.0
0.99=0.00
0.99+0.00
0.99=0.00
0.99=0.00
0.99=0.00
0.99=0.00
AMP-Ite
1.0+0.0
0.99=0.00
0.99=0.00
0.99+0.01
0.99=0.00
0.99=0.00
0.99=0.00
0.99=0.00
Table 8: Investigation of the oversmoothing effect. Table entries measure the accuracy of the subset of nodes that have a distance to the starting node that the model saw in the training set. Oversmoothing would mean that the introduction of nodes that further away (and require additional rounds) causes a drop for the close-by nodes. A model that performs achieves the same result across all columns shows resilience against oversmoothing. All models except AMP-RNN demonstrate resilience, though only AMP-ACT and AMP-ITER remain resilient over all graph sizes.
22

---

Under review as a conference paper at ICLR 2023
C.3 OVERSQUASHING
To estimate oversquashing, we compare the performance of the model when it has to solve the shortest path task to when it has solve three shortest path tasks at the same time the same graph. This triples the amount information nodes need to exchange. Figure shows the accuracy for the single problem, Figure the accuracy for the threefold problem. We see that all methods deteriorate in performance, which is expected since the learning task is harder. However, AMP-Iter and AMP-ACT deteriorate least. Since nodes in AMP receive information for one problem exposed to oversquashing. Recurrent AMP variants perform worse than AMP-Iter and AMP-ACT and even worse than IterGNN and Universal. This suggests that learning to terminate is helpful here.
time, they are less
This task is more difficult than the single source variant because of two reasons: (i) message can contain 0, 1, 2, or3 bits of important information (ii) a node cannot terminate after the first important message but needs to wait for three such messages. The second reason aggravates the challenge discussed in the underreaching problem. Additionally, nodes can no longer just set their state based on the message they receive, they also have take their previous state in account which might contain information about another source. The first reason suggests that messages can carry more information, so blurring that information with that messages of unimportant neighbors makes harder find an learn this information. Furthermore, it might be possible that two sources are equal distance, in these cases synchronous GNN learns of both the same time and has account for both. Nodes AMP receive and can react to the messages individually.
0.7
180
20
180
(a)
Figure 8: Accuracy for the shortest path parity task (y- aris) for solving (a) one (b) three tasks at the same time for different graph sizes axis)..). The more accuracy drops between the left to the right figure, the method is exposed to oversquashing.
23

---

Under review as a conference paper at ICLR 2023
Model
10
25
50
100
250
500
1000
2500
0.68=0.16
0.56:0.08
0.52=0.03
0.49:0.02
0.49:0.01
0.49=0.01
0.50=0.01
0.49=0.00
0.52=0.03
0.49=0.01
0.50=0.00
0.49+0.00
0.50=0.00
0.49=0.00
0.49=0.00
0.50=0.00
0.91=0.05
0.73+0.05
0.62+0.03
0.57+0.02
0.53+0.01
0.51
0.50=0.00
0.50=0.00
Universal
0.78=0.08
0.65=0.06
0.58=0.02
0.54+0.01
0.50
0.50=0.00
0.50=0.00
0.50=0.00
0.85=0.11
0.68=0.06
0.58=0.03
0.55+0.02
0.52=0.00
0.51=0.00
0.50=0.00
0.50=0.00
IterGNN
0.72+0.07
0.62=0.07
0.57=0.04
0.53+0.02
0.51
0.50=0.00
0.50=0.00
0.50=0.00
0,81=0.16
0.73=0.17
0.65#0.16
0.61+0.14
0.54+0.10
0.54=0.08
0.54=0.07
0.53=0.04
AMP-RNN
0.58=0.04
0.53=0.03
0.50=0.02
0.51+0.03
0.50=0.02
0.50=0.01
0.50=0.00
0.50=0.00
0.98=0.01
0.90=0.05
0.83=0.07
0.75+0.10
0.63+0.13
0.57=0.14
0.54
0.52=0.08
AMP-GRU
0.62=0.03
0.58=0.03
0.54=0.04
0.55+0.04
0.52+0.04
0.52=0.02
0.52=0.02
0.51=0.01
0.98=0.02
0.8940.10
0.8=0.10
0.74+0.12
0.66#0.12
0.63=0.11
0.61=0.07
0.58=0.06
AMP-LSTM
0.61=0.04
0.60:0.04
0.55=0.04
0.5610.05
0.53+0.04
0.52=0.02
0.52=0.02
0.51=0.01
0.48=0.01
0.50=0.01
0.49=0.01
0.50+0.00
0.50=0.00
0.49=0.00
0.49=0.00
0.49=0.00
AMP-ATT
0.51+0.02
0.49:0.02
0.50=0.01
0,4940.00
0.49+0.00
0.50=0.00
0.49=0.00
0.49=0.00
1.0+0.0
0.99=0.01
0.98=0.01
0.97+0.02
0.96=0.03
0,95=0.04
0,95=0.05
0.94=0.05
AMP-ACT
0.8410.04
0.7610.04
0.7310.03
0.7010.04
0.6610.04
0.6410.04
0.62-0.04
0.60-0.04
1.0=0.0
0.99=0.00
0.98=0.03
0.97+0.04
0.96:0.05
0.96:0006
0.95=0.07
0.94=0.08
AMP-Ite
0.86=0.03
0.78=0.03
0.72+0.02
0.69+0.03
0.65+0.03
0.62=0.02
0.60=0.03
0.57=0.04
Table 9: Investigation for the oversquashing effect. The effect be seen per method in the degradation from the first to the second row. The first row corresponds to the numbers Table 2 from the main body. The second row corresponds to the accuracy of solving three shortest path parity tasks at the same time. We only emphasize the best accuracy on this task. AMP-based approaches with self-supervised self termination perform best.
24


Reviews:
[{"review_id": "uqh5skv2GAP", "reviewer": "Reviewer_oodJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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. \n", "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\n\nYet, there are certain limitations to the work in its current form:\n* The literature is not conclusive and a more focused presentation would improve the paper overall (see clarity,... below)\n* 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.\n* 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.\n* 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., \n** 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?\n** 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?\n** 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.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EzS0qwGK1i", "reviewer": "Reviewer_BeiX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.\n\n==================post rebuttal========================\n\nI thank the authors' rebuttal. My major concerns are addressed and hence I increase my rating from 5 to 6.", "strength_and_weaknesses": "### Strengths\n\n- The idea of AMP is interesting, especially its various variants of designs.\n\n- The results on the synthetic datasets are impressive.\n\n- The provided experimental code is well-documented. The environment, package dependency, and the steps to reproduce the results are all stated.\n\n### Weaknesses\n\n- 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.\n\n- 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?\n\n- 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.\n\n- 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.\n\n### Detail comments\n\nWhile 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. \n\nAlthough 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.\n\nRegarding 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CC_9qeePwx", "reviewer": "Reviewer_qHED", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "\nStrengths:\n\n1. The motivation and analysis of proposing AMP is inspiring and novel.\n\n2. 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.\n\n3. The expressive analysis of AMP can answer the question why we should use AMP compared to message passing GNNs.\n\n4. The empirical performance on the expressiveness synthetic benchmarks are compelling and can support the main claim well.\n\nWeakness:\n\n1. 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.\n\n2. The proposed new framework seems to be inefficient. The theoretical and/or empirical analysis of the complexity should be included.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BGPM2APnwU", "reviewer": "Reviewer_6FHJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "**Strengths:**\n1. This proposed AMP framework is interesting. \n2. Experiments demonstrate that the AMP-based model outperforms powerful synchronous GNNs on several GNN expressiveness benchmarks in terms of accuracy. \n\n**Weaknesses:**\n1. The authors may want to provide a rigorous proof for Theorem 4.7. Some weaknesses are as follows.\n    1. In the proof, the authors make the assumption of GNN's width and depth, which is not mentioned in Theorem 4.7.\n    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.\n    3. The authors may want to provide the lower bound of the depth of GNNs.\n    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?\n2. 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.\n3. The authors may want to compare the time complexity and runtimes of AMP with those of synchronous GNNs.\n4. The authors claim that AMP can propagate messages over large distances in graphs without the corresponding theoretical analysis.\n\n[1] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations (ICLR), 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject