Union Subgraph Neural Networks
Graph Neural Networks (GNNs) are widely used for graph representation
learning in many application domains. The expressiveness of vanilla GNNs is
upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) test as they operate on
rooted subtrees through iterative message passing. In this paper, we empower
GNNs by injecting neighbor-connectivity information extracted from a new type
of substructure. We first investigate different kinds of connectivities
existing in a local neighborhood and identify a substructure called union
subgraph, which is able to capture the complete picture of the 1-hop
neighborhood of an edge. We then design a shortest-path-based substructure
descriptor that possesses three nice properties and can effectively encode the
high-order connectivities in union subgraphs. By infusing the encoded neighbor
connectivities, we propose a novel model, namely Union Subgraph Neural Network
(UnionSNN), which is proven to be strictly more powerful than 1-WL in
distinguishing non-isomorphic graphs. Additionally, the local encoding from
union subgraphs can also be injected into arbitrary message-passing neural
networks (MPNNs) and Transformer-based models as a plugin. Extensive
experiments on 18 benchmarks of both graph-level and node-level tasks
demonstrate that UnionSNN outperforms state-of-the-art baseline models, with
competitive computational efficiency. The injection of our local encoding to
existing models is able to boost the performance by up to 11.09%. Our code is
available at https://github.com/AngusMonroe/UnionSNN.
Jiaxing Xu, Aihu Zhang, Qingtian Bian, Vijay Prakash Dwivedi, Yiping Ke
# Union Subgraph Neural Networks

###### Abstract

Graph Neural Networks (GNNs) are widely used for graph representation learning in many application domains. The expressiveness of vanilla GNNs is upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) test as they operate on rooted subtrees through iterative message passing. In this paper, we empower GNNs by injecting neighbor-connectivity information extracted from a new type of substructure. We first investigate different kinds of connectivities existing in a local neighborhood and identify a substructure called union subgraph, which is able to capture the complete picture of the 1-hop neighborhood of an edge. We then design a shortest-path-based substructure descriptor that possesses three nice properties and can effectively encode the high-order connectivities in union subgraphs. By infusing the encoded neighbor connectivities, we propose a novel model, namely Union Subgraph Neural Network (UnionSNN), which is proven to be strictly more powerful than 1-WL in distinguishing non-isomorphic graphs. Additionally, the local encoding from union subgraphs can also be injected into arbitrary message-passing neural networks (MPNNs) and Transformer-based models as a plugin. Extensive experiments on 17 benchmarks of both graph-level and node-level tasks demonstrate that UnionSNN outperforms state-of-the-art baseline models, with competitive computational efficiency. The injection of our local encoding to existing models is able to boost the performance by up to 11.09%.

## 1 Introduction

With the ubiquity of graph-structured data emerging from various modern applications, Graph Neural Networks (GNNs) have gained increasing attention from both researchers and practitioners. GNNs have been applied to many application domains, including quantum chemistry [8; 10; 31], social science [14; 44; 60], transportation [9; 40] and neuroscience [2; 52], and have attained promising results on graph classification [31; 60], node classification [43] and link prediction [45; 63] tasks.

Most GNNs are limited in terms of their expressive power. Xu et al., [57] show that GNNs are at most as powerful as 1-dimentional Weisfeiler-Leman (1-WL) test [54] in distinguishing non-isomorphic
graph structures. This is because a vanilla GNN essentially operates on a subtree rooted at each node in its message passing, _i.e._, it treats every neighbor of the node equally in its message aggregation. In this regard, it overlooks any discrepancy that may exist in the connectivities between neighbors. To address this limitation, efforts have been devoted to incorporating local substructure information to GNNs. Several studies attempt to encode such local information through induced subgraphs [65], overlap subgraphs [55] and spatial encoding [4], to enhance GNNs' expressiveness. But the local structures they choose are not able to capture the complete picture of the 1-hop neighborhood of an edge. Some others incorporate shortest path information to edges in message passing via distance encoding [26], adaptive breath/depth functions [29] and affinity matrix [51] to control the message from neighbors at different distances. However, the descriptor used to encode the substructure may overlook some connectivities between neighbors. Furthermore, some of the above models also suffer from high computational cost due to the incorporation of certain substructures.

In this paper, we aim to develop a model that overcomes the above drawbacks and yet is able to empower GNNs' expressiveness. (1) We define a new type of substructures named union subgraphs, each capturing the entire closed neighborhood w.r.t. an edge. (2) We design an effective substructure descriptor that encodes high-order connectivities and it is easy to incorporate with arbitrary message-passing neural network (MPNN) or Transformer-based models. (3) We propose a new model, namely Union Subgraph Neural Network (UnionSNN), which is strictly more expressive than the vanilla GNNs (1-WL) in theory and also computationally efficient in practice. Our contributions are summarized as follows:

* We investigate different types of connectivities existing in the local neighborhood and identify the substructure, named "union subgraph", that is able to capture the complete 1-hop neighborhood.
* We abstract three desirable properties for a good substructure descriptor and design a shortest-path-based descriptor that possesses all the properties with high-order connectivities encoded.
* We propose a new model, UnionSNN, which incorporates the information extracted from union subgraphs into the message passing. We also show how our local encoding can be flexibly injected into any arbitrary MPNNs and Transformer-based models. We theoretically prove that UnionSNN is more expressive than 1-WL. We also show that UnionSNN is stronger than 3-WL in some cases.
* We perform extensive experiments on both graph-level and node-level tasks. UnionSNN consistently outperforms baseline models on 17 benchmark datasets, with competitive efficiency. The injection of our local encoding is able to boost the performance of base models by up to 11.09%, which justifies the effectiveness of our proposed union subgraph and substructure descriptor in capturing local information.

## 2 Related Work

### Substructure-Enhanced GNNs

