Recursive Neighborhood Pooling for Graph Representation Learning
Authors: Behrooz Tahmasebi
Stefanie Jegelka
Venue:  (2021)

Abstract: While massage passing based 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, which substantially increase the expressive power, but at a large computational cost.
  Motivated by this gap, we introduce and analyze a new recursive pooling technique of local neighborhoods that allows different tradeoffs of computational cost and expressive power. First, we show that this model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. Second, we prove that, in several cases, RNP-GNNs can greatly reduce computational complexity compared to the existing higher-order $k$-GNN and Local Relational Pooling (LRP) networks. 
 

Under review as a conference paper at ICLR 2021
RECURSIVE NEIGHBORHOOD POOLING FOR GRAPH REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
While massage passing based Graph Neural Networks (GNNs) have become in- creasingly popular architectures for learning with graphs, recent works have re- vealed important shorteomings in their expressive power. In response, several higher-order GNNs have been proposed, which substantially increase the expres- sive power, but at a large computational cost. Motivated by this gap, we introduce and analyze a new recursive pooling technique of local neighborhoods that allows different tradeoffs of computational cost and expressive power. First, we show that this model can count subgraphs of size k. and thereby overcomes known limita- tion of low-order GNNs. Second, we prove that, in several cases, RNP-GNNs can greatly reduce computational complexity compared to the existing higher-order k-GNN and Local Relational Pooling (LRP) networks.
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 used in applica- tions such as encoding molecules, simulating physics, social network analysis, knowledge graphs, and many others (Duvenaud et al., 2015; Defferrard et al., 2016; Battaglia al., 2016; Jin et al., 2018). An important class of GNNs is the set of Message Passing Graph Neural Networks (MPNNs) (Gilmer et al., 2017: Kipf & Welling, 2017; Hamilton al., 2017; Xu et al., 2019; Scarselli al., 2008), which 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, at best, corresponds to the one-dimensional Reisfeiler-LLema (I-WL) graph isomorphism test (Xu et al., 2019; Morris et al., 2019), so they cannot, e.g., distinguish regular graphs. Moreover, they also cannot count any induced subgraph with at least three vertices (Chen et al., 2020), or learn graph parameters such as clique information, diameter, or shortest cycle (Garg et al., 2020). Still, in several applications, e.g. in computational chemistry, materials design or pharmacy (Elton et al., 2019; Sun et al., 2020; Jin et al., 2018), we aim to learn functions that depend on the presence count of specific substructures.
To strengthen the expressive power of GNNs, higher-order representations such as k: GN-NNs (Morris al., 2019) and k Invariiin Graph Networks (K-IGNs) (Maron et al., 2019) have been proposed. k-GNNs are inspired by the k-dimensional WL (k-WL) graph isomorphism test, message pass- ing algorithm on k-tuples of vertices, and k-IGNs are based on equivariant linear layers of feed-forward neural network applied to the input graph as matrix, and are at least as powerful as
GNN. These models are provably more powerful than MPNNs and can, e.g., count any induced substructure with at most & vertices. But, this power comes at the computational cost of at least Q(n*) operations for n vertices. The necessary tradeoffs between expressive power and computa- tional complexity are still an open question.
The expressive power of a GNN is often measured terms a hierarchy of graph isomorphism tests, i.e., by comparing it to a k-WL test. Yet, there is limited knowledge about how the expressive power of higher-order graph isomorphism tests relates to various functions of interest (Arvind et al., 2020). A different approach is to take the perspective of specific functions that are of practical interest, and quantify a GNN's expressive power via those. Here, we focus on counting induced substructures measure the power of a GNN, as proposed in (Chen et al., 2020). In particular,

---

Under review as a conference paper at ICLR 2021
study whether it is possible to count given substructures with GNN whose complexity is between that of MPNNs and the existing higher-order GNNs.
To this end, study the scheme of many higher-order GNNs (Morris et al., 2019; Chen et al., 2020): select a collection of subgraphs of the input graph, encode these, and (possibly iteratively) compute learned function on this collection. First, propose new such class of GNNs, Re- cursive Neighborhood Pooling Graph Neural Networks (RNP-GNNs). Specifically, RNP-GNNs represent each vertex by representation of its neighborhood of a specific radius. Importantly, this neighborhood representation is computed recursively from its subgraphs. As we show, RNP-GNNS can count any induced substructure with at most & vertices. Moreover, for any set of substructures with at most k vertices, there is a specifiable RNP-GNT that can count them. This flexibility allows to design a GNN that adapted to the power needed for the task of interest, in terms of counting (induced) substructures.
The Local Relational Pooling (LRP) architecture too has been introduced with the goal of counting substructures (Chen et al., 2020). While it can do so, it is polynomial-tine only if the encoded neigh- borhoods are of size o[log(n)). In contrast, RNP-GNNs use almost linear operations, i.c., n' +o(1), if the size of each encoded neighborhood is no(1), This is an exponential theoretical improvement in the tolerable size of neighborhoods, and significant improvement over the complexity of (n*)
in k- k- GNN and I-IGN.
Finally, we take a broader perspective and provide an information thormmttio-tthorrticc lower bound on the complexity of a general class of GNNs that can provably count substructures with at most k vertices. This class includes GNNs that represent given graph by aggregating a number of encoded graphs, where the encoded graphs are related to the given graph with an arbitrary function.
In short, in this paper, we make the following contributions:
We introduce Recursive Neighborhood Pooling Graph Neural Networks (RNP-GNNs), flexible class of higher-order graph neural networks, that provably allow to design graph representation networks with any expressive power of interest, in terms of counting (in- duced) substructures.
We show that RNP-GNNS offer computational gains over existing models that count sub- structures: exponential improvement in terms of the "tolerable" size of the encoded neighborhoods compared to LRP networks, and much less complexity in sparse graphs compared to GNN and K-IGN.
We provide an information-theone theoretic lower bound on the complexity of general class of GNN that can count (induced) substructures with at most k vertices.
2
BACKGROUND
Message Passing Graph Neural Networks. Let G (V) be labeled graph with | = vertices. Here, X, E X denotes the initial label of u E V. where X' C N is a (countable) domain.
typical Message Passing Graph Neural Network (MPNN) first computes representation each vertex, and then aggregates the vertex representations via readout function into representation of the entire graph G. The representation h.55) of each vertex E is computed iteratively by
aggregating the representations hi (1-1) of the neighboring vertices u:
m (GGREGATE()) (EO6-1) : uE ((v))))
h COMBINE (1) (n(111) mm!)
for any V. for A: iterations, and with (1 X,. The AGGREGATE//CMBIINE functions are parametrized, learnable functions, and f. denotes a multi-set, i.c., a set with (possibly) repeating elements. A graph-level representation can be computed as
hG = READOUT (k) :VEV).
where READOUT is a learnalee function. For representational power, it is important that the learn- able functions above are injective, which can be achieved, e.g.. if the AGGREGATE function is a summation and COMBINE is weighted sum concatenated with an MLP (Xu et al. (2019)).
2

---

