summaries: 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.

summaries: The 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.

summaries: 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.

abstractText: 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.

authors:
Emily Alsentzer
Samuel Finlayson
Michelle Li
Marinka Zitnik

title: Subgraph neural networks

venue: Advances in Neural Information Processing Systems,

authors:
Vikraman Arvind
Frank Fuhlbrück
Johannes Köbler
Oleg Verbitsky

title: On weisfeiler-leman invariance: subgraph counts and related graph properties

venue: Journal of Computer and System Sciences,

authors:
Waı̈ss Azizian
Marc Lelarge

title: Characterizing the expressive power of invariant and equivariant graph neural networks

venue: arXiv preprint arXiv:2006.15646,

authors:
Peter Battaglia
Razvan Pascanu
Matthew Lai
Danilo Jimenez Rezende

title: Interaction networks for learning about objects, relations and physics

venue: In Advances in neural information processing systems,

authors:
Suman K Bera
Noujan Pashanasangi
C Seshadhri

title: Linear time subgraph counting, graph degeneracy, and the chasm at size six

authors:
Giorgos Bouritsas
Fabrizio Frasca
Stefanos Zafeiriou
Michael M Bronstein

title: Improving graph neural network expressivity via subgraph isomorphism counting

venue: arXiv preprint arXiv:2006.09252,

authors:
Jianer Chen
Benny Chor
Mike Fellows
Xiuzhen Huang
David Juedes
Iyad A Kanj
Ge Xia

title: Tight lower bounds for certain parameterized np-hard problems

venue: Information and Computation,

authors:
Zhengdao Chen
Soledad Villar
Lei Chen
Joan Bruna

title: On the equivalence between graph isomorphism testing and function approximation with gnns

venue: In Advances in Neural Information Processing Systems,

authors:
Zhengdao Chen
Lei Chen
Soledad Villar
Joan Bruna

title: Can graph neural networks count substructures

venue: arXiv preprint arXiv:2002.04025,

authors:
Leonardo Cotta
Carlos H.C. Teixeira
Ananthram Swami
Bruno Ribeiro

title: Unsupervised joint k-node graph representations with compositional energy-based models

venue: arXiv preprint arXiv:2010.04259,

authors:
Mina Dalirrooyfard
Thuy Duong Vuong
Virginia Vassilevska Williams

title: Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles

venue: In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

title: Convolutional neural networks on graphs with fast localized spectral filtering

authors:
David K Duvenaud
Dougal Maclaurin
Jorge Iparraguirre
Rafael Bombarell
Timothy Hirzel
Alán Aspuru-Guzik
Ryan P Adams

title: Convolutional networks on graphs for learning molecular fingerprints

authors:
Daniel C Elton
Zois Boukouvalas
Mark D Fuge
Peter W Chung

title: Deep learning for molecular design—a review of the state of the art

venue: Molecular Systems Design & Engineering,

authors:
Vikas Garg
Stefanie Jegelka
Tommi Jaakkola

title: Generalization and representational limits of graph neural networks

venue: In Int. Conference on Machine Learning (ICML),

authors:
Justin Gilmer
Samuel S Schoenholz
Patrick F Riley
Oriol Vinyals
George E Dahl

title: Neural message passing for quantum chemistry

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Lior Gishboliner
Yevgeny Levanzov
Asaf Shapira

title: Counting subgraphs in degenerate graphs

venue: arXiv preprint arXiv:2010.05998,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

title: Approximation capabilities of multilayer feedforward networks

venue: Neural networks,

authors:
Kurt Hornik
Maxwell Stinchcombe
Halbert White

title: Multilayer feedforward networks are universal approximators

authors:
Kexin Huang
Marinka Zitnik

title: Graph meta learning via local subgraphs

venue: arXiv preprint arXiv:2006.07889,

authors:
Russell Impagliazzo
Ramamohan Paturi

title: On the complexity of k-sat

authors:
Wengong Jin
Kevin Yang
Regina Barzilay
Tommi Jaakkola

title: Learning multimodal graph-tograph translation for molecule optimization

title: A congruence theorem for trees

venue: Pacific Journal of Mathematics,

authors:
Nicolas Keriven
Gabriel Peyré

title: Universal invariant and equivariant graph neural networks

venue: In Advances in Neural Information Processing Systems (NeurIPS),

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Shengchao Liu
Mehmet F Demirel
Yingyu Liang

title: N-gram graph: Simple unsupervised representation for graphs, with applications to molecules

authors:
Xin Liu
Haojie Pan
Mutian He
Yangqiu Song
Xin Jiang
Lifeng Shang

title: Neural subgraph isomorphism counting

venue: In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

title: What graph neural networks cannot learn: depth vs width

authors:
Haggai Maron
Ethan Fetaya
Nimrod Segol
Yaron Lipman

title: On the universality of invariant networks

venue: In International Conference on Machine Learning,

title: Small graphs are reconstructible

venue: Australasian Journal of Combinatorics,

authors:
Changping Meng
S Chandra Mouli
Bruno Ribeiro
Jennifer Neville

title: Subgraph pattern neural networks for high-order graph evolution prediction

venue: In AAAI,

authors:
Federico Monti
Karl Otness
Michael M Bronstein

title: Motifnet: a motif-based graph convolutional network for directed graphs

venue: IEEE Data Science Workshop (DSW),

authors:
Christopher Morris
Martin Ritzert
Matthias Fey
William L Hamilton
Jan Eric Lenssen
Gaurav Rattan
Martin Grohe

title: Weisfeiler and leman go neural: Higher-order graph neural networks

authors:
R Murphy
B Srinivasan
V Rao

title: Riberio. Janossy pooling: Learning deep permutationinvariant functions for variable-size inputs

authors:
R Murphy
B Srinivasan
V Rao
B Riberio

title: Relational pooling for graph representations

venue: In International Conference on Machine Learning (ICML 2019),

authors:
Ryoma Sato
Makoto Yamada
Hisashi Kashima

title: Approximation ratios of graph neural networks for combinatorial problems

authors:
F. Scarselli
M. Gori
A.C. Tsoi
M. Hagenbuchner
G. Monfardini

