#  Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional
Networks

Hao Chen
Wuhan University
Shanghai Jiao Tong University
<EMAIL_ADDRESS>&Yu Guang Wang
Shanghai Jiao Tong University
University of New South Wales
<EMAIL_ADDRESS>&Huan Xiong
Harbin Institute of Technology
Mohamed bin Zayed University of AI
<EMAIL_ADDRESS>
###### Abstract

The research for characterizing GNN expressiveness attracts much attention as
graph neural networks achieve a champion in the last five years. The number of
linear regions has been considered a good measure for the expressivity of
neural networks with piecewise linear activation. In this paper, we present
some estimates for the number of linear regions of the classic graph
convolutional networks (GCNs) with one layer and multiple-layer scenarios. In
particular, we obtain an optimal upper bound for the maximum number of linear
regions for one-layer GCNs, and the upper and lower bounds for multi-layer
GCNs. The simulated estimate shows that the true maximum number of linear
regions is possibly closer to our estimated lower bound. These results imply
that the number of linear regions of multi-layer GCNs is exponentially greater
than one-layer GCNs per parameter in general. This suggests that deeper GCNs
have more expressivity than shallow GCNs.

##  1 Introduction

Graph Neural Networks (GNNs) [1] have gained a champion for various structured
prediction tasks. GNNs have the similar network architecture as the
traditional CNNs [2] but taking the graph structured data as input. Compared
with CNNs, GNNs take account of the feature on the node, like a pixel feature,
and also geometric property of the data in the network propagation. In
particular, the feature of each node is extracted from layer to layer by
aggregating its neighbor information [3]. While a good many GNN models have
been proposed, the expressiveness of GNNs is yet to be characterized in
theory. The number of linear regions has been a useful tool for capturing how
complex a neural network is, and shown quantitatively why deep neural networks
surpasses shallow networks [4, 5]. The linear regions can also reveal the
expressiveness of GNNs, especially when the GNNs take the form of graph
convolutional networks (GCNs) [6]. In this paper, we prove the lower and upper
bound of the number of linear regions of GCNs and show how the depth links to
the linear regions.

Different kinds of deep neural networks (DNNs) have shown outstanding
performance in some circumstances such as sound recognition, computer vision,
and recommendation system [7, 8, 9, 10, 11, 12, 13]. People have developed
theories for the powerful expressivity of DNNs to explain the outstanding
performance of different neural networks. For example, a one-layer fully
connected neural network is proved to have the power to approximate any
continuous function with enough width [14, 15]. Any given Lebesgue-integrable
function can be approximated by a neural network with enough layers [16, 17].
Yarosky has provided the approximation error of deep neural networks [18].
Other works quantify the impact of the network structure on expressivity for
deep neural networks. Telgarsky [19] has proved that the depth helps reduce
the number of parameters: a shallow network needs much more parameters than a
deep neural network to represent a same function.

Figure 1: 2D slices of linear regions for the input space of 3 GCNs with 1
layer (left), 2 layers (middle) and 3 layers (right), on an input graph with 3
nodes and 2 edges. Each GCN has 1 input feature for the first layer and 3
output features for all layers.

A variety of methods have been proposed to characterize the ability of a
network to approximate any given function, such as number of linear regions
[20, 4, 21], length distortion [22, 23], VC-dimension [24], and other
topological and geometric tools [25, 26]. In this paper, we focus on the
number of linear regions for GCNs. To count linear regions of neural networks,
researchers mainly studied the NNs with Rectifier Linear Unit (ReLU)
activation, a piecewise linear function introduced by [27, 28], which has been
widely used in various kinds of neural networks [29]. The feedforward
propagation of a neural network activated with ReLU from one hidden layer to
the next can be regarded as a piecewise linear function. Then, the whole
neural network can be viewed as a composition of several piecewise linear
functions, which is also piecewise. Neural networks with more linear pieces
can estimate more complex functions. GCNs that are neural networks for
structured data input can be also viewed as piecewise functions, and the
number of the linear regions shows the expressive power of GCNs.

#### Activation Patterns of Neural Networks

Activation pattern of a neural network with piecewise linear activation can be
characterized by the number of activation regions. It is important to measure
the network complexity, approximation error, convergence rate of networks,
implicit bias in parameter optimization and Lipschitz constants. Nguyen et al.
(2020) [30] showed that linear regions can be applied in the research of the
eigenvalues of the neural tangent kernel and Lipschitz constant. Linear
regions have been a useful tool for capturing how complex a neural network is,
and shown quantitatively why deep neural networks surpass shallow networks
[20, 4, 5]. Steinwart et al. (2019) [31] reported that the convergence of
gradient descent is influenced by activation patterns. Phuong et al. (2020)
[32] linked linear regions with function-preserving transformations of network
parameters.

#### Maximum and Expected Numbers of Linear Regions

The maximum number of linear regions is one of the most useful measures for
activation patterns. Montúfar et al. (2014) [4] reported the upper and lower
bounds for the maximum number of linear regions of NNs. The upper bound was
later improved by Serra et al. (2018) [33]. Based on [34], a tighter upper
bound was proved by Hinz et al. (2021) [35]. As the activate pattern is
largely affected by the network architecture and number of parameters,
estimating the expected number of linear regions with respect to the choice of
parameters is significant for comparing the network complexity among different
architectures. The expected number of linear regions for ReLU networks was
first reported in [36, 37]. Tseran et al. (2021) showed the expected number of
linear regions for maxout networks [38].

#### Related Notion

The activation regions can be measured from different perspectives, such as
tropical geometry, max-affine splines, and trajectory length. Zhang et al.
[39] showed that the family of ReLU neural networks is equivalent to the
family of tropical rational maps. The trajectory length was first proposed in
[40] to measure how the network output changes as the input sweeps along a
one-dimensional path. To study the piecewise affine convex nonlinearities, the
new operator was proposed to concatenate the max-affine spline formed from
affine mappings [41].

#### Contributions

Using specific topological and geometrical methods, this work obtains the
lower and upper bounds for the number of one-layer and multi-layer GCNs. Below
are our main contributions.

  * •

We obtain an optimal upper bound for the number of linear regions for one-
layer GCNs when the network parameters are in a complement of a measure zero
set with respect to space $\mathbb{R}^{\\#{\rm weights}+\\#{\rm biases}}$.

  * •

We obtain the upper and lower bounds for the maximal number of linear regions
of multi-layer GCNs. In our theory, we translate the problem of counting areas
in the input space into a problem of counting hyper-cubes in the new space.
The lower bound is proved by constructing a specific GCN.

  * •

We show that the number of linear regions of multi-layer GCNs is exponentially
greater than one-layer GCNs, which suggests that deeper GCNs have more
expressivity than their shallow counterparts.

  * •

We also compare the number of linear regions for GCNs, NNs, and CNNs with the
same input dimension and similar network architectures. It shows that the
multi-layer ReLU (activated) GCNs have more linear regions than multi-layer
ReLU CNNs and multi-layer ReLU NNs.

##  2 Preliminary

In this section, we give some basic notations and definitions. Let
$\mathbb{N}$, $\mathbb{N}^{+}$ and $\mathbb{R}$ be the set of nonnegative
integers, positive integers and real numbers respectively. Let $\\#S$ be the
number of elements in a set $S$. In this paper, we focus on GCNs with
$L$-layer convolutions and exclude pooling layers and fully connected layers
for simplicity. Let $G=(V,E)$ denote the graph of the GCNs where $V$ and $E$
are the set of vertices and edges of the graph. Let $D:=\\#V$ be the number of
nodes, and $N_{0}$ be the number of input features (i.e. feature dimension).
Therefore, the input dimension of the first layer is $D\times N_{0}$. Suppose
that there are $N_{l}$ output features in the $l$-th layer. Let $A$ be the
adjacency matrix of graph $G$. We define $\hat{A}=M^{-1/2}(I+A)M^{-1/2}$ with
$M$ being the degree matrix of $I+A$. Let $\tilde{A}$ be the $\hat{A}$ with
repeated rows deleted, and $D^{*}=\text{rank}(\hat{A})$ which is also the
number of rows of $\tilde{A}$.

The Rectifier Linear Unit (ReLU) is adopted as the activation function for
each neuron in every hidden layer. Let $X^{(0)}\in\mathbb{R}^{D\times N_{0}}$
be the input of the first layer and $X^{(l)}\in\mathbb{R}^{D\times N_{l}}$ be
the output of the $l$-th layer. Let $W_{l}\in\mathbb{R}^{N_{l-1}\times N_{l}}$
and $b_{l}\in\mathbb{R}^{N}_{l}$ be the weight and bias of $l$-th layer.
Therefore, we denote the weights and biases for the GCNs as
$W=(W_{1},W_{2},\dots,W_{L})$ and $B=(b_{1},b_{2},\dots,b_{L})$. Denote by
$\theta=(W,B)$ trainable network parameters including weights and biases.

As we can represent a one-layer GCN with given weights and biases by a
composition of an affine linear function and a piece-wise linear function, we
can see the GCN as a piece-wise linear function. Thus, for any given $W$ and
$B$, the $L$-layer GCN can be seen as a composition of $L$ piece-wise linear
functions, which we then write as a piece-wise linear function
$\mathcal{F}_{\mathcal{N},W,B}(X^{(0)})$.

######  Definition 1 (Activation Patterns and Linear Regions).

Let $\mathcal{N}$ be an $L$-layer GCN with $n$ neurons in total. An activation
pattern is a function of all inputs (denoted as $z_{i},\ i=1,2,\dots,n$) of an
activation function of $n$ neurons in $\mathcal{N}$. The value of an
activation pattern is in $\\{-1,1\\}^{n}$. Suppose that $P_{i}$ is the $i$-th
component of $P(z_{1},z_{2},\dots,z_{n})$. A region corresponding to $P$ and
parameters $\theta$ reads

$\mathcal{R}(P,\theta)=\\{X^{(0)}:\forall i\ \in\ [1,n],\ P_{i}\cdot
z_{i}>0\\}.$

A non-empty $\mathcal{R}(P,\theta)$ is a linear region for $\mathcal{N}$ when
the parameter is $\theta$. Therefore, the number of linear regions of
$\mathcal{N}$ with parameter $\theta$ is
$R_{\mathcal{N},\theta}=\\#\\{\mathcal{R}(P,\theta):\exists P\ such\ that\
\mathcal{R}(P,\theta)\neq\varnothing\\}$. Furthermore, denote the maximal
number of linear regions by $R_{\mathcal{N}}$.

######  Remark 1.

From Definition 1, $\mathcal{F}_{\mathcal{N},W,B}$ is a linear affine function
when restricted in one linear region. Then, the $L$-layer GCN can represent a
piece-wise linear function with $R_{\mathcal{N},\theta}$ pieces. Therefore, we
can count the number of linear regions to measure the expressive power of a
GCN. A formula or bounds of the number of linear regions will be shown for
single- and multi-layer GCNs in our work.

The definition of activation pattern implies that the maximal number of
activation patterns for $\mathcal{N}$ is $2^{n}$, as stated in the next lemma.

######  Lemma 1.

A trivial upper bound of the number of linear regions is

$R_{\mathcal{N},\theta}\leq 2^{n}.$ (1)

To state the main results, we introduce the asymptotic notation: For two
functions $f(x)$ and $g(x)$, we write $f(x)=\mathcal{O}(g(x))$ if $\exists\
c>0$ s.t. $f(x)\leq cg(x)$ for all $x$ greater than some constant;
$f(x)=\Omega(g(x))$ if $\exists\ c>0$ s.t. $f(x)\geq cg(x)$ for all $x$
greater than some constant; $f(x)=\Theta(g(x))$ if $\exists\ c_{1}>0$ and
$c_{2}>0$ s.t. $c_{1}g(x)\leq f(x)\leq c_{2}g(x)$ for all $x$ greater than
some constant. We put all proofs of the results of the paper in the appendix.

