Learning Graph Neural Networks using Exact Compression
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.
Jeroen Bollen, Jasper Steegmans, Jan Van den Bussche, Stijn Vansummeren
# Learning Graph Neural Networks using Exact Compression

###### 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 (Beng et al., 2015; Chen et al., 2016; Chen et al., 2017; Chen et al., 2018; Chen et al., 2019). 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 (Sutton et al., 2018; Chen et al., 2019). 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., (Beng et al., 2015; Chen et al., 2016; Chen et al., 2017; Chen et al., 2018; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019)). Broadly speaking, we can identify three different principles for obtaining scalability in the literature (1) distributing computation across multiple machines or GPUs (Beng et al., 2015; Chen et al., 2016; Chen et al., 2017; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019); (2) learning on a sample of the input graph instead of the entire graph (Beng et al., 2015; Chen et al., 2017; Chen et al., 2019); and (3) compression (Chen et al., 2016; Chen et al., 2017; Chen et al., 2019; Chen et al., 2019). 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. (Deng et al., 2016) use spectral analysis for this purpose; Liang et al. (Liang et al., 2017) use variants of multi-level graph partitioning; and Generale et al. (Gorenale et al., 2018), 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_(Beng et al., 2015; Chen et al., 2017; Chen et al., 2018). This class includes all Graph Convolutional Networks (Chen et al., 2017). Our methodology is based on recent insights into the expressiveness of aggregate-combine GNNs (Chen et al., 2017; Chen et al., 2019). 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 \(\{\ldots\}\) 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 \(\mathit{supp}(M)\) the set of all elements present in \(M\), \(\mathit{supp}(M)\coloneqq\{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 \(\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 \(\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 \(|\mathit{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\(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 \(C\) a _coloring transformer_. In particular, if \(X=\mathbb{R}^{p}\) and \(Y=\mathbb{R}^{q}\) for some dimensions \(p\) and \(q\) then \(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 (1997). In this paper we focus on a standard form of GNNs that is known under the name of _aggregate-combine_ GNNs (Beng et al., 2015), also called _message-passing GNNs_. These are defined as follows (Garno et al., 2016; Garno et al., 2016).

