####

[runin] 0pt #1

####

Jeroen Bollen  0000-0002-8881-5241<EMAIL_ADDRESS>UHasselt, Data
Science InstituteBelgium ,  Jasper Steegmans  0000-0003-2087-9430
<EMAIL_ADDRESS>UHasselt, Data Science InstituteBelgium ,  Jan
Van den Bussche<EMAIL_ADDRESS>0000-0003-0072-3252 UHasselt,
Data Science InstituteBelgium and  Stijn Vansummeren
<EMAIL_ADDRESS>0000-0001-7793-9049 UHasselt, Data Science
InstituteBelgium

0pt 1ex plus .1ex minus .2ex 1ex theoremTheorem[section] lemma[theorem]Lemma
proposition[theorem]Proposition claim[theorem]Claim
corollary[theorem]Corollary observation[theorem]Observation
remark[theorem]Remark

#### Learning Graph Neural Networks using Exact Compression

Jeroen Bollen  0000-0002-8881-5241<EMAIL_ADDRESS>UHasselt, Data
Science InstituteBelgium ,  Jasper Steegmans  0000-0003-2087-9430
<EMAIL_ADDRESS>UHasselt, Data Science InstituteBelgium ,  Jan
Van den Bussche<EMAIL_ADDRESS>0000-0003-0072-3252 UHasselt,
Data Science InstituteBelgium and  Stijn Vansummeren
<EMAIL_ADDRESS>0000-0001-7793-9049 UHasselt, Data Science
InstituteBelgium

###### Abstract.

Graph Neural Networks (GNNs) are a form of deep learning that enable a wide
range of machine learning applications on graph-structured data. The learning
of GNNs, however, is known to pose challenges for memory-constrained devices
such as GPUs. In this paper, we study _exact compression_ as a way to reduce
the memory requirements of learning GNNs on large graphs. In particular, we
adopt a formal approach to compression and propose a methodology that
transforms GNN learning problems into provably equivalent compressed GNN
learning problems. In a preliminary experimental evaluation, we give insights
into the compression ratios that can be obtained on real-world graphs and
apply our methodology to an existing GNN benchmark.

##  1\. Introduction

Whereas Machine Learning (ML) has traditionally been most successful in
analyzing traditional unstructured data such as text or images, ML over
structured data such as graphs has become an active area of research in the
past decade. In particular, Graph Neural Networks (GNNs for short) are a form
of deep learning architectures that enable a wide range of ML applications on
graph-structured data, such as molecule classification, knowledge graph
completion, and web-scale recommendations
(battagliaRelationalInductiveBiases2018; gilmerNeuralMessagePassing2017;
hamiltonInductiveRepresentationLearning2017; yingGraphConvolutionalNeural2018;
hamiltonGraphRepresentationLearning2020). At their core, GNNs allow to embed
graph nodes into vector space. Crucially, the obtained vectors can capture
graph structure, which is essential for the ML applications already cited.

While GNNs are hence an attractive mechanism for ML on graphs, learning GNNs
is known to be resource-demanding which limits their scalability
(wuComprehensiveSurveyGraph2021; zhuSpikingGraphConvolutional2022). In
particular, for large graphs it becomes difficult to encode all the required
information into the limited memory of hardware accelerators like GPUs. For
this reason, scalable methods for learning GNNs on large graphs are an active
subject of research (e.g., (wangNeutronStarDistributedGNN2022;
zhengByteGNNEfficientGraph2022; yuanDistributedLearningFully2022;
linCharacterizingUnderstandingDistributed2022; liaoSCARAScalableGraph2022;
pengSancusStalenessawareCommunicationavoiding2022;
generaleScalingRGCNTraining2022; salhaDegeneracyFrameworkScalable2019;
dengGraphZoomMultilevelSpectral2020a; huangAdaptiveSamplingFast2018;
chenFastGCNFastLearning2018; hamiltonInductiveRepresentationLearning2017)).
Broadly speaking, we can identify three different principles for obtaining
scalability in the literature: (1) distributing computation across multiple
machines or GPUs (wangNeutronStarDistributedGNN2022;
zhengByteGNNEfficientGraph2022; yuanDistributedLearningFully2022;
linCharacterizingUnderstandingDistributed2022; liaoSCARAScalableGraph2022;
pengSancusStalenessawareCommunicationavoiding2022;
generaleScalingRGCNTraining2022); (2) learning on a sample of the input graph
instead of the entire graph (huangAdaptiveSamplingFast2018;
chenFastGCNFastLearning2018; hamiltonInductiveRepresentationLearning2017); and
(3) compression (generaleScalingRGCNTraining2022;
salhaDegeneracyFrameworkScalable2019; dengGraphZoomMultilevelSpectral2020a;
liangMILEMultiLevelFramework2021). Compression-based approaches limit the
memory requirements of learning GNNs on large graphs by reducing the input
graph into a smaller graph and then learn on this smaller, reduced graph
instead. In this paper, we are concerned with compression.

Compression methods are based on collapsing multiple input nodes into a single
reduced node in the compressed graph. Methods vary, however, in how they
collapse nodes. For example, Deng et al.
(dengGraphZoomMultilevelSpectral2020a) use spectral analysis for this purpose;
Liang et al. (liangMILEMultiLevelFramework2021) use variants of multi-level
graph partitioning; and Generale et al. (generaleScalingRGCNTraining2022), who
specifically consider knowledge graphs, use general heuristics (such as two
nodes having equal set of attributes) or bisimulation. While these methods
give intuitive reasons to argue that the structure of the obtained compressed
graph should be similar to that of the original graph, no formal guarantee is
ever given that learning on the compressed graph is in any way equivalent to
learning on the original graph. Furthermore, the methods are usually devised
and tested for a specific GNN architecture (such as Graph Convolutional
Networks, GCN). It is therefore unclear how they fare on other GNN
architectures. Inherently, these methods are hence heuristics. At best the
compressed graphs that they generate _approximate_ the original graph
structure, and it is difficult to predict for which GNN architectures this
approximation is good enough, and for which architectures it poses a problem.

Towards a more principled study of learning GNNs on compressed graphs, we
propose to take a formal approach and study _exact compression_ instead. We
make the following contributions.

(1.) We formally define when two learning problems involving graph neural
networks are equivalent. Based on this definition, our goal is to transform a
given problem into a smaller, equivalent problem based on compression.
(Section 2.)

(2.) We develop a compression methodology that is guaranteed to always yield
an equivalent learning problem and that is applicable to a wide class of GNN
architectures known as _aggregate-combine GNNs_ (groheLogicGraphNeural2021;
barceloExpressivePowerGraph2020; hamiltonGraphRepresentationLearning2020).
This class includes all Graph Convolutional Networks
(hamiltonGraphRepresentationLearning2020). Our methodology is based on recent
insights into the expressiveness of aggregate-combine GNNs
(morrisWeisfeilerLemanGo2019; xuHowPowerfulAre2019). These results imply that
if the local neighborhoods of two nodes $v,w$ in input graph $G$ are equal,
then any GNN will treat $v$ and $w$ identically. We may intuitively exploit
this property for compression: if $v$ and $w$ are treated identically there is
no need for them both to be present during learning; having one of them
suffices. We fully develop this intuition in Section 3, where we also consider
a more relaxed notion of “local neighborhood” that is applicable only to
specific kinds of aggregate-combine GNNs.

(3.) We empirically evaluate the effectiveness of our methodology in Section
4. In particular, we give insights into the compression ratios that can be
obtained on real-world graphs. While we find that these ratios are diverse,
from compressing extremely well to compressing only marginally, a preliminary
experiment on an existing GNN benchmark shows positive impact on learning
efficiency even with marginal compression.

We start with preliminaries in Section 2 and conclude in Section 5. Proofs of
formal statements may be found in the Appendix.

##  2\. Preliminaries

#### Background.

We denote by $\mathbb{R}$ the set of real numbers, by $\mathbb{N}$ the set of
natural numbers, and by $\mathbb{N}_{\infty}$ the set
$\mathbb{N}\cup\\{\infty\\}$ of natural numbers extended with infinity. We
will use double curly braces $\\{\\!\\!\\{\dots\\}\\!\\!\\}$ to denote
multisets and multiset comprehension. Formally, we view a multiset over a
domain of elements $S$ as a function $M\colon S\to\mathbb{N}$ that associates
a multiplicity $M(x)$ to each element $x\in S$. As such, in the multiset
$M=\\{\\!\\!\\{a,a,b\\}\\!\\!\\}$, we have that $M(a)=2$ and $M(b)=1$. If
$M(x)=0$ then $x$ is not present in $M$. We denote by
$\operatorname{\textit{supp}}(M)$ the set of all elements present in $M$,
$\operatorname{\textit{supp}}(M):=\\{x\in S\mid M(x)>0\\}$. Note that if every
element has multiplicity at most one, then $M$ is a set. If $M$ is a multiset
and $c\in\mathbb{N}_{\infty}$ then we denote by ${M}|_{\leq c}$ the multiset
obtained from $M$ by restricting the multiplicity of all elements to be at
most $c$, i.e., ${M}|_{\leq c}(x)=\min(M(x),c)$, for all elements $x$. Note in
particular that ${M}|_{\leq+\infty}=M$ and that ${M}|_{\leq 1}$ converts $M$
into a set.

#### Graphs.

We work with directed node-colored multigraphs. Formally, our graphs are hence
triples $G=(V,E,g)$ where $V$ is a finite set of nodes; $E$ is a _multiset_ of
edges over $V\times V$; and $g$ is a function, called the _coloring_ of $G$,
that maps every node $v\in V$ to a _color_ $g(v)$. (The term “color” is just
an intuitive way to specify that $g$ has some unspecified range.) If $Y$ is
the co-domain of $g$, i.e., $g$ is of the form $g\colon V\to Y$ then we also
call $g$ a _$Y$ -coloring_ and say that $G$ is a _$Y$ -colored graph_, or
simply a $Y$-graph. When $Y=\mathbb{R}^{n}$ we also call $g$ an
$n$-dimensional _feature map_. To ease notation we write $v\in G$ to indicate
that $v\in V$. Furthermore, we write $G(v)$ instead of $g(v)$ to denote the
color of $v$ in $G$, and we write $G(v\to w)$ instead of $E(v\to w)$ to denote
the multiplicity of edge $v\to w$ in $G$. When $E$ is a set, i.e., when every
edge has multiplicity at most one, then we also call $G$ a _simple_ graph. We
write $\operatorname{\mathsf{in}}_{G}(v)$ for the multiset $\\{\\!\\!\\{w\in
G\mid w\to v\in E\\}\\!\\!\\}$ of all incoming neighbors of $v$. So, if the
edge $w\to v$ has multiplicity $5$ in $E$ then $w$ also has multiplicity $5$
in $\operatorname{\mathsf{in}}_{G}(v)$. We drop subscripts when the graph $G$
is clear from the context. The _size_ of a graph $G$ is the number of nodes
$|V|$ plus the number of simple edges $|\\!\operatorname{\textit{supp}}(E)|$.
This is a reasonable definition of the size of a multigraph, since for each
edge it suffices to simply store its multiplicity as a number, and storing a
number takes unit cost in the RAM model of computation.

#### Color transformers.

If $\mathcal{C}$ is a function that maps $X$-colored graphs $G=(V,E,g)$ into
$Y$-colored graphs $G^{\prime}=(V^{\prime},E^{\prime},g^{\prime})$ that leaves
nodes and edges untouched and only changes the coloring, i.e., $V=V^{\prime}$
and $E=E^{\prime}$ then we call $\mathcal{C}$ a _coloring transformer_. In
particular, if $X=\mathbb{R}^{p}$ and $Y=\mathbb{R}^{q}$ for some dimensions
$p$ and $q$ then $\mathcal{C}$ is a _feature map transformer_.

#### Graph Neural Networks.

Graph Neural Networks (GNNs) are a popular form of neural networks that enable
deep learning on graphs. Many different forms of GNNs have been proposed in
the literature. We refer the reader to the overview by Hamilton
(hamiltonGraphRepresentationLearning2020). In this paper we focus on a
standard form of GNNs that is known under the name of _aggregate-combine GNNs_
(barceloExpressivePowerGraph2020), also called _message-passing GNNs_. These
are defined as follows (groheLogicGraphNeural2021;
geertsExpressivePowerMessagePassing2022).

A _GNN layer_ of input dimension $p$ and output dimension $q$ is a pair
$(\textsc{Agg},\textsc{Comb})$ of functions where (1) Agg is an _aggregation
function_ that maps finite multisets of vectors in $\mathbb{R}^{p}$ to vectors
in $\mathbb{R}^{h}$ for some dimension $h$ and (2) Comb is a _combination
function_
$\textsc{Comb}\colon\mathbb{R}^{p}\times\mathbb{R}^{h}\to\mathbb{R}^{q}$. In
practice, Agg is usually taken to compute the arithmetic mean, sum, or maximum
of the vectors in the multiset, while Comb is computed by means of a
feedforward neural network whose parameters can be learned.