title: Computational capabilities of graph neural networks

venue: IEEE Transactions on Neural Networks,

authors:
Franco Scarselli
Marco Gori
Ah Chung Tsoi
Markus Hagenbuchner
Gabriele Monfardini

title: The graph neural network model

authors:
Mengying Sun
Sendong Zhao
Coryandar Gilvary
Olivier Elemento
Jiayu Zhou
Fei Wang

title: Graph convolutional networks for computational drug development and discovery

venue: Briefings in bioinformatics,

authors:
Clement Vignac
Andreas Loukas
Pascal Frossard

title: Building powerful and equivariant graph neural networks with message-passing

venue: arXiv preprint arXiv:2006.15107,

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

authors:
Rex Ying
Zhaoyu Lou
Jiaxuan You
Chengtao Wen
Arquimedes Canedo
Jure Leskovec

title: Neural subgraph matching

venue: arXiv preprint arXiv:2007.03092,

authors:
Zhitao Ying
Jiaxuan You
Christopher Morris
Xiang Ren
Will Hamilton
Jure Leskovec

title: Hierarchical graph representation learning with differentiable pooling

authors:
Yue Yu
Kexin Huang
Chao Zhang
Lucas M. Glass
Jimeng Sun
Cao Xiao

title: Sumgnn: Multityped drug interaction prediction via efficient knowledge graph summarization

heading: 1 INTRODUCTION

