On the Two Sides of Redundancy in Graph Neural Networks
Message passing neural networks iteratively generate node embeddings by
aggregating information from neighboring nodes. With increasing depth,
information from more distant nodes is included. However, node embeddings may
be unable to represent the growing node neighborhoods accurately and the
influence of distant nodes may vanish, a problem referred to as oversquashing.
Information redundancy in message passing, i.e., the repetitive exchange and
encoding of identical information amplifies oversquashing. We develop a novel
aggregation scheme based on neighborhood trees, which allows for controlling
redundancy by pruning redundant branches of unfolding trees underlying standard
message passing. While the regular structure of unfolding trees allows the
reuse of intermediate results in a straightforward way, the use of neighborhood
trees poses computational challenges. We propose compact representations of
neighborhood trees and merge them, exploiting computational redundancy by
identifying isomorphic subtrees. From this, node and graph embeddings are
computed via a neural architecture inspired by tree canonization techniques.
Our method is less susceptible to oversquashing than traditional message
passing neural networks and can improve the accuracy on widely used benchmark
datasets.
Franka Bause, Samir Moustafa, Johannes Langguth, Wilfried N. Gansterer, Nils M. Kriege
# Non-Redundant Graph Neural Networks

###### Abstract

Message passing graph neural networks iteratively compute node embeddings by aggregating messages from all neighbors. This procedure can be viewed as a neural variant of the Weisfeiler-Leman method, which limits their expressive power. Moreover, oversmoothing and oversquashing restrict the number of layers these networks can effectively utilize. The repeated exchange and encoding of identical information in message passing amplifies oversquashing. We propose a novel aggregation scheme based on neighborhood trees, which allows for controlling the redundancy by pruning branches of the unfolding trees underlying standard message passing. We prove that reducing redundancy improves expressivity and experimentally show that it alleviates oversquashing. We investigate the interaction between redundancy in message passing and redundancy in computation and propose a compact representation of neighborhood trees, from which we compute node and graph embeddings via a neural tree canonization technique. Our method is provably more expressive than the Weisfeiler-Leman method, less susceptible to oversquashing than message passing neural networks, and provides high classification accuracy on widely-used benchmark datasets.

## 1 Introduction

Graph neural networks have recently emerged as the dominant technique for machine learning with graphs. The class of message passing neural networks (MPNNs) [9] is widely-used. It updates node embeddings layer-wise by combining the current embedding of a node with the embeddings of its neighbors involving learnable parameters. Suitable neural architectures admit a parametrization such that each layer represents an injective function encoding its input uniquely by the new embedding. In this case the MPNN has the same expressive power as the Weisfeiler-Leman algorithm [28]. The Weisfeiler-Leman algorithm can distinguish two nodes if and only if the unfolding trees representing their neighborhoods are non-isomorphic. This
unfolding tree corresponds to the computational tree of MPNNs [23, 10]. Hence, if two nodes have isomorphic unfolding trees of height \(n\), they will obtain the same embedding after \(n\) layers. Vice versa, for two nodes with non-isomorphic unfolding trees of height \(n\), there are parameters of the network such that the node's embeddings after \(n\) layers differ. However, in practice shallow MPNNs are widely employed. Two phenomena have been identified explaining the poor performance of deep graph neural networks. First, node representations are observed to converge to the same values for deep architecture instead of being able to distinguish more vertices, a phenomenon referred to as _oversmoothing_[14, 15]. Second, _oversquashing_[5] refers to the problem that the neighborhood of a node grows exponentially with the number of layers and aggregation steps and, therefore, cannot be supposed to be accurately represented by a fixed-sized embedding.

We argue that oversquashing can be alleviated by removing the encoding of repeated information. Consider a node \(u\) with an edge \(e=\{u,v\}\) in an undirected graph. In a first step, \(u\) will send information to \(v\) over the edge \(e\). In the next step, \(u\) will receive a message form \(v\) via \(e\) that incorporates the information that \(u\) has previously sent to \(v\). Clearly, this information is redundant. In the context of walk-based graph learning this problem is well-known and referred to as _tottering_[16]. Recently, Chen et al. [7] made the relation between redundancy and oversquashing explicit and investigated it using the Jacobian of node representations [26]. Several graph neural networks have been proposed replacing the walk-based aggregation with repeated vertices by mechanisms based on simple or shortest paths [21, 19, 11]. Closely related to our work are PathNNs [19] and RFGNN [11], which both define path-based trees for nodes and use custom aggregation schemes. Both approaches suffer from high computational costs and do not exploit the computational redundancy, which is a major advantage of standard MPNNs.

Our contribution.We systematically investigate the information redundancy in MPNNs and develop principled techniques to avoid superfluous messages. Fundamental to our consideration is the tree representation implicitly used by MPNNs and the Weisfeiler-Leman method. First, we develop a neural tree canonization approach processing trees systematically in a bottom-up fashion and extend it to operate on directed acyclic graphs (DAGs) representing the union of multiple trees. Our approach recovers the computational graph of MPNNs for unfolding trees, but allows to avoid redundant computations in case of symmetries. Second, we apply the canonization technique to _neighborhood trees_, which are obtained from unfolding trees by deleting nodes that appear multiple times. We show that neighborhood trees allow distinguishing nodes and graphs that cannot be distinguished by the Weisfeiler-Leman method, rendering our technique more expressive than MPNNs. Our approach removes information redundancy on node level, but the non-regular structure of subtrees leads to computational challenges. Our DAG representation of neighborhood trees has size at most \(O(nm)\) for input graphs with \(n\) nodes and \(m\) edges and allows to reuse embeddings of isomorphic subtrees to increase efficiency. Our method achieves high accuracy on several graph classification tasks.
## 2 Related Work