In recent years, several GNN architectures have been designed to enhance their expressiveness by encoding local substructures. GraphSNN [55] brings the information of overlap subgraphs into the message passing scheme as a structural coefficient. However, the overlap subgraph and the substructure descriptor used by GraphSNN are not powerful enough to distinguish all non-isomorphic substructures in the 1-hop neighborhood. Zhao et al. [65] encode the induced subgraph for each node and inject it into node representations. Graph Substructure Network [4] introduces structural biases in the aggregation function to break the symmetry in message passing. For these two methods, the neighborhood under consideration should be pre-defined, and the subgraph matching is extremely expensive (\(O(n^{k})\) for \(k\)-tuple substructure) when the substructure gets large. Similarly, a line of research [3; 17; 47] develops new WL aggregation schemes to take into account substructures like cycles or cliques. Despite these enhancements, performing cycle counting is very time-consuming. Other Transformer-based methods [11; 25; 33; 56] incorporate local structural information via positional encoding [27; 62]. Graphormer [59] combines the node degree and the shortest path information for spatial encoding, while other works [13; 26] employ random walk based encodings that can encode \(k\)-hop neighborhood information of a node. However, these positional encodings
only consider relative distances from the center node and ignore high-order connectivities between the neighbors.

### Path-Related GNNs

A significant amount of works have focused on the application of shortest paths and their related techniques to GNNs. Li et al. [26] present a distance encoding module to augment node features and control the receptive field of message passing. GeniePath [29] proposes an adaptive breath function to learn the importance of different-sized neighborhoods and an adaptive depth function to extract and filter signals from neighbors within different distances. PathGNN [46] imitates how the Bellman-Ford algorithm solves the shortest path problem in generating weights when updating node features. SPN [1] designs a scheme, in which the representation of a node is propagated to each node in its shortest path neighborhood. Some recent works adapt the concept of curvature from differential geometry to reflect the connectivity between nodes and the possible bottleneck effects. CurvGN [58] reflects how easily information flows between two nodes by graph curvature information, and exploits curvature to reweigh different channels of messages. Topping et al. [48] propose Balanced Forman curvature that better reflects the edges having bottleneck effects, and alleviate the over-squashing problem of GNNs by rewiring graphs. SNALS [51] utilizes an affinity matrix based on shortest paths to encode the structural information of hyperedges. Our method is different from these existing methods by introducing a shortest-path-based substructure descriptor for distinguishing non-isomorphic substructures.

## 3 Local Substructures to Empower MPNNs

In this section, we first introduce MPNNs. We then investigate what kind of local substructures are beneficial to improve the expressiveness of MPNNs.

### Message Passing Neural Networks

We represent a graph as \(G=(V,E,X)\), where \(V=\{v_{1},...,v_{n}\}\) is the set of nodes, \(E\in V\times V\) is the set of edges, and \(X=\{\mathbf{x}_{v}\mid v\in V\}\) is the set of node features. The set of neighbors of node \(v\) is denoted by \(\mathcal{N}(v)=\{u\in V\mid(v,u)\in E\}\). The \(l\)-th layer of an MPNN [57] can be written as:

\[\mathbf{h}_{v}^{(l)}=\mathrm{AGG}^{(l-1)}(\mathbf{h}_{v}^{(l-1)},\mathrm{MSG }^{(l-1)}(\{\mathbf{h}_{u}^{(l-1)},u\in\mathcal{N}(v)\})), \tag{1}\]

where \(\mathbf{h}_{v}^{(l)}\) is the representation of node \(v\) at the \(l\)-th layer, \(\mathbf{h}_{v}^{(0)}=\mathbf{x}_{v}\), \(\mathrm{AGG}(\cdot)\) and \(\mathrm{MSG}(\cdot)\) denote the aggregation and message functions, respectively.

### Local Substructures to Improve MPNNs

According to Eq. (1), MPNN updates the representation of a node isotropously at each layer and ignores the structural connections between the neighbors of the node. Essentially, the local substructure utilized in the message passing of MPNN is a subtree rooted at the node. Consequently, if two non-isomorphic graphs have the same set of rooted subtrees, they cannot be distinguished by MPNN (and also 1-WL). Such an example is shown in Figure 1(a). A simple fix to this problem is to encode the local structural information about each neighbor, based on which neighbors are treated unequally in the message passing. One natural question arises: **which substructure shall we choose to characterize the 1-hop local information?**

To answer the above question, we consider two adjacent nodes \(v\) and \(u\), and discuss different types of edges that may exist in their neighbor sets, \(\mathcal{N}(v)\) and \(\mathcal{N}(u)\). We define the closed neighbor set of node \(v\) as \(\tilde{\mathcal{N}}(v)=\mathcal{N}(v)\cup\{v\}\). The induced subgraph of \(\tilde{\mathcal{N}}(v)\) is denoted by \(S_{v}\), which defines the closed neighborhood of \(v\). The common closed neighbor set of \(v\) and \(u\) is \(\mathcal{N}_{vu}=\tilde{\mathcal{N}}(v)\cap\tilde{\mathcal{N}}(u)\) and the exclusive neighbor set of \(v\) w.r.t \(u\) is defined as \(\mathcal{N}_{v}^{-u}=\tilde{\mathcal{N}}(v)-\mathcal{N}_{vu}\). As shown in Figure 1(b), there are four types of edges in the closed neighborhood of \(\{v,u\}\):

* \(E_{1}^{vu}\in\mathcal{N}_{vu}\times\mathcal{N}_{vu}\): edges between the common closed neighbors of \(v\) and \(u\), such as \((a,b)\)
* \(E_{2}^{vu}\in(\mathcal{N}_{vu}\times\mathcal{N}_{v}^{-u})\cup(\mathcal{N}_{vu} \times\mathcal{N}_{u}^{-v})\): edges between a common closed neighbor of \(v\) and \(u\) and an exclusive neighbor of \(v\)/\(u\), such as \((a,d)\);
* \(E_{3}^{vu}\in\mathcal{N}_{v}^{-u}\times\mathcal{N}_{u}^{-v}\): edges between two exclusive neighbors of \(v\) and \(u\) from different sides, such as \((c,d)\);
* \(E_{4}^{vu}\in(\mathcal{N}_{v}^{-u}\times\mathcal{N}_{v}^{-u})\cup(\mathcal{N}_ {u}^{-v}\times\mathcal{N}_{u}^{-v})\): edges between two exclusive neighbors of \(v\) or \(u\) from the same side, such as \((d,f)\).

We now discuss three different local substructures, each capturing a different set of edges.

**Overlap Subgraph[55].** The overlap subgraph of two adjacent nodes \(v\) and \(u\) is defined as \(S_{v\cap u}=S_{v}\cap S_{u}\). The overlap subgraph contains only edges in \(E_{1}^{vu}\).