text:
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 applications such as encoding molecules, simulating physics, social network analysis, knowledge graphs, and many others (Duvenaud et al., 2015; Defferrard et al., 2016; Battaglia et 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 et al., 2017; Xu et al., 2019; Scarselli et 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 Weisfeiler-Leman (1-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 or count of specific substructures.
To strengthen the expressive power of GNNs, higher-order representations such as k−GNNs (Morris et al., 2019) and k−Invariant 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, a message passing algorithm on k−tuples of vertices, and k−IGNs are based on equivariant linear layers of a feed-forward neural network applied to the input graph as a matrix, and are at least as powerful as k−GNN. These models are provably more powerful than MPNNs and can, e.g., count any induced substructure with at most k vertices. But, this power comes at the computational cost of at least Ω(nk) operations for n vertices. The necessary tradeoffs between expressive power and computational complexity are still an open question.
The expressive power of a GNN is often measured in terms of 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 to measure the power of a GNN, as proposed in (Chen et al., 2020). In particular, we
study whether it is possible to count given substructures with a GNN whose complexity is between that of MPNNs and the existing higher-order GNNs.
To this end, we 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 a learned function on this collection. First, we propose a new such class of GNNs, Recursive Neighborhood Pooling Graph Neural Networks (RNP-GNNs). Specifically, RNP-GNNs represent each vertex by a 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 k vertices. Moreover, for any set of substructures with at most k vertices, there is a specifiable RNP-GNN that can count them. This flexibility allows to design a GNN that is 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-time only if the encoded neighborhoods are of size o(log(n)). In contrast, RNP-GNNs use almost linear operations, i.e., n1+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 a significant improvement over the complexity of O(nk) in k−GNN and k−IGN. Finally, we take a broader perspective and provide an information-theoretic 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 a 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), a
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 (induced) substructures.
• We show that RNP-GNNs offer computational gains over existing models that count substructures: an 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 k−GNN and k−IGN.
• We provide an information-theoretic lower bound on the complexity of a general class of GNN that can count (induced) substructures with at most k vertices.

heading: 2 BACKGROUND

text:
Message Passing Graph Neural Networks. Let G = (V, E , X) be a labeled graph with |V| = n vertices. Here, Xv ∈ X denotes the initial label of v ∈ V , where X ⊆ N is a (countable) domain. A typical Message Passing Graph Neural Network (MPNN) first computes a representation of each vertex, and then aggregates the vertex representations via a readout function into a representation of the entire graph G. The representation h(i)v of each vertex v ∈ V is computed iteratively by aggregating the representations h(i−1)u of the neighboring vertices u:
m(i)v = AGGREGATE (i) ( {{h(i−1)u : u ∈ N (v)}} ) , (1)
h(i)v = COMBINE (i) ( h(i−1)v ,m (i) v ) , (2)
for any v ∈ V , for k iterations, and with h(0)v = Xv . The AGGREGATE/COMBINE functions are parametrized, learnable functions, and {{.}} denotes a multi-set, i.e., a set with (possibly) repeating elements. A graph-level representation can be computed as
hG = READOUT ( h(k)v : v ∈ V ) , (3)
where READOUT is a learnable function. For representational power, it is important that the learnable functions above are injective, which can be achieved, e.g., if the AGGREGATE function is a summation and COMBINE is a weighted sum concatenated with an MLP (Xu et al. (2019)).
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 a similar fashion as GNNs do on vertices (Morris et al., 2019). At initialization, each k−tuple is labeled with its type, that is, two k−tuples are labeled differently if their induced subgraphs are not isomorphic. As a result, k−GNNs can count (induced) substructures with at most k vertices even at initialization. Another class of higher-order networks are k−IGNs, which are constructed with linear invariant/equivariant 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 at most k vertices. However, both methods need O(nk) operations.
Specifically for counting substructures, Chen et al. (2020) propose Local Relational Pooling (LRP) networks. LRPs apply Relational Pooling (RP) networks (Murphy et al., 2019b;a) on the neighborhoods around each vertex. RP networks use permutation-variant functions and convert them to a permutation-invariant function by summing over all permutations. This summation is computationally expensive.

heading: 3 OTHER RELATED WORKS

text:
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 an equivalence between the graph isomorphism problem and the power to approximate permutation invariant functions on graphs. Maron et al. (2019) and Keriven & Peyré (2019) propose higher-order, tensor-based GNN models that provably achieve universal approximation of permutation-invariant functions on 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.
Subgraphs and GNNs. The idea of considering local neighborhoods to have better representations than MPNNs is considered in several works (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 & Zitnik, 2020). For example, in link prediction, one can use local neighborhoods around links and apply GNNs, as suggested in (Zhang & Chen, 2018). A novel method based on combining GNNs and a clustering algorithm is proposed in (Ying et al. (2018)). For graph comparison (i.e., testing whether a 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 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.

heading: 4 RECURSIVE NEIGHBORHOOD POOLING

text:
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 a representation of its radius r1-neighborhood, and then combine 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 a different radius r2, and, recursively, a sequence of radii (r1, r2, . . . , rt) ∈ Nt to obtain the final representation h(t)v of vertices after t 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 a result, as we will see in Section 5.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-GNNs to encode more global information, although our representation results in Section 5.1 hold even without that. In Section 6, we will compare the computational complexity of RNP-GNN and these other models.
Formally, an RNP-GNN is a parametrized learnable function f(.; θ) : Gn → Rd, where Gn is the set of all labeled graphs on n vertices. Let G = (V, E , X) be a labeled graph with |V| = n vertices, and let h(0)v = Xv be the initial representation of each vertex v. LetNr(v) denote the neighborhood of radius r of vertex v, and let G(t−1)v ( Nr1(v) \ {v}) ) denote the induced subgraph of G on the set of vertices Nr1(v) \ {v}, with augmented vertex label X(t−1)u = (h(t−1)u ,1[(u, v) ∈ E ]) for any u ∈ Nr1(v) \ {v}. This means we add information about whether vertices are direct neighbors (with distance one) of v. Given a recursion sequence (r1, r2, . . . , rt) or radii, the representations are updated as
m(t)v = RNP-GNN (t−1) ( G(t−1)v (Nr1(v) \ {v}) ) , (4)
h(t)v = COMBINE (t) ( h(t−1)v ,m (t) v ) , (5)
for any v ∈ V , and
hG = READOUT ( {{h(t)v : v ∈ V}} ) . (6)
Different from MPNNs, the recursive update (4) is in general applied to a subgraph, and not a multi-set of vertex representations. RNP-GNN(t−1) is an RNP-GNN with recursion parameters (r2, . . . , rt) ∈ Nt−1. The final READOUT is an injective, permutation-invariant learnable multi-set function.
If t = 1, then m(t)v = AGGREGATE (t) ( {{(h(t−1)u ,1[(u, v) ∈ E ]) : u ∈ Nr1(v)}} ) (7)
is a permutation-invariant aggregation function as used in MPNNs, only over a potentially larger neighborhood. For r1 = 1 and t = 1, RNP-GNN reduces to MPNN.
In Figure 1, we illustrate an RNP-GNN with recursion parameters (2, 2, 1) as an example. We also provide pseudocode for RNP-GNNs in Appendix C.

heading: 5 EXPRESSIVE POWER

text: In this section, we analyze the expressive power of RNP-GNNs.

heading: 5.1 COUNTING (INDUCED) SUBSTRUCTURES

text:
In contrast to 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. LetG,H be arbitrary labeled simple graphs, where V is the set of vertices inG. Also, for any S ⊆ V , let G(S) denote the subgraph of G induced by S. The induced subgraph count function is defined as
C(G;H) := ∑ S⊆V 1{G(S) ∼= H}, (8)
i.e., the number of subgraphs of G isomorphic to H . For unlabeled H , the function is defined analogously.
We also need to define a notion of covering for graphs. Our definition uses distances on graphs. Definition 2. Let H = (VH , EH) be a (possibly labeled) simple connected graph. For any S ⊆ VH and v ∈ VH , define
d̄H(v;S) := max u∈S d(u, v), (9)
where d(., .) is the shortest-path distance in H . Definition 3. Let H be a (possibly labeled) simple connected graph on t + 1 vertices. A permutation of vertices, such as (v1, v2, . . . , vt+1), is called a vertex covering sequence, with respect to a sequence r = (r1, r2, . . . , rt) ∈ Nt called a covering sequence, if and only if
d̄H′i(vi;Si) ≤ ri, (10) for any i ∈ [t + 1] = {1, 2, . . . , t + 1}, where Si = {vi, vi+1 . . . , vt+1} and H ′i = H(Si) is the subgraph of H induced by the set of vertices Si. We also say that H admits the covering sequence r = (r1, r2, . . . , rt) ∈ Nt if there is a 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 vertices with radius r1. Then, we remove that vertex and compute the covering sequence of the remaining graph. Figure 3 shows an example of a covering sequence computation. An important property, which holds by definition, is that if r is a covering sequence for H , then any r′ ≥ r (in a point-wise sense) is also a covering sequence for H .
Note that any connected graph on k vertices admits at least one covering sequence, which is (k − 1, k − 2, . . . , 1). To observe this fact, note that in a connected graph, there is at least one vertex that can be removed and the remaining graph still remains connected. Therefore, we may take this vertex as the first element of a 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 r1, since the complexity of the resulting RNP-GNN depends on r1. 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 k vertices and H1 b H2, i.e., H1 is a subgraph of H2 (not necessarily induced-subgraph), then, it follows from the definition that any covering sequence for H1 is also a 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 1. Consider a set of (labeled or unlabeled) graphs H on t + 1 vertices, such that any H ∈ H admits the covering sequence (r1, r2, . . . , rt). Then, there is an RNP-GNN with recursion parameters (r1, r2, . . . , rt) that can count any H ∈ H. In other words, if there exists H ∈ H such that C(G1;H) 6= C(G2;H), then f(G1; θ) 6= f(G2; θ). The same result also holds for the non-induced subgraph count function.
Theorem 1 states that, with appropriate recursion parameters, any set of (labeled or unlabeled) substructures can be counted by an RNP-GNN. Interestingly, induced and non-induced subgraphs can be both counted in RNP-GNNs1.
The theorem holds for any covering sequence that is valid for all graphs in H. For any graph, one can compute a covering sequence by computing a 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 inH is the coordinate-wise maximum of all these sequences. For large substructures, the sequence (r1, r2, . . . , rt) 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., ri = O(1) for all i), raising the hope to count these structures efficiently. In particular, r1 is an important parameter. In Section 6, we analyze the complexity of RNP-GNNs in more detail.

heading: 5.2 A UNIVERSAL APPROXIMATION RESULT FOR LOCAL FUNCTIONS