The graph isomorphism network (GIN) [28] is an MPNN that generalizes the Weisfeiler-Leman algorithm and reaches its expressive power. The embedding of a vertex \(v\) in layer \(i\) of GIN is defined as

\[x_{i}(v)=\mathrm{MLP}_{i}\left((1+\epsilon_{i})\cdot x_{i-1}(v)+\sum_{u\in N(v) }x_{i-1}(u)\right), \tag{1}\]

where the initial features \(x_{0}(v)\) are usually acquired by applying a multi-layer perceptron (MLP) to the vertex features. The limited expressiveness of simple message passing neural networks has lead to an increased interest in researching the expressiveness of GNNs and finding more powerful architectures, for example, by encoding graph structure as additional features or altering the message passing procedure. Shortest Path Networks [2] use multiple aggregation functions for different shortest path lengths: One for each \(k\) for the \(k\)-hop neighbors. While this allows the target node to directly communicate with nodes further away and in turn possibly might help mitigate oversquashing, some information about the structure of the neighborhood can still not be represented adequately and the gain in expressiveness is limited. In Distance Encoding GNNs [13], the distances of the nodes to a set of target nodes are encoded. While this approach also is provably more expressive than the standard WL method, it is limited to solving node-level tasks, since the encoding depends on a fixed set of target nodes, and has not been employed for graph-level tasks. MixHop [3] employs an activation function for each neighborhood and concatenates their results. However, in contrast to [2], the aggregation is based on normalized powers of the adjacency matrix, not shortest paths, which does not solve the problem of redundant messages. SPAGAN [29] proposes a path-based attention mechanism. Although the idea is very similar, shortest paths are only sampled and the feature aggregation differs. Only one layer is used and the paths are used as features. This approach has not been investigated theoretically. Also [25] uses a method with short-rooted random walks to capture long-range dependencies between nodes. It has notable limitations due to sample paths instead of exploring all of them, and the evaluation is solely on node classification datasets and needs an extensive study of their expressive power. IDGNN [30] keeps track of the identity of the root node in the unfolding tree, which allows for more expressiveness than 1-WL. Their variant ID-GNN-Fast works by using cycles lengths as additional node features. Both variants however, do not reduce the amount of redundant information that is aggregated over multiple layers. PathNNs [19] defines path-based trees and a custom aggregation scheme, but the computational redundancy is not exploited. In RFGNNs [7] the idea of reducing redundancy is similar. The computational flow is altered to only include each node (except for the root node) at most once in each path of the computational tree. While this reduces redundancy to some extent, nodes and even the same subpaths may repeatedly occur in the computational trees. The redundancy in computation is not addressed resulting in a highly inefficient preprocessing and computation, which restricts the method to a maximum of 3 layers in the experiments. See Appendix A for a detailed discussion of the differences between our approach and RFGNN.

For many of these architectures no thorough investigation on their expressiveness and connec
types of redundancy in message passing neural networks, i.e. they do not address redundancy in the information flow and in computation.

## 3 Preliminaries

In this section, we give an overview of the necessary definitions and the notation used throughout the article and introduce fundamental techniques.

Graph theory.A _graph_\(G=(V,E,\mu,v)\) consists of a set of vertices \(V\), a set of edges \(E\subseteq V\times V\) between them and functions \(\mu\colon V\to X\) and \(v\colon E\to X\) assigning arbitrary attributes to the vertices and edges, respectively.1 We refer to an edge from \(u\) to \(v\) by \(uv\), and in case of undirected graphs \(uv=\omega u\). The vertices and edges of a graph \(G\) are denoted by \(V(G)\) and \(E(G)\), respectively, and the _neighbors_ (or in-neighbors) of a vertex \(u\in V\) are denoted by \(N(u)=\{v\mid\omega u\in E\}\). The _out-neighbors_ of a vertex \(u\in V\) are denoted by \(N_{o}(u)=\{v\mid uv\in E\}\). A _multigraph_ is a graph, where \(E\) is a multiset, which means there can be multiple edges between a pair of vertices. Two graphs \(G\) and \(H\) are isomorphic, denoted by \(G\simeq H\), if there exists a bijection \(\phi\colon V(G)\to V(H)\), so that \(\forall u,v\in V(G)\colon\mu(v)=\mu(\phi(v))\wedge w\in E(G)\Leftrightarrow \phi(u)\phi(v)\in E(H)\wedge\forall uv\in E(G)\colon v(uv)=v(\phi(u)\phi(v))\). We call \(\phi\) an _isomorphism_ between \(G\) and \(H\).

Footnote 1: We do not consider edge attributes in the following for clarity of presentation. However, the methods we propose can be extended to incorporate them.