**Union Minus Subgraph.** The union minus subgraph of two adjacent nodes \(v\) and \(u\) is defined as \(S_{v\cup u}^{-}=S_{v}\cup S_{u}\). The union minus subgraph consists of edges in \(E_{1}^{vu}\), \(E_{2}^{vu}\) and \(E_{4}^{vu}\).

**Union Subgraph**. The union subgraph of two adjacent nodes \(v\) and \(u\), denoted as \(S_{v\cup u}\), is defined as the induced subgraph of \(\tilde{\mathcal{N}}(v)\cup\tilde{\mathcal{N}}(u)\). The union subgraph contains all four types of edges mentioned above.

It is obvious that the union subgraph captures the whole picture of the 1-hop neighborhood of two adjacent nodes. This subgraph captures all types of connectivities within the neighborhood, providing an ideal local substructure for enhancing the expressive power of MPNNs. We illustrate how effective different local substructures are in improving MPNNs through an example in Appendix A. Note that we restrict the discussion to the 1-hop neighborhood because we aim to develop a model based on the MPNN scheme, in which a single layer of aggregation is performed on the 1-hop neighbors.

### Union Isomorphism

We now proceed to define the isomorphic relationship between the neighborhoods of two nodes \(i\) and \(j\) based on union subgraphs. The definition follows that of overlap isomorphism in [55].

**Overlap Isomorphism.**\(S_{i}\) and \(S_{j}\) are overlap-isomorphic, denoted as \(S_{i}\simeq_{overlap}S_{j}\), if there exists a bijective mapping \(g\): \(\tilde{\mathcal{N}}(i)\rightarrow\tilde{\mathcal{N}}(j)\) such that \(g(i)=j\), and for any \(v\in\mathcal{N}(i)\) and \(g(v)=u\), \(S_{i\cap v}\) and \(S_{j\cap u}\) are isomorphic (ordinary graph isomorphic).

**Union Isomorphism**. \(S_{i}\) and \(S_{j}\) are union-isomorphic, denoted as \(S_{i}\simeq_{union}S_{j}\), if there exists a bijective mapping \(g\): \(\tilde{\mathcal{N}}(i)\rightarrow\tilde{\mathcal{N}}(j)\) such that \(g(i)=j\), and for any \(v\in\mathcal{N}(i)\) and \(g(v)=u\), \(S_{i\cup v}\) and \(S_{j\cup u}\) are isomorphic (ordinary graph isomorphic).

**Theorem 1**.: _If \(S_{i}\simeq_{union}S_{j}\), then \(S_{i}\simeq_{overlap}S_{j}\); but not vice versa._

Theorem 1 states that union-isomorphism is stronger than overlap-isomorphism. The proofs of all theorems are provided in Appendix B. We provide an example of a pair of non-isomorphic graphs that are distinguishable under union-isomorphism but not overlap-isomorphism or 1-WL (subtree). Please refer to Figure 6 in Appendix C for detailed discussions.

Figure 1: (a) A pair of non-isomorphic graphs not distinguishable by 1-WL; (b) An example of various local substructures for two adjacent nodes \(v\) and \(u\).
UnionSNN

In this section, we first discuss how to design our substructure descriptor so that it well captures the structural information in union subgraphs with several desirable properties. We then present our model UnionSNN, which effectively incorporates the information encoded by the substructure descriptor to MPNNs and Transformer-based models. Finally, we show that UnionSNN has a stronger expressiveness than 1-WL and is superior to GraphSNN in its design.

### Design of Substructure Descriptor Function

Let \(\mathcal{U}=\{S_{v\cup u}|(v,u)\in E\}\) be the set of union subgraphs in \(G\). In order to fuse the information of union subgraphs in message passing, we need to define a function \(f(\cdot)\) to describe the structural information of each \(S_{v\cup u}\in\mathcal{U}\). Ideally, given two union subgraphs centered at node \(v\), \(S_{v\cup u}=(V_{v\cup u},E_{v\cup u})\) and \(S_{v\cup u^{\prime}}=(V_{v\cup u^{\prime}},E_{v\cup u^{\prime}})\), we want \(f(S_{v\cup u})=f(S_{v\cup u^{\prime}})\) iff \(S_{v\cup u}\) and \(S_{v\cup u^{\prime}}\) are isomorphic. We abstract the following properties of a good substructure descriptor function \(f(\cdot)\):

* **Size Awareness**. \(f(S_{v\cup u})\neq f(S_{v\cup u^{\prime}})\) if \(|V_{v\cup u}|\neq|V_{v\cup u^{\prime}}|\) or \(|E_{v\cup u}|\neq|E_{v\cup u^{\prime}}|\);
* **Connectivity Awareness**. \(f(S_{v\cup u})\neq f(S_{v\cup u^{\prime}})\) if \(|V_{v\cup u}|=|V_{v\cup u^{\prime}}|\) and \(|E_{v\cup u}|=|E_{v\cup u^{\prime}}|\) but \(S_{v\cup u}\) and \(S_{v\cup u^{\prime}}\) are not isomorphic;
* **Isomorphic Invariance**. \(f(S_{v\cup u})=f(S_{v\cup u^{\prime}})\) if \(S_{v\cup u}\) and \(S_{v\cup u^{\prime}}\) are isomorphic.

Figure 2 illustrates the properties. Herein, we design \(f(\cdot)\) as a function that transforms \(S_{v\cup u}\) to a path matrix \(\mathbf{P}^{vu}\in\mathbb{R}^{|V_{v\cup u}|\times|V_{v\cup u}|}\) such that each entry:

\[\mathbf{P}^{vu}_{ij}=\mathrm{PathLen}(i,j,S_{v\cup u}),i,j\in V_{v\cup u}, \tag{2}\]

where \(\mathrm{PathLen}(\cdot)\) denotes the length of the shortest path between \(i\) and \(j\) in \(S_{v\cup u}\). We choose the path matrix over the adjacency matrix or the Laplacian matrix as it explicitly encodes high-order connectivities between the neighbors. In addition, with a fixed order of nodes, we can get a unique \(\mathbf{P}^{vu}\) for a given \(S_{v\cup u}\), and vice versa. We formulate it in Theorem 2.