Under review as a conference paper at ICLR 2021
Higher-Order GNNs. To increase the representational power of GNNs, several higher-order GNNs have been proposed. In a k-GNN, a message passing algorithm is applied to the k-tuples of vertices, in similar fashion as GNNs do on vertices (Morris et al., 2019). At initialization, each k-tuple is laheled with its type, that is, two k -ttupess are labeled differently their induced subgraphs are not isomorphie. As result, k-GNNs can count (induced) substructures with at most & vertices even at initialization. Another class of higher-order networks are k-IGNs, which are constructed with linear invariant/equivarian feed-forward layers, whose inputs consider graphs via adjacency matrices (Maron et al., 2019). k-IGNs are at least as powerful as k-GNNs, and hence they too can count substructures with most vertices. However, both methods need (n²) operations.
Specifically for counting substructures, Chen et al. (2020) propose Local Relational Pooling (I.PP) networks. LRPs apply Relational Pooling (RP) networks (Murphy et al., 2019b;a) on the neighbor- hoods around each vertex. RP networks use permutation-varie functions and convert them to a permutation-invariin function by summing over all permutations. This summation is computation- ally expensive.
OTHER RELATED WORKS
Expressive power. Several other works have studied the expressive power of GNNs (Azizian & Lelarge, 2020). Scarselli et al. (2009) extend universal approximation from feedforward networks to GNNs, using the notion of unfolding equivalence. Chen et al. (2019) establish equivalence between the graph isomorphism problem and the power to approximate permutation invariant func- tions on graphs. Maron et al. (2019) and Keriven & Peyré (2019) propose higher-order, tensor-based GNN models that provably achieve universal approximation of permutation-invarian graphs, and Loukas (2019) studies expressive power under 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.
functions on
Subgraphs and GNNs. The idea of considering local neighborhoods to have better representations than MPNNs is considered in several works (Liu al., 2019; Monti et al., 2018; Liu et al., 2020; Yu et al., 2020; Meng et al., 2018: 8; Cotta et al., 2020; Alsentzer et al., 2020; Huang & Zitnik, 2020). For example, link prediction, one can use local neighborhoods around links and apply GNNs, as suggested in (Zhang& & Chen, 2018). A novel method based combining GNNs and a clustering algorithm is proposed in (Ying et al. (2018)). For graph comparison (i.c., testing whether a given possibly large subgraph exists in the given model), Ying al. (2020) compare the outputs of GNNs for small subgraphs of the two graphs. To improve the expressive power of GNNs, Bouritsas et al. (2020) use features that are counts of specific subgraphs of interest. Another related work is (Vignac et al., 2020), where an MPNN is strengthened by learning local context matrices around vertices.
4 RECURSIVE NEIGHBORHOOD POOLING
Next, we construct Recursive Neighborhood Pooling Graph Neural Networks (RNP-GNNs), GNNs that can count any set of induced substructures of interest, with lower complexity than previous models. We represent each vertex by representation of its radius r--neighborhood, and then com- bine these representations. The key question is how to encode these local neighborhoods in a vector representation. To do so, we introduce a new idea: we view local neighborhoods as small subgraphs, and recursively apply our model to encode these neighborhood subgraphs. When encoding the local subgraphs, we use different radius r2, and, recursively, a sequence of radii (r1, r2,..., E N' to
obtain the final representation 1t (t) of vertices after / recursion steps.
While MPNNs also encode a representation of a local neighborhood of certain radius, the recursive representations differ as they essentially take into account intersections of neighborhoods. As result, as we will see in Section 1. they retain more structural information and are more expressive. Models such as 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-GNN Section 5.1 hold even without that. In Section 6, we will compare the computational complexity of RNP-GNN and these other models.
encode more global information, although our representation results in
3

---

Under review as a conference paper at ICLR 2021
N2(2)
u2
V1
(Ne(e) \ (e)) N2(())
Figure 1: Illustration of a Recursive Neighborhood Pooling GNN (RNP-GNN) with recursion pa- rameters (2,2, 1). To compute the representation of vertex in the given input graph (depicted in the top left of the figure), we first recurse on G(N2(e) \ {u)), depicted in the top right of the figure). To do so, we find the representation of each vertex u G(N2(u) {v}). For in- stance, to compute the representation of u1, we apply an RNP-GNN with recursion parameters (2, 1) and aggregate G(NN((v) \ {u)) n (Ng(uz) {w1])). which shown in the bottom left of the figure. To do so, we recursively apply an RNP-GNN with recursion parameter (1) on G((N((v) ( (wr)) (Wi(1)) \ (un))), the bottom right of the figure.
Formally, an RNP-GNN is parametrized learnable function [(; 0) Gn - RRd, where G, the set of all labeled graphs n vertices. Let G = (V,E, E, X) be a labeled graph with |V] vertices, and (.(0) X,, be the initial representation each vertex w. Lv) denote the neighborhood of radius of vertex v, and let G(t-1) (v) \ {u})) denote the induced subgraph of G on the
set of vertices Nr., (v) \ {v), with augmented vertex label X((-1) (A I[(u, v) E]) for any u E (v) \ {o). This means we add information about whether vertices are direct neighbors
(with distance one) of Given recursion sequence (r1, P2..,,.., or radii, the representations
updated as
m RNP-GNN((-1) ( \o))))
( COMBINE (N( -m)))
(5)
for any v E V, and
hGg READOUT (h()) 1 :
(6)
Different from MPNNs, the recursive update (4) in general applied a subgraph, and not multi-set vertex representations. RNP-GNN( is an RNP-GNN with recursion parameters
(r2...., ..) E N1-1, The final READOUT is an injective, permulation-invariant learnable multi-set function.
If t 1. then
m ( (1.NS- I[(u, v) E E)) : u (v)
a permutation-invarii invariinnt aggregation function as used in MPNNs, only over a potentially larger neighborhood. For 1 and t = 1, RNP-GNN reduces to MPNN.
In Figure we illustrate an RNP-GNN with recursion parameters (2,2, 1) as an example. We also provide pseudocode for RNP-GNNs in Appendix C.
4

---

Under review as a conference paper at ICLR 2021
Figure 2: MPNNs cannot count substructures with three vertices or more (Chen et al., 2020). For example, the graph with black center vertex on the left cannot be counted, since the two graphs on the left result in the same vertex representations as the graph on the right.
5 EXPRESSIVE POWER
In this section, we analyze the expressive power of RNP-GNNS.
5.1 COUNTING (INDUCED) SUBSTRUCTURES
In contrast MPNNs, which, in general, cannot count substructures of three vertices or more, in this section we prove that for any set of substructures, there is an RNP-GNN that provably counts them. We begin with a few definitions.
Definition 1. Let G, H be arbitrary labeled simple graphs, where V the set of vertices 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
C(G: = [IG(() H)
SCV
i.e,, the number of subgraphs of G isomorphic to H. For unlabeled H, the function is defined analogously.
We also need define notion of covering for graphs. Our definition uses distances graphs
Definition 2. Let H = (VH, Eh) be a (possibly labeled) simple connected graph. For any C Vμ and u H, define
des S): = max d(u,v).
WES
where d(.,.) is the shortest-path distance H.
Definition 3. Let H be (possibly labeled) simple connected graph on t + 1 vertices. A permuta- tion of vertices, such as (V1, 02 02,..., (2441.) called a vertex covering sequence, with respect to sequence (r1,,2,...,,7 TT) E N' called a covering sequence, if and only if
S,) S Ts:
(10)
for any E [t+ = f1,2, 1), where S; = (Vi, 11+1.... U4+1} and H: = H(,)) is the subgraph of H induced by the of vertices St. We also say that H admits the covering sequence r r= (r., E No if there is vertex covering sequence for with respect to r.
In particular, in covering sequence we first consider the whole graph as a local neighborhood of one of its vertices with radius ri. Then, we remove that vertex and compute the covering sequence of the remaining graph. Figure 3 shows an example of covering sequence computation. An important property, which holds by definition, is that if r is covering sequence for H, then any r' > (ín posnt-wise sense) is also a covering sequence for H.
Note that any connected graph on À vertices admits at least one covering sequence, which is (k To observe this fact, note that in a connected graph, there is at least one vertex that may take this vertex
1, 2, 2,..., 1). can be removed and the remaining graph still remains connected. Therefore, as the first element of vertex covering sequence, and inductively find the other elements. Since the diameter of connected graph with & vertices is always bounded by k 1, achieve the desired
5

---

Under review as a conference paper at ICLR 2021
81 1/2
1/
81
1/2
13 871
V/2 83
04 175
05
16
Figure 3: Example of covering sequence computed for the graph on the left. For this graph, (V6, 11, B1, Us, v2) is vertex covering sequence with respect to the covering sequence (3,3, 3, 1). The first two computations to obtain this covering sequence are depicted in the middle and on the right.
result. However, we will see in the next section that, when using covering sequences to identify sufficiently powerful RNP-GNNs, is desirable to have covering sequences with low ri, since the complexity of the resulting RNP-GNN depends on 71. We provide an algorithm in Appendix D to find such covering sequences in polynomial time
More generally. if H1 and H2 are (possibly labeled) simple graphs on & vertices and H1 E H2, i.e., H1 a subgraph H2 (not necessarily induced-sun subgrraph, then, follows from the definition that any covering sequence for H1 is also covering sequence for H2. As a side remark, as illustrated in Figure 4, covering sequences need not always to be decreasing.
Using covering sequences, we can show the following result.
Theorem Consider a set of (labeled or unlabeled) graphs H on + verfices, such that any Then, there is RNP-GNN with recursion
H E H admits the covering sequence (r1, .2.)...,Tt) "2..,....,,"" H. In other words, if there exists H E H such that C(G;; H) + C(G2 Hf), then f[G + f(G2;0). The same result also holds for the non-induced subgraph count function.
parameters (2..T....... that can count any TT).
Theorem states that, with appropriate recursion parameters, any set of (labeled unlabeled) sub- structures can be counted by an RNP-GNN. Interestingly, induced and non-induced subgraphs can be both counted in RNP-GNNs!.
The theorem holds for any covering sequence that is valid for all graphs H. For any graph, one compute covering sequence by computing spanning tree, and sequentially pruning the leaves of the tree. The resulting sequence nodes is a vertex covering sequence, and the corresponding covering sequence can be obtained from the tree (Appendix D). valid covering sequence for all the graphs in H. is the coordinate-wise maximum of all these sequences.
For large substructures, the sequence (r1, r2,,...... ... TT)) can be long or include large numbers, and this will affect the computational complexity of RNP-GNNs. For small, e.g., constant-size substructures, the recursion parameters are also small (i.e., r; O(1) for all i), raising the hope count these structures efficiently. In particular, is an important parameter. In Section 6, we analyze the complexity of RNP-GNNs in more detail.
5.2 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 learn any function related to local neighborhoods small subgraphs in a graph.
First, we recall that for a graph G, G(S) denotes the subgraph of induced by the set vertices S. Definition 4. A function&& é G Rd is called an r-local graph function if
((G < (G))) S V. < <r)),
(11)
where v G, d is a function graphs and is multi-set function.
For simplicity, assume that 7 only contains vertex graphs. If H includes graphs with strictly less than + vertices, we simply add sufficient number of zeros to the RHS of their covering sequences.

