Counting Substructures with Higher-Order Graph Neural Networks:  Possibility and Impossibility Results
Authors: Behrooz Tahmasebi
Derek Lim
Stefanie Jegelka
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neural networks
expressive power
complexity

Abstract: While message passing Graph Neural Networks (GNNs) have become increasingly popular architectures for learning with graphs, recent works have revealed important shortcomings in their expressive power. In response, several higher-order GNNs have been proposed that substantially increase the expressive power, albeit at a large computational cost. Motivated by this gap, we explore alternative strategies and lower bounds. In particular, we analyze a new recursive pooling technique of local neighborhoods that allows different tradeoffs of computational cost and expressive power. First, we prove that this model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. Second, we show how recursive pooling can exploit sparsity to reduce the computational complexity compared to the existing higher-order GNNs. More generally, we provide a (near) matching information-theoretic lower bound for counting subgraphs with graph representations that pool over representations of derived (sub-)graphs. We also discuss lower bounds on time complexity.

Under review as a conference paper at ICLR 2022
COUNTING SUBSTRUCTURES WITH HIGHER-ORDER GRAPH NEURAL NETWORKS: POSSIBILITY AND IM- POSSIBILITY RESULTS
Anonymous authors Paper under double-bling blind review
ABSTRACT
While message passing Graph Neural Networks (GNNs) have become increas- ingly popular architectures for learning with graphs, recent works have revealed important shortcomings in their expressive power. In response, several higher- order GNNs have been proposed that substantially increase the expressive power, albeit at a large computational cost. Motivated by this gap, we explore alternative strategies and lower bounds. In particular, we analyze a new recursive pooling technique of local neighborhoods that allows different tradeoffs of computational cost and expressive power. First, we prove that this model can count subgraphs of size k and thereby overcomes known limitation of low-order GNNs. Second, we show how recursive pooling can exploit sparsity to reduce the computational complexity compared to the existing higher-order GNNs. More generally, we pro- vide a (near) matching information-theoreli lower bound for counting subgraphs with graph representations that pool over representations of derived (sub-)graphs. We also discuss lower bounds on time complexity.
INTRODUCTION
Graph Neural Networks (GNNs) are powerful tools for graph representation learning (Scarselli et al., 2008: Kipf& Welling. 2017: Hamilton et al., 2017), and have been successfully applied to molecule property prediction, simulating physics, social network analysis, knowledge graphs, traffic predic- tion and many other domains (Duvenaud et al., 2015; Defferrard et al., 2016; Battaglia et al., 2016; Jin et al., 2018). The perhaps most widely used class of GNNs, Message Passing Graph Neural Net- works (MPNNs) (Gilmer et al., 2017: Kipf & Welling, 2017; Hamilton et al., 2017: Xu et al., 2019; Scarselli et al., 2008), follow an iterative message passing scheme to compute a graph representation.
Despite the empirical success of MPNNs, their expressive power has been shown to be limited. For example, their discriminative power, best, corresponds to the dieeennniionll Weisfeiler- Lemaann (1-WL) graph isomorphism test (Xu et al., 2019; Morris et al., 2019), so they cannot distinguish regular graphs, for instance. Likewise, they cannot count any induced subgraph with at least three vertices (Chen et al., 2020), or learn structural graph parameters such as clique information, diame- ter, conjoint or shortest cycle (Garg et al., 2020). Yet, in applications like computational chemistry, materials design or pharmacy (Elton et al., 2019; Sun et al., 2020; Jin et al., 2018), the functions we aim to learn often depend on the presence or count of specific substructures, e.g., functional groups.
The limitations of MPNNs result from their inability to distinguish individual nodes. To resolve this issue, two routes have been studied: (1) using unique node identifiers (Loukas, 2019; Sato et al., 2019; Abboud et al., 2021), and (2) higher-order GNNs that act on k-tuples of nodes. Node IDs, if available, enable Turing completeness for sufficiently large MPNNs (Loukas, 2019). Higher-order networks use encoding of k-tuples and then apply message passing (Morris al., 2019), or cquivariant tensor operations (Maron et al., 2018).
The expressive power of MPNNs is often measured in terms of a hierarchy of graph isomorphism tests, specifically the k- L-Wiisfeiler-Lmmee (k-WL) hierarchy. The k-order models in (Maron et al., 2018) and (Maron et al., 2019a) equivalent to the k-WL and (k (k=1)-WL "tests". respectively. and are universal for the corresponding function classes (Azizian & Lelarge. 2020; Maron et al., 2019b; Keriven & Peyré, 2019). Yet, these models are computationally expensive, operating on ((n²)

---

Under review as a conference paper at ICLR 2022
tuples and according to current upper bounds requiring up to O(n²) iterations (Kiefer & McKay, 2020). The necessary tradeoffs between expressive power and computational complexity are still an open question. However, for specific classes of tasks this full universality may not be needed. Here, we study such an example of practical interest: counting substructures, as proposed in (Chen al., 2020). In particular, we study if it is possible to count given substructures with GNN whose complexity is between that of MPNNs and existing higher-order GNNs.
To this end, we study generic scheme followed by many GNN architectures, including MPNNS and higher-order GNNs (Morris et al., 2019; Chen et al., 2020): select a collection of subgraphs of the input graph, encode these, and apply an aggregation function on this collection. First, we study the power of pooling by itself, as a multi-set function over node features. We prove that l recursive applications on each node's ' neighborhood allow count any substructure of size k. This is in contrast to iterative MPNNs. We call this technique Recursive neighhorhood pooling (RNP). While subgraph pooling relates to the graph reconstruction conjecture, our strategy has important differences. In particular, we show how the aggregation "augments" local encodings, if they play together and the subgraphs are selected appropriately, and this reasoning may be of interest for the design of other, even partially, expressive architectures. Moreover, complexity is adjustable to the counting task of interest and the sparsity of the graph.
results show that the
The strategy of pooling subgraph encodings has previously been used for counting in Local Rela- tional Pooling (LRP) (Chen et al., 2020). LRP relies on an isomorphic encoding of subgraphs, which expensive - e.g., the relational pooling it uses requires (k:) time for subgraph of size k. Other higher-order GNNs would be expensive, too, as high orders are needed for complete isomorphism power. A major difference to our RNP is that our recursion uses subgraphs of varying sizes and structures, many of them much smaller - adapted to the graph structure and specific counting task.
Furthermore, we study lower bounds on GNNs that count motifs. We show an lower bound on the number of subgraphs to encode, as a function of an encoding complexity. We also transfer computational lower bounds that apply any counting GNN. The lower bounds show that the recursive pooling is close to tight.
-hhorrett
In short, in this paper, we make the following contributions:
We study the power of pooling encodings of subgraphs, and show that pooling, injective multi-set function, is sufficient by itself for counting when applied recursively on appropriate subgraphs, remarkably without relying on other encoding techniques or node IDs. This different from any other strategy we are aware of in the literature.
function of the task and input graph. We provide complexity lower bounds for pooling and general GNN architectures that count motifs. For instance, we show a lower bound on the number of subgraphs that need to be encoded.
We analyze the complexity of recursive pooling,
BACKGROUND
Message Passing Graph Neural Networks. Let G [V] = n nodes. Here, X, E X denotes the initial attribute of E V. where X' C N is a (countable) domain.A typical Message Passing Graph Neural Network (MPNN) first computes a representation of each node, and then aggregates the node representations via readout function into representa- tion of the entire graph G. The representation (1) of each node v E is computed iteratively by aggregating the representations h (1-1) of the neighboring vertices u:
EV, be attributed graph with
m = AGGREGATE (gh(t-)) =
h!! = COMBINE ( (n(--)),
(1)
for any E V. for l iterations, and with (0) X., The AGCREGATE/COMBINE functions parametrized, and { denotes a multi-set, i.c., a set with (possibly) repeating elements. A graph- level representation can be computed as hG = READOUT( ( ( E VB), where READOUT a learnable aggregation function. For representational power, it is important that the learnable functions are injective (Xu et al., 2019).
Higher-Order GNNs. To increase the representational power of GNNs, several higher-order GNNs have been proposed. In k-GNN, message passing is applied to k tttuls of nodes, inspired
2

---

Under review as a conference paper at ICLR 2022
by 4-WL (Morris al., 2019). At initialization, each k-tuple is labeled such that two k-tuples labeled differently if their induced subgraphs have different isomorphism types (Maron et al., 2019a; Cai et al., 1992). As result, k-GNNs count (induced) substructures with most & vertices even at initialization. Another class of higher-order networks applies (linear) equivariant operations, in- terleaved with coordinate-win and input node attributes (Maron et al., 2018; 2019a;b). These GNNs are at least as powerful as k k-GNNs, and hence they too can count substructures with at most vertices. All these methods need (2n²)) operations. Local Relational Pooling (LRP) (Chen et al., 2020) was designed for count- ing and applies relational pooling (Murphy al., 2019b;a) on local neighborhoods, i.e., one pools over evaluations of permutation-sensitive function applied to all k! permutations of the nodes in k-size neighborhood of each node.
nonlinearities, order-k tensors consisting of the adjacency matrix
3 OTHER RELATED WORKS
Expressive power. Several other works have studied the expressive power of GNNs function approximators (Azizian & Lelarge, 2020). Scarselli et al. (2009) extend universal approximation from feedforward networks to MPNNs, using the notion of unfolding equivalence, i.e., functions on computation trees. Indeed, graph distinction and function approximation are closely related (Chen al., 2019; Azizian & Lelarge, 2020; Keriven & Peyré, 2019). Maron et al. (2019b) and Keriven & Peyré (2019) show that higher-order, tensor-based GNNs provably achieve universal approximation of permutation-invant depth and width restrictions. Studying GNNs from the perspective of local algorithms, Sato et al. (2019) show that GNNs can approximate solutions to certain combinatorial optimization problems. For counting substricutres, Arvind et al. (2020); Fürer (2017) show that 2-WL, which is equivalent to MPNNs, can count not necessarily induced cycles and paths of up to vertices with O(n²) complexity,
functions on graphs, and Loukas (2019) analyzes expressive power under
Subgraphs and GNNs Having infromation about subgraphs can be quite helpful in various graph representation algorithms (Liu et al., 2019; Monti et al., 2018: Liu et al., 2020; Yu et al., 2020; Meng et al., 2018; Cotta et al., 2020; Alsentzer et al., 2020; Huang & Zitmik, 2020). For example, for graph comparison (i.e., testing whether given (possibly large) subgraph exists in the given model), Ying et al. (2020) compare the outputs of GNNs for small subgraphs of the two graphs. To improve the expressive power of GNNs, Bouritsas al. (2020) use features that counts of specific subgraphs of interest. Another example is (Vignac et al., 2020), where an MPNN is strengthened by learning local context matrices around vertices. Recent works have also developed GNNs that pass messages on ego-nets (You et al., 2021: Sandfelder et al., 2021). With motivation from the reconstruction conjecture, Cotta et al. (2021) process node-deleted subgraphs with individual MPNNs, and then pool them with DeepSets model to get representation of the original graph.
RECURSIVE NEIGHBORHOOD POOLING
Let G = E, X) be an attributed input graph with |V] n nodes, and let h = X₂ be the initial representation of each node v. In this work, we study architectures that first find representations of collection of m subgraphs G, and then aggregate (pool) over these representations with a multi-set function, i.c..
AGGREGATE { (P.G.) : [m]]))
[m] fl....,m] m).
(2)
It is clear that if the vo can count a subgraph structure H, then the entire model can count H. In particular, we aim to apply this strategy to obtain the representations sb, too. To appreciate the challenges in doing so, recall two such examples. First, MPNNs follow this pooling strategy, by iteratively aggregating over node neighborhoods, and then aggregating all node representations into graph representation. However, it is known that MPNNs can count at most star structures or edges (Arvind et al., 2020). This is because they represent local computation tree, which loses structural information about node identities and connectivity. Second, this strategy is at the heart of the Graph Reconstruction Conjecture (Kelly, 1957), which conjectures that a graph G can be reconstructed from its subgraphs G. G \ {0) 8 E V(G) (Appendix E). This, however, is unknown for general graphs. Although the G, retain some structure, we lose information about their structural relationship. In summary, encoding structural information is the key question.
3