**Theorem 2**.: _With a fixed order of nodes in the path matrix, we can obtain a unique path matrix \(\mathbf{P}^{vu}\) for a given union subgraph \(S_{v\cup u}\), and vice versa._

It is obvious that our proposed \(f(\cdot)\) satisfies the above-mentioned three properties, with a node permutation applied in the isomorphic case.

**Discussion on other substructure descriptor functions**. In the literature, some other functions have also been proposed to describe graph substructures. (1) Edge Betweenness [5] is defined by the number of shortest paths between any pair of nodes in a (sub)graph \(G\) that pass through an edge. When applying the edge betweenness to \((v,u)\) in \(S_{v\cup u}\), the metric would remain the same on two different union subgraphs, one with an edge in \(E_{4}^{u}\) and one without. This shows that edge betweenness does not satisfy Size Awareness; (2) Wijesinghe and Wang [55] puts forward a substructure descriptor as a function of the number of nodes and edges. This descriptor fails to distinguish non-isomorphic subgraphs with the same size, and thus does not satisfy Connectivity Awareness; (3) Discrete Graph Curvature, e.g., Olliveier Ricci curvature [28; 37], has been introduced to MPNNs in recent years [58]. Ricci curvature first computes for each node a probability vector of length \(|V|\) that characterizes a uniform propagation distribution in the neighborhood. It then defines the curvature of two adjacent nodes as the Wasserstein distance of their corresponding probability vectors. Similar to edge betweenness, curvature doesn't take into account the edges in \(E_{4}^{vu}\) in its

Figure 2: Three properties that a good substructure descriptor function \(f(\cdot)\) should exhibit.
computation and thus does not satisfy Size Awareness either. We detail the definitions of these substructure descriptor functions in Appendix D.

### Network Design

For the path matrix of an edge \((v,u)\) to be used in message passing, we need to further encode it as a scalar. We choose to perform Singular Value Decomposition (SVD) [18] on the path matrix and extract the singular values:

\[\mathbf{P}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{*}. \tag{3}\]

The sum of the singular values of \(\mathbf{P}^{vu}\), denoted as \(a^{vu}=\mathrm{sum}(\mathbf{\Sigma}^{vu})\), is used as the local structural coefficient of the edge \((v,u)\in E\). Note that since the local structure never changes in message passing, we can compute the structural coefficients in preprocessing before the training starts. A nice property of this structural coefficient is that, it is **permutation invariant** thanks to the use of SVD and the sum operator. With an arbitrary order of nodes, the computed \(a^{vu}\) remains the same, which removes the condition required by Theorem 2.

**UnionSNN.** We now present our model, namely Union Subgraph Neural Network (UnionSNN), which utilizes union-subgraph-based structural coefficients to incorporate local substructures in message passing. For each vertex \(v\in V\), the node representation at the \(l\)-th layer is generated by:

\[\mathbf{h}_{v}^{(l)}=\mathrm{MLP}_{1}{}^{(l-1)}((1+\epsilon^{(l-1)})\mathbf{h}_{v}^{( l-1)}+\sum_{u\in\mathcal{N}(v)}\mathrm{Trans}^{(l-1)}(\tilde{a}^{vu})\mathbf{h}_{u}^ {(l-1)}), \tag{4}\]

where \(\epsilon^{(l-1)}\) is a learnable scalar parameter and \(\tilde{a}^{vu}=\frac{a^{vu}}{\sum_{u\in\mathcal{N}(v)}a^{vu}}\). \(\mathrm{MLP}_{1}(\cdot)\) denotes a multilayer perceptron (MLP) with a non-linear function ReLU. To transform the weight \(\tilde{a}^{vu}\) to align with the multi-channel representation \(\mathbf{h}_{u}^{(l-1)}\), we follow [58] and apply a transformation function \(\mathrm{Trans}(\cdot)\) for better expressiveness and easier training:

\[\mathrm{Trans}(a)=\mathrm{softmax}(\mathrm{MLP}_{2}(a)), \tag{5}\]

where \(\mathrm{MLP}_{2}\) denotes an MLP with ReLU and a channel-wise softmax function \(\mathrm{softmax}(\cdot)\) normalizes the outputs of MLP separately on each channel. For better understanding, we provide the pseudo-code of UnionSNN in Appendix E.

**As a Plugin to Empower Other GNNs.** In addition to a standalone UnionSNN network, our union-subgraph-based structural coefficients could also be incorporated into other GNNs in a flexible and yet effective manner. For arbitrary MPNNs as in Eq. (1), we can plugin our structural coefficients via an element-wise multiplication:

\[\mathbf{h}_{v}^{(l)}=\mathrm{AGG}^{(l-1)}(\mathbf{h}_{v}^{(l-1)},\mathrm{MSG}^{(l-1)}(\{\mathrm{Trans}^{(l-1)}(\tilde{a}^{vu}) \mathbf{h}_{u}^{(l-1)},u\in\mathcal{N}(v)\})). \tag{6}\]

For transformer-based models, inspired by the spatial encoding in Graphormer [59], we can inject our structural coefficients into the attention matrix as a bias term:

\[A_{vu}=\frac{\left(h_{v}W_{Q}\right)\left(h_{u}W_{K}\right)^{T}}{\sqrt{d}}+ \mathrm{Trans}(\tilde{a}^{vu}), \tag{7}\]

where the definition of \(\mathrm{Trans}(\cdot)\) is the same as Eq. (5) and shared across all layers, \(h_{v},h_{u}\in\mathbb{R}^{1\times d}\) are the node representations of \(v\) and \(u\), \(W_{Q},W_{K}\in\mathbb{R}^{d\times d}\) are the parameter matrices, and \(d\) is the hidden dimension of \(h_{v}\) and \(h_{u}\). The detailed interpretation is presented in Appendix F.

### Expressive Power of UnionSNN

We formalize the following theorem to show that UnionSNN is more powerful than 1-WL test in terms of expressive power.

**Theorem 3**.: _UnionSNN is more expressive than 1-WL in testing non-isomorphic graphs._
The stronger expressiveness of UnionSNN over 1-WL is credited to its use of union subgraphs, with an effective encoding of local neighborhood connectivities via the shortest-path-based design of structural coefficients. We further provide a special case to show some graphs can be distinguished by UnionSNN but not by 3-WL or GraphSNN in Appendix G.