An _in-tree_\(T\) is a connected, directed, acyclic graph with a distinct vertex \(r\in V(T)\) with no outgoing edges referred to as _root_, denoted by \(r(T)\), in which \(\forall v\in V(T)\backslash r(T):|N_{o}(v)|=1\). For \(v\in V(T)\backslash r(T)\) the _parent_\(p(v)\) is defined as the unique vertex \(u\in N_{o}(v)\), and \(\forall v\in V(T)\) the _children_ are defined as \(\operatorname{chi}(v)=N(v)\). We refer to all vertices with no incoming edges as _leaves_ denoted by \(l(T)=\{v\in V(T)\mid\operatorname{chi}(v)=\emptyset\}\). Conceptually it is a directed tree, in which there is a unique directed path from each vertex to the root [18]. In our paper, we only cover in-trees and will thereby just refer to them as _trees_. In-trees are generalized by directed, acyclic graphs (DAGs). The _leaves_ of a DAG \(D\) and the _children_ of a vertex are defined as in trees. However, there can be multiple roots and a vertex may have more than one parent. We refer to all vertices in \(D\) with no outgoing edges as _roots_ denoted by \(r(D)=\{v\in V(D)\mid N_{o}(v)=\emptyset\}\) and define the _parents_\(p(v)\) of a vertex \(v\) as \(p(v)=N_{o}(v)\). The height hgt of a node \(v\) is the length of the longest path from any leaf to \(v\): \(\operatorname{hgt}(v)=0\), if \(v\in l(D)\) and \(\operatorname{hgt}(v)=\max_{c\in\operatorname{chi}(v)}\operatorname{hgt}(c)+1\) otherwise.
The height of a DAG \(D\) is defined as \(\operatorname{hgt}(D)=\max_{v\in V(D)}\operatorname{hgt}(v)\). For clarity we refer to the vertices of a DAG as nodes to distinguish them from the graphs that are the input of a graph neural network.

Weisfeiler-Leman unfolding trees.The \(1\)-dimensional Weisfeiler-Leman (WL) algorithm or _color refinement_ starts with all vertices having a color representing their label (or a uniform coloring in case of unlabeled vertices). In each iteration the color of a vertex is updated based on the multiset of colors of its neighbors according to

\[c_{\text{wl}}^{(i+1)}(v)=h\left(c_{\text{wl}}^{(i)}(v),\{\mathbf{c}_{\text{wl }}^{(i)}(u)\mid u\in N(v)\}\right)\quad\forall v\in V(G),\]

where \(h\) is an injective function typically representing colors by integers.

The color of a vertex of \(G\) encodes its neighborhood by a tree \(T\) that may contain multiple representatives of each vertex in \(G\). Let \(\phi\colon V(T)\to V(G)\) be a mapping such that \(\phi(n)=v\) if the node \(n\) in \(V(T)\) represents the vertex \(v\) in \(V(G)\). The _unfolding tree_\(F_{i}^{v}\) with height \(i\) of the vertex \(v\in V(G)\) consists of a root \(n_{v}\) with \(\phi(n_{v})=v\) and child subtrees \(F_{i-1}^{u}\) for all \(u\in N(v)\), where \(F_{0}^{v}=(\{n_{v}\},\emptyset)\). The attributes of the original graph are preserved, see Figure 1 for an example. The unfolding trees \(F_{i}^{v}\) and \(F_{i}^{w}\) of two vertices \(v\) and \(w\) are isomorphic if and only if \(c_{\text{wl}}^{(i)}(v)=c_{\text{wl}}^{(i)}(w)\).

## 4 Non-Redundant Graph Neural Networks

We propose to restrict the information flow in message passing to control redundancy using \(k\)-redundant neighborhood trees. We first develop a neural tree canonization technique and obtain an MPNN via its application to unfolding trees. Then we investigate computational methods on graph level, reusing information computed for subtrees and derive a customized GNN architecture. Finally, we prove that \(1\)-redundant neighborhood trees are strictly more expressive than unfolding trees on both node- and graph-level.

Figure 2: Graph \(G\) and the unfolding, \(0\)- and \(1\)-redundant neighborhood trees of height \(2\) of vertex \(v\) (vertex in the upper left of \(G\)).
### Removing Information Redundancy

It is well-known that two nodes obtain the same WL color if and only if their unfolding trees are isomorphic and this concept directly carries over to message passing neural networks and their computational tree [23, 10]. However, unfolding trees were mainly used as a tool in expressivity analysis and as a concept explaining mathematical properties in graph learning [12, 22]. We discuss a tree canonization perspective on MPNNs and derive a novel non-redundant GNN architecture based on neighborhood trees.

Aho, Hopcroft, and Ullman [4, Section 3.2] describe a linear time isomorphism test for rooted unordered trees in their classical text book, see Appendix B for details. We give a high-level description to lay the foundations for our neural variant without focusing on the running time. The algorithm proceeds in a bottom-up fashion and assigns integers \(\mathrm{c}_{\mathrm{ahu}}(v)\) to each node \(v\) of the tree. Let \(f\) be a function that assigns a pair consisting of an integer and a multiset of integers injectively to a new (unused) integer. Initially, all leaves \(v\) are assigned integers \(\mathrm{c}_{\mathrm{ahu}}(v)=f(\mu(v),\emptyset)\) according to their label \(\mu(v)\). Then, the internal nodes are processed level-wise in a bottom-up fashion guaranteeing that whenever a node is processed all its children have been considered. Hence, the algorithm computes for all nodes \(v\) of the tree

\[\mathrm{c}_{\mathrm{ahu}}(v)=f(\mu(v),\{\!\{c_{\mathrm{ahu}}(u)\mid u\in \mathrm{chi}(v)\}\!\}). \tag{2}\]

GNNs via unfolding tree canonization.We combine Eq. (2) with the definition of unfolding trees and denote the root of an unfolding tree of height \(i\) of a vertex \(v\) by \(n_{v}^{i}\). Then, we obtain

\[\mathrm{c}_{\mathrm{ahu}}(n_{v}^{i})=f(\mu(n_{v}^{i}),\{\!\{c_{\mathrm{ahu}}( n_{u}^{i-1})\mid n_{u}^{i-1}\in\mathrm{chi}(n_{v}^{i})\}\!\})=f(\mu(v),\{\!\{c_{ \mathrm{ahu}}(n_{u}^{i-1})\mid u\in N(v)\}\!\}). \tag{3}\]

