Agent-based Graph Neural Networks
Authors: Karolis Martinkus
Pál András Papp
Benedikt Schesch
Roger Wattenhofer
Venue: ICLR 2023 poster (2023)
Keywords: Graph Neural Networks
GNN
Graph Classification
Expressive Graph Neural Networks
Sublinear algorithms

Abstract: We present a novel graph neural network we call AgentNet, which is designed specifically for graph-level tasks. AgentNet is inspired by sublinear algorithms, featuring a computational complexity that is independent of the graph size. The architecture of AgentNet differs fundamentally from the architectures of traditional graph neural networks. In AgentNet, some trained \textit{neural agents} intelligently walk the graph, and then collectively decide on the output. We provide an extensive theoretical analysis of AgentNet: We show that the agents can learn to systematically explore their neighborhood and that AgentNet can distinguish some structures that are even indistinguishable by 2-WL. Moreover, AgentNet is able to separate any two graphs which are sufficiently different in terms of subgraphs. We confirm these theoretical results with synthetic experiments on hard-to-distinguish graphs and real-world graph classification tasks. In both cases, we compare favorably not only to standard GNNs but also to computationally more expensive GNN extensions.

Published as a conference paper at ICLR 2023
AGENT-BASED GRAPH NEURAL NETWORKS
Karolis Martinkus', Pál András Papp', Benedikt Schesch', Roger Wattenhofer! 'ETH Zurich *Computing Systems Lab, Huawei Zurich Research Center
ABSTRACT
We present novel graph neural network we call AgentNet, which is designed specifically for graph-level tasks. AgentNet is inspired by sublinear algorithms, featuring computational complexity that is independent of the graph size. The architecture of AgentNet differs fundamentally from the architectures of traditional graph neural networks. In AgentNet, some trained neural agents intelligently walk the graph, and then collectively decide on the output. We provide an extensive the- oretical analysis of AgentNet: We show that the agents can learn to systematically explore their neighborhood and that AgentNet can distinguish some structures that are even indistinguishable by 2-WL. Moreover, AgentNet is able to separate any two graphs which are sufficiently different in terms of subgraphs. We confirm these theoretical results with synthetic experiments on hard-to-disse to-distinguish graphs and real-world graph classification tasks. In both cases, compare favorably not only to standard GNNs but also to computationally more expensive GNN extensions.
INTRODUCTION
Graphs and networks are prominent tools to model various kinds of data in almost every branch of science. Due this, graph classification problems also have a crucial role in wide range of applications from biology to social science. In many of these applications, the success of algorithms often attributed to recognizing the presence or absence of specific substructures, e.g. atomic groups
in case of molecule and protein functions, or cliques in case of social networks [10] 77 21 23, 66) 5].
This suggests that some parts of the graph are "more important" than others, and hence it is an essential aspect of any successful classification algorithm to find and focus on these parts.
In recent years, Graph Neural Networks (GNNs) have been established as one of the most prominent tools for graph classification tasks. Traditionally, all successful GNNs are based on some variant of the message passing framework [3] 69). In these GNNs, all nodes in the graph exchange messages with their neighbors for a fixed number of rounds, and then the outputs of all nodes are combined, usually by summing them 27 52. to make the final graph-level decision.
It is natural to wonder if all this computation is actually necessary. Furthermore, since traditional GNNs are also known to have strong limitations in terms of expressiveness, recent works have developed range of more expressive GNN variants; these usually come with an even higher computational complexity, while often still not being able to recognize some simple substructures. This complexity makes the use of these expressive GNNs problematic even for graphs with hundreds of nodes, and potentially impossible when we need to process graphs with thousands or even more nodes. However, graphs of this size are common many applications, e.g. if we consider proteins 665 72), large molecules 79 or social graphs 7
In light of all this, we propose to move away from traditional besssag-passiing and approach graph- level tasks differently. We introduce AgentNet a novel GNN architecture specifically focused on these tasks. AgentNet is based on a collection of trained neural agents, that intelligently walk the graph, and then collectively classify it (see [T. These agents are able to retrieve information from the node they are occupying, its neighboring nodes, and other agents that occupy the same node. This information is used to update the agent's 's state and the state of the occupied node. Finally, the agent then chooses a neighboring node to transition to, based on its own state and the state of with very naive policy, an agent can already
the neighboring nodes. As we will show later, recognize cliques and cycles, which is impossible with traditional GNNs.
Correspondence ma wii.kss@thh..c. ch.

---

Published as a conference paper at ICLR 2023
Graph triangles!
Node Update
Neighborfood Agrogation
I've been there 3 stops ago!
triangle!
didn't see a triangle.
Me neither
Agent Update
Agent Transition
I keep secing these nodes!
(d)
Figure I: AgentNet architecture. We have many neural agents walking the graph (a). Each agent at every step records information on the node, investigates its neighborhood. and makes a probabilistic transition to another neighbor (b). If the agent has walked a cycle (c) or clique (d) it can notice.
One of the main advantages of AgentNet is that its computational complexity only depends on the node degree, the number of agents, and the number of steps. This means that a specific graph problem does not require the entire graph to be observed, then model can often solve it using less than operations, where n is the number of nodes. The study of such sublinear algorithms is popular topic in graph mining [35 26 it is known that many relevant tasks can be solved in sublinear manner. For example, our approach can recognize if one graph has more triangles than another, or estimate the frequency of certain substructures in the graph
sublinear time!
AgentNet also has a strong advantage in settings where e.g. the relevant nodes for our task can be easily recognized based on their node features. these cases, an agent can learn walk only along these nodes of the graph, hence only collecting information that is relevant to the task at hand. The amount of collected information increases linearly with the number of steps. contrast to this, standard gressage-passing GNN always (indirectly) processes the entire multi-hop neighborhood around each node, and hence it is often difficult to identify the useful part of the information from this neighborhood due oversmoothing oversquashing effeets [46] 2 caused by exponential increase in aggregated information with the number of steps. One popular approach that can partially combat this has been attention 770 it allows for soft gating of node interactions. While approach also uses attention for agent transition sampling, the transitions are hard. More importantly, these agent transitions allow for the reduction of computational complexity and increase model expressiveness, both things the standard attention models do not provide.
RELATED WORK
2.1 GNN LIMITATIONS
Expressiveness. Xu et al. [75] and Morris et al. 153 established the equivalence of message passing This spurred research into more expressive
GNNs and the first order Weisfeiler-Lehmal (1-WL)
GNN architectures. Sato et al. (64] and Abboud et al. I proposed to use random node features for unique node identification. As pointed out by Loukas [48] message passing GNNs with truly unique identifiers are universal. Unfortunately, such methods generalize poorly to new graphs [59] Vignac
al. 71 propose propagating matrices order equal the graph size as messages instead of vectors to achieve permutation equivariant unique identification scheme. Other possible expressiveness. improving node feature augmentations include distance encoding [45), spectral features [4] or orbit counts [1I. However, such methods require domain knowledge to choose what structural information to encode. Pre-computing the required information can also be quite expensive [ An alternative to this is directly working with higher-order graph representations [53] 51I. which can directly bring &-WL expressiveness at the cost of operating on k-th order graph representations. To improve this, methods that consider only part of the higher-order interactions have been proposed [55 56)
2

---

Published as a conference paper at ICLR 2023
Alternatiely. extensions to message passing have been proposed, which involve running GNN on many, slightly different copies of the same graph to improve the expressiveness [59] g 80
19: 62
Papp & Wattenhofer [58] provide a theoretical expressiveness comparison of many of these GNN extensions. Geerts & Reutter [3] propose the use of tensor languages for theoretical analysis of GNN expressive power. Interestingly enough, all of these expressive models focus mainly on graph-level tasks. This suggests these are the main tasks to benefit from increased expressiveness.
Scalability. As traditional GNN architectures perform computations on the neighborhood of each node, their computational complexity depends on the number of nodes in the graph and the maximum degree. To enable GNN processing large graphs Hamilton et 37 and Chen et al. [33] propose randomly sub-sampling neighbors every batch or every layer. To better preserve local neighborhoods
Chiang et al. [16] and Zeng et al. 78 use graph clustering, to construct small subgraphs for each batch. Alternatively, Ding et al. [2 quantize node embeddings and use a small number of quantized vectors to approximate messages from out-of-batch nodes. In contrast to our approach, these methods focus on node-level tasks and might not be straightforward to extend to graph-level tasks, because they rely on considering only a predetermined subset of nodes from a graph in a given batch.
2.2 SUBLNNER ALGORITHMS
Sublinear algorithms aim to decide graph property in much less than n time, n being the number of nodes [35]. It is possible to check if one graph has noticeably more substructures such as cliques,
eycles, even minors than another graph in constant time B1 30 6). It is also possible to estimate
counts of such substructures in sublinear time 26 14 7 All of this can be achieved either by
performing random walks [14] 7 or by investigating local neighborhoods of random nodes [3] 30 6].
We will show that AgentNet can do both, local investigations and random walks.
2.3 RANDOM WALKS IN GNNS
Random walks have been previously used in graph machine learning to construct node and graph representations [61| 36 67 32 57). However, traditionally basic random walk strategies are used, such choosing between dept-first or breath-first random neighborhood traversals [36]. It has also been shown by Geerts 32 that rundom-walk-aa
GNNs are at most as expressive as 2-WL test; we will show that our approach does not suffer from this limitation. Toenshoff al. (67 have proposed to explicitly incorporate node identities and neighbor relations into the random walk trace to overcome this limitation. AgentNet is able to automatically learn to capture such information; moreover, our agents can learn to specifically focus on structures that are meaningful for the task at hand, as opposed to the purely random walks of (67]. As an alternative, Lee et al. [44] have proposed to learn graph walking procedure using reinforcement learning. In contrast to our work, their approach is not fully differentiable; furthermore, the node features cannot be updated by the agents during the walk, and the neighborhood information is not considered in each step, which both are crucial for expressiveness.
3 AGENTNET MODEL
The core idea of our approach is that graph-level prediction can be made by intelligently walking on the graph many times in parallel. To be able to learn such intelligent graph walking strategies through gradient descent we propose the AgentNet model (Figure []. On a high level, each agent a is assumed to be uniquely identifiable (have ID) and is initially placed uniformly at random in the graph. Upon an agent visiting node v at time step & (including the initial placement), the model performs four steps: node update, neighborhood aggregation, agent update, and agent transition.
First, the embedding of each node v; that has agents a, E A(wx) on it is updated with information from all of those agents using the node update function fu- To ensure that the update is expressive enough, agent embeddings are processed before aggregation using function Φa-co:
of fo
Σ
if IA(w;)) > 0 else of
EA(s:)
Next, in the neighborhood aggregation step, current neighborhood information is incorporated into the node state using the embeddings of neighhoring nodes 1j E N(vx). Similarly, apply function
3

---

Published as a conference paper at ICLR 2023
(u))- the neighbor embeddings beforehand, to ensure the update is expressive:
o/ In
Σ ()E)(
(N(o)-
if IA(r=)] 0 else v/-
These two steps are separated so that during neighborhood aggregation a node would receive infor- mation about the current state of the neighborhood and not its state in the previous step. The resulting node embedding then used to update agent embeddings so that the agents know the current state of the neighborhood (e.g. how many neighbors of v; have been visited) and which other agents are on the same node. With V(a;) being a mapping from agent O₂ to its current node:
d: fa (at (ovo)))
Now the agent has collected all possible information at the current node it is ready to make transition to another node, For simplicity, we denote the potential next positions of agent o, by (a:) (a))))))) U var First, probability logits zu,t estimated for each of E N (a,). Then this distribution is sampled select the next agent position V(a)):
2a. fp (at, uf) for N
V(a:) + GuumeeSSofmaa (fāa, for Na))))
As we need a categorical sample for the next node position, we use the straight-throug Gumbel softmax estimator [41 50) In the practical implementation,
use dot-product attention [68] to determine the logits - used for sampling the transition. To make the final graph-level prediction, pooling (e.g. sum pooling) is applied on the agent embeddings, followed by readout function (an MLP). Edge features can also be trivially incorporated into this model. For details on this and the practical implementation of the model see Appendix C There also discuss other simple extensions to the model, such as providing node count to the agents or global communication between them. In Appendix D we empirically validate that having all of the steps is necessary for good expressiveness.
Let's consider Simplified AgentNet version of this model, where the agent can only decide if it prefers transitions explored nodes, unexplored nodes, going back the previous node, or staying on the current one. Such an agent can already recognize cycles. If the agent always prefers unexplored nodes and marks every node visits, which it can do uniquely agents are uniquely identifiable, will know once it has completed a cycle (Figure (c)). Similarly, if for e steps an agent always visits a new node, and it always sees all the previously visited nodes, it has observed a c-clique (Figure [ (d)). This clique detection can be improved if the agent systematically visits all neighbors of a node going back to v after each step, until a clique is found. This implics that even this simple model could distinguish the Rook's ss 4x4 and Shrikhande graphs, which are indistinguishable by 2- 2-WI but can be distinguished by detecting 4-cliques. we have more than one agent they could successfully run such algorithms in parallel to improve the chances of recognizing interesting substructures.
4 THEORETICAL ANALYSIS
We first analyze the theoretical expressiveness of the AgentNet model described above. We begin with the case of a single agent, and then we move on to having multiple agents simultaneously. The proofs and more detailed discussion of our theorems available in Appendices A andd B
4.1 EXPRESSIVENESS WITH SINGLE AGENT
We first study the expressiveness of AgentNet with a single agent only. That is, assume that an agent placed on the graph a specific node v. theoretical sense, how much is an agent in our model able to explore and understand the region of the graph surrounding v??
Let us define the r-hop neighborhood of u (denoted (w)) as the subgraph induced by the nodes that are at distance at most from v. One fundamental observation is that AgentNets are powerful
Note that there are two slightly different ways in the literature index the WL. hicrarchy; here we use the so-called folklore variant, where 2-WT. is already much more expressive than 1-WL.. See e.g. [ for details.
4

---

Published as a conference paper at ICLR 2023
enough to efficiently explore and navigate the r-hop neighborhood around the starting node In particular, AgentNets can compute (and maintain) their current distance from v, recognize the nodes they have already visited, and ensure that they move to desired neighbor in each step; this already allows them to efficiently traverse all the nodes in (")).
Lemma 1. An AgentNet can learn to execute a iteratively deepening depth-first search of its r-hop neighborhood, visiting each node of (T) in & S O(r (v)) steps altogether.
We note that in many practical cases, e.g. if the nodes of interest for specific application around can already be identified from their node features, then AgentNets can traverse the neighborhood even more efficiently with depth-first search. We discuss this special case (together with the rest of the proofs) in more detail in Appendix A
While using these methods to traverse the neighborhood around v. an AgentNet can also identify all the edges between any two visited nodes; intuitively speaking, this allows for a complete un- derstanding of the neighborhood in question. More specifically, if the transition functions of the agent are implemented with sufficiently expressive method (e.g. with multi-layer perceptrons), then we can develop a maximally expressive AgentNet implementation, i.e. where each transition function is injective, similarly to GIN in a standard GNN setting [75]. Together with Lemma] [ this provides a strong statement: allows for an AgentNet that can distinguish any pair of different r-hop neighborhoods around v (for any finite and A, where A denotes the maximal degree in the graph).
Theorem 2. There exists injective implementation of an AgentNet (with < O(r (v)I) steps) which computes a different final embedding for every non iimiioooorppi r-hop neighborhood that can occur around node
This already implies that with sufficient number of steps, running AgentNets from node be strictly more expressive than a standard GNN from v with r layers, or in fact any GNN extension that is unable to distinguish every pair of non-isomorphic r-hop neighborhoods around v. In particular, the Rook's 4x4 and Shrikhande graphs are fundamental examples that are challenging to distinguish even for some sophisticated GNN extensions; an AgentNet can learn to distinguish these two graphs in as little as e = 11 steps. Since the comparison of the theoretical expressiveness of GNN variants is a heavily studied topic, we add these observations as an explicit theorem.
Corollary The AgentNet approach can also distinguish graphs that are not separable by standard GNNs or even more powerful GNN extensions such as PPGN [ST], GSN [T]] or DropGNN (59].
Intuitively. Theorem 2 also means that AgentNets are expressive enough to learn any property that a deterministic function of the r-hop neighborhood around e. In particular, for any subgraph H that is contained within distance of one of its nodes to. there is an AgentNet that can compute (in O(r (N"(w)) steps) the number of occurrences of H around a node v of G. i.e. the number of times H appears as an induced subgraph of G such that node v takes the role of to-
Lemma 4. Let H be any subgraph of radius at most around a specific node uo- Then there exists an AgentNet that can compute the number of occurrences of H around a specific node v G. Gf
For several applications, cliques and cycles are often mentioned as some of the most relevant substructures in practice. As such, we also include more specialized lemmas that consider these two structures in particular. In these lemmas, we say that an event happens with high probability (w.h.p) if an agent can ensure that it happens with probability p for an arbitrarily high constant p < 1.
Lemma 5. There exists AgentNet that can count cliques (of any size) in l = 2 A 1 steps, but there is no AgentNet that can count them w.h.p. in less steps.
Lemma 6. There exists an AgentNet that can count c-cycles in E = O(r (o (N)( steps, but there is no AgentNet that count them w.h.p. in less than 2 [N"(w)) 1 steps.
In general, these theorems will allow frequently in some graph G, than in another graph G2. then we can already distinguish the two graphs with only few agents (we formalize this in Theorem 2 for the multi-agent setting).
show that if specific subgraph appears much more
5

---

Published as a conference paper at ICLR 2023
Note that all of our theorems far rely on the agents recognizing the structures around their starting point v. This is a natural approach, since in the general case, without prior knowledge of the structure of the graph, the agents cannot make more sophisticated (global) decisions regarding the directions in which they should move in order to e.g. find a specific structure.
However, another natural idea is to consider the case when the agents do not learn intelligent transition strategy at all, but instead keep selecting from their neighbors wniformly at random. We do not study this case in detail, since the topic of such random walks in graphs has already been studied exhaustively from a theoretical perspectíve. In contrast to this, the main goal of our paper is to study agents that learn to make more sophisticated navigation decisions. In particular, clever initialization of the Simplified AgentNet transition function already ensures in the beginning that the movement of the agent is more of conscious exploration strategy than a uniform random walk.
Nonetheless, we point out that many of the known results on random walks automatically generalize the AgentNetts setting. For example, previous works defined random walk access model [17 (0 where an algorithm begins from a seed vertex and has very limited access to the graph: it can (i) move to a uniform random neighbor, (ii) query the degree of the current node, and (iii) query whether two already discovered nodes are adjacent. Several algorithms have been studied in this model, e.g. for counting triangles in the graph efficiently [7]. Since an AgentNet can execute all of these fundamental steps, it is also able to simulate any of the algorithms developed for this model.
Theorem 7. An AgentNet can simulate any algorithm developed in the random walk access model.
4.2 MULTIPLE AGENTS
We now analyze the expressiveness of AgentNet with multiple agents. Note that the main motivation for using multiple agents concurrently is that it allows for a significant amount of parallelization hence making the approach much more efficient in practice. Nonetheless, having multiple agents also comes with some advantages (and drawbacks) in terms of expressive power.
We first note that adding more agents can never reduce the theoretical expressiveness of the AgentNet framework; intuitively speaking, with unique IDs, the agents are expressive enough to disentangle their own information (i.e. the markings they leave at specific nodes) from that of other agents.
Lemma 8. Given an upper bound b on agent IDs, there is an AgentNet implementation that always computes the same final embedding starting from v, regardless of the actions of the remaining agents.
This shows that even if we have multiple agents, they always have the option to operate independently from each other if desired. Together with Theorem this allows us to show that if two graphs differ significantly in the frequency of some subgraph, then they can already be distinguished by constantly many agents. More specifically, let G and G2 be two graphs can be traversed in steps as discussed above, and let (w denote the number of nodes in G, that incident to at least one induced subgraph H.
nodes, let H be subgraph that
Theorem 9. Let G1 and G2 be graphs such that yvu (G1) (i 2 8. for some constant 8 >>> 0. Then already with E 0(1) agents an AgentNet can distinguish the two graphs whh.p.
In general, Lemma g shows that if the number of steps l is fixed, then we strictly increase the expressiveness by adding more agents. However, another (in some sense more reasonable) approach to compare two AgentNet settings with the same number of total steps: that is, if we consider an AgentNet with l distinct agents, each rumning for E steps, then is this more expressive than an AgentNet with a single agent that runs for k l steps?
We point out that in contrast to Lemmas 6 (which hold in every graph), our results for this question always describe a specific graph construction, i.e. they state that we can embed subgraph H in a specific kind of graph G' such that it can be recognized by a given AgentNet configuration, but not by another one. A more detailed discussion of the theorems is available in Appendix B
On the one hand, it is easy to find an example where having single agent with k steps is more beneficial: if we want to recognize a very large structure, e.g. a path on more than l nodes, then this might be straightforward in single-agent case, but not possible in the case of multiple agents.

---

Published as a conference paper at ICLR 2023
Lemma 10. There is subgraph H (of radius larger than E) that can be recognized by single agent with k- l steps, but not by k distinct agents running for E steps each.
On the other hand, it is also easy to find an example where the multi- case is more powerful at distinguishing two graphs, e.g. if this requires us to combine information from two distant parts of the graph that are more than k. f steps away from each other.
Lemma 11. There is a pair of non- -oniisomopphic graphs (of radius larger than k E) that can be distinguished by k distinct agents with steps each, but not by a single agent with k. E steps.
However, neither of these lemmas cover the simplest (and most interesting) case when we want to find and recognize a single substructure of small size, i.e. that has a radius of at most f. In this case, one might first think that the single-agent setting is more powerful, since it can essentially simulate the multi-agent case by consecutively following the path of each agent. For example, if two agents a1, 02 meet at node while identifying structure in the multi-agent setting, then a single agent could first traverse the path of (1, then move back to U and traverse the path of 02 from here.
However, it turns out that this is not the case in general: one can design construction where subgraph H can be efficiently explored by multiple agents, but not by single agent. Intuitively, the main idea is develop a one-way tree structure that can only be efficiently traversed in one direction: in the correct direction, the next step of a path is clearly distinguishable from the node features, but when traversing the opposite way, there are many identical deetical-looking neighbors in each step.
Theorem 12. There exists a subgruph H that can be recognized w.h.p. by agents in steps, but it cannot be recognized by 1 agent in & steps (for any constant c).
Finally, we note that as an edge case, AgentNets can trivially simulate traditional message-passing GNNs with n agents if separate agent is placed on each node, and performs the node update and neighborhood aggregation steps, while never transitioning to another node. However, if the problem at hand requires such an approach, it is likely more reasonable to use traditional GNN instead.
5 EXPERIMENTS
In this section, we aim to demonstrate that AgentNet is able to recognize various subgraphs, correctly classifies large graphs if class-defining subgraphs are common, performs comparably real-world tasks to other expressive models which are much more computationally expensive, and can also successfully solve said tasks better than GIN while performing much fewer than steps on the graph.
In all of the experiments, we parameterize all of the AgentNet update functions with 2-layer MLPs with skip connection from the input to the output. For details on model implementation see Appendix[C] Unless stated otherwise, to be comparable in complexity to standard GNNs (e.g. GIN) we use the number of agents equal the mean number of nodes n in the graphs of given dataset. We further discuss the choice of the number of agents in Appendix]] [] For details on the exact setup of all the experiments and the hyperparameters considered see Appendix D
5.1 SYNTHETIC DATASETS
First, to ensure that AgentNet can indeed recognize substructures in challenging scenarios we test it on synthetic GNN expressiveness benchmarks (Table There we consider three AgentNet versions. The random walk AgentNet, where the exploration is purely random. The Simplified AgentNet, where each agent only predicts the logits for staying on the current node, going the previous node, or going to any unexplored any explored node, and finally the full AgentNet, which uses dot-product attention for transitions. Notice that the random walk AgentNet not able to solve the 2-WL. task, as random walk is comparatively limited and samplc-intensive exploration strategy. The other two AgentNet models successfully solve all tasks, which means they can detect cycles and cliques. Since the simplified exploration strategy does not account for neighboring node features, in the rest of the experiments we will only consider the full AgentNet model.
Secondly, to test if AgentNet is indeed able to separate two graphs when the defining substructure is prevalent in the graph we perform the ablation in Figure 22] We see that indeed in such case AgentNet can successfully differentiate them, even when observing just a fraction of the graph (n >> k. 6).
7

---

Published as a conference paper at ICLR 2023
Model
4-CYCLES 50
CIRCULAR SKIP LINKS [S
2-WL
GIN 75
50.0 +0.0
10.0 +0.0
50.0 =0,0
GIN with random features 664 1
99.7 +0.4
95.8 +2.1
92.4
SMP 7
100.0 10.0
100.0 10.0
50.0 10.0
DROPGIN
59
100.0 =0.0
100.0 =0,0
100.0 =0.0
ESAN S
100.0 00.0
100,0 00,
100,0 =0.0
1-2-3 GNN
53
100.0 0.00
100.0 0.00
100.0 00.0
PPGN 51
100.0 =0.0
100.0 =0.0
50.0 =0.0
CRAWL 66
100.0 -0.0
100.0 -0.0
100.0 10.0
RANDOM WALK AGENTNET
100.0 =0.0
100.0 00,0
50.5 #44.5
SIMPLIFIED AGENTNET
100.0 10.0
100.0 10.0
100.0 10.0
AGENTNET
100.0 00.0
100.0 00.0
100.0 +0.0
Table I: Evaluation datasets unsolvable by 1-WL (GIN), Regularized 4-cycles (59 dataset tests if a given graph has 4 cycle, while Circular Skip Links dataset [T5) asks classify the graph by its eycle length. 2-WL dataset contains Rook 4 x and Shrikhande graphs which are both co-spectral and indistinguishable by 2-WL, but the Rook graph has 4-cliques, while the Shrikhande graph does not. We highlight the best test scores in bold. AgentNet is able to detect both cycles and cliques. * ESAN can only solve the 2-WL dataset with the edge deletion policy, but not the other three policies. & Interestingly enough, while 1-2-3 GNN should have similar expressive power the 2-WL test, solves this task. This is likely due to the fact that while all possible triplets are needed to simulate 2-WL test, in practice only subset of them considered reduce computational complexity (53]
2.0
32
75
78
79
80
79
79
79
79
78
Number of steps
16
72
76
79
79
79
79
79
79
78
Accuracy
0.8
Constant fraction of subgraphs Constant number subgraphs
0.7
(b)
8-
69
74
77
78
79
79
79
80
80
0.6
66
71
76
78
79
79
0.5
66
69
75
78
79
79
0
200
400
600
800
1000
2
8
16
32
Graph
Number agents
(a)
(d)
Figure 2: AgentNet sublinearity studies. First, create synthetic dataset with variable density of the subgraphs of interest (a). The dataset contains ladder graphs (b) and ladder graphs with some cells replaced by crosses (c). The task is differentiate the graphs. We always k 16 agents, f 16 steps, and gradually increase the ladder graph size from 16 nodes to 1024 nodes. We either preserve the crossed-cell density of 0.5 (blue line) or we always have only in the ladder graph, independent of its size (red line). If the subgraph of interest is common in the graph (blue line) AgentNet successfully learns to differentiate the graphs, even when l < n (gray line). Secondly, to test how this transfers to real-world tasks we test AgentNet on a large protein DD dataset using a different number of agents and steps (d). Grey-bordered cells mark configurations that perform fewer node visits than GIN (k e < 4 n)) and black-bordered cells mark configurations that perform less than n node visits (k < n)). GIN achieved 77% accuracy on this task. AgentNet outperforms it, even when using just node visits and matches GIN while using only node visits.
erossed cells
5.2 REAL-WORLD GRAPH CLASSIFICATION DATASETS
To verify that this novel architecture works well on real-world graph classification datasets, following Papp et network datasets 10s of nodes per graph on average, we also include one large-graph protein dataset (DD) 23 and one large-graph social dataset (REDDIT-BINARY (76). In these datasets, graphs have hundreds of nodes on average and the largest graphs have thousands of nodes (Appendix We compare our model to GIN, which has maximal 1-WL expressive power achievable by standard pesssage-passing
we use three bioinformaties datasets (MUTAG, PTC, PROTEINS) and two social and IMDB-MULTD) [76. As graphs in these datasets only have
GNN 75 and more expressive GNN architectures, which do not require pre-computed features As you in Table 2 our novel approach usually outperforms least half
59 g
53 51 67
8

---

Published as a conference paper at ICLR 2023
Model
Complexity
MUTAG
PTC
PROTEINS
IMDB-B
IMDB-M
DD
RDT-B
GIN 75
O(n E)
89.4 +5.6
64.6 #7.0
76.2 #2.8
75.1 +5.1
52.3 +2.8
76.9 =3.7
92.4 =2.5
DropCiN
O(r.n-
90.4 17.0
66.3 18.6
76.3 16.1
75.7 #4.2
51.4 42.8
76.4
89,9 =1.7
ESAN g
O(r-n-
91.1 +7.0
69.2 :6,5
77.1 #4.6
77.1 #2.6
53.5 #3,4
81.2 223
93.3 =13
1-2-3 GNN
53
Oin :
88.8 17.00
64.0 16.0
76.8 #3.7
73.6 22.2
51.1 #3.8
00M
00M
PPGN ST
Oix
90.6 +8.7
66.2 +6,5
77.2 =4.7
73 =5.8
50.5 +3.6
00M
00M
CRAW1
67
[ m) -f)
90.4 17.1
68.0 26.5
76.2 #3.77
73.4
47.8 1:3.9
78.3 =5.
92.8 =2.2
N-ACENTNET
Ol6)
89.4 10.9
66.6 +7.6
75.1 #3.4
+3.9
$2.3 +3.9
67.4 =3.0
77.9 =3.0
AGENTNET
O(k-
93.6 288.6
67.4 4:5,9
76.7 #3.22
75.2 #4.6
52.2 #3.88
80.1 =2.7
94.2 =1.
Rank
1st
3rd
4th
3rd
3rd
2nd
1st
Table 2: Graph classification accuracy (%). DropGIN and ESAN models use r x O(n) versions of each graph, which makes them of quadratic complexity in practice. We set & z for AgentNet models to have a comparable setting to GIN. We also compare it to a l-AgentNet, which uses only one agent and cannot visit the whole graph. The state-of-the-art random walk model CRAWL computes k = random walks, that are m = 50 steps long at every layer. We report the best result achieved by any of the different model versions. PPGN has different versions and ESAN has different versions. f Originally 1-2-3 GNN used slightly different evaluation setup. We re-trained it to follow the same experimental setup as the other baselines (75 (see Appendix D). All other results come from the respective papers or were trained using the original setup and code.
of the more expressive baselines. It also compares favorably to CRAWL [67]. the state-of-the-art random- handom-walk-aae walk-based model in out of the 7 tasks. Even the AgentNet model that uses just a single agent matches the performance of GIN, even though in this case the agent cannot visit the whole graph, as for these experiments we only consider f E (8, 16] (Appendix (D and using only one agent reduces expressiveness. Naturally, 1-AgnetNet performance deteriorates on the large graphs, while AgentNet does very well. The higher-order methods cannot even train on these large graphs on a 24GB GPU. To train the ESAN and DropGIN models them we have to only use 5% of the usual n different versions of the same graph [8]. For DropGIN, this results in a loss of accuracy. While ESAN performs well in this scenario, it requires lengthy pre-processing and around 68GB to store the pre-processed dataset on disk (original datasets are < 150MB), which can become prohibitive we need to test even larger graphs or larger datasets (Appendix H
To test in detail how AgentNet performance depends on the number of agents and steps in large real-world graphs we perform an ablation on the DD dataset (Fig- ure 2d.. We see that many configurations perform well, even when just fraction of the graph is explored. Es- pecially when fewer than agents are used (n =s 284).
OGB-M
Model
Validation
Test
GIN 75
82,32 +0.90
75.58
#1.40
GIN + Virtual node 75
84.79 =0.68
77.07
#1.49
CRAWL 67
83.44 =0.96
77.78
+0.87
ESAN 8
84,28 =0.90
78.00
#1.42
The previous datasets do not use edge features. As mentioned in Section B. this straightforward ex- tension (Appendix C.. We test this extension on the OGB-MolHIV molecule classification dataset, which uses edge features (38). In Table 3 we see that AgentNet performs well in this scenario. In Appendix
AGENTNET
84.77 #0.92 78.33 #0.69
Table 3: Test and validation ROC-AUC (%) on the OGB-MolHIV dataset with edge fea- tures. *Best result achieved by any version.
F Fland you
how the model performs on even more tasks. In Appendix K we also show that
AgentNet indeed can make use of the defining subgraphs in real-world datasets.
CONCLUSION
In this work, we presented novel AgentNet architecture for graph-level tasks. We provide an extensive theoretical analysis, which shows that this architecture is able to distinguish various substructures that are impossible to distinguish with traditional GNNs. We show that AgentNet also brings improvements to real-world datasets. Furthermore, if features necessary to determine the graph class are frequent in the graph, AgentNet allows for classification in sublinear or even a constant number of rounds. To our knowledge, this is the first fully differentiable GNN computational model capable of graph classification which inherently has this feature, without requiring explicit graph sparsification it learns which substructures worth exploring on its own.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
[1] Ralph Abboud, ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization, pp. 2112-2118, 2021.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. International Conference on Learning Representations, 2021.
[3] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Banchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1xXiv:1806.01266. 2018.
[4] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Líò. Directional graph networks. International Conference on Machine Learning, pp. 748-758. PMLR, 2021.
[5] Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 16-24, 2008.
[6] Itai Benjamini, Oded Schramm, and Asaf Shapira. Every dinor-closed property of sparse graphs is testable. Advances in mathematics, (23(00)2000-220 2010.
[7] Suman Bera and C Seshadhri. How count triangles, without seeing the whole graph. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 306-316, 2020.
[8] 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 Learning Representations, 2022.
[9] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pictro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34:2625-266 2021.
[10] Christian Borgelt and Michael R Berthold. Mining molecular fragments: Finding relevant substructures of molecules. 2002 IEEE International Conference on Data Mining, 2002. Proceedings., pp. 51-58. IEEE, 2002.
[11] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[12] Shaked Brody, Uri Alon, and Eran Yahav. How attentive graph attention networks? In International Conference on Learning Representations, 2022.
[13] Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
[14] Xiaowei Chen, Yongkun Li, Pinghui Wang, and John CS Lui. A general framework for estimating graphlet statistics via random walk. Proceedings of the VLDB Endowment, 10(3): 253-264, 2016.
[15] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances neural information processing systems, 2019.
[16] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen. An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 257-266, 2019.
10

---

Published as a conference paper at ICLR 2023
[17] Flavio Chiericetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi, and Tamás Sarlós. On sampling nodes in a network. In Proceedings of the 25th International Conference on World Wide Web, WWW 16. pp. 471-4814 2016.
[18] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets, Advances in Neural Information Processing Systems, 33:13260-1333 13271, 2020.
[19] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems, 34, 2021.
[20] Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. On estimating the average degree. In Proceedings of the 23rd International Conference on World Wide Web, WWW "14, pp. 795-806, 2014.
[21] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. ceucture-activing relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-777, 1991.
[22] Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John Dickerson, Furong Huang, and Tom Goldstein. Vq-gnn: A universal framework scale up graph neural networks using vector quantization. Advances in Neural Information Processing Systems, 34, 2021.
[23] Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
[24] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint urXiv:2003.009.0
2020.
[25] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022.
[26] Talya Eden, Amit Levi, Dana Ron, and C Seshadhri. Approximately counting triangles in sublinear time. SIAM Journal on Computing, (115):6603-1444 2017.
[27] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference Learning Representations, 2020.
[28] M. Fey, J. G. Yuen, and F. Weichert. Hierarchical inter-message passing for learning on molecular graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
[29] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning Graphs and Manifolds, 2019.
[30] Orr Fischer, Tzlil Gonen, and Rotem Oshman. Distributed property testing for subgraph-freeness revisited. corr, abs/1105.044 00403.. arXiv preprint arXiv: 7705 703.04033, 2017.
[31] Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of excluded subgraphs. In 30th International Symposium on Distributed Computing (DISC 2016), pp. 342-356. Springer, 2016
[32] Floris Geerts. Walk message passing neural networks and second-order graph neural networks. arXiv preprint arXiv:2006.09499, 2020.
[33] Floris Geerts and Juan I. Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference Learning Representations, 2022.
[34] 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), Sydney, Australia, August 2017.
11

---

Published as a conference paper at ICLR 2023
[35] Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017.
[36] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp.
2016.
[37] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, 2017.
[38] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec, Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint urXiv:2005.0068/ 2020.
[39] Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its variants. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533-8537. IEEE, 2021.
[40] John Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52 (7):1757-1768, 2012.
[41] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztiion with gumbel-softmax. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017.
[42] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 3rd International Conference Learning Representations, ICLR 2015, 2015.
[43] Chul-Ho Lee, Xin Xu, and Do Young Eun. Beyond random walk and cerropoiis-hasting samplers: why you should not backtrack for unbiased graph sampling. ACM SIGMETRICS Performance evaluation review, 30(1):319-330
2012. 2012.
[44] John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 1666-1674, 2018.
[45] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 4478, 2020.
[46] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi supervisd learning. In Thirty-Second AAAI conference on artificial intelligence. 2018.
[47] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[48] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference Leurning Representations, 2020.
[49] Andrew Maas, Awni Hanmun, Andrew Ng, et al. Rectifier nonlinearities improve neural network acoustic models. In Proceedings of the 30th International Conference Machine Learning (ICML), Atlanta, Georgia, USA, 2013.
[50] Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A contin- uous relaxation of discrete random variables. In 5th International Conference on Learning Representations, ICLR 2017. Toulon, France, April 24-26, 2017.
[51] Haggai Maron, Heli Ben- Nen-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[52] Diego Mesquita, Amauri Souza, and Samuel Kaski. Rethinking pooling in graph neural networks. Advances in Neural Information Processing Systems, 33:2220-2233 2020.
12

---

Published as a conference paper at ICLR 2023
[53] 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 Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 4602-4609)
2019.
[54] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: collection of benchmark datasets for learning with graphs. ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[55] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33:21824-21840 2020.
[56] Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity-aware germutation-qquivariant graph networks. In ICLR 2022 Workshop Geo- metrical and Topological Representation Learning, 2022.
[57] Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. Advances Neural Information Processing Systems, 33:16211-16221 2020.
[58] Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions. arXiv preprini arXiv:2201.1288/ 2022.
[59] Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. DropGNN: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[60] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. volume 32. 2019.
[61] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
[62] Chendi Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Ordered subgraph aggregation networks. arXiv preprint 120.::2006.11668. 2022.
[63] Raghunathan Ramakrishnan, Pavlo Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
[64] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference Data Mining (SDM), pp. 333-341. SIAM, 2021.
[65] Ben-Ami Sela. Titin: some aspects of the largest protein in the body. Harefuah, 141(7):631-5, 2002.
[66] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488-495, PMLR, 2009.
[67] Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with ld convolutions on random walks. arXiv preprint 102.:::1022087660 2021.
[68] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[69] Petar Veličković. Message passing all the way up. arXiv preprint arXiv: 1009, 2022.
13

---

Published as a conference paper at ICLR 2023
[70] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, In International Conference on Learning Representations (ICLR), Vancouver, BC, Canada, May 2018.
[71] Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. Advances in Neural Information Processing Systems, 13:14143-141555 2020.
[72] Nathan Thompson Wright and Logan C Meyer. Structure of giant muscle proteins. Frontiers in physiology, 4:368, 2013.
[73] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, (12):513-300, 2018.
[74] Ruibin Xiong, Yunchang Yang. Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pp. 10524-10533. PMLR, 2020.
[75] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
[76] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
[77] Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
[78] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020.
[79] Baozhong Zhang, Roger Wepf, Karl Fischer, Manfred Schmidt, Sébastien Besse, Peter Lindner, Benjamin T King, Reinhard Sigel, Peter Schurtenberger, Yeshayahu Talmon, et al. The largest synthetic structure with molecular precision: towards molecular object. Angewandte Chemie, 123(3):763-766, 2011.
[80] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2022.
14

---

Published as a conference paper at ICLR 2023
A PROOFS FOR SECTION 4.1
A.1 INJECTIVE IMPLEMENTATION
The fundamental idea behind developing a maximally expressive AgentNet implementation is to ensure that the functions learned by the agent are injective. A similar proof technique for developing injective GNN implementations has already been applied to analyze the expressive power of standard GNNs 75 and also some GNN extensions [59]; we refer the reader to these papers for more technical details on this proof approach. As in the rest of these proofs, we assume that the range of the node features is a finite set, and we also have a finite upper bound on the maximal degree A of the graph. With an induction, this already shows that after any finite number of time steps I, the range of possible embeddings (of agents or nodes) is still finite.
The main tool we will use is the following: assume we have a finite number of embeddings ho, .... h1-1 E I. and assume for simplicity that they are from the interval (0, 1). Then there exists a function f: (0, - (0, 1) that is injective on its entire domain.; that is, if we have hi..... h, such that hú * h; for at least one i E jo. 1). then [ho..... -,...) + (ho..... .......j -nj-1). 1). One possible way to construct such an f is as follows: we consider the binary representation of each hs, and encode it in the bits of f'hho...,.h h,-))) at positions that are equal to i modulo j. That is, if 21 - + 22 for some 0 S 2/2 < j. then we define the i-th bit of fhe..... h (after the decimal point) to be equal to the 21-th bit of heg (after the decimal point). Note that this function is indeed injective, since for any [hoo....h h)-1); we can uniquely reconstruct all the values ho,... hj-1- Note that the numbers only restricted to the interval (0, 1) for the sake of simplicity; if h, > 1, then bits of h; by alternatingly moving in both directions from the decimal point.
encode the
As such, for any finite number of values, there exists an injective function f that combines these into a single real embedding. Such a function I can be approximated arbitrarily closely with a multi-layer perceptron according to the universal approximation theorem, and hence an AgentNet can also have the theoretical expressiveness to learn any such function.
From here, the concrete design of the injective AgentNet implementation only requires the repeated application of this idea. As a first step, we need to create an injective node update function fo for the single agent case; for this, we encode the values o and a (and for convenience, also the value of f) with the method above. That is, whenever we have either of 1111 + 0f -1 or a'-1 + âr-1 or 1 A i, then our update function will ensure (c a1-1) + (o -1 af-1), As described above, such function fo exists, and hence can be learned by a sufficiently powerful AgentNet.
As next step, the node essentially executes message- message-passing phase around its neighborhood; this can again be done injectively. In particular, the work of (75] describes how to design an injective multiset function, i.c. an aggregation of neighbors that returns different embedding for every possible multiset of neighboring embeddings. We can once again combine this with the embedding of of the node discussed above, creating an fn. that is injective in uf and the multiset vz E N (1:).
In the single-agent case, we can simply select (a = of. since this already contains all the information available to the agent at this point.
Intuitively, the injective implementation means that any decision that can be made by a deterministic algorithm from the same information can also be executed in our setting. In particular, this also holds for the node transition functions: in each step, we can select the transition function fp to model almost any categorical distribution over the closed neighborhood (vo) U ((o)) of the current node Uo. based on the current node state d',, That is, given the desired probabilities π (vy), inverting the softmax function determines the set of required logits, and we need to define fp accordingly. Recall that in the injective implementation, d'., already determines both vf and the multiset of vš in N (vo); hence when defining (a(, uf), we can indeed already determine the set of desired logits from of alone, and assign the appropriate value for each v/-
For categorical distribution æ to be obtainable as a transition function this way, it needs to satisfy two simple properties: (i) I TTu) E (0, 1) for any {vo) U ((g)), and (ii) if U1 U2 has the same current embedding, then x T ) = x (u2). Furthermore, property (i) is also not strict in the sense that probability of ( is desired, then we can also select sufficiently small transition value such that the
15

---

Published as a conference paper at ICLR 2023
probability is essentially 0 after the softmax; that is, if l and A are both finite, then always set (u) small enough to ensure that the probability of executing any of these "O-probability transitions" at any point during the entire E steps is below arbitrary constant As such, the only real restriction on the set of obtainable categorical distributions is that two nodes with the same embedding must receive the same transition probabilities. Since an injective agent ensures that every visited node has different embedding, this only means the following restriction in practice: if to has multiple unvisited neighbors with the same initial node features, then the transition probabilities to these nodes will be identical. If any categorical distribution over the closed neighborhood satisfies this property, then there exists an fp function corresponding to this distribution, and an agent can learn to approximate this.
For completeness, we also introduce a technical modification to our injective agent implementation to ensure that the range of the function fo can never accidentally coincide with any of the (finite) possible initial values of the node features. To do this, we encode one more finite value in the representation of fo (in every j-th bit, as before). Since there are only finitely many possible node features, we can e.g. use the i-th of these extra bits to ensure that that fo is not equal to the i-th possible initial feature (this approach is also known as the "diagonalization method"). This ensures that any node that is not yet visited will have a different embedding than all the already visited nodes.
Finally, let make some simple observations about this injective implementation that can serve as building blocks for our more complex algorithms later. First of all, we note that each node encodes the entire history of the agent from all of the time steps when the node was visited; in particular, a node is aware of each time unit when it was visited by the agent. Furthermore, in each step, an agent can uniquely determine the neighbor of the current node that has arrived from. Also, for each neighbor of the current node, an agent can determine whether it has already been visited or not.
A.2 GRAPH TRAVERSAL METHODS
With the injective implementation discussed above, agents can already learn to intelligently traverse the r-hop neighborhood of their starting node v in the graph. We first discuss the iterative depth- first search approach that provides Lemma and then also comment on the simpler case when a depth-first search is sufficient.
Proof of Lemma 7 Since the agent is not aware of the size and shape of its r-hop neighborhood in advance, it needs to execute an iteratively deepening depth-first search (IDDFS) in the neighborhood to ensure that it discovers all nodes from N (v(v), but only these nodes. The IDDFS algorithm iterates a depth limit d from to and in each iteration, it executes a depth first search from v up to depth d only. This ensures that all the nodes at distance d from V are already identified in iteration d, but no nodes that are farther away from are visited. Note that cannot achieve the same with regular depth-first search with depth limit r: it might happen that some parts of the search tree from node u discarded due to this depth limit, and only find shorter path to u later which shows that the distance from v to these discarded nodes is, in fact, smaller than r.
It is easy to see that an injective AgentNet (as described above) can indeed execute such IDDFS algori algorithm; we just need to select the transition function fp appropriately. Note that the current embedding aj of the agent already uniquely determines the current iteration d that the agent is executing; alternatively, we can also save this current value d' on separate bits when constructing the injective functions of the agent (recall that we can encode any finite number of values with the same approach). This also implies that the current embedding of each node u determines whether u was already visited in iteration d or not. Besides this, the embedding of each (already visited) node determines the distance of u from v: in the iteratively deepening setting, this is simply the index of the first iteration where this node was visited. Finally, when the agent is on a node u, it can determine the predecessor of in the ferth-first search tree of the current iteration: it can consider the first time step É when u was visited in iteration d, and the predecessor of u is the node that was visited in time step (t-1).
Based on these observations, we can describe the transition function fp with the following few simple rules. When the agent is at distance at most (d - 1) from e and there are still neighbors that have not been visited in the current iteration, then we assign a large constant value of c to these nodes in fp- and value of (essentially) ( to all other nodes. When the agent is at distance d from e, or all of its
16

---

Published as a conference paper at ICLR 2023
neighbors have already been visited in iteration d, then the agent moves backward: we set value of c for the predecessor of the current node, and a value of 0 to all other nodes. Finally, if the agent is at and all of its neighbors have been visited in iteration d already, then it begins iteration (d + 1) and sets the value of all neighbors to c (it selects the next neighbor uniformly at random).
Any iteration of the IDDFS traverses depth-ffrst search tree with most (e) nodes; each edge of the tree is traversed at most twice, resulting in at most 2. [N'(v) (u) steps. Since the number of iterations is r, our agent indeed needs f S O(r (u)). We note that in most practical cases, we can even drop the factor r from this expression: e.g. when the graph region around v is a A-regular tree, then
we will have most nodes in (v) at distance exactly from v, and thus all iterations except for the last one will become asymptotically irrelevant.
This iteratively deepening search method is only required because we always need to be aware of the distance of the current node from e in order decide whether we need to explore the graph further in a specific direction. However, in some special cases, we can apply a much more efficient depth- first search (DFS) traversal of the neighborhood; this removes the factor from the required number of steps.
One simple example of such setting is when the connected component of the graph containing is very small. In particular, assume that the entire component only consists of no nodes; while this might be unusual in actual applications, it is relatively frequent in the synthetic datasets that are often used to measure the expressive power of different GNN extensions. For another example, consider applications where the nodes that are important for our purpose have some specific features that make them easy to distinguish from other nodes; in this case, an injective AgentNet can learn to only consider these nodes while processing the graph (i.e. set the transition probability to all other nodes to 0). As such, we can fictitiously remove every from the graph that does not have the appropriate features, and if the connected component of u in the remaining graph (the "interesting part" of the region around v) is relatively small with only no nodes, then we can again restrict our exploration strategy to this subgraph.
In the cases mentioned above, the agent can traverse the entire subgraph of size ny around with depth-first -irst search approach: it becomes unnecessary to maintain the distances from v anymore since the agent traverses the entire connected component anyway. This is much more efficient method in terms of the number of steps, not requiring an extra factor r: the entire connected component around can be traversed in 2 no 3 steps (or in terms of the radius r of the connected component, in 2 [v)) 3 steps). This is because the DFS tree has n4- - 1 edges, each of these is traversed at most twice, and the edges leading to the last discovered node are traversed only once (but for this we can only subtract a single edge in the worst case).
We note that this bound is indeed tight, i.e. even in this DFS-based setting. we cannot explore every neighborhood in é = 2 - no - 4 steps. This also allows us to show that there are subgraphs H of radius r such that no AgentNet can decide w.h.p. in 2 no 4 steps whether H occurs as an induced substructure around v. A concrete example is shown for this in the proof of the negative result in Lemma 5 the neighborhood of interest (that can contain a triangle) in this case consists of no = + A nodes, but it is not possible w.h.p. in 2 no 4 = 4 steps to decide whether has an incident triangle.
A.3 RECOGNIZING STRUCTURES
Given an agent that systematically traverses its neighborhood, we can now consider the claims of recognizing specific substructures.
We begin with the proof of Theorem We point out that in the context of graphs with node features, we when we say that two graphs G₁ 1/, E,) and G2(V,, Eg) are isomorphic, then besides the regular graph-theoren definition of having o: : Vi + V22 such that (11, 02) E E1 = (o(v1), (vz)) Eg. we also require that en and ((0)) have identical features for all 0n E V1.
Proof of Theorem 2 According to Lemma [ there exists an AgentNet that explores every node in the r-hop neighborhood of v; furthermore, during this traversal, the agent also becomes aware of the features of every node in (v), and all edges between pairs of nodes in NT)v) when the second endpoint of the edge is visited. This allows an agent to uniquely identify the entire r-hop
17

---

Published as a conference paper at ICLR 2023
neighborhood around v. More specifically, if injective agent produces the same output embedding for two neighborhoods, then this implies that for the two traversals T1, T2, the following properties must all hold: (i) the nodes visited in the t-th and t'-th steps of Ii are the same node if and only if the nodes visited in the 1-th and 1'-th steps of T2 are the same node, (ii) the (-th visited nodes of Ti and T2 have the same node features, and (iii) the 1-th and ('-th visited nodes of T7 are adjacent if and only if the t-th and t'-th visited nodes of T22 are adjacent. These properties provide clear bijection between the nodes of the two neighborhoods, also preserving node features and edges; this implies that the two neighborhoods are isomorphic.
This shows that an injective AgentNet always assigns a different embedding to non non- -on-isomorppic neighborhoods. However, we also need to ensure that isomorphic neighborhoods, on the other hand, obtain the same embedding. Indeed, with the injective AgentNet described so far, it could easily happen that two nodes have isomorphic neighhorhoods, but an agent traverses these neighborhoods in different order, and hence computes a different embedding in the two cases.
In order to resolve this, we only need to observe that there is function assigning every possible IDDFS traversal to the isomorphism class of ("), and a sufficiently powerful agent can learn to apply this function on the final embedding. More specifically, let G denote the set of all different (non-isomorphic) graphs of radius at most 7 (and degree at most A) around v. We have already seen that if two r-hop neighborhoods are non-isomorphic, then our injective agent always produces different final embedding for them. This implies that the final embedding uniquely determines the graph induced by N (v),,, i.e. there exists well-defined function 4/1- IR - 9 which assigns the graph induced by (v) to every possible final embedding generated by the agent. Finally, consider a function 2/2 + I. which assigns the numbers {1, {I,.... [9]] to the graphs in in arbitrary order. Then vi = 1/2 dh is simply a function 3 I + R. and according to the universal approximation theorem, it can be learnt e.g. by an MLP implementation. Applying this function e on the final embedding (in the last step of the traversal) ensures that the final output of the agent describes the
isomorphism class of N (v), and hence two starting nodes receive the same final embedding if and only if their r-hop neighborhoods are isomorphic.
Proof of Corollary 3 Corollary 3 follows easily from Theorem and the fact that there are known limitations to the expressiveness of each of the listed GNN extensions. In the case of standard GNN, two small cycles of different lengths are already simple example of indistinguishabiliy [75] For the 2- 2L algorithm (and hence equivalently, PPGN), the Rook 4x4 and Shrikhande graphs are a well-known example on 16 nodes that are not distinguishable. For GSN and DropGNN, the analysis of (58) describes an example construction that cannot be distinguished without preprocessing structures of size O A) removing ((A) nodes. Hence for any fixed parametrization of GSN or DropGNN (preprocessing substructures of fixed size, or removing a fixed number of nodes), there exists pair of neighborhoods that cannot be distinguished by GSN or DropGNN. These example
graphs have A + nodes, so they can still be distinguished by AgentNet in E 2- A - 1 steps. [7
Lemma follows easily from Theorem
Proof of Lemma The r-hop neighborhood around already determines the number of occurrences of any structure H of radius at most r from That is, if we denote the set of all possible non- isomorphic r-hop neighhorhoods around v by N",, then there is a deterministic function fn N N that describes the number of occurrences of H for each neighborhood in Nr, Theorem 2 shows that we can learn an injective function fA N - IR that describes the final embedding of an agent; hence we can define the function g fu o f that assigns the appropriate number of occurrences of H to any final embedding. This function g can also be learned according to the universal approximation theorem, and hence an AgentNet can learn to execute this function in its last step.
We discuss these substructure-related claims for cliques and cycles explicitly, which are both important substructures for specific applications. Note that the positive parts of the lemmas are deterministic, ie. given specific number of steps. there is agent implementation that always (with probability 1) returns the desired number of subgraphs as its final embedding; meanwhile, the negative parts claim that if the number of steps is small, then agent can return the correct number w.h.p.
18

---

Published as a conference paper at ICLR 2023
13
UI
13
Figure 3: Example graphs G1 (left) and G2 (right) for the negative result in Lemma
Proof of Lemma S AgentNet can learn to mark the starting node v, then transition to an unvisited neighbor of each odd step, and then move back to e in even steps. This allows it to visit all neighbors of in 2 A - steps, and identify the entire 1-hop neighborhood of v as discussed in Lemmal I Since every clique containing is completely included in this induced subgraph, this AgentNet can compute the number of cliques incident to e for any clique size.
As special case of the IDDFS discussed before (with r 1), an injective
On the other hand, if f s 2- A 2, then the agent does not have enough steps visit every neighbor of u; as such, it might not detect a clique the last unvisited neighbor of is contained in it. For concrete example, consider two graphs where v has degree 3 (and also A 3); in G1, we have edges {(v, vı) (v, v2), (u, va). (2), (1a, vg)} i.e. a triangle and a path of length 2 incident to v, while in G2, we have edges {1V, U1), (v, U2), (v, Us), (v1, vf), (V2, v/),, (V3, v))), i.e. three paths of length 2 incident to 27 see Figure for an illustration. Assume that all nodes begin with identical node features.
In the first step, any agent can only move to a uniform random neighbor u of v (staying at the current node is not reasonable action in this setting). In either of the graphs, the agent observes the same situation after the first step, so it must move to the other neighbor of u with fixed probability pr. and back to e with probability (1 pi). Note that if pl 2 1. and if the current node u happens to be Uy (this has probability }), then the agent cannot distinguish the two graphs in the remaining steps (with probability at least {).
If the agent returns to in the second step, then in the remaining two steps, it gains the highest possible amount of information by visiting another neighbor u' of u and then moving to the other neighbor of u'. However, once again, if V3 (this has probability z). then the agent cannot distinguish the two graphs from the path has traversed. Thus (1 - pi) Z implies a failure probability of least again. This shows for any choice of pt. the agent fails to distinguish the two graphs with an arbitrarily high constant probability (i.e. it higher than ))
Proof of Lemma 6
A cycle of e nodes has radius [ so according to Lemma 4 an AgentNet can indeed count the number of incident cycles of length in O(c- | (v)]) steps.
On the other hand, if the | |hhop neighborhood of v consists only of paths of length [ starting from and we need to visit each of these paths to see if the endpoints of two paths are adjacent (thus forming a c-cycle), then é = 2 .V (v)l 1 2 steps can indeed be required: intuitively, we need to visit each path starting from up distance [ J. and then return on each occasion except for the last one. For a concrete example, we can consider the graphs G1,G2 from the proof of Lemma again: a triangle is a cycle for e = 3, we have 2. IN I (v) - 1 = 4 - - 2 5 in this case, and we have already seen that that AgentNet can distinguish these graphs w.h.p. in less than 5 steps.
We note that for tight lower bound in this case, we would also need incorporate a further factor r = ] (to account for the iterative phases of the IDDFS); however, this would require a much more complex construction, since here intuitively we would also need to ensure that leaving out any of the iterative phases would result in an incorrect traversal of the neighborhood.
A.4 RANDOM WALK ACCESS MODEL
Finally, we have already outlined the proof of Theorem 7 in Section 4.1
19

---

Published as a conference paper at ICLR 2023
Proof of Theorem 7 The injective version of AgentNet can easily carry out all three fundamental steps of the random walk access model. Moving to a uniform random neighbor in each step can be implemented by simple transition function fp that assigns the same value to each neighbor. Besides this, the agent ensures (by encoding the time step 1) that it leaves a unique node embedding at each of the visited nodes, so injective AgentNet can recognize any of these nodes (or in fact, any possible subset of these nodes) in all subsequent steps, In this case, an injective AgentNet can ensure in general that in the i-th step (for any finite i), it computes an embedding that is injective in the (i) degree of the current node and (ii) set of previously visited nodes that are adjacent to the current node. That is, in the injective implementation, after any number of steps, the agent is aware of the degree sequence observed so far and the adjacency relations between all the already discovered nodes. Such an agent already in possession of all the information that can be queried the random walk access model. As such, the output of any algorithm in this model can be expressed as deterministic function of the final embedding of the agent, and hence due to the universal approximation theorem, an agent can approximate this output if implemented by sufficiently expressive method (c.g. multi-layer perceptron).
B PROOFS FOR SECTION 4.2
B.1 SIMPLER CLAIMS IN THE MULTI-AGENT SETTING
We now discuss the theorems on expressiveness with multiple agents. We begin with Lemma g only requires a further extension of the injective implementation provided earlier.
which
Proof of Lemma g The lemma assumes that each agent has a unique ID from 1 to some known upper bound b (alternatively, case, we can modify the injective construction described in Appendix A to ensure that the i-th agent only uses the bits at positions i modulo b for its own encoding. This means that when summing the embeddings of different agents in fe, we again have an injective function, even all the agents visit the same node at the same time. As such, any single agent can determine its final embedding based on only its own part of the node embeddings, and disregard the embeddings of other agents.
can also select the agent IDs from predetermined finite set). In this
After this proof, Theorem Pholly Jonly requires a few more steps. Note that the rest of the claims in this section discuss the ability of AgentNets (with specific k and E) to distinguish two graphs G and G2. To formalize this concept, we say that an AgentNet can distinguish G1 and G2 if it returns different output (in the final readout function) for the two graphs w.h.p., i.e. it returns a given value a1 w.h.p. in case of G1. and another value ag w.h.p.in case of G2. We say that it cannot distinguish two graphs this is not possible, i.c. there is a constant upper bound on the success probability.
Proof of Theorem 9 From Lemmas 4 and 8 it follows that there exists an AgentNet implementation such that if an agent is placed on node v, then computes a final embedding of 1 if is incident to a copy of / in G, and 0 otherwise (note that we can include it in the last transition function to also convert the injective outputs into these more convenient 0-1 values). Consider an aggregation of the agents that simply sums up their final embeddings; this results in a final embedding that equals to the number of starting nodes v that were incident to a copy of H.
Let 7/- = (G.) for E (1,2), and / = 2 (71 - 72). Recall that 71 7-7'201--2 and >' - 22 2 The starting point of the agents is chosen uniformly random and independently from each other; hence if we run an AgentNet with & agents in G., then each of these will output 1 with probability 7/2 and 0 otherwise, and thus our final embedding (after aggregating the agents) will follow binomial distribution X with parameters l and %.s We can then use Chernoff bound to upper bound the probability that the sum falls below (above) 2/ k in G₁ (G2, respectively). If the value is above 7 in G and below n/ l in G2 w.h.p., then a simple classification function that compares the sum of embeddings to this value 7² 1: can already distinguish the two graphs.
(G.))
Let p denote the constant probability we require for our definition of w.h.p. Let c == 2-78 fixed E (1,2)); then for the expected value E.X of the binomial distribution, we have 6 EX
8 (for
20

---

Published as a conference paper at ICLR 2023
6 2-7 %/- k = 2 k. According the Chernoff bound, we have
22 Pr (IX - EX| 2 e EX)= S 2 - - 2 8 2.
While this looks like a complicated expression, ,-,," 7/8 is simply a constant in our case. This implies that for any choice of p. there exists high enough constant value k such that the expression on the
8²
right-hand side is smaller than (1p)). By our choice of e, having |X - EX| < E. <..EX implies
X 7 in G1 and X < <> in Gz. This means that the probability of having X <> in G1 is at most (1 - p). and similarly, the probability of having X 2 7 in G2 is at most (1 p).
We next present the proofs of Lemmas 10 and settings.
11 that compare the single-agent and multi-agent
Proof of Lemma TQ A simple example for such a subgraph H is a path on nodes; let us assume for simplicity that the nodes have single feature, and the value of this feature is 0 for all nodes of the path.
Consider graph G1 that consists of such a path H, and é further nodes (with feature 1) that are all connected to the first node of the path. If n is large enough (and & is smaller, e.g. a constant), then w.h.p. all of the agents will start to reach the other end of the path.
node with feature 1. As such, in l steps, neither of them is able
This means that if we consider another graph G2 where the only difference is that the last node of the path also has feature 0, then any AgentNet with & agents fails to distinguish the graphs w.h.p. In contrast to this, single agent with at least l 1 steps can easily learn to walk the other end of the path (by simply moving to the neighbor with feature 1 in the first step, and then always to the unmarked neighbor of feature 1), and hence distinguish the two graphs.
Note that if we want a version of this construction that has A = O(1), we can simply replace the nodes added to the beginning of the path by a complete (A - -ary tree of depth h: the root node is the first node of the path, and every node (apart from the leaves) has (A - 1) children. By assigning a different feature to each level of the tree, we can ensure that wherever an agent begins in the tree, it can learn to directly walk to the root in at most h steps (we discuss these one-way way trees in detail later). Note that we have h S Ollog n) in this graph. Hence if we select & = h, then we can again ensure w.h.p. that all nodes start in the tree, and hence cannot reach the end of the path after l steps. In contrast to this, with k steps (assuming k 2 2), a single agent can always reach the end of the path and hence distinguish the two graphs
Proof of Lemma 77 Let both GJ and G2 consist of two identical connected components of equal size; in the first component, both graphs have a node feature of 0 on all nodes, whereas, in the second component, the node features are 0 and 1 in G2 and G2. respectively. If having multiple components are undesired, we can also connect the two components with path of length it e + (with node features of, say, 2).
In the case of a single agent, the agent appears in the first part of the graph with probability (almost) and is hence unable to distinguish the two graphs w.h.p., regardless of its actions.
However, in the case of a sufficiently high number of agents & (i.e. if 1 - 2* > is satisfied, and assuming that the connecting path is an asymptotically irrelevant part of the graph). at least one of the agents begins in the second component; in this case, they can easily recognize node with feature 1, and hence distinguish the two graphs.
B.2 PROOF OF THEOREM 12
It remains prove the more involved Theorem 12 regarding the comparison of the two settings. For completeness, we first state the theorem in a more precise form:
Theorem 12 (detailed). There exists a pair of non-isomorphic graphs G1, G2 and connected subgraph A such that
H appears as subgraph in G1, but not in G2,
21

---

Published as a conference paper at ICLR 2023
there exists AgentNet with 2 agents and steps that can distinguish the two graphs w.h.p. by walking through the nodes of H in G1.
there exists no AgentNet with agent and e. e steps (for any constant c) that can distinguish the two graphs w.h.p.
That is, our proof here is more surprising construction than that of Lemma 11 the whole graph has a diameter & only, and there is specific structure H that distinguishes the two graphs, but single agent is unable to navigate this structure. We first present the key idea to develop such constructions, which we call one-way trees.
Definition 13. A one-way tree is complete (A 1) -ary tree of depth h, i.e. rooted tree where every node (apart from the leaves) has exactly (A - 1) children. The single node feature of every node in the i-th level is the integer i (for E h)).
Note that the node degrees are still bounded by A this way. The key idea of the tree is that an AgentNet can easily lean to walk towards the root in this tree, but finding a specific leaf is not possible without traversing significant portion of the tree.
Lemma 14. Consider a one-way tree, select one of its leaf nodes u, and let us add an extra neighbor (with feature (h 1)) this leaf u.
There exists an AgentNet implementation which, if placed u initially, can reach the root of the tree in 8 steps.
There exists no AgentNet implementation which, if placed on the root node initially, can reach u in i ( - 1)th steps with probability larger than
Proof. If an agent is placed at u initially, then in each step. it can easily distinguish the parent node of its current node in the tree, since this is the only node that has a smaller feature. That if the agent learns to transition to the node with feature h in the first step, with feature (h - 1) in the second step, and so on, then it can reach the root of the tree in l steps without ambiguity (i.e. with probability 1).
On the other hand, when starting from the root, the agent has way to distinguish the different children of the current node from each other. The agent can only proceed by visiting each of the (A - 1)th leaves of the tree sequentially to find the leaf which has neighbor with feature (h + 1). In (A - 1)a steps, the agent can visit strictly less than half of the leaves, so it will only find u with probability less than +
With this tool, we can already move on to the proof of Theorem 12
Proof of Theorem 12 Let be constant parameter (to be discussed later), and consider node with feature 0. Let us consider distinct one-way trees of depth hn (we will call these primary Irees), and connect the root of all these trees v. So far do this in both of our graphs. Then in the case of G2. let us further select one of the leaf nodes Uo in one of the primary trees, and attach the root node of another way tree of depth h2 (called the secondary tree) to Vo. In contrast this, in G1. we select an arbitrary leaf node in every primary tree, and we attach another one-way tree of depth l2 (a secondary tree) to each of these leaf nodes.
For our substructure H, let us select path on 2- h1 + 3 nodes, such that the node features on the path (in order) are (1, h1, h2 1, .... 2, 0, 2....... ...,.... h1 1, h1, 1). Note that this structure appears in G we start from root node of secondary tree, then move to the attached leaf of the primary tree, then to the root of the primary tree, then to v, then to the root of another primary tree, then all the way down to another Icaf node that has secondary tree attached, and finally to the root of this secondary tree. On the other hand, H does not appear as a substructure in G2, since vo is the only node in the graph which has feature h and has neighbor with feature 1.
We select h2 significantly larger than h2; with this, we can ensure that with arbitrarily high probability, the agents always placed in one of the secondary trees (even in G2, since b is only constant). Furthermore, note that if we have k = 2 agents, then with probability different secondary trees initially in G. That is, by selecting the constant b large enough, we can
they are placed into
22

---

Published as a conference paper at ICLR 2023
ensure that the two agents are placed into two distinct secondary trees with probability of at least p (i.e. w.h.p.). Finally, we select = h2 + h11
In the case of 2 agents, the agents can learn to always move to the root of the trees discussed in the proof of Lemma 14 first to the root of the secondary tree, and then to the root of the primary tree. In l steps, both agents can reach v. In the case of G1, if the two agents begin in different secondary trees, then they only meet at node U; in G2, they will always already meet at the root of the single secondary tree in the graph. Since the agents can learn to check if they share their location with the other agent in a given step, they can easily distinguish these two cases. Hence they can separate the two graphs w.h.p.: in G1 they are correct with probability at least 1o2 2 p. and in G2 they are correct with probability 1.
However, a single agent is unable to do the same. It can walk to node e in l steps in either of the graphs, but from there it cannot decide if there exists another secondary tree attached to the graph in one of the other primary trees. More specifically, according to the second part of Lemma [4] the agent cannot find another secondary tree with probability larger than 1 in 2 (A 1)a1 steps, so ensure this when choosing the value
if 1 (A 1)aa > c. l (for any given and A 2 3. of h1), then the agent only finds a copy of H with probability 1 at most, even in G₁ where such subgraph exists. Hence the agent encounters this situation (not finding another secondary tree) with a probability of at least in both graphs. This implies that it cannot distinguish the two graphs w.h.p.: whichever classification (G1 or G2) the agent assigns to this situation, it is wrong in one of the two graphs with a probability of at least 3.
Note that if we want an example for Theorem 12 where the two graphs have the same number of nodes (e.g. to extend it to the case when the agents are aware of n), need to adjust it slightly. We can define Gi to consist of b independent copies of our original G1. Now both graphs contain b secondary trees. Since h2 is significantly larger than h1, their number of nodes is essentially equal: that is, we can add a small independent component G to our original G2 in order to ensure that G¹ and G¹2- = G2 UGJ E (A- nodes).
have the same size (i.e. G is just an arbitrary graph on (b - 1)-
ensure that G is asymptotically irrelevant part of G² i.e holds with an arbitrarily high constant probability that neither of the agents is placed within G.. Now given these graphs G¹ and G2z, a single agent is still unable to distinguish the two cases, since they observe the same situation in both graphs with a probability of at least 1 However, when 2 we have two agents, in Gi2 they meet w.h.p. only at v, whereas in G¹. they always meet either already at the root of the secondary tree, or not at all; hence we can distinguish the two graphs.
By choosing h2 much larger than h1,
C MODEL IMPLEMENTATION
In this section, we will discuss all aspects of the practical implementation of our model and its possible extensions. The model is implemented using PyTorch [60] and PyTorch Geometric (29
C.1 GENERAL NOTES AND INITIALIZATION
We use 2-layer MLPs to parameterize all of the model update functions (node update fe, neighborhood aggregation fn. agent update fa) and the different inputs are concatenated. We use a Leaky ReLU [9 activation function with a negative slope of 0.01. As you will see below, we use skip connections for both node and agent embeddings. This necessitates the use of Layer Normalization (LN) for the MLP inputs. This makes each MLP Pre-LN residual block 74]. Both agents and nodes have I--dimensional embedding vectors.
To ensure starting node embeddings are of the correct dimension and that their sum is injective we first pre-process all node features with an MLP. Since for the majority of the graphs we consider we expect the agents to observe a large fraction of the graph, we process all nodes once in parallel. To stick to the strictly sub-linear setting the model can be modified to only process node embeddings the first time they are observed.
"Code is available at httpppp://ggtttbbb.omm/
23

---

Published as a conference paper at ICLR 2023
As we need our agents to be uniquely identifiable, we use it learnable h--dimensional embedding vectors, which are used as the starting agent state. We initially place agents uniformly at random on the graph.
C.2 MODEL STEPS AND POSSIBLE EXTENSIONS
Let's now see, how the four model steps performed upon visiting node we described in Section are implemented in practice. Note that the same functions (MLPs) are used for every agent. However, because agents have different embeddings, the functions can produce different outcomes for different agents.
Here, we will also show how the model can be extended with edge features and global communication between the agents. In practice, we always include global agent communication. If the given dataset does not make use of edge features, functions & -o) and Pa-+u are set to identity. As MLPs are universal function approximators, pre- vious MLP can already directly approximate (u)) and 0a-te. thus do not lose expressiveness by excluding them [75]. One could also imagine, that providing the agents with the total number of nodes in the graph could help. If the task, for example, is to estimate the density of triangles in the graph, by observing just fraction of it. Such conditioning can be trivially achieved by including n. as input to every update function. However, in our experiments, we did not consider such augmentation.
simplified model where the pre-aggregation update
Node update. As discussed earlier we use skip connection. If we have edge features, then Φa-tr includes both the agent state and the edge cay it took to arrive at the current node da-ve (a) Faz) = LeakyReLU (LinearLayer (LN (a)-1 .Cay)
)a,))). )) In this case, we use a negative slope of 0.2. If there
are no edge features Pa-vo (a) Cay) =
of = + fo
E
f-1 U
Σ EA(s)
Oo-eo (d) eaa))
if [A(w))] > 0 else of
we want to have global information between the agents, we can include mean of their embeddings Eojev aj another input to fu. As all of the subsequent operations make use of the current node state v/. this global information can impact every other update function. Note that since k fixed, this mean is also injective.
To ensure all of these sum pooling operations do not cause value explosion and training problems but retain their expressiveness we implement them as mean scaled by the log of summand count. This is also true for the neighbor aggregation.
Neighborhood aggregation. In the same fashion, skip connection is used, while d is either identity or a linear layer followed by non-linearity, depending on whether the graph has edge features or not, E -v used denote an edge from node by node eq. This results in GIN-like convolution [75] with a skip connection:
of -
ot +
Σ (E.(
dN( (1/ Coy..))))).)))
if |A(
0 else v/-
Agent update. Similarly, the agent update is straightforward and can take into account the edge ea. the agent used to reach the current node if edge features are used:
a = o + fa (ai " Eas)
Agent transition. First, let us consider the Simplified AgentNet. In this case, for each agent a; we track which nodes By have been explored by it 2(a,, vy) E [0, 1). Every time step we decay the values x = 0.9 x and set the values for the current nodes V(a,) of all of the agents a, E A to aaa, V(a:)) 1. We can
these exploration values construct the simplified transition
24

---

Published as a conference paper at ICLR 2023
function fas- Using agent embedding MLP g(a)) produces four logits [gp. 9c. 9e. gul g(a)). respectively for the previous node, the current node, explored nodes and unexplored nodes. Then, for each neighboring node, we determine its final logits weighted sum of these four values. To check if a given node "i was the agent's dg previous node V(=(a;) we use an indicator variable va,=v=>(a.)> Another indicator variable checks if the node is the agent's current node 1 =V.)( The explored and unexplored node logits ge and Ia are interpolated using the node's exploration value x(0;, Vj):
fps (o), u)) 9p(a.) -0,=v- + gc((a))))) (1 V(.)) t tc xlas 15) -a (a(( x(;; Uy)),
2e,+o fps (a. 0J) for of (
To ensure efficient training in the beginning we want as many agents as possible to observe the defining subgraphs. This requires exploration. Unfortunately, random walks are sample inefficient and require many steps to even walk whole simple connected component e.g. a cycle. It is known, that just preventing the random walk from backtracking already greatly increases the sample efficiency [43] In the same vein, we initialize the learnable bias of the g(a)) output layer such that [9p. 9c, 9c= 9u. F [0, 10,11,0,5
0,.5) 5] and the model is initially biased to focus on the yet unexplored nodes. Note that in principle one can also restrict g(af) to be just set of learnable global bias parameters that do not depend on the agent to produce an even simpler model.
For the full AgentNet, we use dot- dot-product attention fp to determine the next node, where the query vector Q(a)) is linear projection of the agent embedding and the key vector (vf uf. ev,-v,) is linear projection of the source node embedding, target node embedding, and any edge features.
fp (af. u)) Q(at)² K(vf, v/,, Cny-var (ey->o.)
Vh
To still ensure that the exploration is efficient at the beginning of the training, combine dot-product attention with values produced by the Simplified AgentNet transition function fps- this case, the transition logits 9p. Ic- 9e, and Iu are just global learnable bias parameters that are independent of the agent and are initialized the same way as before:
Za; bk0 = fps (at, v/)) + fp of) for Na;:).
The resulting logits -ay are used to sample node from the neighborhood using straight-through Gumbel Softmax:
V(a:) +- GumbelSoftmax (fza,-10 for (a))))
To ensure the gradients flow through the Gumbel Softmax sampling, we interpret its output as sparse one-hot vector (where only the Is are present). We use the resulting agent -> node adjacency matrix for agent pooling in the node update step and for selecting the appropriate node in the agent update step, thus multiplying the 1s carrying the gradients with the correct embedding vectors.
C.3 READOUT
As we have stated in Section 3 agent embeddings are pooled together to make the final graph-level decision. In practice following Xu al. (75] we pool agent embeddings after each agent update step and sum the individual step predictions to make the final prediction:
dr = do (at)
0 E fo
Σ de max (or for a, _EA))
a,EA
Here do is 2-layer MLP used to project agent embeddings before the pooling. We use both mean and max pooling because in theory there could be two kinds problems, respectively: problems where agents collectively need decide how commonplace certain features and problems where it is sufficient that just one agent finds class-defining feature. As the final readout fo we use simple linear layer.
25