A _GNN_ is a sequence $\overline{L}=(L_{1},\dots,L_{k})$ of GNN layers, where
the output dimension of $L_{i}$ equals the input dimension of $L_{i+1}$, for
$1\leq i<k$. The _input and output dimensions_ of the GNN are the input
dimension of $L_{1}$, and the output dimension of $L_{k}$ respectively. In
what follows, we write $\overline{L}\colon p,q$ to denote that $p$ is the
input dimension of $\overline{L}$ and $q$ is the output dimension.

Semantically, GNN layers and GNNs are feature map transformers
(geertsExpressivePowerMessagePassing2022) In particular, when GNN layer
$L=(\textsc{Agg},\textsc{Comb})$ of input dimension $p$ and output dimension
$q$ is executed on $\mathbb{R}^{p}$-colored graph $G=(V,E,g)$ it returns the
$\mathbb{R}^{q}$-colored graph $G^{\prime}=(V,E,g^{\prime})$ with $g^{\prime}$
the $q$-dimensional feature map defined by

$g^{\prime}\colon
v\mapsto\textsc{Comb}\big{(}g(v),\textsc{Agg}\,\\{\\!\\!\\{g(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}\big{)}.$

As such, for each node $v$, $\overline{L}$ aggregates the (multiplicity-
weighted) $\mathbb{R}^{p}$ colors of $v$’s neighbors, and combines this with
$v$’s own color to compute the $\mathbb{R}^{q}$ output.

A GNN $\overline{L}\colon p,q$ simply composes the transformations defined by
its layers: given $\mathbb{R}^{p}$-colored graph $G$ it returns the
$\mathbb{R}^{q}$-colored graph $(L_{k}\circ L_{k-1}\circ\dots\circ L_{1})(G)$.

#### Discussion.

It is important to stress that in the literature GNNs are defined to operate
on _simple graphs_ , whereas we have generalized their semantics above to also
work on _multigraphs_. We did so because, as we will see in Section 3, the
result of compressing a simple graph for the purpose of learning naturally
yields a multigraph.

#### Learning problems.

GNNs are used for a wide range of supervised learning tasks on graphs. For
example, for a node $v$, the $\mathbb{R}^{q}$-vector $\overline{L}(G)(v)$
computed for $v$ by GNN $\overline{L}$ can be interpreted, after
normalisation, as a probability distribution over $q$ new labels (for node
classification), or as predicted values (for node regression). Similarly, an
edge prediction for nodes $v$ and $w$ can be made based on the pair
$(\overline{L}(G)(v),\overline{L}(G)(w))$. Finally, by aggregating
$\overline{L}(G)(v)$ over all nodes $v\in G$, one obtains graph embeddings
that can be used for graph classification, regression and clustering
(hamiltonGraphRepresentationLearning2020).

In this work, we focus on the tasks of node classification and regression. Our
methodology is equally applicable to the other tasks, however.

In order to make precise what we mean by learning GNNs on compressed graphs
for node classification, we propose the following formal definition.

###### Definition 2.1.

A _learning problem_ of input dimension $p$ and output dimension $q$ is a
tuple $\mathcal{P}=(G,T,\operatorname{\textsc{Loss}},\mathcal{S})$ where

  * •

$G$ is the $\mathbb{R}^{p}$-colored graph on which we wish to learn;

  * •

$T$ is a subset of $G$’s nodes, representing the training set;

  * •

$\operatorname{\textsc{Loss}}\colon T\times\mathbb{R}^{q}\to\mathbb{R}$ is a
loss function that allows to quantify, for each node $v\in T$ the
dissimilarity $\operatorname{\textsc{Loss}}(v,c)$ of the
$\mathbb{R}^{q}$-color $c$ that is predicted for $v$ by a GNN and the desired
$\mathbb{R}^{q}$-color for $v$ as specified in the training set;

  * •

$\mathcal{S}$ is the _hypothesis space_ , a (possibly infinite) collection of
GNNs of input dimension $p$ and output dimension $q$.

Given a learning problem $\mathcal{P}$, a learning algorithm produces a
“learned” GNN in $\mathcal{S}$ by traversing the search space $\mathcal{S}$.
For each currently considered GNN $\overline{L}\in\mathcal{S}$, the observed
loss of $\overline{L}$ on $G$ w.r.t. $T$ is computed as

$\operatorname{\textsc{Loss}}(\overline{L}(G),T):=\sum_{v\in
T}\operatorname{\textsc{Loss}}\big{(}v,\overline{L}(G)(v)\big{)}.$

The learning algorithm aims to minimize this loss, but possibly returns an
$\overline{L}$ for which this is only a local minimum.

In practice, $\mathcal{S}$ is usually a collection of GNNs with the same
topology: they all have the same number of layers (with each layer $d$ having
the same input and output dimensions accross GNNs in $\mathcal{S}$) and are
parametrized by the same number of learnable parameters. Each concrete
parametrization constitutes a concrete GNN in $\mathcal{S}$ in our framework.
Commonly, the learned GNN $\overline{L}$ is then found by means of gradient
descent, which updates the learnable parameters of the GNNs in $\mathcal{S}$
to minimize the observed error.

No matter which concrete learning algorithm is used to solve a learning
problem, the intent is that the returned $\overline{L}$ generalizes well: it
makes predictions on $G$ for the nodes not in $T$, and can also be applied to
other, new $\mathbb{R}^{p}$-colored graphs to predict $\mathbb{R}^{q}$-vectors
for each node.

#### Our research question in this paper is the following.

> Given a GNN learning problem
> $\mathcal{P}=(G,T,\operatorname{\textsc{Loss}},\mathcal{S})$, is it possible
> to transform this into a new problem
> $\mathcal{P}^{\prime}=(G^{\prime},T^{\prime},\operatorname{\textsc{Loss}}^{\prime},\mathcal{S})$
> that is obtained by _compressing_ $G$, $T$, and
> $\operatorname{\textsc{Loss}}$ into a smaller graph $G^{\prime}$, training
> set $T^{\prime}$, and loss function $\operatorname{\textsc{Loss}}^{\prime}$
> such that instead of learning a GNN on $\mathcal{P}$ we could equivalently
> learn a GNN on $\mathcal{P}^{\prime}$ instead?

Here “equivalently” means that ideally, no matter which learning algorithm is
used, we would like the learned GNN to be identical in both cases. Of course,
this is not possible in practice because the learning process is itself non-
deterministic, e.g., because the learning algorithm makes random starts;
because of stochasticity in stochastic gradient descent; or because of non-
deterministic dropout that is applied between layers. Nevertheless, we expect
the GNN obtained by learning on the compressed problem would perform “as good”
as the GNN obtained by the learning on the uncompressed problem, in the sense
that it generalizes to unseen nodes and unseen colored graphs equally well.

To ensure that we may hope any learning algorithm to perform equally well on
$\mathcal{P}^{\prime}$ as on $\mathcal{P}$, we formally define:

###### Definition 2.2.

Two learning problems $\mathcal{P}$ and $\mathcal{P}^{\prime}$ are
_equivalent_ , written $\mathcal{P}\equiv\mathcal{P}^{\prime}$, if they share
the same hypothesis space of GNNs $\mathcal{S}$ and, for every
$\overline{L}\in\mathcal{S}$ we have
$\operatorname{\textsc{Loss}}(\overline{L}(G),T)=\operatorname{\textsc{Loss}}^{\prime}(\overline{L}(G^{\prime}),T^{\prime})$.

In other words, when traversing the hypothesis space for a GNN to return, no
learning algorithm can distinguish between $\mathcal{P}$ and
$\mathcal{P}^{\prime}$. All other things being equal, if the learning
algorithm then returns a GNN $\overline{L}$ when run on $\mathcal{P}$, it will
return $\overline{L}$ on $\mathcal{P}^{\prime}$ with the same probability.

Note that, while the hypothesis space $\mathcal{S}$ remains unchanged in this
definition, it is possible (and, as we will see, actually required) to adapt
the loss function $\operatorname{\textsc{Loss}}$ into a modified loss function
$\operatorname{\textsc{Loss}}^{\prime}$ during compression.

The benefit of a positive answer to our research question, if compression is
efficient, is computational efficiency: learning on smaller graphs is faster
than learning on larger graphs and requires less memory.

##  3\. Methodology

To compress one learning problem into an equivalent, hopefully smaller,
problem we will exploit recent insights into the expressiveness of GNNs
(morrisWeisfeilerLemanGo2019; xuHowPowerfulAre2019;
barceloExpressivePowerGraph2020). In particular, it is known that if the local
neighborhoods of two nodes $v,w$ in input graph $G$ are equal, then any GNN
will treat $v$ and $w$ identically. In particular, it will assign the same
output colors to $v$ and $w$. We may intuitively exploit this property for
compression: since $v$ and $w$ are treated identically there is no need for
them both to be present during learning; having one of them suffices. So, we
could compress by removing nodes that are redundant in this sense. We must
take care, however, that by removing one, we do not change the structure (and
hence, possibly, the predicted color) of the remaining node. Also, of course,
we need to make sure that by removing nodes we do not lose training
information. I.e., if $T$ specifies a training color for $v$ but not $w$ then
if we decide to remove $v$, we somehow need to “fix” $T$, as well as the loss
function.

This section is devoted to developing this intuitive idea. In Section 3.1 we
first study under which conditions GNNs treat nodes identically. Next, in
Section 3.2 we develop compression of colored graphs based on collapsing
identically-treated nodes, allowing to remove redundant nodes while retaining
the structure of the remaining nodes. Finally, in Section 3.3, we discuss
compression of the training set and loss function. Together, these three
ingredients allow us to compress a learning problem into an equivalent
problem, cf. Definition 2.2.

We close this section by proposing an alternative definition of compression
that works only for a limited class of learning problems. It is nevertheless
interesting as it may allow better compression, as we will show in Section 4.

###  3.1. Indistinguishability

The following definition formalizes when two nodes, not necessarily in the
same graph, are treated identically by a class of GNNs.

###### Definition 3.1.

Let $\mathcal{S}$ be a class of GNNs, let $G$ and $H$ be two
$\mathbb{R}^{p}$-colored graphs for some $p$, and let $v\in G,w\in H$ be two
nodes in these graphs. We say that $(G,v)$ is
$\mathcal{S}$-_indistinguishable_ from $(H,w)$, denoted
$(G,v)\sim_{\mathcal{S}}(H,w)$, if for every GNN $\overline{L}\in\mathcal{S}$
of input dimension $p$ it holds that $\overline{L}(G)(v)=\overline{L}(H)(w)$.

In other words, two nodes are indistinguishable by a class of GNNs
$\mathcal{S}$ if no $GNN$ in $\mathcal{S}$ can ever assign a different output
color to these nodes, when started on $G$ respectively $H$. We call $(G,v)$
and $(H,w)$ $\mathcal{S}$-_distinguishable_ otherwise.

For the purpose of compression, we are in search of sets of nodes in the input
graph $G$ that are pairwise $\mathcal{S}$-indistinguishable, with
$\mathcal{S}$ the hypothesis space of the input learning problem. It is these
nodes that we can potentially collapse in the input learning problem.
Formally, let $[G,v]_{\mathcal{S}}$ denote the set of all nodes in $G$ that
are $S$-indistinguishable from $v$,

$[G,v]_{\mathcal{S}}:=\\{w\in G\mid(G,v)\sim_{\mathcal{S}}(G,w)\\}.$

We aim to calculate $[G,v]_{\mathcal{S}}$ and subsequently compress $G$ by
removing all but one node in $[G,v]_{\mathcal{S}}$ from $G$.

#### Color refinement.

To calculate $[G,v]_{\mathcal{S}}$, we build on the work of Morris et al.
(morrisWeisfeilerLemanGo2019) and Xu et al. (xuHowPowerfulAre2019). They
proved independently that a GNN can distinguish two nodes if an only if the
so-called _color refinement_ algorithm assigns different colors to these
nodes. Color refinement is equivalent to the one-dimensional Weisfeiler-Leman
(WL) algorithm (groheLogicGraphNeural2021), and works as follows.

###### Definition 3.2.

The (one-step) _color-refinement_ of colored graph $G=(V,E,g)$, denoted
$\operatorname{\mathsf{cr}}(G)$, is the colored graph
$G^{\prime}=(V,E,g^{\prime})$ where $g^{\prime}$ maps every node $v\in G$ to a
pair, consisting of $v$’s original color and the multiset of colors of its
incoming neighbors:

$g^{\prime}\colon v\mapsto\big{(}G(v),\\{\\!\\!\\{G(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}\big{)}.$

As such, we can think of $\operatorname{\mathsf{cr}}(G)(v)$ as representing
the immediate neighborhood of $v$ (including $v$), for any node $v$.

We denote by $\operatorname{\mathsf{cr}}^{d}(G)$ the result of applying $d$
color refinement steps on $G$, so $\operatorname{\mathsf{cr}}^{0}(G)=G$ and
$\operatorname{\mathsf{cr}}^{d+1}(G)=\operatorname{\mathsf{cr}}(\operatorname{\mathsf{cr}}^{d}(G))$.
Using this notation, we can think of $\operatorname{\mathsf{cr}}^{d}(G)(v)$ as
representing the local neighborhood of $v$ “up to radius $d$”.

To illustrate, Figure 1 shows a colored graph $G$ and two steps of color
refinement.

$a_{1}$$a_{2}$$a_{3}$$b_{1}$$b_{2}$$b_{3}$ | $\operatorname{\mathsf{cr}}^{0}$ | $\operatorname{\mathsf{cr}}^{1}$ | $\operatorname{\mathsf{cr}}^{2}$
---|---|---|---
$a_{1}$ | $a$ |  1 $=(a,\\{\\!\\!\\{a\\}\\!\\!\\})$ | $(\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c1}}}}}}},\\{\\!\\!\\{\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}}\\}\\!\\!\\})$
$a_{2}$ | $a$ |  2 $=(a,\\{\\!\\!\\{a,a\\}\\!\\!\\})$ | $(\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}},\\{\\!\\!\\{\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c1}}}}}}},\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}}\\}\\!\\!\\})$
$a_{3}$ | $a$ |  1 $=(a,\\{\\!\\!\\{a,a\\}\\!\\!\\})$ | $(\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}},\\{\\!\\!\\{\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c1}}}}}}},\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}}\\}\\!\\!\\})$
$b_{1}$ | $b$ |  3 $=(b,\\{\\!\\!\\{a,a\\}\\!\\!\\})$ | $(\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c3}}}}}}},\\{\\!\\!\\{\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c1}}}}}}},\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}}\\}\\!\\!\\})$
$b_{2}$ | $b$ |  1 $=(b,\\{\\!\\!\\{a,a\\}\\!\\!\\})$ | $(\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c3}}}}}}},\\{\\!\\!\\{\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c1}}}}}}},\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}}\\}\\!\\!\\})$
$b_{3}$ | $b$ |  1 $=(b,\\{\\!\\!\\{a,a\\}\\!\\!\\})$ | $(\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c3}}}}}}},\\{\\!\\!\\{\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}},\textnormal{\raisebox{-3.75pt}{\makebox[11.0pt]{\makebox(0.0,0.0)[]{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\put(0.0,0.0){\circle{missing}}}\makebox(0.0,0.0)[]{\put(-2.72223,0.0){\scriptsize{\ref{c2}}}}}}}\\}\\!\\!\\})$
Figure 1. Example of color refinement. Nodes $a_{1},a_{2},a_{3}$ have the same
color $a$; nodes $b_{1},b_{2},b_{3}$ have the same color $b$. All edges have
multiplicity $1$.