##  3 Number of Linear Regions for One-Layer GCNs

In this section, we show the exact formula for the maximal number and average
number of linear regions of GCNs. The estimate shows that if the parameters of
GCNs are drawn from some distribution, the average number of linear regions is
exactly the maximal number of linear regions. Therefore, it is almost sure
that the number of linear regions of GCNs with arbitrary given parameters can
reach the maximal number.

#### Exact Formulas for One-Layer GCNs

The next proposition about linear regions of fully connected NNs is needed to
derive the exact formula for One-Layer GCNs.

######  Proposition 1.

Let $\mathcal{N}$ be a one-layer fully connected neural network. Assume that
the input dimension of $\mathcal{N}$ is $n_{0}$ and there are $n_{1}$ neurons.
Then, the maximal number of linear regions of $\mathcal{N}$ is
$\sum_{i=0}^{n_{0}}\tbinom{n_{1}}{i}$.

Since $\mathcal{N}$ is a fully connected neural network, the pre-activation of
a hidden layer neuron is the affine function of the input, which then
translates the problem of counting the number of linear regions to counting
the number of regions of hyperplane arrangements in the general position, and
this then implies the following formula for the number of linear regions of
one-layer GCNs.

######  Theorem 1.

Assume that $\mathcal{N}$ is a one-layer GCN with the input
$X^{(0)}\in\mathbb{R}^{D\times N}$ and the output
$X^{(1)}\in\mathbb{R}^{D\times N^{\prime}}$. Let $\tilde{A}$ denote normalized
adjacency matrix $A$ with duplicated rows removed and $D^{*}=\text{rank}(A)$.
Let $V_{1,1},V_{1,2},\dots,V_{D^{*}N^{\prime}}$ be the subspaces of
$V=\mathbb{R}^{D^{*}\times N}$ and $V_{ij}=\alpha_{i}^{\top}w_{j}^{\top}$
where $\alpha_{i}$ is the $i$-th column of $\hat{A}$ and $w_{j}$ is the $j$-th
row of $W$. For given network parameters $\theta$, let

$K_{\mathcal{N},\theta}:=\left\\{(k_{1,1},k_{1,2},...,k_{D^{*}N^{\prime}}):k_{ij}\in\mathbb{N},\sum_{i\in
I,\>j\in J}k_{ij}\leq{\rm
dim}\bigl{(}\sum_{k_{ij}=1}V_{ij}\bigr{)},\;\forall(i,j)\in[D^{*}]\times[N^{\prime}]\right\\}.$
(2)

Then, we have the upper bound

$R_{\mathcal{N},\theta}\leq\sum\limits_{(k_{1,1},...,k_{D^{*}N^{\prime}})\in
K_{\mathcal{N},\theta}}\;\prod\limits_{(i,j)\in[D^{*}]\times[N^{\prime}]}^{D^{*}}\binom{1}{k_{ij}}=\\#K_{\mathcal{N},\theta}.$
(3)

To prove Theorem 1, we creatively change the form of adjacency matrix
$\hat{A}$ by deleting the repeated rows and constructing several arrangements
not in general position with the row and column number. From the
generalization form of Zaslavsky theorem in [5], we derive (3).

From the above Theorem 1, the rank of $A$ and $W$ is closely related to the
number of elements in $K_{\mathcal{N},\theta}$ in (2). We have the next
proposition which shows the upper bound for the maximal number of linear
regions in two scenarios for whether $N>N^{\prime}$ or $N\leq N^{\prime}$.

######  Proposition 2.

Let $\text{rank}(\tilde{A})=D^{*}$. The next two estimates for
$K_{\mathcal{N},\theta}$ in (2) hold.

(i) When $N>N^{\prime}$ and $\mathrm{rank}(W)=N^{\prime}$,

$\\#K_{\mathcal{N},\theta}=2^{N^{\prime}D^{*}}.$ (4)

(ii) When $N\leq N^{\prime}$ and any N column vectors in W are linearly
independent,

$\\#K_{\mathcal{N},\theta}=\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}.$
(5)

Theorem 1 and Proposition 2 show that in general case $R_{\mathcal{N},\theta}$
is upper bounded by $\\#K_{\mathcal{N},\theta}$. The next theorem shows that
the probability of $R_{\mathcal{N},\theta}=\\#K_{\mathcal{N},\theta}$ is $1$.

######  Theorem 2.

Assume that the parameters $W$ and $B$ are drawn from some distribution $\mu$
which has densities with respect to Lebesgue measure in
$\mathbb{R}^{\\#weights+\\#biases}$. Then, the number of linear regions of the
GCN
$R_{\mathcal{N},\theta}=\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}$
almost surely, that is, when network parameters are in the complement of a
measure-zero set of $\mu$ on $\mathbb{R}^{\\#{\rm weights}+\\#{\rm biases}}$.
Moreover, the expectation is

$E_{\theta\sim\mu}(R_{\mathcal{N},\theta})=\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}.$
(6)

Theorem 2 relies on the following lemmas.

######  Lemma 2.

Let the adjacency matrix of graph G for one GCN be $\tilde{A}$. If each row of
$\tilde{A}$ is different, $\tilde{A}$ is invertible. If we take away the rows
that have already appeared in $\tilde{A}$, then the left row vectors are
linearly independent.

######  Lemma 3.

All $W\in\mathbb{R}^{N\times N^{\prime}}$ satisfying
$\mathrm{rank}(W)\textless\text{min}(N,N^{\prime})$ form a measure zero set in
$\mathbb{R}^{N\times N^{\prime}}$.

######  Lemma 4.

For $W\in\mathbb{R}^{N\times N^{\prime}}$ and $N\leq N^{\prime}$, all $W$ such
that $\exists\ \ I\subseteq[N^{\prime}]$ and $\\#I=N$ satisfying ${\rm
rank}((W_{i},\ i\in I))\textless N$ form a measure-zero set in
$\mathbb{R}^{N\times N^{\prime}}$.

######  Lemma 5.

Let $W\in\mathbb{R}^{N\times N^{\prime}}$ and $B\in\mathbb{R}^{N^{\prime}}$.
All pairs $(W,B)$ satisfying that there exists one vector $p_{w}$ such that
$p_{w}{\rm vec}(B)=0$, form a null set in $\mathbb{R}^{D\times
N^{\prime}+N^{\prime}}$ with respect to Lebesgue measure.