**Design Comparisons with GraphSNN** Our UnionSNN is similar to GraphSNN in the sense that both improve the expressiveness of MPNNs (and 1-WL) by injecting the information of local substructures. However, UnionSNN is superior to GraphSNN in the following aspects. (1) Union subgraphs in UnionSNN are stronger than overlap subgraphs in GraphSNN, as ensured by Theorem 1. (2) The shortest-path-based substructure descriptor designed in UnionSNN is more powerful than that in GraphSNN: the latter fails to possess the property of Connectivity Awareness (as elaborated in Section 4.1). An example of two non-isomorphic subgraphs \(S_{v^{\prime}\cap u}\) and \(S_{v^{\prime}\cap u^{\prime}}\) is shown in Figure 3. They have the same structural coefficients in GraphSNN. (3) The aggregation function in UnionSNN works on adjacent nodes in the input graph, while that in GraphSNN utilizes the structural coefficients on all pairs of nodes (regardless of their adjacency). Consequently, GraphSNN requires to pad the adjacency matrix and feature matrix of each graph to the maximum graph size, which significantly increases the computational complexity. The advantages of UnionSNN over GraphSNN are also evidenced by experimental results in Section 5.4.

## 5 Experimental Study

In this section, we evaluate the effectiveness of our proposed model under various settings and aim to answer the following research questions: **RQ1.** Can UnionSNN outperform existing MPNNs and transformer-based models? **RQ2.** Can other GNNs benefit from our structural coefficient? **RQ3.** How do different components affect the performance of UnionSNN? **RQ4.** Is our runtime competitive with other substructure descriptors? We conduct experiments on three tasks: graph classification, graph regression and node classification. When we use UnionSNN to plugin other models we use the prefix term "Union-", such as UnionGCN.

**Datasets.** For graph classification, we use 10 benchmark datasets. Eight of them were selected from the TUDataset [22], including MUTAG, PROTEINS, ENZYMES, DD, FRANKENSTEIN (denoted

\begin{table}
\begin{tabular}{l|c c c c c c c c} \hline \hline  & MUTAG & PROTEINS & ENZYMES & DD & FRANK & Tox21 & NCI1 & NCI109 \\ \hline GAT & 77.56 \(\pm\) 10.49 & 74.34 \(\pm\) 2.09 & 67.67 \(\pm\) 3.74 & 74.25 \(\pm\) 3.76 & 62.85 \(\pm\) 1.59 & 90.35 \(\pm\) 0.71 & 78.07 \(\pm\) 1.94 & 74.34 \(\pm\) 2.18 \\
3WL-GNN & 84.06 \(\pm\) 6.62 & 60.18 \(\pm\) 6.35 & 54.17 \(\pm\) 6.25 & 74.84 \(\pm\) 2.63 & 58.68 \(\pm\) 1.93 & 90.31 \(\pm\) 1.33 & 78.39 \(\pm\) 1.54 & 77.97 \(\pm\) 2.22 \\ UGformer & 75.66 \(\pm\) 8.67 & 70.17 \(\pm\) 5.42 & 64.57 \(\pm\) 4.53 & 75.51 \(\pm\) 5.52 & 56.13 \(\pm\) 2.51 & 88.06 \(\pm\) 0.50 & 68.84 \(\pm\) 1.54 & 66.37 \(\pm\) 2.74 \\ MEWISPool & 84.73 \(\pm\) 4.73 & 68.10 \(\pm\) 3.97 & 53.66 \(\pm\) 6.07 & 76.03 \(\pm\) 2.59 & 64.63 \(\pm\) 2.83 & 88.13 \(\pm\) 0.05 & 74.21 \(\pm\) 3.26 & 75.30 \(\pm\) 1.45 \\ CurvGN & 87.25 \(\pm\) 6.28 & 75.73 \(\pm\) 2.87 & 56.50 \(\pm\) 7.13 & 72.16 \(\pm\) 1.88 & 61.89 \(\pm\) 2.41 & 90.87 \(\pm\) 0.38 & 79.32 \(\pm\) 1.26 & 77.30 \(\pm\) 1.78 \\ NestedGIN & 86.23 \(\pm\) 8.82 & 86.85 \(\pm\) 3.22 & 54.67 \(\pm\) 9.90 & 70.44 \(\pm\) 3.67 & 67.14 \(\pm\) 19.42 & 11.81 \(\pm\) 82.04 & 22.32 \(\pm\) 79.94 \(\pm\) 1.59 \\ GatedGCN-LSPE & 88.33 \(\pm\) 8.38 & 73.94 \(\pm\) 4.22 & 64.50 \(\pm\) 5.92 & 76.74 \(\pm\) 2.69 & 67.44 \(\pm\) 2.65 & 91.71 \(\pm\) 78.05 & 78.15 \(\pm\) 68.01 & 3.23 \(\pm\) 2.33 \\ GraphSNN & 84.04 \(\pm\) 4.09 & 71.78 \(\pm\) 4.11 & 67.67 \(\pm\) 3.74 & 76.03 \(\pm\) 2.59 & 67.17 \(\pm\) 2.25 & **92.24**\(\pm\) 0.59 & 70.87 \(\pm\) 2.78 & 70.11 \(\pm\) 1.86 \\ \hline GCN & 77.13 \(\pm\) 5.24 & 73.89 \(\pm\) 2.85 & 64.33 \(\pm\) 5.83 & 72.16 \(\pm\) **2.28** 58.80 \(\pm\) 1.06 & 90.10 \(\pm\) 0.77 & 79.73 \(\pm\) 0.95 & 75.91 \(\pm\) 1.53 \\ UnionGCN (ours) & **81.87 \(\pm\) 3.81** & 75.02 \(\pm\) **2.50** & **64.67**\(\pm\)**7.14** & 69.69 \(\pm\) 4.18 & 61.72 \(\pm\) 1.76 & 91.63 \(\pm\) **0.72** & 80.41 \(\pm\) **1.84** & 79.50 \(\pm\) 1.82 \\ \hline GatedGCN & 77.11 \(\pm\) 10.05 & 76.18 \(\pm\) 3.12 & 66.83 \(\pm\) 5.08 & 72.58 \(\pm\) 3.061 & 61.40 \(\pm\) 1.92 & 90.83 \(\pm\) 0.96 & 80.32 \(\pm\) 2.07 & 78.19 \(\pm\) 2.39 \\ UnionGCN(ours) & 77.14 \(\pm\) **8.14** & **76.91** & 8.06 \(\pm\) **6.73** & 8.68 \(\pm\) 6.89 & 72.50 \(\pm\) 2.22 & 61.44 \(\pm\) **9.81** & 91.31 \(\pm\) **0.88** & 80.95 \(\pm\) 2.11 & 61.82 \(\pm\) **0.88** \\ \hline GraphSAGE & 80.38 \(\pm\) 0.98 & 74.87 \(\pm\) 3.35 & 52.50 \(\pm\) 5.65 & 73.10 \(\pm\) 3.44 & 52.95 \(\pm\) 4.01 & 88.36 \(\pm\) 0.15 & 63.94 \(\pm\) 2.65 & 64.6 \(\pm\) 1.12 \\ UnionSAGE(ours) & 83.04 \(\pm\) 8.20 & 74.57 \(\pm\) 3.55 & 88.32 \(\pm\) 26.64 & 73.85 \(\pm\) 4.06 & 88.59 \(\pm\) 0.12 & 69.36 \(\pm\) 1.84 & 69.87 \(\pm\) 0.06 \\ \hline GIN & 86.23 \(\pm\) 8.17 & 72.86 \(\pm\) 4.14 & 65.83 \(\pm\) 5.93 & 70.29 \(\pm\) 2.96 & 66.50 \(\pm\) 2.37 & 91.74 \(\pm\) 0.95 & 82.29 \(\pm\) 1.77 & 80.95 \(\pm\) 1.87 \\ UnionGIN (ours) & **88.86 \(\pm\) 4.33** & 73.22 \(\pm\) 3.90 & 67.83 \(\pm\) **6.10** & 70.47 \(\pm\) **4.98** & **68.02** & **91.74** & **74.04** & **82.29** & **9.185** & **82.24** & **9.158** \\ \hline UnionSNN (ours) & 87.31 \(\pm\) 5.29 & 75.02 \(\pm\) 2.50 & **68.17** \(\pm\) 7.50 & **77.00** & \(\pm\) 3.73 & 67.83 \(\pm\) 1.99 & 91.76 \(\pm\) 0.85 & **82.34** & \(\pm\) 1.93 & 81.61 \(\pm\) 1.78 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Graph classification results (average accuracy \(\pm\) standard deviation) over 10-fold-CV. The first and second best results on each dataset are highlighted in **bold
as FRANK in our tables), Tox21, NCI1 and NCI109. The other two datasets OGBG-MOLHIV and OGBG-MOLBBBP were selected from Open Graph Benchmark [19]. For graph regression, we conduct experiments on ZINC10k and ZINC-full datasets [12]. For node classification, we test on five datasets, including citation networks (Cora, Citeseer, and PubMed [42]) and Amazon co-purchase networks (Computer and Photo [32]). These datasets cover various graph sizes and densities. The statistics of datasets are summarized in Appendix H.