Realizing \(f\) using a suitable neural architecture and replacing its codomain by embeddings in \(\mathbb{R}^{d}\) we immediately obtain a GNN from our canonization approach. The only notable difference to standard GNNs is that the first component of the pair in Eq. (3) is the initial node feature instead of the embedding of the previous iteration. We use the technique proposed by Xu et al. [28] replacing the first addend in Eq. (1) with the initial embedding to obtain the _unfolding tree canonization GNN_

\[x_{i}(v)=\mathrm{MLP}_{i}\left((1+\epsilon_{i})\cdot x_{0}(v)+\sum_{u\in N(v)} x_{i-1}(u)\right). \tag{4}\]

It is known that MPNNs cannot distinguish two nodes with the same WL color or unfolding tree. Since the function \(\mathrm{c}_{\mathrm{ahu}}(n_{v}^{i})\) uniquely represents the unfolding tree for an injective function \(f\) which can be realized by Eq. (4) [28], we conclude the following.

**Proposition 1**.: Unfolding tree canonization GNNs given by Eq. (4) are as expressive as GIN (Eq. (1)).
However, since \(x_{i-1}(v)\) represents the whole unfolding tree rooted at \(v\) of height \(i-1\), while using the initial node features \(x_{0}(v)\) is sufficient, the canonization-based approach avoids redundancy. We proceed by investigating redundancy in unfolding trees themselves.

GNNs via neighborhood tree canonization.We use the concept of neighborhood trees allowing to control the redundancy in unfolding trees.2 A \(k\)-redundant neighborhood tree (\(k\)-NT) \(T^{v}_{i,k}\) can be constructed from the unfolding tree \(F^{v}_{i}\) by deleting all subtrees with its roots, that already occurred more than \(k\) levels before (seen from root to leaves). Let \(\operatorname{depth}(v)\) denote the length of the path from \(v\) to the root and \(\phi(v)\) again denote the original vertex in \(V(G)\) represented by \(v\) in the unfolding or neighborhood tree.

Footnote 2: In a parallel work, neighborhood trees were investigated to approximate the graph edit distance [6].

**Definition 2** (\(k\)-redundant Neighborhood Tree).: For \(k\geq 0\), the \(k\)_-redundant neighborhood tree_ (\(k\)-NT) of a vertex \(v\in V(G)\) with height \(i\), denoted by \(T^{v}_{i,k}\), is defined as the subtree of the unfolding tree \(F^{v}_{i}\) induced by the nodes \(u\in V(F^{v}_{i})\) satisfying

\[\forall w\in V(F^{v}_{i})\colon\phi(u)=\phi(w)\Rightarrow\operatorname{depth }(u)\leq\operatorname{depth}(w)+k.\]

Figures 2 and 3 show a examples of unfolding and neighborhood trees. Note that for \(k\geq i\) the \(k\)-redundant neighborhood tree is equivalent to the WL unfolding tree.

We can directly apply the neural tree canonization technique to neighborhood trees. However, a simplifying expression based on the neighbors in the input graph as given by Eq. (3) for unfolding trees is not possible for neighborhood trees. Therefore, we investigate techniques to systematically exploit computational redundancy.

### Removing Computational Redundancy

The computation DAG of an MPNN involves the embedding of a set of trees representing the node neighborhoods of a single or multiple graphs. Results computed for one tree can be reused for others by identifying isomorphic substructures causing computational redundancy. We first describe, how to merge trees in general and then discuss the application to unfolding and neighborhood trees.
Merging trees into a DAG.The neural tree canonization approach developed in the last section can directly be applied to DAGs. Given a DAG \(D\), it computes an embedding for each node \(n\) in \(D\) that represents the tree \(F_{n}\) obtained by recursively following its children similar as in unfolding trees, cf. Section 3. Since \(D\) is acyclic the height of \(F_{n}\) is bounded. A detailed description of a neural architecture is postponed to Section 4.3.

Given a set of trees \(\mathcal{T}=\{T_{1},\ldots,T_{n}\}\), a _merge DAG_ of \(\mathcal{T}\) is a pair \((D,\xi)\), where \(D\) is a DAG, \(\xi\colon\{1,\ldots n\}\to V(D)\) is a mapping and for all \(i\in\{1,\ldots,n\}\) we have \(T_{i}\simeq F_{\xi(i)}\). The definition guarantees that the neural tree canonization approach applied to the merge DAG produces the same result for the nodes in the DAG as for the nodes in the original trees. A trivial merge DAG is the disjoint union of the trees with \(\xi(i)=r(T_{i})\). However, depending on the structure of the given trees, we can identify the subtrees they have in common and represent them only once, such that two nodes of different trees share the same child, resulting in a DAG instead of a forest.

We propose an algorithm that builds a merge DAG by successively adding trees to an initially empty DAG creating new nodes only when necessary. Our approach maintains a canonical labeling for each node of the DAG and computes a canonical labeling for each node of the tree to be added using the AHU algorithm, cf. Appendix B. Then, the tree is processed starting at the root. If the canonical labeling of the root is present in the DAG, then algorithm terminates. Otherwise the subtrees rooted at its children are inserted into the DAG by recursive calls. Finally, the root is created and connected to the representatives of its children in the DAG. We introduce a node labeling \(L\colon V_{T}\to\mathcal{O}\) used for tree canonization, where \(V_{T}=\bigcup_{i=1}^{n}V(T_{i})\) and \(\mathcal{O}\) an arbitrary set of labels, refining the original node attributes, i.e., \(L(u)=L(v)\Rightarrow\mu(u)=\mu(v)\) for all \(u,v\) in \(V_{T}\). When \(\mathcal{O}\) are integers from the range \(1\) to \(|V_{T}|\), the algorithm runs in \(O(|V_{T}|)\) time, see Appendix D for details. When two siblings that are the roots of isomorphic subtrees are merged, this leads to parallel edges in the DAG. Parallel edges can be avoided by using a labeling satisfying \(L(u)=L(v)\Rightarrow\mu(u)=\mu(v)\wedge p(u)\neq p(v)\) for all \(u,v\) in \(V_{T}\).