The following property was observed by Morris et al.
(morrisWeisfeilerLemanGo2019) and Xu et al (xuHowPowerfulAre2019) for GNNs
operating on _simple_ graphs. We here extend it to multigraphs.

Let $\overline{L}$ be a GNN composed of $d\in\mathbb{N}$ layers, $d\geq 1$. If
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(H)(w)$
then $\overline{L}(G)(v)=\overline{L}(H)(w)$. As a consequence, if
$\mathcal{S}$ is a hypothesis space consisting of GNNs of at most $d$ layers
and
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(H)(w)$
then $(G,v)\sim_{\mathcal{S}}(H,w)$.

###### Proof.

It suffices to show that, for all graphs $G,H$ and nodes $v\in G,w\in H$ it
holds that, if
$\operatorname{\mathsf{cr}}(G)(v)=\operatorname{\mathsf{cr}}(H)(w)$ then
$L(G)(v)=L(H)(w)$ for any GNN layer $L$. Using this observation, the
proposition then follows for GNNs by straightforward induction on the number
of layers $d$ and the fact that if
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(H)(w)$,
then also
$\operatorname{\mathsf{cr}}^{d^{\prime}}(G)(v)=\operatorname{\mathsf{cr}}^{d^{\prime}}(H)(w)$
for all $d^{\prime}\leq d$.111This latter fact is because
$\operatorname{\mathsf{cr}}^{d}(G)(v)$ is a pair, whose first component is
$\operatorname{\mathsf{cr}}^{d-1}(G)(v)$ (which is a pair, whose first
component is $\operatorname{\mathsf{cr}}^{d-2}(G)(v)$, and so on), and
similarly for $\operatorname{\mathsf{cr}}^{d}(H)(w)$.

So, assume that
$\operatorname{\mathsf{cr}}(G)(v)=\operatorname{\mathsf{cr}}(H)(w)$. Since, by
definition,