text:
Theorem 1 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 or small subgraphs in a graph.
First, we recall that for a graph G, G(S) denotes the subgraph of G induced by the set of vertices S. Definition 4. A function ` : Gn → Rd is called an r−local graph function if
`(G) = φ({{ψ(G(S)) : S ⊆ V, |S| ≤ r}}), (11) where ψ : Gr → Rd ′ is a function on graphs and φ is a multi-set function.
1For simplicity, we assume that H only contains t+ 1 vertex graphs. If H includes graphs with strictly less than t + 1 vertices, we can simply add a sufficient number of zeros to the RHS of their covering sequences.
In other words, a local function only depends on small substructures.
Theorem 2. For any r−local graph function `(.), there exists an RNP-GNN f(.; θ) with recursion parameters (r − 1, r − 2, . . . , 1) such that f(G; θ) = `(G) for any G ∈ Gn.
As a result, we can provably learn all the local information in a graph with an appropriate RNPGNN. 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 to 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 r = 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 a polynomial in n.

heading: 6 COMPUTATIONAL COMPLEXITY

text:
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. A complexity measure existing in the literature is the tensor order. For higher-order networks, e.g., k−IGNs, we need to consider tensors in Rnk . The space complexity is then O(nk) and the time complexity can be even more, dependent on the algorithm used to process tensors. In general, for a 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 a method, we need to bound the number of node representation updates, which we do in the following theorem.
Theorem 3. Let f(.; θ) : Gn → Rd be an RNP-GNN with the recursion parameters (r1, r2, . . . , rt). Assume that the observed graphs G1, G2, . . ., whose representations we compute, satisfy the following property:
max v∈[n]
|Nr1(v)| ≤ c, (12)
where c is a graph independent constant. Then, the number of node updates in the RNP-GNN is O(nct).
In other words, if c = no(1) and t = O(1), then RNP-GNN requires relatively few updates (that is, n1+o(1)), compared to the higher-order networks (O(nt+1)). Also, in this case, finding neighborhoods is not difficult, since neighborhoods are small (no(1)). Note that if the maximum degree of the given graphs is ∆, then c = O(r1∆r1). Therefore, similarly, if ∆ = no(1) then we can count with at most n1+o(1) updates.
The above results show that when using RNP-GNNs with sparse graphs, we can learn functions of substructures with k vertices without requiring k−order tensors. LRPs also encode neighborhoods of distance r1 around nodes. In particular, all c! permutations of the nodes in a neighborhood of size c are considered to obtain the representation. As a result, LRP networks only have polynomial complexity if c = o(log(n)). Thus, RNP-GNNs can provide an exponential improvement in terms of the tolerable size c of neighborhoods with distance r1 in the graph.
Moreover, theorem 3 suggests to aim for small r1. The other ri’s may be larger than r1, as shown in Figure 4, but do not affect the upper bound on the complexity.

heading: 7 AN INFORMATION-THEORETIC LOWER BOUND

text:
In this section, we provide a general information-theoretic lower bound for graph representations that encode a given graph G by first encoding a number of (possibly small) graphs G1, G2, . . . , Gt and then aggregating the resulting representations. The sequence of graphs G1, G2, . . . , Gt may be obtained in an arbitrary way from G. For example, in an MPNN, Gi can be the computation tree (rooted tree) at node i. As another example, in LRP, Gi is the local neighborhood around node i.
Formally, consider a graph representation f(.; θ) : Gn → Rd as f(G; θ) = Φ({{ψ(Gi) : i ∈ [t]}}), [t] = {1, . . . , t} (13) for any G ∈ Gn, where Φ is a multi-set function, (G1, G2, . . . , Gt) = Ξ(G) where Ξ(.) : Gn →(⋃∞ m=1 Gm )t is a function from one graph to t graphs, and ψ : ⋃∞ m=1 Gm → [s] is a function on graphs taking s values. In short, we encode t graphs, and each encoding takes one of s values. We call this graph representation function an (s, t)-good graph representation.
Theorem 4. Consider a parametrized class of (s, t)−good representations f(.; θ) : Gn → Rd that is able to count any (not necessarily induced2) substructure with k vertices. More precisely, for any graph H with k vertices, there exists f(.; θ) such that if C(G1;H) 6= C(G2;H), then f(G1; θ) 6= f(G2; θ). Then3, t = Ω̃(n k s−1 ).
In particular, for any (s, t)−good graph representation with s = 2, i.e., binary encoding functions, we need Ω̃(nk) encoded graphs. This implies that, for s = 2, enumerating all subgraphs and deciding for each whether it equals H is near optimal. Moreover, if s ≤ k, then t = Ω(n) small graphs would not suffice to enable counting.
More interestingly, if k, s = O(1), then it is impossible to perform the substructure counting task with t = O(log(n)). As a result, in this case, considering n encoded graphs (as is done in GNNs or LRP networks) cannot be exponentially improved.
The lower bound in this section is information-theoretic and hence applies to any algorithm. It may be possible to strengthen it by considering computational complexity, too. For binary encodings, i.e., s = 2, however, we know that the bound cannot be improved since manual counting of subgraphs matches the lower bound.

heading: 8 TIME COMPLEXITY LOWER BOUNDS FOR COUNTING SUBGRAPHS

text:
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 a conjecture in complexity theory (Impagliazzo & Paturi, 2001), and states that several NP-complete problems cannot be solved in sub-exponential time. ETH, as a stronger version of the P 6= 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 a graph representation can count any subgraph H of size k, then computing it requires at least nΩ(k) time.
Corollary 1. Assuming ETH conjecture holds, any graph representation that can count any substructure H on k vertices with appropriate parametrization needs nΩ(k) time to compute.
The above bound matches the O(nk) complexity of the higher-order GNNs. Comparing with Theorem 4 above, Corollary 1 is more general, while Theorem 4 has fewer assumptions and offers a refined result for aggregation-based graph representations.
2The theorem also holds for induced-subgraphs, with/without vertex labels. 3Ω̃(m) is Ω(m) up to poly-logarithmic factors.
Given that Corollary 1 is a worst-case bound, a natural question is whether we can do better for subclasses of graphs. Regarding H , even if H is a random Erdös-Rényi graph, it can only be counted in nΩ(k/ log k) 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(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 O(nk). One may ask whether it is possible 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)). 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.