Outline for the proof of Theorem 2. With the results in Theorem 1 and
Proposition 2, we need only to show that all $W$ and $B$ satisfying
$R_{\mathcal{N},\theta}\textless\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}$
form a measure zero set for $\mu$ on $\mathbb{R}^{\\#weights+\\#biases}$. By
Lemma 2, we can show that the rank of the adjacency matrix is equal to the
number of distinct rows. The operation of deleting the repeated rows in the
adjacency matrix helps us to obtain Lemma 5, which implies that
$R_{\mathcal{N},\theta}=\\#K_{\mathcal{N},\theta}$ almost surely. By Lemmas 4
and 3, (4) and (5) then hold almost surely on
$\mathbb{R}^{\\#weights+\\#biases}$.

Denote $R_{\mathcal{N}}$ as the optimal upper bound of
$R_{\mathcal{N},\theta}$ that is
$\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}$. Table 1 compares
the estimate for a one-layer GCN with input dimension $3\times 1$ and output
dimension $3\times N_{1}$ by Theorem 1 and Proposition 2 with Proposition 1
and Lemma 1, where $N_{1}$ ranges in $\\{1,2,3,4,5\\}$. From (6),
$R_{\mathcal{N}}=(1+N_{1})^{3}$ almost surely. The upper bound for
$R_{\mathcal{N}}$ obtained from Lemma 1 is $2^{3d}$, and by Proposition 1,
$\sum_{i=0}^{3}\tbinom{3d}{i}$. The table results show that Theorem 1 which
gives the tight upper bound provides a precise estimate than the upper bound
of Proposition 1 and the trivial bound of Lemma 1. We compare the estimates as
Table 1 for another two types of graphs in Section 6.

Table 1: Comparison of estimates for one-layer GCN with input, output size $3\times 1$, $3\times N_{1}$. | $N_{1}=1$ | $N_{1}=2$ | $N_{1}=3$ | $N_{1}=4$ | $N_{1}=5$
---|---|---|---|---|---
$R_{\mathcal{N}}$ (Thm 2, Cor 2) | 8 | 27 | 64 | 125 | 216
Upper bound (Prop 1) | 8 | 42 | 130 | 299 | 576
Naive upper bound (Lem 1) | 8 | 64 | 512 | 4096 | 32768

#### Asymptotic Estimate

Let $R_{\mathcal{N}}$ be the maximum of the $R_{\mathcal{N},\theta}$ over all
possible parameters $\theta$. The following theorem shows an asymptotic
estimate for $R_{\mathcal{N}}$.

######  Theorem 3.

Let $\mathcal{N}$ be a one-layer GCN. Suppose that $N^{\prime}$ tends to
infinity and other parameters are fixed integers. Let
$\text{rank}(\hat{A})=D^{*}$, then

$R_{\mathcal{N}}=\Theta\bigl{(}(N^{\prime})^{D^{*}N}\bigr{)}.$ (7)

##  4 Bounds of the Number of Linear Regions for Multi-Layer GCNs

The following theorem presents upper and lower bounds for the maximal number
of linear regions for multi-layer GCNs. Both lower and upper bounds can be
written by the maximum number of linear regions for a one-layer GCN multiplied
by an exact number depending on the network depth and the number of neurons.
The theory applies to general network architectures of GCNs.

######  Theorem 4.

Let $\mathcal{N}$ be a GCN with L hidden layers and ReLU activation. Suppose
that the input is $X^{(0)}\in\mathbb{R}^{D\times N_{0}}$ and the output of
each layer is $X^{(l)}\in\mathbb{R}^{D\times N_{l}}$. Let the adjacency matrix
be $\hat{A}\in\mathbb{R}^{D\times D}$ and the weight of each layer be
$W\in\mathbb{R}^{N_{0}\times N_{l}}$. Assume that $N_{l}\geq N_{0}$ for each
$l\geq 1$. Then, we have the following lower and upper bounds of
$R_{\mathcal{N}}$.

(i) The maximal number of linear regions $R_{\mathcal{N}}$ of GCN
$\mathcal{N}$ is at most:

$R_{\mathcal{N}}\leq
R_{\mathcal{N^{{}^{\prime\prime}}}}\prod\limits_{l=2}^{L}\left(\sum\limits_{i=0}^{DN}\tbinom{DN_{l}}{i}\right),$
(8)

where $\mathcal{N}^{\prime\prime}$ is a one-layer GCN with input and output
dimensions $D\times N_{0}$ and $D\times N_{1}$.

(ii) The maximal number of linear regions $R_{\mathcal{N}}$ of GCN
$\mathcal{N}$ is no less than:

$R_{\mathcal{N}}\geq
R_{\mathcal{N^{\prime}}}\prod\limits_{l=1}^{L-1}\left\lfloor\frac{N_{l}}{N}\right\rfloor^{N\times\text{rank}(A)},$
(9)

where $\mathcal{N}^{\prime}$ is a one-layer GCN with input and output
dimensions $D\times N$ and $D\times N_{L}$.

We derive (8) by induction. Assume that (8) is true for $L-1$ layers. Then the
input space could be separated into several linear regions by the first $L-1$
layers. In each linear region, the network consists of the first $L-1$ layers
and could be viewed as a linear function of the input. Then, in each linear
region, the network consisting of $L$ layers could be viewed as a fully
connected neural network whose upper bound is given in [4].

To obtain the lower bound in Theorem 4, we design a GCN with specific
parameters. Both the adjacency matrix and weight have an influence on the
input features $X$ so we can use the space folding method introduced in [4]
directly. We consider the adjacency matrix as a linear mapping from the input
space $V_{X}$ into another space $V_{Y}$. With specific parameters, we could
separate an area in $V_{Y}$ into several hypercubes and each could be mapped
to the original area in the input space. The eigenvalue and eigenvector
properties in Lemma 8 make such transformation possible. Therefore, with Lemma
2 in [4], we then obtain the lower bound.

##  5 Expressivity Comparison of Different Network Architectures

We compare the number of parameters in deep and shallow graph convolutional
networks. First, for an $L$-layer GCN, its number of parameters can be counted
exactly. This demonstrates the complexity of deep GCNs compared to shallow
GCNs and MLPs with the same-order number of parameters.

######  Lemma 6.

Suppose that there are D nodes in the graph, $N_{0}$ input features and
$N_{l}$ output features for the $l$-th layer. Then the number of network
parameters is $\sum_{l=1}^{L}(N_{l-1}\times N_{l}+N_{l})$.

###  5.1 Deep GCNs vs Shallow GCNs

By Lemma 6, Theorem 1 and Theorem 4, it is easy to obtain the following
results.

######  Theorem 5.

Let $\mathcal{N}_{1}$ be an L-layer GCN. Suppose that
$N_{1}=N_{2}=\cdots=N_{L}=N^{\prime}$ tends to infinity. Then,
$\mathcal{N}_{1}$ has $L(NN^{\prime}+DN^{\prime})=\Theta(LN^{\prime})$
parameters and the ratio $\rho_{\mathcal{N}_{1}}$ of $R_{\mathcal{N}_{1}}$ to
the number of parameters of $\mathcal{N}_{1}$ is bounded by

$\rho_{\mathcal{N}_{1}}=\Omega\left(\frac{1}{L}{N^{\prime}}^{LN\times\text{rank}(A)-1}\right).$
(10)

On the other hand, let $\mathcal{N}_{2}$ be a one-layer GCN with input
dimension $D\times N$ and output dimension $D\times LN^{\prime}$. Then
$\mathcal{N}_{2}$ also has $\Theta(LN^{\prime})$ parameters, which has the
same-order number of parameters as $\mathcal{N}_{1}$. The ratio
$\rho_{\mathcal{N}_{2}}$ of $R_{\mathcal{N}_{2}}$ to the number of parameters
of $\mathcal{N}_{2}$ is

$\rho_{\mathcal{N}_{2}}=\Theta\left((LN^{\prime}D)^{N\times\text{rank}(A)-1}\right).$
(11)

Since only $N^{\prime}$ tends to infinity, we obtain that
$\rho_{\mathcal{N}_{2}}=\Theta((N^{\prime})^{N\times\text{rank}(A)})$.

It is not difficult to check that $\rho_{\mathcal{N}_{1}}$ grows much faster
when $L$ and $N^{\prime}$ are large enough. Theorem 5 then shows that with the
same total number of parameters, a deep GCN has more complexity than a shallow
GCN, and thus more expressive power.

###  5.2 GCNs vs Fully Connected NNs

Let $\mathcal{N}_{1}$ be the $L$-layer GCN in Theorem 5 with invertible
adjacency matrix and $\mathcal{N}_{3}$ be an $L$-layer fully connected NNs (or
an $L$-layer MLP). Suppose that the input dimension of NNs is $D\times N_{0}$
and the output dimension of each layer is $N$. Trivially, the number of
parameters for $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ are both
$\mathcal{O}(LN^{2})$ so we only need to compare the maximum number of linear
regions. Again, we compare the upper bound of linear number of
$\mathcal{N}_{2}$ with the lower bound of $\mathcal{N}_{1}$. Since
$R_{\mathcal{N}_{1}}=\Theta\left((DN_{0})^{L}\tbinom{N}{DN_{0}}^{L}\right)$,
from Stirling’s formula [42] we could obtain
$R_{\mathcal{N}_{1}}=\Theta\left((DN_{0})^{L}\frac{N^{LDN_{0}}}{(DN_{0}/e)^{DN_{0}L}\sqrt{2\pi
DN_{0}}^{L}}\right)$. Therefore,

$\frac{R_{\mathcal{N}_{1}}}{R_{\mathcal{N}_{2}}}=\Omega\left(\left(\frac{D^{DN_{0}}}{DN_{0}e^{DN_{0}}}\right)^{L}\right).$
(12)

Obviously, when D tends to infinity, the ratio
$\frac{R_{\mathcal{N}_{1}}}{R_{\mathcal{N}_{2}}}$ approaches infinity. This
shows that $R_{\mathcal{N}_{1}}$ grows much faster than $R_{\mathcal{N}_{2}}$.
This observation means ReLU GCNs with invertible adjacency matrix has more
expressivity than NNs.

######  Remark 2.

Let $\mathcal{N}_{1}$ be the $L$-layer GCN in Theorem 5 with invertible
adjacency matrix and $\mathcal{N}_{3}$ be an $L$-layer CNN. Suppose that the
input dimension of the first layer is $D\times 1\times N$ and the output
dimension of each layer is $1\times 1\times N^{\prime}$. Therefore, the upper
bound of the number of linear regions for $\mathcal{N}_{3}$ is
$R_{\mathcal{N}_{3}^{*}}\prod_{l=2}^{L}\sum_{i=0}^{Nd}\tbinom{N^{\prime}}{i}$
where $R_{\mathcal{N}_{3}^{*}}$ is the number of linear regions for a one-
layer CNN with input dimension $D\times 1\times N$ and output dimension
$1\times 1\times N^{\prime}$. From [5] we can prove
$R_{\mathcal{N}_{3}^{*}}=\mathcal{O}(R_{\mathcal{N}_{1}^{*}})$. Thus, we
obtain the same order to (12),
$\frac{R_{\mathcal{N}_{1}}}{R_{\mathcal{N}_{3}}}=\Omega\left(\left(\frac{D^{DN_{0}}}{DN_{0}e^{DN_{0}}}\right)^{L}\right)$.
This means that ReLU GCNs with invertible adjacency matrix has more expressive
power than CNNs. Note here we provide a rough comparison as we used the upper
bound of CNNs in [5], which has the same order as the fully connected NNs with
same depth and similar size of input and same order number of network
parameters. The true maximum number of linear regions of CNNs is smaller than
$\mathcal{O}(R_{\mathcal{N}_{1}^{*}})$.

##  6 Experiments

Table 2: The lower and upper bounds from (8) and (9), and simulated estimate of Linear regions of GCN with two layers, for different feature dimensions $N_{2}$ of the second layer output. The input feature dimension for the first and second is both set 2. $N_{2}$ | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
Lower bound | 8 | 64 | 343 | 1331 | 4096
Simulated Estimate | 101 | 223 | 1643 | 2398 | 4453
Upper bound | 512 | 4096 | 29824 | 160640 | 636736

#### Number of Linear Regions for 2-layer GCNs

We show an example of two-layer GCN to illustrate lower and upper bounds of
Theorem 4 compared with the simulated estimate. Let $\mathcal{N}$ be a two-
layer GCN. The inputs of the first layer and the second layer are
$X^{(0)}\in\mathbb{R}^{3\times 2}$ and $X^{(1)}\in\mathbb{R}^{3\times N_{1}}$,
respectively. The output dimension of the second layer is $3\times N_{2}$. The
input graph has the normalized adjacency matrix

$\hat{A}=\left(\begin{matrix}\frac{1}{2}&\frac{1}{\sqrt{6}}&0\\\
\frac{1}{\sqrt{6}}&\frac{1}{3}&\frac{1}{\sqrt{6}}\\\
0&\frac{1}{\sqrt{6}}&\frac{1}{2}\end{matrix}\right).$

Table 2 shows the bounds of different GCNs with different values of $N_{2}$
together with the simulated estimate for $R_{\mathcal{N}}$ by random sampling
methods. The results suggest that the lower bound is closer to the simulated
estimate, and thus the true number of the linear regions.

To validate our results in the previous sections, we have randomly sampled
data points as the input, and counted the corresponding number of linear
regions by Definition 1. We initialize the parameters based on Kaiming He
initialization [43]. Given parameters, we have tried normal distribution and
uniform distribution to sample our input points with different distribution
parameters and report the biggest number of linear regions in Table 2.
Concretely, we test for the normal distribution with $\mu=0$ and
$\sigma^{2}\in\\{1,3,5,7,9\\}$, and for uniform distribution
$\mathcal{U}(-u,u)$ with $u\in\\{1,5,10\\}$. To obtain a statistically sound
estimate, we sample $2\times 10^{6}$ input data and record the activation
pattern for each input, and find the total disjoint patterns as the total
linear regions for all inputs. This number is summarized in Table 2 as the
simulated estimate for the linear regions of a specific GCN.

Figure 2: Bounds for GCNs with 1 layer (left) and 2 layers (right) on an input
graph which consists of 4 nodes and 3 edges. The left image shows the optimal
upper bound (green) gained from Theorem 2, upper bound (orange) from
Proposition 1 and the naive upper bound (blue) from Lemma 1 for a 1-layer GCN
with 1 input feature and $N_{1}$ output features where $N_{1}$ ranges from 1
to 19. The right image shows the lower bound (orange) and upper bound (blue)
obtained from Theorem 4 for a 2-layer GCN with 1 input feature and $N_{1}$ and
3 output features for the first and second layers.

#### Estimates for Linear Regions of GCNs with 1 and 2 layers

Figure 3 shows the bounds for the number of linear regions of one-layer and
two-layer GCNs as given by Theorem 2, Proposition 1, Lemma 1 and Theorem 4.
The input graph has 4 nodes and adjacency matrix

$\hat{A}=\left(\begin{matrix}\frac{1}{3}&\frac{1}{3}&\frac{1}{\sqrt{6}}&0\\\
\frac{1}{3}&\frac{1}{3}&0&\frac{1}{\sqrt{6}}\\\
\frac{1}{\sqrt{6}}&0&\frac{1}{2}&0\\\ 0&\frac{1}{\sqrt{6}}&0&\frac{1}{2}\\\
\end{matrix}\right).$

In this specific case, we can obtain exact formulas for the estimated bounds,
as follows. For 1-layer GCN with 1 input feature and $N_{1}$ output features,
from (6), $R_{\mathcal{N}}=(1+N_{1})^{4}$ almost surely. The upper bounds in
Proposition 1 and Lemma 1 read
$R_{\mathcal{N}}\leq\sum_{i=0}^{4}\tbinom{4N_{1}}{i}$ and $R_{\mathcal{N}}\leq
2^{4N_{1}}$. For the 2-layer GCN with 1 input feature and $N_{1}$ output
features for the first layer and 3 output features for the second layer, the
upper and lower bounds are given by $625N_{1}^{4}\leq
R_{\mathcal{N}}\leq(1+N_{1})^{4}\sum_{i=0}^{4N_{1}}\tbinom{4N_{1}}{i}$. We use
these bounds to plot Figure 2. The results demonstrate that for one-layer
GCNs, our estimated upper bound (orange) for the maximum number of linear
regions has an improvement for the existing upper bound (blue). For both the
one-layer and two-layer GCNs, the network becomes more complex as the number
of neurons of the first layer increases.

##  7 Related Work

#### Linear Regions

The number of linear regions for one-layer NNs with $n_{0}$ inputs and $n_{1}$
neurons was first reported by [20]. They turned the problem of counting linear
regions into the problem of counting regions of hyperplane arrangements in
general position and applied Zaslavsky’s theorem [44, 45]. Moreover, they
proposed a lower bound
$\left(\prod_{l=1}^{L-1}\lfloor\frac{n_{l}}{n_{0}}\rfloor\right)\sum_{i=0}^{n_{0}}\tbinom{n_{L}}{n_{0}}$
for the maximal number of linear regions for a fully connected neural network
with input dimension $n_{0}$ and $L$ hidden layers of width $n_{1}$,
$n_{2}$,…, $n_{L}$. Based on these results, they concluded that deep fully-
connected ReLU NNs have exponentially more maximal linear regions than the
shallow counterparts with asymptotically the same number of parameters. The
exact number of linear regions for one-layer CNNs with input dimension
$n_{0}^{(1)}\times n_{0}^{(2)}\times d_{0}$ and output dimension
$n_{1}^{(1)}\times n_{1}^{(2)}\times d_{1}$ was first proposed[5]. In their
work, they translate the problem of counting the linear regions of CNNs to a
problem on counting the regions of some class of hyperplane arrangements which
usually are not in general position, and develop a generalized Zaslavsky’s
theorem to solve this problem. Furthermore, they proposed a lower bound
$R_{\mathcal{N}^{\prime}}\prod_{l=1}^{L-1}\lfloor\frac{d_{l}}{d_{0}}\rfloor^{n_{l}^{(1)}\times
n_{l}^{(2)}\times d_{0}}$ ($R_{\mathcal{N}}$ is the number of linear regions
for the one-layer CNN with input dimension $n_{L-1}^{(1)}\times
n_{L-1}^{(2)}\times d_{L-1}$ and output dimension $n_{L}^{(1)}\times
n_{L}^{(2)}\times d_{L}$. ) for the maximal number of linear regions for a
fully connected neural network with input dimension $n_{0}^{(1)}\times
n_{0}^{(2)}\times d_{0}$ and $L$ hidden layers size $n_{1}^{(1)}\times
n_{1}^{(2)}\times d_{1}$, $n_{2}^{(1)}\times n_{2}^{(2)}\times d_{2}$,…,
$n_{L}^{(1)}\times n_{L}^{(2)}\times d_{L}$. Based on these results, they
concluded that deep fully-connected ReLU CNNs have exponentially more maximal
linear regions than their shallow counterparts with asymptotically the same
number of parameters. Besides, they also compared the expressive power of deep
ReLU CNNs with deep fully-connected ReLU NNs on some assumptions of the
network architecture and found that there are more linear regions in the input
space of deep ReLU CNNs than the deep ReLU NNs.

The exact number of linear regions for GNNs is reported in 2021 [46]. They
focus on one-layer GNNs without bias and translate the problem of counting the
linear regions of CNNs to a problem on counting the regions of some class of
hyperplane arrangements in general position. They also obtained that the
regions of an arrangement $\mathcal{A}$ of $M$ hyperplanes in $\mathbb{R}^{N}$
is equal to $2\sum_{j=0}^{N-1}\tbinom{M-1}{j}$. Compared to [46], we consider
a general case of bias for GCNs, and prove the lower and upper bounds of the
maximal number of linear regions of multilayer GCNs.

#### WL Tests for GNN Expressiveness

[47] gave a thorough study of the expressiveness and approximation properties
of GNNs in terms of the separation power and WL-test. For the expressivity of
GNNs, WL-tests are designed. The Weisfeiler-Lehman algorithm [48] was first
proposed to solve the graph isomorphism problem. The properties of these WL
algorithms are also investigated [49, 50]. Later, $k$-WL and $k$-FWL
algorithms were proposed and proved to be more powerful or efficient. For
instance, $\forall k\geq 2$, $k$-FWL is as powerful as $(k+1)$-WL and
$(k+1)$-WL is strictly more powerful than $k$-WL [51, 52]. [53, 54] have
proved that if there exist two graphs $G$ and $H$ that are possibly isomorphic
from the output of $1$-WL algorithm, the embeddings computed by GNNs must be
the same. For any two graphs $G$ and $H$ that are non-isomorphic according to
the $k$-WL algorithm, there would exist a $k$-GNN computing different
embeddings $h_{G}$ and $h_{H}$ [54]. For higher order graph neural networks,
$k$-WL algorithm could also be a standard criterion for the expressive power
of GNNs and more neural networks on simplicial complexes [55, 56, 46, 57].
These works could describe the expressive power of a GNN by its ability of
distinguishing different graphs.

##  8 Discussion

We focus on the number of linear regions of GCNs with non-zero biases. We give
the exact formula for the maximal and average number of linear regions for
one-layer GCNs and the upper and lower bounds for multi-layer GCNs. By these
results, we compare the number of linear regions per parameter between deep
GCNs and their shallow counterparts and among deep GCNs, CNNs and fully
connected NNs. It turns out that deep GCNs have more expressivity than shallow
GCNs.

We finally propose several potential directions related to the current work.
1) From table 2, we can find that the stochastic sampling result is close to
the lower bound but far from the upper bound. Thus, we seek for tighter bounds
or exact formulas. 2) We obtain the formula for the expectation of the number
of linear regions for one-layer ReLU GCNs, which is the same as the maximal
number. When the number of layers for a fully connected NN is greater than
one, it has been proved in [37] that the expectation of the number of linear
regions is usually much smaller than the maximal number. It is interesting to
derive similar formulas for the expectation of the number of linear regions
for multi-layer GCNs. 3) We only consider the number of linear regions for
GCNs which is one typical type of GNNs. However, there have been proposed many
kinds of GNN models with various graph feature extraction modules including
convolutions and message passing. To extend the results of the paper to other
graph convolutions or neural message passing is one direction to pursue.