$\displaystyle\operatorname{\mathsf{cr}}(G)(v)$
$\displaystyle=\left(G(v),\\{\\!\\!\\{G(v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}\right)$
$\displaystyle\operatorname{\mathsf{cr}}(H)(w)$
$\displaystyle=\left(H(w),\\{\\!\\!\\{H(w^{\prime})\mid
w^{\prime}\in\operatorname{\mathsf{in}}_{H}(w)\\}\\!\\!\\}\right)$

we may conclude that, $G(v)=H(w)$ and $\\{\\!\\!\\{G(v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}=\\{\\!\\!\\{H(w^{\prime})\mid
w^{\prime}\in\operatorname{\mathsf{in}}_{H}(w)\\}\\!\\!\\}$. Let
$L=(\textsc{Agg},\textsc{Comb})$ be an arbitrary GNN layer. Then,

$\displaystyle\overline{L}(G)(v)$
$\displaystyle=\textsc{Comb}(G(v),\textsc{Agg}\\{\\!\\!\\{G(v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\})$
$\displaystyle=\textsc{Comb}(H(w),\textsc{Agg}\\{\\!\\!\\{H(w^{\prime})\mid
w^{\prime}\in\operatorname{\mathsf{in}}_{H}(w)\\}\\!\\!\\})$
$\displaystyle=\overline{L}(H)(w)\qed$

In other words, $d$-layer GNNs cannot distinguish nodes that are assigned the
same color by $d$ steps of color refinement.

Let $[G,v]_{d}$ denote the set of all nodes in $G$ that receive the same color
as $v$ after $d$ steps of color refinement,

$[G,v]_{d}:=\\{w\in
G\mid\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(G)(w)\\}.$

Then it follows from Proposition 3.1 that $[G,v]_{d}$ is a _refinement_ of
$[G,v]_{\mathcal{S}}$ in the sense that
$[G,v]_{d}\subseteq[G,v]_{\mathcal{S}}$, for all $v\in G$. Morris et al.
(morrisWeisfeilerLemanGo2019) and Xu et al. (xuHowPowerfulAre2019) have also
shown that for every graph $G$ and every depth $d$ there exists a GNN
$\overline{L}$ of $d$ layers such that $[G,v]_{d}=[G,v]_{\\{\overline{L}\\}}$,
for every node $v\in G$. Consequently, if, in addition to containing only GNNs
with at most $d$ layers, $\mathcal{S}$ includes _all possible_ $d$-layer GNNs,
then $[G,v]_{d}=[G,v]_{\mathcal{S}}$ coincide, for all $v\in G$. Hence, for
such $\mathcal{S}$ we may calculate $[G,v]_{\mathcal{S}}$ by calculating
$[G,v]_{d}$ instead. When $\mathcal{S}$ does not include all $d$-layer GNNs we
simply use $[G,v]_{d}$ as a proxy for $[G,v]_{\mathcal{S}}$. This is certainly
safe: since $[G,v]_{d}\subseteq[G,v]_{\mathcal{S}}$ no GNN in $\mathcal{S}$
will be able to distinguish the nodes in $[G,v]_{d}$ and we may hence collapse
nodes in $[G,v]_{d}$ for the purpose of compression. In this case, however, we
risk that $[G,v]_{d}$ contains too few nodes compared to
$[G,v]_{\mathcal{S}}$, and therefore may not provide enough opportunity for
compression. We will return to this issue in Section 3.4.

What happens if there is no bound on the number of layers of GNNs in
$\mathcal{S}$? In that case we can still use color refinement to compute
$[G,v]_{\mathcal{S}}$ as follows. It is known that after a finite number of
color refinements steps we reach a value $d$ such that for all nodes $v\in G$
we have $[G,v]_{d}=[G,v]_{d+1}$. The smallest value $d$ for which this holds
is called the _stable coloring number_ of $G$, and we denote the colored graph
obtained by this value of $d$ by $\operatorname{\mathsf{cr}}^{\infty}(G)$ in
what follows. Similarly we denote the equivalence classes at this value of $d$
by $[G,v]_{\infty}$. From Proposition 3.1 it readily follows:

###### Corollary 3.3.

For any class $\mathcal{S}$ of GNNs, if
$\operatorname{\mathsf{cr}}^{\infty}(G)(v)=\operatorname{\mathsf{cr}}^{\infty}(H)(w)$
then $(G,v)\sim_{\mathcal{S}}(H,w)$.

We note that it is very efficient to compute the set $\\{[G,v]_{d}\mid v\in
G\\}$ of all color refinement classes: this can be done in time
$\mathcal{O}((n+m)\log n)$ with $n$ the number of vertices and $m$ the number
of edges of the input graph (cardonPartitioningGraphLog1982).

###### Example 3.4.

To illustrate, consider the colored graph from Figure 1, as well as the color
refinement steps illustrated there. (Recall that nodes $a_{1},a_{2},a_{3}$
share the same color, as do $b_{1},b_{2},b_{3}$.) Then after one step of color
refinement we have

$\displaystyle\small[G,a_{1}]_{1}$ $\displaystyle=\\{a_{1}\\}$
$\displaystyle[G,a_{2}]_{1}$ $\displaystyle=[G,a_{3}]_{1}=\\{a_{2},a_{3}\\}$
$\displaystyle[G,b_{1}]_{1}$
$\displaystyle=[G,b_{2}]_{1}=[G,b_{3}]_{1}=\\{b_{1},b_{2},b_{3}\\},$

while after two steps of color refinement we obtain the following color
refinement classes:

$\displaystyle\small[G,a_{1}]_{2}$ $\displaystyle=\\{a_{1}\\}$
$\displaystyle[G,b_{1}]_{2}$ $\displaystyle=[G,b_{2}]_{2}=\\{b_{1},b_{2}\\}$
$\displaystyle[G,a_{2}]_{2}$ $\displaystyle=[G,a_{3}]_{2}=\\{a_{2},a_{3}\\}$
$\displaystyle[G,b_{3}]_{2}$ $\displaystyle=\\{b_{3}\\}.$

We invite the reader to check that for every node $v$ in this graph,
$[G,v]_{3}=[G,v]_{2}$. As such, the stable coloring is obtained when $d=2$ and
$[G,v]_{2}=[G,v]_{\infty}$.

###  3.2. Graph reduction

Having established a way to compute redundant nodes, we now turn our attention
to compression. Assume that we have already computed the color refinement
classes $\\{[G,v]_{d}\mid v\in G\\}$ for $d\in\mathbb{N}_{\infty}$. For each
$v\in G$, we wish to “collapse” all nodes in $[G,v]_{d}$ into a single node.
To that end, define a _$d$ -substitution_ on a graph $G$ to be a function that
maps each color refinement class in $\\{[G,v]_{d}\mid v\in G\\}$ to a node
$\rho([G,v]_{d})\in[G,v]_{d}$. Intuitively, $\rho([G,v]_{d})$ is the node that
we wish to keep; all other nodes in $[G,v]_{d}$ will be removed. In what
follows we extend $\rho$ to also operate on nodes in $G$ by setting
$\rho(v)=\rho([G,v]_{d})$.

###### Definition 3.5.

The _reduction of graph $G$ by $d$-substitution $\rho$ on $G$_ is the graph
$H=(V,E,h)$ where

  * •

$V=\\{\rho(v)\mid v\in G\\}$

  * •

For all $v,w\in V$ we have

$E(v\to w)=\sum_{v^{\prime}\in[G,v]_{d}}G(v^{\prime}\to w)$

In particular, if there is no edge into $w$ in $G$, there will be no edge into
$w$ in $H$, as this sum is then zero.

  * •

nodes retain colors: for each node $v\in H$ we have $h(v)=G(v)$.

In what follows, we denote by $G/\rho$ the reduction of $G$ by $\rho$. A graph
obtained by reducing $G$ according to some $d$-substitution $\rho$ is called a
_$d$ -reduct of $G$_.

###### Example 3.6.

Reconsider the colored graph $G$ of Figure 1. Let $\rho_{1}$ and $\rho_{2}$ be
the following $d=1$-substitutions:

$\displaystyle\rho_{1}\colon\\{a_{1}\\}$ $\displaystyle\mapsto a_{1}$
$\displaystyle\\{a_{2},a_{3}\\}$ $\displaystyle\mapsto a_{2}$
$\displaystyle\\{b_{1},b_{2},b_{3}\\}$ $\displaystyle\mapsto b_{1}$
$\displaystyle\rho_{2}\colon\\{a_{1}\\}$ $\displaystyle\mapsto a_{1}$
$\displaystyle\\{a_{2},a_{3}\\}$ $\displaystyle\mapsto a_{2}$
$\displaystyle\\{b_{1},b_{2},b_{3}\\}$ $\displaystyle\mapsto b_{3}$

Then $G/\rho_{1}$ and $G/\rho_{2}$ are illustrated in Figure 2.

$a_{1}$$a_{2}$$b_{1}$$1$$1$$1$$1$$a_{1}$$a_{2}$$b_{3}$$1$$1$$2$ Figure 2.
Reduction of the graph of Figure 1 by the $1$-substitutions $\rho_{1}$ and
$\rho_{2}$ from Example 3.6.

The following proposition is an essential property of our compression
methodology.

For every graph $G$, every $d$-substitution $\rho$ of $G$ with
$d\in\mathbb{N}_{\infty}$, and every node $v\in G$ we have
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(G/\rho)(\rho(v))$.

###### Proof.

Fix $d\in\mathbb{N}_{\infty}$ arbitrarily. When $d\not=\infty$, the statement
follows from Proposition 3.7 below. It hence remains to prove the case where
$d=\infty$. To that end, let $c_{1}\in\mathbb{N}$ be the stable coloring
number of $G$, and let $c_{2}\in\mathbb{N}$ be the stable coloring number of
$G/\rho$. We prove that $c_{1}=c_{2}$. From this, the claimed equality
directly follows:

$\displaystyle\operatorname{\mathsf{cr}}^{\infty}(G)(v)$
$\displaystyle=\operatorname{\mathsf{cr}}^{c_{1}}(G)(v)$
$\displaystyle=\operatorname{\mathsf{cr}}^{c_{2}}(G)(v)$
$\displaystyle=\operatorname{\mathsf{cr}}^{c_{2}}(G/\rho)(\rho(v))$
$\displaystyle=\operatorname{\mathsf{cr}}^{\infty}(G/\rho)(\rho(v))$

Here, the first and last equality are by definition of
$\operatorname{\mathsf{cr}}^{\infty}$; the second equality is because
$c_{1}=c_{2}$; and the third equality is by Proposition 3.7.

To prove that $c_{1}=c_{2}$ it suffices to show that $c_{1}\geq c_{2}$ and
$c_{1}\leq c_{2}$. We only explain how to obtain the inequality $c_{1}\geq
c_{2}$; the other direction is similar.

To show that $c_{1}\geq c_{2}$, we must show that
$[G/\rho,\rho(v)]_{c_{1}}=[G/\rho,\rho(v)]_{c_{1}+1}$ for all nodes
$\rho(v)\in G/\rho$. Since
$[G/\rho,\rho(v)]_{c_{1}}\supseteq[G/\rho,\rho(v)]_{c_{1}+1}$ trivially holds
by definition of $\operatorname{\mathsf{cr}}$, it remains to show that if
$\rho(w)\in[G/\rho,\rho(v)]_{c_{1}}$ then also
$\rho(w)\in[G/\rho,\rho(v)]_{c_{1}+1}$, for all nodes $\rho(w)\in G/\rho$.
Hence, fix $\rho(w)\in G/\rho$ and assume
$\operatorname{\mathsf{cr}}^{c_{1}}(G/\rho)(\rho(v))=\operatorname{\mathsf{cr}}^{c_{1}}(G/\rho)(\rho(w))$.
Then, by Proposition 3.7 we derive

$\displaystyle\operatorname{\mathsf{cr}}^{c_{1}}(G)(v)$
$\displaystyle=\operatorname{\mathsf{cr}}^{c_{1}}(G/\rho)(\rho(v))=\operatorname{\mathsf{cr}}^{c_{1}}(G/\rho)(\rho(w))=\operatorname{\mathsf{cr}}^{c_{1}}(G)(w)$

Since $c_{1}$ is the stable coloring number of $G$ and
$\operatorname{\mathsf{cr}}^{c_{1}}(G)(v)=\operatorname{\mathsf{cr}}^{c_{1}}(G)(w)$,
also
$\operatorname{\mathsf{cr}}^{c_{1}+1}(G)(v)=\operatorname{\mathsf{cr}}^{c_{1}+1}(G)(w)$.
Therefore, again by Proposition Proposition 3.7,

$\displaystyle\operatorname{\mathsf{cr}}^{c_{1}+1}(G/\rho)(\rho(v))$
$\displaystyle=\operatorname{\mathsf{cr}}^{c_{1}+1}(G)(v)$
$\displaystyle=\operatorname{\mathsf{cr}}^{c_{1}+1}(G)(w)$
$\displaystyle=\operatorname{\mathsf{cr}}^{c_{1}+1}(G/\rho)(\rho(w)).$

As such, $\rho(w)\in[G/\rho,\rho(v)]_{c_{1}+1}$, as desired. ∎

###### Proposition 3.7.

For every graph $G$, every $d$-substitution $\rho$ of $G$ with
$d\in\mathbb{N}$ (i.e., $d\not=\infty$), and every node $v\in G$ we have
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(G/\rho)(\rho(v))$.

###### Proof.

Let $d$ be an arbitrary but fixed natural number, and let $\rho$ be a
$d$-substitution of $G$. For ease of readability, let us abbreviate $G/\rho$
by $H$.

Throughout the proof, we will use the following observations.

(O1.) By definition of $d$-substitutions, $\rho([G,v]_{d})\in[G,v]_{d}$ for
every node $v\in G$. Because we have extended $d$-substitutions to nodes by
setting $\rho(v)=\rho([G,v]_{d})$, it follows in particular that
$\rho(v)\in[G,v]_{d}$ for every node $v$. Therefore, by definition of
$[G,v]_{d}$ we have
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(G)(\rho(v))$
for every $v\in G$. Because $d$-step color refinement includes $d-1$-step
color refinement in the first component of the pair that it outputs, this also
implies that
$\operatorname{\mathsf{cr}}^{l}(G)(v)=\operatorname{\mathsf{cr}}^{l}(G)(\rho(v))$
for every $l\leq d$.

(O2.) In addition, we note that for every node $w\in H=G/\rho$ we have
$\rho(w)=w$. Indeed: only nodes that appear in the image of $\rho$ are in
$G/\rho$. As such, if $w\in G/\rho$ there exists some $w^{\prime}$ such that
$w=\rho([G,w^{\prime}]_{d})$. Because
$\rho([G,w^{\prime}]_{d})\in[G,w^{\prime}]_{d}$, it follows that
$w\in[G,w^{\prime}]_{d}$ and as such, $[G,w]_{d}=[G,w^{\prime}]_{d}$. Hence,
$w=\rho([G,w]_{d})=\rho(w)$.

(O3.) In addition, we note that for every node $w\in H$ and every node
$w^{\prime}\in[G,w]_{d}$ we have $\rho(w^{\prime})=w$. Indeed, because
$w^{\prime}\in[G,w]_{d}$ we have $[G,w^{\prime}]_{d}=[G,w]_{d}$. As such
$\rho(w^{\prime})=\rho([G,w^{\prime}]_{d})=\rho([G,w]_{d})=\rho(w)=w$, where
the last equality is due to observation (O2).

(O4.) For every node $v\in H$ we have
$\operatorname{\mathsf{in}}_{H}(v)=\\{\\!\\!\\{\rho(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}$. Indeed, let $E_{H}$ denote
the multiset of edges of $H$ and $E_{G}$ the multiset of edges of $G$. Then

$\displaystyle\operatorname{\mathsf{in}}_{H}(v)$
$\displaystyle=\\{\\!\\!\\{w\mid(w\to v)\in E_{H}\\}\\!\\!\\}$
$\displaystyle=\\{\\!\\!\\{w\mid w^{\prime}\in[G,w]_{d},(w^{\prime}\to v)\in
E_{G}\\}\\!\\!\\}$
$\displaystyle=\\{\\!\\!\\{w\mid\rho(w^{\prime})=w,(w^{\prime}\to v)\in
E_{G}\\}\\!\\!\\}$
$\displaystyle=\\{\\!\\!\\{\rho(w^{\prime})\mid(w^{\prime}\to v)\in
E_{G}\\}\\!\\!\\}$ $\displaystyle=\\{\\!\\!\\{\rho(w^{\prime})\mid
w^{\prime}\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}$
$\displaystyle=\\{\\!\\!\\{\rho(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}$

The first equality is by definition of $\operatorname{\mathsf{in}}_{H}$; the
second because by definition the multiplicity of $w\to v$ in $E_{H}$ equals
$\sum_{w^{\prime}\in[G,w]_{d}}E_{G}(w^{\prime}\to v)$; and the third by (O3).

To prove the proposition, we now prove the stronger statement that for every
$l\leq d$ and every node $v\in G$ we have
$\operatorname{\mathsf{cr}}^{l}(G)(v)=\operatorname{\mathsf{cr}}^{l}(G/\rho)(\rho(v))$.
Clearly
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(G/\rho)(\rho(v))$
then follows when $l=d$.

The proof of this stronger statement is by induction on $l$. For the base case
when $l=0$ we have, for every $v\in G$,

$\operatorname{\mathsf{cr}}^{0}(H)(\rho(v))=H(\rho(v))=G(\rho(v))=\operatorname{\mathsf{cr}}^{0}(G)(\rho(v))=\operatorname{\mathsf{cr}}^{0}(G)(v)$

as desired. Here, the first equality is by definition of
$\operatorname{\mathsf{cr}}^{0}$; the second is by definition of $H=G/\rho$;
the third is again by definition of $\operatorname{\mathsf{cr}}^{0}$; and the
final equality is by observation (O1).

For the inductive case $l>0$, consider an arbitrary node $v\in G$. Then, by
definition,

$\displaystyle\operatorname{\mathsf{cr}}^{l}(G)(v)$
$\displaystyle=(\operatorname{\mathsf{cr}}^{l-1}(G)(v),\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(G)(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\})$
$\displaystyle\operatorname{\mathsf{cr}}^{l}(H)(\rho(v))$
$\displaystyle=(\operatorname{\mathsf{cr}}^{l-1}(H)(\rho(v)),\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(H)(w^{\prime})\mid
w^{\prime}\in\operatorname{\mathsf{in}}_{H}(\rho(v))\\}\\!\\!\\})$

To show that
$\operatorname{\mathsf{cr}}^{l}(G)(v)=\operatorname{\mathsf{cr}}^{l}(H)(\rho(v))$
we hence need to show:

  1. (i)

$\operatorname{\mathsf{cr}}^{l-1}(G)(v)=\operatorname{\mathsf{cr}}^{l-1}(H)(\rho(v))$;
and

  2. (ii)

$\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(G)(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\})=\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(H)(w^{\prime})\mid
w^{\prime}\in\operatorname{\mathsf{in}}_{H}(\rho(v))\\}\\!\\!\\}$.

Equality (i) follows directly from the induction hypothesis. To show (ii), we
reason as follows:

$\displaystyle\\{\\!\\!\\{$
$\displaystyle\operatorname{\mathsf{cr}}^{l-1}(H)(w^{\prime})\mid
w^{\prime}\in\operatorname{\mathsf{in}}_{H}(\rho(v))\\}\\!\\!\\})$
$\displaystyle=\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(H)(w^{\prime})\mid
w^{\prime}\in\\{\\!\\!\\{\rho(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(\rho(v))\\}\\!\\!\\}\\}\\!\\!\\})$
$\displaystyle=\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(H)(\rho(w))\mid
w\in\operatorname{\mathsf{in}}_{G}(\rho(v))\\}\\!\\!\\}$
$\displaystyle=\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(G)(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(\rho(v))\\}\\!\\!\\}$
$\displaystyle=\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{l-1}(G)(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}$