**Baseline Models.** We select various GNN models as baselines, including (1) classical MPNNs such as GCN [24], GIN [57], GraphSAGE [16], GAT [49], GatedGCN [6]; (2) WL-based GNNs such as 3WL-GNN [30]; (3) transformer-based methods such as UGformer [35], Graphormer [59] and GPS [41]; (4) state-of-the-art graph pooling methods such as MEWISPool [36]; (5) methods that introduce structural information by shortest paths or curvature, such as GeniePath [29], CurvGN [58], and NestedGIN [64]; (6) GNNs with positional encoding, such as GatedGCN-LSPE [13]; (7) GraphSNN [55]. Model implementation details are provided in Appendix I.

### Performance on Different Graph Tasks

**Graph-Level Tasks**. For graph classification, we report the results on 8 TUDatasets in Table 1 and the results on 2 OGB datasets in Appendix J. Our UnionSNN outperforms all baselines in 7 out of 10 datasets (by comparing UnionSNN with all baselines without "ours"). We further apply our structural coefficient as a plugin component to four MPNNs: GCN, GatedGCN, GraphSAGE and GIN. The results show that our structural coefficient is able to boost the performance of the base model in almost all cases, with an improvement of up to 11.09%. For graph regression, we report the mean absolute error (MAE) on ZINC10k and ZINC-full. As shown in Table 2, the performance of MPNNs with our structural coefficient (UnionGCN, UnionGIN and UnionSAGE) dramatically beat their counterparts. Additionally, when injecting our structural coefficient into Transformer-based models, Unionormer and UnionGPS make further improvements over Graphormer and GPS.

**Node-Level Tasks**. We report the results of node classification in Table 3. UnionSNN outperforms all baselines on all 5 datasets. Again, injecting our structural coefficient to GCN, GIN, and GraphSNN achieves performance improvement over base models in almost all cases.

\begin{table}
\begin{tabular}{l|c c c} \hline  & ZINC10k & ZINC-full \\ \hline GCN & 0.3800 \(\pm\) 0.0171 & 0.1152 \(\pm\) 0.0010 \\ UnionGCN (ours) & 0.2811 \(\pm\) 0.0050 & 0.0877 \(\pm\) 0.0003 \\ \hline GIN & 0.5090 \(\pm\) 0.0365 & 0.1552 \(\pm\) 0.0079 \\ UnionGIN (ours) & 0.4625 \(\pm\) 0.0222 & 0.1334 \(\pm\) 0.0013 \\ \hline GraphSAGE & 0.3953 \(\pm\) 0.0290 & 0.1205 \(\pm\) 0.0034 \\ UnionSAGE (ours) & 0.3768 \(\pm\) 0.0011 & 0.1146 \(\pm\) 0.0017 \\ \hline Graphormer & 0.1269 \(\pm\) 0.0033 & 0.039 \(\pm\) 0.0031 \\ Unionformer (ours) & 0.1241 \(\pm\) 0.0066 & 0.0252 \(\pm\) 0.0026 \\ \hline GPS & 0.0740 \(\pm\) 0.0022 & 0.0262 \(\pm\) 0.0025 \\ UnionGPS (ours) & 0.0681 \(\pm\) 0.0013 & 0.0236 \(\pm\) 0.0017 \\ \hline \end{tabular}
\end{table}
Table 2: Graph regression results (average test MAE \(\pm\) standard deviation) on ZINC10k and ZINC-full datasets. The best result is highlighted in **bold**. The winner between a base model with and without our structural coefficient injected is highlighted in **gray background**.