## References

  * [1] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  IEEE Transactions on Neural Networks, 20(1):61–80, 2008.
  * [2] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio.  Deep learning, volume 1.  MIT Press, 2016.
  * [3] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In ICML, pages 1263–1272, 2017.
  * [4] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio.  On the number of linear regions of deep neural networks.  MIT Press, 2014.
  * [5] Huan Xiong, L. Huang, M. Yu, L. Liu, Fan Zhu, and Ling Shao.  On the number of linear regions of convolutional neural networks.  In ICML, 2020.
  * [6] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In ICLR, 2017.
  * [7] Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al.  Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups.  IEEE Signal Processing Magazine, 29(6):82–97, 2012.
  * [8] Ian Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio.  Maxout networks.  In ICML, pages 1319–1327, 2013.
  * [9] Ossama Abdel-Hamid, Abdel-rahman Mohamed, Hui Jiang, Li Deng, Gerald Penn, and Dong Yu.  Convolutional neural networks for speech recognition.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 22(10):1533–1545, 2014.
  * [10] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  Nature, 529(7587):484–489, 2016.
  * [11] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NeurIPS, pages 5998–6008, 2017.
  * [12] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang.  Lightgcn: Simplifying and powering graph convolution network for recommendation.  In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 639–648, 2020.
  * [13] Yu Zheng, Chen Gao, Xiang Li, Xiangnan He, Yong Li, and Depeng Jin.  Disentangling user interest and conformity for recommendation with causal embedding.  In Proceedings of the Web Conference 2021, pages 2980–2991, 2021\.
  * [14] Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  Neural Networks, 4:251–257, 1991.
  * [15] Andrew R Barron.  Approximation and estimation bounds for artificial neural networks.  Machine Learning, 14(1):115–133, 1994.
  * [16] Boris Hanin and Mark Sellke.  Approximating continuous functions by relu nets of minimal width.  arXiv preprint arXiv:1710.11278, 2017.
  * [17] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang.  The expressive power of neural networks: A view from the width.  In NeurIPS, volume 30, 2017.
  * [18] Dmitry Yarotsky.  Error bounds for approximations with deep relu networks.  Neural Networks, 94:103–114, 2017.
  * [19] M. Telgarsky.  Representation benefits of deep feedforward networks.  Computer Science, 15(8):1204–1211, 2015.
  * [20] Razvan Pascanu, Guido Montúfar, and Yoshua Bengio.  On the number of response regions of deep feed forward networks with piece-wise linear activations.  In ICLR, 2013.
  * [21] Wuyang Chen, Xinyu Gong, and Zhangyang Wang.  Neural architecture search on ImageNet in four GPU hours: A theoretically inspired perspective.  In ICLR, 2021.
  * [22] Ilan Price and Jared Tanner.  Trajectory growth lower bounds for random sparse deep ReLU networks.  In 20th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 1004–1009, 2021.
  * [23] Boris Hanin, Ryan S Jeong, and David Rolnick.  Deep ReLU networks preserve expected length.  In ICLR, 2022.
  * [24] Vladimir N Vapnik and A Ya Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In Measures of Complexity, pages 11–30. Springer, 2015.
  * [25] William H Guss and Ruslan Salakhutdinov.  On characterizing the capacity of neural networks using algebraic topology.  arXiv preprint arXiv:1802.04443, 2018.
  * [26] Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes.  Fisher-rao metric, geometry, and complexity of neural networks.  In AISTATS, pages 888–896, 2019.
  * [27] Richard HR Hahnloser, Rahul Sarpeshkar, Misha A Mahowald, Rodney J Douglas, and H Sebastian Seung.  Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit.  Nature, 405(6789):947–951, 2000.
  * [28] Richard Hahnloser and H Sebastian Seung.  Permitted and forbidden sets in symmetric threshold-linear networks.  In NeurIPS, volume 13, 2000.
  * [29] Xavier Glorot, Antoine Bordes, and Yoshua Bengio.  Deep sparse rectifier neural networks.  In AISTATS, pages 315–323, 2011.
  * [30] Quynh Nguyen, Marco Mondelli, and Guido Montúfar.  Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks.  In ICML, 2021.
  * [31] Ingo Steinwart.  A sober look at neural network initializations.  CoRR, abs/1903.11482, 2019.
  * [32] Mary Phuong and Christoph H. Lampert.  Functional vs. parametric equivalence of ReLU networks.  In ICLR, 2020.
  * [33] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam.  Bounding and counting linear regions of deep neural networks.  In ICML, pages 4558–4566, 2018.
  * [34] Peter Hinz and Sara Geer.  A framework for the construction of upper bounds on the number of affine linear regions of relu feed-forward neural networks.  IEEE Transactions on Information Theory, PP:1–1, 07 2019.
  * [35] Peter Hinz.  Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networks.  arXiv preprint arXiv:2103.17174, 2021.
  * [36] Boris Hanin and David Rolnick.  Complexity of linear regions in deep networks.  In ICML, pages 2596–2604, 2019.
  * [37] Boris Hanin and David Rolnick.  Deep ReLU networks have surprisingly few activation patterns.  In NeurIPS, volume 32, 2019.
  * [38] Hanna Tseran and Guido F Montúfar.  On the expected complexity of maxout networks.  In NeurIPS, volume 34, 2021.
  * [39] Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim.  Tropical geometry of deep neural networks.  In ICML, pages 5824–5832, 2018.
  * [40] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In ICML, pages 2847–2854, 2017.
  * [41] Randall Balestriero, Romain Cosentino, Behnaam Aazhang, and Richard Baraniuk.  The geometry of deep networks: Power diagram subdivision.  In NeurIPS, volume 32, 2019.
  * [42] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University Press, USA, 1 edition, 2009.
  * [43] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In ICCV, pages 1026–1034, 2015.
  * [44] Thomas Zaslavsky.  Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes: Face-count formulas for partitions of space by hyperplanes, volume 154.  American Mathematical Soc., 1975.
  * [45] Richard P Stanley et al.  An introduction to hyperplane arrangements.  Geometric combinatorics, 13(389-496):24, 2004.
  * [46] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montúfar, Pietro Liò, and Michael Bronstein.  Weisfeiler and Lehman go topological: Message passing simplicial networks.  In ICML, pages 1026–1037, 2021.
  * [47] Floris Geerts and Juan L Reutter.  Expressiveness and approximation properties of graph neural networks.  In ICLR, 2022.
  * [48] Boris Weisfeiler and Andrei Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  NTI, Series, 2(9):12–16, 1968.
  * [49] László Babai, Paul Erdos, and Stanley M Selkow.  Random graph isomorphism.  SIAM Journal on Computing, 9(3):628–635, 1980.
  * [50] Jin-Yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Combinatorica, 12(4):389–410, 1992.
  * [51] Martin Grohe and Martin Otto.  Pebble games and linear equations.  The Journal of Symbolic Logic, 80(3):797–844, 2015.
  * [52] Martin Grohe.  Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47.  Cambridge University Press, 2017.
  * [53] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In ICLR, 2019.
  * [54] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and Leman go neural: Higher-order graph neural networks.  In AAAI, volume 33, pages 4602–4609, 2019.
  * [55] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman.  Provably powerful graph networks.  In NeurIPS, volume 32, 2019.
  * [56] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna.  Can graph neural networks count substructures?  In NeurIPS, volume 33, pages 10383–10395, 2020.
  * [57] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido F Montufar, and Michael Bronstein.  Weisfeiler and Lehman go cellular: CW networks.  In NeurIPS, volume 34, pages 2625–2640, 2021.