The first equality is due to observation (O3); the second is an elementary
equality of multiset comprehensions; the third is by induction hypothesis; and
the fourth is because
$\operatorname{\mathsf{cr}}^{l}(G)(v)=\operatorname{\mathsf{cr}}^{l}(G)(\rho(v)$
by Observation (O1). In particular, the next-to-last line is exactly the
second component of the color $\operatorname{\mathsf{cr}}^{l}(G)(\rho(v)$ and
the last line is the second component of
$\operatorname{\mathsf{cr}}^{l}(G)(v)$, which must hence be equal. ∎

It hence follows from Proposition 3.1 and Corollary 3.3 that if $\mathcal{S}$
consists of GNNs of at most $d\in\mathbb{N}_{\infty}$ layers, then
$(G,v)\sim_{\mathcal{S}}(G/\rho,\rho(v))$.

#### Discussion

Example 3.6 shows that the choice of $d$-substitution determines the reduct
$G/\rho$ that we obtain. In particular, the example shows that distinct
substitutions can yield distinct, _non-isomorphic_ reducts. This behavior is
unavoidable, unless $d$ is the stable coloring number of $G$. Indeed, we are
able to show:

###### Lemma 3.8.

Let $H_{1}=G/\rho_{1}$ and $H_{2}=G/\rho_{2}$ be two $d$-reducts of $G$ and
let $f$ be an isomorphism from $H_{1}$ to $H_{2}$. Then $f$ agrees with
$\rho_{2}$: $f(u)=\rho_{2}(v)$ for all $u\in H_{1}$.

###### Proof.

It is straightforward to verify by induction on $d$ that
$\operatorname{\mathsf{cr}}^{d}$ is invariant under isomorphism, in the sense
that
$\operatorname{\mathsf{cr}}^{d}(H_{1})(u)=\operatorname{\mathsf{cr}}^{d}(H_{2})(f(u))$
for all $u\in H_{1}$. Therefore, for all $u\in H_{1}$

$\displaystyle\operatorname{\mathsf{cr}}^{d}(G)(u)$
$\displaystyle=\operatorname{\mathsf{cr}}^{d}(H_{1})(\rho_{1}(u))$
$\displaystyle=\operatorname{\mathsf{cr}}^{d}(H_{1})(u)$
$\displaystyle=\operatorname{\mathsf{cr}}^{d}(H_{2})(f(u))$
$\displaystyle=\operatorname{\mathsf{cr}}^{d}(H_{2})(\rho_{2}(f(u)))$
$\displaystyle=\operatorname{\mathsf{cr}}^{d}(G)(f(u))$

The first equality is by Proposition 3.2; the second by the fact that
$\rho_{1}(u)=u$ for all $u\in H_{1}$; the third by invariance under
isomorphisms; the fourth by the fact that $f(u)\in H_{2}$ and
$\rho_{2}(u^{\prime})=u^{\prime}$ for every $u^{\prime}\in H_{2}$ ; and the
last again by Proposition 3.2.

In other words, $f(u)\in[G,u]_{d}$, for every $u\in H_{1}$. Then, because
$f(u)\in H_{2}$ and $H_{2}$ contains only one node for each color refinement
class in $\\{[G,u]_{d}\mid u\in G\\}$, it follows that $\rho_{2}(u)=f(u)$, for
every $u\in H_{1}$ (including $v$). ∎

There is a single $d$-reduct of a graph $G$ up to isomorphism if and only if
$d$ is greater than or equal to the stable coloring number of $G$.

###### Proof.

(If.) For the if-implication, assume that $c$ is the stable coloring number of
$G$ and let $d\geq c$, $d\in\mathbb{N}$. Then, for all nodes $v\in G$ we have
$[G,v]_{d}=[G,v]_{d+1}$. Let $H_{1}=G/\rho_{1}$ and $H_{2}=G/\rho_{2}$ be two
$d$-reducts of $G$. Let $V_{1}=\\{\rho_{1}(v)\mid v\in G\\}$ be the set of
nodes in $H_{1}$ and $V_{2}=\\{\rho_{2}(v)\mid v\in G\\}$ be the set of nodes
in $H_{2}$. It is clear that $V_{1}$ and $V_{2}$ are of the same cardinality,
as they have one node for each color refinement class in $\\{[G,v]_{d}\mid
v\in G\\}$. It is furthermore straightforward to obtain that $\rho_{1}(v)=v$
for all $v\in V_{1}$, and similarly $\rho_{2}(v)=v$ for all $v\in V_{2}$.

We claim that the function $f={\rho_{2}}|_{V_{1}}$ is an isomorphism from
$H_{1}$ to $H_{2}$.

(1) This function is injective: assume that $v,w\in V_{1}$ and
$\rho_{2}(v)=\rho_{2}(w)$. Since, by defintion of $d$-substitutions, we have
$\rho_{2}(v)\in[G,v]_{d}$ and $\rho_{2}(w)\in[G,w]_{d}$ it follows that
$[G,v]_{d}=[G,w]_{d}$. Because $v,w\in V_{1}$ we have $\rho_{1}(v)=v$ and
$\rho_{1}(w)=w$. As such
$v=\rho_{1}(v)=\rho_{1}([G,v]_{d})=\rho_{1}([G,w]_{d})=w$ as desired.

(2) Since $f$ is an injective function from $V_{1}$ to $V_{2}$ and $V_{1}$ and
$V_{2}$ are finite sets of the same cardinality, it is also surjective. Hence
$f$ is a bijection between $V_{1}$ and $V_{2}$.

(3) It remains to show that for all $v,w\in V_{1}$ we have

$H_{1}(v\to w)=H_{2}\left(\rho_{2}(v)\to\rho_{2}(w)\right).$

Fix $v,w\in V_{1}$ arbitrarily. By definition of $\rho_{2}$ we have
$\rho_{2}(w)\in[G,w]_{d}$ and because $[G,w]_{d}=[G,w]_{d+1}$ ($d$ is larger
than the stable coloring number of $G$) it follows that
$\rho_{2}(w)\in[G,w]_{d+1}$. Therefore,
$\operatorname{\mathsf{cr}}^{d+1}(G)(w)=\operatorname{\mathsf{cr}}^{d+1}(G)(\rho_{2}(w))$.
In particular,

$\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G)(v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(w)\\}\\!\\!\\}=\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G)(v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(\rho_{2}(w))\\}\\!\\!\\}$

Hence, for any $v\in G$ we also have

(1) $\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G)(v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(w),v^{\prime}\in[G,v]_{d}\\}\\!\\!\\}\\\
=\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G)(v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(\rho_{2}(w)),v^{\prime}\in[G,v]_{d}\\}\\!\\!\\}$

Let us denote the total multplicity of a finite multiset $M$ by $\\#M$, i.e.,
$\\#M=\sum_{x}M(x)$. Then we reason as follows.

$\displaystyle H_{1}(v\to w)$
$\displaystyle=\sum_{v^{\prime}\in[G,v]_{d}}G(v^{\prime}\to w)$
$\displaystyle=\\#\\{\\!\\!\\{v^{\prime}\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(w),v^{\prime}\in[G,v]_{d}\\}\\!\\!\\}$
$\displaystyle=\\#\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G,v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(w),v^{\prime}\in[G,v]_{d}\\}\\!\\!\\}$
$\displaystyle=\\#\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G,v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(\rho_{2}(w)),v^{\prime}\in[G,v]_{d}\\}\\!\\!\\}$
$\displaystyle=\\#\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G,v^{\prime})\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(\rho_{2}(w)),v^{\prime}\in[G,\rho_{2}(v)]_{d}\\}\\!\\!\\}|$
$\displaystyle=\\#\\{\\!\\!\\{v^{\prime}\mid
v^{\prime}\in\operatorname{\mathsf{in}}_{G}(\rho_{2}(w)),v^{\prime}\in[G,\rho_{2}(v)]_{d}\\}\\!\\!\\}|$
$\displaystyle=\sum_{v^{\prime}\in[G,\rho_{2}(v)]_{d}}G(v^{\prime}\to\rho_{2}(w))$
$\displaystyle=H_{2}(\rho_{2}(v)\to\rho_{2}(w))$

The first equality is by definition of $H_{1}$; the second is by rewriting the
sum in multiset notation; the third because we are only interested in the
total multiplicity of the multiset and not its elements; the fourth by
$(\star$); the fifth because $[G,v]_{d}=[G,\rho(v)]_{d}$ by definition of
$d$-substitutions; the sixth again because we care only about multiplicity and
not the actual elements; the seventh by rewriting the multiset notation into a
sum; and the last by definition of $H_{2}$.

(Only if). Assume that all $d$-reducts of $G$ are isomorphic. We need to show
that for all $v\in G$ we have $[G,v]_{d}=[G,v]_{d+1}$. The containment
$[G,v]_{d}\supseteq[G,v]_{d+1}$ trivially holds by definition of
$\operatorname{\mathsf{cr}}$. For the other containment, assume that
$w\in[G,v]_{d}$, i.e.,
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(G)(w)$.
We will show that also
$\operatorname{\mathsf{cr}}^{d+1}(G)(v)=\operatorname{\mathsf{cr}}^{d+1}(G)(w)$,
which is equivalent to saying that $w\in[G,v]_{d+1}$.

Recall that $\operatorname{\mathsf{cr}}^{d+1}(G)(v)$ and
$\operatorname{\mathsf{cr}}^{d+1}(G)(w)$ are pairs by definition. Since
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(G)(w)$ by
assumption, the first components of of these pairs are certainly equal. To
prove
$\operatorname{\mathsf{cr}}^{d+1}(G)(v)=\operatorname{\mathsf{cr}}^{d+1}(G)(w)$,
we hence only need to show that also their second components are equal, i.e.,
that

(${\ddagger}$)
$\underbrace{\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G)(u)\mid
u\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}}_{=:M_{1}}=\underbrace{\\{\\!\\!\\{\operatorname{\mathsf{cr}}^{d}(G)(u)\mid
u\in\operatorname{\mathsf{in}}_{G}(w)\\}\\!\\!\\}}_{=:M_{2}}$

To obtain this equality, consider two $d$-substitutions $\rho_{1}$ and
$\rho_{2}$ s.t.

$\displaystyle\rho_{1}$ $\displaystyle\colon[G,v]_{d}\mapsto v$
$\displaystyle\rho_{2}$ $\displaystyle\colon[G,v]_{d}\mapsto w$

In other words, $\rho_{1}(v)=\rho_{1}(w)=v$ and $\rho_{2}(v)=\rho_{2}(w)=w$.
By assumption, $H_{1}=G/\rho_{1}$ and $H_{2}=G/\rho_{2}$ are isomorphic. Let
$f$ be an isomorphism from $H_{1}$ to $H_{2}$. By Lemma 3.8 $f$ agrees with
$\rho_{2}$: $f(u)=\rho_{2}(u)$ for all $u\in H_{1}$ (including $v$).
Furthermore, by definition of isomorphism, for all $u\in H_{1}$ we have
$H_{1}(u\to v)=H_{2}(f(u)\to
f(v))=H_{2}(\rho_{2}(u)\to\rho_{2}(v))=H_{2}(\rho_{2}(u)\to w)$.

To show that $M_{1}=M_{2}$ we show that for every $x$, $M_{1}(x)\leq M_{2}(x)$
and $M_{2}(x)\leq M_{1}(x)$. We only illustrate the reasoning for
$M_{1}(x)\leq M_{2}(x)$, the converse direction is similar. Consider an
element $x$ in $M_{1}$, and let $m=M(x)$ be its multiplicity. Then there
exists some $u\in\operatorname{\mathsf{in}}_{G}(v)$ such that
$x=\operatorname{\mathsf{cr}}^{d}(G)(u)$, and $x$ occurs as many times in
$M_{1}$ as there are elements in $M^{\prime}_{1}:=\\{\\!\\!\\{u^{\prime}\mid
u^{\prime}\in\operatorname{\mathsf{in}}_{G}(v),u^{\prime}\in[G,u]_{d}\\}\\!\\!\\}$,
i.e., $m_{1}=\\#M^{\prime}_{1}$. Because $[G,u]_{d}=[G,\rho_{1}(u)]_{d}$ for
all $u\in G$, it follows that

$\displaystyle m_{1}$ $\displaystyle=\\#\\{\\!\\!\\{u^{\prime}\mid
u^{\prime}\in\operatorname{\mathsf{in}}_{G}(v),u^{\prime}\in[G,u]_{d}\\}\\!\\!\\}$
$\displaystyle=\\#\\{\\!\\!\\{u^{\prime}\mid
u^{\prime}\in\operatorname{\mathsf{in}}_{G}(v),u^{\prime}\in[G,\rho_{1}(u)]_{d}\\}\\!\\!\\}$
$\displaystyle=H_{1}(\rho_{1}(u)\to v)$
$\displaystyle=H_{2}(\rho_{2}(\rho_{1}(u))\to w)$
$\displaystyle=\\#\\{\\!\\!\\{u^{\prime}\mid
u^{\prime}\in\operatorname{\mathsf{in}}_{G}(w),u^{\prime}\in[G,\rho_{2}(\rho_{1}(u))]_{d}\\}\\!\\!\\}$
$\displaystyle=\\#\\{\\!\\!\\{u^{\prime}\mid
u^{\prime}\in\operatorname{\mathsf{in}}_{G}(w),u^{\prime}\in[G,u]_{d}\\}\\!\\!\\}$

