#  Counting Substructures with Higher-Order Graph Neural Networks: Possibility
and Impossibility Results

Behrooz Tahmasebi
CSAIL, MIT
<EMAIL_ADDRESS>Derek Lim
CSAIL, MIT
<EMAIL_ADDRESS>Stefanie Jegelka
CSAIL, MIT
<EMAIL_ADDRESS>
###### Abstract

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

##  1 Introduction

Graph Neural Networks (GNNs) are powerful tools for graph representation
learning [1, 2, 3], and have been successfully applied to molecule property
prediction, simulating physics, social network analysis, knowledge graphs,
traffic prediction and many other domains [4, 5, 6, 7]. The perhaps most
widely used class of GNNs, Message Passing Graph Neural Networks (MPNNs) [8,
2, 3, 9, 1], 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 [9, 10],
so they cannot distinguish regular graphs, for instance. Likewise, they cannot
count any induced subgraph with at least three vertices [11], or learn
structural graph parameters such as clique information, diameter, conjoint or
shortest cycle [12]. Yet, in applications like computational chemistry,
materials design or pharmacy [13, 14, 7], the functions we aim to learn often
depend on the presence or count of specific substructures, e.g., functional
groups.

The limitations of MPNNs result from their inability to distinguish individual
nodes. To resolve this issue, two routes have been studied: (1) using unique
node identifiers [15, 16, 17], and (2) higher-order GNNs that act on
$k$-tuples of nodes. Node IDs, if available, enable Turing completeness for
sufficiently large MPNNs [15]. Higher-order networks use an encoding of
$k$-tuples and then apply message passing [10], or equivariant tensor
operations [18].

The expressive power of MPNNs is often measured in terms of a hierarchy of
graph isomorphism tests, specifically the $k$-Weisfeiler-Leman ($k$-WL)
hierarchy. The $k$-order models in [18] and [19] are equivalent to the $k$-WL
and ($k+1$)-WL “tests”, respectively, and are universal for the corresponding
function classes [20, 21, 22]. Yet, these models are computationally
expensive, operating on $\Theta(n^{k})$ tuples and according to current upper
bounds requiring up to $O(n^{k})$ iterations [23]. The necessary tradeoffs
between expressive power and computational complexity are still an open
question. However, for specific classes of tasks this full universality may
not be needed. Here, we study such an example of practical interest: counting
substructures, as proposed in [11]. In particular, we study if it is possible
to count given substructures with a GNN whose complexity is between that of
MPNNs and existing higher-order GNNs.

To this end, we study a generic scheme followed by many GNN architectures,
including MPNNs and higher-order GNNs [10, 11]: select a collection of
subgraphs of the input graph, encode these, and apply an aggregation function
on this collection. First, we study the power of pooling _by itself_ , as a
multi-set function over node features. We prove that $k$ _recursive_
applications on each node’s neighborhood allow to count any substructure of
size $k$. This is in contrast to _iterative_ MPNNs. We call this technique
_Recursive neighborhood pooling (RNP)_. While subgraph pooling relates to the
graph reconstruction conjecture, our strategy has important differences. In
particular, we show how the aggregation “augments” local encodings, if they
play together and the subgraphs are selected appropriately, and this reasoning
may be of interest for the design of other, even partially, expressive
architectures. Moreover, our results show that the complexity is _adjustable_
to the counting task of interest and the sparsity of the graph.

The strategy of pooling subgraph encodings has previously been used for
counting in Local Relational Pooling (LRP) [11]. LRP relies on an isomorphic
encoding of subgraphs, which is expensive – e.g., the relational pooling it
uses requires $O(k!)$ time for a subgraph of size $k$. Other higher-order GNNs
would be expensive, too, as high orders are needed for complete isomorphism
power. A major difference to our RNP is that our recursion uses subgraphs of
_varying_ sizes and structures, many of them much smaller – adapted to the
graph structure and specific counting task.

Furthermore, we study lower bounds on GNNs that count motifs. We show an
information-theoretic lower bound on the number of subgraphs to encode, as a
function of an encoding complexity. We also transfer computational lower
bounds that apply to any counting GNN. The lower bounds show that the
recursive pooling is close to tight.

In short, in this paper, we make the following contributions:

  * •

We study the power of pooling encodings of subgraphs, and show that pooling,
as an injective multi-set function, is sufficient _by itself_ for counting
when applied _recursively_ on appropriate subgraphs, remarkably without
relying on other encoding techniques or node IDs. This is different from any
other strategy we are aware of in the literature.

  * •

We analyze the complexity of recursive pooling, as a function of the task and
input graph.

  * •

We provide complexity lower bounds for pooling and general GNN architectures
that count motifs. For instance, we show a lower bound on the number of
subgraphs that need to be encoded.

##  2 Background

#### Message Passing Graph Neural Networks.

Let $G=(\mathcal{V},\mathcal{E},X)$ be an attributed graph with
$|\mathcal{V}|=n$ nodes. Here, $X_{v}\in\mathcal{X}$ denotes the initial
attribute of $v\in\mathcal{V}$, where $\mathcal{X}\subseteq\mathbb{N}$ is a
(countable) domain.

A typical Message Passing Graph Neural Network (MPNN) first computes a
representation of each node, and then aggregates the node representations via
a readout function into a representation of the entire graph $G$. The
representation $h^{(i)}_{v}$ of each node $v\in\mathcal{V}$ is computed
iteratively by aggregating the representations $h^{(i-1)}_{u}$ of the
neighboring vertices $u$:

$\displaystyle m_{v}^{(i)}$
$\displaystyle=\textsc{Aggregate}^{(i)}\Big{(}\\{\\!\\!\\{h_{u}^{(i-1)}:u\in\mathcal{N}(v)\\}\\!\\!\\}\Big{)},\quad
h_{v}^{(i)}=\textsc{Combine}^{(i)}\Big{(}h_{v}^{(i-1)},m_{v}^{(i)}\Big{)},$
(1)

for any $v\in\mathcal{V}$, for $k$ iterations, and with $h_{v}^{(0)}=X_{v}$.
The Aggregate/Combine functions are parametrized, and
$\\{\\!\\!\\{.\\}\\!\\!\\}$ denotes a multi-set, i.e., a set with (possibly)
repeating elements. A graph-level representation can be computed as
$h_{G}=\textsc{Readout}\big{(}\\{\\!\\!\\{h_{v}^{(k)}:v\in\mathcal{V}\\}\\!\\!\\}\big{)}$,
where Readout is a learnable aggregation function. For representational power,
it is important that the learnable functions are injective [9].

#### Higher-Order GNNs.

To increase the representational power of GNNs, several higher-order GNNs have
been proposed. In _$k$ -GNN_, message passing is applied to $k-$tuples of
nodes, inspired by $k$-WL [10]. At initialization, each $k$-tuple is labeled
such that 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 applies (linear) equivariant operations, interleaved with
coordinate-wise nonlinearities, to order-$k$ tensors consisting of the
adjacency matrix and input node attributes [18, 19, 21]. These GNNs are at
least as powerful as $k-$GNNs, and hence they too can count substructures with
at most $k$ vertices. All these methods need $\Omega(n^{k})$ operations.
_Local Relational Pooling (LRP)_ [11] was designed for counting and applies
relational pooling [24, 25] on local neighborhoods, i.e., one pools over
evaluations of a permutation-sensitive function applied to all $k!$
permutations of the nodes in a $k$-size neighborhood of each node.

##  3 Other Related Works

Expressive power. Several other works have studied the expressive power of
GNNs as function approximators [20]. [26] extend universal approximation from
feedforward networks to MPNNs, using the notion of _unfolding equivalence_ ,
i.e., functions on computation trees. Indeed, graph distinction and function
approximation are closely related [27, 20, 22]. [21] and [22] show that
higher-order, tensor-based GNNs provably achieve universal approximation of
permutation-invariant functions on graphs, and [15] analyzes expressive power
under depth and width restrictions. Studying GNNs from the perspective of
local algorithms, [16] show that GNNs can approximate solutions to certain
combinatorial optimization problems.

Subgraphs and GNNs.  Having infromation about subgraphs can be quite helpful
in various graph representation algorithms [28, 29, 30, 31, 32, 33, 34, 35].
For example, for graph comparison (i.e., testing whether a given (possibly
large) subgraph exists in the given model), [36] compare the outputs of GNNs
for small subgraphs of the two graphs. To improve the expressive power of
GNNs, [37] use features that are counts of specific subgraphs of interest.
Another example is [38], where an MPNN is strengthened by learning local
context matrices around vertices. Recent works have also developed GNNs that
pass messages on ego-nets [39, 40]. With motivation from the reconstruction
conjecture, [41] process node-deleted subgraphs with individual MPNNs, and
then pool them with a DeepSets model to get a representation of the original
graph.

##  4  Recursive Neighborhood Pooling

Let $G=(\mathcal{V},\mathcal{E},X)$ be an attributed input graph with
$|\mathcal{V}|=n$ nodes, and let $h_{v}^{(0)}=X_{v}$ be the initial
representation of each node $v$. In this work, we study architectures that
first find representations of a collection of $m$ subgraphs $G_{i}$ and then
aggregate (pool) over these representations with a multi-set function, i.e.,

$\textsc{Aggregate}(\\{\\!\\!\\{\psi(G_{i}):i\in[m]\\}\\!\\!\\}),\quad[m]=\\{1,\ldots,m\\}.$
(2)

It is clear that if the $\psi$ count a subgraph structure $H$, then the entire
model can count $H$. In particular, we aim to apply this strategy to obtain
the representations $\psi$, too. To appreciate the challenges in doing so,
recall two such examples. First, MPNNs follow this pooling strategy, by
iteratively aggregating over node neighborhoods, and then aggregating all node
representations into a graph representation. However, it is known that MPNNs
can count at most star structures or edges. This is because they represent a
local computation tree, which loses structural information about node
identities and connectivity. Second, this strategy is at the heart of the
Graph Reconstruction Conjecture [42], which conjectures that a graph $G$ can
be reconstructed from its subgraphs $\\{\\!\\!\\{G_{v}=G\setminus\\{v\\}:v\in
V(G)\\}\\!\\!\\}$ (Appendix E). This, however, is unknown for general graphs.
Although the $G_{v}$ retain some structure, we lose information about their
_structural relationship_. In summary, encoding structural information is the
key question.