##  Appendix A Proof of the Number of Linear Regions for One-Layer GCNs

###  A.1 Proof of Theorem 1

To prove Theorem 1, we need the following result from [5].

######  Lemma 7 ([5]).

Let m, n be some positive integers, $V=\mathbb{R}^{n}$, $V_{1}$,
$V_{2}$,…$V_{m}$ be m non-empty subspaces of $V$, and $n_{1}$,
$n_{2}$,…$n_{m}$ be some nonnegative integers. Let $\mathcal{A}=\\{H_{kj},\
1\leq k\leq n,\ 1\leq j\leq n_{i}\\}$ be an arrangement in $\mathbb{R}^{n}$
with $H_{kj}={X:\alpha X=b_{kj}}$ where $\boldsymbol{0}\neq\alpha_{kj}\in
V_{k}$, $b_{kj}\in\mathbb{R}$. Then, the number of linear regions for the
arrangement $\mathcal{A}$ satisfies

$r(\mathcal{A})\leq\sum_{(i_{1},\ i_{2},\ \dots,\ i_{m})\in K_{V;V_{1},\
V_{2},\ \dots,\ V_{m}}}\prod_{k=1}^{m}\tbinom{n_{k}}{i_{k}},$ (13)

where

$K_{V;V_{1},V_{2},\dots,V_{m}}=\left\\{(i_{1},i_{2},\dots,i_{m}):\
i_{k}\in\mathbb{N},\ \sum_{k\in J}i_{k}\leq{\rm dim}(\sum_{i\in
J}V_{k})\;\forall J\subseteq[m]\right\\}.$

Furthermore, assume that the two conditions hold for the arrangement
$\mathcal{A}$:

(i) For each $(i_{1},\ i_{2},\ \dots,\ i_{m})\in K_{V;V_{1},\ V_{2},\ \dots,\
V_{m}}$, any $\sum_{k=1}^{m}i_{k}$ vectors with $i_{k}$ distinct vectors
chosen from the set $\\{\alpha_{kj}:\ 1\leq j\leq n_{k}\\}$ are linearly
independent;

(ii) For each $(i_{1},i_{2},\dots,i_{m})\in\mathbb{N}^{m}\backslash
K_{V;V_{1},V_{2},\dots,V_{m}}$, the intersection of any $\sum_{k=1}^{m}i_{k}$
hyperplanes with $i_{k}$ distinct hyperplanes chosen from the set
$\\{H_{kj}:1\leq j\leq n_{k}\\}$ are empty.

Then, the equality in (13) holds:

$r(\mathcal{A})=\sum_{(i_{1},i_{2},\dots,i_{m})\in
K_{V;V_{1},V_{2},\dots,V_{m}}}\prod_{k=1}^{m}\tbinom{n_{k}}{i_{k}}.$ (14)

Now, we could give proofs of Theorem 1 and Proposition 2.

###### Proof of Theorem 1.

Assume that $\mathcal{N}$ is a one-layer GCN with input dimension $D\times N$
like this:

$X^{(1)}=h(\hat{A}X^{(0)}W),$ (15)

where $\hat{A}\in\mathbb{R}^{D\times D}$, $W\in\mathbb{R}^{N\times
N^{\prime}}$ and $h$ is the activation function. Let
$V_{1,1},V_{1,2},...,V_{D^{*}N^{\prime}}$ be subspaces of
$V=\mathbb{R}^{D^{*}\times N}$. Suppose $\mathcal{A}=\\{H_{ijk},1\leq i\leq
D^{*},1\leq j\leq N^{\prime},1\leq k\leq q\\}$ is an arrangement in $V$ with
$H_{ijk}=\\{X:\left<\alpha_{ij},X\right>_{F}+b_{ij}=e_{k}\\}$, where
$\alpha_{ij}=a_{i}^{\top}w_{j}^{\top}\in V_{ij}$ and $a_{i}$ is the $i$-th row
of $\hat{A}$ and $w_{j}$ is $j$-th column of $W,$ and $\left<,\right>_{F}$ is
the Frobenius inner product. Then, ${\rm dim}(V_{ij})=1$ and ${\rm
dim}(\Sigma_{i\in I,\ j\in J}V_{ij})={\rm rank}((w_{j}^{\top}),j\in
J)\times{\rm rank}((a_{i}^{\top}),i\in I)$, $\forall J\subseteq[D^{*}],\
I\subseteq[N^{\prime}]$. We thus obtain