---

Under review as a conference paper at ICLR 2022
N2
Figure 1: Illustration of Recursive Neigh- borhood Pooling GNN (RNP-GNN) with re- cursion parameters (2, 1). To compute the representation of node in the given input graph (depicted in the top left of the figure), we first recurse on G(N2(v) \ {v}) (top right of figure). To do so, we find the represen- tation of each node u E G(N((u) (v))- For instance, to compute the representation of 4₁ apply RNP-GNN with recursion parameters (2, 1) and aggregate G((N((v) {u)) n (N2(u1) {ur)), which is shown in the bottom left of the figure. To do so, we recursively apply RNP-GNN with recur-
U2
u1
U3
sion parameter (1) on G((N((v) \ (u)) n (N2(ug) ) (ui}) }) (N1 (u1)) (um))), in
(W2(e) (u)) (2((
the bottom right of the figure.
Hence, represent the counting function over potentially large neighborhoods, MPNN does not suffice. But, aggregation over input node attributes, along with edge information, can count edge types, ie.. tiny subgraphs. Hence, we recursively apply aggregation on smaller sub-neighborhoods while remembering structural information, with node-wise aggregation as the base casc. For intu- ition, suppose we aim to count the occurrence of subgraph H in the r--neighborhood Nr, (v) of node v. To do we may count H, H \ (v) in the smaller graph Nr, (v) \ {v). But, to combine these counts with the presence of e to "complete" H, we must know how the H. are con- nected to in the screened graph. Hence, to retain structure information, v. We then recursively call neighborhood pooling to process smaller neighborhoods Nr. (u) within Nr, (v) {u}. This could, e.g., learn count marked versions of H,. The radii of neighborhoods may differ in recursive calls. Section 5, we relate their size to H.
mark the neighbors of
Recursive neighborhood pooling RNP-GNN(G, ) JuEVIG), (rI.....TT)) takes attributed graph along with a sequence of neighborhood radii for different recursions, and returns a set of node encodings (Ev)ey) For any E G, RNP-GNN first constructs v's neighborhood, removes and marks neighbors':
G Nr, (v)
ha - (h [((,,)) E E(G.)))
Here, we extracted 71 - neighborhood of v removed the central node v, and then added the new structural information to 1 -eiigghoors of Then aggregate subgraph representations, i.e., the representations of G,,, v E [n] when they considered as a set graphs. r (base case), we the input features:
h, K AGGREGATE
(Nip. (N) (h G.))).
(4)
In other words, in this case we only combine hidden representations in each G, without any itera- tion/recursion. If T > we recursively represent neighborhoods of nodes in G,;;
(hr,a) (ue,a RNP-GNN ) Ju.., (r2, Ps,..... .3...... rr))
(5)
he f- AGGREGATE
(hy, (ha,, : u G.
(6)
Here, we first apply an RNP-GNN on each G, update the representations of nodes for each node in G.. Then, we combine those representations to find the representation c. The fact that G, has less nodes than G' allows to define the algorithm in an inductive way; this ensures the algorithm does not have any logical loop. For aggregation, we can use, e.g., the injective multi-set function from (Xu al., 2019):
AGGREGATE(T) (Ro, (Iu (hu MLP(1) (a ((++))) c)he + E'uco imu).
$1 [] when the condition is satisficd, and otherwise is zero.
4

---

Under review as a conference paper at ICLR 2022
where we MLP modules with ReLU activation, and is an arbitrary irrational constant (Xu et al., 2019). The final readout aggregates over the final node representations the entire graph. Figure illustrates RNP-GNN with recursion parameters (2, 2, 1), and Appendix F provides pseudocode. One can optionally do message passing iterations to the representations h, v E [xx] to make the model more expressive; though our results hold even without those iterations.
While MPNNs also encode a representation of a local neighborhood, the recursive representations differ as they take into account intersections of neighborhoods. As result, as will see in Sec- tion 5, they retain more structural information and are more expressive than MPNNs; one can take r1 simulate one iteration of MPNNs (and then iterate).
Models like k-GNN and LRP also compute encodings of subgraphs, and then update the resulting representations via message passing. We can do the same with the neighborhood representations computed by RNP-GNNs to encode more global information, although our representation results in Section hold even without that.
EXPRESSIVE POWER OF RECURSIVE POOLING
In this section, we analyze the expressive power of RNP-GNNS. We notice that for full expres- siveness, we indeed need the identifiers in Eq. (3); their addition is an important insight. Still, RNP-GNN does maintain some expressive power without the augmented identifiers. For instance, consider the graphs G1 two triangles and G2 the 6-cycle, which are 1-WL equivalent and thus cannot be distinguished by MPNNs. An RNP-GNN with r1 = 1 can distinguish these without the augmented identifiers. This is because the first recursion level, the 1-neighborhoods of G1 two nodes with an edge between them, and the I-neighborhoods of G2 consist of two isolated nodes.
5.1 COUNTING (INDUCED) SUBSTRUCTURES
In contrast to MPNNs, which in general cannot count substructures three vertices or more (Chen et al., 2020), in this section we prove that for any set of substructures, there is RNP-GNN that provably counts them. We begin with a few definitions.
Definition 1.
Let G, H be arbitrary, potentially attributed simple graphs, where is the set of nodes in G. Also, for any S C V, let G(S) denote the subgraph of G induced by S. The induced subgraph count function is defined as
CIC; I(G(S) = 11),
ie., the number of subgraphs of isomorphic to H.
To relate the size of encoded neighborhoods the substructure H, we will need notion of covering sequences for graphs.
Definition 2. Let H = (VH, Eh) be a simple connected graph. For any S S VH and v E VH define the covering distance of from S as
(u((v;) :mxxxxxxxxxxxxxx
max d d(u, v),
where d(...) is the shortest-path distance H.
Definition Let H be simple connected graph on T + vertices. A permutation of vertices, such as (V1, 02.... .., (Q2...)) is called a vertex covering sequence with respect to sequence (r1, T2..., INT called covering sequence, if and only if
dir (ws; (t) S
(10)
for any i E [T 21, 1}. where S, = {U;, Vi+l Ur+1} and H(()) is the subgraph of induced by the set of vertices S.. We also say that H admits the covering sequence r = (2.. E N2 if there is vertex covering sequence for H with respect to r.
In particular, in a covering sequence we first consider the whole graph as a local neighborhood of one of its nodes with radius ri. Then, remove that node and compute the covering sequence of
5

---

Under review as a conference paper at ICLR 2022
the remaining graph. Figure 4 shows example of covering sequence computation. An important property, which holds by definition, is that if r is a covering sequence for H. then any 2 r (coordinate-wisse is also covering sequence for H.
Note that any connected graph on & nodes admits at least one covering sequence, which is (A 1, 2, To observe this fact, note that in connected graph, there is at least one node that can be removed and the remaining graph still remains connected. Therefore, we may take this node as the first element of vertex covering sequence, and inductively find the other elements. Since the diameter of a connected graph with k vertices is always bounded by k - 1, we achieve the desired result. However, we will see in the next section that, when using covering sequences to identify sufficiently powerful RNP- GNNs. it is desirable to have covering sequences with low T1, since the complexity of the resulting RNP-GNN depends on r-
1).
More generally, if H1 and H2 are (possibly attributed) simple graphs on k nodes and H1 E H2, i.e., H1 a subgraph of Hz (not necessarily induced subgraph), then it follows from the definition that any covering sequence for Hi is also covering sequence for H2. As side remark, as illustrated in Figure 2, covering sequences need not always to be decreasing. Using covering wetueeeeeuueeeee sequences, we can
show the following result.
Theorem 1. Consider set (possibly altributed) graphs H on T r+1 vertices, such that any H E H admits the covering sequence (2..72....,T, Then, there is an RNP-GNN f(=;0) () with recursion parameters (T1. F2,...,TT> T.) that can count any H E H. In other words. for any two graphs G1. G2, if there exists E such that C(G,; H) + C(G2; H), then f(G1; # f(G;; 0). The same result also holds for the non-induced subgraph count function.
Theorem 1 states that, with appropriate recursion parameters, any set of (possibly attributed) sub- structures can be counted by an RNP-GNN. Interestingly, induced and non-induced subgraphs can be both counted in RNP-GNNS'. Also, for given covering sequence, we can simultaneously count of substructures that each admit it. This means that one RNP-GNN is able potentially count many substructures. We prove Theorem I in Appendix A.2. The main idea is to show that we can implement the intuition for recursive pooling outlined in Section formally with the proposed architecture and multiset functions
The theorem holds for any covering sequence that is valid for all graphs in H. For any graph, one can compute covering sequence by computing spanning tree, and sequentially pruning the leaves of the tree. The resulting sequence of nodes is a vertex covering sequence, and the corresponding covering sequence can be obtained from the tree too (Appendix D). A valid covering sequence for all the graphs in H is the coordinate-wise maximum of all these sequences.
For large substructures, the sequence (ri, r2,...,, rr) can be long or include large numbers, and this will affect the computational complexity of RNP-GNNs. For small, c.g., constant-size substructures, the recursion parameters structures efficiently. In particular, T1 is an important parameter. In Section 5.3, we analyze the complexity of RNP-GNNs in more detail.
also small (i.e., T2 O(1) for all i), raising the hope to count these
5.2 A UNIVERSAL. APPROXIMATION RESULT FOR LOCAL FUNCTIONS
Theorem I shows that RNP-GNNs can count substructures if their recursion parameters are chosen carefully. Next, we provide a universal approximation result, which shows that they can represent any function related to local neighborhoods or small subgraphs in graph.
First, we recall that for graph G, G(S) denotes the subgraph of G induced by the set of nodes S.
Definition 4. A function é G. R is called an rlcoaal graph function if
((G) = a (GGS)) S VVV, S &)),
(11)
where vb: : G, + ddd is a functioo on graphs, is a multi-set function, and V denotes the set of all nodes.
For simplicity, we assume that H only contains 7 + node graphs. If H includes graphs with strictly less than T + vertices, we can simply append a sufficient number of zeros to their covering sequences.
Onee can also generalize this theorem to wider classes of graphs; see Remark 1. However, here in this paper focus on a special class of graph with covering sequences to keep the results simple and insightful

---

Under review as a conference paper at ICLR 2022
In other words, local function only depends on small substructures.
Theorem 2. For any r-local graph function {(.), there exists an RNP-GNI {(: with recursion parameters (r- 1,r 1ar--2.... .....: 1) such that f(; = =(GG) for any G E Gn.
:......)))).
To prove the theorem, we use specific aggregation functions, but since MLPs with ReLU activation universal approximators.
can approximate those aggregations and find an RNP-GNN f(G; 0) implemented by MLPs such that If(G; - P{G) < e, for arbitrary small As result, we can provably approximate all the local information in a graph with an appropriate RNP-GNN. Note that we still need recursions, because the function *t..) may be an arbitrarily difficult graph function. However, achieve the full generality of such a universal approximation result, we need consider large recursion parameters (r1 r 1) and injective aggregations in the RNP-GNN network. For universal approximation, we may also need high dimensions if fully connected layers are used for aggregation (see the proof in Appendix B for more details).
As a remark. for = n, achieving universal approximation on graphs implies solving the graph isomorphism problem. But, in this extreme case, the computational complexity of RNP is in general not polynomial in n.
5.3 COMPUTATIONAL COMPLEXITY
The computational complexity of RNP-GNNs is graph- dependent. For instance, we need to compute the set of local neighborhoods, which is cheaper for sparse graphs. Moreover, in the recursions, we use intersections of neighborhoods which become smaller and sparser.
Theorem 3. Let f(.;0) Gn + Rd be an RNP. GNN with recursion parameters (r1, r2,-..,TTT As- sume that the observed graphs G1, G2...., whose rep- resentations we compute, satisfy the following property: maxxe[m] [Wr, (v) S c, for a constant Then the num- ber of node updates in the RNP-GNN is Oncc)).
Figure 2: For the above graph, (v1, 02 ..., 0b) is vertex covering quence. The corresponding covering se- quence (1, 4, 3, 2, 1) is not decreasing.
In other words, if c = (1) and = O(1), then RNP- GNN requires relatively few updates (that is, n n2)+)
If the maximum degree of the given graphs is A, then = O(r Therefore, similarly, A (1) then we can count with at most n ++((1) updates. Additional gains may arise from rapidly shrinking neighborhoods, which are not yet accounted for in Theorem 3. To put this in context, the higher-order GNNs based on tensors or k- WL would operate on tensors of order n ++1
The above results show that when us- ing RNP-GNNs with sparse graphs, can represent functions of sub- structures with nodes without re- quiring --rrder tensors. LRPs also encode neighborhoods of distance 71 around nodes. In particular, all c! per- mutations of the nodes neighbor- hood of size are considered ob-
Table 1: Time complexity of various models. A is the max- degree, and '_' means the complexity is not polynomial in n.
Model worst-case A (0)) A Ollo((n)
0(1)
LRP
O(n)
k WL
n
x n 1
x*
n²
RNP
n
Ó(a)
O(n)
tain the representation. As a result, LRP networks only have polynomial complexity if e o(log(r (n)). Thus, RNP-GNNs can provide an exponential improvement terms of the tolerable size e of neighborhoods with distance 71 in the graph.
Moreover, Theorem 3 suggests aim for small 71- The other ry 's may be larger than rı, as shown in Figure 2, but do not affect the upper bound on the complexity.
6 AN INFORMATION- THEORETIC LOWER BOUND
In this section, we provide a general information theoretic lower bound for graph representations that encode given graph G by first encoding number of (possibly small) graphs G1, G2,... G
7

---

Under review as a conference paper at ICLR 2022
and then aggregating the resulting representations. The sequence of graphs G1. ......, Gt may be obtained in an arbitrary way from G. For example, in an MPNN, G, can be the computation tree (rooted tree) at node i. As another example, in LRP, G₃ is the local neighborhood around node i.
Formally, consider a graph representation (l:0) 0): G, + R2 as
O(G;0) AGGREGATE( ( (G.) : (48), 14 (1.......
(12)
for any G G22 where AGGREGATE multi-set function, (G1, G2......... G1) E where E(:): Gn + (Um=) Gm) is a function from one graph to l graphs, and và Um=1 Gm + [s] is a function on graphs taking values. In short, we encode graphs, and each encoding takes one of values. We call this graph representation function an (s, -ggood graph representation.
Theorem 4. Consider a parametrized class of (s,t)-good representations f(;;0) : G, + TRd that is able count any (not necessarily induced") substructure with k. vertices. More precisely, for any graph H with k vertices, there exists f(; such that if C(G1; + C(G2; H). then f(G1:0) + f(G2;) 0). Then' ()(
In particular, for any need ((n*)) encoded graphs This implies that, for 2, enumerating all subgraphs and deciding for each whether equals H near optimal. Moreover, s S k. then t = ((n) small graphs would not suffice to enable counting.
graph representation with 2, i.c., binary encoding functions,
More interestingly, if k, 8 = Q(1), then it impossible to perform the substructure counting task with (n)og(n)) As result, in this case, considering n encoded graphs (as is done in GNNs or LRP networks) cannot be exponentially improved.
The lower bound this section is informatioonthhorette and hence applies to any algorithm. It may be possible to strengthen it by considering computational complexity, too. For binary encodings, i.e., 2, however, we know that the bound cannot be improved since manual counting of subgraphs matches the lower bound.
7 TIME COMPLEXITY LOWER BOUNDS FOR COUNTING SUBGRAPHS
In this section, we put our results in the context of known hardness results for subgraph counting. In general, the subgraph isomorphism problem is known to be NP-complete. Going further, the Exponential Time Hypothesis (ETH) is conjecture in complexity theory (Impagliazzo & Paturi, 2001), and states that several NP-complete problems cannot be solved in sub-exponential time. ETH, as stronger version of the P F NP problem, is widely believed to hold. Assuming that ETH holds, the k-clique detection problem requires at least n ((K) time (Chen et al., 2005). This means that if graph representation can count any subgraph H of size k then computing it requires least n ((k) time.
Corollary 1. Assuming the ETH conjecture holds, any graph representation that can count any substructure H on k vertices with appropriate parametrization needs ((k) time to compute.
The above bound matches the O(r*) complexity of the higher-order GNNs. Comparing with The- orem 4 above, Corollary is more general, while Theorem 4 has fewer assumptions and offers refined result for aggregation based graph representations.
Given that Corollary is worst-case bound, natural question is whether subclasses of graphs. Regarding H, even if H is random Erdös-Rényi graph, can only be counted in n. 90k/ log k) time (Dalirrooyfard et al., 2019).
do better for
Regarding the input graph in which we count, consider two classes of sparse graphs: strongly sparse graphs have maximum degree A = O11), and weakly sparse graphs have average degree À = O(1). We argued in Theorem 3 that RNP-GNNs achieve almost linear complexity for the class of strongly sparse graphs. For weakly sparse graphs, in contrast, the complexity of RNP-GNNS is generally not linear, but still polynomial, and can be much better than ((n)). One may ask whether it is possible
'The theorem also holds for induced subgraphs, with/without node attributes. (() is (m)) up to poly-logarithmic factors.
8

---

Under review as a conference paper at ICLR 2022
to achieve a learnable graph representation such that its complexity for weakly sparse graphs is still linear. Recent results in complexity theory imply that this is impossible:
Corollary 2 (Gishboliner et al. (2020); Bera et al. (2019; 2020)), There is no graph representation algorithm that runs in linear time on weakly sparse graphs and is able to count any substructure H on k vertices (with appropriate parametrization)
Hence, RNP-GNNS are close to optimal for several cases of counting substructures with parametrized learnable functions.
EXPERIMENTS
In this section, we validate our theoretical findings via numerical experiments. Here, we briefly describe our experimental setup and results - further experimental details are given in Appendix H.
Table 2: Numerical results for counting induced triangles and non-induced 3-stars, following the setup of Chen et al. (2020). We report the test MSE divided by variance of the true counts of each substructure (lower is better). The best three models for each task are bolded.
Table Test accuracy on the EXP dataset with setup as in Abboud et al. (2021). Re- sults for baselines taken from Abboud et al. (2021). 'Reported PPGN performance dif- fers in other work (Balcilar al., 2021).
Endōs-Renyi
Random Regular
triangle
3-star
triangle
3-star
Model
Accuracy (%)
GCN
6.78E-1
4.36E-1
1.82
2.63
GCN-RNI
98.0 +:: 1.85
GIN
1,23E-1
1.62E-4
4,70E-1
3.73E-4
PPGN'
50.0
GraphSAGE
1.31E-1
2.40E-10
3,62E-1
8.70E-8
1-2-3-GCN-L.
50.0
sGNN
9,25E-2
2.36E-3
3.92E-1
2.37E-2
3-GCN
99.7 + 0.004
2-1GN
9,83E-2
5,40E-4
2.62E-1
1.19E-2
RNP-GNN (r) (r=11)
50.0
PPGN
5.08E-8
4.00E-5
1,40E-6
8,49E-5
RNP-GNN (71 =2
99.8 0.005
LRP-1-3
1.56E-4
2.17E-5
2.47E-4
188E--6
Deep LRP-1-3
2.81E-5
1.12E-5
1,30E-6
2.07E-6
RNP-GNN
1.39E-5
1.39E-5
2.38E-6
1.50E.4
Counting substructures. First, we follow the experimental setup of Chen et al. (2020) on tasks for counting substructures. In Table 2, we report results for learning induced subgraph count of triangles and non-induced subgraph count of 3-stars. We test on two datasets of 5000 graphs each: one of Erdös-Res Prnōs-RReni graphs and one of random regular graphs. Our RNP-GNN model is consistently within the best performing models for these counting tasks, thus validating our theoretical results. Based on the baseline results taken from (Chen et al., 2020), RNP-GNN tends to widely outperform MPNNs (GCN (Kipf & Welling, 2017), GIN (Xu et al., 2019), Graph AGE (Hamilton et al., 2017)), and other models not tailored for counting: spectral GNN (Chen et al., 2018), and 2-IGN (Maron et al., 2018). Also, RNP-GNN often beats higher-order GNNs: PPGN (Maron et al., 2019a) and LRP-1- 3 (Chen et al., 2020). RNP-GNN is mostly comparable to Deep LRP-1-3, though Deep LRP-1-3 outperforms it in a few cases. Recall that Deep LRP-1-3 is practical version of LRP we leave further developments of practical variants of RNP-GNN to future work. The best r parameters for RNP-GNN were:
(1, 1, 1, 1) for triangles on Erdōs-Reny,. r (1, 1) for stars on Erdōs-Renyi, r= (1, for triangles on random regular and = 1, for stars on random regular.
Satisfiability of propositional formulas. Second, we test the expressiveness of our model in dis- tinguishing non-isomorphic graphs that 1-WL cannot distinguish. The EXP dataset of 600 graphs (Abboud et al., 2021) for classifying whether certain propositional formulas are satisfiable requires higher than 1-WL expressive power to achieve better than random accuracy. As shown in Table 3, while our RNP-GNN with rı is unable achieve better than random accuracy, our RNP-GNN with = 2 (we use r = (2, 1) achieves near perfect accuracy beating all other models based on results taken from (Abboud et al., 2021). These other models include universal models with random node identifiers (GCN-RNI (Abboud et al., 2021)), GNNs with 3-WL power (PPGN (Maron et al., 2019a)). and GNNs that imitate some (possibly weaker) version of 3-WL (1-2-3-GCN-L (Morris et al., 2019), 3-GCN (Abboud al., 2021)). Thus, architecture, which is not developed within common frameworks for achieving i- W-L expressiveness, is in fact powerful at distinguishing non- isomorphic graphs

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ralph Abboud, ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth Inter- national Joint Conference on Artificial Intelligence, IJCAI-21, pp. 2112-2118, 8 2021.
Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik. Subgraph neural networks. Advances in Neural Information Processing Systems, 33. 2020.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 2020.
Waiss Azizian and Mare Lelarge. Characterizing the expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006. / 15646, 2020.
Muhammet Balcilar, Pierre Héroux. Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pp. 4502-4510, 2016.
Suman K Bera, Noujan Pashanasangi. and C Seshadhri. Linear time subgraph counting, graph degeneracy, and the chasm at size six. arXiv preprint vrXiv:1911.000 2019.
Suman Bera, Noujan Pashanasangi, and Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: The barrier of long induced cycles, 2020.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09225,, 2020.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang. David Juedes, Iyad A Kanj. and Ge Xia. Tight lower bounds for certain parameterized np-hard problems. Information and Computation, 201(2):216-231, 2005.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations, 2018.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pp. 15894-15902, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? arXiv preprint arXiv:2002.04025. 2020.
Leonardo Cotta, Carlos H. C. Teixeira, Ananthram Swami, and Bruno Ribeiro. Unsupervised joint k-node graph representations with compositional energy-based models. arXiv preprint arXiv:2010.04259, 2020.
Lconardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations, 2021.
Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams. Graph pattern detec- tion: Hardness for all induced patterns and faster non-induced cycles. In Proceedings of the 51st Annual ACM SIGACT' Symposium on Theory of Computing, pp. 1167-1178, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852. 2016.
10

---

Under review as a conference paper at ICLR 2022
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguiree, Rafael Bombarell, Timothy Hirzel, Alán Sapuru-Guzike and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2232,222, 2015.
Daniel C Elton, Zois Boukouvalas, Mark D Fuge, and Peter W Chung. Deep learning for molecular design a review of the state of the art. Molecular Systems Design & Engineering. 4(4):828-888 849, 2019.
Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. In International Conference on Algorithms and Complexity, pp. 270.-77..20 Springer, 2017.
Vikas Garg, Stefanic Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In Int. Conference on Machine Learning (ICML), pp. 5204-522 5215. 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1263-1272, 2017.
Lior Gishboliner, Yevgeny Levanzov, and Asaf Shapira. Counting subgraphs in degenerate graphs arXiv preprint arXiv:2010.05990 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs
In Advances neural information processing systems, pp. 1024-1034, 2017.
Kurt Hornik. Approximation capabilities multilayer feedforward networks. Neural networks, (2):251-257, 1991.
Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks universal approximators. Neural networks, 265):359-366, 1989.
Kexin Huang and Marinka Zitnik. Graph meta learning via local subgraphs. arXiv preprint
arXiv:2006.07889, 2020.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375. 2001.
Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to- graph translation for molecule optimization. In International Conference on Learning Represen- tations, 2018
Paul Kelly. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1)9611966, 1957.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7092-7101, 2019.
Sandra Kiefer and Brendan D McKay. The iteration number of colour refinement. In 47th Interna- tional Colloquiun Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations, 2017.
Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education India, 2006.
Shengchao Liu, Mehmet F Demirel, and Yingyu Liang. N-gram graph: Simple unsupervised repre- sentation for graphs, with applications to molecules. In Advances Neural Information Process- ing Systems, pp. 8476,8778, 2019.
Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. Neural subgraph isomorphism counting. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1959-1969, 2020.

---

Under review as a conference paper at ICLR 2022
Andreas Loukas. What graph neural networks cannot learn: depth width. In International Con- ference on Learning Representations, 2019.
Haggai Maron, Heli Ben-Hamu Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. International Conference on Learning Representations, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2156-2167, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning, pp. 4363-4371, 2019b.
Brendan D McKay. Small graphs reconstructible. Australasian Journal of Combinatorics, 15: 123-126, 1997.
Changping Meng, Chandra Mouli, Bruno Ribeiro, and Jennifer Neville. Subgraph pattern neural networks for high-order graph evolution prediction. AAAI, pp. 3778-3787, 2018.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: motif-based graph convolu- tional network for directed graphs. 2018 IEEE Data Science Workshop (DSW), pp. 225 228. IEEE, 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Murphy, B Srinivasan, V Rao, and B Riberio. Janossy pooling: Learning deep permutation- invariant functions for variable-size inputs. In International Conference on Learning Representa- tions, 2019a.
Murphy, B Srinivasan, V Rao, and B Riberio. Relational pooling for graph representations. In International Conference on Machine Learning (ICML 2019), 2019b.
Dylan Sandfelder, Priyesh Vijayan, and William L Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8523 8527. IEEE, 2021.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pp- 4081- - 4090, 2019.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, (001):81-102) 2009.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2008
Angelika Steger and Nicholas Wormald. Generating random regular graphs quickly. Combina- torics, Probability and Computing, 844)3377-36, 1999.
Mengying Sun, Sendong Zhao, Coryandar Gilvary, Olivier Flemento, Jiayu Zhou, and Fei Wang- Graph convolutional networks for computational drug development and discovery. Briefings in bioinformatics, 21(3):919-923 2020.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with message-passingg arXiv preprint arXiv:2006. 107, 2020.
Keyulu Xu. Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Rex Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. Neural subgraph matching. arXiv preprint arXiv:2007.03002 2020.
12

---

Under review as a conference paper at ICLR 2022
Jiaxuan You, Jonathan M Gomes-Selman Selman, Rex Ying, and Jure Leskovec. Identity-awand aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Yue Yu, Kexin Huang, Chao Zhang, Lucas M. Glass, Jimeng Sun, and Cao Xiao. Sumgnn: Multi- typed drug interaction prediction via efficient knowledge graph summarization. arXiv preprint arXiv:2010.01450, 2020.
A PROOF OF THEOREM
A.1 PRELIMINARIES
Let first state few definitions about the graph functions. Note that for any graph function f: Gn + IR, we have f(G) = f(H) for any G = H.
Definition 5. Given two graph functions S.g Ga + Rd, write f 3 g. if and only if for any G1,G2 E Gn.
VG1,G2 E Gn gG()) ( g(G2) = -f(G)) f(G2),
(13)
or, equivalently,
vG1, G2 E G, f(Gi) - f(G2)
- g(G2).
(14)
Proposition Consider gruph fanctions I 9, h Gn + Rd such that f 2 and y J h. Then, C h. In other words, 3 is transilive.
Proof. The proposition holds by definition.
Proposition 2. Consider graph f.g: Gn IRd such that f 2 g. Then, there is a function { R. + Rd such that & =
Proof. Let G, LiENF;; the partitioning induced by the equality relation with respect to the function f on G., Similarly define G. E N for y. Note that due to the definition, {F; i E NJ is refinement for {9, E NJ. Define & to be the unique mapping from (F, : E N} to {9, : i E N} which respects the equality relation. One can observe that such & satisfies the requirement in the proposition.
Definition 6. An RNP-GNN is called maximally expressive, and only if
all the aggregate functions are injective as mappings from a multi-set on a countable ground set their codomain.
all the combine functions injective mappings.
Proposition 3. Consider two RNP-GNNs f.g with the same recursion parameters r (ri, (2,,,,...., where maximally expressive. Then, I g.
Proof. The proposition holds by definition.
Proposition 4. Consider sequence of graph functions f. J.9h,...,9e Ifs g. for all [k], then
fp
Cifs:
(15)
1=1
for any E i.
Proof. Since f 2 Gio we have
VG1, G2 E G. f(GG) f(G2) (G.) (G2).
(16)
for all i E [k]. This means that for any G1, G2 E G, if f(G)) = f(G2) then (G) = (( i E [k)] and consequently Σk (gg((G)) Σ Gigi (G2). (G2) Therefore, from the definition conclude f 2 Σ Cgg,- Note that the same proof also holds in the case of countable summations as long the summation is bounded.
13

---

Under review as a conference paper at ICLR 2022
Definition 7. Let H (VH, EH, (H) be attributed connected simple graph with k nodes. For any attributed graph = (Va, ))) E Gn the induced subgraph count function C(G: H) is defined as
C(G: ():
E ((((S) = H). SCIm]
(17)
Also, let CG; H) denote the number of non-induced subgraphs of G which are isomorphic H. can be defined with the homomorphisms, from H to G. Formally, if n > & define
C(G: H) = Σ Ö(G(S); H).
(18)
Otherwise, n = k, and we define
C(G;H) :=
E
CH. x x H)
(19)
HEA(H)
where
;= = (i C2 it 3 H},
(20)
defined with respect the graph isomorphism, and CH,H H E N denotes the number of subgraphs in H identical to H. Note that H.H is a finite set and @ denotes being (not necessarily induced) subgraph.
Proposition 5. Let H be a family of graphs. for any H E H. there is an RNP-GNN fH (::0) with recursion parameters (r1, T.) such that fH 2 C(G; H). then there exists an RNP-GNN f(;0) with recursion parameters (r1, r2,..., [T) such that f EhEn C(G; H).
Proof. Let fl; be maximally expressive RNP-GNN. Note that by the definition J fH for any H E H. Since ] is transitive, f C(G; H) for all H E H. and using Proposition 4, we conclude that f 3 > IHen C),
The following proposition shows that it is sufficient to address counting attributed graphs
Proposition Let Ho be an unattributed connected graph. Assume that for any attributed graph H, which is constructed by adding arbitrary attributes to Ho. there exists an RNP-GNN fa (.: 0zz) such that fH 2 C(G: H), then for unattributed counterpart Hy, there exists an RNP-GNN f(:;0) with the same recursion parameters as f.:0:H)) such that f 2 (G; Ho).
Proof. If there exists an RNP-GNN (=: (x) such that fH 3 C(G; H), then for maximally expressive RNP-GNN (.: with the same recursion parameters as fH we also have f C(G: H). Let H be the set of all attributed graphs H E 8, X) E G5 up to graph isomorphism, where X E A for a countable set X. Note that H = H,, H2,... is countable set. Now we write
C(G;
Σ 1(G(S)= Ho}
(21)
8CIn
Σ E((G(S)= = =
(22)
84 iEN
Σ Σ ((G(S) = H.)
(23)
5chml
Σ C(G.H.).
(24)
EN
(25)
Now using Proposition& 4 we conclude that f 3 C(: Ho) since C(G; Ho) is always finite.
n
14

---

Under review as a conference paper at ICLR 2022
Definition 8. Let H. be (possibly attributed) simple connected graph. For any S C Vu and v E VH. define
dz(v;)) == max d(u, v). wES
(26)
Definition 9. Let H. be (possibly attributed) connected simple graph with k: 7 verfices. A permutation of vertices, such as (V1, U2...., 1,+1), is called a vertex covering sequence, with respect sequence (r1, . r7) N", called covering sequence, and only if
(u: r..
(27)
for i E [T + 11, where H; = HS,) and S; = {ur, 1i-1..... 17+1}. Let (T) denote the set of all vertex covering sequences with respect the covering sequence r for H.
Proposition 7. For any G, HH E Gg, if G 3 H (non-induced subgraph). then
CH(r) Co(r).
(28)
for any sequence r.
Proof. The proposition follows from the fact that the function d is decreasing with introducing new edges.
Proposition 8. Assume that Theorem I holds for induced-subgraph count functions. Then, it also holds for the non-induced subgraph count functions.
Proof. Assume that for a connected (attributed or unattributed) graph H, there exists an RNP-GNN with appropriate recursion parameters {- 0H) such that fH 2 C(G; H)) then we prove there exists an RNP-GNN f(; with the same recursion parameters fH such that C(G; H).
there exists an RNP-GNN (-; 0H) such that SH 2 C(G; H), then for a maximally expressive RNP-GNN (.; 0) with the same recursion parameters fa we also have f 2 CGG Note that
H(G,H) E
H(G(S):
(29)
scIm
Isi-k
Σ
Σ
Cn. x 1(G(S) = i
(30)
SEIn НEH()) si
= Σ
CH. H
(G(() = M
(31)
HEA(H)
SChJl 18
= Σ
CHHH X C(G,
(32)
ENN
where A(HH) = HH,, H2,.....
Claim 1. f2 H:) for any i.
Using Proposition 4 and Claim 1 we conclude that 3 Ō(G H) since Č(G; H) is finite and f C(G, H4) for any i, and the proof complete. The missing part which we must show here that for any Ht the sequence (21,,),...,77) which covers zi also covers H, This follows from Proposition 7. We are done.
At the end of this part, let introduce an important notation. For any attributed connected simple graph on l vertices = (V,E, X), let G be the resulting induced graph obtained after removing E V from G with the new attributes defined as
x= : (Xu, v ((u,v) E)),
(33)
for each V. (v). We may also use x for more clarification.
15

---

Under review as a conference paper at ICLR 2022
A.2 PROOF OF THEOREM 1
We utilize an inductive proof on r. which is the length of the covering sequence of H. Equivalently. due the definition, to Proposition 8, without loss of generality, we can assume that H is a simple connected attributed graph and the goal is to achieve the -sburrp count function via an RNP-GNN with appro- priate recursion parameters. We also consider only maximally expressive networks here to prove the desired result.
1, where k is the number of vertices in H. First, we note that due
Induction base. For the induction base, i.e., T = 1, H is a two-node graph. This means that we only need to count the number of specific (attributed) edge in the given graph G. Note that in this case we apply an RNP-GNN with recursion parameter 2 1. Denote the two attributes of the vertices in H by X X E X. The output of an RNP-GNN f(:66) is
f(G: = o( (X, (XXX"" : E NG, (o)B)) [n])),
(34)
where we assume that f): is maximally expressive. The goal is to show that f 2 C(G; H).
Using the transitivity of J, we only need to choose appropriate o, v. ip to achieve f f= C(G: H) as the final representation. Let
MH= (m]B) 2+ x 1 = X Σ 2
(35)
(x,, = x x 1 1(x 1x=xx1) 2' 1(x= X
(36)
n!'
n'
pli u [n( = Σ 1 1]}, Σ
11z = (XH,1)) 1)).
(37)
Then, simple computation shows that
f(G; 0) = ( ( pixx"" : :u (o) = H)
(38)
(39)
Since f(;;0) is an RNP-GNN with recursion parameter T1 and for any maximally expressive RNP-
GNN f(:; 0) with the same recursion parameter as f we have f コ f and f L C(G; H), we conclude that 2 C(G; H) and this completes the proof.
Induction step. Assume that the desired result holds for T 1 (r 2 2). We show that it also holds for T. Let us first define
=- (H; Joz................... ,,,,
U7 E [k] : (0i, Ur) E Cn(r))
(40)
c² (HH)) = 11 E HH) x #(v E [k] H = H²).
(41)
where Hº means the induced subgraph after removing a node, with new attributes (see A. Note that 71" 7 by the assumption. Let
| == Σ (HH).
(42)
HºEH-
For all HD Ht, using the induction hypothesis, there is (universal) RNP-GNN f(::)) with recursion parameters (r2,7a.... ra...., .r) such that f= C(G; H²). Using Proposition we conclude
Σ
C(G; H.).
(43)
Define maximally expressive RNP-GNN with the recursion parameters (r1, (21,72....,, r7) as follows:
f(G; o (
(Ns, : v e [n]]].
(44)
Similar to the proof for - = 1, here we only need to propose (not necessarily maximally expressive) RNP-GNN which achieves the function C(G; H).
16

---

Under review as a conference paper at ICLR 2022
Let us define
[H;(G:0) = ollvm; (x
: [m]
(45)
where
:0: [m]B)) = ||t*1] || Σ 22
(46)
i=1
(x) x 1 = x
(47)
(48)
and E fo = C(G; = Hj). Note that the existence of such function & is guaranteed due to Proposition
2. Now write
|7*1| x C(G: H))
|71
Σ [G((S) = H}
(49)
SgIn
Σ
Σ
1 E [k] (G(S) (v))); E A A =
(50)
( WES
Σ
Σ
1 E I.: (G(S) (,))) E H" A x = = (51)
MEiN] [E)
= Σ
Σ
e (G(S) {u))); e H Λ = x
ME n
vESCN,,
(52)
Σ
E
E
H(G(SM(b)) 11 =x (53)
eE veSCN, N (0) HEEN
Σ
Σ
(t)) x 11X. = =
(54)
MEIN H
which means that
Σ
(55)
uE|R]:H;ER Ex EN
However, for a maximally expressive RNP-GNN f(;; (): we know that f 2 fH; for all H E and this means that C(G; H). The proof is thus complete.
B PROOF THEOREM 2
For any attributed graph H nodes (not necessarily connected) claim that RNP-GNNs can count them.
Claim 2. Let (1:0) Gn + Rd be a maximally expressive RNP-GNN with recursion parameters (r (r- 1,r 2, ,,..., 1). Then, f H):
Now consider the function
GG) = ol (( S SV <T)).
(56)
We claim that / (f is defined the previous claim) and this completes the proof according to Proposition 2.
To prove the claim, assume that f(G) = fG2). Then, we conclude that C(Gi; H) = C(G2; H) for any attributed /l (not necessarily connected) with vertices. Now, we have
((G) o ((fvv)((S) S C V, |S| <T)
(57)
(H) H e G,, the multiplicity of is C(G;
(58)
which shows that ((G) ((G2).
17

---

Under review as a conference paper at ICLR 2022
Proof of Claim 2. To prove the claim, CH of graph H. If H connected, i.e., Cи = 1, then according to Theorem 1, we know that (
induction the number of connected components
Now assume that the claim holds for eи = c- 2 1. We show that it also holds for eи = c. Let H1, H....., He denote the connected components of H. Also assume that H, H2 for all i + j- We will relax this assumption later. Let us define
Aa = {(S1, S...,, Sc) Vi [c] : S [m]: G(S,) H.).
(59)
Note that we can write
Aa
II C(G: t=1
(60)
= C)G + H.) 1=1
(61)
where Hi: Hy.... are all non-isomorphic graphs obtained by adding edges (at least one edge) be- tween e graphs H1, H2...., He, or contracting number of vertices of them. The constants of are just used to remove the effect of multiple counting due to the symmetry. Now, since for any H1, H3 the number of connected components is strictly less that c, using the induction, J C(G; H:) and f 2 C(G; HJ) for all and all E [c]. According Proposition 4, conclude that f C(G; H) and this completes the proof. Also, H,, [c], are not pairwise non-isomorphic, then we can use (C(G; H) in above equation instead of C(G; H). where a > removes the effect of multiple counting by symmetry. The proof is thus complete.
have
Remark 1. As we explained in the above proof, one can modify Theorem graphs. To this end, we need to generalize the notion of covering sequence to hold for this class of graphs. Since this special case out of scope of this paper, we only restrict special, but more insighiful case.
hold for disconnected
C PROOF OF THEOREM 3
To prove Theorem 3, we need to bound the number of node updates required for an RNP-GNN with recursion parameters (f1, (21, rz). tations of vertices. For each vertex 01 E V. we explore the local neighborhood Nr, (v1) and apply new RNP-GNN network to that neighborhood. In other words, for the second step need to update [W, (V1) nodes. Similarly, for the ith step of the algorithm we have at most
First of all, we have variables used for the final represen-
A = max max e| EeegNNy WeEl-1
[W (11) NW (o) (Wr
O NN, (w:))
(62)
updates. Therefore, we can bound the number of node updates as
Y X
X
(63)
1=1
Since A; is decreasing in i, the desired result holds.
D PROOF OF THEOREM
Let K₂ denote the complete graph on vertices.
Claim 3. For any k n N, such that n is sufficiently large,
[C(G, KR) G
G.)/2 GG.)
(cn/(k ((looo///k)) - k))²
= =((n
(64)
k!
where is constant which does not depend on k
18

---

Under review as a conference paper at ICLR 2022
In particular, claim that the number of different values that C(G; take is n², up to poly-logarithiic factors.
To prove the theorem, ((;0) which can count any substructure on k vertices, As result. f 3 CG;; Ks) for an appropriate
the above claim. Consider a class of (s. t)good graph representations
parametrization 0. By the definition, f(-) must take at least [C(G; K&) G E G different values, i.c.,
( 2
(65)
Also,
(S(G:O): GG Gn) [[v(G.) :e : c.c.) where (G1, G2 ...., ,.i) = EGG). But, can take only values. Therefore, have (C(G: G G..
(66)
< (S(G:0) Ge C.)
(67)
$ [W((G)) :i | G G.)
(68)
< [Maa E [1 vi (1) oo [+]]
(69)
s (t + 1)
(70)
As result, (t + 1)a-1 = =((n=* ort t- 11) To complete the proof, we only need to prove the claim.
Proof of Claim 3. Let P1,P2..... ........pe Pm be distinct prime numbers less than n/k. Using the prime number theorem, we know that limn- [/(loog(//k)) = 1. In particular, we can choose n large enough to ensure en/(A log(n/k)) < for any constant < 1.
m
For any {b), b2...., ......,,,, ba} S [m]] define GB as a graph on n vertices such that VGe Vo L (UbeT V:), and [V:] = pb. Also.
(u, v) GB + 3i,j E [m]. i + u & V/. The graph GB is well-defined since Σ Ph. S n/k: = n. Note that C(GB; K&)
(71)
I Ph.-
Also, since Pt, E [m], are prime numbers, there is unique bijection
B B C(GB; K&).
(72)
Therefore,
(C(G: KR) : Gn) 2 [C(Gs; K&): B C [m], |8| k}
(73)
m
(74)
(m
k)**
(75)
k!
(cn/ (k log(n/k)) - k)*
(76)
k!
E RELATIONSHIP TO THE RECONSTRUCTION CONJECTURE
Theorem provides universality result for RNP-GNNG Here, note that the proposed method is closely related to the reconstruction conjecture, an old open problem in graph theory. This motivates explain their eeltiiosshipddifferenees. First, need definition for unattributed graphs.
Definition 10. Let F, C Gn be a set of graphs and let G, = G(V \ (v)) for any finite simple graph G = EV,E), and any E V. Then, we say the set F is reconstructible if and only if there is bijection
(G, : L.UVVV " G,
(77)
for any G F.. In other words, Fa is reconstructible, if and only if the multi-set set {G,, : E VB fully identifies G for any G E F..
19

---

Under review as a conference paper at ICLR 2022
It is known that the class of disconnected graphs, trees, regular graphs, reconstructible (Kelly, 1957; McKay, 1997). The general case still open; however it is widely believed that it is true.
Conjecture (Kelly (1957)). Gn is reconstructible.
For RNP-GNNs, the reconstruction from the subgraphs G V [n] possible, since we relabel any subgraph (in the definition of X*) and this preserves the critical information for the recursion to the original graph. the reconstruction conjecture, this part of information is missing, and this makes the problem difficult. Nonetheless, since in GNNs preserve the original node's information in the subgraphs with relabeling, the reconstruction conjecture is not required to hold to show the universality results for RNP-GNNS although that conjecture is motivation for this paper. Moreover, it can shown that the reconstruction conjecture it true, it may be also possible to find simple encoding of subgraphs complex new GNNs.
original graph and this may lead to more powerful but less
F THE RNP-GNN ALGORITHM
In this section, provide pseudocode for RNP-GNNs. The algorithm below computes node rep- resentations. In the algorithms,, we frequently use MLP modules with ReLU activation. For graph representation, we can aggregate them with common readout, e.g., hig < MLP (LP(( Evev ((()) pooling here, to ensure that
Following (Xu et al., 2019), aggregation functions.
represent injective
Algorithm Recursive Neighborhood Pooling-GNN (RNP-GNN)
Input: G = (V, E, (Ie]vev) where V [m]. recursion parameters F1, ?2....,Ty E N. e() E R,
E [r), node features (orJoEy.
Output: h, for all E V
ht - F, for all v E
if T then
ho MLP(F.1) (1+e +
Σ
MLP ((, =))).
ueN. (o]lee)
for all v E V. else
for all v E V do
G¹, G-G(,, (v) \, {u}), which has node attributes {(h 1(u, v) E EE) EYTeE,, (o) (hemuuuec + RNN--GNN(G,,, (r2, ......, rr), (c(2) c())) h + (LP(()) (1++e())ni) Eveoy iru.))
end for end if
return (hr
With this algorithm, one can achieve the expressive power of RNP-GNNs if high dimensional MLPs allowed (Xu et al., 2019; Homik al., 1989; Homik, 1991). That said, in practice, smaller MI. may be acceptable (Xu et al., 2019).
G COMPUTING A COVERING SEQUENCE
As explained in the context of Theorem 1, need covering sequence (or upper bound to that) to design an RNP-GNN network that can count given substructure. A covering sequence can be constructed from spanning tree of the graph.
For reducing complexity, it is desirable to have covering sequence with minimum Ti (Theorem 3). Here, suggest algorithm for obtaining such covering sequence, shown in Algorithm 2.
20

---

Under review as a conference paper at ICLR 2022
For obtaining merely an aribtrary covering sequence, compute any minimum spanning tree (MST), and then proceed as with the MST in Algorithm
Given MST, we build vertex covering sequence by iteratively removing leaf from the tree and adding the respective node e, to the sequence. This ensures that, at any point, the remaining graph is connected. At position i corresponding U4 the covering sequence contains the maximum distance r; of v; to any node in the remaining graph, or an upper bound on that. For efficiency, an upper bound on the distance can be computed in the tree.
To minimize Tı = max d(u, v1), we need to ensure that node in arg minggy max d(u, v) leaf in the spanning tree. Hence, first compute maxney d(u, v) for all nodes u, e.g., by (APSP) (Kleinberg & Tardos, 2006), and sort them in increasing order by this distance. Going down this list, we try whether it is possible use the respective node as 01, and stop when we find one.
running -.PParr--Shorestt
Say the current node in the list. To compute spanning tree where 2* is leaf, we assign large weight to all the edges adjacent to v", and very low weight to all other edges. If there exists such a tree, running an MST with the assigned weights will find one. Then, we use 8² as in in the vertex covering sequence. This algorithm runs in polynomial time.
Algorithm 2 Computing a covering sequence with minimum T1
Input: И = (V, E, X) where V = [T [T+ +1]
Output: A minimal covering sequence (21, TT), and its corresponding vertex covering
quence (U1,
For any u, V, compute d(uu, v) using APSP
(u1, .2, 4y+1) < all the vertices sorted increasingly in s(u) == m d(u, v) for = to + do
Set edge weights w(u, = x 11 [u us V v = u.} for all (u, v) E
HT & the MST of H with weights if us is a leaf in Hr then
01 ui
s(u))
break
end if
end for
for i 2 to
do 0 < one of the leaves of Hy
r; 4- max d(u, vz)
H1 +- HT after removing i;
end for
return (r1, (21,72....,,7 and (U1, ... .,, Dr41)
H EXPERIMENTAL DETAILS
Table 4: Runtime (in seconds) averaged over 10 epochs of training on the synthetic triangle counting experiments on Prdōs-Renyl graphs. Times do include LRP preprocessing (which takes several minutes for this dataset).
Model
Parameters
Runtime (s)
RNP-GNN, r = =(11))
10210
153.13
RNP-GNN, 1,,
10834
199.49
RNP-GNN, -= 12
10210
370.38
RNP-GNN,
12,1,,1
10834
835.77
GIN
10186
.88
Deep-LRP
10231
24.43
21

---

Under review as a conference paper at ICLR 2022
H.1 DATASET AND TASK DETAILS
For the counting experiments, we follow the setup of Chen al. (2020). There are two datasets: one consisting of 5000 Erdös-Renyi graphs (Erdos et al., 1960) and one consisting of 5000 noisy random regular graphs (Steger & Wormald, 1999). Each Berlös-Renyl graph has 10 nodes, and each random regular graph has either 10, 15, 20, or 30 nodes. Also, random edges are deleted from each random regular graph, where n is the number of nodes.
For the experiments distinguishing non-isomorppic graphs. we the EXP dataset (Abboud et al., 2021). This dataset consists of 600 pairs of graphs (so 1200 graphs in total), where each pair is 1-WL equivalent but distinguishable by 3-WL, and each pair contains one graph that represents satisfiable formula and one graph that represents an unsatisfiable formula. On average, each graph contains about 44 nodes and 1 110 edges (Balcilar et al., 2021). We report the mean and standard deviation across 10 cross-validation folds. Additionally, we report the runtimes in Table 4 for the counting experiments.
H.2 RNP-GNN IMPLEMENTATION DETAILS
Here, we detail some specific design choices we make in implementing our RNP-GNN model. Most embeddings are computed in E for some fixed hidden dimension d. The input node features first embedded I2d by an initial linear layer. Then RNP layers are applied to compute node representations. Finally, graph-level output.
pooling across nodes followed by final MLP is used to compute
An RNP layer for r (r1, (ri,...,Trr) ,r) is implemented as follows. Note that the input node features to this layer are in R2d due to our initial linear layer. Also, note that we concatenate an extra feature dimension due to the augmented indicator feature at each recursion step. To align these feature dimensions, for E [r]. we parameterize the I-th GIN (Xu et al., 2019) by a feedforward neural network MLP(), RR++ + Rd-1-1, For instance, the last GIN has feedforward network MLP(()) Rd+r + Rd++-1, because after r levels of recursion we have augmented r features. Dropout and nonlinear activation functions only applied in the MLPs.
H.3 HYPERPARAMETERS
For all baseline models, we take the results from other papers. Thus, for the counting experiments the configurations for the baseline models are from Chen et al. (2020), while for the EXP experiments the configurations for the baseline models are from Abboud al. (2021).
RNP-GNN hy typerparameters. For all experiments we ran random search over hyperparameters. In all cases we used the Adam optimizer with initial learning rate in {.01, .001, ,0001, .0005). We train for 100 epochs with a batch size in {16, 32, 128). The number of stacked RNP-GNNs for computing node representations is in (1, We use a dropout ratio in {0, .5). The recursion parameters used varies for each task. We used two layers for each MLP used in the aggregation function. Also, the graph-level output obtained after sum-pooling across nodes computed by a two layer MLP.
Specifically for the counting experiments, the number of hidden dimensions is searched in 316,32, 32, 64). For all tasks we used r = 1. In particular, the optimal parameters for RNP-GNN were: (1, 1) for triangles on Erdös-Renyl
(1, 1) for stars Erdös- Reniss,Reni,,aa r (1, for triangles on random regular and r = (1, 1, 1) for stars on random regular. We use ReLU activa- tions in the MLPs. We either decay the learning rate by half every 25, 50, or oc epochs (where do means never decaying).
For the EXP experiments, the number of hidden dimensions is searched in (8, 16, 32, 64). We use either ELU or ReLU activations in the MLPs. We decay the learning rate by half at the 50th epoch. The recursion parameters are (2, 1).
22

---

Under review as a conference paper at ICLR 2022
1
MORE FIGURES
Figure 3: MPNNs cannot count substructures with three nodes or more (Chen et al., 2020), For example, the graph with black center vertex on the left cannot be counted, since the graphs on the left result in the same node representations as the graph on the right.
01
122
13
01
211
V2
F3
00
175
16
M5
1/1
05
16
Figure 4: Example of covering sequence computed for the graph the left. For this graph, (Mg, U1, Ug, Us U3 02) vertex covering sequence with respect to the covering sequence (3,3, 2, 1). The first two computations obtain this covering sequence are depicted in the middle and on the right.
23


Reviews:
[{"review_id": "iF6DZdumH7Y", "reviewer": "Reviewer_bVPW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this is a practical deep learning contribution, with a specific problem (counting sub-graphs) to solve, despite than a large portion of the paper is spent on theoretical analysis. The novelty mainly lies on how the recursive neighbourhoods are defined. This is not significant and sits in a family of similar structured GNNs. From my view, the paper is borderline on the negative side.\n\nThe writing is well polished. However, the notations system is a bit cumbersome and hard to interpret.  The quality of the statements can be improved. For example, it is not clear what is the exact computation of \"AGGREGATE\" and what is the non-linear activation here.  Theorem 1 is only significant if f outputs an integer, of the difference |f(G_1,\\theta)-f(G_2,\\theta)| can be lower-bounded.  Similar for theorem 4. Theorem 2 is a weird way to state universal approximation, as we usual states upper-bound on the difference between the neural network and a given function by an arbitrary small \\epsilon.\n\nAs an important hyper-parameter, the proposed method relies on a vector of radius (r_1, r_2, ... ) that are recursively used in the neighborhood nodes when building the presentation of any node. The overall complexity scales with the size of N_{r_1}, or the size of the\nr_1-neighborhoods. In the experiments, $r_1$ is set to a very small value (1 or 2). This is in general an expensive method and only suitable for small-degree graphs, and related application (like counting triangles).\n\nAs a practical deep learning contribution, the experiments section is too brief.  First, what is the setting of  (r_1, r_2, ...), which is perhaps the most important parameter, is not specified (instead, there is pointer to Appendix). The statistics of the dataset are also missing, especially, it  is important to say more details about the EXP dataset, and what are \"certain propositional formulas\" and their sizes.\nSecond, in the first experiment on counting regular sub-graphs. As Deep-LRP (rather than the authors' method) has the best performance,\nit is important to have another experiments to compare their efficiency. Ideally, the authors can show that Deep-LRP is much slower than the proposed RNP-GNN, so the proposed method still wins overall.\n\n#### Minor comments:\n\nThe notion of \"count substructure\" should be clearly defined when it is mentioned in the introduction. What is a substructure, and what is the space when the counting is performed, etc.\n\nSec 2 the introduction to Higher-Order GNNs can be improved,  as currently it is not so clear what are the underlying operations\nof Higher-Order GNNs. I suggest to use some equations similar to eq.(1)\n\neq.(7) explain what is MLP, and how its parameters/structures are set\n\neq.(7) explain \\epsilon\n\nSection 4, at the end, explain on what settings, the proposed RNP-GNN becomes exactly MPNN.\n\neq.(8) explain the \"\\bold{1}\" notation, also \"\\simeq\"\n\nDefinition 4, explain the difference between {S} and \\calligraphic{S}\n\nDefinition 4, is \\caligraphic{V} introduced in the body of the definition?", "summary_of_the_paper": "This paper studies the problem of counting isomorphic sub-graphs in a given graph. The author proposed a new graph neural network (GNN), named RNP-GNN, which operates by recursively aggregating node representations based on different settings of the radius. A difference with previous work is that, during recursion, this aggregation is always performed on recursive *subsets* of neighborhoods.  Figure 1 gives an intuitive toy example of the computation process.\n\nThe authors also did some theoretical analysis, to show that it is more capable to count sub-graphs, to show that RNP-GNN satisfies universal approximation properties, and to give the exact computation complexity.\n\nThe method is tested on counting small structures on random graphs and Erdos-Renyi graphs (which have a very small size, <=30 nodes), and counting non-trivial sub-graphs on the EXP dataset by Abboud et al. (2021), showing better performance than most baselines.", "summary_of_the_review": "Pro:\n- A simple GNN that is well explained\n- Good writing\n\nCon:\n- Insufficient experimental evaluation\n- Quality of mathematical statements", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fX9UsS8Fra9", "reviewer": "Reviewer_T3yH", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "To the best of my knowledge, this is the first time that the algorithmic technique of recursion is employed to define a Graph Neural Network. From a theoretical perspective, the paper is quite strong, and given that substructure counting is arguably a necessary property for a plethora of tasks in graph learning, the universality of RNP in that respect makes the proposed solution quite appealing. Moreover, the computational complexity analysis, as well as the fact that the authors bring impossibility results from the field of complexity theory to the machine learning community, is very insightful. \n\nMy major concern right now is the practicality of the method which is reinforced by the fact that the experimental section is quite weak. In particular, in my opinion, the paper raises the reader’s expectations, since the fact that there is a clean procedure to define the recursion neighbourhood sizes creates the impression that it is straightforward to design RNP-GNNs that can perform well not only in counting tasks but also in downstream applications (recently many papers have demonstrated the superiority of GNNs that use information from substructures), albeit with arguably increased computational complexity. However, these expectations are not met, since RNP does not seem to enjoy a clear advantage in simple counting tasks in comparison to other methods, while real-world data are completely omitted. \n\nThe above, as well as the fact that RNP is not tested in more challenging tasks, indicate that there might be an inherent practical limitation of RNP, regarding which I am afraid that the authors are not completely upfront. For example, an obvious disadvantage is the exponential dependence in the maximum size of the subgraphs of interest, which might imply that the method is practical only for very small subgraphs. Although the authors argue that this might be hard to improve, there are some cases that this is not true. For example, as far as I know, it is not clear if k-WL algorithms can count *induced* subgraphs of size $>k$, but in some cases, they can achieve this for *not necessarily induced subgraphs*. For example, Arvind et al., FCT’19 and Fürer, CIAC’17 show that 2-WL can count not necessarily induced cycles and paths of up to 7 vertices with $O(n^2)$ complexity, while RNP will need $O(nr_1^6\\Delta^{6r_1})$ to solve this task, which will be prohibitive unless the valence of the graph is very small. \n\nAt this stage, I am reluctant to suggest a clear acceptance for the paper, since (1) I cannot be sure if it can be implemented in practice and (2) I believe that a stronger experimental section would increase the impact, which will be beneficial both for the authors and the community in general. Below, I provide further details:\n\n**Strengths**:\n-\tThe idea is interesting and novel since it introduces a completely new paradigm for GNNs with clear expressivity advantages.\n-\tThe theoretical results are important, well-posed and in some cases quite general providing new insights into how to prove substructure counting abilities for GNNs. Several constructions and proof techniques are of independent interest which is also positive. For example, the construction of a graph family using prime numbers in Theorem 4, Claim 3, is in my opinion quite clever.\n-\tThe fact that we can define the recursion neighbourhood sizes via the construction of the covering sequences of the subgraphs of interest, provides practical advice and can save the practitioner from tedious hyperparameter tuning.\n-\tThe complexity analysis, although it mainly contains worst-case results, has wide applicability and provides insights into the limitations of GNNs in general.\n\n**Weaknesses**:\n- The presentation of RNP does not seem to imply that it is a purely theoretical construction. For example, the argument that the complexity of RNP depends on the sparsity of the graph, contrary to higher-order GNNs is compelling (note that this argument is introduced early on, in the abstract, and this perhaps exceedingly raises expectations). However, the experimental section currently points towards the opposite direction. Can the authors clarify their position w.r.t. that?\n- For example, I would expect the triangle counting task to be relatively easy for this network, but RNP does not seem to be better than other more expressive GNNs. The same holds for the 3-star where GraphSage performs much better (question: is GraphSage permutation sensitive here?). How do the authors comment on that? What is the depth of the recursion that you used (is it 2 as expected from the theory)? In general, what is it that prevents RNP from being implemented in a practical form and why isn't it clearly better in these two experiments. Is it only the computational complexity (that perhaps makes it harder to do more extensive experimentation)? Does it have to do with optimization and/or generalisation (it wasn't clear to me if there is a hold-out test here)? \n- Unless the method is purely theoretical, I think the authors would benefit a lot from creating a working instantiation of their model and a simple experimental section with more convincing results. Suggestions: (1) counting various substructures and contrasting their r parameters with those predicted by the theory, (2) real-world datasets where substructure counting is important (a single one would be OK – it might be useful here to measure the runtime of your method and contrast it with the sparsity of the graphs)  and optionally (3) predicting graph properties. \n- Although the paper is generally well-written, it is notation-heavy and at some points requires significant effort to parse the mathematical expressions. In my opinion, the authors should try to simplify some parts in order to make it more accessible to readers not versed in the theory. For example:\n  1.  Architecture - Eq (3-7). This is the heart of the proposed method, but it is a bit hard to follow. Notation can be off-loaded at some points (e.g., Eq.  (5) is very important since it is the recursion formula, yet it’s quite complicated - what is G’? Why do you write h_{u,v}  in Eq. (5) and h_{v,u} in Eq. (6)?)\n  2. Could the authors provide an explanation by unrolling the recursion? This might help the reader develop intuition and compare RNP to conventional iterative GNNs.\n\n**Other comments and questions**: (I don’t expect all these to be addressed in the rebuttal, but it might be useful to clarify in the next revision of the paper)\n-\tHow important are the identifiers used to augment the node embeddings (Eq. (3))? Can RNP retain its expressive power without them or it might collapse to that of an MPNN? Regarding the connection with the reconstruction conjecture: How important is the removal of the central node while recursing? In terms of complexity it’s beneficial to remove the central node, but is it crucial in terms of expressive power?\n-\tWhat happens in case we want to count a subgraph that is disconnected? How can you define the covering sequence in this case? I think the authors make such an argument in the proof of Theorem 2, but this is not clear from the main paper.\n-\tI believe at least the proof idea for Theorem 1 should be given in the main paper.\n-\tAs far as I understand, the lower bound of Theorem 4 applies only to functions of the form of Eq. (12), i.e., those that encode $t$ subgraphs with $s$ different unique values and then take the resulting histogram. Is that general enough? Also, although, as I said above, I found the construction of clique-containing graphs very clever, I am wondering if the lower bound is very loose since it is based on counting these graphs only. Finally, personally, I would call it a counting argument rather than information-theoretic (I was expecting to see something else in the proof when I first read it). \n\n\n**Minor**:\n-\tYou wrote: (Background. Higher-Order GNNs.) “At initialization, each k-tuple is labelled such that two k-tuples are labelled differently if their induced subgraphs are not isomorphic”. If I am not mistaken, k-WL labels k-tuples based on their isomorphism *types*, which is different from isomorphism *classes* since it takes into account the order of the vertices in the tuple as well. \n-\tThe following sentence is unclear: “In particular, we show how the aggregation “augments” local encodings, if they play together and the subgraphs are selected appropriately”.\n-\tProposition 6: You state “there is no difference between counting induced attributed graphs and counting induced unattributed graphs in RNP-GNNs”, however, if I am not mistaken your argument does not go both ways. Is that correct?\n-\tDefinition 7 requires further clarifications/is quite hard to follow (e.g., I am not sure if I understand the term homomorphism here since homomorphisms allow vertex repetitions).\n-\t“However, it is known that MPNNs can count at most star structures or edges”: missing citation: \"On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties\", Arvind et al., FCT’19\n\n\n### --------------- After rebuttal ---------------\n\nMy major concerns were not addressed by the rebuttal, hence I will keep my recommendation unchanged. Please see my final comment to the authors for more details.\n", "summary_of_the_paper": "This paper proposes a new theoretical paradigm for designing Graph Neural Network architectures, based on recursion. Differently from conventional architectures that iteratively update node embeddings by computing a function of the embeddings of the previous step (locally for MPNNs or globally for higher-order GNNs), *Recursive Neighborhood pooling (RNP)* recursively updates the node embeddings by computing a function of the embeddings of the next level in the recursion hierarchy. Importantly, at each level the computations happen in different neighborhoods in the graph (of potentially different sizes) and node embeddings are enhanced with identifiers that keep track of the graph connectivity.  The authors prove that RNP can count any substructure (induced or not necessarily induced, attributed or not) by appropriately selecting the neighborhood sizes at each recursion level, and show that this implies universal approximation of local functions that depend on substructure counts. Importantly, they provide an explicit procedure to compute the required neighborhood sizes for each substructure of interest, which can potentially be useful for practitioners. In addition, they analyse the computational complexity of RNP and contrast it with theoretical lower bounds, showing that it is close-to-optimal for specific classes of graphs. The proposed framework is tested on two tasks including subgraph counting and graph isomorphism partially verifying the theoretical results.", "summary_of_the_review": "The paper is quite rich and insightful from a theoretical perspective, but currently, it is unclear if and how it can be implemented in practice and if it can work well. The authors should prepare a much stronger experimental section and clearly discuss the limitations of their approach. I am not negative about the paper, but I believe that this part is crucial to recommend acceptance. I would be willing to discuss my score after that.", "strength_and_weaknesses": "", "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": "Naeq7qLa1OH", "reviewer": "Reviewer_572g", "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": "Strengths:\n* The paper addresses and important problem: most GNN architectures are not expressive enough for many tasks, and architectures that are, are not always feasible. RNP-GNN offers a trade-off between the expressiveness and computational-needs.\n* The proposed architecture is backed with wide theoretical analysis, proving that it can count substructures and that it can approximate local graph functions. \n\nMain weaknesses:\n* The presentation of the method, described in section 4, was hard to follow, even with the example in Figure 1. I think a clearer explanation would improve the paper.\n* According the computational complexity analysis, even with small $c$ and $\\tau$ (paragraph after Theorem 3), RNP-GNN will join most higher-order architecture and become unfeasible. I.e., in large, not so sparse graphs the method will not be feasible, yet for small graphs other GNN architectures can be just as good. \n* In the experiments sections, I'd like to see a comparison between RNP-GNN and the other architectures with similar performance, so I can see if there is a real improvement w.r.t. accuracy/speed/memory etc.\n\nAddressing the first and last weaknesses will help me change my score.", "summary_of_the_paper": "While GNN architectures became very popular in recent years, their expressive power is limited. Higher order architectures offer more expressive power, but in turn require sometimes infeasible computation power. This paper offers a new architecture (RNP-GNN) that uses recursive pooling in and offers a trade-off between the expressiveness and the computational needs. The paper provides a theoretical analysis of the proposed architecture, as well as 2 experiments. ", "summary_of_the_review": "To summarize, the paper studies an important problem, and proposes an architecture with strong theoretical justifications. In practice, I'm not convinced that the new architecture has any real advantages over existing, simpler architectures.\n\nI (weakly) support the acceptance of the paper.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JWf_w7GFzpv", "reviewer": "Reviewer_vpVz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents a fundamental pooling technique that could inspire the construction of future GNN architectures.\nThe theoretical analysis is quite thorough and places the work in the context of other works. \n\nI have however encountered difficulty reading it and understanding some of it:\n\n1. **Clarity and Readability** - I find the paper packed and hard to follow, although it seems that the authors put a lot of effort into defining every bit of notation.\n\n2. **The algorithm** - \n     - It is not clear to me what happens in the recursive pooling calls when the removed vertex disconnects the remaining subgraph? \n     - How do the authors choose $(r_1,..._r_{\\tau})$ and for instance - how many subgraphs of interest share the same covering sequence? or whether several covering sequences should be used together?\n\n3. **Scalability** - Although providing results on improved complexity, the method is only demonstrated on toy datasets, what are the gaps for scalability in real world datasets?\n\n4. **Larger substructures** - results are shown only on substructures of size 3, I would have wanted to see results on larger ones. \n\n- result in table 3 of PPGN performance seem weird as PPGN expressivity should allow to learn the EXP dataset, see [1]\n\n[1] Balcilar, M. et al. “Breaking the Limits of Message Passing Graph Neural Networks.” ICML (2021).\n\n", "summary_of_the_paper": "Motivated by the limitations of the expressive power of MPNNs this paper addresses one of the expressive shortcomings --- counting substructures. \nWhile previous works allowed counting by suggesting higher-order GNNs, they come at a high computational cost. This paper introduces a flexible recursive pooling technique that provides control over the expressivity-complexity tradeoff. The authors analyze the proposed framework and show expressivity results, complexity results under sparse graph assumptions, and an information-theoretic lower bound. Finally, the paper presents results on toy datasets validating the theoretically guaranteed expressive power.", "summary_of_the_review": "The paper introduces a novel framework and provides a detailed analysis, but the readability issues are shading it. ", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "FVVqjIniB-S", "reviewer": "Reviewer_BQ8d", "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": "I think this paper suggests a very interesting GNN architecture, which essentially allows more expressive power than standard MPNN, while not using k-th order tensors such as in higher-order GNNs. In this aspect, this paper makes a step forward in our understanding of the expressive power of GNNs. Theorem 1 and Theorem 2 successfully provide theoretical guarantees for this architecture, while the experimental part shows that this architecture is indeed successful in tasks in which standard MPNNs fail (such as the EXP dataset, and counting subgraphs). Finally, the information-theoretic and computational complexity lower bounds show that such tasks cannot be solved in a more efficient way. The paper is also well presented and easy to follow.\n\nI have two concerns about the paper which I would be happy to see the author’s response:\n\n1) The comparison of computational complexity to other models in Section 5.3 is unclear, and it is also unclear whether RNP is really more efficient asymptotically than k-WL. \nTo put into context, suppose \\Delta=O(1), and our task at hand is to count a certain subgraph with k nodes. by Table 1, the time complexity of k-WL is n^k, and for RNP it is O(n). But, according to Theorem 1, to count subgraphs with k nodes requires that the \\tau in RNP is k-1. This means, according to Theorem 3, that the time complexity (asymptotically) is exponential in k. Hence, it is not clear that RNP is more efficient than k-WL. Also, if k=O(1), then the time complexity of k-WL is n^{O(1)}, which seems to be the same as RNP. I think the authors should give a more concrete case on why RNP is more efficient than higher-order GNNs.\n\n2) The experiments are done only on artificial datasets such as counting subgraphs from random graphs, and the EXP dataset from Abboud et al. which is specifically designed to test 3-WL. It would be beneficial to test whether RNP is successful also on real datasets, otherwise, it is not clear whether RNP can also be used in more realistic settings. For example, testing on datasets from the OGB collection or TUDatasets.\n\nOther minor comments:\n\n1) I think the authors should give more motivation on why counting subgraphs is an interesting task, besides being studied in a previous paper.\n\n2) There are a couple of notations that are used throughout the paper but are not defined, e.g. V(G), \\Epsilon(G) G(A) (where A is a subset of nodes), \\mathbb{G}_n. They may be standard graph theory notations, but I still suggest adding a short notations section to prevent ambiguity.\n\n3) Although Theorem 2 shows a universal approximation property, the connection to the approximation power of k-WL is unclear. Given a certain choice of (r_1,...,r_\\tau), where \\tau=k-1, is RNP and k-WL equivalent in approximation power, or is there still a gap? I think this should be clarified in the paper.\n\n4) In Appendix F, r_t-> r_\\tau (in the input).\n\n5) In Section 8 it says: “we leave further developments of practical variants of RNP-GNN to future work.” What does it mean? Is RNP as described in the paper not practical?\n", "summary_of_the_paper": "The main contribution of this paper is to propose a novel GNN architecture called RNP-GNN. This architecture seems to be specifically designed to tackle the task of counting subgraphs. The authors prove two expressiveness results: (1) RPN-GNN succeeds in the task of counting subgraphs (with an appropriate parameter choice); (2) RPN-GNN has the universal approximation property w.r.t local graph functions. Also, the computational complexity of this architecture is calculated. The authors also provide information-theoretic and computational complexity lower bounds. Finally, several experiments are done on the EXP dataset, and on counting substructures from random graphs.", "summary_of_the_review": "I think this is a good paper that provides a novel GNN architecture that on the one hand is more expressive than standard MPNN and on the other doesn’t require k-th order tensors to compute. The theoretical aspect of the paper is very thorough and gives insights both into the expressive power of RGP and on lower bounds for the task of counting subgraphs. On the experimental side, the current experiments presented in the paper provide evidence of the expressive power of RGP.\nMy two concerns are whether RGP is really more computationally efficient than k-WL, and whether it would outperform other MPNNs on standard benchmarks from the GNN literature. I would be happy to read the author’s response and consider raising my score accordingly.\n", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission has been evaluated by 5 reviewers with 3 leaning towards borderline accept and 2 leaning towards borderline reject. Reviewers have been consistently concerned about several aspects of this work, i.e. that *the method is only demonstrated on toy datasets*, that there is an issue with the scalability to larger substructures, that the proposed approach did not excel *in the simple task of triangle counting* or even that *the authors did not perform any other experiments even on a toy dataset*, and that comparisons on Deep-LRP re. efficiency were not provided, and *more complex settings and sensitivity* were not investigated. Reviewers also noted that the general idea of recursion did already appear in GNNs in one or another setting.

In making this decision, AC agrees that there is some potential in the proposed analysis and reviewers also highlighted this as a positive side of the submission. Yet, it is really hard to overlook at the same time the rebuttal where authors had the chance to address all reviewers comments regarding the experiments, their various details, and their variations.

Failing to address these comments to the satisfaction of the majority of reviewers makes it impossible for AC to recommend the acceptance even tough there is every chance that the paper will ultimately make it to a high quality venue after a thorough revision (reviewers have really given a fair number of good suggestions that should assist authors).
Decision: Reject