Figure 1: Illustration of a Recursive Neighborhood Pooling GNN (RNP-GNN) with
recursion parameters $(2,2,1)$. To compute the representation of node $v$ in
the given input graph (depicted in the top left of the figure), we first
recurse on $G(\mathcal{N}_{2}(v)\setminus\\{v\\})$ (top right of figure). To
do so, we find the representation of each node $u\in
G(\mathcal{N}_{2}(v)\setminus\\{v\\})$. For instance, to compute the
representation of $u_{1}$, we apply an RNP-GNN with recursion parameters
$(2,1)$ and aggregate
$G((\mathcal{N}_{2}(v)\setminus\\{v\\})\cap(\mathcal{N}_{2}(u_{1})\setminus\\{u_{1}\\}))$,
which is shown in the bottom left of the figure. To do so, we recursively
apply an RNP-GNN with recursion parameter $(1)$ on
$G((\mathcal{N}_{2}(v)\setminus\\{v\\})\cap(\mathcal{N}_{2}(u_{1})\setminus\\{u_{1}\\})\cap(\mathcal{N}_{1}(u_{11})\setminus\\{u_{11}\\}))$,
in the bottom right of the figure.

Hence, to represent the counting function $\psi$ over potentially large
neighborhoods, an MPNN does not suffice. But, aggregation over input node
attributes, along with edge information, can count edge types, i.e., tiny
subgraphs. Hence, we _recursively_ apply aggregation on smaller sub-
neighborhoods while remembering structural information, with node-wise
aggregation as the base case. For intuition, suppose we aim to count the
occurrence of subgraph $H$ in the $r_{1}$-neighborhood
$\mathcal{N}_{r_{1}}(v)$ of a node $v$. To do so, we may count
$H_{v}=H\setminus\\{v\\}$ in the smaller graph
$\mathcal{N}_{r_{1}}(v)\setminus\\{v\\}$. But, to combine these counts with
the presence of $v$ to “complete” $H$, we must know how the $H_{v}$ are
connected to $v$ in the screened graph. Hence, to retain structure
information, we mark the neighbors of $v$. We then recursively call
neighborhood pooling to process smaller neighborhoods $\mathcal{N}_{r_{2}}(u)$
_within_ $\mathcal{N}_{r_{1}}(v)\setminus\\{v\\}$. This could, e.g., learn to
count marked versions of $H_{v}$. The radii $r$ of neighborhoods may differ in
recursive calls. In Section 5, we relate their size to $H$.

_Recursive neighborhood pooling_ $\textsc{RNP-
GNN}(G,\\{h^{\text{in}}_{u}\\}_{u\in\mathcal{V}(G)},(r_{1},\ldots,r_{\tau}))$
takes a graph with node features and a sequence of neighborhood radii for
different recursions, and returns a set of node encodings
$\\{h_{v}\\}_{v\in\mathcal{V}(G)}$. For any $v\in G$, RNP-GNN first constructs
$v$’s neighborhood, removes $v$ and marks its neighbors:

$\displaystyle G_{v}$
$\displaystyle\leftarrow\mathcal{N}_{r_{1}}(v)\setminus\\{v\\},\quad\quad
h^{\text{in}}_{u,\text{aug}}=(h^{\text{in}}_{u},\mathds{1}[(u,v)\in\mathcal{E}(G_{v})]).$
(3)

Then we aggregate over subgraph representations. If $\tau=1$ (base case), we
use the input features:

$h_{v}\leftarrow\textsc{Aggregate}^{(\tau)}(h^{\text{in}}_{v},\\{\\!\\!\\{h^{\text{in}}_{u,\text{aug}}:u\in
G_{v}\\}\\!\\!\\}).$ (4)

If $\tau>1$, we recursively represent neighborhoods of nodes in $G_{v}$:

$\displaystyle\\{\hat{h}_{v,u}\\}_{u\in G^{\prime}}$
$\displaystyle\leftarrow\textsc{RNP-
GNN}\big{(}G_{v},\\{h^{\text{in}}_{u,\text{aug}}\\}_{u\in
G_{v}},(r_{2},r_{3},\ldots,r_{\tau})\big{)}$ (5) $\displaystyle h_{v}$
$\displaystyle\leftarrow\textsc{Aggregate}^{(\tau)}\Big{(}h_{v}^{\text{in}},\\{\\!\\!\\{\hat{h}_{u,v}:u\in
G_{v}\\}\\!\\!\\}\Big{)}$ (6)

For aggregation, we can use, e.g., the injective multi-set function from [9]:

$\textsc{Aggregate}^{(\tau)}\Big{(}h_{v},\\{h_{u}\\}_{u\in
G_{v}}\Big{)}=\textsc{MLP}^{(\tau)}\Big{(}(1+\epsilon)h_{v}+\sum\nolimits_{u\in
G_{v}}\hat{h}_{u}\Big{)}.$ (7)

The final readout aggregates over the final node representations of the entire
graph. Figure 1 illustrates an RNP-GNN with recursion parameters $(2,2,1)$,
and Appendix F provides pseudocode.

While MPNNs also encode a representation of a local neighborhood, the
recursive representations differ as they take into account _intersections_ of
neighborhoods. As a result, as we will see in Section 5, they retain more
structural information and are more expressive than MPNNs. Models like $k$-GNN
and LRP also compute encodings of subgraphs, and then update the resulting
representations via message passing. We can do the same with the neighborhood
representations computed by RNP-GNNs to encode more global information,
although our representation results in Section 5 hold even without that.

##  5 Expressive Power of Recursive Pooling

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

Figure 2: MPNNs cannot count substructures with three nodes or more [11]. 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 node representations as
the graph on the right.

###  5.1 Counting (Induced) Substructures

In contrast to MPNNs, which in general cannot count substructures of three
vertices or more [11], 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, potentially attributed simple graphs, where
$\mathcal{V}$ is the set of nodes in $G$. Also, for any
$\mathcal{S}\subseteq\mathcal{V}$, let $G(\mathcal{S})$ denote the subgraph of
$G$ induced by $\mathcal{S}$. The _induced subgraph count function_ is defined
as

$\displaystyle
C(G;H):=\sum\nolimits_{\mathcal{S}\subseteq\mathcal{V}}\mathds{1}\\{G(\mathcal{S})\cong
H\\},$ (8)

i.e., the number of subgraphs of $G$ isomorphic to $H$.

To relate the size of encoded neighborhoods to the substructure $H$, we will
need a notion of _covering sequences_ for graphs.

######  Definition 2.

Let $H=(\mathcal{V}_{H},\mathcal{E}_{H})$ be a simple connected graph. For any
$\mathcal{S}\subseteq\mathcal{V}_{H}$ and $v\in\mathcal{V}_{H}$, define the
covering distance of $v$ from $\mathcal{S}$ as

$\displaystyle\bar{d}_{H}(v;\mathcal{S}):=\max_{u\in\mathcal{S}}d(u,v),$ (9)

where $d(.,.)$ is the shortest-path distance in $H$.

######  Definition 3.

Let $H$ be a simple connected graph on $\tau+1$ vertices. A permutation of
vertices, such as $(v_{1},v_{2},\ldots,v_{\tau+1})$, is called a _vertex
covering sequence_ with respect to a sequence
$\mathbf{r}=(r_{1},r_{2},\ldots,r_{\tau})\in\mathbb{N}^{\tau}$ called a
_covering sequence_ if and only if

$\displaystyle\bar{d}_{H^{\prime}_{i}}(v_{i};\mathcal{S}_{i})\leq r_{i},$ (10)

for any $i\in[\tau+1]=\\{1,2,\ldots,\tau+1\\}$, where
$\mathcal{S}_{i}=\\{v_{i},v_{i+1}\ldots,v_{\tau+1}\\}$ and
$H^{\prime}_{i}=H(\mathcal{S}_{i})$ is the subgraph of $H$ induced by the set
of vertices $\mathcal{S}_{i}$. We also say that $H$ _admits_ the covering
sequence $\mathbf{r}=(r_{1},r_{2},\ldots,r_{\tau})\in\mathbb{N}^{\tau}$ if
there is a vertex covering sequence for $H$ with respect to $\mathbf{r}$.

In particular, in a covering sequence we first consider the whole graph as a
local neighborhood of one of its nodes with radius $r_{1}$. Then, we remove
that node 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 $\mathbb{r}$ is a covering sequence for
$H$, then any $\mathbb{r^{\prime}}\geq\mathbb{r}$ (coordinate-wise) is also a
covering sequence for $H$.

Note that any connected graph on $k$ nodes admits at least one covering
sequence, which is $(k-1,k-2,\ldots,1)$. To observe this fact, note that in a
connected graph, there is at least one node that can be removed and the
remaining graph still remains connected. Therefore, we may take this node as
the first element of 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 $r_{1}$, since the complexity of the resulting RNP-GNN depends on
$r_{1}$.

More generally, if $H_{1}$ and $H_{2}$ are (possibly attributed) simple graphs
on $k$ nodes and $H_{1}\Subset H_{2}$, i.e., $H_{1}$ is a subgraph of $H_{2}$
(not necessarily induced subgraph), then it follows from the definition that
any covering sequence for $H_{1}$ is also a covering sequence for $H_{2}$. As
a side remark, as illustrated in Figure 4, covering sequences need not always
to be decreasing.

Figure 3: Example of a covering sequence computed for the graph on the left.
For this graph, $(v_{6},v_{1},v_{4},v_{5},v_{3},v_{2})$ is a vertex covering
sequence with respect to the covering sequence $(3,3,3,2,1)$. The first two
computations to obtain this covering sequence are depicted in the middle and
on the right.

Using covering sequences, we can show the following result.

######  Theorem 1.

Consider a set of (possibly attributed) graphs $\mathcal{H}$ on $\tau+1$
vertices, such that any $H\in\mathcal{H}$ admits the covering sequence
$(r_{1},r_{2},\ldots,r_{\tau})$. Then, there is an RNP-GNN $f(\cdot;\theta)$
with recursion parameters $(r_{1},r_{2},\ldots,r_{\tau})$ that can count any
$H\in\mathcal{H}$. In other words, for any $H\in\mathcal{H}$, if
$C(G_{1};H)\neq C(G_{2};H)$, then $f(G_{1};\theta)\neq f(G_{2};\theta)$. The
same result also holds for the non-induced subgraph count function.

Theorem 1 states that, with appropriate recursion parameters, any set of
(possibly attributed) substructures can be counted by an RNP-GNN.
Interestingly, induced and non-induced subgraphs can be both counted in RNP-
GNNs111For simplicity, we assume that $\mathcal{H}$ only contains $\tau+1$
node graphs. If $\mathcal{H}$ includes graphs with strictly less than $\tau+1$
vertices, we can simply append a sufficient number of zeros to their covering
sequences.. We prove Theorem 1 in Appendix A.2. The main idea is to show that
we can implement the intuition for recursive pooling outlined in Section 4
formally with the proposed architecture and multiset functions.