heading: 9 CONCLUSION

text: In this paper, we studied the theoretical possibility of counting substructures (induced-subgraphs) by a graph representation network. We proposed an architecture, called RNP-GNN, and we proved that for reasonably sparse graphs we can efficiently count substructures. Characterizing the expressive power of GNNs via the set of functions they can learn on substructures may be useful for developing new architectures. In the end, we proved a general lower bound for any graph representation which counts subgraphs and works by aggregating representations of a collection of graphs derived from the graph.

heading: A PROOFS

text:
A.1 PROOF OF THEOREM 1
A.1.1 PRELIMINARIES
Let us first state a few definitions about the graph functions. Note that for any graph function f : Gn → Rd, we have f(G) = f(H) for any G ∼= H . Definition 5. Given two graph functions f, g : Gn → Rd, we write f w g, if and only if for any G1, G2 ∈ Gn,
∀G1, G2 ∈ Gn : g(G1) 6= g(G2) =⇒ f(G1) 6= f(G2), (14) or, equivalently,
∀G1, G2 ∈ Gn : f(G1) = f(G2) =⇒ g(G1) = g(G2). (15)
Proposition 1. Consider graph functions f, g, h : Gn → Rd such that f w g and g w h. Then, f w h. In other words, w is transitive.
Proof. The proposition holds by definition.
Proposition 2. Consider graph functions f, g : Gn → Rd such that f w g. Then, there is a function ξ : Rd → Rd such that ξ ◦ f = g.
Proof. Let Gn = ti∈NFi be the partitioning induced by the equality relation with respect to the function f on Gn. Similarly define Gi, i ∈ N for g. Note that due to the definition, {Fi : i ∈ N} is a refinement for {Gi : i ∈ N}. Define ξ to be the unique mapping from {Fi : i ∈ N} to {Gi : i ∈ 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, if and only if
• all the aggregate functions are injective as mappings from a multi-set on a 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, r2, . . . , rt) where f is maximally expressive. Then, f w g.
Proof. The proposition holds by definition.
Proposition 4. Consider a sequence of graph functions f, g1, . . . , gk. If f w gi for all i ∈ [k], then
f w k∑
i=1
cigi, (16)
for any ci ∈ R, i ∈ N.
Proof. Since f w gi, we have ∀G1, G2 ∈ Gn : f(G1) = f(G2) =⇒ gi(G1) = gi(G2), (17) for all i ∈ [k]. This means that for any G1, G2 ∈ Gn if f(G1) = f(G2) then gi(G1) = gi(G2), i ∈ [k], and consequently ∑ki=1 cigi(G1) = ∑ki=1 cigi(G2). Therefore, from the definition we conclude f w∑ki=1 cigi. Note that the same proof also holds in the case of countable summations as long as the summation is bounded.
Definition 7. Let H = (VH , EH , XH) be a labeled connected simple graph on k vertices. For any labeled graph G = (VG, EG, XG) ∈ Gn, the induced subgraph count function C(G;H) is defined as
C(G;H) := ∑ S⊆[n] 1{G(S) ∼= H}. (18)
Also, let C̄(G;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 n > k define
C̄(G;H) := ∑ S⊆[n] |S|=k C̄(G(S);H). (19)
Otherwise, n = k, and we define C̄(G;H) := ∑
H̃∈H̃(H)
cH̃,H × 1{G ∼= H̃}, (20)
where
H̃(H) := {H̃ ∈ Gk : H̃ c H } , (21)
is defined with respect to the graph isomorphism, and cH̃,H ∈ N denotes the number of subgraphs in H identical to H̃ . Note that H̃(H) is a finite set and c denotes being a (not necessarily induced) subgraph.
Proposition 5. Let H be a family of graphs. If for any H ∈ H, there is an RNP-GNN fH(.; θ) with recursion parameters (r1, r2, . . . , rt) such that fH w C(G;H), then there exists an RNP-GNN f(.; θ) with recursion parameters (r1, r2, . . . , rt) such that f w ∑ H∈H C(G;H).
Proof. Let f(.; θ) be a maximally expressive RNP-GNN. Note that by the definition f w fH for any H ∈ H. Since w is transitive, f w C(G;H) for all H ∈ H, and using Proposition 4, we conclude that f w∑H∈H C(G;H). The following proposition shows that there is no difference between counting induced labeled graphs and counting induced unlabeled graphs in RNP-GNNs. Proposition 6. Let H0 be an unlabeled connected graph. Assume that for any labeled graph H , which is constructed by adding arbitrary labels to H0, there exists an RNP-GNN fH(.; θH) such that fH w C(G;H), then for its unlabeled counterpart H0, there exists an RNP-GNN f(.; θ) with the same recursion parameters as fH(.; θH) such that f w C(G;H0).
Proof. If there exists an RNP-GNN fH(.; θH) such that fH w C(G;H), then for a maximally expressive RNP-GNN f(.; θ) with the same recursion parameters as fH we also have fH w C(G;H). Let H be the set of all labeled graphs H = (V, E , X) ∈ Gk up to graph isomorphism, where X ∈ X k for a countable set X . Note thatH = {H1, H2, . . .} is a countable set. Now we write
C(G;H0) = ∑ S⊆[n] |S|=k 1{G(S) ∼= H0} (22)
= ∑ S⊆[n] |S|=k ∑ i∈N 1{G(S) ∼= Hi} (23)
= ∑ i∈N ∑ S⊆[n] |S|=k 1{G(S) ∼= Hi} (24)
= ∑ i∈N C(G;Hi). (25)
(26)
Now using Proposition 4 we conclude that f w C(G;H0) since C(G;H0) is always finite.
Definition 8. Let H be a (possibly labeled) simple connected graph. For any S ⊆ VH and v ∈ VH , define
d̄H(v;S) := max u∈S d(u, v). (27)
Definition 9. Let H be a (possibly labeled) connected simple graph on k = t + 1 vertices. A permutation of vertices, such as (v1, v2, . . . , vt+1), is called a vertex covering sequence, with respect to a sequence r = (r1, r2, . . . , rt) ∈ Nt, called a covering sequence, if and only if
d̄H′i(vi;Si) ≤ ri, (28)
for i ∈ [t + 1], where H ′i = H(Si) and Si = {vi, vi+1, . . . , vt+1}. Let CH(r) denote the set of all vertex covering sequences with respect to the covering sequence r for H .
Proposition 7. For any G,H ∈ Gk, if G c H (non-induced subgraph), then CH(r) ⊆ CG(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 1 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 fH(.; θH) such that fH w C(G;H), then we prove there exists an RNP-GNN f(.; θ) with the same recursion parameters as fH such that f w C̄(G;H). If there exists an RNP-GNN fH(.; θH) such that fH w C(G;H), then for a maximally expressive RNP-GNN f(.; θ) with the same recursion parameters as fH we also have f w C(G;H). Note that
C̄(G,H) = ∑ S⊆[n] |S|=k C̄(G(S);H) (30)
= ∑ S⊆[n] |S|=k ∑ H̃∈H̃(H) cH̃,H × 1{G(S) ∼= H̃} (31)
= ∑
H̃∈H̃(H)
cH̃,H ∑ S⊆[n] |S|=k 1{G(S) ∼= H̃} (32)
= ∑ i∈N cHi,H × C(G,Hi), (33)
where H̃(H) = {H1, H2, . . .}. Claim 1. f w C(G,Hi) for any i.
Using Proposition 4 and Claim 1 we conclude that f w C̄(G;H) since C̄(G;H) is finite and f w C(G,Hi) for any i, and the proof is complete. The missing part which we must show here is that for any Hi the sequence (r1, r2, . . . , rt) which covers H also covers Hi. This follows from Proposition 7. We are done.
At the end of this part, let us introduce an important notation. For any labeled connected simple graph on k vertices G = (V, E , X), let G∗v be the resulting induced graph obtained after removing v ∈ V from G with the new labels defined as
X∗u := (Xu,1{(u, v) ∈ E}), (34) for each u ∈ V \ {v}. We may also use X∗vu for more clarification.
A.1.2 PROOF OF THEOREM 1
We utilize an inductive prove on t, which is the length of the covering sequence of H . Equivalently, due to the definition, t = 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 a simple connected labeled graph and the goal is to achieve the induced-subgraph count function via an RNP-GNN with appropriate 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 a specific (labeled) edge in the given graph G. Note that in this case we apply an RNP-GNN with recursion parameter r1 ≥ 1. Denote the two labels of the vertices in H by XH1 , X
H 2 ∈ X . The output of an RNP-GNN f(.; θ) is f(G; θ) = φ({{ψ(XGv , ϕ({{X∗vu : u ∈ Nr1(v)}})) : v ∈ [n]}}), (35)
where f(.; θ) we assume that f(.; θ) is maximally expressive. The goal is to show that f w C(G;H). Using the transitivity of w, we only need to choose appropriate φ, ψ, ϕ to achieve f̂ = C(G;H) as the final representation. Let
φ({{zv : v ∈ [n]}}) := 1
2 + 2× 1{XH1 = XH2 } n∑ i=1 zi (36)
ψ(X, (z, z′)) := z × 1{X = XH1 }+ z′ × 1{X = XH2 } (37)
ϕ({{zu : u ∈ [n′]}}) := ( n′∑
i=1 1{zu = (XH2 , 1)}, n′∑ i=1 1{zu = (XH1 , 1) ) . (38)
Then, a simple computation shows that
f̂(G; θ) = φ({{ψ(XGv , ϕ({{X∗vu : u ∈ Nr1(v)}})) : v ∈ [n]}}), (39) = C(G;H). (40)
Since f̂(.; θ) is an RNP-GNN with recursion parameter r1 and for any maximally expressive RNPGNN f(.; θ) with the same recursion parameter as f̂ we have f w f̂ and f̂ w C(G;H), we conclude that f w C(G;H) and this completes the proof. Induction step. Assume that the desired result holds for t − 1 (t ≥ 2). We show that it also holds for t. Let us first define
H∗ := {H∗v1 : ∃v2, . . . , vt ∈ [k] : (v1, v2, . . . , vt) ∈ CH(r)} (41) c∗(H∗) := 1{H∗ ∈ H∗} ×#{v ∈ [k] : H∗v ∼= H∗}. (42)
Note thatH∗ 6= ∅ by the assumption. Let ‖H∗‖ := ∑ H∗∈H∗ c∗(H∗). (43)
For all H∗ ∈ H∗, using the induction hypothesis, there is a (universal) RNP-GNN f̂(.; θ̂) with recursion parameters (r2, r3, . . . , rt) such that f̂ w C(G;H∗). Using Proposition 4 we conclude
f̂ w ∑
u∈[k]:H∗u∈H∗ C(G;H∗u). (44)
Define a maximally expressive RNP-GNN with the recursion parameters (r1, r2, . . . , rt) as follows:
f(G; θ) = φ({{ψ(XGv , f̂(G∗(Nr1(v)); θ̂)) : v ∈ [n]}}). (45) Similar to the proof for t = 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∗u(G; θ) := φ({{ψH∗u(XGv , ξ ◦ f̂(G∗(Nr1(v)); θ̂)) : v ∈ [n]}}), (46)
where
φ({{zv : v ∈ [n]}}) := 1 ‖H∗‖ n∑
i=1
zi (47)
ψH∗u(X, z) := z × 1{X = XHu }, (48) (49)
and ξ ◦ f̂ = C(G;H∗u). Note that the existence of such function ξ is guaranteed due to Proposition 2. Now we write
‖H∗‖ × C(G;H) = ‖H∗‖ ∑ S⊆[n] 1{G(S) ∼= H} (50)
= ∑ S⊆[n] ∑ v∈S 1{∃u ∈ [k] : (G(S \ {v}))∗v ∼= H∗u ∈ H∗ ∧XGv = XHu } (51)
= ∑ v∈[n] ∑ v∈S⊆[n] 1{∃u ∈ [k] : (G(S \ {v}))∗v ∼= H∗u ∈ H∗ ∧XGv = XHu } (52)
= ∑ v∈[n] ∑ v∈S⊆Nr1 (v) 1{∃u ∈ [k] : (G(S \ {v}))∗v ∼= H∗u ∈ H∗ ∧XGv = XHu }
(53) = ∑ v∈[n] ∑ v∈S⊆Nr1 (v) ∑ u∈[k]:H∗u∈H∗ 1{(G(S \ {v}))∗v ∼= H∗u}1{XGv = XHu } (54)
= ∑ v∈[n] ∑ u∈[k]:H∗u∈H∗ C(G∗(Nr1(v));H∗u)× 1{XGv = XHu }, (55)
which means that ∑ u∈[k]:H∗u∈H∗ fH∗u(G; θ) w C(G;H). (56)
However, for a maximally expressive RNP-GNN f(.; θ) we know that f w fH∗u for all H∗u ∈ H and this means that f w C(G;H). The proof is thus complete.
A.2 PROOF OF THEOREM 2
For any labeled graph H on r vertices (not necessarily connected) we claim that RNP-GNNs can count them.
Claim 2. Let f(.; θ) : Gn → Rd be a maximally expressive RNP-GNN with recursion parameters (r − 1, r − 2, . . . , 1). Then, f w C(G;H).
Now consider the function
`(G) = φ({{ψ(G(S)) : S ⊆ V, |S| ≤ r}}). (57) We claim that f w ` (f is defined in the previous claim) and this completes the proof according to Proposition 2.
To prove the claim, assume that f(G1) = f(G2). Then, we conclude that C(G1;H) = C(G2;H) for any labeled H (not necessarily connected) with r vertices. Now, we have
`(G) = φ({{ψ(G(S)) : S ⊆ V, |S| ≤ r}}) (58) = φ({{ψ(H) : H ∈ Gr, the multiplicity of H is C(G;H)}}), (59)
which shows that `(G1) = `(G2).
Proof of Claim 2. To prove the claim, we use an induction on the number of connected components cH of graph H . If H is connected, i.e., cH = 1, then according to Theorem 1, we know that f w C(G;H).
Now assume that the claim holds for cH = c − 1 ≥ 1. We show that it also holds for cH = c. Let H1, H2, . . . ,Hc denote the connected components of H . Also assume that Hi 6∼= Hj for all i 6= j. We will relax this assumption later. Let us define
AG := {(S1,S2, . . . ,Sc) : ∀i ∈ [c] : Si ⊆ [n];G(Si) ∼= Hi}. (60) Note that we can write
|AG| = c∏
i=1
C(G;Hi) (61)
= C(G;H) + ∞∑ j=1 c′jC(G;H ′ j), (62)
where H ′1, H ′ 2, . . . are all non-isomorphic graphs obtained by adding edges (at least one edge) between c graphs H1, H2, . . . ,Hc, or contracting a number of vertices of them. The constants c′j are just used to remove the effect of multiple counting due to the symmetry. Now, since for any Hi, H ′j the number of connected components is strictly less that c, using the induction, we have f w C(G;Hi) and f w C(G;H ′j) for all j and all i ∈ [c]. According to Proposition 4, we conclude that f w C(G;H) and this completes the proof. Also, if Hi, i ∈ [c], are not pairwise non-isomorphic, then we can use αC(G;H) in above equation instead of C(G;H), where α > 0 removes the effect of multiple counting by symmetry. The proof is thus complete.
A.3 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 (r1, r2, . . . , rt). First of all, we have n variables used for the final representations of vertices. For each vertex v1 ∈ V , we explore the local neighborhood Nr1(v1) and apply a new RNP-GNN network to that neighborhood. In other words, for the second step we need to update |Nr1(v1)| nodes. Similarly, for the ith step of the algorithm we have as most
λi := max v1∈[n] max vj+1∈Nrj (vj) ∀j∈[i−1]
|Nr1(v1) ∩Nr2(v2) ∩Nr3(v3) . . . ∩Nri(vi)|, (63)
updates. Therefore, we can bound the number of node updates as
n× t∏
i=1
λi. (64)
Since λi is decreasing in i, we simply conclude the desired result.
A.4 PROOF OF THEOREM 4
Let Kk denote the complete graph on k vertices. Claim 3. For any k, n ∈ N, such that n is sufficiently large,∣∣∣{C(G;Kk) : G ∈ Gn}∣∣∣ ≥ (cn/k log(n/k)− k)k
k! = Ω̃(nk), (65)
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;Kk) can take is nk, up to poly-logarithmic factors.
To prove the theorem, we use the above claim. Consider a class of (s, t)−good graph representations f(.; θ) which can count any substructure on k vertices. As a result, f w C(G;Kk) for an appropriate parametrization θ. By the definition, f(.) must take at least ∣∣∣{C(G;Kk) : G ∈ Gn}∣∣∣ different values, i.e., ∣∣∣{f(G; θ) : G ∈ Gn}∣∣∣ ≥ ∣∣∣{C(G;Kk) : G ∈ Gn}∣∣∣. (66)
Also, ∣∣∣{f(G; θ) : G ∈ Gn}∣∣∣ ≤ ∣∣∣{{{ψ(Gi) : i ∈ [t]}} : G ∈ Gn}∣∣∣, (67) where (G1, G2, . . . , Gt) = Ξ(G). But, ψ can take only s values. Therefore, we have∣∣∣{C(G;Kk) : G ∈ Gn}∣∣∣ ≤ ∣∣∣{f(G; θ) : G ∈ Gn}∣∣∣ (68)
≤ ∣∣∣{{{ψ(Gi) : i ∈ [t]}} : G ∈ Gn}∣∣∣ (69)
≤ ∣∣∣{{{αi : i ∈ [t]}} : ∀i ∈ [t] : αi ∈ [s]}∣∣∣ (70)
≤ (t+ 1)s−1. (71)
As a result, (t+ 1)s−1 = Ω̃(nk) or t = Ω̃(n k
s−1 ). To complete the proof, we only need to prove the claim.
Proof of Claim 3. Let p1, p2, . . . , pm be distinct prime numbers less than n/k. Using the prime number theorem, we know that limn→∞ mn/k log(n/k) = 1. In particular, we can choose n large enough to ensure cn/k log(n/k) < m for any constant c < 1.
For any B = {b1, b2, . . . , bk} ⊆ [m], define GB as a graph on n vertices such that VGB = V0 t (ti∈[k]Vi), and |Vi| = pbi . Also,
e = (u, v) ∈ GB ⇐⇒ ∃ i, j ∈ [m], i 6= j : u ∈ Vi & v ∈ Vj . (72)
The graph GB is well-defined since ∑k i=1 pbi ≤ k × n/k = n. Note that C(GB;Kk) = ∏k
i=1 pbi . Also, since pi, i ∈ [m], are prime numbers, there is a unique bijection
B ϕ←→ C(GB;Kk). (73) Therefore, ∣∣∣{C(G;Kk) : G ∈ Gn}∣∣∣ ≥ ∣∣∣{C(GB;Kk) : B ⊆ [m], |B| = k}∣∣∣ (74)
=
( m
k
) (75)
≥ (m− k) k
k! (76)
≥ (cn/k log(n/k)− k) k
k! . (77)

heading: B RELATIONSHIP TO THE RECONSTRUCTION CONJECTURE

text:
Theorem 2 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 relationship/differences. First, we need a definition for unlabeled graphs. Definition 10. Let Fn ⊆ Gn be a set of graphs and let Gv = G(V \ {v}) for any finite simple graph G = (V, E), and any v ∈ V . Then, we say the set F is reconstructible if and only if there is a bijection
{{Gv : v ∈ V}} Φ←→ G, (78) for any G ∈ Fn. In other words, Fn is reconstructible, if and only if the multi-set {{Gv : v ∈ V} fully identifies G for any G ∈ Fn.
It is 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 1 (Kelly et al. (1957)). Gn is reconstructible.
For RNP-GNNs, the reconstruction from the subgraphs G∗v , v ∈ [n] is possible, since we 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 relabeling, the reconstruction conjecture is not required to hold to show the universality results for RNP-GNNs, although that conjecture is a motivation for this paper. Moreover, if it can be shown that the reconstruction conjecture it true, it may be also possible to find a simple encoding of subgraphs to an original graph and this may lead to more powerful but less complex new GNNs.

heading: C THE RNP-GNN ALGORITHM

text:
In this section, we provide pseudocode for RNP-GNNs. The algorithm below computes node representations. For a graph representation, we can aggregate them with a common readout, e.g., hG ← MLP (∑ v∈V h (t) v ) . Following (Xu et al., 2019), we use sum pooling here, to ensure that we can represent injective aggregation functions.
Algorithm 1 Recursive Neighborhood Pooling-GNN (RNP-GNN) Input: G = (V, E , {xv}v∈V) where V = [n], recursion parameters r1, r2, . . . , rt ∈ N, (i) ∈ R, i ∈ [t], node features {xv}v∈V . Output: hv for all v ∈ V hinv ← xv for all v ∈ V if t = 1 then
hv ← MLP(t) ( (1 + (1))hinv + ∑
u∈Nr1 (v)\{v}
(hinu ,1(u, v) ∈ E)′ ) ,
for all v ∈ V . else
for all v ∈ V do G′v ← G(Nr1(v) \ {v}) with node features {hinu} {ĥv,u}u∈G′v\{v} ← RNP-GNN(G′v, (r2, r3, . . . , rt), ( (2), . . . , (t))) hv ← MLP(t) ( (1 + (t))hinv + ∑ u∈Nr1 (v)\{v} ĥu,v ) .
end for end if return {hv}v∈V
With this algorithm, one can achieve the expressive power of RNP-GNNs if high dimensional MLPs 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).

heading: D COMPUTING A COVERING SEQUENCE

text:
As we explained in the context of Theorem 1, we need a covering sequence (or an upper bound to that) to design an RNP-GNN network that can count a given substructure. A covering sequence can be constructed from a spanning tree of the graph.
For reducing complexity, it is desirable to have a covering sequence with minimum r1 (Theorem 3). Here, we suggest an algorithm for obtaining such a covering sequence, shown in Algorithm 2. For obtaining merely an aribtrary covering sequence, one can compute any minimum spanning tree (MST), and then proceed as with the MST in Algorithm 2.
Given an MST, we build a vertex covering sequence by iteratively removing a leave vi from the tree and adding the respective node vi to the sequence. This ensures that, at any point, the remaining graph is connected. At position i corresponding to vi, the covering sequence contains the maximum
distance ri of vi 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 r1 = maxu∈V d(u, v1), we need to ensure that a node in arg minv∈V maxu∈V d(u, v) is a leaf in the spanning tree. Hence, we first compute maxu∈V d(u, v) for all nodes v, e.g., by running All-Pairs-Shortest-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 v1, and stop when we find one.
Say v∗ is the current node in the list. To compute a spanning tree where v∗ is a leaf, we assign a large weight to all the edges adjacent to v∗, and a 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 v1 in the vertex covering sequence. This algorithm runs in polynomial time.
Algorithm 2 Computing a covering sequence with minimum r1 Input: H = (V, E , X) where V = [t+ 1] Output: A minimal covering sequence (r1, r2 . . . , rt), and its corresponding vertex covering se-
quence (v1, v2, . . . , vt+1) For any u, v ∈ V , compute d(u, v) using APSP (u1, u2, . . . , ut+1)← all the vertices sorted increasingly in s(v) := maxu∈V d(u, v) for i = 1 to t+ 1 do
Set edge weights w(u, v) = 1 + t× 1{u = ui ∨ v = ui} for all (u, v) ∈ E HT ← the MST of H with weights w if ui is a leaf in HT then v1 ← ui r1 ← s(ui) break
end if end for for i = 2 to t+ 1 do vi ← one of the leaves of HT ri ← maxu∈VHT d(u, vi) HT ← HT after removing vi end for return (r1, r2, . . . , rt) and (v1, v2, . . . , vt+1)