\begin{table}
\begin{tabular}{l|c c c c c} \hline  & Cora & Citeseer & PubMed & Computer & Photo \\ \hline GraphSAGE & \(70.60\pm 0.64\) & \(55.02\pm 3.40\) & \(70.36\pm 4.29\) & \(80.30\pm 1.30\) & \(89.16\pm 1.03\) \\ GAT & \(74.82\pm 1.95\) & \(63.82\pm 2.81\) & \(74.02\pm 1.11\) & \(85.94\pm 2.35\) & \(91.86\pm 0.47\) \\ GeniePath & \(72.16\pm 2.69\) & \(57.40\pm 2.16\) & \(70.96\pm 2.06\) & \(82.68\pm 0.45\) & \(89.98\pm 1.14\) \\ CurvGN & \(74.06\pm 1.54\) & \(62.08\pm 0.85\) & \(74.54\pm 1.61\) & \(86.30\pm 0.70\) & \(92.50\pm 0.50\) \\ \hline GCN & \(72.56\pm 4.41\) & \(85.30\pm 3.2\) & \(74.44\pm 0.71\) & \(84.58\pm 3.02\) & \(91.71\pm 0.55\) \\ UnionGCN (ours) & \(74.48\pm 0.42\) & \(59.02\pm 3.64\) & \(74.82\pm 1.10\) & \(88.84\pm 0.27\) & \(92.33\pm 0.53\) \\ \hline GIN & \(75.86\pm 1.09\) & \(63.10\pm 2.24\) & \(76.62\pm 0.64\) & \(86.26\pm 0.56\) & \(92.11\pm 0.32\) \\ UnionGIN (ours) & \(75.90\pm 0.80\) & \(63.66\pm 1.75\) & \(76.78\pm 1.02\) & \(86.81\pm 2.12\) & \(92.28\pm 0.19\) \\ \hline GraphSNN & \(75.44\pm 0.73\) & \(64.68\pm 2.72\) & \(76.76\pm 0.54\) & \(84.11\pm 0.57\) & \(90.82\pm 0.30\) \\ UnionGraphSNN (ours) & \(75.58\pm 0.49\) & \(65.22\pm 1.12\) & \(76.99\pm 0.56\) & \(84.58\pm 0.46\) & \(90.60\pm 0.58\) \\ \hline UnionSNN (ours) & \(76.86\pm 1.58\) & \(65.02\pm 1.02\) & \(77.06\pm 1.07\) & \(87.76\pm 0.36\) & \(92.92\pm 0.38\) \\ \hline \end{tabular}
\end{table}
Table 3: Node classification results (average accuracy \(\pm\) standard deviation) over 10 runs. The first and second best results on each dataset are highlighted in **bold** and underlined. The winner between a base model with and without our structural coefficient injected is highlighted in **gray background**.
### Ablation Study

In this subsection, we validate empirically the design choices made in different components of our model: (1) the local substructure; (2) the substructure descriptor; (3) the encoding method from a path matrix to a scalar. All experiments were conducted on 6 graph classification datasets.

**Local Substructure**. We test three types of local substructures defined in Section 3.2: overlap subgraphs, union minus subgraphs and union subgraphs. They are denoted as "overlap", "minus", and "union" respectively in Table 4. The best results are consistently achieved by using union subgraphs.

**Substructure Descriptor**. We compare our substructure descriptor with four existing ones discussed in Section 4.1. We replace the substructure descriptor in UnionSNN with edge betweenness, node/edge counting, Ricci curvature, and Laplacian matrix (other components unchanged), and obtain four variants, namely BetSNN, CountSNN, CurvNN, and LapSNN. Table 5 shows our UnionSNN is a clear winner: it achieves the best result on 5 out of 6 datasets. This experiment demonstrates that our path matrix better captures structural information.

**Path Matrix Encoding Method**. We test three methods that transform a path matrix to a scalar: (1) sum of all elements in the path matrix (matrix sum); (2) maximum eigenvalue of the path matrix (eigen max); (3) sum of all singular values of the matrix (svd sum) used by UnionSNN in Section 4.2. Table 6 shows that the encoding method "svd sum" performs the best on 5 out of 6 datasets.

### Case Study

In this subsection, we investigate how the proposed structural coefficient \(a^{vu}\) reflects local connectivities. We work on an example union subgraph \(S_{v\cup u}\) in Figure 4 and modify its nodes/edges to study how the coefficient \(a^{vu}\) varies with the local structural change. We have the following observations: (1) with the set of nodes unchanged, deleting an edge increases \(a^{vu}\); (2) deleting a node (and its incident edges) decreases \(a^{vu}\); (3) the four types of edges in the closed neighborhood (Section 3.2) have different effects to \(a^{vu}\): \(E_{1}^{vu}\) <\(E_{2}^{vu}\) <\(E_{3}^{vu}\) <\(E_{4}^{vu}\) (by comparing -ab, -ad, -de, and +df). These observations indicate that a smaller coefficient will be assigned

\begin{table}
\begin{tabular}{l|c c c c c} \hline \hline  & MUTAG & PROTEINS & ENZYMES & DD & NCI1 & NCI109 \\ \hline \hline \multirow{2}{*}{
\begin{tabular}{l} BetSNN \\ CountSNN \\ CurvNN \\ LapSNN \\ UnionSNN \\ \end{tabular} } & \(80.94\pm 6.60\) & \(69.44\pm 6.15\) & \(65.00\pm 5.63\) & \(70.20\pm 5.15\) & \(74.91\pm 2.48\) & \(73.70\pm 1.87\) \\  & \(84.65\pm 6.76\) & \(70.79\pm 5.07\) & \(66.50\pm 6.77\) & \(74.36\pm 7.21\) & \(81.74\pm 2.35\) & \(79.80\pm 1.67\) \\  & \(85.15\pm 7.35\) & \(72.77\pm 4.42\) & \(67.17\pm 6.54\) & \(75.88\pm 3.24\) & \(81.34\pm 2.27\) & \(80.64\pm 1.85\) \\  & \(89.39\pm 5.24\) & \(68.32\pm 3.49\) & \(66.17\pm 4.15\) & \(76.31\pm 2.85\) & \(81.39\pm 2.08\) & \(81.34\pm 2.93\) \\  & \(87.31\pm 5.29\) & \(75.02\pm 2.50\) & \(68.17\pm 5.70\) & \(77.00\pm 2.37\) & \(82.34\pm 1.93\) & \(81.61\pm 1.78\) \\ \hline \hline \end{tabular}
\end{table}
Table 5: Ablation study on substructure descriptor. The best result is highlighted in **bold**.