Unfolding trees and \(k\)-NTs can grow exponentially in size with increasing height. However, this is not case for the merge DAGs obtained by the algorithm described above as we will show below. Moreover, we can directly generate DAGs of size \(O(m\cdot(k+1))\) representing individual \(k\)-NTs with unbounded height in a graph with \(m\) edges, see Appendix C for details.

Figure 4: Computation DAGs for unfolding (a) and 0-NTs (b) of height \(2\) of graph \(G\). And edges in the different layers of the merge DAG of 0-NTs (c), (d).
Merging unfolding trees.Merging the unfolding trees of a graph with the labeling \(L=\phi\) leads to the computation DAG of GNNs. Figure 3(a) shows the computation DAG for the graph from Figure 1. The roots in this DAG correspond to the representation of the vertices after aggregating information from the lower layers. Each node occurs once at every layer of the DAG and the links between any two consecutive layers are given by the adjacency matrix of the original graph. While this allows computation based on the adjacency matrix widely-used for MPNNs, it involves the encoding of redundant information. Our method has the potential to compress the computational DAG further by using the less restrictive labeling \(L=\mu\) leading to a DAG, where at layer \(i\) all vertices \(u,v\) with \(c^{(i)}_{\text{wl}}(u)=c^{(i)}_{\text{wl}}(v)\) are represented by the same node. This compression appears particularly promising for graphs with symmetries.

Merging neighborhood trees.Merging the \(k\)-redundant neighborhood trees in the same way using the labeling \(L=\mu\) (or \(L=\phi\) if we want to avoid parallel edges), leads to a computation DAG having a less regular structure, see Figure 3(b) for an example. First, there might be multiple nodes on the same level representing the same original vertex. Second, the adjacency matrix of the original graph cannot be used to propagate the information. A trivial upper bound on the size of the merge DAG of a graph with \(n\) nodes and \(m\) edges is \(O(nmk+nm)\).

We apply the neural tree canonization approach to the merge DAG in a bottom-up fashion from the leaves to the roots. Each edge is used exactly once in this computation. Let \(D=(\mathcal{V},\mathcal{E})\) be a merge DAG. The nodes can be partitioned based on their height resulting in \(\mathcal{L}_{i}=\{v\in\mathcal{V}\mid\text{hgt}(v)=i\}\). This induces the edge partition \(\mathcal{E}_{i}=\{uv\in\mathcal{E}\mid v\in\mathcal{L}_{i}\}\), in which all edges with some end node \(v\) are in the same layer and all the incoming edges of children of \(v\) are in a previous layer. Note, that since \(\mathcal{L}_{0}\) contains all leaves of the DAG, there is no \(\mathcal{E}_{0}\). Figures 3(c) and 3(d) show the edge sets \(\mathcal{E}_{1}\) and \(\mathcal{E}_{2}\) for the example merge DAG of Figure 3(b).

### Non-Redundant Neural Architecture (DAG-MLP)

We introduce a neural architecture computing embeddings for the nodes in a merge DAG allowing to retrieve embeddings of the contained trees from its roots. First, a preprocessing step transforms the node labels using \(\text{MLP}_{0}\), mapping them to an embedding space of fixed dimensions. Then, an \(\text{MLP}_{i}\) is used to process the nodes at each layer \(\mathcal{L}_{i}\).

\[\mu^{\prime}(v) =\text{MLP}_{0}\left(\mu(v)\right), \forall v\in\mathcal{V}\] \[x(v) =\mu^{\prime}(v), \forall v\in\mathcal{L}_{0}\] \[x(v) =\text{MLP}_{i}\left((1+\epsilon_{i})\cdot\mu^{\prime}(v)+\sum_{ \forall u:\;uv\in\mathcal{E}_{i}}x(u)\right), \forall v\in\mathcal{L}_{i},i\in\{1,\ldots,n\}\]

The DAG-MLP can be computed through iterated matrix-vector multiplication analogous to standard GNNs. Let \(\mathbf{L}_{i}\) be a square matrix with ones on the diagonal at position \(j\) if \(v_{j}\in\mathcal{L}_{i}\), and zeros elsewhere. Let \(\mathbf{E}_{i}\) represent the adjacency matrix of \((\mathcal{V},\mathcal{E}_{i})\), and let \(\mathbf{F}\) denote the node features of \(\mathcal{V}\), corresponding to the initial node labels. The transformed features \(\mathbf{F}^{\prime}\) are
obtained using the preprocessing \(\mathrm{MLP}_{0}\), and \(\mathbf{X}^{[i]}\) represents the updated embeddings at layer \(i\) of the DAG.

\[\mathbf{F}^{\prime} =\mathrm{MLP}_{0}\left(\mathbf{F}\right),\quad\mathbf{X}^{[0]}\ = \mathbf{L}_{0}\mathbf{F}^{\prime},\] \[\mathbf{X}^{[i]} =\mathrm{MLP}_{i}\left((1+\epsilon_{i})\cdot\mathbf{L}_{i}\mathbf{ F}^{\prime}+\mathbf{E}_{i}\mathbf{X}^{[i-1]}\right)+\mathbf{X}^{[i-1]}\,,\]