$K_{\mathcal{N},\theta}:=\\{(k_{1,1},k_{1,2},...,k_{D^{*}N^{\prime}}):k_{ij}\in\mathbb{N},\sum_{i\in
I,\ j\in J}k_{ij}\leq{\rm
dim}(\sum_{k_{ij}=1}V_{ij}),\forall(i,j)\in[D^{*}]\times[N^{\prime}].$ (16)

From the definition of arrangement $\mathcal{A}$, the number of linear regions
for $\mathcal{A}$ is equal to the number of linear regions for the input space
of $\mathcal{N}$. The maximal number of linear region of $\mathcal{N}$ is then

$R_{\mathcal{N},\theta}\leq\sum\limits_{(k_{1,1},...,k_{DN^{\prime}})\in
K_{\mathcal{N}}}\prod\limits_{(i,j)\in[D^{*}]\times[N^{\prime}]}^{D}\binom{1}{k_{ij}}=\\#K_{\mathcal{N}}.$
(17)

∎

###### Proof of Proposition 2.

By Lemma 2, all row vectors in $\tilde{A}$ are linearly independent. Then, if
the distinct vectors $\alpha_{ij}$ are linearly independent, for any chosen
index $i$ in $\alpha_{ij}$ (assuming that $J^{*}_{i}$ is the index set for all
$j$), the vectors $w_{j}$ in $\alpha_{ij}$ are linearly independent. On the
other hand, for any chosen $i$, if the vectors $w_{j}$ (for all $j\in
J^{*}_{i}$) are linearly independent, the vectors $\alpha_{ij}$ for all $i$
and $j$ are linearly independent. Otherwise, we could assume that $\exists\
k_{ij}$ that are not all zero could make $\sum_{i=1}\sum_{j\in
J^{*}_{i}}k_{ij}a^{\top}_{i}w^{\top}_{j}=0$. Therefore, $\forall\ i,\
\sum_{j\in J^{*}_{i}}k_{ij}w^{\top}_{j}=0$ and this is contrary to the fact
that for all the vectors $w_{j}$ (for all $j\in J^{*}_{i}$) are linearly
independent.

We then obtain if and only if there are a group of $\alpha_{ij}$ linearly
independent, the corresponding group of $W_{j}$ (for all $j$ in $J^{*}$) are
linearly independent. Besides, since $k_{ij}\in\\{0,1\\}$, the number of the
elements of $K_{\mathcal{N},\theta}$ is equivalent to the number of ways of
choosing a group of independent vectors from all $\alpha_{ij}$.

(i) Since the rank of $W$ is $N^{\prime}$, the column vectors in $W$ are
linearly independent. If $\mathrm{rank}(W)\textless N^{\prime}$, not all
$\alpha_{ij}$ are linearly independent, which indicates that there will be
less elements in $K_{\mathcal{N},\theta}$. We thus obtain that
$\\#K_{\mathcal{N},\theta}=2^{D^{*}N^{\prime}}$.

(ii) If any $N$ column vectors in $W$ are linearly independent, we could
choose at most $N$ column vectors from $W$ so that all the corresponding
$\alpha_{ij}$ are linearly independent. If not, there will be less elements in
$K_{\mathcal{N},\theta}$. This implies that

$\\#K_{\mathcal{N},\theta}=\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}.$

∎

###  A.2 Proof of Theorem 2

To prove Theorem 2, we need to show that when the rows $\hat{A}$ are linearly
independent to each other and $\text{rank}(W)=\text{min}(N,N^{\prime})$, the
condition 1 and condition 2 are satisfied, which means the equality in theorem
can be achieved. Next, we need to prove that when we take away all the
repeated rows of $\hat{A}$, the left rows are linearly independent. Moreover,
it is not difficult to check that if $W$ and $B$ are drawn from a distribution
which has densities with respect to Lebesgue measure in
$\mathbb{R}^{\\#weights+\\#biases},$ the set of $W$ with
$\text{rank}(W)=\text{min}(N,N^{\prime})$ is a complement of a measure-zero
set with respect to the Lebesgue measure on $\mathbb{R}^{\\#{\rm weights}}$.
To achieve these, we need Lemmas 2 to 5, which we prove now.

###### Proof of Lemma 2.

If we can find one row vector of $\tilde{A}$ denoted as $\alpha_{k}$ such that

$\alpha_{k}=\sum\limits_{i\in S}a_{i}\alpha_{i},$

where $\alpha_{i}$ is the $i$-th row of $\tilde{A}$ and $a_{i}>0$. Since the
element of $\tilde{A}$ is either 1 or 0 and $\tilde{A}_{ii}=1$, we obtain that
$\tilde{A}_{ki}=1$. Moreover, as $\tilde{A}$ is symmetric, $\tilde{A}_{ik}=1$.
Thus $\sum\limits_{i\in S}a_{i}=1$. Now we claim that for any $j$ that
$\tilde{A}_{kj}=1$, $\tilde{A}_{ij}=1\ \forall i\in S$ and that for any $j$
that $\tilde{A}_{kj}=0$, $\tilde{A}_{ij}=0$. Therefore,
$\alpha_{k}=\alpha_{i}\ \forall\ i\in S$, which is contrary to the hypothesis.
Then, $\tilde{A}$ is invertible. We can then check that if we eliminate the
duplicate rows of $\tilde{A}$, the left row vectors are linearly independent.
∎

###### Proof of Lemma 3.

Without loss of generality, let $N\geq N^{\prime}$. Suppose that $W_{0}$ be
the first $N^{\prime}$ rows of $W$. Consider the set
$\mathcal{W}=\\{W\in\mathbb{R}^{N\times N^{\prime}}:\ W_{0}\ \text{is}\
\text{not}\ \text{invertible}\\}$. From Lemma 6 in [5], $\mathcal{W}$ is a
Lebesgue measure-zero set in $\mathbb{R}^{N\times N^{\prime}}$. Then, for any
given $N$ and $N^{\prime}$, all $W$ such that the matrix consisting of any
$N^{\prime}$ rows of $W$ is not invertible form a measure zero set. On the
other hand, if the matrix formed by any $N^{\prime}$ rows of $W$ is not
invertible, $\mathrm{rank}(W)\textless\text{min}(N,N^{\prime})$. Then, all $W$
such that $\mathrm{rank}(W)\textless\text{min}(N,N^{\prime})$ form a null set
in $\mathbb{R}^{N\times N^{\prime}}$. ∎

###### Proof of Lemma 4.

Since there are $N$ column vectors in $W$ that are linearly dependent, there
exists a $w_{i_{0}}$ in these $N$ vectors that could be linearly expressed as
the linear sum of the other $N-1$ vectors. Therefore, from Lemma 6 in [5], all
the matrices consisting of these $N$ vectors form a measure zero set in
$\mathbb{R}^{N\times N}$. This implies that all $W$ form a null zero set in
$\mathbb{R}^{N\times N}$. ∎

###### Proof of Lemma 5.

Denote the set of $(W,B)$ as $E$. Let the $(X_{1},\mathcal{B}_{1},\mu_{1})$,
$(X_{1},\mathcal{B}_{1},\mu_{1})$ be Lebesgue measure space. Let
$X_{1}=\mathbb{R}^{N\times N^{\prime}}$ and $X_{2}=\mathbb{R}^{D\times
N^{\prime}}$. Then, $W\in X_{1}$, $B\in X_{2}$ and $E\in X_{1}\times X_{2}$.
Let $\mu_{1}$ and $\mu_{2}$ be two Lebesgue measures,
$\mu=\mu_{1}\times\mu_{2}$ and $E^{W}=\\{B:(W,B)\in E\\}$. Then,
$\mu(E^{W})=0$. We thus obtain $\mu(E)=\int\mu_{1}(E^{W})d\mu_{2}=0$. ∎

###### Proof of Theorem 2.

With Theorem 1, we only need to consider the two conditions in Lemma 7.

Condition (i): If we choose $\sum_{i,j}a_{ij}$ vectors with $a_{ij}$ vectors
from $V_{ij}$, and $\sum_{i,j}a_{ij}\leq{\rm dim}(\sum_{i,j}V_{ij})$, these
vectors are linearly independent.

Condition (ii): Let $A^{*}=\\{\alpha_{ij}:\;H_{ij}\;\hbox{~{}is~{}chosen}\\}$,
$B^{*}=\\{b_{j}:H_{ij}\;\hbox{~{}is~{}chosen}\\}$,
$I_{H}=\\{(i,j):\;H_{ij}\;\hbox{~{}is~{}chosen}\\}$. Then, the intersection of
the chosen hyperplanes is empty is equivalent to say that there is no solution
to the linear functions $\left\langle\alpha_{ij},X\right\rangle_{F}=b_{j}$.
The linear functions could be turned into the matrix form $E\cdot{\rm
vec}(X)=B$ with $E$ consisting of all the vectorized $\alpha_{ij}$. Due to the
way of choosing $H_{ij}$, the rank of $E$ is less than its row number.
Therefore, there exists a vector $\rho_{E}=(r_{1,1},\dots,r_{ij},\dots)$ such
that $\sum_{(i,j)\in I_{H}}r_{ij}\alpha_{ij}=0$. For any $i$ that $(i,j)\in
I_{H},$ we then have

$\sum_{j}r_{ij}a_{i}^{\top}w_{j}^{\top}=a_{i}^{\top}(\sum_{j}r_{ij}w_{j}^{\top})=0.$

Since the row vectors in $\tilde{A}$ are linearly independent,
$\sum_{j}r_{ij}b_{j}=0$. This shows that the set of all $(W,B)$ that satisfies
condition (ii) is a complement of Lebesgue null set in $\mathbb{R}^{\\#{\rm
weights}+\\#{\rm biases}}$. When the parameters $\theta$ are in a complement
of Lebesgue measure-zero set in $\mathbb{R}^{\\#{\rm weights}+\\#{\rm
biases}}$, $R_{\mathcal{N},\theta}=K_{\mathcal{N},\theta}$. Moreover, by Lemma
4 and Lemma 3, all the $(W,B)$ that does not satisfy the two conditions in
Proposition 2 also form a measure-zero set in $\mathbb{R}^{(N+1)\times
N^{\prime}}$. This indicates

$E_{\theta\sim\mu}(R_{\mathcal{N},\theta})=\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}.$

∎

###  A.3 Proof of Theorem 3

###### Proof of Theorem 3.

By Theorem 2,

$R_{\mathcal{N},\theta}=\left(\sum_{i=0}^{N}\tbinom{N^{\prime}}{i}\right)^{D^{*}}.$

Since $N^{\prime}$ tends to infinity and $N=\Theta(1)$,
$\tbinom{N^{\prime}}{N}=\Theta({N^{\prime}}^{N})$ and
$\tbinom{N^{\prime}}{i}=\Theta({N^{\prime}}^{i})$, which gives

$R_{\mathcal{N},\theta}=\Theta({N^{\prime}}^{DN}).$

∎

##  Appendix B Proof of Linear Regions for Multi-Layer GCNs

Let $\mathcal{N}$ be a GCN with $L$ hidden convolutional layers. Suppose that
there are $N_{0}$ input features and $N_{l}$ output features in the $l$-th
layer. First of all, we give the proof of the upper bound.

###### Proof of Theorem 4(i).

First, when $L=1$, the inequality holds in (9). Now suppose that $L\geq 2$ and
that the inequality is true for $L-1$. Let $\mathcal{N}^{*}$ be the GCN
consist the first $L-1$ layers of $\mathcal{N}$. Then, it can calculated that

$R_{\mathcal{N}^{*}}\leq
R_{\mathcal{N}^{\prime\prime}}\prod\limits_{l=2}^{L-1}\left(\sum\limits_{i=0}^{DN}\tbinom{DN_{l}}{i}\right).$

Suppose that the first $L-1$ layers divide the input space into $m$ distinct
linear regions $R_{i}$ ($1\leq i\leq m$). Let $\mathcal{F}_{\mathcal{N}}$ be
the function represented by $\mathcal{N}$ and $\mathcal{F}_{\mathcal{N}^{*}}$
be the function represented by $\mathcal{N}^{*}$. When restricted into
$\mathbb{R}_{i}$, $\mathcal{F}_{\mathcal{N}^{*}}$ is a linear function and
$\mathcal{F}_{\mathcal{N}}$ is a composition of
$\mathcal{F}_{\mathcal{N}^{*}}$ and the function represented by the last layer
which is a composition of linear function and activation function. Therefore,
$\mathcal{N}$ could be represented as a one-layer fully connected neural
network with input dimension $D\times N_{0}$ and the output dimension $D\times
N_{L}$. We thus obtain

$R_{\mathcal{N}}\leq
R_{\mathcal{N}^{*}}\left(\sum\limits_{i=0}^{DN}\tbinom{DN_{L}}{i}\right)\leq
R_{\mathcal{N}^{\prime\prime}}\prod\limits_{l=2}^{L}\left(\sum\limits_{i=0}^{DN}\tbinom{DN_{l}}{i}\right).$

∎

Before starting the proof of the lower bound, we need several lemmas.

######  Lemma 8.

An eigenvalue of $\hat{A}$ is 1 and one of the corresponding eigenvector is
$M^{\frac{1}{2}}J$, where $J$ is a vector with all elements equal to 1. This
implies that all elements in the eigenvector $M^{\frac{1}{2}}J$ are
nonnegative.

###### Proof.

Denote $\lambda$ as an eigenvalue and $x$ as the corresponding eigenvector. We
then have $\hat{A}x=\lambda x$. Let $y=M^{\frac{1}{2}}x$. Then,
$M^{-1}(A+I)y=\lambda y$, and we could let $\lambda=1$ and $y=J$. Thus,
$x=M^{\frac{1}{2}}J$. ∎

###### Proof of Theorem 4(ii).

Now we are ready to prove the lower bound. Consider the ReLU GCN model

$X^{(l+1)}=h(\hat{A}X^{(l)}W),$ (18)

where $\hat{A}=M^{-\frac{1}{2}}(A+I)M^{-\frac{1}{2}}$ and $M={\rm
diag}\bigl{(}\sum\limits_{j=1}^{D}(A_{ij}+1),\>i=1,2,...,D\bigr{)}$. We now
prove the lower bound by constructing a specific multi-layer GCN that meets
the lower bound. As $N_{1}\geq N$, we can divide $N_{l}$ into $N$ parts:
$n_{l}^{(k)}$, $k=1,2,...,N$, $\sum\limits_{k=1}^{N}n_{l}^{(k)}=N_{l}$ and
$n_{l}^{(k)}\geq 1$. For simplicity, we let
$n_{l}^{(k)}=\left\lfloor\frac{N_{l}}{N}\right\rfloor$ denoted as $p$. We then
let

$W_{a,b}^{l}=\left\\{\begin{array}[]{ccll}p,&&a=k,\;b=p(k-1)+1,&k=1,2,...,N,\\\\[2.84526pt]
2p,&&a=k,\;p(k-1)+2\leq b\leq pk,&k=1,2,...,N,\\\\[2.84526pt]
0,&&\hbox{otherwise},&\\\ \end{array}\right.$ (19)

and

$B_{a,b}^{l}=-2(m-1)\sqrt{r_{a}},\quad b=p(k-1)+m,\quad k=1,2,...,N,\quad
m=1,2,...,p,$ (20)

where $r_{a}$ is the ($a,a$)-th entry of the matrix $R$.

Denote $Y^{(l)}=\hat{A}X^{(l)}=(Y_{1},...,Y_{N})$. Then,

$Z^{l}_{a,b}=\left\\{\begin{array}[]{cclll}pY^{(l)}_{a,b},&&a=k,&b=p(k-1)+1&k=1,2,...,N,\\\\[2.84526pt]
2(pY^{(l)}_{a,b}-(m-1)\sqrt{r_{a}}),&&b=p(k-1)+m,&k=1,2,...,N,&m=1,2,...,p,\\\\[2.84526pt]
0,&&otherwise.&&\\\ \end{array}\right.$ (21)

The map $X^{(l+1)}=\max\\{0,Z^{l}_{a,b}\\}$ defines a function
$X^{(l+1)}=\Phi_{l+1}(X^{(l)})$.

Next, we define an intermediate linear layer without activation function from
$X^{(l)}$ to $X^{(l+1)}$ to $U^{(l+1)}$. We define weights by

$W_{a,b}^{*l}=\left\\{\begin{array}[]{cclll}(-1)^{m+1},&&a=p(k-1)+m&k=1,2,...,N&m=1,2,...,p,\\\\[2.84526pt]
0,&&\hbox{otherwise}&&\\\ \end{array}\right.$ (22)

and $B^{*l}=0$. We then have the equation

$U^{(l+1)}_{a,b}=\sum\limits_{j=1}^{p}(-1)^{j+1}X^{(l+1)}_{a,(b-1)p+j},$ (23)

which defines an affine function

$Y_{l+1}=\Phi^{*}_{1}(X_{l+1}).$ (24)

For each $i,j\in\mathbb{N^{+}}$, let

$\psi_{i}^{c}(x)=\left\\{\begin{array}[]{ccl}\max\\{0,x\\},&i=1,\\\\[2.84526pt]
\max\\{0,2x-(2i-2c)\\}&i\geq 2,\\\ \end{array}\right.$ (25)

where $c$ is a constant, and we let

$\phi_{j}^{c}(x)=\sum\limits_{i=1}^{j}\psi_{i}^{c}(jx).$ (26)

It can be checked that

$\phi_{j}^{c}(x)=\left\\{\begin{array}[]{ccl}0&i=1,\\\\[2.84526pt]
jx-i&\frac{i}{j}c\leq x\leq\frac{i+1}{j}c,\\\\[2.84526pt]
i-jx&\frac{i-1}{j}c\leq x\leq\frac{i}{j}c.\\\ \end{array}\right.$ (27)

Then, $\phi_{j}$ is a linear function when $x$ is restricted to the interval
$\left[0,\frac{1}{j}c\right],$ $\left[\frac{1}{j}c,\frac{2}{j}c\right],\dots$
$,\left[\frac{j-1}{j}c,c\right]$ and

$\phi_{j}\left(\left[\frac{i}{j}c,\frac{i+1}{j}c\right]\right)=\left[0,c\right].$

It can verified that $U^{(l+1)}_{a,b}=\phi_{p}^{\sqrt{r_{a}}}(Y^{(l)}_{a,b})$
and this determines the mapping

$\Psi_{l+1}=\Phi^{*}_{l+1}\circ\Phi_{l+1}\circ\mathscr{A},$

where $\mathscr{A}$: $X\rightarrow AX$. Since $\mathscr{A}$ sends
$\prod\limits_{i=1}^{D}\left[0,\sqrt{r_{i}}\right]$ into
$\prod\limits_{i=1}^{D}\left[0,\sqrt{r_{i}}\right]$ , the $\Psi_{l+1}$ sends
$p^{N\cdot\text{rank}(A)}$ distinct linear regions in the original space

$\prod\limits_{i=1}^{D}\left\\{\left[0,\frac{1}{p}\sqrt{r_{i}}\right],\left[\frac{1}{p}\sqrt{r_{i}},\frac{2}{p}\sqrt{r_{i}}\right],...,\left[\frac{p-1}{p}\sqrt{r_{i}},\sqrt{r_{i}}\right]\right\\}^{N}$

in $\prod\limits_{i=1}^{D}\left[0,\sqrt{r_{i}}\right]^{N}$ onto the same
hypercubes. We can use similar mappings $\Psi_{1}$, $\Psi_{2},\dots$, and
$\Psi_{L}$ to send the $p^{N\cdot\text{rank}(A)}$ distinct linear regions in
the input space onto the same hypercubes
$\prod\limits_{i=1}^{D}\left[0,\sqrt{r_{i}}\right]^{N}$. The left part of the
network is a one-layer ReLU GCN with $D$ nodes and $N$ input features.

Also, a one-layer ReLU GCN with $D$ nodes and $N$ features for each node and
output dimension $D\times N_{L}$ can partition the hypercube
$\prod\limits_{i=1}^{D}\left[0,\sqrt{r_{i}}\right]^{N}$ into
$R_{\mathcal{N^{\prime}}}$ regions. Putting the networks from $X^{(0)}$ to
$U^{(L-1)}$ and $U^{(L-1)}$ to $X^{(L)}$ together, we obtain the lower bound
in (9). ∎

##  Appendix C Experiments

#### Details on Figure 1

We consider the two-layer and three layer GCN with one input feature and three
nodes in the graph. We choose a 2D slice of the input space and show the
linear regions in it. The 2D slice is determined by three random points. We
choose 90000 points uniformly in $[-10,10]^{2}$ from the slice and evaluate
the gradient of each point. Then we plot the gradient of each point using
colors determined by the gradient. Therefore, the region with the same color
is the region with the same gradient and could be considered as one linear
region in the slice.

#### Estimate for Linear Regions of GCNs with 1 and 2 layers

Suppose that the adjacency matrix is

$\tilde{A}=\left(\begin{matrix}\frac{1}{3}&\frac{1}{\sqrt{6}}&\frac{1}{\sqrt{6}}\\\
\frac{1}{\sqrt{6}}&\frac{1}{2}&0\\\
\frac{1}{\sqrt{6}}&0&\frac{1}{2}\end{matrix}\right).$ (28)

For 1-layer GCN with 1 input feature and $N_{1}$ output features, from (6),
$R_{\mathcal{N}}=\left(\frac{N_{1}^{2}}{2}+\frac{N_{1}}{2}+1\right)^{3}$
almost surely. The upper bounds in Proposition 1 and Lemma 1 are
$R_{\mathcal{N}}\leq\sum_{i=0}^{6}\tbinom{3N_{1}}{i}$ and $R_{\mathcal{N}}\leq
2^{3N_{1}}$. For the 2-layer GCN with 1 input feature and $N_{1}$ output
features for the first layer and 3 output features for the second layer, the
upper and lower bounds are given by
$343\left\lfloor\frac{N_{1}}{2}\right\rfloor^{3}\leq
R_{\mathcal{N}}\leq\left(\frac{N_{1}^{2}}{2}+\frac{N_{1}}{2}+1\right)^{3}\sum_{i=0}^{3N_{1}}\tbinom{3N_{1}}{i}$.

Figure 3: Bounds for GCNs with 1 layer (left) and 2 layers (right) on an input
graph which consists of 4 nodes and 3 edges. The adjacency matrix is shown in
(28). The left image shows the optimal upper bound (green) gained from Theorem
2, upper bound (orange) from Proposition 1 and the naive upper bound (blue)
from Lemma 1 for a 1-layer GCN with 2 input feature and $N_{1}$ output
features where $N_{1}$ ranges from 2 to 20. The right image shows the lower
bound (orange) and upper bound (blue) obtained from Theorem 4 for a 2-layer
GCN with 2 input feature and $N_{1}$ and 3 output features for the first and
second layers.


11institutetext:  Sapienza University of Rome 22institutetext: University of
Pisa 11institutetext: Sapienza University of Rome 22institutetext: University
of Pisa

# RRAML: Reinforced Retrieval Augmented Machine Learning

Anonymous Authors  Andrea Bacciu 11 Florin Cuconasu 11 Federico Siciliano 11
Fabrizio Silvestri 11 Nicola Tonellotto 22 Giovanni Trappolini
<EMAIL_ADDRESS>1111<EMAIL_ADDRESS>22

###### Abstract

The emergence of large language models (LLMs) has revolutionized machine
learning and related fields, showcasing remarkable abilities in comprehending,
generating, and manipulating human language. However, their conventional usage
through API-based text prompt submissions imposes certain limitations in terms
of context constraints and external source availability. LLMs suffer from the
problem of hallucinating text, and in the last year, several approaches have
been devised to overcome this issue: adding an external Knowledge Base or an
external memory consisting of embeddings stored and retrieved by vector
databases. In all the current approaches, though, the main issues are: (i)
they need to access an embedding model and then adapt it to the task they have
to solve; (ii) in case they have to optimize the embedding model, they need to
have access to the parameters of the LLM, which in many cases are “black
boxes”. To address these challenges, we propose a novel framework called
Reinforced Retrieval Augmented Machine Learning (RRAML). RRAML integrates the
reasoning capabilities of LLMs with supporting information retrieved by a
purpose-built retriever from a vast user-provided database. By leveraging
recent advancements in reinforcement learning, our method effectively
addresses several critical challenges. Firstly, it circumvents the need for
accessing LLM gradients. Secondly, our method alleviates the burden of
retraining LLMs for specific tasks, as it is often impractical or impossible
due to restricted access to the model and the computational intensity
involved. Additionally, we seamlessly link the retriever’s task with the
reasoner, mitigating hallucinations and reducing irrelevant and potentially
damaging retrieved documents. We believe that the research agenda outlined in
this paper has the potential to profoundly impact the field of AI,
democratizing access to and utilization of LLMs for a wide range of entities.

###### Keywords:

Deep Learning Information Retrieval Large Language Models.

##  1 Introduction

The advent of Large Language Models (LLMs) has brought about a paradigm shift
in machine learning and its related disciplines. LLMs [2, 20, 13, 24, 1] have
exhibited unprecedented capabilities in understanding, generating, and
manipulating the human language. Famously, ChatGPT [13] has entered the public
space by reaching one million users in a matter of days. The way these models
are usually used is through API that only allows submitting a textual prompt
and getting back from the server the generated text. However, this causes an
immediate limitation: all information must be passed through this context, and
we know transformer-based models do not scale nicely. Even if they did, API
costs are charged on the basis of their usage. Therefore, using long contexts
would be expensive. Even if one had the resources to run their own LLM, the
costs of training and of the hardware infrastructure, and the environmental
impact should be considered. There is an impendent need, though, to
accommodate the enormous power of those models to specific user needs by
making sure that they could use the reasoning capabilities of LLMs, through
in-context learning [2] on their data.
A solution is to adopt a retrieval-augmented approach [8, 26]. In this
setting, a retriever is used to filter out relevant information to be passed
as context to the reasoner. This generates a new problem, however, namely that
the retriever and the reasoner are not aligned [25, 22, 23]. In particular,
the retriever might not be trained on the task of interest to the user.
Moreover, the retriever might actually provide “dangerous” pieces of
information to the reasoner, as proved in [19], leading to poor results and,
more importantly, to hallucinations.

Ideally, one would have to fine-tune these models to account for these issues.
Within this setting, fine-tuning the model for a given task is technically
impossible. We asked ourselves: “Is it still possible to use the API that
gatekeeps those powerful LLMs on our data without the need for fine-tuning?”
We show that this question has a positive answer and in this paper, we propose
a novel framework, Reinforced Retrieval Augmented Machine Learning (RRAML), in
which we combine the reasoning capabilities of large foundational models
enhanced by the provision of supporting relevant information provided by a
retriever that searches them in a large database. In this setting, an
efficient retriever model is tasked to search for relevant information in an
arbitrarily large database of data provided by users. Once this set of
relevant data has been retrieved, it is forwarded to the reasoner (a large
foundational model such as ChatGPT, for instance) through its API to “reason”
on the input and produce an adequate result. In particular, we plan to
overcome current limitations, namely that the retriever’s task is detached
from that of the reasoner, reducing in such a way the tendency of LLM to
hallucinate and diminishing the number of damaging documents (as defined in
[3, 18, 25]) returned by the retriever. The approach we devise in this
research work exploits recent advances in reinforcement learning. Recently, in
fact, reinforcement learning techniques like PPO [21] have been used to
improve large foundational models with human feedback where the loss is non-
differentiable. We propose to link the training phase of the retriever to the
final task outcome by the use of a purposefully crafted reward model that
depends either on human feedback or on the specific characteristics of the
task data. The RL technique also offers the advantage of not requiring fine-
tuning an LLM as a reasoner, which can be considered a black box in this
setting, and exchanged freely.

Finally, we argue that the research agenda we lay out in this paper has the
potential to hugely impact the field of AI and democratize the access and use
of these large foundational models to a large set of entities.

##  2 Methodology

The system takes as input a task description, a query, and a database and
gives as output the response generated by a reasoner. The overall system
architecture, shown in Figure 1, consists of three main components: a
Generative Language Model, a Retriever, and a Reasoner (typically an LLM).

Figure 1: High-level design of the RRAML framework. On the left side, there
are the three inputs: Task Description, user’s query, and a database that
represents the external knowledge used to augment/update the reasoner. Then,
we present the overall architecture flow with the Retriever, Generative
Language Model, and Reasoner. Finally, how the reward is computed and
propagated in the Generative Language Model and Retriever.

More in detail, the Generative Language Model takes the task description and
query as input and generates a prompt. The Retriever takes the query and the
database as input and outputs a support set, which is then concatenated with
the query and passed to the Reasoner.

###  2.1 Data

The data is a critical component of the framework: the task description guides
the generation of an appropriate prompt, the query represents the user
request, and the database provides the data needed by the reasoner to perform
the task.

#### Task Description

The task description is a string that defines the nature of the task, possibly
with expected results, that the user wants to perform. For example, if the
user wants to generate a summarization of multiple news articles, a possible
task description could be “News Summarization”. If the user wants to perform
question answering on a vast document collection, the task description could
be “Question Answering”.

#### Query

The query represents the user’s need. The Retriever will operate on the
database w.r.t to the user’s query, and the resulting data is input for the
task. For example, if the user wants to summarize a collection of news
articles, the query could be the topic the user is interested in. If the user
wants to answer a specific query, this becomes the actual question.

#### Database

The database is a collection of public or private data (or documents) that can
be queried to provide relevant information to satisfy the user’s information
needs. The database represents the knowledge needed by the Reasoner to perform
the task. The data stored in the database will depend on the specific task and
may include text, images, audio, and other data types (as in [25]). For
example, if the user wants to summarize multiple news articles, the database
could be an indexed collection of articles. If the user wants to perform
Question Answering, the database may consist of facts related to a particular
topic (as in [22, 23]).

###  2.2 Models

#### Generative Language Model

The Generative Language Model component of the framework is responsible for
generating textual instructions based on the input Task Description and Query
that maximize the rewards w.r.t Reasoner. Specifically, it receives a string
representing the task to be performed (Task Description) and a query (Query)
that represents the user’s request. The Generative Language Model then
generates a textual prompt that is relevant to the query and the task by
performing automatic prompt engineering.

#### Retriever

The Retriever component of the framework is responsible for retrieving
relevant data from the Database based on the user’s query. We refer to the
Retriever outputs as support set (as in [22, 23]). A support set is a subset
of the data from the Database that either directly answers the given query or
contributes to the final answer.

#### Prompt Aggregator

This component is responsible for processing the input required by the
Reasoner. In its simplest form, it just needs to concatenate the prompt
generated by the Generative Language Model with the Support Set provided by
the Retriever. However, in a more complex version, it may need to rework the
prompt based on the number of support sets received to ensure that the LLM can
provide a coherent response. For example, if the Retriever provides two
support sets, the Prompt Aggregator may need to split the prompt into two
parts and concatenate each part with one of the support sets.

#### Reasoner

The Reasoner is responsible for generating the answer to the user’s query
based on the final prompt generated by the Prompt Aggregator. The Reasoner can
be a pre-trained model like GPT or a custom-trained model specific to the task
at hand. The output of the LLM is a textual response, which can be further
parsed to comply with the intended output.

###  2.3 Reinforcement Learning

The Reinforcement Learning (RL) part of the framework is responsible for fine-
tuning the Generative Language Model (GLM) and Retriever based on the computed
reward. The RL is a crucial part of RRAML, it will be used to constantly
improve the GLM and Retriever. As mentioned earlier, the retriever will get a
penalty if some of his recommendations will leads the Reasoner to a
hallucinate, for example by adding damaging documents. The RL allows use to
integrate and augment the signals in the training of these models, going
beyond the data present in their training set, ensuring that they are aligned
with the environment (i.e., the reasoner and the final task).

#### Reward

The reward function can be defined based on the similarity between the
generated output and the expected output and it can be estimated by training a
Reward Model [21].

#### RL algorithm

The specific RL method which can be used is Deep Q-Networks (DQN) [11], which
is a model-free RL algorithm that learns to maximize the cumulative reward
over time. DQN combines Q-Learning, which is a RL algorithm that learns the
optimal action-value function, with a Deep Neural Network to approximate the
action-value function. In the proposed framework, DQN is used to train the
Generative Language Model and the Retriever to maximize the reward obtained
from user feedback. The update process is performed by backpropagating the
reward signal through the neural networks using Stochastic Gradient Descent
(SGD). The weights of the neural networks are updated in the direction that
maximizes the expected reward, using the Q-Learning update rule. The update is
performed iteratively until convergence, which is achieved when the expected
reward stops improving.

#### Human-in-the-loop

Human preferences can be incorporated into our ML system by allowing users to
provide feedback on the system’s output. This feedback will be used to compute
the reward for the RL algorithm and will help improve the performance of the
overall system over time. We acknowledge that some tasks may not have a clear
expected output or may require additional context that is not available in the
input data. In these cases, we will leverage human-in-the-loop approaches to
provide additional context and guidance to the system. For example, crowd-
sourcing platforms or internal subject matter experts can be used to provide
feedback on the system’s output and help train the model on more complex
tasks.

##  3 Use Case Example

RRAML proves to be effective in many applications. Consider a situation where
a company possesses a private database, which consists of factual information
expressed in natural language, and they need to apply reasoning to this data.
The volume of their data may exceed the context capacity of the LLM, and fine-
tuning is not an option, for pricing/environmental impact or because the LLM
is served by other company APIs. To tackle this challenge, RRAML uses its
retriever to get only the relevant facts within the context, enabling the LLM
to reason over them.

For instance, suppose a company has an employee list, projects that employees
are currently or were previously assigned to, and performance evaluation grids
with text-based feedback from superiors. The company might want to assign
employees to a new project on a specific topic. To do so, it is necessary to
input the information contained in these data to the LLM. However, due to
capacity constraints, the entire data cannot fit within the context.
Therefore, the retriever has to return a subset of this information, perhaps
excluding data on projects from the distant past, employees who are already
overburdened with multiple projects, or employees who have never worked on a
project related to the same topic.

##  4 Related Work

Recent years have seen the emergence of large language models. Starting from
the first Generative Pre/Training Model, better known as GPT [17], these kinds
of large language models have rapidly improved. GPT-4 [14] is the most recent
iteration, but in the meanwhile, many have rushed to propose their own
version. Google has recently released BARD111https://bard.google.com/, while
Meta has proposed their own take on LLM with LLaMA [24]. The research
community has also capitalized its effort by releasing several open source LLM
of different sizes, like Bloom [20],
Dolly222https://github.com/databrickslabs/dolly, and RWKV [16]. However, all
these models fail to scale to a larger context size, either by excessive
computational costs or by “losing it in the middle”, as shown in [9].
To address this context-length limitation, some have tried to incorporate
external knowledge into LLMs [6, 4, 15]. In particular, in “Retrieval-enhanced
machine learning” [27], authors have envisioned a framework in which retrieval
systems can enhance the performance of a machine learning model. More
recently, there have been attempts of jointly training retrieval models with
LLMs [8, 28], notably, the line of research on neural databases, in which the
authors tried to replace a traditional database with a neural framework
removing the need for a schema [23, 22, 25]. However, all these works assume
full access to the reasoner module, which is not the case for most users in
practice.
To overcome this limitation, many have tried to craft systems that are able to
deliver an optimized prompt that is input to the LLM. For instance, the
research conducted by [10] demonstrated a substantial influence of the
sequence in which prompts are presented on the ultimate performance of the
task. Meanwhile, a study by Nie et al. [12] highlighted that the performance
is susceptible to the arrangement of the examples in the prompt, prompt
templates, and the in-context instances in the prompt. Lester et al. [7]
suggested a method to enhance task performance by adding adjustable tokens
during fine-tuning. LLM-AUGMENTER iteratively revises [15] to improve the
model response.
All the works introduced above do not improve on the retriever, which is
assumed fixed. In our work, we propose to finetune the retriever in
conjunction with the reasoner to improve on results. Since the feedback is
non-differentiable we resort to reinforcement learning. In particular, recent
formulation such as Proximal Policy Optimization (PPO) [5] make use of a
differentiable neural reward module to include and account for generally non-
differentiable feedback, like in the case of reinforcement learning with human
feedback (RLHF).

##  5 Conclusions

In conclusion, RRAML provides a promising framework for building intelligent
interfaces to interact with large language models like GPT. By combining a
generative language model with a retriever, this approach can effectively
improve the performance of language models and help them understand user
intents better.

However, this approach also comes with several challenges and uncertainties,
such as the need for a large amount of training data, the potential for bias
in the data and models, and the difficulty of balancing the trade-offs between
generative and retrieval-based approaches.

Despite these challenges, RRAML holds great promise for creating more
intelligent, natural, and effective interfaces for interacting with language
models. We hope that this paper has provided a useful overview of this
approach and its potential applications, and we look forward to further
research and development in this exciting area.

## References

  * [1] Bacciu, A., Trappolini, G., Santilli, A., Rodolà, E., Silvestri, F.: Fauno: The italian large language model that will leave you senza parole! arXiv preprint arXiv:2306.14457 (2023)
  * [2] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.: Language models are few-shot learners. Advances in neural information processing systems 33, 1877–1901 (2020)
  * [3] Carmel, D., Cohen, N., Ingber, A., Kravi, E.: Ir evaluation and learning in the presence of forbidden documents. In: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 556–566 (2022)
  * [4] Dinan, E., Roller, S., Shuster, K., Fan, A., Auli, M., Weston, J.: Wizard of wikipedia: Knowledge-powered conversational agents. arXiv preprint arXiv:1811.01241 (2018)
  * [5] Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., Madry, A.: Implementation matters in deep policy gradients: A case study on ppo and trpo. arXiv preprint arXiv:2005.12729 (2020)
  * [6] Ghazvininejad, M., Brockett, C., Chang, M.W., Dolan, B., Gao, J., Yih, W.t., Galley, M.: A knowledge-grounded neural conversation model. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 32 (2018)
  * [7] Lester, B., Al-Rfou, R., Constant, N.: The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104.08691 (2021)
  * [8] Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.t., Rocktäschel, T., et al.: Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems 33, 9459–9474 (2020)
  * [9] Liu, N.F., Lin, K., Hewitt, J., Paranjape, A., Bevilacqua, M., Petroni, F., Liang, P.: Lost in the middle: How language models use long contexts. arXiv preprint arXiv:2307.03172 (2023)
  * [10] Lu, Y., Bartolo, M., Moore, A., Riedel, S., Stenetorp, P.: Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08786 (2021)
  * [11] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. nature 518(7540), 529–533 (2015)
  * [12] Nie, F., Chen, M., Zhang, Z., Cheng, X.: Improving few-shot performance of language models via nearest neighbor calibration. arXiv preprint arXiv:2212.02216 (2022)
  * [13] OpenAI: Chatgpt: A large-scale language model for conversational ai. OpenAI Blog (November 2022)
  * [14] OpenAI: Gpt-4 technical report (2023)
  * [15] Peng, B., Galley, M., He, P., Cheng, H., Xie, Y., Hu, Y., Huang, Q., Liden, L., Yu, Z., Chen, W., et al.: Check your facts and try again: Improving large language models with external knowledge and automated feedback. arXiv preprint arXiv:2302.12813 (2023)
  * [16] PENG, B.: RWKV-LM (Aug 2021). https://doi.org/10.5281/zenodo.5196577, https://github.com/BlinkDL/RWKV-LM
  * [17] Radford, A., Narasimhan, K., Salimans, T., Sutskever, I., et al.: Improving language understanding by generative pre-training. OpenAI Blog (2018)
  * [18] Sauchuk, A., Thorne, J., Halevy, A., Tonellotto, N., Silvestri, F.: On the role of relevance in natural language processing tasks. In: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 1785–1789 (2022)
  * [19] Sauchuk, A., Thorne, J., Halevy, A.Y., Tonellotto, N., Silvestri, F.: On the role of relevance in natural language processing tasks. In: Amigó, E., Castells, P., Gonzalo, J., Carterette, B., Culpepper, J.S., Kazai, G. (eds.) SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, Madrid, Spain, July 11 - 15, 2022. pp. 1785–1789. ACM (2022). https://doi.org/10.1145/3477495.3532034, https://doi.org/10.1145/3477495.3532034
  * [20] Scao, T.L., Fan, A., Akiki, C., Pavlick, E., Ilić, S., Hesslow, D., Castagné, R., Luccioni, A.S., Yvon, F., Gallé, M., et al.: Bloom: A 176b-parameter open-access multilingual language model. arXiv preprint arXiv:2211.05100 (2022)
  * [21] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)
  * [22] Thorne, J., Yazdani, M., Saeidi, M., Silvestri, F., Riedel, S., Halevy, A.: Database reasoning over text. arXiv preprint arXiv:2106.01074 (2021)
  * [23] Thorne, J., Yazdani, M., Saeidi, M., Silvestri, F., Riedel, S., Halevy, A.: From natural language processing to neural databases. In: Proceedings of the VLDB Endowment. vol. 14, pp. 1033–1039. VLDB Endowment (2021)
  * [24] Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., Lample, G.: Llama: Open and efficient foundation language models (2023)
  * [25] Trappolini, G., Santilli, A., Rodolà, E., Halevy, A., Silvestri, F.: Multimodal neural databases. arXiv preprint arXiv:2305.01447 (2023)
  * [26] Xie, Z., Singh, S., McAuley, J., Majumder, B.P.: Factual and informative review generation for explainable recommendation. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 37, pp. 13816–13824 (2023)
  * [27] Zamani, H., Diaz, F., Dehghani, M., Metzler, D., Bendersky, M.: Retrieval-enhanced machine learning. In: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 2875–2886 (2022)
  * [28] Zhang, Y., Sun, S., Gao, X., Fang, Y., Brockett, C., Galley, M., Gao, J., Dolan, B.: Retgen: A joint framework for retrieval and grounded text generation modeling. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36, pp. 11739–11747 (2022)