The theorem holds for any covering sequence that is valid for all graphs in
$\mathcal{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 in $\mathcal{H}$ is the
coordinate-wise maximum of all these sequences.

For large substructures, the sequence $(r_{1},r_{2},\ldots,r_{\tau})$ 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_{i}=O(1)$ for all $i$), raising
the hope to count these structures efficiently. In particular, $r_{1}$ is an
important parameter. In Section 5.3, we analyze the complexity of RNP-GNNs in
more detail.

###  5.2 A Universal Approximation Result for Local Functions

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 represent any function related to local
neighborhoods or small subgraphs in a graph.

First, we recall that for a graph $G$, $G(\mathcal{S})$ denotes the subgraph
of $G$ induced by the set of vertices $\mathcal{S}$.

######  Definition 4.

A function $\ell:\mathbb{G}_{n}\to\mathbb{R}^{d}$ is called an $r-$local graph
function if

$\displaystyle\ell(G)=\phi(\\{\\!\\!\\{\psi(G(S)):\mathcal{S}\subseteq\mathcal{V},|\mathcal{S}|\leq
r\\}\\!\\!\\}),$ (11)

where $\psi:\mathbb{G}_{r}\to\mathbb{R}^{d^{\prime}}$ is a function on graphs
and $\phi$ is a multi-set function.

In other words, a local function only depends on small substructures.

######  Theorem 2.

For any $r-$local graph function $\ell(.)$, there exists an RNP-GNN
$f(.;\theta)$ with recursion parameters $(r-1,r-2,\ldots,1)$ such that
$f(G;\theta)=\ell(G)$ for any $G\in\mathbb{G}_{n}$.

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 $\psi(.)$ 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 ($r_{1}=r-1$) and injective
aggregations in the RNP-GNN network. For universal approximation, we may also
need high dimensions if fully connected layers are used for aggregation (see
the proof in Appendix B for more details).

As a remark, for $r=n$, achieving universal approximation on graphs implies
solving the graph isomorphism problem. But, in this extreme case, the
computational complexity of RNP is in general not polynomial in $n$.

###  5.3 Computational Complexity

Figure 4: For the above graph, $(v_{1},v_{2},\ldots,v_{6})$ is a vertex
covering sequence. The corresponding covering sequence $(1,4,3,2,1)$ is not
decreasing.

The computational complexity of RNP-GNNs is graph-dependent. For instance, we
need to compute the set of local neighborhoods, which is cheaper for sparse
graphs. Moreover, in the recursions, we use intersections of neighborhoods
which become smaller and sparser.

######  Theorem 3.

Let $f(.;\theta):\mathbb{G}_{n}\to\mathbb{R}^{d}$ be an RNP-GNN with recursion
parameters $(r_{1},r_{2},\ldots,r_{\tau})$. Assume that the observed graphs
$G_{1},G_{2},\ldots$, whose representations we compute, satisfy the following
property: $\max_{v\in[n]}|\mathcal{N}_{r_{1}}(v)|\leq c,$ for a constant $c$.
Then the number of node updates in the RNP-GNN is $O(nc^{\tau})$.

In other words, if $c=n^{o(1)}$ and $\tau=O(1)$, then RNP-GNN requires
relatively few updates (that is, $n^{1+o(1)}$). If the maximum degree of the
given graphs is $\Delta$, then $c=O(r_{1}\Delta^{r_{1}})$. Therefore,
similarly, if $\Delta=n^{o(1)}$ then we can count with at most $n^{1+o(1)}$
updates. Additional gains may arise from rapidly shrinking neighborhoods,
which are not yet accounted for in Theorem 3. To put this in context, the
higher-order GNNs based on tensors or $k$-WL would operate on tensors of order
$n^{\tau+1}$.

Table 1: Time complexity of various models. $\Delta$ is the max-degree, and
’$-$’ means the complexity is not polynomial in $n$.

Model | worst-case | $\Delta=n^{o(1)}$ | $\Delta=O(\log(n))$ | $\Delta=O(1)$
---|---|---|---|---
LRP | $-$ | $-$ | $-$ | $O(n)$
$k-$WL | $n^{k}$ | $n^{k}$ | $n^{k}$ | $n^{k}$
RNP | $n^{k}$ | $n^{1+o(1)}$ | $\tilde{O}(n)$ | $O(n)$

The above results show that when using RNP-GNNs with sparse graphs, we can
represent functions of substructures with $k$ nodes without requiring
$k-$order tensors. LRPs also encode neighborhoods of distance $r_{1}$ 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 $r_{1}$ in the graph.

Moreover, Theorem 3 suggests to aim for small $r_{1}$. The other $r_{i}$’s may
be larger than $r_{1}$, as shown in Figure 4, but do not affect the upper
bound on the complexity.

##  6 An Information-Theoretic Lower Bound

In this section, we provide a general information-theoretic lower bound for
graph representations that encode a given graph $G$ by first encoding a number
of (possibly small) graphs $G_{1},G_{2},\ldots,G_{t}$ and then aggregating the
resulting representations. The sequence of graphs $G_{1},G_{2},\ldots,G_{t}$
may be obtained in an arbitrary way from $G$. For example, in an MPNN, $G_{i}$
can be the computation tree (rooted tree) at node $i$. As another example, in
LRP, $G_{i}$ is the local neighborhood around node $i$.

Formally, consider a graph representation
$f(.;\theta):\mathbb{G}_{n}\to\mathbb{R}^{d}$ as

$\displaystyle
f(G;\theta)=\textsc{Aggregate}(\\{\\!\\!\\{\psi(G_{i}):i\in[t]\\}\\!\\!\\}),\quad[t]=\\{1,\ldots,t\\}$
(12)