The last equality is because $[G,\rho_{2}(\rho_{1}(u))]_{d}=[G,u]_{d}$ by
definition of $d$-reducts. Notice that all elements $u^{\prime}$ in the
multiset on the last line will create one copy of
$\operatorname{\mathsf{cr}}^{d}(G)(u^{\prime})=\operatorname{\mathsf{cr}}^{d}(G)(u)$
in $M_{2}$. As such, $x=\operatorname{\mathsf{cr}}^{d}(G)(u)$ occurs at least
$m$ times in $M_{2}$, as desired. ∎

A direct consequence of having different non-isomorphic reducts when $d$ is
less than the coloring number is that some of these reducts may be smaller
than others. In Example 3.6, $G/\rho_{1}$ has $3$ nodes and $4$ edges while
$G/\rho_{2}$ has $3$ nodes and only $3$ edges. We may always obtain a
$d$-reduct of minimal size as follows. For $d\in\mathbb{N}_{\infty}$, define
the _$d$ -incidence_ of a node $w\in G$, denoted
$\operatorname{\mathsf{incidence}}^{d}_{G}(w)$, to be the number of color
refinement classes in $\\{[G,v]_{d}\mid v\in G\\}$ that contain an incoming
neighbor of $w$. That is, the $d$-incidence of $w$ is the number of distinct
classes in $\\{[G,u]_{d}\mid u\in\operatorname{\mathsf{in}}_{G}(w)\\}$. The
following proposition shows that we obtain a $d$-reduct of minimal size by by
choosing a $d$-substitution that maps color refinement classes to nodes of
minimal $d$-incidence.

Let $G$ be a graph, let $d\in\mathbb{N}_{\infty}$ and let $\rho$ be a
$d$-substitution such that

$\operatorname{\mathsf{incidence}}^{d}_{G}(\rho(v))=\min_{v^{\prime}\in[G,v]_{d}}\operatorname{\mathsf{incidence}}^{d}_{G}(v^{\prime}),$

for every node $v\in G$. Then the size of $G/\rho$ is minimal among all
$d$-reducts of $G$.

###### Proof.

Since $\infty$-substitutions are simply $d$-substitutions with
$d\in\mathbb{N}$ the stable coloring number of $G$, it suffices to show the
statement for all $d\in\mathbb{N}$.

Fix $d\in\mathbb{N}$, let $C=\\{[G,v]_{d}\mid v\in G\\}$ be the color
refinement classes of $G$ of depth $d$, and let $\rho$ be a $d$-substitution
such that

$\operatorname{\mathsf{incidence}}^{d}_{G}(\rho(c))=\min_{v^{\prime}\in
c}\operatorname{\mathsf{incidence}}^{d}_{G}(v),$

for every refinement class $c\in C$. Let $H=G/\rho$. Furthermore, let $\mu$ be
another $d$-substitution and let $U=G/\mu$. We will show that $H$, viewed as a
simple graph by ignoring edge multiplicities, has no more edges than $U$.

Note that for each class $c\in C$ there is exactly one corresponding node in
$H$ (namely, $\rho(c)$) and one corresponding node in $U$ (namely $\mu(c)$).
We claim that, for every $c\in C$, the indegree222That is, the number of nodes
$w$ in $H$ having an outgoing edge to $\rho(c)$. of $\rho(c)$ in $H$ is at
most the indegree of $\mu(c)$ in $U$. Since the total number of simple edges
in $H$ equals $\sum_{c\in C}\textsf{indegree}_{H}(\rho(c))$ and the total
number of simple edges in $U$ similarly equals $\sum_{c\in
C}\textsf{indegree}_{U}(\mu(c))$, it follows that $H$, viewed as a simple
graph, has no more edges than $U$.

To prove the claim, let $c\in C$. There is an edge from
$\rho(c^{\prime})\to\rho(c)$ in $H$ if and only if
$[G,\rho(c^{\prime})]_{d}\cap\operatorname{\mathsf{in}}_{G}(\rho(c))$ is non-
empty. Hence, since $[G,\rho(c^{\prime})]_{d}=c^{\prime}$, the indegree of
$\rho(c)$ in $H$ is exactly
$\operatorname{\mathsf{incidence}}^{d}_{G}(\rho(c))$. Similar reasoning shows
that the indegree of $\mu(c)$ in $U$ equals
$\operatorname{\mathsf{incidence}}^{d}_{G}(\mu(c))$. As such,

$\displaystyle\textsf{indegree}_{H}(\rho(c))$
$\displaystyle=\operatorname{\mathsf{incidence}}^{d}_{G}(\rho(c))$
$\displaystyle=\min_{v^{\prime}\in
c}\operatorname{\mathsf{incidence}}^{d}_{G}(v^{\prime})$
$\displaystyle\leq\operatorname{\mathsf{incidence}}^{d}_{G}(\mu(c))$
$\displaystyle=\textsf{indegree}_{U}(\mu(c))$

The inequality in the third line is because $\mu(c)\in c$ by definition of
$d$-substitution. ∎

When we report the size of $d$-reducts in our experiments (Section 4), we
always report the minimal size among all $d$-reducts.

#### Discussion

Example 3.6 illustrates that, depending on the substitution used, the result
of reducing a simple graph may be a multigraph. In the literature, however,
GNNs and color refinement are normally defined to operate on simple graphs.
One may therefore wonder whether it is possible to define a different notion
of reduction that always yields a simple graph when executed on simple,
instead of a multigraph as we propose here. To answer this question, consider
the tree-shaped graph $G$ in Figure 3(left), whose root $v$ has $m$
$b$-colored children, each having $n$ $c$-labeled children. It is
straightforward to see that when $d\geq 2$, any simple graph $H$ that has a
node $w$ such that
$\operatorname{\mathsf{cr}}^{d}(G)(v)=\operatorname{\mathsf{cr}}^{d}(H)(w)$
must be such that $w$ has $m$ $b$-colored children in $H$, each having $n$
$c$-labeled children. As such, because $H$ is simple, it must be of size at
least as large as $G$. Instead, by moving to multigraphs we are able to
compress this “regular” structure in $G$ by only three nodes, as show in
Figure 3(right). This illustrates that for the purpose of compression we
naturally need to move to multigraphs.

$v$$b_{1}$…$b_{m}$$c^{1}_{1}$…$c^{1}_{n}$$c^{m}_{1}$…$c^{m}_{n}$$v$$b_{1}$$c^{1}_{1}$$n$$m$
Figure 3. Reduction of a tree-shaped simple graph (left) into a small
multigraph (right).

###  3.3. Problem compression

We next combine the insights from Sections 3.1 and 3.2 into a method for
compressing learning problems.

Let $\mathcal{P}=(G,T,\operatorname{\textsc{Loss}},\mathcal{S})$ be a learning
problem. Let $\rho$ be a $d$-substitution. We then define the reductions
$T/\rho$ and $\operatorname{\textsc{Loss}}/\rho$ of $T$ and
$\operatorname{\textsc{Loss}}$ by $\rho$ as follows:

$\displaystyle T/\rho$ $\displaystyle=\\{\rho(v)\mid v\in T\\}$
$\displaystyle\operatorname{\textsc{Loss}}/\rho(v,c)$
$\displaystyle=\sum_{w\in T\cap[G,v]_{d}}\operatorname{\textsc{Loss}}(w,c)$

We denote by $\mathcal{P}/\rho$ the learning problem
$(G/\rho,T/\rho,\operatorname{\textsc{Loss}}/\rho,\mathcal{S})$.

Let $\mathcal{P}$ be a learning problem with hypothesis space $\mathcal{S}$
and assume that $d\in\mathbb{N}_{\infty}$ is such that every GNN in
$\mathcal{S}$ has at most $d$ layers. (In particular, $d=\infty$ if there is
no bound on the number of layers in $\mathcal{S}$.) Then
$\mathcal{P}\equiv\mathcal{P}/\rho$ for every $d$-substitution $\rho$.

###### Proof.

Let
$\mathcal{P}/\rho=(G^{\prime},T^{\prime},\operatorname{\textsc{Loss}}^{\prime})$,
so $G^{\prime}=G/\rho$; $T^{\prime}=T/\rho$, and
$\operatorname{\textsc{Loss}}^{\prime}=\operatorname{\textsc{Loss}}/\rho$.
Consider an arbitrary but fixed GNN $\overline{L}\in\mathcal{S}$. We need to
show that
$\operatorname{\textsc{Loss}}(\overline{L}(G),T)=\operatorname{\textsc{Loss}}^{\prime}(\overline{L}(G^{\prime}),T^{\prime})$.
To that end, first observe that for every node $v\in G^{\prime}$ and every
node $w\in[G,v]_{d}$ we have $\rho(w)=v$. Consequently,

$\displaystyle\operatorname{\mathsf{cr}}^{d}(G^{\prime},v)=\operatorname{\mathsf{cr}}^{d}(G^{\prime},\rho(w))=\operatorname{\mathsf{cr}}^{d}(G/\rho,\rho(w))=\operatorname{\mathsf{cr}}^{d}(G,w),$

Here, the last equality follows from Proposition 3.2. Hence, by Proposition
3.1 (or Corollary 3.3 when $d=\infty$),
$(G^{\prime},v)\sim_{\mathcal{S}}(G,w)$ and such
$\overline{L}(G^{\prime})(v)=\overline{L}(G)(w)$ for every $v\in G^{\prime}$
and $w\in[G,v]_{d}$.

Using this observation we now reason as follows.

$\displaystyle\operatorname{\textsc{Loss}}^{\prime}(\overline{L}(G^{\prime}),T^{\prime})$
$\displaystyle=\sum_{v\in
T^{\prime}}\operatorname{\textsc{Loss}}^{\prime}(v,\overline{L}(G^{\prime})(v))$
$\displaystyle=\sum_{v\in T^{\prime}}\sum_{w\in
T\cap[G,v]_{D}}\operatorname{\textsc{Loss}}(w,\overline{L}(G^{\prime})(v))$
$\displaystyle=\sum_{v\in T^{\prime}}\sum_{w\in
T\cap[G,v]_{D}}\operatorname{\textsc{Loss}}(w,\overline{L}(G)(w))$
$\displaystyle=\sum_{w\in
T}\operatorname{\textsc{Loss}}(w,\overline{L}(G)(w))$
$\displaystyle=\operatorname{\textsc{Loss}}(\overline{L}(G),T)$

The second equality is by definition of
$\operatorname{\textsc{Loss}}^{\prime}$. The third equality follows from our
observation. The fourth equality is because $T=\bigcup_{v\in
T^{\prime}}[G,v]_{d}\cap T$. ∎

###  3.4. Graded Color Refinement

So far, we have focused on compression based on the _depth_ of the GNNs
present in the hypothesis space, where the depth of a GNN equals its number of
layers and the depth of a hypothesis space $\mathcal{S}$ is the maximum depth
of any of its GNNs, or $\infty$ if this maximum is unbounded. In particular,
the notion of $d$-reduct hinges on this parameter $d$ through the calculated
color refinement classes $[G,v]_{d}$.

As we have already observed in Section 3.1, however, when $\mathcal{S}$ does
not contain all $d$-layer GNNs the color refinement classes $[G,v]_{d}$ that
we base compression on may contain too few nodes compared to
$[G,v]_{\mathcal{S}}$ and may therefore not provide enough opportunity for
compression.

In such cases, it may be beneficial to move to more fine-grained notions of
color refinement that better capture $[G,v]_{\mathcal{S}}$. In this section we
propose one such fine-grained notion, which takes into account the “width” of
$\mathcal{S}$. We say that _GNN $\overline{L}$ has width
$c\in\mathbb{N}_{\infty}$_ if for every layer in $\overline{L}$ the
aggregation function Agg is such that $\textsc{Agg}(M)=\textsc{Agg}({M}|_{\leq
c})$ for every multiset $M$. In other words: Agg can only “count” up to $c$
copies of a neighbor’s color. When $c=\infty$ there is no limit on the count.
The width of $\mathcal{S}$ is then the maximum width of any of its GNNs, or
$\infty$ if this maximum is unbounded. Hypothesis spaces of bounded width
clearly do not contain _all_ $d$-layer GNNs, for any depth $d$.