In the above equation, \(\mathrm{MLP}_{i}\) is applied to the rows associated with nodes in \(\mathcal{L}_{i}\). The embeddings \(\mathbf{X}^{[i]}\) are initially set to zero for the inner nodes and are computed level-wise. To preserve the embeddings from all previous layers, we add \(\mathbf{X}^{[i-1]}\) during the computation of \(\mathbf{X}^{[i]}\). Assume the merge DAG \((D,\xi)\) contains the trees \(\{T_{1},\ldots,T_{n}\}\), then we obtain a node embedding \(\mathbf{X}^{[n]}_{\xi(i)}\) for each tree \(T_{i}\) with \(i\in\{1,\ldots,n\}\). When using a single tree for each vertex of the input graph, this directly yields its final embedding. If we include trees of different height for each vertex of the input graph, we group them accordingly. We use NTs of a given fixed height (Fixed Single-Height) or all NTs of size up to a certain maximum (Combine Heights), see Appendix E for a description of the resulting architecture.

### Expressiveness of 1-NTs

Let \(\varphi\) be an isomorphism between \(G\) and \(H\). We call two nodes \(u\) and \(v\) (or edges \(uw\) and \(vx\)) _corresponding_ in an isomorphism \(\varphi\), if \(\varphi(u)=v\) (for edges \(\varphi(u)\varphi(w)=vx\)). We denote two nodes \(u\) and \(v\) (or edges \(uw\) and \(vx\)) by \(u\cong v\) (\(uw\cong vx\), respectively), if there exists an isomorphism in which \(u\) and \(v\) (\(uw\) and \(vx\)) are corresponding.

For isomorphism testing the (multi)sets of unfolding trees of two graphs (and \(k\)-redundant neighborhood trees, respectively) can be compared. The sets are denoted with \(wl_{i}(G)\) and \(nt_{i,k}(G)\) for iteration \(i\), and defined as \(wl_{i}(G)=\{F_{i}^{v}|v\in V(G)\}\) and \(nt_{i,k}(G)=\{T_{i,k}^{v}|v\in V(G)\}\). If two graphs \(G\) and \(H\) are isomorphic, then by definition of the trees, we can find a bijection \(\psi\) between their tree sets \(wl_{\infty}(G)\) and \(wl_{\infty}(H)\) (and \(nt_{\infty,k}(H)\) and \(nt_{\infty,k}(G)\), respectively), with \(\forall T\colon T\simeq\psi(T)\), which we denote by \(wl_{\infty}(G)=wl_{\infty}(H)\) (\(nt_{\infty,k}(G)=nt_{\infty,k}(H)\)). However, \(wl_{\infty}(G)=wl_{\infty}(H)\Rightarrow G\simeq H\) (and also \(nt_{\infty,k}(G)=nt_{\infty,k}(H)\Rightarrow G\simeq H\)). We focus on 1-redundant neighborhood trees from now on.

**Theorem 3**.: The 1-NT isomorphism test is more powerful than the Weisfeiler-Leman isomorphism test, i.e.,

\[1.\ \forall G,H\colon wl_{\infty}(G)\neq wl_{\infty}(H)\Rightarrow nt _{\infty,1}(G)\neq nt_{\infty,1}(H)\] \[2.\ \exists G,H\colon G\neq H\wedge wl_{\infty}(G)=wl_{\infty}(H) \wedge nt_{\infty,1}(G)\neq nt_{\infty,1}(H).\]

Proof.: 1. We prove the first statement by contradiction. Assume \(u\in V(G),v\in V(H)\), two nodes with \(u\ncong v\), and let \(i\) be the first iteration in which \(F_{i}^{u}\neq F_{i}^{v}\), but \(T_{i,1}^{u}\simeq T_{i,1}^{v}\). From the definition it follows that \(\forall v\colon F_{0}^{v}\simeq T_{0,1}^{v}\), and also \(\forall v\colon F_{1}^{v}\simeq T_{1,1}^{v}\), so \(i\geq 2\).
Since \(i\) is the first iteration they differed, \(F^{u}_{i-1}\simeq F^{v}_{i-1}\). Any isomorphism between \(F^{u}_{i}\) and \(F^{v}_{i}\) can only be generated from extending an isomorphism between \(F^{u}_{i-1}\) and \(F^{v}_{i-1}\). Let \(\varphi\) be an arbitrary isomorphism between \(F^{u}_{i-1}\) and \(F^{v}_{i-1}\), then, no matter how we extend it, there exists an edge in the last layer of \(F^{u}_{i}\), that has no corresponding edge in the last layer of \(F^{v}_{i}\) (or vice versa).

If this edge is in \(T^{u}_{i,1}\) in the last layer, then (since \(T^{u}_{i,1}\simeq T^{v}_{i,1}\)) there is also a corresponding edge in \(T^{o}_{i,1}\), which implies it is also in \(F^{v}_{i}\). This would imply \(F^{u}_{i}\simeq F^{v}_{i}\), contradicting the assumption.

If this edge is not in \(T^{u}_{i,1}\) in the last layer, the same edge must have already occurred in a previous layer in \(T^{u}_{i,1}\). Let \(l\) be the layer that this edge first occurred. Then, \(l\leq i-2\) must hold (because \(k=1\)), and this edge must also occur in \(F^{u}_{i}\), with a corresponding edge in \(T^{o}_{i,1}\) and most importantly in \(F^{v}_{i}\) in that layer (since the trees up to \(i-1\) were the same). But in unfolding trees, an edge from the original graph will be present in every layer after its first occurrence. If the corresponding edge occurs in \(F^{v}_{i}\) in layer \(l\), it also has to occur in layer \(i\) again (implying \(F^{u}_{i}\simeq F^{v}_{i}\)), which implies \(T^{u}_{i,1}\neq T^{v}_{i,1}\) and thereby contradicts the initial assumption. So \(\forall G,H\colon wl_{\infty}(G)\neq wl_{\infty}(H)\Rightarrow nt_{\infty,1} (G)\neq nt_{\infty,1}(H)\).