for any $G\in\mathbb{G}_{n}$, where Aggregate is a multi-set function,
$(G_{1},G_{2},\ldots,G_{t})=\Xi(G)$ where
$\Xi(.):\mathbb{G}_{n}\to\big{(}\bigcup_{m=1}^{\infty}\mathbb{G}_{m}\big{)}^{t}$
is a function from one graph to $t$ graphs, and
$\psi:\bigcup_{m=1}^{\infty}\mathbb{G}_{m}\to[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(.;\theta):\mathbb{G}_{n}\to\mathbb{R}^{d}$ that is able to count any (not
necessarily induced222The theorem also holds for induced subgraphs,
with/without node attributes.) substructure with $k$ vertices. More precisely,
for any graph $H$ with $k$ vertices, there exists $f(.;\theta)$ such that if
$C(G_{1};H)\neq C(G_{2};H)$, then $f(G_{1};\theta)\neq f(G_{2};\theta)$.
Then333$\tilde{\Omega}(m)$ is $\Omega(m)$ up to poly-logarithmic factors.
$t=\tilde{\Omega}(n^{\frac{k}{s-1}})$.

In particular, for any $(s,t)-$good graph representation with $s=2$, i.e.,
binary encoding functions, we need $\tilde{\Omega}(n^{k})$ 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\leq k$, then
$t=\Theta(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.

##  7 Time Complexity Lower Bounds for Counting Subgraphs

In this section, we put our results in the context of known hardness results
for subgraph counting. In general, the subgraph isomorphism problem is known
to be NP-complete. Going further, the Exponential Time Hypothesis (ETH) is a
conjecture in complexity theory [43], and states that several NP-complete
problems cannot be solved in sub-exponential time. ETH, as a stronger version
of the $P\neq NP$ problem, is widely believed to hold. Assuming that ETH
holds, the $k-$clique detection problem requires at least $n^{\Omega(k)}$ time
[44]. This means that if a graph representation can count any subgraph $H$ of
size $k$, then computing it requires at least $n^{\Omega(k)}$ time.

######  Corollary 1.

Assuming the ETH conjecture holds, any graph representation that can count any
substructure $H$ on $k$ vertices with appropriate parametrization needs
$n^{\Omega(k)}$ time to compute.

The above bound matches the $O(n^{k})$ 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.

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
Erdös-Rényi graph, it can only be counted in $n^{\Omega(k/\log{k})}$ time
[45].

Regarding the input graph in which we count, consider two classes of sparse
graphs: _strongly sparse graphs_ have maximum degree $\Delta=O(1)$, and
_weakly sparse graphs_ have average degree $\bar{\Delta}=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(n^{k})$. 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 ([46, 47, 48]).

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.

##  8 Experiments

In this section, we validate our theoretical findings via numerical
experiments. Here, we briefly describe our experimental setup and results —
further experimental details are given in Appendix H.

Table 2: Numerical results for counting induced triangles and non-induced
$3$-stars, following the setup of [11]. We report the test MSE divided by
variance of the true counts of each substructure (lower is better). The best
three models for each task are bolded.

| Erdős-Renyi |  | Random Regular
---|---|---|---
| triangle |  $3$-star |  | triangle |  $3$-star
GCN | 6.78E-1 | 4.36E-1 |  | 1.82 | 2.63
GIN | 1.23E-1 | 1.62E-4 |  | 4.70E-1 | 3.73E-4
GraphSAGE | 1.31E-1 | 2.40E-10 |  | 3.62E-1 | 8.70E-8
sGNN | 9.25E-2 | 2.36E-3 |  | 3.92E-1 | 2.37E-2
2-IGN | 9.83E-2 | 5.40E-4 |  | 2.62E-1 | 1.19E-2
PPGN | 5.08E-8 | 4.00E-5 |  | 1.40E-6 | 8.49E-5
LRP-1-3 | 1.56E-4 | 2.17E-5 |  | 2.47E-4 | 1.88E-6
Deep LRP-1-3 | 2.81E-5 | 1.12E-5 |  | 1.30E-6 | 2.07E-6
RNP-GNN | 1.39E-5 | 1.39E-5 |  | 2.38E-6 | 1.50E-4

Table 3: Test accuracy on the EXP dataset with setup as in [17].

Model | Accuracy (%)
---|---
GCN-RNI | 98.0 $\pm$ 1.85
PPGN | 50.0
1-2-3-GCN-L | 50.0
3-GCN | 99.7 $\pm$ 0.004
RNP-GNN $(r_{1}=1)$ | 50.0
RNP-GNN $(r_{1}=2)$ | 99.8 $\pm$ 0.005

Counting substructures. First, we follow the experimental setup of [11] on
tasks for counting substructures. In Table 3, we report results for learning
the induced subgraph count of triangles and non-induced subgraph count of
$3$-stars. Our RNP-GNN model is consistently within the best performing models
for these counting tasks, thus validating our theoretical results. Based on
the baseline results taken from [11], RNP-GNN tends to widely outperform MPNNs
(GCN [2], GIN [9], GraphSAGE [3]), and other models not tailored for counting:
spectral GNN [49], and 2-IGN [18]. Also, RNP-GNN often beats higher-order
GNNs: PPGN [19] and LRP-1-3 [11]. RNP-GNN is mostly comparable to Deep
LRP-1-3, though Deep LRP-1-3 outperforms it in a few cases. Recall that Deep
LRP-1-3 is a practical version of LRP — we leave further developments of
practical variants of RNP-GNN to future work.

Satisfiability of propositional formulas. Second, we test the expressiveness
of our model in distinguishing non-isomorphic graphs that 1-WL cannot
distinguish. The EXP dataset [17] for classifying whether certain
propositional formulas are satisfiable requires higher than 1-WL expressive
power to achieve better than random accuracy. As shown in Table 3, while our
RNP-GNN with $r_{1}=1$ is unable to achieve better than random accuracy, our
RNP-GNN with $r_{1}=2$ achieves near perfect accuracy — beating all other
models based on results taken from [17]. These other models include universal
models with random node identifiers (GCN-RNI [17]), GNNs with 3-WL power (PPGN
[19]), and GNNs that imitate some (possibly weaker) version of 3-WL
(1-2-3-GCN-L [10], 3-GCN [17]). Thus, our architecture, which is not developed
within common frameworks for achieving $k$-WL expressiveness, is in fact
powerful at distinguishing non-isomorphic graphs.

##  9 Conclusion

In this paper, we studied the theoretical possibility of counting
substructures (induced subgraphs) by a graph neural network that pools
encodings of graphs derived from the input graph. In particular, we show that
_recursive_ pooling can achieve counting power without additional
representation techniques via other architectures. This approach is different
from previous works, and the insights for how it captures structural
information — neighborhood intersections and marking — is potentially of more
general interest for designing future architectures. Our second set of results
establishes general lower bounds on the complexity of GNNs that can count
substructures of a given size, and puts the positive results in context.

## References

  * [1] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Transactions on Neural Networks, vol. 20, no. 1, pp. 61–80, 2008.
  * [2] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in International Conference on Learning Representations, 2017.
  * [3] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Advances in neural information processing systems, pp. 1024–1034, 2017.
  * [4] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” in Advances in neural information processing systems, pp. 2224–2232, 2015.
  * [5] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in Advances in neural information processing systems, pp. 3844–3852, 2016.
  * [6] P. Battaglia, R. Pascanu, M. Lai, D. J. Rezende, et al., “Interaction networks for learning about objects, relations and physics,” in Advances in neural information processing systems, pp. 4502–4510, 2016.
  * [7] W. Jin, K. Yang, R. Barzilay, and T. Jaakkola, “Learning multimodal graph-to-graph translation for molecule optimization,” in International Conference on Learning Representations, 2018.
  * [8] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 1263–1272, 2017\.
  * [9] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?,” in International Conference on Learning Representations, 2019\.
  * [10] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, “Weisfeiler and leman go neural: Higher-order graph neural networks.,” in AAAI, 2019.
  * [11] Z. Chen, L. Chen, S. Villar, and J. Bruna, “Can graph neural networks count substructures?,” arXiv preprint arXiv:2002.04025, 2020.
  * [12] V. Garg, S. Jegelka, and T. Jaakkola, “Generalization and representational limits of graph neural networks,” in Int. Conference on Machine Learning (ICML), pp. 5204–5215, 2020.
  * [13] D. C. Elton, Z. Boukouvalas, M. D. Fuge, and P. W. Chung, “Deep learning for molecular design a review of the state of the art,” Molecular Systems Design and Engineering, vol. 4, no. 4, pp. 828–849, 2019.
  * [14] M. Sun, S. Zhao, C. Gilvary, O. Elemento, J. Zhou, and F. Wang, “Graph convolutional networks for computational drug development and discovery,” Briefings in bioinformatics, vol. 21, no. 3, pp. 919–935, 2020.
  * [15] A. Loukas, “What graph neural networks cannot learn: depth vs width,” in International Conference on Learning Representations, 2019.
  * [16] R. Sato, M. Yamada, and H. Kashima, “Approximation ratios of graph neural networks for combinatorial problems,” in Advances in Neural Information Processing Systems, pp. 4081–4090, 2019.
  * [17] R. Abboud, A. A. Ceylan, M. Grohe, and T. Lukasiewicz, “The surprising power of graph neural networks with random node initialization,” in Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 2112–2118, 8 2021.
  * [18] H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman, “Invariant and equivariant graph networks,” in International Conference on Learning Representations, 2018.
  * [19] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman, “Provably powerful graph networks,” in Advances in Neural Information Processing Systems (NeurIPS), pp. 2156–2167, 2019.
  * [20] W. Azizian and M. Lelarge, “Characterizing the expressive power of invariant and equivariant graph neural networks,” arXiv preprint arXiv:2006.15646, 2020.
  * [21] H. Maron, E. Fetaya, N. Segol, and Y. Lipman, “On the universality of invariant networks,” in International Conference on Machine Learning, pp. 4363–4371, 2019.
  * [22] N. Keriven and G. Peyré, “Universal invariant and equivariant graph neural networks,” in Advances in Neural Information Processing Systems (NeurIPS), pp. 7092–7101, 2019.
  * [23] S. Kiefer and B. D. McKay, “The iteration number of colour refinement,” in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [24] R. Murphy, B. Srinivasan, V. Rao, and B. Riberio, “Relational pooling for graph representations,” in International Conference on Machine Learning (ICML 2019), 2019.
  * [25] 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 Representations, 2019.
  * [26] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “Computational capabilities of graph neural networks,” IEEE Transactions on Neural Networks, vol. 20, no. 1, pp. 81–102, 2009.
  * [27] Z. Chen, S. Villar, L. Chen, and J. Bruna, “On the equivalence between graph isomorphism testing and function approximation with gnns,” in Advances in Neural Information Processing Systems, pp. 15894–15902, 2019.
  * [28] S. Liu, M. F. Demirel, and Y. Liang, “N-gram graph: Simple unsupervised representation for graphs, with applications to molecules,” in Advances in Neural Information Processing Systems, pp. 8466–8478, 2019.
  * [29] F. Monti, K. Otness, and M. M. Bronstein, “Motifnet: a motif-based graph convolutional network for directed graphs,” in 2018 IEEE Data Science Workshop (DSW), pp. 225–228, IEEE, 2018.
  * [30] X. Liu, H. Pan, M. He, Y. Song, X. Jiang, and L. Shang, “Neural subgraph isomorphism counting,” in Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1959–1969, 2020.
  * [31] Y. Yu, K. Huang, C. Zhang, L. M. Glass, J. Sun, and C. Xiao, “Sumgnn: Multi-typed drug interaction prediction via efficient knowledge graph summarization,” arXiv preprint arXiv:2010.01450, 2020.
  * [32] C. Meng, S. C. Mouli, B. Ribeiro, and J. Neville, “Subgraph pattern neural networks for high-order graph evolution prediction.,” in AAAI, pp. 3778–3787, 2018.
  * [33] L. Cotta, C. H. C. Teixeira, A. Swami, and B. Ribeiro, “Unsupervised joint $k$-node graph representations with compositional energy-based models,” arXiv preprint arXiv:2010.04259, 2020.
  * [34] E. Alsentzer, S. Finlayson, M. Li, and M. Zitnik, “Subgraph neural networks,” Advances in Neural Information Processing Systems, vol. 33, 2020.
  * [35] K. Huang and M. Zitnik, “Graph meta learning via local subgraphs,” arXiv preprint arXiv:2006.07889, 2020.
  * [36] R. Ying, Z. Lou, J. You, C. Wen, A. Canedo, and J. Leskovec, “Neural subgraph matching,” arXiv preprint arXiv:2007.03092, 2020.
  * [37] G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein, “Improving graph neural network expressivity via subgraph isomorphism counting,” arXiv preprint arXiv:2006.09252, 2020.
  * [38] C. Vignac, A. Loukas, and P. Frossard, “Building powerful and equivariant graph neural networks with message-passing,” arXiv preprint arXiv:2006.15107, 2020.
  * [39] J. You, J. M. Gomes-Selman, R. Ying, and J. Leskovec, “Identity-aware graph neural networks,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 10737–10745, 2021.
  * [40] D. Sandfelder, P. Vijayan, and W. L. Hamilton, “Ego-gnns: Exploiting ego structures in graph neural networks,” in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8523–8527, IEEE, 2021.
  * [41] L. Cotta, C. Morris, and B. Ribeiro, “Reconstruction for powerful graph representations,” 2021.
  * [42] P. Kelly et al., “A congruence theorem for trees.,” Pacific Journal of Mathematics, vol. 7, no. 1, pp. 961–968, 1957.
  * [43] R. Impagliazzo and R. Paturi, “On the complexity of k-sat,” Journal of Computer and System Sciences, vol. 62, no. 2, pp. 367–375, 2001.
  * [44] J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, I. A. Kanj, and G. Xia, “Tight lower bounds for certain parameterized np-hard problems,” Information and Computation, vol. 201, no. 2, pp. 216–231, 2005.
  * [45] M. Dalirrooyfard, T. D. Vuong, and V. V. Williams, “Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 1167–1178, 2019.
  * [46] L. Gishboliner, Y. Levanzov, and A. Shapira, “Counting subgraphs in degenerate graphs,” arXiv preprint arXiv:2010.05998, 2020.
  * [47] S. K. Bera, N. Pashanasangi, and C. Seshadhri, “Linear time subgraph counting, graph degeneracy, and the chasm at size six,” arXiv preprint arXiv:1911.05896, 2019.
  * [48] S. K. Bera, N. Pashanasangi, and C. Seshadhri, “Near-linear time homomorphism counting in bounded degeneracy graphs: The barrier of long induced cycles,” 2020\.
  * [49] Z. Chen, L. Li, and J. Bruna, “Supervised community detection with line graph neural networks,” in International Conference on Learning Representations, 2018.
  * [50] B. D. McKay, “Small graphs are reconstructible,” Australasian Journal of Combinatorics, vol. 15, pp. 123–126, 1997.
  * [51] K. Hornik, M. Stinchcombe, H. White, et al., “Multilayer feedforward networks are universal approximators.,” Neural networks, vol. 2, no. 5, pp. 359–366, 1989.
  * [52] K. Hornik, “Approximation capabilities of multilayer feedforward networks,” Neural networks, vol. 4, no. 2, pp. 251–257, 1991.
  * [53] J. Kleinberg and E. Tardos, Algorithm design.  Pearson Education India, 2006.
  * [54] P. Erdos, A. Rényi, et al., “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17–60, 1960.
  * [55] A. Steger and N. C. Wormald, “Generating random regular graphs quickly,” Combinatorics, Probability and Computing, vol. 8, no. 4, pp. 377–396, 1999.

##  Appendix A Proof of Theorem 1

###  A.1 Preliminaries

Let us first state a few definitions about the graph functions. Note that for
any graph function $f:\mathbb{G}_{n}\to\mathbb{R}^{d}$, we have $f(G)=f(H)$
for any $G\cong H$.

######  Definition 5.

Given two graph functions $f,g:\mathbb{G}_{n}\to\mathbb{R}^{d}$, we write
$f\sqsupseteq g$, if and only if for any $G_{1},G_{2}\in\mathbb{G}_{n}$,

$\displaystyle\forall G_{1},G_{2}\in G_{n}:g(G_{1})\neq g(G_{2})\implies
f(G_{1})\neq f(G_{2}),$ (13)

or, equivalently,

$\displaystyle\forall G_{1},G_{2}\in G_{n}:f(G_{1})=f(G_{2})\implies
g(G_{1})=g(G_{2}).$ (14)

######  Proposition 1.

Consider graph functions $f,g,h:\mathbb{G}_{n}\to\mathbb{R}^{d}$ such that
$f\sqsupseteq g$ and $g\sqsupseteq h$. Then, $f\sqsupseteq h$. In other words,
$\sqsupseteq$ is transitive.

###### Proof.

The proposition holds by definition. ∎

######  Proposition 2.

Consider graph functions $f,g:\mathbb{G}_{n}\to\mathbb{R}^{d}$ such that
$f\sqsupseteq g$. Then, there is a function
$\xi:\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that $\xi\circ f=g$.

###### Proof.

Let $\mathbb{G}_{n}=\sqcup_{i\in\mathbb{N}}\mathcal{F}_{i}$ be the
partitioning induced by the equality relation with respect to the function $f$
on $\mathbb{G}_{n}$. Similarly define $\mathcal{G}_{i}$, $i\in\mathbb{N}$ for
$g$. Note that due to the definition, $\\{\mathcal{F}_{i}:i\in\mathbb{N}\\}$
is a refinement for $\\{\mathcal{G}_{i}:i\in\mathbb{N}\\}$. Define $\xi$ to be
the unique mapping from $\\{\mathcal{F}_{i}:i\in\mathbb{N}\\}$ to
$\\{\mathcal{G}_{i}:i\in\mathbb{N}\\}$ which respects the equality relation.
One can observe that such $\xi$ 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
$\mathbb{r}=(r_{1},r_{2},\ldots,r_{\tau})$ where $f$ is maximally expressive.
Then, $f\sqsupseteq g$.

###### Proof.

The proposition holds by definition. ∎

######  Proposition 4.

Consider a sequence of graph functions $f,g_{1},\ldots,g_{k}$. If
$f\sqsupseteq g_{i}$ for all $i\in[k]$, then

$\displaystyle f\sqsupseteq\sum_{i=1}^{k}c_{i}g_{i},$ (15)

for any $c_{i}\in\mathbb{R}$, $i\in\mathbb{N}$.

###### Proof.

Since $f\sqsupseteq g_{i}$, we have

$\displaystyle\forall G_{1},G_{2}\in G_{n}:f(G_{1})=f(G_{2})\implies
g_{i}(G_{1})=g_{i}(G_{2}),$ (16)

for all $i\in[k]$. This means that for any $G_{1},G_{2}\in\mathbb{G}_{n}$ if
$f(G_{1})=f(G_{2})$ then $g_{i}(G_{1})=g_{i}(G_{2})$, $i\in[k]$, and
consequently
$\sum_{i=1}^{k}c_{i}g_{i}(G_{1})=\sum_{i=1}^{k}c_{i}g_{i}(G_{2})$. Therefore,
from the definition we conclude $f\sqsupseteq\sum_{i=1}^{k}c_{i}g_{i}$. Note
that the same proof also holds in the case of countable summations as long as
the summation is bounded. ∎

######  Definition 7.

Let $H=(\mathcal{V}_{H},\mathcal{E}_{H},X^{H})$ be a attributed connected
simple graph with $k$ nodes. For any attributed graph
$G=(\mathcal{V}_{G},\mathcal{E}_{G},X^{G})\in\mathbb{G}_{n}$, the induced
subgraph count function $C(G;H)$ is defined as

$\displaystyle C(G;H):=\sum_{\mathcal{S}\subseteq[n]}\mathds{1}\\{G(S)\cong
H\\}.$ (17)

Also, let $\bar{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

$\displaystyle\bar{C}(G;H):=\sum_{\mathcal{S}\subseteq[n]\atop|\mathcal{S}|=k}\bar{C}(G(\mathcal{S});H).$
(18)

Otherwise, $n=k$, and we define

$\displaystyle\bar{C}(G;H):=\sum_{\tilde{H}\in\tilde{\mathcal{H}}(H)}c_{\tilde{H},H}\times\mathds{1}\\{G\cong\tilde{H}\\},$
(19)

where

$\displaystyle\tilde{\mathcal{H}}(H):=\\{\tilde{H}\in\mathbb{G}_{k}:\tilde{H}\Supset
H\big{\\}},$ (20)

is defined with respect to the graph isomorphism, and
$c_{\tilde{H},H}\in\mathbb{N}$ denotes the number of subgraphs in $H$
identical to $\tilde{H}$. Note that $\tilde{\mathcal{H}}(H)$ is a finite set
and $\Supset$ denotes being a (not necessarily induced) subgraph.

######  Proposition 5.

Let $\mathcal{H}$ be a family of graphs. If for any $H\in\mathcal{H}$, there
is an RNP-GNN $f_{H}(.;\theta)$ with recursion parameters
$(r_{1},r_{2},\ldots,r_{\tau})$ such that $f_{H}\sqsupseteq C(G;H)$, then
there exists an RNP-GNN $f(.;\theta)$ with recursion parameters
$(r_{1},r_{2},\ldots,r_{\tau})$ such that
$f\sqsupseteq\sum_{H\in\mathcal{H}}C(G;H)$.

###### Proof.

Let $f(.;\theta)$ be a maximally expressive RNP-GNN. Note that by the
definition $f\sqsupseteq f_{H}$ for any $H\in\mathcal{H}$. Since $\sqsupseteq$
is transitive, $f\sqsupseteq C(G;H)$ for all $H\in\mathcal{H}$, and using
Proposition 4, we conclude that $f\sqsupseteq\sum_{H\in\mathcal{H}}C(G;H)$. ∎

The following proposition shows that there is no difference between counting
induced attributed graphs and counting induced unattributed graphs in RNP-
GNNs.

######  Proposition 6.

Let $H_{0}$ be an unattributed connected graph. Assume that for any attributed
graph $H$, which is constructed by adding arbitrary attributes to $H_{0}$,
there exists an RNP-GNN $f_{H}(.;\theta_{H})$ such that $f_{H}\sqsupseteq
C(G;H)$, then for its unattributed counterpart $H_{0}$, there exists an RNP-
GNN $f(.;\theta)$ with the same recursion parameters as $f_{H}(.;\theta_{H})$
such that $f\sqsupseteq C(G;H_{0})$.

###### Proof.

If there exists an RNP-GNN $f_{H}(.;\theta_{H})$ such that $f_{H}\sqsupseteq
C(G;H)$, then for a maximally expressive RNP-GNN $f(.;\theta)$ with the same
recursion parameters as $f_{H}$ we also have $f\sqsupseteq C(G;H)$. Let
$\mathcal{H}$ be the set of all attributed graphs
$H=(\mathcal{V},\mathcal{E},X)\in\mathbb{G}_{k}$ up to graph isomorphism,
where $X\in\mathcal{X}^{k}$ for a countable set $\mathcal{X}$. Note that
$\mathcal{H}=\\{H_{1},H_{2},\ldots\\}$ is a countable set. Now we write

$\displaystyle C(G;H_{0})$
$\displaystyle=\sum_{\mathcal{S}\subseteq[n]\atop|\mathcal{S}|=k}\mathds{1}\\{G(S)\cong
H_{0}\\}$ (21)
$\displaystyle=\sum_{\mathcal{S}\subseteq[n]\atop|\mathcal{S}|=k}\sum_{i\in\mathbb{N}}\mathds{1}\\{G(S)\cong
H_{i}\\}$ (22)
$\displaystyle=\sum_{i\in\mathbb{N}}\sum_{\mathcal{S}\subseteq[n]\atop|\mathcal{S}|=k}\mathds{1}\\{G(S)\cong
H_{i}\\}$ (23) $\displaystyle=\sum_{i\in\mathbb{N}}C(G;H_{i}).$ (24)

Now using Proposition 4 we conclude that $f\sqsupseteq C(G;H_{0})$ since
$C(G;H_{0})$ is always finite. ∎

######  Definition 8.

Let $H$ be a (possibly attributed) simple connected graph. For any
$\mathcal{S}\subseteq\mathcal{V}_{H}$ and $v\in\mathcal{V}_{H}$, define

$\displaystyle\bar{d}_{H}(v;\mathcal{S}):=\max_{u\in\mathcal{S}}d(u,v).$ (26)

######  Definition 9.

Let $H$ be a (possibly attributed) connected simple graph with $k=\tau+1$
vertices. A permutation of vertices, such as
$(v_{1},v_{2},\ldots,v_{\tau+1})$, is called a vertex covering sequence, with
respect to a sequence
$\mathbf{r}=(r_{1},r_{2},\ldots,r_{\tau})\in\mathbb{N}^{\tau}$, called a
covering sequence, if and only if

$\displaystyle\bar{d}_{H^{\prime}_{i}}(v_{i};\mathcal{S}_{i})\leq r_{i},$ (27)

for $i\in[\tau+1]$, where $H^{\prime}_{i}=H(\mathcal{S}_{i})$ and
$\mathcal{S}_{i}=\\{v_{i},v_{i+1},\ldots,v_{\tau+1}\\}$. Let
$\mathcal{C}_{H}({\bf r})$ denote the set of all vertex covering sequences
with respect to the covering sequence $\mathbf{r}$ for $H$.

######  Proposition 7.

For any $G,H\in\mathbb{G}_{k}$, if $G\Supset H$ (non-induced subgraph), then

$\displaystyle\mathcal{C}_{H}({\bf r})\subseteq\mathcal{C}_{G}({\bf r}),$ (28)

for any sequence $\mathbb{r}$.

###### Proof.

The proposition follows from the fact that the function $\bar{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 (attributed or unattributed) graph $H$, there
exists an RNP-GNN with appropriate recursion parameters $f_{H}(.;\theta_{H})$
such that $f_{H}\sqsupseteq C(G;H)$, then we prove there exists an RNP-GNN
$f(.;\theta)$ with the same recursion parameters as $f_{H}$ such that
$f\sqsupseteq\bar{C}(G;H)$.

If there exists an RNP-GNN $f_{H}(.;\theta_{H})$ such that $f_{H}\sqsupseteq
C(G;H)$, then for a maximally expressive RNP-GNN $f(.;\theta)$ with the same
recursion parameters as $f_{H}$ we also have $f\sqsupseteq C(G;H)$. Note that

$\displaystyle\bar{C}(G,H)$
$\displaystyle=\sum_{\mathcal{S}\subseteq[n]\atop|\mathcal{S}|=k}\bar{C}(G(\mathcal{S});H)$
(29)
$\displaystyle=\sum_{\mathcal{S}\subseteq[n]\atop|\mathcal{S}|=k}\sum_{\tilde{H}\in\tilde{\mathcal{H}}(H)}c_{\tilde{H},H}\times\mathds{1}\\{G(S)\cong\tilde{H}\\}$
(30)
$\displaystyle=\sum_{\tilde{H}\in\tilde{\mathcal{H}}(H)}c_{\tilde{H},H}\sum_{\mathcal{S}\subseteq[n]\atop|\mathcal{S}|=k}\mathds{1}\\{G(S)\cong\tilde{H}\\}$
(31) $\displaystyle=\sum_{i\in\mathbb{N}}c_{H_{i},H}\times C(G,H_{i}),$ (32)

where $\tilde{\mathcal{H}}(H)=\\{H_{1},H_{2},\ldots\\}$.

######  Claim 1.

$f\sqsupseteq C(G,H_{i})$ for any $i$.

Using Proposition 4 and Claim 1 we conclude that $f\sqsupseteq\bar{C}(G;H)$
since $\bar{C}(G;H)$ is finite and $f\sqsupseteq C(G,H_{i})$ for any $i$, and
the proof is complete. The missing part which we must show here is that for
any $H_{i}$ the sequence $(r_{1},r_{2},\ldots,r_{t})$ which covers $H$ also
covers $H_{i}$. This follows from Proposition 7. We are done. ∎

At the end of this part, let us introduce an important notation. For any
attributed connected simple graph on $k$ vertices
$G=(\mathcal{V},\mathcal{E},X)$, let $G^{*}_{v}$ be the resulting induced
graph obtained after removing $v\in\mathcal{V}$ from $G$ with the new
attributes defined as

$\displaystyle X^{*}_{u}:=(X_{u},\mathds{1}\\{(u,v)\in\mathcal{E}\\}),$ (33)

for each $u\in\mathcal{V}\setminus\\{v\\}$. We may also use $X^{*v}_{u}$ for
more clarification.

###  A.2 Proof of Theorem 1

We utilize an inductive proof on $\tau$, which is the length of the covering
sequence of $H$. Equivalently, due to the definition, $\tau=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
attributed 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., $\tau=1$, $H$ is a two-node
graph. This means that we only need to count the number of a specific
(attributed) edge in the given graph $G$. Note that in this case we apply an
RNP-GNN with recursion parameter $r_{1}\geq 1$. Denote the two attributes of
the vertices in $H$ by $X^{H}_{1},X^{H}_{2}\in\mathcal{X}$. The output of an
RNP-GNN $f(.;\theta)$ is

$\displaystyle
f(G;\theta)=\phi(\\{\\!\\!\\{\psi(X^{G}_{v},\varphi(\\{\\!\\!\\{X^{*v}_{u}:u\in\mathcal{N}_{r_{1}}(v)\\}\\!\\!\\})):v\in[n]\\}\\!\\!\\}),$
(34)

where we assume that $f(.;\theta)$ is maximally expressive. The goal is to
show that $f\sqsupseteq C(G;H)$. Using the transitivity of $\sqsupseteq$, we
only need to choose appropriate $\phi,\psi,\varphi$ to achieve
$\hat{f}=C(G;H)$ as the final representation. Let

$\displaystyle\phi(\\{\\!\\!\\{z_{v}:v\in[n]\\}\\!\\!\\})$
$\displaystyle:=\frac{1}{2+2\times\mathds{1}\\{X_{1}^{H}=X_{2}^{H}\\}}\sum_{i=1}^{n}z_{i}$
(35) $\displaystyle\psi(X,(z,z^{\prime}))$
$\displaystyle:=z\times\mathds{1}\\{X=X_{1}^{H}\\}+z^{\prime}\times\mathds{1}\\{X=X_{2}^{H}\\}$
(36) $\displaystyle\varphi(\\{\\!\\!\\{z_{u}:u\in[n^{\prime}]\\}\\!\\!\\})$
$\displaystyle:=\Big{(}\sum_{i=1}^{n^{\prime}}\mathds{1}\\{z_{u}=(X^{H}_{2},1)\\},\sum_{i=1}^{n^{\prime}}\mathds{1}\\{z_{u}=(X^{H}_{1},1)\Big{)}.$
(37)

Then, a simple computation shows that

$\displaystyle\hat{f}(G;\theta)$
$\displaystyle=\phi(\\{\\!\\!\\{\psi(X^{G}_{v},\varphi(\\{\\!\\!\\{X^{*v}_{u}:u\in\mathcal{N}_{r_{1}}(v)\\}\\!\\!\\})):v\in[n]\\}\\!\\!\\}),$
(38) $\displaystyle=C(G;H).$ (39)

Since $\hat{f}(.;\theta)$ is an RNP-GNN with recursion parameter $r_{1}$ and
for any maximally expressive RNP-GNN $f(.;\theta)$ with the same recursion
parameter as $\hat{f}$ we have $f\sqsupseteq\hat{f}$ and $\hat{f}\sqsupseteq
C(G;H)$, we conclude that $f\sqsupseteq C(G;H)$ and this completes the proof.

Induction step. Assume that the desired result holds for $\tau-1$ ($\tau\geq
2$). We show that it also holds for $\tau$. Let us first define

$\displaystyle\mathcal{H}^{*}$ $\displaystyle:=\\{H^{*}_{v_{1}}:\exists
v_{2},\ldots,v_{\tau}\in[k]:(v_{1},v_{2},\ldots,v_{\tau})\in\mathcal{C}_{H}(\mathbb{r})\\}$
(40) $\displaystyle c^{*}(H^{0})$
$\displaystyle:=\mathds{1}\\{H^{0}\in\mathcal{H}^{*}\\}\times\\#\\{v\in[k]:H^{*}_{v}\cong
H^{0}\\},$ (41)

where $H^{*}_{v}$ means the induced subgraph after removing a node, with new
attributes (see A.1). Note that $\mathcal{H}^{*}\neq\emptyset$ by the
assumption. Let

$\displaystyle\|\mathcal{H}^{*}\|:=\sum_{H^{0}\in\mathcal{H}^{*}}c^{*}(H^{0}).$
(42)

For all $H^{0}\in\mathcal{H}^{*}$, using the induction hypothesis, there is a
(universal) RNP-GNN $\hat{f}(.;\hat{\theta})$ with recursion parameters
$(r_{2},r_{3},\ldots,r_{\tau})$ such that $\hat{f}\sqsupseteq C(G;H^{0})$.
Using Proposition 4 we conclude

$\displaystyle\hat{f}\sqsupseteq\sum_{u\in[k]:H^{*}_{u}\in\mathcal{H}^{*}}C(G;H^{*}_{u}).$
(43)

Define a maximally expressive RNP-GNN with the recursion parameters
$(r_{1},r_{2},\ldots,r_{\tau})$ as follows:

$\displaystyle
f(G;\theta)=\phi(\\{\\!\\!\\{\psi(X^{G}_{v},\hat{f}(G^{*}(\mathcal{N}_{r_{1}}(v));\hat{\theta})):v\in[n]\\}\\!\\!\\}).$
(44)

Similar to the proof for $\tau=1$, here we only need to propose a (not
necessarily maximally expressive) RNP-GNN which achieves the function
$C(G;H)$.

Let us define

$\displaystyle
f_{H^{*}_{u}}(G;\theta):=\phi(\\{\\!\\!\\{\psi_{H^{*}_{u}}(X^{G}_{v},\xi\circ\hat{f}(G^{*}(\mathcal{N}_{r_{1}}(v));\hat{\theta})):v\in[n]\\}\\!\\!\\}),$
(45)

where

$\displaystyle\phi(\\{\\!\\!\\{z_{v}:v\in[n]\\}\\!\\!\\})$
$\displaystyle:=\frac{1}{\|\mathcal{H}^{*}\|}\sum_{i=1}^{n}z_{i}$ (46)
$\displaystyle\psi_{H^{*}_{u}}(X,z)$
$\displaystyle:=z\times\mathds{1}\\{X=X^{H}_{u}\\},$ (47)

and $\xi\circ\hat{f}=C(G;H^{*}_{u})$. Note that the existence of such function
$\xi$ is guaranteed due to Proposition 2. Now we write

$\displaystyle\|\mathcal{H}^{*}\|\times C(G;H)$
$\displaystyle=\|\mathcal{H}^{*}\|\sum_{\mathcal{S}\subseteq[n]}\mathds{1}\\{G(S)\cong
H\\}$ (49)
$\displaystyle=\sum_{\mathcal{S}\subseteq[n]}\sum_{v\in\mathcal{S}}\mathds{1}\\{\exists
u\in[k]:(G(S\setminus\\{v\\}))^{*}_{v}\cong H^{*}_{u}\in\mathcal{H}^{*}\land
X^{G}_{v}=X^{H}_{u}\\}$ (50)
$\displaystyle=\sum_{v\in[n]}\sum_{v\in\mathcal{S}\subseteq[n]}\mathds{1}\\{\exists
u\in[k]:(G(S\setminus\\{v\\}))^{*}_{v}\cong H^{*}_{u}\in\mathcal{H}^{*}\land
X^{G}_{v}=X^{H}_{u}\\}$ (51)
$\displaystyle=\sum_{v\in[n]}\sum_{v\in\mathcal{S}\subseteq\mathcal{N}_{r_{1}}(v)}\mathds{1}\\{\exists
u\in[k]:(G(S\setminus\\{v\\}))^{*}_{v}\cong H^{*}_{u}\in\mathcal{H}^{*}\land
X^{G}_{v}=X^{H}_{u}\\}$ (52)
$\displaystyle=\sum_{v\in[n]}\sum_{v\in\mathcal{S}\subseteq\mathcal{N}_{r_{1}}(v)}\sum_{u\in[k]:H^{*}_{u}\in\mathcal{H}^{*}}\mathds{1}\\{(G(S\setminus\\{v\\}))^{*}_{v}\cong
H^{*}_{u}\\}\mathds{1}\\{X^{G}_{v}=X^{H}_{u}\\}$ (53)
$\displaystyle=\sum_{v\in[n]}\sum_{u\in[k]:H^{*}_{u}\in\mathcal{H}^{*}}C(G^{*}(\mathcal{N}_{r_{1}}(v));H^{*}_{u})\times\mathds{1}\\{X^{G}_{v}=X^{H}_{u}\\},$
(54)

which means that

$\displaystyle\sum_{u\in[k]:H^{*}_{u}\in\mathcal{H}^{*}}f_{H^{*}_{u}}(G;\theta)\sqsupseteq
C(G;H).$ (55)

However, for a maximally expressive RNP-GNN $f(.;\theta)$ we know that
$f\sqsupseteq f_{H^{*}_{u}}$ for all $H^{*}_{u}\in\mathcal{H}$ and this means
that $f\sqsupseteq C(G;H)$. The proof is thus complete.

##  Appendix B Proof of Theorem 2

For any attributed graph $H$ on $r$ nodes (not necessarily connected) we claim
that RNP-GNNs can count them.

######  Claim 2.

Let $f(.;\theta):\mathbb{G}_{n}\to\mathbb{R}^{d}$ be a maximally expressive
RNP-GNN with recursion parameters $(r-1,r-2,\ldots,1)$. Then, $f\sqsupseteq
C(G;H)$.

Now consider the function

$\displaystyle\ell(G)=\phi(\\{\\!\\!\\{\psi(G(S)):\mathcal{S}\subseteq\mathcal{V},|\mathcal{S}|\leq
r\\}\\!\\!\\}).$ (56)

We claim that $f\sqsupseteq\ell$ ($f$ is defined in the previous claim) and
this completes the proof according to Proposition 2.

To prove the claim, assume that $f(G_{1})=f(G_{2})$. Then, we conclude that
$C(G_{1};H)=C(G_{2};H)$ for any attributed $H$ (not necessarily connected)
with $r$ vertices. Now, we have

$\displaystyle\ell(G)$
$\displaystyle=\phi(\\{\\!\\!\\{\psi(G(S)):\mathcal{S}\subseteq\mathcal{V},|\mathcal{S}|\leq
r\\}\\!\\!\\})$ (57)
$\displaystyle=\phi(\\{\\!\\!\\{\psi(H):H\in\mathbb{G}_{r},\leavevmode\nobreak\
\text{the multiplicity of }\leavevmode\nobreak\ H\leavevmode\nobreak\
\text{is}\leavevmode\nobreak\ C(G;H)\\}\\!\\!\\}),$ (58)

which shows that $\ell(G_{1})=\ell(G_{2})$.

Proof of Claim 2. To prove the claim, we use an induction on the number of
connected components $c_{H}$ of graph $H$. If $H$ is connected, i.e.,
$c_{H}=1$, then according to Theorem 1, we know that $f\sqsupseteq C(G;H)$.

Now assume that the claim holds for $c_{H}=c-1\geq 1$. We show that it also
holds for $c_{H}=c$. Let $H_{1},H_{2},\ldots,H_{c}$ denote the connected
components of $H$. Also assume that $H_{i}\not\cong H_{j}$ for all $i\neq j$.
We will relax this assumption later. Let us define

$\displaystyle\mathcal{A}_{G}:=\\{(\mathcal{S}_{1},\mathcal{S}_{2},\ldots,\mathcal{S}_{c}):\forall
i\in[c]:\mathcal{S}_{i}\subseteq[n];G(\mathcal{S}_{i})\cong H_{i}\\}.$ (59)

Note that we can write

$\displaystyle|\mathcal{A}_{G}|$ $\displaystyle=\prod_{i=1}^{c}C(G;H_{i})$
(60)
$\displaystyle=C(G;H)+\sum_{j=1}^{\infty}c^{\prime}_{j}C(G;H^{\prime}_{j}),$
(61)

where $H^{\prime}_{1},H^{\prime}_{2},\ldots$ are all non-isomorphic graphs
obtained by adding edges (at least one edge) between $c$ graphs
$H_{1},H_{2},\ldots,H_{c}$, or contracting a number of vertices of them. The
constants $c^{\prime}_{j}$ are just used to remove the effect of multiple
counting due to the symmetry. Now, since for any $H_{i}$, $H^{\prime}_{j}$ the
number of connected components is strictly less that $c$, using the induction,
we have $f\sqsupseteq C(G;H_{i})$ and $f\sqsupseteq C(G;H^{\prime}_{j})$ for
all $j$ and all $i\in[c]$. According to Proposition 4, we conclude that
$f\sqsupseteq C(G;H)$ and this completes the proof. Also, if $H_{i}$,
$i\in[c]$, are not pairwise non-isomorphic, then we can use $\alpha C(G;H)$ in
above equation instead of $C(G;H)$, where $\alpha>0$ removes the effect of
multiple counting by symmetry. The proof is thus complete.

##  Appendix C Proof of Theorem 3

To prove Theorem 3, we need to bound the number of node updates required for
an RNP-GNN with recursion parameters $(r_{1},r_{2},\ldots,r_{t})$. First of
all, we have $n$ variables used for the final representations of vertices. For
each vertex $v_{1}\in\mathcal{V}$, we explore the local neighborhood
$\mathcal{N}_{r_{1}}(v_{1})$ and apply a new RNP-GNN network to that
neighborhood. In other words, for the second step we need to update
$|\mathcal{N}_{r_{1}}(v_{1})|$ nodes. Similarly, for the $i$th step of the
algorithm we have as most

$\displaystyle\lambda_{i}:=\max_{v_{1}\in[n]}\max_{v_{j+1}\in\mathcal{N}_{r_{j}}(v_{j})\atop\forall
j\in[i-1]}|\mathcal{N}_{r_{1}}(v_{1})\cap\mathcal{N}_{r_{2}}(v_{2})\cap\mathcal{N}_{r_{3}}(v_{3})\ldots\cap\mathcal{N}_{r_{i}}(v_{i})|,$
(62)

updates. Therefore, we can bound the number of node updates as

$\displaystyle n\times\prod_{i=1}^{\tau}\lambda_{i}.$ (63)

Since $\lambda_{i}$ is decreasing in $i$, we simply conclude the desired
result.

##  Appendix D Proof of Theorem 4

Let $K_{k}$ denote the complete graph on $k$ vertices.

######  Claim 3.

For any $k,n\in\mathbb{N}$, such that $n$ is sufficiently large,

$\displaystyle\Big{|}\\{C(G;K_{k}):G\in\mathbb{G}_{n}\\}\Big{|}\geq\frac{(cn/(k\log(n/k))-k)^{k}}{k!}=\tilde{\Omega}(n^{k}),$
(64)

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;K_{k})$
can take is $n^{k}$, up to poly-logarithmic factors.

To prove the theorem, we use the above claim. Consider a class of $(s,t)-$good
graph representations $f(.;\theta)$ which can count any substructure on $k$
vertices. As a result, $f\sqsupseteq C(G;K_{k})$ for an appropriate
parametrization $\theta$. By the definition, $f(.)$ must take at least
$\Big{|}\\{C(G;K_{k}):G\in\mathbb{G}_{n}\\}\Big{|}$ different values, i.e.,

$\displaystyle\Big{|}\\{f(G;\theta):G\in\mathbb{G}_{n}\\}\Big{|}\geq\Big{|}\\{C(G;K_{k}):G\in\mathbb{G}_{n}\\}\Big{|}.$
(65)

Also,

$\displaystyle\Big{|}\\{f(G;\theta):G\in\mathbb{G}_{n}\\}\Big{|}\leq\Big{|}\big{\\{}\\{\\!\\!\\{\psi(G_{i}):i\in[t]\\}\\!\\!\\}:G\in\mathbb{G}_{n}\big{\\}}\Big{|},$
(66)

where $(G_{1},G_{2},\ldots,G_{t})=\Xi(G)$. But, $\psi$ can take only $s$
values. Therefore, we have

$\displaystyle\Big{|}\\{C(G;K_{k}):G\in\mathbb{G}_{n}\\}\Big{|}$
$\displaystyle\leq\Big{|}\\{f(G;\theta):G\in\mathbb{G}_{n}\\}\Big{|}$ (67)
$\displaystyle\leq\Big{|}\big{\\{}\\{\\!\\!\\{\psi(G_{i}):i\in[t]\\}\\!\\!\\}:G\in\mathbb{G}_{n}\big{\\}}\Big{|}$
(68)
$\displaystyle\leq\Big{|}\big{\\{}\\{\\!\\!\\{\alpha_{i}:i\in[t]\\}\\!\\!\\}:\forall
i\in[t]:\alpha_{i}\in[s]\\}\Big{|}$ (69) $\displaystyle\leq(t+1)^{s-1}.$ (70)

As a result, $(t+1)^{s-1}=\tilde{\Omega}(n^{k})$ or
$t=\tilde{\Omega}(n^{\frac{k}{s-1}})$. To complete the proof, we only need to
prove the claim.

Proof of Claim 3. Let $p_{1},p_{2},\ldots,p_{m}$ be distinct prime numbers
less than $n/k$. Using the prime number theorem, we know that
$\lim_{n\to\infty}\frac{m}{n/(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 ${\mathcal{B}}=\\{b_{1},b_{2},\ldots,b_{k}\\}\subseteq[m]$, define
$G_{\mathcal{B}}$ as a graph on $n$ vertices such that
$\mathcal{V}_{G_{\mathcal{B}}}=V_{0}\sqcup(\sqcup_{i\in[k]}\mathcal{V}_{i})$,
and $|\mathcal{V}_{i}|=p_{b_{i}}$. Also,

$\displaystyle e=(u,v)\in G_{\mathcal{B}}\iff\exists\leavevmode\nobreak\
{i,j\in[m],i\neq j}:u\in\mathcal{V}_{i}\leavevmode\nobreak\
\&\leavevmode\nobreak\ v\in\mathcal{V}_{j}.$ (71)

The graph $G_{\mathcal{B}}$ is well-defined since $\sum_{i=1}^{k}p_{b_{i}}\leq
k\times n/k=n$. Note that $C(G_{\mathcal{B}};K_{k})=\prod_{i=1}^{k}p_{b_{i}}$.
Also, since $p_{i}$, $i\in[m]$, are prime numbers, there is a unique bijection

$\displaystyle\mathcal{B}\overset{\varphi}{\longleftrightarrow}C(G_{\mathcal{B}};K_{k}).$
(72)

Therefore,

$\displaystyle\Big{|}\\{C(G;K_{k}):G\in\mathbb{G}_{n}\\}\Big{|}$
$\displaystyle\geq\Big{|}\\{C(G_{\mathcal{B}};K_{k}):\mathcal{B}\subseteq[m],|\mathcal{B}|=k\\}\Big{|}$
(73) $\displaystyle={m\choose k}$ (74) $\displaystyle\geq\frac{(m-k)^{k}}{k!}$
(75) $\displaystyle\geq\frac{(cn/(k\log(n/k))-k)^{k}}{k!}.$ (76)

##  Appendix E Relationship to the Reconstruction Conjecture

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 unattributed graphs.

######  Definition 10.

Let $\mathcal{F}_{n}\subseteq\mathbb{G}_{n}$ be a set of graphs and let
$G_{v}=G(\mathcal{V}\setminus\\{v\\})$ for any finite simple graph
$G=(\mathcal{V},\mathcal{E})$, and any $v\in\mathcal{V}$. Then, we say the set
$\mathcal{F}$ is reconstructible if and only if there is a bijection

$\displaystyle\\{\\!\\!\\{G_{v}:v\in\mathcal{V}\\}\\!\\!\\}\overset{\Phi}{\longleftrightarrow}G,$
(77)

for any $G\in\mathcal{F}_{n}$. In other words, $\mathcal{F}_{n}$ is
reconstructible, if and only if the multi-set
$\\{\\!\\!\\{G_{v}:v\in\mathcal{V}\\}\\!\\!\\}$ fully identifies $G$ for any
$G\in\mathcal{F}_{n}$.

It is known that the class of disconnected graphs, trees, regular graphs, are
reconstructible [42, 50]. The general case is still open; however it is widely
believed that it is true.

######  Conjecture 1 ([42]).

$\mathbb{G}_{n}$ is reconstructible.

For RNP-GNNs, the reconstruction from the subgraphs $G^{*}_{v}$, $v\in[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.

##  Appendix F The RNP-GNN Algorithm

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.,
$h_{G}\leftarrow\text{MLP}\Big{(}\sum_{v\in\mathcal{V}}h_{v}^{(k)}\Big{)}$.
Following [9], we use sum pooling here, to ensure that we can represent
injective aggregation functions.

Algorithm 1 Recursive Neighborhood Pooling-GNN (RNP-GNN)

0: $G=(\mathcal{V},\mathcal{E},\\{x_{v}\\}_{v\in\mathcal{V}})$ where
$\mathcal{V}=[n]$, recursion parameters
$r_{1},r_{2},\ldots,r_{t}\in\mathbb{N}$, $\epsilon^{(i)}\in\mathbb{R}$,
$i\in[\tau]$, node features $\\{x_{v}\\}_{v\in\mathcal{V}}$.

0: $h_{v}$ for all $v\in\mathcal{V}$

$h_{v}^{\text{in}}\leftarrow x_{v}$ for all $v\in\mathcal{V}$

if $\tau=1$ then

$h_{v}\leftarrow\text{MLP}^{(\tau,1)}\Big{(}(1+\epsilon^{(1)})h^{\text{in}}_{v}+\sum_{u\in\mathcal{N}_{r_{1}}(v)\setminus\\{v\\}}\text{MLP}^{(\tau,2)}(h^{\text{in}}_{u},\mathds{1}{(u,v)\in\mathcal{E}})\Big{)},$
for all $v\in\mathcal{V}$.

else

for all $v\in V$ do

$G_{v}^{\prime}\leftarrow G(\mathcal{N}_{r_{1}}(v)\setminus\\{v\\})$, which
has node attributes
$\\{(h_{u}^{\text{in}},\mathds{1}{(u,v)\in\mathcal{E}})^{\prime}\\}_{u\in\mathcal{N}_{r_{1}}(v)\setminus\\{v\\}}$

$\\{\hat{h}_{v,u}\\}_{u\in G_{v}^{\prime}\setminus\\{v\\}}\leftarrow\text{RNP-
GNN}(G_{v}^{\prime},(r_{2},r_{3},\ldots,r_{\tau}),(\epsilon^{(2)},\ldots,\epsilon^{(\tau)}))$

$h_{v}\leftarrow\text{MLP}^{(\tau)}\Big{(}(1+\epsilon^{(\tau)})h_{v}^{\text{in}}+\sum_{u\in\mathcal{N}_{r_{1}}(v)\setminus\\{v\\}}\hat{h}_{u,v}\Big{)}.$

end for

end if

return $\\{h_{v}\\}_{v\in\mathcal{V}}$

With this algorithm, one can achieve the expressive power of RNP-GNNs if high
dimensional MLPs are allowed [9, 51, 52]. That said, in practice, smaller MLPs
may be acceptable [9].

##  Appendix G Computing a Covering Sequence

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 $r_{1}$ (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
leaf $v_{i}$ from the tree and adding the respective node $v_{i}$ to the
sequence. This ensures that, at any point, the remaining graph is connected.
At position $i$ corresponding to $v_{i}$, the covering sequence contains the
maximum distance $r_{i}$ of $v_{i}$ 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 $r_{1}=\max_{u\in\mathcal{V}}d(u,v_{1})$, we need to ensure that a
node in $\arg\min_{v\in\mathcal{V}}\max_{u\in\mathcal{V}}d(u,v)$ is a leaf in
the spanning tree. Hence, we first compute $\max_{u\in\mathcal{V}}d(u,v)$ for
all nodes $v$, e.g., by running All-Pairs-Shortest-Paths (APSP) [53], 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 $v_{1}$, 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 $v_{1}$ in the vertex covering sequence. This algorithm runs in
polynomial time.

Algorithm 2 Computing a covering sequence with minimum $r_{1}$

0: $H=(\mathcal{V},\mathcal{E},X)$ where $\mathcal{V}=[\tau+1]$

0: A minimal covering sequence $(r_{1},r_{2}\ldots,r_{\tau})$, and its
corresponding vertex covering sequence $(v_{1},v_{2},\ldots,v_{\tau+1})$

For any $u,v\in\mathcal{V}$, compute $d(u,v)$ using APSP

$(u_{1},u_{2},\ldots,u_{\tau+1})\leftarrow$ all the vertices sorted
increasingly in $s(v):=\max_{u\in\mathcal{V}}d(u,v)$

for $i=1$ to $\tau+1$ do

Set edge weights $w({u,v})=1+\tau\times\mathds{1}\\{u=u_{i}\lor v=u_{i}\\}$
for all $(u,v)\in\mathcal{E}$

${H_{T}\leftarrow}$ the MST of $H$ with weights $w$

if $u_{i}$ is a leaf in $H_{T}$ then

${v_{1}\leftarrow u_{i}}$

$r_{1}\leftarrow s(u_{i})$

break

end if

end for

for $i=2$ to $t+1$ do

$v_{i}\leftarrow$ one of the leaves of $H_{T}$

$r_{i}\leftarrow\max_{u\in\mathcal{V}_{H_{T}}}d(u,v_{i})$

$H_{T}\leftarrow H_{T}$ after removing $v_{i}$

end for

return $(r_{1},r_{2},\ldots,r_{\tau})$ and $(v_{1},v_{2},\ldots,v_{t+1})$

##  Appendix H Experimental Details

###  H.1 Dataset and Task Details

For the counting experiments, we follow the setup of [11]. There are two
datasets: one consisting of 5000 Erdős-Renyi graphs [54] and one consisting of
5000 noisy random regular graphs [55]. Each Erdős-Renyi graph has 10 nodes,
and each random regular graph has either 10, 15, 20, or 30 nodes. Also, $n$
random edges are deleted from each random regular graph, where $n$ is the
number of nodes.

For the experiments on distinguishing non-isomorphic graphs, we use the EXP
dataset [17]. This dataset consists of 600 pairs of graphs (so 1200 graphs in
total), where each pair is 1-WL equivalent but distinguishable by 3-WL, and
each pair contains one graph that represents a satisfiable formula and one
graph that represents an unsatisfiable formula. We report the mean and
standard deviation across 10 cross-validation folds.

###  H.2 RNP-GNN Implementation Details

Here, we detail some specific design choices we make in implementing our RNP-
GNN model. Most embeddings are computed in $\mathbb{R}^{d}$ for some fixed
hidden dimension $d$. The input node features are first embedded in
$\mathbb{R}^{d}$ by an initial linear layer. Then RNP layers are applied to
compute node representations. Finally, a sum pooling across nodes followed by
a final MLP is used to compute a graph-level output.

An RNP layer for $r=(r_{1},\ldots,r_{t})$ is implemented as follows. Note that
the input node features to this layer are in $\mathbb{R}^{d}$ due to our
initial linear layer. Also, note that we concatenate an extra feature
dimension due to the augmented indicator feature at each recursion step. To
align these feature dimensions, for $l\in[t]$, we parameterize the $l$-th GIN
[9] by a feedforward neural network
$\mathrm{MLP}^{(l)}:\mathbb{R}^{d+l}\to\mathbb{R}^{d+l-1}$. For instance, the
last GIN has a feedforward network
$\mathrm{MLP}^{(t)}:\mathbb{R}^{d+t}\to\mathbb{R}^{d+t-1}$, because after $t$
levels of recursion we have augmented $t$ features. Dropout and nonlinear
activation functions are only applied in the MLPs.

###  H.3 Hyperparameters

For all baseline models, we take the results from other papers. Thus, for the
counting experiments the configurations for the baseline models are from [11],
while for the EXP experiments the configurations for the baseline models are
from [17].

RNP-GNN hyperparameters. For all experiments we ran random search over
hyperparameters. In all cases we used the Adam optimizer with initial learning
rate in $\\{.01,.001,.0001,.0005\\}$. We train for 100 epochs with a batch
size in $\\{16,32,128\\}$. The number of stacked RNP-GNNs for computing node
representations is in $\\{1,2\\}$. We use a dropout ratio in $\\{0,.1,.5\\}$.
The recursion parameters used varies for each task. We used two layers for
each MLP used in the aggregation function. Also, the graph-level output
obtained after sum-pooling across nodes is computed by a two layer MLP.

Specifically for the counting experiments, the number of hidden dimensions is
searched in $\\{16,32,64\\}$. For all tasks we used $r_{1}=1$. We use ReLU
activations in the MLPs. We either decay the learning rate by half every
$25,50,$ or $\infty$ epochs (where $\infty$ means never decaying).

For the EXP experiments, the number of hidden dimensions is searched in
$\\{8,16,32,64\\}$. We use either ELU or ReLU activations in the MLPs. We
decay the learning rate by half at the 50th epoch. The recursion parameters
are $r=(2,1)$.