While we know of no practical GNN architectures that explicitly limit the
width, there are influential learning _algorithms_ that implicitly limit the
width. For example, to speed up learning, GraphSAGE
(hamiltonInductiveRepresentationLearning2017) can be parametrized by a
hyperparameter $c$. When $c<\infty$ GraphSAGE does not consider all of a
node’s neighbors in each layer, but only a random sample of at most $c$
neighbors of that node. Such sampling effectively limits the width of
$\mathcal{S}$.

We next define a variant of color refinement, called _graded_ color
refinement, that takes width into account. It may lead to larger color
refinement classes, and therefore potentially also to better compression.

###### Definition 3.9.

Let $c\in\mathbb{N}_{\infty}$. The (one-step) _$c$ -graded color refinement_
of colored graph $G=(V,E,g)$, denoted $\operatorname{\mathsf{cr}}_{c}(G)$, is
the colored graph $G^{\prime}=(V,E,g^{\prime})$ with

$g^{\prime}\colon v\mapsto\big{(}G(v),{\\{\\!\\!\\{G(w)\mid
w\in\operatorname{\mathsf{in}}_{G}(v)\\}\\!\\!\\}}|_{\leq c}\big{)}.$

Note that $\operatorname{\mathsf{cr}}_{\infty}$ equals normal, non-graded,
color refinement. We also remark that $\operatorname{\mathsf{cr}}_{c}$ with
$c=1$ corresponds to standard _bisimulation_ on graphs
(baierPrinciplesModelChecking2008). We denote by
$\operatorname{\mathsf{cr}}_{c}^{d}(G)$ the result of applying $d$ refinement
steps of $c$-graded color refinement, so
$\operatorname{\mathsf{cr}}_{c}^{0}(G)=G$ and
$\operatorname{\mathsf{cr}}_{c}^{d+1}=\operatorname{\mathsf{cr}}(\operatorname{\mathsf{cr}}_{c}^{d}(G))$.
We denote by $[G,v]_{c,d}$ the set of all nodes in $G$ that receive the same
color after $d$ steps of $c$-graded color refinement. The concept of
$(c,d)$-substitution is then defined analogously to $d$-substitution, as
mappings from the $[G,v]_{c,d}$ color refinement classes to nodes in these
classes. The reduction of a graph $G$ by a $(c,d)$ substitution is similar to
reductions by $d$-substitution except that the edge multiplicity $E(v\to w)$
for $v,w$ in the reduction is now limited to $c$, i.e.,

$E(v\to w)=\sum_{v^{\prime}\in[G,v]_{c,d}}{G(v^{\prime}\to w)}|_{\leq c}.$

With these definitions, we can show that for any $\mathcal{P}$ with hypothesis
space $\mathcal{S}$ of width $c$ and depth $d$ we have
$\mathcal{P}\equiv\mathcal{P}/\rho$ for any $(c,d)$-reduction $\rho$. The full
development is omitted due to lack of space.

We note that $[G,v]_{d}\subseteq[G,v]_{c,d}$, always. Graded color refinement
hence potentially leads to better compression, but only applies to problems
with hypothesis spaces of width $c$. We will empirically contrast the
compression ratio obtained by $(c,d)$-reducts to those obtained by $d$-reducts
(i.e., where $c=\infty$) in Section 4. There, we also study the effect of $c$
on learning accuracy for problems whose width is not bounded.

##  4\. Evaluation

In this section, we empirically evaluate the compression methodology described
in Section 3. We first give insights into the compression ratios that can be
obtained on real-world graphs in Section 4.1. Subsequently, we evaluate the
learning on compressed graphs versus learning on the original graphs.

###  4.1. Compression

We consider the real-world graphs listed in Table 1. The ogbn-* graphs are
from the Open Graph Benchmark (OGB), a collection of realistic, large-scale,
and diverse benchmark datasets for machine learning on graphs
(huOpenGraphBenchmark2020), where they belong to the OGB node property
prediction benchmark (OGBN). Specifically, ogbn-arxiv is a network of academic
papers, where edge $x\to y$ indicates that $x$ cites $y$. Graph ogbn-arxiv-inv
is the inverted version of ogbn-arxiv; it is obtained by reversing edges, so
that edge $x\leftarrow y$ indicates that $y$ was cited by $x$. Graph ogbn-
arxiv-undirected is the undirected version of ogbn-arxiv; it is obtained by
adding inverse edges to ogbn-arxiv. Next, there is ogbn-products, an
undirected graph representing an Amazon product co-purchasing network. The
other datasets are from the Stanford Large Network Dataset Collection (SNAP)
(leskovecSNAPDatasetsStanford). Here, snap-roadnet-ca, snap-roadnet-pa, and
snap-roadnet-tx are undirected graphs representing road networks, and snap-
soc-pokec is a directed graph containing an online social network.