\begin{table}
\begin{tabular}{l|c c c c c c} \hline \hline  & MUTAG & PROTEINS & ENZYMES & DD & NCI1 & NCI109 \\ \hline \hline \multirow{2}{*}{
\begin{tabular}{l} overlap \\ minus \\ union \\ \end{tabular} } & \(85.70\pm 7.40\) & \(71.33\pm 5.35\) & \(65.00\pm 5.63\) & \(73.43\pm 4.07\) & \(73.58\pm 1.73\) & \(72.96\pm 2.01\) \\  & \(\mathbf{87.31\pm 5.29}\) & \(68.70\pm 3.61\) & \(65.33\pm 4.58\) & \(74.79\pm 4.63\) & \(80.66\pm 1.90\) & \(78.70\pm 2.48\) \\  & \(\mathbf{87.31\pm 5.29}\) & \(\mathbf{75.02\pm 2.50}\) & \(\mathbf{68.17\pm 5.70}\) & \(\mathbf{77.00\pm 2.37}\) & \(\mathbf{82.34\pm 1.93}\) & \(\mathbf{81.61\pm 1.78}\) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Ablation study on local substructure. The best result is highlighted in **bold**.

Figure 4: Structural coefficient analysis.

\begin{table}
\begin{tabular}{l|c c c c c c} \hline \hline  & MUTAG & PROTEINS & ENZYMES & DD & NCI1 & NCI109 \\ \hline \hline \multirow{2}{*}{
\begin{tabular}{l} BetSNN \\ CountSNN \\ CurvNN \\ LapSNN \\ UnionSNN \\ \end{tabular} } & \(80.94\pm 6.60\) & \(69.44\pm 6.15\) & \(65.00\pm 5.63\) & \(70.20\pm 5.15\) & \(74.91\pm 2.48\) & \(73.70\pm 1.87\) \\  & \(84.65\pm 6.76\) & \(70.79\pm 5.07\) & \(66.50\pm 6.77\) & \(74.36\pm 7.21\) & \(81.74\pm 2.35\) & \(79.80\pm 1.67\) \\  & \(85.15\pm 7.35\) & \(72.77\pm 4.42\) & \(67.17\pm 6.54\) & \(75.88\pm 3.24\) & \(81.34\pm 2.27\) & \(80.64\pm 1.85\) \\  & \(\mathbf{89.39\pm 5.24}\) & \(68.32\pm 3.49\) & \(66.17\pm 4.15\) & \(76.31\pm 2.85\) & \(81.39\pm 2.08\) & \(81.34\pm 2.93\) \\  & \(87.31\pm 5.29\) & \(\mathbf{75.02\pm 2.50}\) & \(\mathbf{68.17\pm 5.70}\) & \(\mathbf{77.00\pm 2.37}\) & \(\mathbf{82.34\pm 1.93}\) & \(\mathbf{81.61\pm 1.78}\) \\ \hline \hline \end{tabular}
\end{table}
Table 5: Ablation study on substructure descriptor. The best result is highlighted in **bold**.
to an edge with a denser local substructure. This matches our expectation that the coefficient should be small for an edge in a highly connected neighborhood. The rationale is, such edges are less important in message passing as the information between their two incident nodes can flow through more paths. By using the coefficients that well capture local connectivities, the messages from different neighbors could be properly adjusted when passing to the center node. This also explains the effectiveness of UnionSNN in performance experiments. A quantitative analysis of cycle detection is provided in Appendix J.2 to show the ability of our proposed structural coefficients to capture local substructure information.

### Efficiency Analysis

In this subsection, we conduct experiments on PROTEINS, DD and FRANKENSTEIN datasets, which cover various number of graphs and graph sizes.

**Preprocessing computational cost.** UnionSNN computes structural coefficients in preprocessing. We compare its preprocessing time with the time needed in baseline models for pre-computing their substructure descriptors, including edge betweenness (Betweenness) in BetSNN, node/edge counting (Count_ne) in GraphSNN, Ricci curvature (Curvature) in CurvGN, and counting cycles (Count_cycle) in [3]. As shown in Table 7, the preprocessing time of UnionSNN is comparable to that of other models. This demonstrates that our proposed structural coefficient is able to improve classification performance without significantly sacrificing efficiency. Theoretical time complexity analysis of the structure descriptors is provided in Appendix K.

**Runtime computational cost.** We conduct an experiment to compare the total runtime cost of UnionSNN with those in other MPNNs. The results are reported in Table 8. Although UnionSNN runs slightly slower than GCN and GIN, it runs over 4.56 times faster than WL-based MPNN (3WL-GNN) and is comparable to MPNN with positional encoding (GatedGCN-LSPE). Compared with GraphSNN, UnionSNN runs significantly faster: the efficiency improvement approaches an order of magnitude on datasets with large graphs, e.g., DD. This is because UnionSNN does not need to pad the adjacency matrix and the feature matrix of each graph to the maximum graph size in the dataset, as what GraphSNN does.

## 6 Conclusions

We present UnionSNN, a model that outperforms 1-WL in distinguishing non-isomorphic graphs. UnionSNN utilizes an effective shortest-path-based substructure descriptor applied to union subgraphs, making it more powerful than previous models. Our experiments demonstrate that UnionSNN surpasses state-of-the-art baselines in both graph-level and node-level classification tasks while maintaining its computational efficiency. The use of union subgraphs enhances the model's ability to capture neighbor connectivities and facilitate message passing. Additionally, when applied to existing MPNNs and Transformer-based models, UnionSNN improves their performance by up to 11.09%.