---

Published as a conference paper at ICLR 2023
C.4 SIME-STEP CONDITIONING
Technically. the agents are able to track time themselves, as the model is injective and they act every time step. However, make the task easier for the model, we condition all of the update functions (node update f.. neighborhood aggregation fn. agent update fa) and the readout function do on the current time step. We achieve this by adding the Transformer sinusoidal position (time step) embedding [68] to the inputs of each function (MLP).
C.5 POSSIBLE MODEL SIMPLIFICATIONS
We implemented the model to be flexible as possible and to match the theoretical analysis. However, the resulting model performs quite a few operations every step. We could simplify it at a loss of some expressiveness. For example, node update and neighborhood aggregation steps can be merged, but this will cause the neighborhood aggregation to see the neighbors as they were in the previous time step. Similarly, the agent update step could be merged into this unified update step, if we are content with producing the same delta update for every agent that is on the same node. Even the agent transition probabilities could be incorporated in this unified step for example we would model the node aggregation after the GATv2 12] convolution and would use the final attention head to produce transition probabilities for every edge. The same transition probabilities would then be used by every agent. Naturally, this would reduce the model's ss expressiveness, but it would result in simpler and fully parallelized model. However, in this work, we aimed to provide an expressive, theoretically motivated model and show that it works well in practice. We leave the investigation of various model simplifications for future work.
D EXPERIMENTAL SETUP
For AgentNet in all of the tasks, we AdamW optimizer [47 with a weight decay of 0.1. We set the initial learning rate to 10-4 and decay it over the whole training to 10-11 using a cosine schedule. We also clip the global gradient norm In all of the cases, Gumbel-Softtax temperature is to as this has been suggested as a robust choice when the distribution has only a few categories [50]
D.1 SYNTHETIC DATASETS
Expressiveness benchmarks. To ensure all of the baseline models as well as the different AgentNet versions have fair shot at solving the given tasks we perform a generous grid search for all of them. We consider batch size E (50, 300} and hidden units {64, 128} and learning rate e {0.001, 0.0005, 0.0001}. For AgentNet we set number of agents kt = n (16 for 4-Cycles and 2- WL, 41 for Circular Skip Links) and consider E {16, 64). For other GNN architectures, E {4,8 4, 3) as they tend to perform worse with high depth. On top of this for AgentNet we consider the number of agents & E (2,n} these problems should be solvable even with few agents. In fact, we did observe that having k = n agents can make the model convergence slower, and for 2-WL dataset results in mean accuracy of 98 + 2%. We train each configuration using 10 random seeds and report the mean and the standard deviation of the best configuration after 10 thousand training steps. For the baseline models, we use the same training setup as for AgentNet. The baselines themselves were chosen as the most expressive models among their class of expressive GNNs. PPGN [I represents the higher-order GNNs and matches 2- in expressive power, GIN with random features [64] 1 represents non-equivariant node identification, SMP [71 represents the equivariant node identification scheme, while DropGNN (59 represents the models that use many different
also include
versions of a graph to make prediction 59 g 19
As described in Appendix C.2 the AgentNet and the Simplified AgentNet use initial attention weights biased for exploration. We also tested these models these synthetic benchmarks without this bias and they still successfully solved the task. However, we kept this bias in the other experiments due to the theoretically better sample complexity.
Subgraph density ablation. As discussed in Figure 2 we set A = 16. é = 16, use 128 hidden units and a batch size of 200 and train using 10 random seeds for 10 thousands steps. We report the mean and the standard deviation of accuracy at the end of the training. While such large batch
26

---

Published as a conference paper at ICLR 2023
size and large number of hidden units are not necessary for this task, we aimed to make sure these hyperparameters are large enough to rule out any training or capacity issues in the results of this ablation study.
D.2 REAL-WORLD GRAPH CLASSIFICATION DATASETS
TU datasets. We follow the evaluation setup by Xu et al. 75 as was done by all of the baseline models. We perform a 10-fold cross-validation and report the mean and the standard deviation. line with baseline models, we train for 350 epochs, and for each of the datasets we perform a grid search over the batch size E {32, 128). hidden units E {32, 64, ]28} and number of steps E {8, 16). We always set the number of agents to the mean number of nodes in the graphs of the corresponding dataset (see Table 4 As REDDIT-BINARY has some very high-degree nodes with thousands of neighhors (Table 4 this node at the same time and compute their transition probabilities. To avoid this, for REDDIT-BINARE we use k = 350 agents instead of 430 and consider E (4,8). For the DD dataset, we use the usual setup, as it does not have such high-degree nodes. Neither DropGNN [59] nor ESAN & or CRAWL 667 were trained on DD (DropGNN also wasn't 't trained on REDDIT-BINARY), thus we trained them using the original code and hyperparameter tuning.
cause memory issues when many agents end up on the same high-degree
[3
As authors of CRAWL 67 do not describe the hyperparameter search used, based on the hyperparam- eters they report in the paper, for CRAWI. we perform grid search over the batch size E {10, 100), hidden units E {50, 100} and dropout E (0.0, 0.5). We train all of the TU datasets not reported in the original paper for 350 epochs. Otherwise, the original code base is unchanged.
We also re-trained 1-2-3 GNN (53] to follow the experimental setup by Xu et al. (75]. We use the original architecture 6 including the layer counts and similar hyperparameter search as used for our model and by Xu et al. (75). The search is performed over the batch size E {32, 64), the hidden unit count {16, 32, 64, 128) and dropout ratio E {0.0, 0.5). The model is trained with Adam optimizer [42]. a learning rate of 0.001, and no weight decay as done originally [53]. We used a learning rate
decay of 50% every 50 epochs done by Xu et al. (75). We found this schedule to perform slightly better than the original decay on plateau used by Morris et al. (53)
OGB. We follow the standard evaluation setup proposed by Hu al. [38. Similarly to the previous graph classification tasks, we set k to mean number of nodes (n s 26), considered number of steps E {8, 16). batch size E {32, 64) and hidden units {64, 128]. We train the model with 10 random seeds for 100 epochs, select the model with the best validation ROC-AUC and report the mean and the standard deviation. The best setup proved to be using batch size of 64, 128 hidden units, and é = 16 steps. In general, over most of the tasks we tested, we observed that a larger batch size tends to improve the AgentNet training and that having around 128 hidden units is good choice, at least with our considered range of values for the number of agents k. When we train AgentNet on OGB-MoIPCBA and OGB-PPA we use these best hyperparameters from OGB-MolHIV, only reducing the number of steps to 8 and setting & 150 for OGB-PPA. Similarly, when we train CRAWL on OGB-MolHIN and OGB-PPA we use the setup used by the authors for [67.. When training ESAN GGB-MoIPCBA and OGB-PPA we also use the authors' setup for OGB-MolHIV g
E GRAPH STATISTICS
In Table 4 we provide the graph statistics for all of the real-world datasets used in Section (.22 As you can see, most of the commonly used TU datasets (54), QM9 (3), OGB-MolHIV and OGB-MoIPCBA have
38 have small graphs. The two large TU datasets we include (DD and REDDIT-BINAEE much larger graphs, especially when considering the largest examples. REDDIT -INDRY also has some very high-degree nodes. To an extent, this is also true for the smaller social- -raph datasets
27

---

Published as a conference paper at ICLR 2023
Dataset
# graphs
Mean # nodes
Max # nodes
Min # nodes
Mean deg.
Max deg.
MUTAG
188
17.9
28
10
2.2
4
PTC
344
25.6
109
2
2.0
4
PROTEINS
1113
39.1
620
4
3.73
25
IMDB-B
1000
19.8
136
12
9.8
135
IMDB-M
1500
13.0
89
7
10.1
88
DD
1178
284.3
5748
30
5.0
19
RDTBB
2000
429.6
3782
6
2.3
3062
OGB-MolliN
41127
25.5
222
2
2.2
10
-oB-MoIPCBA
437929
26.0
332
2.2
NGB-PPA
158100
243.4
300
50
18.62
299
ZINC
12000
23.2
37
9
2.2
4
QM9
130831
18.0
29
3
2.0
5
Table 4: Graph statistics for the real-world datasets.
(IMDB-BINARY and IMDB-MULTI), OGB-PPA 38 included in Appendix H also comprised of larger graphs on average, but lacks very large examples present in DD and REDDIT-BINARY
F PERFORMANCE ON POORLY ALIGNED TASKS
We want check how our model performs in graph-level tasks is not well aligned with. To this end, we test our AgentNet on the molecule property regression task on the QM9 dataset [63] Conceptually, for this molecule property regression task, we probably want to perform message passing on each node every time, we likely need to learn the exact geometric structure of the molecule (position of every node, relative to other nodes, taking charges and bonds into account). This would make AgentNet (with randomly placed agents) not well suited for this task. However, in Table S we can see that AgentNet still outperforms the non-expressive baselines (MPNN and I-GNN) of similar computational complexity while performing comparably to the expressive baselines (1-2-3 GNN, PPGN, DropMPNN, and Drop- Prop-1-GNNN I-GNN) which have much higher computational complexity. This means that even unfavorable tasks it can perform sufficiently well.
Property
Unit
MPNN VA
I-GNN 53
1-2-3 GNN 53
PPGN [1
DropMPNN 59
Drop-I-GNN
50
AgentNer
Debye
0.358
0.493
0.473
0.0934
0.059
0.453
0.254
Bohr'
0.89
0.78
0.27
0.318
0l.173
0.767
0.198
Hartree
0.00441
0.00321
0.003377
0.00174
0.00193
0.00306
0.00183
"LUMO
Hartree
0.00623
0.00350
0.00351
0.0021
0.00177
0.00306
0.0016
Ac
Hartree
0.0066
0,0049
0.0048
0.00229
0,00282
0.0044
0.0025
(179)
Bohr?
28.5
34.1
22.9
3.78
0.392
30.8
1.28
ZPVE
Hartree
0.002166
0,00124
0,00019
0.0013999
0,000112
0.000895
0.000232
Uo
Hartree
2.05
2.32
0.0427
0.022
0.0409
1,80
0.145
G
Hartree
2.0
2.08
0.111
0.0504
0.0536
1.86
0.146
Hartree
0.0294
G
Hartree
2.02
1.94
0.0469
0.24
0.0508
2.12
0.119
C.
calicnol K)
0.42
0.27
0.0944
0.0144
0.0596
0.259
0.0708
Table 5: Mean absolute eтrоrs on QM9 dataset 63
The best- pest-perffoming model is in bold.
For this task, we changed the neighborhood aggregation function fa to align better with the task, by using continuous kernel-based convolutional operator proposed by Gilmer et al. (4 for the message pre-processing function (N( This convolution is used by all of the baseline models we consider. Similarly, to stay close to baseline models we parameterize both the final readout So and the da-to function used for agent aggregation in the node update by 2-layer MLPs. We also the global information exchange between the agents, both the node update step and in the agent update step. Otherwise, the training procedure is the same for the other tasks.
G CONVERGENCE WITH RANDOMNESS
The AgentNet model uses random agent placement, and initially when the model untrained agent transitions also random. This raises natural question: how negatively does this randomness affect
28

---

Published as a conference paper at ICLR 2023
AgentNet training? In Figure we see that the AgentNet always converges, and does this faster than an expressive GIN model, which also depends on randomness. This difference particularly noticeable on harder tasks, such distinguishing two 2-WL indistinguishable graphs.
1.0
0.9
Rccuract
0.8
0.8
0.7
0.6
0.6
with random
0.5
with random
GIN with random features AgentNet
AgentNet
AgentNet
2000 4000 6000 8000
10000
0
2000 4000 6000 8000
10000
0.4
0
2000
4000 6000 8000 10000 Training steps
Training steps
Training steps
(a) 4-CYCLES
(b) CIRCULAR SKIP LINKS
(c) 2-WL
Figure 4: Convergence test accuracy as a function training steps for AgentNet and GIN with random features hard synthetic expressiveness benchmarks. AgentNet always converges and does so faster than GIN with random features, especially on harder tasks, such as 2-WL. The curves correspond to the best of hyperparameters from Table experiments.
In this context, it is also worth noting, that for all of the OGB and TU dataset experiments we used the standard number of training epochs (100 for OGB and 350 for TU datasets). This means that the competitive results seen in Tables 2 and do not require extended training to counteract the randomness.
H ADDITIONAL REAL-WORLD EXPERIMENTS
In this section, we provide additional experiments on other graph classification tasks from Open Graph Benchmark (38. OGB-MoIPCBA dataset is larger dataset for multi-class molecule classification and OGB-PPA a classification dataset of ego-graphs from a protein-protein association network. These ego graphs
bit larger and have around 243 nodes average. In Table you can see that AgentNet noticeably outperforms the GIN baselines, while on the small OGB-MoGi MolICAA its performance is in-between GIN and GIN with virtual node. The big gap in performance between GIN and GIN that uses a virtual which connects all other nodes, suggests that this task might depend on more global features. As diseussed in Appendix F we expect AgentNet perform bit worse on tasks where the global structure is more important than local structure.
OGB-MoIPCBA (AP)
OGB-PPA (Acc)
Model
Validation
Test
Validation
Test
GIN
75
23.05 =0.27
22.66
10.28
+1.07
68.92 +1.00
GIN virtual node 7
27.98 =0.25
27.03
+0.23
66.78 #1.05
70.37 +1.07
ESAN
28.46 =0.22
26.64
10.27
00M
00M
CRAWL
67
30.75 -0.20
29.86
10.25
63.66 10.56
70.25 10.52
AGENTNET
26.22 =0.26
25.49 +0.27
67.24 =0.65
72.33 +0.62
Table 6: Test and validation average precision (%) on the OGB-MoIPCBA dataset and accuracy (%) on OGB-PPA datasets. We were unable to train ESAN model on OGB-PPA dataset, as a machine with 256GB of main memory did not have enough RAM pre-process the graphs for training (OOM).
Note that the pre-processed graphs for the much smaller DD dataset (Table 4 already took 68GB of space on disk and required 120GB of main memory to load.
We also test our model on popular ZINC-12H 12K molecular graph regression dataset [24 40 where the models need to predict the constrained solubility the molecule. While this property is more defined by the global structure of the molecule, might not align very well with AgentNet inductive bias (Appendix F). some local features, like cycle counts are important for this metric 24 Originally Dwivedi et al. (24] recommended constraining the models have either 100K or 500k parameters for this benchmark (not baselines state that they follow this). Since our model less parameter efficient, compared standard GNN, due to the of multiple MLPs for every step and concatenation
29

---

Published as a conference paper at ICLR 2023
of various embeddings input to those MLPs, chose to the 500k parameter budget. This corresponds to an embedding size of 88. In Table [we we can see that this model performs comparably to GIN. If we instead would use embedding size of 128, which would correspond to around 100k parameters for a traditional GNN architecture, such as GIN, AgentNet outperforms quite a few of the and half of the different ESAN [8] configurations which use different sub-graph construction techniques, Some of the baselines depend on explicitly pre-computed structural features, such as cycles 4 28
expressive baselines [51; 71 28
8: 11 9 [7]
2 which are known be important in this task [24]. It is also worth noting that for some models such as GIN the performance on this task becomes worse when the parameter count is increased 24
Model
ZINC (MAB)
PPGN
ST
0,256 +0.054
GIN 75
0,252 #0.017
PNA 18
0.188 +0.004
DGN [4]
0.168 +0.003
HIMP 28
0.151 #0.006
SMP 7
0.138
ESAN (Edge Dropout) g
0,172 #0.005
ESAN (Node Dropout)
0,166 +0.004
ESAN (Ego Graphs) 8
0.107 #0.005
ESAN (Ego Graphs Root ID) 8
0.102 #0.003
GSN 11
0.108 #0.018
CIN-small
9
0.094 +0.004
CIN 9
0.079 #0,006
CRAWL 67
0.085 +0.004
AGENTNET
0.258 #0.033
AGENTNET (Embedding size 128)
0.144 #0.016
Table 7: Mean absolute error on the ZINC 12k dataset.
For the OGB experiments, we used the best hyperparameterss from OGB-MolHIV (batch size of 64, 128 hidden units) and k = 26 agents with E = 16 steps for OGB-MoIPCBA, while k = 150 agents with f steps were used for OGB-PPA, to account for larger graph size and memory constraints. As standard, results are reported over 10 random seeds (38]. For ZINC we used batch size of 128, = 16 steps, k 37 agents, and either 90 or 128 hidden units and train it for 2000 epochs. this case, we use 4 random seeds to report the results, following Dwivedi et al. 24)
I IMPORTANCE OF DIFFERENT MODEL STEPS
In this section, we experimentally verify, that of the model steps as described in Section 3 and Figure [ are necessary. Besides testing Random Walk AgentNet, in Table & we also check how removing the node update step (AgentNet, No Node Update) or neighborhood update step (AgentNet, No Neighborhood Update) affects the model's ability to solve hard synthetic tasks. An important thing to note here is that normally, only nodes that have an agent on them perform the neighborhood update step. Meaning, that even if we remove the node update, there is still information accessible to the model about which neighboring nodes and how many times were visited, but its unknown by which agent. To account for this we also provide model (AgentNet, No Node Update, and Neighborhood Update For All), which skips the node update step and performs neighborhood update for all nodes, not just ones that have an agent on them. As you can see in Table this model is no longer expressive, while the other two versions do still have much better than random accuracy. However, we see that their predictions are no longer perfect. When we not use the neighborhood update it becomes harder for the model to observe the structural information, especially if we want to find cliques, for which we need to check the neighborhood (Figure (d)). Interestingly, AgentNet with no node update does quite well on all tasks, as visit counts can act as surrogate for random features. Although performance is slightly worse than that of GIN with random features on all but the 2-WL task. In Table 9 we graph classification task. It is worth noting that random walk AgentNet achieves quite a close result to the full AgentNet. The reasons for this can be twofold: 1) as we have seen in Table this formulation
that these performance differences also transfer the real-world OGB-MolHH
30

---

Published as a conference paper at ICLR 2023
Model
4-CYCLES 59
CIRCULAR SKIP LINKS L3
2-WL
GIN
75
50.0 40.0
10.0 =0.0
30.0 =0.0
GIN random features 64
99.7 #0.4
95.8 #2.1
RANDOM WALK AGENTNET
100.0 00.0
100.0 00.0
50.5 =4.5
SIMPLIFIED AGENTNET
100.0 00.0
100.0 00.0
100.0 :0.0
AGENINET. Neighborhood Update
11..9
40.6
51.2 =2.0
AGENTNET, No Node Update
92.4 19.7
89.8 18.9
98.9 :0.6
AGENINET. No Node Update and Neighborhood Update For All
50.0 #0.0
10.0 =0.8
49.7 =1.2
AGENTNET
100.0
100.0
100.0
Table & Ablation on how different AgentNet modules influence expressiveness on datasets unsolvable
by 1-WL (GIN). Removing any of the AgentNet steps as described in Section 3 reduces models expressiveness.
OGB-MolHIV
Model
Validation
Test
GIN
82.32 =0.9
+1.40
GIN virtual node 75
84.79 =0688
77.07
+1.49
ESAN [
84.28 =0.90
78.00
+1.42
RANDOM WALK AGENTNET
85.61 =1.29
77.89
11.29
AGENTNET, No Neighborhood Update
84.06 0.76
75.41
+1.41
AGENTNET, No Node Update
84,70 =1.40
76.71
+1.37
AGENTNET, No Node Update and Neighborhood Update For All
84.40 =0.89
75.47 +0.85
AGENTNET
84.77 =092
78.33 +0.69
Table Ablation on how different AgentNet modules influence and validation ROC-AUC (%) on the OGB-MolHIV dataset. *Best result achieved by any version.
is able to recognize cycles, which are one of the most important structures in molecules; 2) as we have k zs n agents the whole graph can be explored even with random walks.
For synthetic tasks in Table g we used the same experimental setup as before (Appendix D.I with grid search over the hyperparameters, while for OGB-MolHIV Table we used the best hyperparameters of the full AgentNet (Appendix D.2)
SELECTING THE NUMBER OF AGENTS
0.78
0.76
Accuracy
0.74
0.72
0.70
AgentNet
0.68
20
60
100
Number of agents
Figure 5: AgentNet ROC-AUC (%) on the OGB-MolHIV when using different number of agents (mean n 26). Gray line marks the mean number of nodes in the dataset.
One of the hyperparameters that could be tuned for the model is the number of agents. To avoid an extensive grid search we normally set the number of agents to the mean number nodes in the dataset. Besides matching the computational complexity of traditional GNNs, that we want that most of the nodes in the graph would be visited by at least some agent. Another reason is that node embedding vectors, where agents record information are of finite size. If we have
reason for this is
31

---

Published as a conference paper at ICLR 2023
many more agents than nodes (e.g. 1000 agents 10 node graph) there could be negative interplay between the agents, where they would corrupt the information stored on nodes by other agents. Choosing to around agents helps avoid such negative interplay. As could be seen from (d), (d), AgentNet performance stable over a wide range of step and agent counts, but ideally, the model should visit the majority of the nodes if one wants maximize accuracy, while further step and agent count increase beyond this does not bring much benefit. Here in Figure 5 we also provide an ablation the effects the number of agents has on AgentNet ROC-AUC on OGB-MolHIV dataset, when using the best hyperparameters from the original experiment (Appendix (.2). We again see that having around n agents is a good choice and that fact, having 2n or 4n agents results in slightly lower performance than when using less than agents. This again suggests that having only a fraction of the nodes active at given time step can be simple way to reduce the computational burden.
Figure
K IMPORTANT SUBGRAPHS
As we have discussed in the main paper, one of the potential benefits of AgentNet is that the agents can learn to prioritize important substructures. Here we investigate the MUTAG dataset [54), which is comprised of mutagenic and non-mutagenic molecules. It is known that good indicator that molecule is mutagenic is the presence of NO, groups [21]. This dataset was constructed such that all molecules have at least one NO₂ group, however, mutagenic molecules still tend have more such groups. In Figure 6 we can indeed see that agents in AgentNet indeed visit such informative subgroups more often.
Figure 6: AgentNet node visitation heat map on test graphs from the MUTAG dataset. The brighter the color, the more often the given node has been visited. Agents prioritize some important substructures (NO2) when they move around the graph.
32


Reviews:
[{"review_id": "jPCmBYefnN", "reviewer": "Reviewer_wMRf", "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": "This work focuses on the design of expressive neural network architecture for  learning on graphs, specifically aimed at improving performance on graph-level tasks. The proposed approach modifies the existing message passing mechanism by introducing the concept of an agent(s) capable of aggregating different types of graph (node, edge) information at subgraph level and then mapping it to graph level output. The key ability of such agent(s) is to perform intelligent walks over subgraphs of size l. The authors argue that such a construction enables sublinearity in learning algorithms that is independent of original graph size. The authors perform theoretical analysis of various properties of this new design in settings with both single and multiple agents. The main theoretical results revolve around the ability of the new approach to distinguish non-isomorphic subgraphs and  to count various substructures such as cycles and cliques. The authors also present and discuss tradeoff scenarios on using single vs multiple agents architectures. Three synthetic datasets are used to test these theoretical properties and compared with various representative baselines focussing on expressivity of graph neural networks. To fully elucidate the gains made in computational complexity and asses the learning performance of the proposed design, the authors present graph classification results on  a suite of real-world graphs and compare it against representative baselines. ", "summary_of_the_review": "The topic of designing expressive graph neural network is very interesting and the authors present an interesting idea towards that direction. The claims of sub-linearity is appealing and the authors show some improvement on classification tasks over representative baselines. However, both the theoretical results and empirical evidence fall short of strongly supporting overall claims of the paper and further the complete miss of discussion with attention based approaches and other related works, both of which informs my current assessment of the paper.  ", "strength_and_weaknesses": "Strengths:\n------------\n+ The topic of designing expressive graph neural networks for learning on graphs has received significant attention recently and if of great interest to community.\n+ The use of meta-level information in the form of agents to gain subgraph-level expressiveness is an interesting idea and has potential for more exploration.\n+ The property of the proposed architecture to provide sublinear computational complexity is very appealing.\n+ The paper shows strong empirical results in the settings considered by the authors  with gains either in performance or in complexity over previous baselines\n+ The ablations with respect to the number of agents and number of steps are very insightful and clearly help to discern if and when the proposed method achieves \ngain. \n\nWeaknesses\n---------------\n\n- While the idea of intelligent walk is interesting, the language of agent is not useful. The single agent case is just a single initialization of an intelligent walk with memory and multi agent case is its extention to multiple walks. It is also confusing to present polling as some sort of global communication, it is just better to present it as aggregation of information from multiple walks. \n- As the transition function is based on attention, this method is clearly very related to attention based graph neural networks. Of course, attention [1] is one way to select a subgraph to focus on for computing a node embedding and thereby graph emebdding. The authors fail to discuss how the proposed  method relates to attention based models. Both theoretical and empirical justification is required. \n- There are several strong works that are relevant to this approach and provide both theoretical and empirical insights [2,3,4]. The authors have neither discussed them nor considered them for comparisons which is a big miss.\n- While the theoretical results attempt to detail different scenarios, many of the theorems and lemmas are more of propositions or insights (e.g. Thm 2, Corollary 3, Lemma 4, thm 7, lemma 8) and it would be good to describe them so.\n- While the approach can be considered independent of graph size in some cases (not really clear if you can always avoid visiting most nodes), it does seem to depend on the degree of nodes and hence large graphs graphs where several (even ~100) nodes may have high degree, this approach will potentially struggle. Can the authors comment on such scenarios\n- More concrete theoretical results relating to the counting of substructures such as cycle and cliques are provided for single agent case. how does this results hold in multiple agent case?  \n- In experiments, using mean number of nodes as number of agents is a very strange and adhoc choice for the proposed approach. It needs better motivation than just matching the complexity of other  works.\n- Interpretations of the results are not always clear or adequate - For figure 2(d) for example, higher number of agents of course lead to fewer node visits per agent and it does not perform better than GIN. So how to interpret these results? The claim of better robustness using Table 3 is very hand wavy and needs lot more investigation. Can the authors comment more on why they think those results indicate robustness to oversmoothing and oversquashing?\n- Empirically, the gains with AgentNet are below marginal and couple this with missing comparisons, the proposed approach has lot of room for improvement. \n\n[1] HOW TO FIND YOUR FRIENDLY NEIGHBORHOOD: GRAPH ATTENTION DESIGN WITH SELF-SUPERVISION, KIM et. al. ICLR 2021\n\n[2] Random Walk Graph Neural Networks, Nikolentzos et. al. Neurips 2020\n\n[3] Walk Message Passing Neural Networks and Second-Order Graph Neural Networks, Gertz et. al. 2020\n\n[4] Ordered Subgraph Aggregation Networks, Qian et. al. June 2022", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_6SmGZQ4lTm", "reviewer": "Reviewer_z2nH", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This work proposes to learn graph-level representations by exploring the graph structure with an agent ---rather than with message-passing schemes. The authors present an extensive theoretical characterization of the expressive power of such a model, connecting it with, for instance, deterministic functions of the r-hop neighborhood around a node v. In practice, the authors show how the model is competitive with other baselines and confirm its enhanced expressive power.", "summary_of_the_review": "Overall, the strength of this paper outweighs its weakness (see S&W section) and therefore my recommendation is supported. If the authors are able to at least partially address my concerns in the weakness section I'm willing to raise my score. To clarify, I'm not looking for SOTA results necessarily, but to be convinced that this architecture is competitive with existing ones. ", "strength_and_weaknesses": "---Strength---\na) Novelty: moving away from message-passing schemes is a necessity of the graph learning community.\nb) Clarity: presenting intuition together with a theoretical result is always welcome.\nc) The authors precisely characterize the class of functions (graph properties) AgentNet can learn. This type of characterization is very help to guide practitioners' model choices. Eg., \"deterministic functions of the r-hop neighborhood around a node v\".\nd) Results as far as I was able to follow and check all hold. Proofs are clear and well written.\n\n---Weaknesses---\na) The main weakness in my opinion is the empirical evaluation. Since the authors tested their model in the OGB hiv task, I don't understand why other OGB datasets were not used. I don't find the TUDataset suit insightful of a practical evaluation of a model anymore. Further, the authors could have designed synthetic datasets that explore the properties known to be \"learnable\" by their model (see theory results). This could strengthen a lot the submission.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "J7n5XkIIh5g", "reviewer": "Reviewer_6DSe", "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 introduces an agent-based GNN which differs fundamentally from the message-passing based architecture. AgentNet consists of a collection of neural agents that are trained to walk on the graph and their states are pooled to make graph classification predictions. Theoretical analysis and empirically evaluation verify good properties of the proposed model.\n", "summary_of_the_review": "This paper is overall well motivated and well written. The proposed agent based graph learning architecture is novel, fresh, flexible, efficient and expressive. It should be interesting to the community.\n", "strength_and_weaknesses": "**Strength** \n- This paper provides a novel perspective for graph based learning beyond message-passing mechanism\n- The proposed model enjoys several good properties, e.g. expressiveness and efficiency, which are demonstrated via theoretical and empirical evidence\n- The new architecture is practical and flexible to extend\n\n**Weaknesses**\n- Lack ablation study to verify the importance of different steps in the model\n\n**Questions**\n- Do the agents share the same set of model parameters, but only vary in the start node? I am curious if these agents can be designed to collect different patterns.\n- Will the proposed method also encounter the oversmoothing or oversquashing issue if the number of steps or the number of agents are set too large, and undereaching issue if they are set too small?\n- Can the proposed method be extended to serve for other popular downstream tasks, such as node classification and link prediction tasks?\n- It would be better if ablation study can be provided to show the importance of each model design, e.g. node update, neighborhood aggregation, etc.\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": "F6CfEwJrJt", "reviewer": "Reviewer_PGLs", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 presents a model for graph representation learning called AgentNet. \n\nThe main idea of the paper is to combine graph walks with neural networks: the model consists of agents that, in parallel, explore the graph by performing the following steps: \n\n1. Updating the state of the current node\n2. Aggregate information from the node's neighborhood\n3. Update the state of the agent\n4. Move to a new node in the neighborhood\n\nThe key difference from typical GNNs is that agents maintain their own global state as they explore the graphs, while also being able to \"read\" the other agents' contributions to the node states. \n\nThrough a nice theoretical analysis, the authors show that their model is more expressive than message-passing and even higher-order GNNs, while also having a cost sublinear in the number of nodes. \n\nExperiments confirm that that model is indeed capable of solving synthetic benchmarks to measure the expressivity of GNNs at a fraction of the cost. \nResults on real-world datasets are less exciting, although AgentNet shows performance comparable to much more expensive higher-order GNNs.", "summary_of_the_review": "I really enjoyed the paper and I can safely recommend acceptance. There are a few minor issues that I ask the authors to address, but this is otherwise a good paper that would fit well at ICLR and would be of interest to the GNN community.", "strength_and_weaknesses": "**Strengths**: \n- The paper presents an interesting idea and is well-written and thorough. \n- The theoretical analysis of the expressivity of AgentNets is interesting and easy to follow. \n- The proposed method is significantly less expensive than other higher-order baselines and, although the performance is not always exceptional, I believe that it's more than acceptable. \n\n**Weaknesses**: \n- What is the difference between \"pooling\" and \"readout\" in the following sentence?\n  > pooling is applied on the agent embeddings, followed by a readout function\n- I suggest removing the claim that the agents \"consciously select the next neighbor\".\n- The following claim:\n  > In Table 3 we can see that AgentNet performs well in this scenario and outperforms even the best ESAN model.\n\n  should be removed. There is no evidence to claim that the results reported in the table are significantly different between GIN (with virtual node), ESAN, and AgentNet.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "B-K5dNyi3B", "reviewer": "Reviewer_pbyu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 paper proposes a new type of graph neural network with agents running learnable(intelligent) random walk on the given graph. The author studies the theoretical analysis of proposed agent based method in counting substructures, for both 1 agent case and multi agent case. To demonstrate the effectiveness, the author run experiments over counting substructure dataset and many small real-world TU dataset. The experimental results show improvement or comparable result to other GNNs. ", "summary_of_the_review": "To summarize, the paper studies applying learnable random walk on graphs for graph classification. Although being a different angle of performing representation learning, many issues of introduced randomness are not properly addressed, and the connection to other random-walk based graph neural networks mentioned above are not clear yet. \n\n\n------------------------------------ after rebuttal -----------------   \nI would like to raise the score as 5, considering the great effort on providing more experiments and visualization. However, the real-world usage of the proposed method is still questionable. The expressivity of the proposed method is not well understood yet. ", "strength_and_weaknesses": "**Strength**: \n1. The angle of conducting agent-based random walk is very interesting. And with small number of agent, the method can be more efficient than message passing gnns.\n\n\n**Weakness**:\n1. Similar to Random Node Initialization based method, it achieves higher expressivity with the cost of introducing randomness which hurts training stability and generalization. The author doesn't give enough analysis and empirical result to show the badness of randomness introduced. \n2. The theorems in section 4.1 is kind of questionable, giving it doesn't consider the badness of random. Specifically, for two isomorphism graphs, the traverse sequence for a agent can be different which leads to different embeddings that is not desirable. In the proof of theorem 2, the author claims that this kind of problem can be avoid by assuming there is a function that can assigning every possible IDDFS traversal to its isomorphism class of r-hop neighbor subgraph. The claim is misguiding as this is equivalent to say \"Deep network can learn random noise\" which is of course possible but needs tons of data and time to train and are not guranteed to converge easily. This is actually also observed in RNI based method. \n3. All other theorems in section 4.1 have similar issues. The author starts every theorem of \"there exists any configuration\" which is perhaps true but also not considering the randomness of instability, hardness of training and requirements of more data. \n4. In fact if isolating all randomness of random walks, the expressivity is known to be limited by 2-WL. Please see [Geerts 20]. Hence I highly doubt the expressivity of this designed agent-based graph neural network when taking randomness into account. Another related work that needs to compare is [Toenshoff et al. 21], which designing a very interesting subgraph encoding method with random walk. \n5. The real-world performance is actually not good, which perhaps means that the expressivity of introduced method is limited, or suffering from the randomness. This means the proposed method is not practical to use for real-world problem. \n6. The author also needs to include other datasets like ZINC and some larger dataset from Benchmarking GNN, as these datasets are observed to be correlated with expressivity. \n7. The author claims that the agent can learn intelligent random walk, it would be very interesting to see some visualization of the walk learned, and to see whether it correlates to tasks like finding specific substructure. \n\n[Geerts 20] Walk message passing neural networks and second-order graph neural networks  \n[Toenshoff et al. 21] Graph learning with 1d convolutions on random walks   ", "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: Accept: poster