Graph | Type | #Nodes | #Edges
---|---|---|---
[ late after line= |  |  |
, late after last line= |  |  |
Table 1. Datasets

The input colors used for learning on these graphs typically depend on the
application. To get an understanding of the maximum amount of compression that
we can obtain independent of the target application, we assign a shared single
color $c$ to each node, in all graphs. As such, the color refinement classes
$[G,v]_{d}$ that we obtain are maximal, in the sense that for any other
colorored graph $G^{\prime}$ whose topology equals $G$ we will have
$[G^{\prime},v]_{d}\subseteq[G,v]_{d}$. In this setting, we hence reach
maximal compression.

We consider three versions of ogbn-arxiv to get an indication of how edge
directionality impacts compression. Recall that GNN layers propagate color
information following the direction of edges. Hence, because in ogbn-arxiv an
edge $x\to y$ indicates that $x$ cites $y$, color information flows from
citing papers to cited papers. In ogbn-arxiv-inv, by contrast, it flows from
cited papers to citing papers while in ogbn-arxiv-undirected it flows in both
directions. The direction in which the information can flow impacts the number
of color refinement classes that we obtain, and hence the compression, as we
will see.

$0$$2$$4$$6$$0$$0.5$$1$Refinement depth $d$$(a)$ $\%$ of nodes in $d$-reduct
relative to original

$0$$2$$4$$6$$0$$0.5$$1$Refinement depth $d$$(b)$ $\%$ of edges in $d$-reduct
relative to original

$1$$2$$3$$4$$5$$0$$0.5$$1$Grade $c$$(c)$ $\%$ of nodes in $(c,3)$ reduct
relative to $3$-reduct

$1$$2$$3$$4$$5$$0$$0.5$$1$Grade $c$$(d)$ $\%$ of edges in $(c,3)$ reduct
relative to $3$-reduct

4

Figure 4. Normalized reduction in nodes and edges using $d$-reduction (a and
b) and $(c,3)$-reduction (c and d).

#### Ungraded compression

Figures 4(a) and 4(b) shows the fraction of nodes and edges remaining in
$d$-reducts of these graphs, plotted as a function of the number of color
refinement rounds $d$. (Consistent with our definition of the size of a
multigraph, the number of edges plotted is the number of unique edges, i.e.,
ignoring edge multiplicities.) We see that in terms of the number of nodes,
compression is effective for $d\leq 2$, obtaining compression ratios of
$0.03\%-0.05\%$ on the road network datasets, to $77\%$ on ogbn-products. For
$d=3$, compression becomes ineffective for ogbn-arxiv-undirected, ogbn-
products and snap-soc-pokec as these retain $88\%$ of their nodes or more.
Compression on the other datasets is satsifactory for $d=3$, as shown in Table
2. From $d>3$ onwards, node compression becomes ineffective for most datasets,
with all datasets except ogbn-arxiv retaining at least $86\%$ of their nodes
when $d\geq 5$. By contrast, ogbn-arxiv stabilizes at $d=4$, retaining only
$36\%$ of its nodes.

In terms of the number of edges, we see that ogbn-arxiv-inv, ogbn-arxiv-
undirected, ogbn-products, and snap-soc-pokec retain almost $100\%$ of their
edges from $d\geq 2$ onwards, while ogbn-arxiv retains only $56\%$ of its
edges when $d=3$ and the road networks compress to $5\%-8\%$ of the edges when
$d=3$.

While we may hence conclude that in general compression becomes ineffective
for deeper layer numbers, $d>4$, we note that in practice most GNN topologies
use only $d=3$ layers. For such GNNs, compression on ogbn-arxiv and the road
networks is promising.

One may wonder why the inverted and undirected variants of ogbn-arxiv differ
so much in terms of compression. The short answer is that that, their graph
topology is completely different. As such, the local neighborhood information
that $\operatorname{\mathsf{cr}}^{d}$ calculates is also completely different,
yielding different reductions. For example, a manual inspection of ogbn-arxiv
reveals a number of highly cited papers that have no outgoing edges. While
these papers are the “sink nodes” in ogbn-arxiv, they are “source nodes” in
ogbn-arxiv-inv. Quite quickly we may then distinguish nodes in ogbn-arxiv-inv
based solely on the number of highly cited papers that they cite. This
behavior does not occur in ogbn-arxiv, because the highly cited papers are
outgoing neighbors, which $\operatorname{\mathsf{cr}}^{d}$ ignores.

Graph |  Nodes ($\%$) |  Edges ($\%$)
---|---|---
[ late after line= |  |
, late after last line= |  |
Table 2. Compression at $d=3$.

#### Graded compression

We next evaluate the effect of moving to compression based on $c$-graded color
refinement. Figure 4(c) and (d) shows the fraction of nodes and edges
remaining in $(c,3)$-reducts of our graphs, relative to the number of nodes
and edges in the corresponding $d=3$-reduct, plotted as a function of $c$. In
terms of the number of nodes we see that, as expected, moving to graded
compression yields better compression than non-graded compression. In
particular, for $c=1$ all datasets retain $<1\%$ of their nodes while for
$c=3$, compression is $27\%$ or less for ogbn-arxiv, ogbn-arxiv-undirected,
and the road networks. In the latter setting, ogbn-products is at $75\%$ of
nodes and snap-soc-pokec at $55\%$. Compression hence becomes less effective
as $c$ increases.

In terms of the number of edges, compression is most effective when $c=1$ or
$c=2$ in which case it significantly improves over ungraded compression. From
$c\geq 3$ onwards, graded compression becomes only marginally better than
ungraded compression.

We conclude that graded compression has the potential to yield significantly
smaller graphs than ungraded compression, but only for small gradedness
values, $c=1$ (i.e., bisimulation) or $c=2$.

#### Conclusion

Overall, we see that real-world graphs have diverse non-graded compression
ratios: road networks compress extremely well (to $4\%$ of nodes and $5\%$ of
edges when $d=3$); while other graphs such as ogbn-arxiv-inv compress
reasonably in terms of number of nodes ($65\%$) but only marginally in terms
of edges ($93\%$ or more); and graphs such as ogbn-products compress only
marginally in both (retaining $90\%$ or more of nodes and edges). This
diversity is to be expected: our exact compression methodology is based on
exploiting redundancy in local neighborhoods of nodes. For graphs where few
nodes have equal local neighborhoods, we cannot expect reduction in size.
Moving to graded compression for those graphs improves reduction in size, but
will yield approximate compression unless the learning problem hypothesis
space has small width.

###  4.2. Learning

Problem | Nodes | Edges | Accurracy | Training
---|---|---|---|---
|  ($\%$) |  ($\%$) |  ($\%$) |  time ($s$) | mem (GiB)
[ late after line= |  |  |  |  |
, late after last line= |  |  |  |  |
Table 3. Comparison of learning on the original uncompressed problem
$\mathcal{P}_{1}$, the uncompressed problem with discretized labels
$\mathcal{P}_{2}$, and $(c,d=3)$-compressed variants $\mathcal{P}_{3}^{c}$.

We next turn to validating empirically the effect of learning on compressed
problems according to our methodology. Specifically, we apply our methodology
to learning on ogbn-arxiv-inv with $d=3$. We know from Section 4.1 that
compression on this graph is reasonable in terms of nodes, but only marginal
in terms of edges. Despite the modest compression, the effect on learning
efficiency in terms of learning time and memory consumption is still positive,
as we will see.

We hence focus in this section on ogbn-arxiv-inv and the associated learning
problem from the OGBN benchmark: predict, for every paper in ogbn-arxiv-inv,
its subject area (e.g., cs.AI, cs.LG, and cs.OS, …). There are $40$ possible
subject areas. In addition to the citation network, we have available for each
paper a $128$-dimensional feature vector obtained by averaging the embeddings
of words in its title and abstract. Our learning problem $\mathcal{P}_{1}$
hence consists of the ogbn-arxiv-inv graph in which each node is colored with
this feature vector. The training set $T$ consists of 90941 nodes, obtained
conform the OGBN benchmark. The hypothesis space $\mathcal{S}$ consists of
GNNs that all share the same topology and vary only in their concrete
parameters. The topology consists of $3$ GNN layers whose Agg function
computes the mean of all colors of incoming neighbors. The Comb function
applies a linear transformation to $G(v)$, applies a linear transformation to
the result of the aggregation, and finally sums these two intermediates
together. Each layer, except the final one, is followed by a batch
normalisation as well ReLU to introduce non-linearity. The layers have
dimensions $(128,256)$, $(256,256)$ and $(256,40)$, respectively. We apply a
$50\%$ dropout between layers during training. Softmax is applied after the
last layer to turn feature vectors into subject areas, and we use cross-
entropy as loss function.

Unfortunately, the initial coloring in $\mathcal{P}_{1}$ is such that every
node has a distinct color. Therefore, every node is in its own unique color
refinement class, and compression is not possible. We therefore transform
$\mathcal{P}_{1}$ into a problem $\mathcal{P}_{2}$ that can be compressed by
first converting the $128$-dimensional word embedding vectors into estimates
of paper areas by means of a multilayer perceptron (MLP) that is trained on
the nodes in $T$ _but without having the graph structure available_. This
hence yields an initial estimate of the paper area for each node. By learning
a GNN on the graph that is colored by one-hot encodings of these initial
estimates, the estimates can be refined based on the graph topology. We denote
the new problem hence obtained by $\mathcal{P}_{2}$. Note that
$\mathcal{P}_{2}$ has the same training set, hypothesis space, and loss
function as $\mathcal{P}_{1}$. The MLP has input dimension $128$, one hidden
layer of dimension 256, and output layer of dimension $40$.

We next compress $\mathcal{P}_{2}$ using $(c,d)$-reduction with $d=3$. The
resulting compressed problems are denoted $\mathcal{P}_{3}^{c}$. The
corresponding compressed graph sizes are shown in Table 3. We note that,
because we consider labeled graphs here, the compression ratio is worse than
the maximum-compression scenario of Section 4.1.

We gauge the generalisation power of the learned GNNs by computing the
accurracy on the test set, determined by the OGBN benchmark, comprising 48603
nodes. We learn for 256 epochs with learning rate $0.01$ on all problems. All
experiments are run on an HP ZBook Fury G8 with Intel Core i9 11950H CPU, 32
GB of RAM and NVIDIA RTX A3000 GPU with 6 GB RAM.

The results are summarized in Table 3. Comparing $\mathcal{P}_{1}$ with
$\mathcal{P}_{2}$ we see that estimating the paper area through an MLP has
marginal effect on the test accurracy, training time and memory consumption.
Further comparing $\mathcal{P}_{2}$ with $\mathcal{P}_{3}^{c}$, which are
equivalent by Theorem 3.3, we see that training accurracy is indeed comparable
between $\mathcal{P}_{2}$ and $\mathcal{P}_{3}^{\infty}$; we attribute the
difference in accurracy to the stochastic nature of learning. There is a
larger difference in accurracy between $\mathcal{P}_{2}$ and
$\mathcal{P}_{3}^{c}$ when $c=1$, i.e., when we compress based on
bisimulation, than when $c>1$. This is because $c$-graded compression is an
approximation, as explained in Section 3.4, and because, as we can see,
$c$-graded compression for $c>1$ is nearly identical in size to ungraded
compression. For $c>1$ we may hence expect there to be only marginal
differences w.r.t. ungraded compression. Learning the compressed problems
$\mathcal{P}_{3}^{c}$ is more efficient than learning on the uncompressed
$\mathcal{P}_{2}$, taking only $81.5$–$84.3\%$ of the learning time and
$78.7$–$81.6\%$ of the memory respectively which is comparable to the
reduction in number of nodes when compressing.

Our evaluation in this section is on a single learning problem; it should
hence be interpreted as a preliminary insight that requires further
evaluation. Based on these preliminary findings, however, we conclude that
compressed learning can yield observable improvements in training time and
memory consumption.

##  5\. Conclusion and Future Work

We have proposed a formal methodology for exact compression of GNN-based
learning problems. While the attainable exact compression ratio depends on the
input graph, our experiment in Section 4.2 nevertheless indicates that
observable improvements in learning efficiency are possible, even when the
compression in terms of the number of edges is negligible.

In terms of future work, first and foremost our preliminary empirical
evaluation should be extended to more learning tasks. Second, as we have seen
$c$-graded color refinement offers a principled way of approximating exact
compression, which becomes exact for hypothesis spaces of width $c$. It is an
interesting question whether other existing approximate compression proposals
(dengGraphZoomMultilevelSpectral2020a; liangMILEMultiLevelFramework2021) can
similarly be tied to structural properties of the hypothesis space.

###### Acknowledgements.

We thank Floris Geerts for helpful discussions. S. Vansummeren and J.
Steegmans were supported by the Bijzonder Onderzoeksfonds (BOF) of Hasselt
University under Grants No. BOF20ZAP02 and BOF21D11VDBJ. This work was further
supported by the Research Foundation Flanders (FWO) under research project
Grant No. G019222N. We acknowledge computing resources and services provided
by the VSC (Flemish Supercomputer Center), funded by the Research Foundation –
Flanders (FWO) and the Flemish Government.

## References

  * (1)
  * Baier and Katoen (2008) Christel Baier and Joost-Pieter Katoen. 2008.  _Principles of Model Checking_.  MIT Press.
  * Barceló et al. (2020) Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan-Pablo Silva. 2020.  The Expressive Power of Graph Neural Networks as a Query Language.  _ACM SIGMOD Record_ 49, 2 (Dec. 2020), 6–17.  https://doi.org/10.1145/3442322.3442324
  * Battaglia et al. (2018) Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. 2018\.  Relational Inductive Biases, Deep Learning, and Graph Networks.  https://doi.org/10.48550/arXiv.1806.01261 arXiv:arXiv:1806.01261
  * Cardon and Crochemore (1982) A. Cardon and M. Crochemore. 1982.  Partitioning a Graph in $O(—A— \log_2 —V—)$.  _Theoretical Computer Science_ 19, 1 (July 1982), 85–98.  https://doi.org/10.1016/0304-3975(82)90016-0
  * Chen et al. (2018) Jie Chen, Tengfei Ma, and Cao Xiao. 2018.  FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net.
  * Deng et al. (2020) Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. 2020.  GraphZoom: A Multi-Level Spectral Approach for Accurate and Scalable Graph Embedding.  https://doi.org/10.48550/arXiv.1910.02370 arXiv:arXiv:1910.02370
  * Geerts et al. (2022) Floris Geerts, Jasper Steegmans, and Jan Van den Bussche. 2022\.  On the Expressive Power of Message-Passing Neural Networks as Global Feature Map Transformers. In _Foundations of Information and Knowledge Systems_ _(Lecture Notes in Computer Science)_ , Ivan Varzinczak (Ed.). Springer International Publishing, Cham, 20–34.  https://doi.org/10.1007/978-3-031-11321-5_2
  * Generale et al. (2022) Alessandro Generale, Till Blume, and Michael Cochez. 2022\.  Scaling R-GCN Training with Graph Summarization. In _Companion Proceedings of the Web Conference 2022_ _(WWW ’22)_. Association for Computing Machinery, New York, NY, USA, 1073–1082.  https://doi.org/10.1145/3487553.3524719
  * Gilmer et al. (2017) Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017\.  Neural Message Passing for Quantum Chemistry. In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ _(ICML’17)_. JMLR.org, Sydney, NSW, Australia, 1263–1272.
  * Grohe (2021) Martin Grohe. 2021\.  The Logic of Graph Neural Networks. In _Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science_ _(LICS ’21)_. Association for Computing Machinery, New York, NY, USA, 1–17.  https://doi.org/10.1109/LICS52264.2021.9470677
  * Hamilton (2020) William L. Hamilton. 2020\.  _Graph Representation Learning_.  Morgan & Claypool Publishers.  https://doi.org/10.2200/S01045ED1V01Y202009AIM046
  * Hamilton et al. (2017) William L. Hamilton, Rex Ying, and Jure Leskovec. 2017\.  Inductive Representation Learning on Large Graphs. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ _(NIPS’17)_. Curran Associates Inc., Red Hook, NY, USA, 1025–1035.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020\.  Open Graph Benchmark: Datasets for Machine Learning on Graphs. In _Advances in Neural Information Processing Systems_ , Vol. 33. Curran Associates, Inc., 22118–22133.
  * Huang et al. (2018) Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018\.  Adaptive Sampling towards Fast Graph Representation Learning. In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ _(NIPS’18)_. Curran Associates Inc., Red Hook, NY, USA, 4563–4572.
  * Leskovec and Krevl ([n. d.]) Jure Leskovec and Andrej Krevl. [n. d.].  SNAP Datasets: Stanford Large Network Dataset Collection.
  * Liang et al. (2021) Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy. 2021\.  MILE: A Multi-Level Framework for Scalable Graph Embedding.  _Proceedings of the International AAAI Conference on Web and Social Media_ 15 (May 2021), 361–372.  https://doi.org/10.1609/icwsm.v15i1.18067
  * Liao et al. (2022) Ningyi Liao, Dingheng Mo, Siqiang Luo, Xiang Li, and Pengcheng Yin. 2022.  SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization.  _Proceedings of the VLDB Endowment_ 15, 11 (July 2022), 3240–3248.  https://doi.org/10.14778/3551793.3551866
  * Lin et al. (2022) Haiyang Lin, Mingyu Yan, Xiaocheng Yang, Mo Zou, Wenming Li, Xiaochun Ye, and Dongrui Fan. 2022.  Characterizing and Understanding Distributed GNN Training on GPUs.  _IEEE Computer Architecture Letters_ 21, 1 (Jan. 2022), 21–24.  https://doi.org/10.1109/LCA.2022.3168067
  * Morris et al. (2019) Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019\.  Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 33, 01 (July 2019), 4602–4609.  https://doi.org/10.1609/aaai.v33i01.33014602
  * Peng et al. (2022) Jingshu Peng, Zhao Chen, Yingxia Shao, Yanyan Shen, Lei Chen, and Jiannong Cao. 2022\.  Sancus: Staleness-Aware Communication-Avoiding Full-Graph Decentralized Training in Large-Scale Graph Neural Networks.  _Proceedings of the VLDB Endowment_ 15, 9 (May 2022), 1937–1950.  https://doi.org/10.14778/3538598.3538614
  * Salha et al. (2019) Guillaume Salha, Romain Hennequin, Viet-Anh Tran, and Michalis Vazirgiannis. 2019.  A Degeneracy Framework for Scalable Graph Autoencoders. In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019_ , Sarit Kraus (Ed.). ijcai.org, 3353–3359.  https://doi.org/10.24963/ijcai.2019/465
  * Wang et al. (2022) Qiange Wang, Yanfeng Zhang, Hao Wang, Chaoyi Chen, Xiaodong Zhang, and Ge Yu. 2022\.  NeutronStar: Distributed GNN Training with Hybrid Dependency Management. In _Proceedings of the 2022 International Conference on Management of Data_ _(SIGMOD ’22)_. Association for Computing Machinery, New York, NY, USA, 1301–1315.  https://doi.org/10.1145/3514221.3526134
  * Wu et al. (2021) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021\.  A Comprehensive Survey on Graph Neural Networks.  _IEEE Transactions on Neural Networks and Learning Systems_ 32, 1 (Jan. 2021), 4–24.  https://doi.org/10.1109/TNNLS.2020.2978386
  * Xu et al. (2019) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019\.  How Powerful Are Graph Neural Networks?. In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018.  Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ _(KDD ’18)_. Association for Computing Machinery, New York, NY, USA, 974–983.  https://doi.org/10.1145/3219819.3219890
  * Yuan et al. (2022) Binhang Yuan, Cameron R. Wolfe, Chen Dun, Yuxin Tang, Anastasios Kyrillidis, and Chris Jermaine. 2022.  Distributed Learning of Fully Connected Neural Networks Using Independent Subnet Training.  _Proceedings of the VLDB Endowment_ 15, 8 (April 2022), 1581–1590.  https://doi.org/10.14778/3529337.3529343
  * Zheng et al. (2022) Chenguang Zheng, Hongzhi Chen, Yuxuan Cheng, Zhezheng Song, Yifan Wu, Changji Li, James Cheng, Hao Yang, and Shuai Zhang. 2022.  ByteGNN: Efficient Graph Neural Network Training at Large Scale.  _Proceedings of the VLDB Endowment_ 15, 6 (Feb. 2022), 1228–1242.  https://doi.org/10.14778/3514061.3514069
  * Zhu et al. (2022) Zulun Zhu, Jiaying Peng, Jintang Li, Liang Chen, Qi Yu, and Siqiang Luo. 2022\.  Spiking Graph Convolutional Networks. In _Thirty-First International Joint Conference on Artificial Intelligence_ , Vol. 3. 2434–2440.  https://doi.org/10.24963/ijcai.2022/338