A _GNN layer_ of input dimension \(p\) and output dimension \(q\) is a pair \(\textsc{(Agg,Comb)}\) of functions where (1) \(\textsc{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) \(\textsc{Comb}\) is a _combination function_\(\textsc{Comb}\colon\mathbb{R}^{p}\times\mathbb{R}^{h}\to\mathbb{R}^{q}\). In practice, \(\textsc{Agg}\) is usually taken to compute the arithmetic mean, sum, or maximum of the vectors in the multiset, while \(\textsc{Comb}\) is computed by means of a feedforward neural network whose parameters can be learned.

A _GNN_ is a sequence \(\overline{L}=(L_{1},\ldots,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 (Garno et al., 2016) In particular, when GNN layer \(L=\textsc{(Agg,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\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\cdots\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 (Hamilton et al., 2016).

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,\mathrm{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;
* Loss : \(T\times\mathbb{R}^{q}\rightarrow\mathbb{R}\) is a loss function that allows to quantify, for each node \(v\in T\) the dissimilarity \(\operatorname{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{Loss}(\overline{L}(G),T)\coloneqq\sum_{v\in T}\operatorname{ 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{Loss},\mathcal{S})\), is it possible to transform this into a new problem \(\mathcal{P}^{\prime}=(G^{\prime},T^{\prime},\operatorname{Loss}^{\prime}, \mathcal{S})\) that is obtained by_ compressing \(G\), \(T\), _and Loss into a smaller graph \(G^{\prime}\), training set \(T^{\prime}\), and loss function \(\operatorname{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{Loss}(\overline{L}(G),T)=\operatorname{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{Loss}\) into a modified loss function \(\operatorname{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 (Bahdan et al., 2016; Goyal et al., 2017; Goyal et al., 2017). 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.

### 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)\prec_{\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. (Morris et al., 2019) and Xu et al. (Xu et al., 2020). 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 (Lewis, 1996), and works as follows.

Definition 3.2 ().: The (one-step) _color-refinement_ of colored graph \(G=(V,E,g)\), denoted \(\operatorname{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}:v\mapsto\big{(}G(v),\{G(w)\mid w\in\operatorname{in}_{G}(v)\} \big{)}.\]

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

We denote by \(\operatorname{cr}^{d}(G)\) the result of applying \(d\) color refinement steps on \(G\), so \(\operatorname{cr}^{0}(G)=G\) and \(\operatorname{cr}^{d+1}(G)=\operatorname{cr}(\operatorname{cr}^{d}(G))\). Using this notation, we can think of \(\operatorname{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.

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

Proposition 3.3 ().: _Let \(\overline{L}\) be a GNN composed of \(d\in\mathbb{N}\) layers, \(d\geq 1\). If \(\operatorname{cr}^{d}(G)(v)=\operatorname{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{cr}^{d}(G)(v)=\operatorname{cr}^{d}(H)(w)\) then \((G,v)\sim_{\mathcal{S}}(H,w)\)._

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}\coloneqq\{w\in G\mid\operatorname{cr}^{d}(G)(v)=\operatorname{cr}^ {d}(G)(w)\}.\]

Then it follows from Proposition 3.3 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. (Morris et al., 2019) and Xu et al. (Xu et al., 2020) 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 size-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{cr}^{\infty}(G)\) in what follows. Similarly we denote the equivalence classes at this value of \(d\) by \([G,v]_{\infty}\). From Proposition 3.3 it readily follows:

Corollary 3.4 ().: _For any class\(\mathcal{S}\) of GNNs, if \(\operatorname{cr}^{\infty}(G)(v)=\operatorname{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 (Brandt, 2007).

Example 3.5 ().: 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

\[[G,a_{1}]_{1} =\{a_{1}\}\] \[[G,a_{2}]_{1} =[G,a_{3}]_{1}=\{a_{2},a_{3}\}\] \[[G,b_{1}]_{1} =[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:

\[[G,a_{1}]_{2} =\{a_{1}\}\] \[[G,b_{1}]_{2} =[G,b_{2}]_{2}=\{b_{1},b_{2}\}\] \[[G,a_{2}]_{2} =[G,a_{3}]_{2} =\{a_{2},a_{3}\} [G,b_{3}]_{2} =\{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}\).

### 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\}\)

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\).
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(\rho)=\rho([G,v]_{d})\).

Definition 3.6 ().: 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.7 ().: Reconsider the colored graph \(G\) of Figure 1. Let \(\rho_{1}\) and \(\rho_{2}\) be the following \(d=1\)-substitutions:

\[\rho_{1} :\{a_{1}\}\mapsto a_{1} \{a_{2},a_{3}\}\mapsto a_{2} \{b_{1},b_{2},b_{3}\}\mapsto b_{1}\] \[\rho_{2} :\{a_{1}\}\mapsto a_{1} \{a_{2},a_{3}\}\mapsto a_{2} \{b_{1},b_{2},b_{3}\}\mapsto b_{3}\]

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

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

Proposition 3.8 ().: _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{cr}^{d}(G)(v)=\operatorname{cr}^{d}(G/\rho)(\rho(v))\)._

It hence follows from Proposition 3.3 and Corollary 3.4 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))\).

DiscussionExample 3.7 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:

Proposition 3.9 ().: _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\)._

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.7, \(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{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{in}\operatorname{in}\operatorname{in} \operatorname{in}\operatorname{in}\operatorname{out}\}\). 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.

Proposition 3.10 ().: _Let \(G\) be a graph, let \(d\in\mathbb{N}_{\infty}\) and let \(\rho\) be a \(d\)-substitution such that_

\[\operatorname{incidence}^{d}_{G}(\rho(v))=\min_{v^{\prime}\in[G,v]_{d}} \operatorname{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\)._

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

DiscussionExample 3.7 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{cr}^{d}(G)(v)=\operatorname{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.

### 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{Loss},\mathcal{S})\) be a learning problem. Let \(\rho\) be a \(d\)-substitution. We then define the reductions \(T/\rho\) and \(\operatorname{Loss}/\rho\) of \(T\) and Loss by \(\rho\) as follows:

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

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

Figure 3. Reduction of a tree-shaped simple graph (left) into a small multigraph (right).

Figure 2. Reduction of the graph of Figure 1 by the \(1\)-substitutions \(\rho_{1}\) and \(\rho_{2}\) from Example 3.7.
**Theorem 3.11**.: _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\)._

### 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 \(\text{Agg}(M)=\text{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 (Garfani et al., 2016) 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.12**.: Let \(c\in\mathbb{N}_{\infty}\). The (one-step) \(c\)-_graded color refinement_ of colored graph \(G=(V,E,g)\), denoted \(\text{c}\text{c}_{c}(G)\), is the colored graph \(G^{\prime}=(V,E,g^{\prime})\) with

\[g^{\prime}:v\mapsto\big{(}G(v),\{G(w)\mid w\in\text{in}_{G}(v)\}\|_{\leq c} \big{)}.\]

Note that \(\text{c}\text{c}_{\infty}\) equals normal, non-graded, color refinement. We also remark that \(\text{c}\text{c}_{r}\) with \(c=1\) corresponds to standard _bisimulation_ on graphs (Bill et al., 2016). We denote by \(\text{c}\text{c}\text{c}_{c}^{d}(G)\) the result of applying \(d\) refinement steps of \(c\)-graded color refinement, so \(\text{c}\text{c}\text{c}_{c}^{d}(G)=G\) and \(\text{c}\text{c}\text{c}_{c}^{d+1}=\text{c}\text{c}(\text{c}\text{c}_{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 the 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.

### 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 (Garfani et al., 2016), where they belong to the OGB node property prediction benchmark (OGBN). Specifically, ogbn-arvis is a network of academic papers, where edge \(x\to y\) indicates that \(x\) cites \(y\). Graph ogbn-arvis-inv is the inverted version of ogbn-arvis; it is obtained by reversing edges, so that edge \(x\gets y\) indicates that \(y\) was cited by \(x\). Graph ogbn-arvis-undirected is the undirected version of ogbn-arvis; it is obtained by adding inverse edges to ogbn-arvis. 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) (Kipfani et al., 2016). 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.

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

\begin{table}
\begin{tabular}{l l c c} \hline \hline Graph & Type & \#Nodes & \#Edges \\ \hline ogbn-arviv & directed & 169.343 & 1.166.243 \\ ogbn-arvis-inv & directed & 169.343 & 1.166.243 \\ ogbn-arvis-undirected & undirected & 169.343 & 2.315.598 \\ ogbn-products & undirected & 2.449.029 & 61.859.140 \\ snap-roadnet-ca & undirected & 1.965.206 & 5.533.214 \\ snap-roadnet-pa & undirected & 1.088.092 & 3.083.796 \\ snap-roadnet-tx & undirected & 1.379.917 & 3.843.320 \\ snap-soc-pokec & directed & 1.632.803 & 30.622.564 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Datasets
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.

#### 4.2.2. 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-pokce as these retain \(88\%\) of their nodes or more. Compression on the other datasets is satisfactory 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-pokce 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 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 cr\({}^{d}\) ignores.

#### 4.2.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-pokce 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\).

#### 4.2.4. 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.

### Learning

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.

\begin{table}
\begin{tabular}{l r r} \hline \hline Graph & Nodes (\%) & Edges (\%) \\ \hline ogbn-arxiv & 32.9 & 56.3 \\ ogbn-arxiv-inv & 65.9 & 92.7 \\ ogbn-arxiv-undirected & 93.3 & 98.9 \\ ogbn-products & 88.5 & 98.6 \\ snap-roadnet-ca & 4.4 & 5.9 \\ snap-roadnet-pa & 6.1 & 7.9 \\ snap-roadnet-tx & 3.9 & 5.2 \\ snap-soc-pokce & 87.9 & 99.1 \\ \hline \hline \end{tabular}
\end{table}
Table 2. Compression at \(d=3\).

\begin{table}
\begin{tabular}{l r r r r r} \hline \hline Problem & Nodes & Edges & Accuracy & \multicolumn{2}{c}{Training} \\  & (\%) & (\%) & (\%) & time (s) & mem (GiB) \\ \hline \(\mathcal{P}_{1}\) & 100.0 & 100.0 & 66.7 & 61.66 & 2.14 \\ \(\mathcal{P}_{2}\) & 100.0 & 100.0 & 65.9 & 58.99 & 2.02 \\ \(\mathcal{P}_{3}^{1}\) & 76.9 & 95.9 & 60.9 & 48.10 & 1.59 \\ \(\mathcal{P}_{3}^{3}\) & 79.2 & 97.1 & 64.5 & 49.71 & 1.65 \\ \(\mathcal{P}_{3}^{1}\) & 79.3 & 97.2 & 64.9 & 49.55 & 1.65 \\ \(\mathcal{P}_{3}^{0c}\) & 79.4 & 97.2 & 63.8 & 49.16 & 1.65 \\ \hline \hline \end{tabular}
\end{table}
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}\).
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 fcn 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 fcn by computing the accuracy 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 Furry 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 accuracy, training time and memory consumption. Further comparing \(\mathcal{P}_{2}\) with \(\mathcal{P}_{3}^{c}\), which are equivalent by Theorem 3.11, we see that training accuracy is indeed comparable between \(\mathcal{P}_{2}\) and \(\mathcal{P}_{3}^{\infty}\); we attribute the difference in accuracy to the stochastic nature of learning. There is a larger difference in accuracy 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.

Figure 4. Normalized reduction in nodes and edges using \(d\)-reduction (a and b) and \((c,3)\)-reduction (c and d).
## 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 (Garon et al., 2016; Goyal et al., 2017) can similarly be tied to structural properties of the hypothesis space.

## Acknowledgments

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.