2. The statement is proven by the example, where \(G\) is a hexagon and \(H\) consists of two triangles. For these graphs all nodes have isomorphic unfolding trees, while their 1-NTs differ (see Figure 5). 

The 1-NTs can also distinguish the molecules decalin and bicyclopentyl, which WL cannot distinguish. We investigate the expressiveness of 0-NTs in Appendix G.

## 5 Experimental Evaluation

We evaluate DAG-MLP with \(k\)-NTs on both synthetic [1, 21] and real-world datasets [20]. We provide information on the datasets in Appendix H.

**Experimental setup.** For synthetic datasets, we choose the number of layers in DAG-MLP based on the average graph diameter. This ensures that most nodes can effectively aggregate information from all other nodes during message propagation. The embeddings at each layer are extracted using readouts, concatenated, and then passed to two learnable linear layers for

Figure 5: Two graphs (a), (b) that cannot be distinguished by unfolding trees, but by 1-NTs. Figure (c) shows the unfolding tree \(F_{3}\), which is the same for all vertices of both graphs, while (d) shows the 1-NTs of the vertices in the hexagon (left) and the triangle (right).
prediction. For evaluation on the TUDataset, we follow the same splits across 10 folds as proposed by [8]. This allows conducting a grid search to identify the optimal hyper-parameters for each dataset. The architecture for combined heights is designed such that each "readout," is used to extract the embeddings corresponding to each layer, and the mean of the average-pooled embeddings is passed to a final MLP layer responsible for prediction (see Appendix E). For the fixed single-height architecture, only the last readout is used, pooled and passed to the final MLP layer. The hyper-parameters are detailed in Appendix J.

**Results.** Table 1 shows the results on the synthetic expressivity datasets. Comparing our approach to GIN, the results we see are consistent with the theoretical findings: 1-NTs are more expressive than GIN. Our hypothesis that 0-NTs are more expressive than GIN on a graph-level is experimentally validated, but a theoretical proof remains future work.

In Table 2, we investigate the impact of the parameter \(k\) and the number of layers \(l\) on the accuracy on EXP-Class. Cases with \(k>l\) can be disregarded, since the computation for NTs remains the same when \(k=l\). Empirically, 0- and 1-NTs yield the highest accuracy. This is consistent with our discussions on expressivity in Section 4.4 and Appendix G. The decrease in accuracy with increasing \(k\) indicates that information redundancy leads to oversquashing.

For TUDataset, we report the accuracy compared to related work in Table 3. Due to the high

\begin{table}
\begin{tabular}{l c c c} \hline \hline
**Model** & **EXP-Class \(\uparrow\)** & **EXP-Iso \(\downarrow\)** & **CSL \(\uparrow\)** \\ \hline GIN [28] & 50.0 \(\pm\) 0.0 & 600 & 10.0 \(\pm\) 0.0 \\
3WLGNN [17] & **100.0 \(\pm\) 0.0** & **0** & 97.8 \(\pm\) 10.9 \\ PathNN-\(\mathcal{SP}^{+}\)[19] & 100.0 \(\pm\) 0.0 & 0 & 100.0 \(\pm\) 0.0 \\ PathNN-\(\mathcal{AP}\)[19] & 100.0 \(\pm\) 0.0 & 0 & 100.0 \(\pm\) 0.0 \\ \hline DAG-MLP (0-NTs) & **100.0 \(\pm\) 0.0** & **0** & **100.0 \(\pm\) 0.0** \\ DAG-MLP (1-NTs) & **100.0 \(\pm\) 0.0** & **0** & **100.0 \(\pm\) 0.0** \\ \hline \hline \end{tabular}
\end{table}
Table 1: Average classification accuracy for EXP-Class and CSL across \(k\)-folds (4-folds and 5-folds), and the number of undistinguished pairs of graphs in EXP-Iso. Best results are highlighted in gray, best results from methods with polynomial time complexity are highlighted in bold.

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline \(k\)**-NTs** & **1 layer** & **2 layers** & **3 layers** & **4 layers** & **5 layers** & **6 layers** \\ \hline
0-NTs & 51.1 \(\pm\) 1.6 & 57.5 \(\pm\) 6.6 & 91.7 \(\pm\) 11.6 & 99.7 \(\pm\) 0.3 & **100.0 \(\pm\) 0.0** & **100.0 \(\pm\) 0.0** \\
1-NTs & 50.1 \(\pm\) 0.2 & 58.9 \(\pm\) 4.6 & 59.4 \(\pm\) 5.7 & 99.6 \(\pm\) 0.5 & 99.9 \(\pm\) 0.2 & **100.0 \(\pm\) 0.0** \\
2-NTs & - & 52.6 \(\pm\) 3.4 & 54.9 \(\pm\) 5.3 & 52.4 \(\pm\) 3.8 & 97.6 \(\pm\) 1.9 & **100.0 \(\pm\) 0.0** \\
3-NTs & - & - & 56.2 \(\pm\) 5.7 & 51.1 \(\pm\) 1.9 & 52.4 \(\pm\) 4.1 & 87.1 \(\pm\) 21.4 \\
4-NTs & - & - & - & 50.1 \(\pm\) 0.2 & 50.6 \(\pm\) 1.0 & 50.4 \(\pm\) 0.7 \\
5-NTs & - & - & - & - & 50.4 \(\pm\) 0.7 & 50.0 \(\pm\) 0.0 \\
6-NTs & - & - & - & - & - & 53.2 \(\pm\) 5.2 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Average accuracy for DAG-MLP using 4-fold cross-validation on EXP-Class [1], evaluated with varying number of layers.
standard deviation across all methods, we present a statistical box plot for the accuracy based on three runs on the testing set of 10-fold cross-validation in Appendix F. We group the methods by their time complexity. Note that, while PathNN performs well on ENZYMES and PROTEINS, the time complexity of this method is exponential. Therefore, we also highlight the best method with polynomial time complexity. For IMDB-B and IMDB-M, which have small diameters, we see that \(k\)-NTs outperform all other methods. For ENZYMES a variant of our approach achieves the best result among the approaches with non-exponential time complexity and \(k\)-NTs lead to a significant improvement over GIN.