---

Under review as a conference paper at ICLR 2021
In other words, local function only depends on small substructures.
Theorem 2. For any r-local graph function E(.), there exists RNP-GNN f(:00 with recursion parameters (r 1, r. - 2..... such that f(; E(G) for any E Gp.
As a result, we can provably learn all the local information in a graph with an appropriate RNP- GNN. Note that we still need recursions, because the function (.)) may be an arbitrarily difficult graph function. However, to 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 feedforward network layers are used for aggregation (see the proof of the theorem 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 the model in general is not polynomial in n.
COMPUTATIONAL COMPLEXITY
The computational complexity of RNP-GNNs is graph-dependent. For instance, we need compute the set of local neighborhoods, which is cheaper for sparse graphs. A complexity measure existing the literature the tensor order. For higher-order networks, e.g., I-IGSs, we need to consider
tensors in g=* The space complexity is then O(n²) and the time complexity can be even more, dependent on the algorithm used to process tensors. In general, for message passing algorithm on graphs the complexity of the model depends linearly on the number of vertices (if the graph is sparse). Therefore, to bound the complexity of method, we need to bound the number of node representation updates, which we do in the following theorem.
Lef f(::0)= Gn - IRd be an RNP-GNN with the recursion paramelers (r1, r2,-... r2). Assume that the observed graphs G1, G2...,, whose representations we compute, satisfy the follow- ing property:
Theorem 3.
max WN, (v), nE(n)
(12)
where e is a graph independent constant. Then, the number of node updates in the RNP-GNN is Onne))
In other words, if (1) and O(1), then RNP-GNN requires relatively few updates (that is, n (+(())), compared to the higher-order networks (O(n++1)). Also, in this case, finding neighbor- hoods is not difficult, since neighborhoods are small (n²(1)). Note that if the maximum degree of the given graphs is A, then c A+) Therefore, similarly, A (1) then we can count with at most n ++0(( updates.
The above results show that when using RNP-GNNs with sparse graphs, we can learn functions of substructures with & vertices without requiring -odde tensors. LRPs also encode neighhorhoods of distance F1 around nodes. In particular, all c! permutations of the nodes in a neighborhood of size e are considered obtain the representation. As result, LRP networks only have polynomial complexity if c ollog(n)). Thus, RNP-GNNS GNNs can provide an exponential improvement in terms of the tolerable size of neighborhoods with distance 71 in the graph.
Moreover, theorem 3 suggests to aim for small r1. The other ry may be larger than r1, as shown in Figure 4, but do not affect the upper bound on the complexity.
7 AN INFORMATION-THORREE
LOWER BOUND
In this section, we provide general information-theorre lower bound for graph representations that encode a given graph G by first encoding a number of (possibly small) graphs G1. G2. G and then aggregating the resulting representations. The sequence of graphs G1. Gz...., G5 may be obtained in an arbitrary way from G. For example, in an MPNN, G; can be the computation tree (rooted tree) node i. As another example, in LRP, G; is the local neighhorhood around node i.

---

Under review as a conference paper at ICLR 2021
81
2i
Figure 4: For the above graph, (V), U2...., U6) is a vertex covering sequence. The corresponding covering sequence (1, 4, 3, 1) is not decreasing.
Formally, consider a graph representation f(::0) : Gn - R2 as
S(G; 0) = ((HV(G.) : i [ -1
(13)
for any G E Gn. where + is a multi-set function, (G1, G2, Gi) = E()) where E(.) : G, (Ummi Gm) is function from one graph to & graphs, and U Gm + [s] is function on graphs taking s values. In short, we encode graphs, and each encoding takes one of values. We call this graph representation function (s, tsgoo graph representation.
Theorem 4. Consider a parametrized class of (s. good representations f(:;0) : G, Rd that is able to count any (not necessarily induced-) substructure with l vertices. More precisely, for any graph with l vertices, there exists f(;; 8) such that if C(G1; H) * C(G2; then f(G1;0) + f(G2;0). Then', (
In particular, for any (s, ()ood graph representation with = 2, i.e., binary encoding functions, we need (2(=*) encoded graphs. This implies that, for s = 2, enumerating all subgraphs and deciding for each whether equals H near optimal. Moreover, if S k, then t 22(n) small graphs would not suffice to enable counting.
More interestingly, if k, s O()), then impossible to perform the substructure counting task with /. = Ollog(n)). As a result, in this case, considering n encoded graphs (as is done in GNNs or LRP networks) cannot exponentially improved.
The lower bound in this section is information-theoreti and hence applies to any algorithm. It may be possible strengthen by considering computational complexity, too. For binary encodings, i.e., 2, however, know that the bound cannot be improved since manual counting of subgraphs matches the lower bound.
8 TIME COMPLEXITY LOWER BOUNDS FOR COUNTING SUBGRAPHS
In this section, we put 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 sub-exponential time. ETH, as stronger version of the P F NP problem, is widely believed to hold. Assuming that ETH holds, the c-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 ETH conjecture holds, any graph representation that can count any sub- structure H on i vertices with appropriate parametrization needs (80) time to compute.
The above bound matches the O complexity of the higher-order GNNs. Comparing with The- orem 4 above, Corollary more general, while Theorem 4 has fewer assumptions and offers refined result for aggregation based graph representations.
Thh theorem also holds for induced-subbraahs, with/without vertex labels. (m) is (2)) up to poly-logarithmic factors.
8

---

Under review as a conference paper at ICLR 2021
Given that Corollary is worst-case bound, natural question is whether do better for subclasses graphs. Regarding H, even if is a random Rénis graph, can only be counted in n00k/ log R) time (Dalirrooyfard et al., 2019).
Regarding the input graph in which we count, consider two classes of sparse graphs: strongly sparse graphs have maximum degree = O(1), and weakly sparse graphs have average degree = O(). 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 linear, but still polynomial, and can be much better than Onn)). One may ask whether it is possible to achieve a learnable graph representation such that its complexity for weakly sparse graphs still linear. Recent results complexity theory imply that this is impossible:
is generally not
Corollary (Gishboliner et al. (2020); Bera et al. (2019)). There is no graph representation algo- rithun that runs in linear time on weakly sparse graphs and is able to count any substructure H on --vertices (with appropriate parametrization.
Hence, RNP-GNNs are close to optimal for several cases of counting substructures with parametrized learnable functions.
CONCLUSION
In this paper, we studied the theoretical possibility of counting substructures (induced-subgraph) by a graph representation network. We proposed an architecture, called RNP-GNN, and we proved that for reasonably sparse graphs can efficiently count substructures. Characterizing the expressive power GNNs via the set functions they can learn on substructures may be useful for developing new architectures. In the end, proved general lower bound for any graph representation which counts subgraphs and works by aggregating representations of a collection of graphs derived from the graph.
REFERENCES
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. 1..2200066.660 /5646, 2020.
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 arXiv:1911.05880 2019.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.00255. 2020.
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-23) 2005.
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 20X0:22002.04025, 2020.

---

Under review as a conference paper at ICLR 2021
Leonardo Cotta, Carlos H. C. Teixeira, Ananthram Swami, and Bruno Ribeiro. Unsupervised joint k-node graph representations with compositional energy-based based models. arXiv preprint 9.XY::2010.04259, 2020.
Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams. Graph pattern detec- tion: Hardness for all induced patterns and faster non-induced eycles. In Proceedings of the 5 Anmual 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. Advances neural information processing systems, pp. 3144-384455 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Espuru-Guzik and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances neural information processing systems, pp. 2224-2232, 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 Molecular Systems Design & Engineering. 4(4):828- 849, 2019.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In Int. Conference on Machine Learning (ICML), pp. 5204-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.
learning-Volume
Lior Gishboliner, Yevgeny Levanzov, and Asaf Shapira. Counting subgraphs in degenerate graphs. arXiv preprint urXiv:2010.05998, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs.
In Advances in neural information processing systems, pp. 1024-1034, 2017.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, (2):251-257, 1991.
Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks universal approximators. Neural networks, 2(5))399 3666, 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-377 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 al. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1::611-668, 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.
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. 8466-8478. 2019.
10

---

Under review as a conference paper at ICLR 2021
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.
Andreas Loukas. What graph neural networks cannot learn: depth width. In International Con- ference on Learning Representations, 2019.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference Machine Learning, pp- 4363 4371, 2019.
Brendan D McKay. Small graphs are 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. In 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.
R 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- fions, 2019a.
R Murphy, B Srinivasan, V Rao, and B Riberio. Relational pooling for graph representations. In International Conference on Machine Learning (ICML 2019), 2019b.
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.
Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. Computational capphttiiiiiiaaaaiiaaaiaici of graph neural networks. IEEE Transactions Neural Networks, 20(1) 20(1):81-102, 2009.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20 20(1):61-80, 2008
Mengying Sun, Sendong Zhao, Coryandar Gilvary, Olivier Elemento, Jiayu Zhou, and Fei Wang. Graph convolutional networks for computational drug development and discovery. Briefings in bioinformatics, 21(3):919 9355, 2020.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with message-passingg arXiv preprint arXiv:2006. 1077 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful 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.03092 2020.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- crarchical graph representation learning with differentiable pooling. In Advances in neural infor- mation processing systems, pp. 4800 4810. 10, 2018.
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.0144 045000 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp. 3391- 3401, 2017.
11

---

Under review as a conference paper at ICLR 2021
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
A PROOFS
A.1 PROOF OF THEOREM 1
A.1.1 PRELIMINARIES
Let first state few definitions about the graph functions. Note that for any graph function f: Gn + Rd, we have ( for any G = H.
Definition 5. Given two graph functions f.g- Cn + R2,, write f 2 g. if and only if for any
G1. E Gn.
VG1, E Gn g(G)) # s((2)) = f(G1)+ f(G2).
(14)
or, equivalently,
AGI, G2 E G. :(G)) I(G2) = - g(G2).
(15)
Proposition Consider graph fanctiions f.g, h Gn + Rdd such that f 9 and g h. Then, f h. In other words, 2 is transitive.
Proof. The proposition holds by definition.
Proposition 2. Consider functions f.g : Gn RR such that f 2 g. Then, there is function : R + IR such that =
Proof. Let G, LieNF; F; the partitioning induced by the equality relation with respect to the function f on G,, Similarly define G. N for g. Note that due to the definition, {F; 1 N} is refinement for (9, i E NJ. Define & to be the unique mapping from {Fi :1: N] to {9, i e N} which respects the equality relation. One observe that such & satisfies the requirement in the proposition.
Definition 6. An RNP-GNN is called maximally expressive, if and only if
all the aggregate functions are injective as mappings from multi-set on countable ground set to their codomain.
all the combine functions are injective mappings.
Proposition 3. Consider two RNP-GNNs f.g with the same recursion parameters r (r1, (2,,2,...,,7' where f is maximally expressive. Then, f [gg. g.
Proof. The proposition holds by definition.
Proposition 4. Consider sequence of graph functions f. J.91...., If 2 for all i E [k], then
f2
ci
(16)
for any E N.
Proof. Since f Gi. we have
VG1,G E G, f(G1) f(G2) g((G)) (G2),
(17)
for all i E [k]. This means that for any G1, G2 E G, if f(G)) = f(G2) then (G)))) = (: i E [R:], 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 long the summation is bounded.
12

---

Under review as a conference paper at ICLR 2021
Definition 7. Let H (VH, En, X") be a labeled connected simple graph k vertices. For any labeled graph = (Va. Eg, x E Gn the induced subgraph count function C(G; H) is defined as
C(G: = E 1(G(S) = H).
(18)
SCIM
Also, let CG; H) denote the number of non-induced subgraphs of G which are isomorphic to H. It can be defined with the homomorphisms from H to G. Formally, if >> &s define
H) Σ C(G(S);
(19)
[n]
|
Otherwise, k, and we define
C(G ==
E
CH x x = H}.
(20)
HEA((H)
where
#(H): : (i E Cp i 3 H3,
(21)
defined with respect to the graph isomorphism, and Că H E .N denotes the number of subgraphs in H identical to H. Note that HH) is a finite and 3 denotes being (not necessarily induced) subgraph.
Proposition Let H be a family of graphs. for any H E H. there is an RNP-GNN f.( with recursion parameters (2..7).... such that fu 2 C(G; H). then there exists RNP-GNN ():0) with recursion parameters
T1) such that I a ΣhEn C(G; H).
Proof. Let [(:; 0) be maximally expressive RNP-GNN. Note that by the definition f J JH for any H H. Since is transitive, f C(G:)) H) for all H e H. and using Proposition 4, we conclude that f 2 Ehen C(G; H).
The following proposition shows that there no difference between counting induced labeled graphs and counting induced unlabeled graphs in RNP-GNNs.
Proposition 6. Let Ho be unlabeled connected graph. Assume that for any labeled graph H, which is constructed by adding arbitrury labels to Ho, there exists an RNP-GNN JH (1; 00)) such that fH 2 C(; H). then for its unlabeled counterpart Ho, there exists RNP-GNN f(:00 with the same recursion parameters as fH (.; 0H) such that f C(G; Ho).
Proof. If there exists an RNP-GNN f- 9x) such that fH 2 C(G; H), then for a maximally ex- pressive RNP-GNN f(: 0) with the same recursion parameters as fHr we also have fu 2 C(G; H). Let H be the set of all labeled graphs H (V,E, X) E G2 up to graph isomorphism, where X E A for countable set X. Note that H = H1, H2,...) -} is countable set. Now we write
C(G; = Σ 1{G(()) Ho}
(22)
ScIm
18
Σ Σ((G(S) = H.}
(23)
SCIn
iEN
18|=k
Σ Σ (GG(S) = H.)
(24)
EEN
18
Σ
C(G
(25)
(26)
Now using Proposition& 4 we conclude that f 3 C(G Ho) since C(G; Ho) is always finite.
n
13

---

Under review as a conference paper at ICLR 2021
Definition 8. Let H. be (possibly labeled) simple connected graph. For any 8 VH and E VH, define
dH( == max d(u,, 2). wES
(27)
Definition 9. Let H be a (possibly labeled) connected simple graph on k = +++ vertices. A permutation of vertices, such as (U1, .2..... "2....,V(+1) ). is called a vertex covering sequence, with respect sequence (T1, ,,,,,,..,, TT) E N', called covering sequence, and only if
di (v:: S r..
(28)
for i E [t [ 11, where H; (S,) and S; = {us, vi+1...... r411. Let Cи (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).
(29)
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 (labeled or unlabeled) graph H, there exists an RNP-GNN with appropriate recursion parameters [H 0H) such that fH 2 C(G; H)), then we prove there exists an RNP-GNN (.; 0) with the same recursion parameters fH such that f 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 C(G; Note that
H(G,H) E
H(G(S):
(30)
scIm
1si-k
Σ
Σ
Cn. x 1(G(S) = i
(31)
SEIn НEH()) si
= Σ
CH. H
(G((S = M
(32)
HEA(H)
SChJl 18
= Σ
CHHH X C(G,
(33)
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 (r1, (2.,,,,..., 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 labeled 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 labels defined as
x = (Xu, ((u, v) E)),
(34)
for each V. (v). We may also use x for more clarification.
14

---

Under review as a conference paper at ICLR 2021
A.1.2 PROOF OF THEOREM 1
We utilize an inductive prove on which is the length of the covering sequence of H. Equivalenty, due to the definition, & = k - 1, where k: is the number of vertices in H. First, we note that due to Proposition 8, without loss of generality, we can assume that H is simple connected labeled graph and the goal is to achieve the induced-subgrapl count function via an RNP-GNN with appro- priate recursion parameters. We also consider only maximally expressive networks here to prove the desired result.
Induction base. For the induction base, i.e., t 1, H is a two-vertex graph. This means that we only need to count the number of specific (labeled) edge in the given graph G. Note that in this case we apply an RNP-GNN with recursion parameter 71 2 1. Denote the two labels of the vertices in H by X X E X. The output of an RNP-GNN f(;;0) is
[n]B), where f(; 0) we assume that (.; 0) is maximally expressive. The goal is to show that f C(G; H).
f(G;0) = (X (XXX"" u E (r,
(35)
Using the transitivity of J. we only need to choose appropriate o; v, yp to achieve f C(G; H) as the final representation. Let
of [n]B) == 2+2x (X x Σ 24
(36)
(2, :=
x=x=)===>x>XX>0- 1 + 1 X
(37)
p( : ue [n]])== = Σ
(5 = (x 1)}, Σ 1(zu = (Xf
(38)
Then, a simple computation shows that
( (f (eN, H).
(39)
(40)
Since f(=:0) is an RNP-GNN with recursion parameter rı and for any maximally expressive RNP-
GNN f(:: with the same recursion parameter as ff we have f 2 f and f C(G: H), we conclude
that 2 C(G; H) and this completes the proof.
Induction step. Assume that the desired result holds for 1 (t 2 2). We show that also holds for l. Let us first define
H. == {HC 3e....., Ve E [k] : (vi, U2 .2...., E CH(r)) c (H') (H E H*} ( [M] H = HH)
(41)
(42)
Note that H' # by the assumption. Let
|| = Σ (HH)).
(43)
H-
For all H" H", using the induction hypothesis, there is (universal) RNP-GNN f(: with recursion parameters (r2, Ta......... 12) such that f 3 C(G; H*). Using Proposition 4 we conclude
8= Σ
C(G; H.).
(44)
HEE
Define maximally expressive RNP-GNN with the recursion parameters (r1,
(r1, r2, .......,r.) r1) as follows:
f(G; 0) (( (NG, (x)): : u e [n]]]-
(45)
Similar to the proof for / = 1, here we only need to propose a (not necessarily maximally expressive) RNP-GNN which achieves the function C(G; H).
Let us define
fH:(G:0) == o(Hvn; (X &
e (n))),
(46)
15

---

Under review as a conference paper at ICLR 2021
where
Σ 2
(47)
1|7 i=1
(H²(X,2) = 11 )
(48)
(49)
and go C(G; Note that the existence of such function & is guaranteed due Proposition
2. Now we write
|70 x C(G; H) = Σ (G((S)
|711|
H}
(50)
SCIn
Σ
Σ
1
[k] (G(S) (u))), = HE EH A AX. x
(51)
(g(R)
Σ
Σ
1B [|] (G(S) (v))) E H" A A = _ (52)
"CIn] (ESC(n)
Σ
E
1 [M] (G(S) (v))) it H" AX = =
eE vESCN, (v)
(53)
E
E
H[G((S) (r) = x (54)
"E[n] ve (0) WTEER
= Σ Σ
(W); x x = x
(55)
M H,E
which means that
Σ
(56)
HE[R)-H;EEE EN
However, for a maximally expressive RNP-GNN f(;; 0) we know that f fH; for all H E H. and this means that 2 C(G; H). The proof is thus complete.
A.2 PROOF OF THBOREM 2
For any labeled graph H vertices (not necessarily connected) claim that RNP-GNNG can count them.
Claim 2. Let (=:0) : Gn + Rd be a maximally expressive RNP-GNN with recursion parameters (r ( 1,r - 2,...,1) 1). Then, f H(G
Now consider the function
(G) o ((E((G(S) S V1 <r.).
(57)
We claim that f 3 E (f is defined the previous claim) and this completes the proof according to Proposition 2.
To prove the claim, assume that f(Gi) = f(G2). Then, we conclude that C(G H) = C(G2; H) for any labeled H (not necessarily connected) with vertices. Now, have
((G) ol ((()) : S C V, (
(58)
= (() H E Gr, the multiplicity of H is C(G;
(59)
which shows that E(Gr) = ((G2).
Proof of Claim 2. To prove the claim, Ch of graph H. If H connected, i.c., Cy = 1. then according to Theorem 1, we know that fJ
induction the number of connected components
16

---

have Under review as a conference paper at ICLR 2021
Now assume that the claim holds for cи c H1, H2...., He denote the connected components of H. Also assume that H2 * H for all i # j. We will relax this assumption later. Let us define
1. We show that it also holds for cH Let
Aa = {(S), St..,,,,, Vi Vi [c] S; S [m]] G(S,) n.).
(60)
Note that we can write
AAl = II C(G; H,)
(61)
i=1
=(G: + ECC(GHH))
(62)
where Hi; Hy..... are non-isomorphic graphs obtained by adding edges (at least one edge) be- tween graphs H1, H2...., or contracting a number of vertices of them. The constants dj are just used to remove the effect of multiple counting due to the symmetry. Now, since for any H3. H the number of connected components is strictly less that c, using the induction, f C(G; H.) and 2 C(G; H)) for all and all E [c). According to Proposition 4, conclude that f C(G; H) and this completes the proof. Also, if 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 symmetry. The proof is thus complete.
A.3 PROOF OF THBOREM 3
To prove Theorem 3, we need to bound the number of node updates required for an RNP-GNN with recursion parameters (r1, T2,.... rz).
First of all, we have n variables used for the final represen- tations of vertices. For each vertex 01 E V, we explore the local neighborhood Nr, (v1) and apply a new RNP-GNN network to that neighborhood. In other words, for the second step we need to update [N, (v1)l nodes. Similarly, for the ith step of the algorithm we have most
A = max "1 (L
max SHLLEN ENrging)
(12) n [W (01) (v) (wr, n AN;(
(63)
u Therefore, we can bound the number of node updates as
Y X
(64)
i=1
Since A is decreasing in i, we simply conclude the desired result.
A.4 PROOF OF THBOREM 4
Let K₂ denote the complete graph on k vertices.
Claim 3. For any k, N, such that n is sufficiently large,
[[C(G:KA) G G. (cn/k (on/klo((n/k))> k))* = Ō(nn²)
(65)
k!
where c is a constant which does not depend on k, n.
In particular, we claim that the number of different values that C(G; Kx) can take n² up to poly-logarithmic factors.
To prove the theorem, we use the above claim. Consider a class of (s, ()oodd graph representations f(; 8) which can count any substructure on l vertices. As result, f C(G; KG) for appropriate
parametrization 6. By the definition, f.) must take at least (C(G: G e G.) different values, i.e.,
[[f(G:0):CG :GE G G.) [[((G:K): Gm)
(66)
17

---

Under review as a conference paper at ICLR 2021
Also,
(s(G;0) G &
([v(G.) : :i : G.
(67)
where (Gi, G2
G.) = E(G). But, & can take only 8 values. Therefore, we have
(C(G; KR) : G e G.G))
x [IGG:)):GGG.]
(68)
_ : G G.)
(69)
1 (faa Wi [t] a or e [s]}
(70)
$ (t+
(71)
As result, (t + -(2-1 or ... To complete the proof, we only need to prove the claim.
Proof of Claim 3. Let P1.P2.....1 Pm be distinct prime numbers less than n/k. Using the prime number theorem, we know that lim n/k login/E] 1. particular, we can choose n large enough to ensure en/k log(n/k) < m for any constant < 1.
For any {b), ....... , by} S [m]. define GB as a graph on n vertices such that VGe Vo (Uleje) Vi), and [V: = Ph. Also,
vu, GB + 3i,j E [m]. + W
(72)
The graph Ga is well-defined since Σ Ph. S k x n/k k = n. Note that C(GB; K&) Also, since Pt. E [m], are prime numbers, there is unique bijection
11 Ph.
B f C(GB; K2).
(73)
Therefore,
(C(G: :G) G.)
(C(GB; K&) : [m], |8| 1:]
(74)
m
(75)
(m k***
(76)
k!
(cn/ k log(n/k) k)*
(77)
k!
B RELATIONSHIP TO THE RECONSTRUCTION CONJECTURE
Theorem provides a universality result for RNP-GNNs. Here, we note that the proposed method is closely related to the reconstruction conjecture, an old open problem in graph theory. This motivates us to explain their relationshipddifeernnesss First, we need a definition for unlabeled graphs.
Definition 10. Let F, S Gn be set of graphs and let G. G(V \ (v)) for any finite simple graph G = E), and any E V. Then, we say the set F is reconstructible if and only if there is bijection
(G, : VVEVVVVV +
(78)
for any G Fr. In other words, Fn is reconstructible, if and only if the multi-set & 1 VB fully identifies G for any G E Fn.
known that the class of disconnected graphs, trees, regular graphs, are reconstructible (Kelly et al., 1957; McKay, 1997). The general case is still open; however it is widely believed that it is true.
Conjecture (Kelly et al. (1957)). Gr is reconstructible.
18

---

Under review as a conference paper at ICLR 2021
For RNP-GNNN the reconstruction from the subgraphs G [n]] is possible, since relabel any subgraph (in the definition of X*) and this preserves the critical information for the recursion to the original graph. In the reconstruction conjecture, this part of information is missing, and this makes the problem difficult. Nonetheless, since in RNP-GNNs we preserve the original node's information in the subgraphs with relaheling, the reconstruction conjecture is not required hold to show the universality results for RNP- although that conjecture is motivation for this paper. Moreover, it can be shown that the reconstruction conjecture it true, it may be also possible find simple encoding of subgraphs to an original graph and this may lead to more powerful but less complex new GNNs.
C THE RNP-GNN ALGORITHM
In this section, we provide pseudocode for RNP-GNNs. The algorithm below computes node rep- resentations. For graph representation, can aggregate them with common readout, e.g., lig <- MLP Evey A Following (Xu et al., 2019), we use sum pooling here, to ensure that we can represent injective aggregation functions.
Algorithm Recursive Neighborhood Pooling-GNN (RNP-GNN)
Input: G = (V, &, { where V [ni]. recursion parameters T2, ; it E N, e E R, E [t], node features frelve..
Output: h2 for all v E
1 <- F. for all v E
if t = then
by MLPP)((1) (1+ (1++
Σ
(he ((,)
WEN, (b){(b)
for all E else
for
all v E do G¹ G(N,, (e) \ {u}) with node features {hi) Weuubuerrs (o) RERRRN--NNNNN R-R--GNNNGG,, (r2, T3..... rr...., (c(2) (ele)....ee.))
ho + MLP(1) ((1 e(0) + +EENN, (W)E()) Buv).
end for end return (hylvev
With this algorithm, are allowed (Xu et al., 2019; Hornik et al., 1989; Hornik, 1991). That said, in practice, smaller MLPs may be acceptable (Xu et al., 2019).
achieve the expressive power of RNP-GNNs if high dimensional MLPs
D COMPUTING A COVERING SEQUENCE
As we explained in context of Theorem 1, we need covering sequence (or an upper bound to that) to design an RNP-GNN network that can count given substructure. A covering sequence can be constructed from a spanning tree of the graph.
For reducing complexity, it is desirable to have covering sequence with minimum r1 (Theorem 3). Here, we suggest an algorithm for obtaining such covering sequence, shown Algorithm 2. For obtaining merely aribtrary covering sequence, one compute any minimum spanning tree (MST), and then proceed as with the MST in Algorithm
Given MST, build vertex covering sequence by iteratively removing leave 2; from the tree and adding the respective node v; to the sequence. This ensures that, at any point, the remaining graph is connected, At position i corresponding v, the covering sequence contains the maximum
19

---

Under review as a conference paper at ICLR 2021
distance r, of 22 to any node in the remaining graph, upper bound that. For efficiency, upper bound on the distance can be computed in the tree.
To minimize т1 maXuev d(u, 21), need to ensure that node in arg min m d(u d(u, v) leaf the spanning tree. Hence, we first compute y d(u, v) for all nodes v, c.g., by running Paaairs-Shortst-PPaaie Paths (APSP) (Kleinberg & Tardos, 2006), and sort them in increasing order by this distance. Going down this list, we try whether it is possible to use the respective node as 01, and stop when we find one.
Say v² the current node in the list. To compute a spanning tree where s² is a leaf, we assign a large weight all the edges adjacent 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 v" as in the vertex covering sequence. This algorithm runs in polynomial time.
Algorithm Computing a covering sequence with minimum T1
Input: H = (V,E, X) where V = -t++1
Output: A minimal covering sequence (r..,2...,,1)) rt), and its corresponding vertex covering se- quence (v1, "2,...,,tt+111
For any u, U E V, compute d(u,, e) using APSP
(u1, U2,.... (M+1))== +- all the vertices sorted increasingly in s(v) max d(u, v)
for t do
Set edge weights w(u, v)
1fu u, V uz) for all (u, v) 3
Hr + the MST of with weights w
if u, is a leaf in H7 then
11 + Ui
ri s(s))
break end if
end for
for i to + do
0; <- one of the leaves of HT
r; f- max d(u, v;)
Hr + Hy after removing 0/
end for return (r1, (2,,,.,..... r1) and (vi, 02,+,,
20


Reviews:
[{"review_id": "tA_SA1-2IBv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe goal of the paper is to show that GNN's (without exponential computational complexity) can be constructed with the ability to count subgraphs. To this effect, the authors propose a principled neighborhood pooling strategy and theoretically characterize their expressive power - with respect to other models proposed earlier. More specifically, the authors propose a recursive neighborhood pooling strategy which characterizes graphs based on the counts of subgraphs . Furthermore, they show that if the tuple of recursion parameters are chosen well, their proposed model can capture all induced subgraphs (universality) of sizes smaller than the first value in the tuple of recursion parameters plus 1 - and show a relationship to the reconstruction conjecture (Kelly et al. 1957). The authors also provide a bound on the number of iterations required to learn the expressive representations.\n\nPros:\n1. Theoretical contributions which provide a strategy to learn expressive representations with the ability to count subgraphs and distinguish graphs based on the same.\n2. Proposed model provides a strategy to perform a tradeoff on the exponential nature required to compute sugraphs in earlier works.\n3. Comprehensive literature review\n\nConcerns:\n1. The theorems all state that, there exists a set of recursion parameters, etc - but do not provide a computationally tractable strategy to determine the same for real world graphs (e.g. diameters of the graph > 15) - or a strategy to determine the vertex covering sequence if it exists - which is the basis for theorem 1(among all permutations of the set $\\mathcal{S}$ - without looking over all permutations - this can explode even with subgraphs of size 10 for instance).\n2. Lack of any experimental evidence to empirically show gains - While the authors explicitly say that their work is theoretical, they could have included synthetic experiments to demonstrate the same- given that the Local Relational Pooling,  k-WL works and k-IGN (the latter two, which are exponential) works have experimental results. \n\nIf the concerns are addressed, I will be happy to update my scores.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AYM7ftta3C", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The proposed paper seeks a theoretical possibility of counting the subgraph by a graph neural network. To this end, the authors proposed a recursive neighborhood pooling graph neural network and proved the express power of the model. The universal approximation results on a subgraph have been shown as well. Analysis of computational complexity shows the algorithm is much efficient than the known class of models that can count substructures.\n\nThe strength of this paper is the detailed theoretical analysis of the proposed method. The analysis has been taken from multiple perspectives: model complexity, computational complexity, and theoretic lower-bound on the class of the proposed method. The paper gives a new insight into measuring the representation power of graph neural networks through subgraph counting.\n\nAlthough subgraph counting is an interesting problem from a theoretical viewpoint, the weakness of this paper is that it is not answered how relevant it is to real-world tasks and how successful it is. Since this is the first paper proposing a new way of measuring the express power of the graph neural network, it would have been much better if there's some discussion on this point.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "3TRBinUpOml", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Update following author response and reviewer discussion:**\n\nI would like to thank the authors for providing a response, and in particular for providing further justification for their injectivity assumption. However, the main concern remains the lack of empirical validation, even on toy examples, showing that (or whether) the derived theory here goes beyond a hypothetical thought exercise and can be implemented in practice. It shouldn't be difficult to provide such examples, assuming the proposed approach does indeed work as indicated by the theory developed here, and without such examples, the paper seems rather incomplete. Therefore, unfortunately, my score remains unchanged at this point, although I would like to encourage the authors to keep pursuing this direction.\n\n---\n\n**Initial review:**\n\nThis manuscript discusses a hypothetical pooling approach that recursively applies a generic (unspecified) GNN to subgraph constructed from local neighborhoods of a certain radius (or sequence of them, applied in successive applications of the recursion) in an input graph. The main motivation set out by this work is to prove that, under some assumptions (which may or may not be realistic) on the applied GNNs, this pooling strategy is sufficiently expressive to admit a configuration of weights that would enable counting subgraphs of certain size in the main input graph. The authors provide theoretical study of this expressivity and prove the capability to count subgraphs in an existence sense. That is, they show there exists some function that can be written in the form of their proposed pooling architecture (with sufficiently rich architecture between pooled levels) such that non isomorphic subgraphs would necessarily be distinguishable by some of the extracted features, and thus counting equivalency classes of these features would provide the desired subgraph counting. The authors also provide other results showing functions written in the form of their pooling based architecture have reasonable complexity of node operations, and providing some lower bound on the capability of any GNN approach to count subgraphs, thus putting their theoretical results in context.\n\nThe proposed pooling approach itself is rather straight forward, but intuitively makes sense. Given an input sequence of radii, at each iteration of the recursion each node in the graph constructs a subgraph over nodes that are within the current considered radius in the sequence. Then, by recursion, the same approach is applied to each of these subgraphs, with the remainder of the radii sequence (subsequent to the current one) being passed on, until reaching only a single radius or a single node as stopping conditions. Given the resulting (sub)graph features for each node, these are combined with the input node features via generic functions parametrized by unspecified neural networks (written as an MLP with arbitrary architecture for the sake of presenting pseudocode in the supplement) that are supposed to be injective, when carefully examining the derivation and proofs in the supplement. Finally, the resulting node features are aggregated together (again, via generic functions modeled as unspecified neural networks that are supposed to be injective, this time up to node permutation) into graph features that provide a readout to be returned as the output of the network to outer levels of the recursion, or finally to the general output of the network.\n\nIt seems to me that the main theoretical results here crucially hinge on the injectivity assumption, and yet the authors make no attempt to verify that any existing GNN indeed provides an architecture that satisfies their assumed conditions. More importantly, they do not provide any empirical evidence that the approach described here is viable in practice. There is no implementation or demonstration of this approach, even on toy examples, let alone benchmarks on graph datasets. There is also no discussion on the impact of the proposed pooling on the training of the resulting RNP-GNN. It is not clear to me that this approach is feasible to apply in practice, beyond a hypothetical thought experiment. Therefore, while this line of research seems like an interesting direction, I find it somewhat lackluster and do not thing it is mature enough at this stage to be accepted for publication.\n\nFinally, as a minor remark, the writing here seems somewhat rushed, with several typos and unclear phrases. Some examples:\n- Equation (4) should probably have \"RNP-GNN\" rather than \"RNN-GNN\"\n- The last line before section 5: \"Appendix ??\" missing a proper reference.\n- Page 6: \"sincethe\" missing a space between \"since\" and \"the\"\n- Page 7: \"used for for aggregation\" has a duplicated \"for\"\n- The last sentence of section 5 (right before section 6) should be rephrased - I couldn't decipher it grammatically.\nThere may be more that I missed, but the paper and supplement would benefit from some additional proofreading.", "extra_scores": {}, "extra_text": {}}, {"review_id": "0Qd3xsIUJnb", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper has a fully theoretical flair while proposing a novel and seemingly efficient procedure to recursively compute the higher-order (i.e. more than 1-hop) neighbourhood of a node that are used for learning discriminative graph embedding. The paper contributes with the model above (RNP-GNN) and by providing a proof of its representational power and a general theorem supplying an information theoretic lower bound on the complexity of GNNs that can count induced substructures.\n\nTo the extent of my knowledge the recursive neighbourhood construction procedure presented in the paper is original and it is based on solid graph-theoretic concepts. A proof of the asymptotic complexity of the approach is provided in Section 6, suggesting that the approach can yield to increased representational power at minor computational costs. These results are derived under a sparsity assumption which is not completely clear how much it would hold in practice. In particular, I am not sure whether the sparsity constraint should hold on average in the graph or if the presence of a single node infringing the constraint will induce an exponential growth in complexity. I am thinking in particular to social graphs where hubness might become an issue if the second is true. I would like to read some elaborations as concerns this specific point. \n\nThe theoretical results appear solid and the proof well-constructed although, admittingly, I have not checked the proofs in Appendix in detail. I do have one question as regards the construction of counting substructures proof. Since it entails leveraging vertex covers, does it require this to be minimal or any vertex cover would suffice? Is there any change if the cover is not minimal?\nConcluding, while the paper has certainly good quality theoretical contributions, it lacks an empirical analysis (even a small one, given the theoretical nature of the problem), which would have made the paper claims more convincing. In particular, since much of the results hang on the tradeoff between representational power and efficiency, one would have liked to see an empirical proof of such excellent tradeoff, possibly in graphs of different nature (i.e. bio-chemical and social, given that they tend to have considerably different connectivity patterns). The short but informative empirical analysis in the paper by Murphy et al, ICML 2019 is an excellent example.\n\nOne final remark: the paper, while generally well written, has misprints here and there which can be easily spotted by careful proofreading. Not listing them here, but they should be taken care of.\n\n=========== POST REBUTTAL\n\nThe rebuttal is very helpful and \"to the point\" in clarifying the issues that I had raised as concerns the impact of the assumptions taken in the theoretical proofs. The fact that complexity hinges on average node degree and that any vertex cover sufficies for the proof confirms that the approach put forward in the paper might work out of the theoretical box. The Authors also suggest that the theoretical framework can be translated to a running model with a certain ease and that, in fact, its practical implementation and empircal assessment is on the way. Which brings me to the key point in my assessment. I am convinced there is value in this work and in the theoretical contribution in the paper.  I am not convinced that this paper can have a strong impact without an empirical validation. As I have underlined in my review, there are several related works in literature, with a similar theoretical flair which, nevertheless, provided at least a simple empirical validation. I believe that this paper shold do the same: it would be stronger, more complete and with a higher potential to influence the community. As it is, this is a borderline paper (leaning on the positive side). \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this is an interesting and promising paper, although it is on the theoretical side, without even satisfying toy examples to demonstrate its usefulness. This itself is not a fatal problem (ICLR can and should welcome theoretical papers), however including such experiments would significantly strengthen the impact of this paper, and make it more competitive with other ICLR submissions.
Decision: Reject