## 6 Conclusion

We propose a neural tree canonization technique and combined it with neighborhood trees, which are pruned and more expressive versions of unfolding trees used by standard MPNNs. By merging trees in a DAG, we derive compact representations that form the basis for our neural architecture DAG-MLP, which learns across DAG levels. It inherits the properties of the GIN architecture, but is provably more expressive than 1-WL when based on 1-redundant neighborhood trees. In this effort, we introduced general techniques to derive compact computation DAGs for tree structures encoding node neighborhoods. This revealed a complex interplay between information redundancy, computational redundancy and expressivity, the balancing of which is an avenue for future work.

\begin{table}
\begin{tabular}{l l c c c c} \hline \hline  & **Algorithm** & **IMDB-B** & **IMDB-M** & **ENZYMES** & **PROTEINS** \\ \hline \multirow{4}{*}{\begin{tabular}{} \end{tabular} } & GIN [28] & 71.2 \(\pm\) 3.9 & 48.5 \(\pm\) 3.3 & 59.6 \(\pm\) 4.5 & 73.3 \(\pm\) 4.0 \\  & GAT [27] & 69.2 \(\pm\) 4.8 & 48.2 \(\pm\) 4.9 & 49.5 \(\pm\) 8.9 & 70.9 \(\pm\) 2.7 \\  & SPN (\(l=1\)) [2] & NA & NA & 67.5 \(\pm\) 5.5 & 71.0 \(\pm\) 3.7 \\  & SPN (\(l=5\)) [2] & NA & NA & 69.4 \(\pm\) 6.2 & **74.2 \(\pm\) 2.7** \\ \hline \multirow{4}{*}{\begin{tabular}{} \end{tabular} } & PathNet [25] & 70.4 \(\pm\) 3.8 & 49.1 \(\pm\) 3.6 & 69.3 \(\pm\) 5.4 & 70.5 \(\pm\) 3.9 \\  & PathNN-\(\mathcal{P}\)[19] & 72.6 \(\pm\) 3.3 & 50.8 \(\pm\) 4.5 & **73.0 \(\pm\) 5.2** & **75.2 \(\pm\) 3.9** \\  & PathNN-\(\mathcal{S}\mathcal{P}^{+}\)[19] & - & - & 70.4 \(\pm\) 3.1 & 73.2 \(\pm\) 3.3 \\ \hline \multirow{4}{*}{
\begin{tabular}{} \end{tabular} } & DAG-MLP (0-NTs) Fixed Single-Height & **72.9 \(\pm\) 5.0** & 50.2 \(\pm\) 3.2 & 67.9 \(\pm\) 5.3 & 70.1 \(\pm\) 1.7 \\  & DAG-MLP (1-NTs) Fixed Single-Height & 72.4 \(\pm\) 3.8 & 48.8 \(\pm\) 4.3 & **70.6 \(\pm\) 5.5** & 70.2 \(\pm\) 3.4 \\  & DAG-MLP (0-NTs) Combine Heights & 72.8 \(\pm\) 5.6 & 50.1 \(\pm\) 3.8 & 66.7 \(\pm\) 4.8 & 69.1 \(\pm\) 3.6 \\  & DAG-MLP (1-NTs) Combine Heights & 72.2 \(\pm\) 4.5 & **51.3 \(\pm\) 4.4** & 69.2 \(\pm\) 4.5 & 69.5 \(\pm\) 3.0 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Classification accuracy (\(\pm\) standard deviation) over 10-fold cross-validation on the datasets from TUDataset, taken from Michel et al. [19]. Best performance is highlighted in gray, best results from methods with polynomial time complexity are highlighted in bold. “-” denotes not applicable and “NA” means not available.
## Acknowledgments

We would like to thank Christian Permann for his contribution to the conception of neighborhood trees and their efficient generation. This work was supported by the Vienna Science and Technology Fund (WWTF) [10.47379/VRG19009]. The computational results presented have been achieved in part using the Vienna Scientific Cluster (VSC).

## Author Contributions

NK devised the project and the main conceptual ideas. FB made significant contributions to the conception of \(k\)-redundant neighborhood trees and their efficient generation. NK and FB developed the methods for redundancy removal presented in Sections 4.1, 4.2. FB developed the proof of Theorem 3. FB implemented the \(k\)-redundant neighborhood trees, merge DAGs and algorithmic components of the implementation. NK, SM and FB developed the DAG-MLP architecture. SM implemented DAG-MLP, conducted the experimental evaluation and wrote parts of the corresponding sections in the manuscript. FB and NK drafted the manuscript with input from all authors. NK, WG and JL supervised the project. All authors provided critical feedback, participated in discussions, contributed to the interpretation of the results and revised the manuscript.
