# Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph
Products

Guy Bar-Shalom
Department of Computer Science
Technion - Israel Institute of Technology
<EMAIL_ADDRESS>
&Beatrice Bevilacqua
Department of Computer Science
Purdue University
<EMAIL_ADDRESS>&Haggai Maron
Department of Electrical & Computer Engineering
Technion - Israel Institute of Technology, Nvidia Research
<EMAIL_ADDRESS>
###### Abstract

In the realm of Graph Neural Networks (GNNs), two exciting research directions
have recently emerged: Subgraph GNNs and Graph Transformers. In this paper, we
propose an architecture that integrates both approaches, dubbed Subgraphormer,
which combines the enhanced expressive power, message-passing mechanisms, and
aggregation schemes from Subgraph GNNs with attention and positional
encodings, arguably the most important components in Graph Transformers. Our
method is based on an intriguing new connection we reveal between Subgraph
GNNs and product graphs, suggesting that Subgraph GNNs can be formulated as
Message Passing Neural Networks (MPNNs) operating on a product of the graph
with itself. We use this formulation to design our architecture: first, we
devise an attention mechanism based on the connectivity of the product graph.
Following this, we propose a novel and efficient positional encoding scheme
for Subgraph GNNs, which we derive as a positional encoding for the product
graph. Our experimental results demonstrate significant performance
improvements over both Subgraph GNNs and Graph Transformers on a wide range of
datasets.

##  1 Introduction

Due to their scalability and elegant architectural design, Message Passing
Neural Networks (MPNNs) have become the most popular type of Graph Neural
Networks (GNNs). Nonetheless, these architectures face significant
limitations, particularly in terms of expressive power (Morris et al., 2019;
Xu et al., 2018), resulting in underwhelming performances in certain tasks.
Over the past few years, multiple GNN architectures have been proposed to
mitigate these problems Morris et al. (2021).

In this paper, we focus on two different enhanced GNN architecture families:
Subgraph GNNs and Graph Transformers. In Subgraph GNNs Zhang and Li (2021);
Cotta et al. (2021); Zhao et al. (2022); Bevilacqua et al. (2022); Frasca et
al. (2022); Zhang et al. (2023b), a GNN is applied to a bag (multiset) of
subgraphs, which is generated from the original graph (for example, the
multiset of subgraphs obtained by deleting one node in the original graph).
Notably, these architectures are provably more expressive than the traditional
message passing algorithms applied directly to the original graph. In
parallel, Transformers Vaswani et al. (2017) have demonstrated outstanding
performance across a wide range of applications, including natural language
processing Vaswani et al. (2017); Kalyan et al. (2021); Kitaev et al. (2020),
computer vision Khan et al. (2022); Dosovitskiy et al. (2020); Li et al.
(2022b), and, more recently, graph-based tasks Ying et al. (2021); Zhang et
al. (2023b); Rampášek et al. (2022). Two of the most important components of
Graph Transformers are their attention mechanism and their positional encoding
scheme, which captures the graph structure. Graph Transformers have achieved
impressive empirical performance, demonstrated by their state-of-the-art
results on molecular tasks Li et al. (2022a).

This work aims to integrate Subgraph GNNs and Graph Transformers into a
unified architecture, which we call Subgraphormer, to leverage the benefits of
both approaches. In order to define this hybrid approach, we develop two main
techniques specifically adapted to subgraphs: (1) A subgraph attention
mechanism, dubbed Subgraph Attention Block (SAB); and (2) A subgraph
positional encoding scheme, which we call product graph PE. We derive these
two mechanisms through a key observation: Subgraph GNNs can be naturally
interpreted as MPNNs operating on a new product graph. This product graph is
defined on 2-tuples of nodes and encodes both the subgraph structure and their
inter-subgraph aggregation schemes.

Our approach builds on the recent maximally expressive (node-based) Subgraph
GNN by Zhang et al. (2023a). The product graph of this architecture has two
main types of edges. First, _internal_ edges, that connect each vertex $v$ in
subgraph $s$ to neighbors of $v$ within $s$. Second, _external_ edges, which
are similarly constructed to connect $v$ to copies of $v$ itself across
different subgraphs $s^{\prime}$ when the node generating subgraph
$s^{\prime}$ is a neighbor of the node generating subgraph $s$. Those are
illustrated in Section 3.1. These external edges enable the exchange of
information between subgraphs, like the aggregation schemes used in existing
Subgraph GNNs, which have been shown to improve performance and expressivity
Zhang et al. (2023a). Our SAB implements both internal and external attention-
based aggregation methods, based on the edges defined above, thereby allowing
individual nodes to refine their representations by selectively attending to
nodes within the same or from different subgraphs. Importantly, as Subgraph
GNNs are already computationally expensive, we restrict the attention to the
product graph connectivity, similarly to sparse transformers Choromanski et
al. (2022); Shirzad et al. (2023).

Our Positional Encoding (PE) scheme, product graph PE, is tailored to the new
product graph connectivity that emerges from the architecture defined above.
Interestingly, this connectivity stems from the Cartesian product of the
original graph with itself, which is a well-known type of graph product. We
define our positional encoding as the Laplacian eigenvectors Rampášek et al.
(2022); Dwivedi et al. (2023); Kreuzer et al. (2021) of the adjacency matrix
associated with this Cartesian product. Crucially, although the vertex set of
the new graph comprises $n^{2}$ nodes, in contrast to $n$ nodes in the
original graph, the special structure of the Cartesian product graph allows us
to compute positional encodings with time complexity equivalent to calculating
positional encodings on the original, smaller graph. We demonstrate that those
subgraph-positional encodings offer a performance boost for Subgraphormer,
particularly in the case of larger graphs where stochastic subgraph sampling
is used. We also describe how product graph PE, and Subgraphormer in general,
can be generalized to other higher-order GNNs that operate on $k$-tuples of
nodes.

An extensive experimental analysis over a variety of eight different datasets
confirms that our architecture leads to significant performance improvements
over both Subgraph GNNs and Graph Transformers, yielding outstanding results
on multiple datasets, including ZINC-12k Sterling and Irwin (2015); Gómez-
Bombarelli et al. (2018); Dwivedi et al. (2023) and the long-range benchmark
Peptides-struct Dwivedi et al. (2022). Furthermore, we address the potential
computational burden of operating on large bags of subgraphs, demonstrating
that the performance of stochastic bag sampling improves when using
Subgraphormer compared to other Subgraph GNNs. In particular, we show that our
positional encodings play a key role in this case.

To summarize, the main contributions of this paper are (1) Subgraphormer, a
novel architecture that combines the strengths of both transformer-based and
subgraph-based architectures; (2) A novel observation connecting Subgraph GNNs
to product graphs; (3) A novel positional encoding scheme tailored to subgraph
methods; and (4) An empirical study demonstrating significant improvements of
Subgraphormer compared to existing baselines in both full bag and stochastic
bag sampling setups.

##  2 Related Work

Subgraph GNNs. Subgraph GNNs (Zhang and Li, 2021; Cotta et al., 2021; Papp et
al., 2021; Bevilacqua et al., 2022; Zhao et al., 2022; Papp and Wattenhofer,
2022; Frasca et al., 2022; Qian et al., 2022; Huang et al., 2022; Zhang et
al., 2023a; Bevilacqua et al., 2023) represent a graph as a collection of
subgraphs, obtained by a predefined generation policy. For example, each
subgraph can be generated by marking exactly one node in the original graph,
an approach commonly referred to as _node marking_ Papp and Wattenhofer (2022)
– which is also the generation policy on which we focus in this paper. Since a
node $v$ of the original graph belongs to multiple subgraphs, we use the tuple
$(s,v)$ to refer to node $v$ in subgraph $s$. Following the literature, we
denote node $s$ in subgraph $s$ as the _root_ of the subgraph. An example of
this concept is illustrated in Figure 1. The success of Subgraph GNNs can be
attributed to the enhanced expressive capabilities of these models, which
surpass those of MPNNs working directly on the original graph.

Figure 1: An example of generating subgraphs from the original graph. We
denote by $v$ the index used for the node dimension, and by $s$ the one
employed for the subgraph dimension. Each subgraph is generated by marking a
single node in the original graph, with the marked node represented in black.
We refer to the marked node as the root of the corresponding subgraph.

Graph Transformers. Transformers have achieved notable success in natural
language processing Vaswani et al. (2017); Kalyan et al. (2021); Kitaev et al.
(2020) and computer vision Khan et al. (2022); Dosovitskiy et al. (2020); Li
et al. (2022b), largely owing to their key component, the attention mechanism
Vaswani et al. (2017), often coupled with positional encoding schemes.
Building on this, the GNN community has introduced Graph Transformers Ying et
al. (2021); Zhang et al. (2023b); Rampášek et al. (2022); Park et al. (2022);
Chen et al. (2022), a specialized variant for graph-structured data. Graph
Transformers incorporate either global attention Kreuzer et al. (2021); Mialon
et al. (2021); Ying et al. (2021), which operates on fully-connected data, or
make use of sparse attention Shirzad et al. (2023); Choromanski et al. (2022);
Brody et al. (2021), tailored to leverage the graph structure. Given the
quadratic nature of Subgraph GNNs, we focus on sparse attention methods.

##  3 From Subgraph GNNs to Product Graphs

This section serves a dual purpose. Firstly, we demonstrate that the most
expressive version of Subgraph GNNs Zhang et al. (2023a), which serves as a
main motivation in our paper, can be implemented by applying an MPNN to a
newly constructed graph. Second, we explore the relationship between this new
graph and the graph Cartesian product operation. Both of those aspects will be
used in the following sections to develop our Subgraphormer architecture.

###  3.1 Subgraph GNNs as MPNNs

Notation. Let $G=(A,X)$ denote an undirected graph with node features.111The
consideration of edge features is omitted for simplicity. The adjacency matrix
$A\in\mathbb{R}^{n\times n}$ represents the graph connectivity while the
feature matrix, $X\in\mathbb{R}^{n\times d}$, represents the node features. We
denote the sets of nodes and edges as $V$ and $E$, respectively, with $|V|=n$.
Additionally, we denote neighbors in $G$ by $\sim_{G}$, that is
$v_{1}\sim_{G}v_{2}$ denotes that $v_{1}$ and $v_{2}$ are neighbors in $G$. We
denote the (usually highly sparse) adjacency and feature matrices of all
subgraphs of a graph with calligraphic letters as,
$\mathcal{A}\in\mathbb{R}^{n^{2}\times n^{2}}$ and
$\mathcal{X}\in\mathbb{R}^{n^{2}\times d}$, respectively. Notably, we index
$\mathcal{X}$ and $\mathcal{A}$ using the tuple $(s,v)$, where
$\mathcal{X}(s,v)$ is the feature of node $v$ in subgraph $s$, and
$\mathcal{A}((s,v),(s^{\prime},v^{\prime}))$ denotes the edge between node $v$
in subgraph $s$ and node $v^{\prime}$ in subgraph $s^{\prime}$.

GNN-SSWL+. We build upon the construction of the maximally expressive Subgraph
GNN proposed in Zhang et al. (2023a), which employs the _Node Marking_
generation policy for generating the subgraphs, and updates the representation
of node $(s,v)$ according to the following formula:

$\displaystyle\mathcal{X}(s,v)^{t+1}$
$\displaystyle=f^{t}\Big{(}\mathcal{X}(s,v)^{t},\mathcal{X}(v,v)^{t},$
$\displaystyle\\{\mathcal{X}(s,v^{\prime})^{t}\\}_{v^{\prime}\sim_{G}v},\\{\mathcal{X}(s^{\prime},v)^{t}\\}_{s^{\prime}\sim_{G}s},\Big{)},$
(1)

for an appropriate parameterized learnable function $f^{t}$, where the
superscript $t$ represents the layer number. Essentially, in each step, a node
is updated using its representation, $\mathcal{X}(s,v)^{t}$, its
representation in the subgraph it is root of, $\mathcal{X}(v,v)^{t}$, and two
multisets of its neighbors’ representations. The first multiset encompasses
horizontal neighbors within the same subgraph, represented as
$\\{\mathcal{X}(s,v^{\prime})^{t}\\}_{v^{\prime}\sim_{G}v}$, and the second
multiset consists of vertical neighbors between the subgraphs, denoted by
$\\{\mathcal{X}(s^{\prime},v)^{t}\\}_{s^{\prime}\sim_{G}s}$.

Product Graph Definition. In what follows, we construct an adjacency matrix of
the form $\mathcal{A}\in\mathbb{R}^{n^{2}\times n^{2}}$ to represent each one
of the updates in Section 3.1; we note that in all cases, this matrix,
although in $\mathbb{R}^{n^{2}\times n^{2}}$, is extremely sparse. We define
the _product graph_ to be the heterogeneous graph222 With a single node type
and multiple edge types. defined by these adjacency matrices, together with a
node feature matrix $\mathcal{X}\in\mathbb{R}^{n^{2}\times d}$. Each adjacency
we construct is visualized for the specific case where the original graph is
the one given in Figure 1.

Internal subgraph connectivity. We start by introducing
$\mathcal{A}_{G}\in\mathbb{R}^{n^{2}\times n^{2}}$ (see inset on the left),
which corresponds to
$\\{\mathcal{X}(s,v^{\prime})^{t}\\}_{v^{\prime}\sim_{G}v}$ and maintains the
connectivity of each subgraph separately. Formally,

$\displaystyle\mathcal{A}_{G}\Big{(}(s,v),(s^{\prime},v^{\prime})\Big{)}=\begin{cases}\delta_{ss^{\prime}}&\text{if
}v\sim_{G}v^{\prime};\\\ 0&\text{otherwise},\end{cases}$ (2)

where $\delta$ is the Kronecker delta.

External subgraph connectivity. The adjacency
$\mathcal{A}_{G^{S}}\in\mathbb{R}^{n^{2}\times n^{2}}$ corresponds to
$\\{\mathcal{X}(s^{\prime},v)^{t}\\}_{s^{\prime}\sim_{G}s}$ (see inset) and
contains edges across different subgraphs; hence denoted by the superscript
$S$ for $G$. In particular, these edges connect the same node in different
subgraphs whenever the root nodes of these subgraphs are neighbors in the
original graph. Formally,

$\displaystyle\mathcal{A}_{G^{S}}\Big{(}(s,v),(s^{\prime},v^{\prime})\Big{)}=\begin{cases}\delta_{vv^{\prime}}&\text{if
}s\sim_{G}s^{\prime};\\\ 0&\text{otherwise}.\end{cases}$ (3)

##### Point-wise updates.

The adjacency corresponding to $\mathcal{X}(v,v)^{t}$, denoted as
$\mathcal{A}_{\text{point}}$, allows a node $v$ in subgraph $s$ to receive its
root representation. Those updates are visualized inset by the grey arrows
pointing from root nodes to other nodes in the same column. This adjacency
matrix can be written as,

$\displaystyle\mathcal{A}_{\text{point}}\Big{(}(s,v),(s^{\prime},v^{\prime})\Big{)}=\begin{cases}1&\text{if
}s^{\prime}=v^{\prime}=v;\\\ 0&\text{otherwise}.\end{cases}$ (4)

To conclude our discussion on the relationship between GNN-SSWL+ and the
product graph we constructed, we state and prove the following proposition
showing that GNN-SSWL+ can be simulated by running an MPNN on the product
graph:

######  Proposition 3.1 (GNN-SSWL+ as an MPNN on the product graph).

Consider a graph $G=(A,X)$. Applying a stacking of RGCN layers Schlichtkrull
et al. (2018), interleaved with ReLU activations, on the product graph, as
defined via the adjacencies in Equations 2, 3 and 4, can implement the GNN-
SSWL$+$ update in Section 3.1.

The proof is in Appendix E. This idea can be easily extended to other Subgraph
GNN types. We note that the general idea of viewing GNNs as MPNNs operating on
a new graph was recently proposed by Bause et al. (2023); Jogl et al. (2022,
2023), and a preliminary discussion on simulating Subgraph GNNs with MPNNs
also appeared in Veličković (2022).

###  3.2 Connection to the Graph Cartesian Product

In the previous section, we described how to build a product graph for
simulating a maximally expressive Subgraph GNN. Next we demonstrate that the
connectivity of this particular product graph is tightly related to the
concept of Graph Cartesian Product Vizing (1963); Harary (2018).

Graph Cartesian Product. In simple terms, the Cartesian product of two graphs
$G_{1}$ and $G_{2}$, denoted $G_{1}\square G_{2}$, is a graph whose vertex set
is the Cartesian product of $V(G_{1})$ and $V(G_{2})$, with two vertices
$(u_{1},u_{2})$ and $(v_{1},v_{2})$ being adjacent if either $u_{1}=v_{1}$ and
$u_{2}$ is adjacent to $v_{2}$ in $G_{2}$, or $u_{2}=v_{2}$ and $u_{1}$ is
adjacent to $v_{1}$ in $G_{1}$; we denote the adjacency matrix of this new
product graph as $\mathcal{A}_{G_{1}\square G_{2}}$. In this paper, we mainly
focus on a specific scenario where $G_{1}=G_{2}$, namely, the Cartesian
product of a graph with itself. For a formal definition, we refer the reader
to Definition A.1 in Appendix A.

Given a graph $G=(A,X)$, the adjacency matrix corresponding to $G\square G$
can be expressed as:

$\mathcal{A}_{G\square G}\triangleq A\otimes I+I\otimes A,$ (5)

with $\otimes$ the Kronecker product and $I$ the identity matrix. We can now
establish a direct connection between the product graph we have built for GNN-
SSWL+ in the previous subsection and the Cartesian product graph.

######  Proposition 3.2 (Internal and External Connectivities give rise to the
Cartesian Product Graph).

The edges induced by the internal and external subgraph connectivities,
represented by $\mathcal{A}_{G}$ and $\mathcal{A}_{G^{S}}$ (Equations 2 and 3)
represent the connectivity of$\mathcal{A}_{G\square G}$. This implies the
relationship:

$\mathcal{A}_{G\square G}=\mathcal{A}_{G^{S}}+\mathcal{A}_{G}.$ (6)

In particular, we have $\mathcal{A}_{G^{S}}=A\otimes
I,\mathcal{A}_{G}=I\otimes A$.

The proof is given in Appendix E.

General Subgraph GNNs as Product Graphs. Different Subgraph GNNs differ in
their aggregation schemes. While the aggregations defined by the adjacencies
in Equations 2, 3 and 4 are sufficient for maximal expressivity among known
subgraph architectures, additional aggregation schemes, that may be important
for certain tasks, have been proposed (Frasca et al., 2022). For instance,
global updates enable nodes to refine their representations by incorporating
information from other nodes, irrespective of their connectivity in the
original graph. For example, a node $(s,v)$, can aggregate information from
all nodes within the same subgraph, $(s,v^{\prime})$, for each $v^{\prime}\in
V$. Similarly, it can refine its representation by considering its copies in
all subgraphs, $(s^{\prime},v)$, for each $s^{\prime}\in V$. Both of these
aggregations can be derived from the adjacency matrices of the Cartesian
product $G_{c}\square G_{c}$. Here, $G_{c}$ denotes the _clique_ graph, whose
adjacency matrix is $\vec{1}\vec{1}^{T}-I$. For a comprehensive discussion on
the connection between Subgraph GNNs and Cartesian product graphs, refer to
Appendix A.

##  4 Subgraphormer

Figure 2: An overview of Subgraphormer. Given an input graph, we first
construct the product graph and compute a subgraph-specific positional
encoding. Then, we apply a stacking of Subgraph Attention Blocks, followed by
a pooling layer to obtain a graph representation. A more comprehensive
depiction of this figure can be found in Figure 3 of Appendix F.

Having established the relationship between Subgraph GNNs and product graphs,
we can now use it to define our architecture: Subgraphormer. Subgraphormer is
composed of a subgraph-specific positional encoding layer, node marking, a
stacking of Subgraph Attention Blocks (SABs), and a final pooling layer, as
depicted in Figure 2. In this section, we delve into the specifics of these
components.

###  4.1 Subgraph Attention Block

In this subsection, we introduce the structure of the Subgraph Attention Block
(SAB), designed to update the representation of each node $v$ in subgraph $s$,
denoted by $\mathcal{X}(s,v)$. In the SAB, the adjacency matrices defined
above serve as sparsification functions, effectively biasing the attention
mechanism to focus on the neighbors of each node in the product graph.

Implementing internal and external subgraph attentions. We implement two
attention mechanisms - dubbed internal and external subgraph attention. These
mechanisms are governed by the adjacency matrices $\mathcal{A}_{G}$ and
$\mathcal{A}_{G^{S}}$, respectively. In general, we employ a sparse attention
approach that computes Query ($\mathcal{Q}^{t}$), Key ($\mathcal{K}^{t}$), and
Value ($\mathcal{V}^{t}$) transformations from the node features
$\mathcal{X}^{t}\in\mathbb{R}^{n^{2}\times d_{1}}$, according to the following
equations:

$\mathcal{Q}^{t}=\mathcal{X}^{t}\mathbf{W}^{t}_{\mathcal{Q}},\
\mathcal{K}^{t}=\mathcal{X}^{t}\mathbf{W}^{t}_{\mathcal{K}},\
\mathcal{V}^{t}=\mathcal{X}^{t}\mathbf{W}^{t}_{\mathcal{V}},$ (7)

where
$\mathbf{W}^{t}_{\mathcal{Q}},\mathbf{W}^{t}_{\mathcal{K}},\mathbf{W}^{t}_{\mathcal{V}}\in\mathbb{R}^{d_{1}\times
d_{2}}$ are learned linear projections. The attention weights
$\alpha^{t}(\mathcal{Q}^{t},\mathcal{K}^{t}|\mathcal{A})\in\mathbb{R}^{n^{2}\times
n^{2}}$ are computed from $\mathcal{Q}^{t}$ and $\mathcal{K}^{t}$ (e.g., by
computing their outer product) _only_ for the non-zero entries of the
adjacency matrix $\mathcal{A}\in\\{\mathcal{A}_{G},\mathcal{A}_{G^{S}}\\}$.
The resulting node representation are then computed employing the following
equations:

$\alpha^{t}_{\mathcal{A}_{G}}\\!(\mathcal{Q}^{t}_{\mathcal{A}_{G}}\\!,\mathcal{K}^{t}_{\mathcal{A}_{G}}\\!|\mathcal{A}_{G}\\!)\mathcal{V}_{\mathcal{A}_{G}}^{t},\alpha^{t}_{\mathcal{A}_{G^{S}}}\\!(\mathcal{Q}^{t}_{\mathcal{A}_{G^{S}}}\\!,\mathcal{K}^{t}_{\mathcal{A}_{G^{S}}}\\!|\mathcal{A}_{G^{S}}\\!)\mathcal{V}_{\mathcal{A}_{G^{S}}}^{t}\\!,$

where we use different parameters (denoted by subscripts) to compute the
attention coefficients of $\mathcal{A}_{G},\mathcal{A}_{G^{S}}$. Importantly,
our formulation of Subgraph GNNs as MPNNs on a product graph (Section 3)
allows us to leverage existing optimized attention-based MPNNs to implement
the Subgraphormer architecture. This avoids the need to build complex custom
Subgraph GNN models from scratch. In particular, our implementation follows
the Graph Attention Network (GAT) approach proposed by Veličković et al.
(2017), which is implemented efficiently by accounting only for the non-zero
entries in $\alpha(Q^{t},K^{t}|\mathcal{A})$. We note that our approach can
leverage any sparse attention model.

Implementing pointwise updates. For pointwise updates we do not use any
attention mechanism, since every node has only a single neighbor. To
additionally include the “self” (self loop) component from Section 3.1 in this
update, namely, $\mathcal{X}(s,v)$, we follow Zhang et al. (2023a) and employ
a GIN encoder Xu et al. (2018), that is,

$\text{point}^{t}(\mathcal{X}^{t},\mathcal{A}_{\text{Point}})=\texttt{MLP}^{t}((1+\epsilon^{t})\mathcal{X}^{t}+(\mathcal{A}_{\text{point}}\mathcal{X}^{t})).$
(8)

Final update step. Putting it all together, a single SAB is defined as an
application of an MLP (applied to the feature dimension) to the concatenation
of all the updates:

$\displaystyle\text{SAB}^{t}$
$\displaystyle(\mathcal{X}^{t},\mathcal{A}_{G},\mathcal{A}_{G^{S}},\mathcal{A}_{\text{Point}})=$
$\displaystyle\texttt{MLP}^{t}$
$\displaystyle(\alpha^{t}_{\mathcal{A}_{G}}(\mathcal{Q}^{t}_{\mathcal{A}_{G}},\mathcal{K}^{t}_{\mathcal{A}_{G}}|\mathcal{A}_{G})\mathcal{V}^{t}_{\mathcal{A}_{G}}\oplus$
$\displaystyle\alpha^{t}_{\mathcal{A}_{G^{S}}}\\!(\mathcal{Q}^{t}_{\mathcal{A}_{G^{S}}}\\!,\mathcal{K}^{t}_{\mathcal{A}_{G^{S}}}\\!|\mathcal{A}_{G^{S}})\mathcal{V}^{t}_{\mathcal{A}_{G^{S}}}\\!\\!\oplus\\!\text{point}^{t}(\mathcal{X}^{t}\\!,\mathcal{A}_{\text{Point}})),$

where $\oplus$ represents feature concatenation.

We remark that one way of looking at a SAB update is by taking inspiration
from Proposition 3.1 and extending the message passing within RGCN to further
include different attention weights for each edge type, enabling nodes to
attend differently to nodes connected via various edge types.

Pooling. After a stacking of SAB layers, we employ a pooling layer to obtain a
graph representation, that is,

$\displaystyle\rho(\mathcal{X}^{T})=\texttt{MLP}^{T}\Big{(}\sum_{s=1}^{n}\Big{(}\sum_{v=1}^{n}\mathcal{X}^{T}(s,v)\Big{)}\Big{)},$
(9)

where $T$ denotes the final layer.

We note that a stacking of SABs followed by an invariant pooling layer as
described above, guarantees invariance to node permutations. This is because
each block in our model maintains equivariance to node permutations, while the
final pooling layer ensures invariance to such permutations.

Complexity. SAB matches GNN-SSWL+ in time and space complexity, with both at
$\mathcal{O}(|V|^{2}+|V||E|)$ for an original graph of $|V|$ nodes and $|E|$
edges. See Appendix D for a detailed complexity analysis of each aggregation.

###  4.2 Subgraph Positional Encodings

Positional encodings for graphs have been well studied Dwivedi et al. (2021);
Wang et al. (2022); Lim et al. (2022), and were shown to provide valuable
information for both message-passing based GNNs and graph transformers.

A prominent approach that we follow in this work makes use of the
eigendecomposition of the graph Laplacian matrix. More specifically, given a
graph $G=(A,X)$, the Laplacian is defined as $L=D-A$, where
$D=\text{diag}(A\vec{1})$ is the degree matrix. The positional encoding is
calculated by an eigendecomposition of the Laplacian, $L=U^{T}\Lambda U$, as

$\textbf{p}_{v}^{:k}\triangleq[U_{v1},\ldots,U_{vk}],$ (10)

as the encoding for node $v$, where $k$ is a hyperparameter denoting the
number of eigenvectors we consider, $k\leq n$. We note that the eigenvectors
are sorted (in ascending order) according to their eigenvalues.

Unfortunately, directly applying this approach to Subgraph GNNs is not
straightforward for two reasons: _(1) Unclear adjacency structure:_ For the
Laplacian to be computed, it is necessary to determine the relevant symmetric
adjacency matrix. Specifically, Subgraph GNNs, in general, operate over a
collection of subgraphs rather than on a graph structure. It is not clear what
type of connectivity we should use for the Laplacian of this structure. _(2)
Efficiency concerns:_ The adjacency matrix for Subgraph GNNs is of size
${n^{2}\times n^{2}}$. Consequently, computing its Laplacian’s $k$
eigenvectors results in a computational complexity of $\mathcal{O}(k\cdot
n^{4})$, as opposed to $\mathcal{O}(k\cdot n^{2})$Lanczos (1950); Lehoucq et
al. (1998); Lee et al. (2009) for a graph with $n$ nodes, rendering it
impractical in many scenarios.

In the following, we design a positional encoding scheme that addresses these
two challenges. We start with the adjacency challenge. A natural solution to
(1) is to employ the adjacencies $\mathcal{A}_{G}$, $\mathcal{A}_{G^{S}}$ in
Equations 2 and 3, excluding $\mathcal{A}_{\text{point}}$ since it is
asymmetrical and the connectivity it represents is not related to the original
graph. These adjacencies correspond to the main connectivity employed by
Subgraphormer. Consequently, our proposed positional encoding method will
primarily focus on the symmetric connectivity defined by $\mathcal{A}_{G}$ and
$\mathcal{A}_{G^{S}}$ only. This choice brings us to the challenge (2).

To address point (2), we utilize Proposition 3.2 that established a
relationship between the adjacency matrices $\mathcal{A}_{G^{S}}$,
$\mathcal{A}_{G}$, and the Cartesian product graph, expressed as,

$\mathcal{A}_{G\square G}=\mathcal{A}_{G^{S}}+\mathcal{A}_{G}=A\otimes
I+I\otimes A.$ (11)

Surprisingly, Equation 11 simplifies the computation of eigenvectors for the
Laplacian $\mathcal{L}_{G\square G}$, by leveraging the eigenvectors and
eigenvalues of the original graph $G$, as detailed in the following
proposition Barik et al. (2015).

######  Proposition 4.1 (Product Graph eigendecomposition).

Consider a graph $G=(A,X)$.333We assume $A$ has no self loops. The
eigenvectors and eigenvalues of the Laplacian matrix of $G\square G$, namely,
$\mathcal{L}_{G\square G}$, are $\\{(v_{i}\otimes
v_{j},\lambda_{i}+\lambda_{j})\\}_{i,j=1}^{n^{2}}$, where
$\\{(v_{i},\lambda_{i})\\}_{i=1}^{n}$ are the eigenvectors and eigenvalues of
the Laplacian matrix of $G$.

We refer to Appendix E for the proof. The implications of this observation are
profound. It reveals that, despite the fact that Subgraphormer processes
product graphs with $n^{2}$ nodes, computing the positional encodings only
requires an eigendecomposition of the original smaller graph. Specifically,
for an undirected graph $G=(A,X)$ with $n$ vertices and its Cartesian product
graph $G\square G$, calculating the first $k$ eigenvectors, $k\leq n$, has a
time complexity of $\mathcal{O}(k\cdot n^{2})$ (Lanczos, 1950; Lee et al.,
2009) – the same as computing $k$ eigenvectors for the Laplacian of $G$. A
proof for this claim is also given Appendix E. We refer to our subgraph-
positional encodings as _product graph PE_ , or simply _PE_.

Visualizing product graph PE. To illustrate the benefits of our product graph
PE, we visualize in different colors the entries of the first non-trivial
eigenvector of both the original graph (upper) and the product graph (lower).

It is readily apparent that the eigenvector on the product graph conveys more
information than the one on the original graph. This distinction is
particularly evident by observing the color diversity, with the product graph
featuring ten distinct colors as opposed to the four in the original graph.

Concatenation PE. We briefly introduce another subgraph positional encoding
method, _concatenation PE_. Given the Laplacian matrix $L=U^{T}\Lambda U$, of
a graph $G$, the concatenation PE for a node $(s,v)$ is given by the output of
an MLP on the concatenated vectors
$\mathbf{p}_{s}^{:k}=[U_{s1},\ldots,U_{sk}]$ and
$\mathbf{p}_{v}^{:k}=[U_{v1},\ldots,U_{vk}]$; we highlight that those two
vectors corresponds to the eigenvectors when considering each of the
connectivities, $\mathcal{A}_{G},\mathcal{A}_{G^{S}}$, independently. Notably,
concatenation PE can approximate (up to an ordering) the product graph PE.
This is because the product graph PE multiplies specific elements from the
concatenation PE, a process that can be approximated using a MLP by using the
Universal Approximation Theorem Hornik (1991); Cybenko (1989). However, we use
the product graph PE in this study due to its superior performance, as shown
in the comparison over the ZINC-12k dataset in Section C.3.1.

Node Marking. Motivated by existing Subgraph GNNs, we leverage an additional
“special mark”, defined as _node marking_ , which we concatenate to each
node’s positional encoding. Following the approach of Zhang et al. (2023a), we
hold a lookup table, and assign a learnable embedding to each node,
represented as $z_{\text{dist}(s,v)}\in\mathbb{R}^{d}$. The embedding assigned
to node $(s,v)$ is indexed by the shortest path distance between them in the
original graph $G$ – $\text{dist}(s,v)$.444We assign a unique mark if the two
nodes are unreachable from each other, i.e., $\text{dist}(s,v)=\infty$.

###  4.3 Scaling up Subgraphormer

Given a graph $G$ with $n$ nodes, Subgraphormer operates on a transformed
graph with $n^{2}$ nodes. Even though this transformed graph is extremely
sparse, this is a well-known drawback of Subgraph GNNs (Qian et al., 2022;
Kong et al., 2023; Bevilacqua et al., 2023) when considering large graphs,
since processing the new graph might be infeasible.

Thus, in this section we adopt the idea of stochastic sampling (Bevilacqua et
al., 2022; Cotta et al., 2021; Zhao et al., 2022). Specifically, we adapt
Subgraphormer to stochastic sampling by adding sparsifications to the
adjacencies based on the sampling (see inset). We sample rows (subgraphs)
uniformly at random and include an edge if and only if both of its endpoints
are part of the sampled graph.

Formally, we introduce a sampling mask, $\mathcal{A}_{\text{mask}}$, defined
as,

$\displaystyle\mathcal{A}_{\text{mask}}\Big{(}(s,v),(s^{\prime},v^{\prime})\Big{)}=\begin{cases}1&\text{if
}s~{}\text{and}~{}s^{\prime}~{}\text{are sampled};\\\
0&\text{otherwise}.\end{cases}$

Given an adjacency matrix $\mathcal{A}$ and a generated sampling mask
$\mathcal{A}_{\text{mask}}$, we perform an element-wise logical AND operation
between them. Consequently, $\mathcal{A}$ is adjusted to preserve only edges
that connect node pairs in sampled subgraphs.

Importantly, our _product graph PE_ (Section 4.2) can be computed
independently from the sampling process. This feature allows them to retain
information from the complete, unsampled graph. As demonstrated in the
experimental section, this attribute of _product graph PE_ proves
advantageous, as it appears to effectively compensate for the information loss
incurred due to sampling.

###  4.4 Generalization to Higher-Order Graph Networks

While our current derivation considers product graphs containing 2-tuples of
nodes, both the SAB and the product graph PE can be naturally extended to
define similar high-order architectures operating on $k$-tuples of nodes
Morris et al. (2019); Maron et al. (2018). This extension is grounded in our
understanding that Subgraph GNNs are connected to the Cartesian product of
graphs. Accordingly, this product can be generalized to be applied $k$ times,
rather than being limited to $k=2$. This generalization leads to the formation
of $k$ distinct adjacency matrices, each representing different
“Internal/External” aggregations. To elaborate, the $i$-th adjacency matrix is
defined as $\underbrace{I\otimes I\otimes\cdots\otimes I\otimes A\otimes
I\otimes\cdots\otimes I\otimes I}_{\text{with }A\text{ exclusively positioned
in the }i\text{-th slot}}$. Similarly, the positional encodings can also be
extended to any $k$-tuple, with the eigenvectors obtained by the tensor
product of $k$ eigenvectors of $G$, and the eigenvalues by the sum of the
respective eigenvalues. More specifically, for each sequence of indices
$\\{i_{1},i_{2},\ldots,i_{k}\\}$, where $i_{j}\in\\{1,2,\ldots,n\\}$ for each
$j$, there exists an eigenvector-eigenvalue pair given by $(v_{i_{1}}\otimes
v_{i_{2}}\otimes\ldots\otimes
v_{i_{k}},\lambda_{i_{1}}+\lambda_{i_{2}}+\ldots+\lambda_{i_{k}})$. Here,
$\\{(v_{i},\lambda_{i})\\}_{i=1}^{n}$ represent the eigenvectors and
eigenvalues of the Laplacian matrix of $G$. Appendix B presents a detailed
derivation of SABs and PEs for $k$-tuples, for any given $k$.

Additionally, we note that the high-order positional encoding discussed here
may be useful for other high-order GNNs.

##  5 Experiments

We conducted an extensive set of experiments over eight different datasets to
answer the following questions:  (Q1) _Can Subgraphormer outperform Subgraph
GNNs and Graph Transformers in real-world benchmarks?_ (Q2) _Does the
attention mechanism prove advantageous?_ (Q3) _Does our product graph
positional encoding scheme boost performance, and in which contexts?_ (Q4)
_How well does Subgraphormer perform when using stochastic sampling?_ (Q5)
_Can Subgraphormer offer competitive performance on long-range benchmarks when
compared to Graph Transformers?_

In the following, we present our main results and refer to Appendix C for
additional experiments.

Table 1: On the ZINC datasets, Subgraphormer outperforms Graph Transformers
and Subgraph GNNs. The top three results are reported as First, Second, and
Third.

Model $\downarrow$ / Dataset $\rightarrow$ | Param. | ZINC-12k | ZINC-Full
---|---|---|---
(MAE $\downarrow$) | (MAE $\downarrow$)
GSN Bouritsas et al. (2022) | $500k$ |  $0.101$$\pm 0.010$ | -
CIN (small) Bodnar et al. (2021) | $100k$ |  $0.094$$\pm 0.004$ |  $0.044$$\pm 0.003$
GIN Xu et al. (2018) | $500k$ |  $0.163$$\pm 0.004$ | -
PPGN++(6) Puny et al. (2023) | $500k$ |  $0.071$$\pm 0.001$ |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.020}}$$\pm 0.001$
SAN Kreuzer et al. (2021) | $509k$ |  $0.139$$\pm 0.006$ | -
URPE Luo et al. (2022) | $492k$ |  $0.086$$\pm 0.007$ |  $0.028$$\pm 0.002$
GPS Rampášek et al. (2022) | $424k$ |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.070}}$$\pm 0.004$ | -
Graphormer Ying et al. (2021) | $489k$ |  $0.122$$\pm 0.006$ |  $0.052$$\pm 0.005$
Graphormer-GD Zhang et al. (2023b) | $503k$ |  $0.081$$\pm 0.009$ |  $0.025$$\pm 0.004$
K-Subgraph SAT Chen et al. (2022) | $523k$ |  $0.094$$\pm 0.008$ | -
NGNN Zhang and Li (2021) | $500k$ |  $0.111$$\pm 0.003$ |  $0.029$$\pm 0.001$
DS-GNN Bevilacqua et al. (2022) | $100k$ |  $0.116$$\pm 0.009$ | -
DSS-GNN Bevilacqua et al. (2022) | $100k$ |  $0.102$$\pm 0.003$ |  $0.029$$\pm 0.003$
GNN-AK Zhao et al. (2022) | $500k$ |  $0.105$$\pm 0.010$ | -
GNN-AK+ Zhao et al. (2022) | $500k$ |  $0.091$$\pm 0.002$ | -
SUN Frasca et al. (2022) | $526k$ |  $0.083$$\pm 0.003$ |  $0.024$$\pm 0.003$
OSAN Qian et al. (2022) | $500k$ |  $0.154$$\pm 0.008$ | -
DS-GNN Bevilacqua et al. (2023) | $500k$ |  $0.087$$\pm 0.003$ | -
GNN-SSWL Zhang et al. (2023a) | $274k$ |  $0.082$$\pm 0.003$ |  $0.026$$\pm 0.001$
GNN-SSWL+ Zhang et al. (2023a) | $387k$ |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.070}}$$\pm 0.005$ |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{0.022}}$$\pm 0.001$
Subgraphormer | $293k$ |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{0.067}}$$\pm 0.007$ |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.020}}$$\pm 0.002$
Subgraphormer + PE | $293k$ |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.063}}$$\pm 0.001$ |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.023}}$$\pm 0.001$

Table 2: On the OGB datasets, Subgraphormer outperforms Graph Transformers and
Subgraph GNNs. The top three results are reported as First, Second, and Third.

Model $\downarrow$ / Dataset $\rightarrow$ | molhiv | molbace | molesol
---|---|---|---
(ROC-AUC $\uparrow$) | (ROC-AUC $\uparrow$) | (RMSE $\downarrow$)
GCN Kipf and Welling (2016) |  $76.06$$\pm 0.97$ |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{79.15}}$$\pm 1.44$ |  $1.114$$\pm 0.036$
GIN Xu et al. (2018) |  $75.58$$\pm 1.40$ |  $72.97$$\pm 4.00$ |  $1.173$$\pm 0.057$
PNA Corso et al. (2020) |  $79.05$$\pm 1.32$ | - | -
GSN Bouritsas et al. (2022) |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{80.39}}$$\pm 0.90$ | - | -
CIN Bodnar et al. (2021) |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{80.94}}$$\pm 0.57$ | - | -
SAN Kreuzer et al. (2021) |  $77.85$$\pm 0.24$ | - | -
GPS Rampášek et al. (2022) |  $78.80$$\pm 1.01$ | - | -
NGNN Zhang and Li (2021) |  $78.34$$\pm 1.86$ | - | -
Recon. GNN Cotta et al. (2021) |  $76.32$$\pm 1.40$ |  $1.026$$\pm 0.033$ | -
DS-GNN Bevilacqua et al. (2022) |  $77.40$$\pm 2.19$ | - | -
DSS-GNN Bevilacqua et al. (2022) |  $76.78$$\pm 1.66$ | - | -
GNN-AK+ Zhao et al. (2022) |  $79.61$$\pm 1.19$ | - | -
SUN Frasca et al. (2022) |  $80.03$$\pm 0.55$ | - | -
OSAN Qian et al. (2022) | - |  $72.30$$\pm 6.60$ |  $0.980$$\pm 0.086$
DS-GNN Bevilacqua et al. (2023) |  $76.54$$\pm 1.37$ |  $78.41$$\pm 1.94$ |  $0.847$$\pm 0.015$
GNN-SSWL+ Zhang et al. (2023a) |  $79.58$$\pm 0.35$ |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{82.70}}$$\pm 1.80$ |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.837}}$$\pm 0.019$
Subgraphormer |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{80.38}}$$\pm 1.92$ |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{81.62}}$$\pm 3.55$ |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{0.832}}$$\pm 0.043$
Subgraphormer + PE |  $79.48$$\pm 1.28$ |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{84.35}}$$\pm 0.65$ |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.826}}$$\pm 0.010$

##### Real-world data.

On the ZINC-12k and ZINC-Full datasets (Sterling and Irwin, 2015; Gómez-
Bombarelli et al., 2018; Dwivedi et al., 2023), Subgraphormer outperforms both
Subgraph GNNs and Graph Transformers by a significant margin, while using a
smaller number of parameters (Table 2). Importantly, the attention mechanism
proves advantageous, as Subgraphormer always outperforms GNN-SSWL+ Zhang et
al. (2023a), on which it builds on by integrating attention blocks.
Remarkably, our product graph PE boosts the performance of Subgraphormer on
ZINC-12k, where it is the top-performing method. A similar trend is observed
on the OGB datasets (Hu et al., 2020) in Table 2. Notably, on the molbace
dataset, the inclusion of the PE improves the performance by $3\%$. Additional
results on Alchemy-12k are reported in Section C.3.

##### Efficacy of stochastic sampling on long-range data.

We experimented on the Peptides-func and Peptides-struct datasets (Dwivedi et
al., 2022), evaluating the ability of Subgraphormer to scale to larger graphs
and to capture long-range dependencies, a notoriously hard task for MPNNs
(Dwivedi et al., 2022). We considered a sampling ratio of $30\%$, which allows
us to run Subgraphormer though typical full-bag Subgraph GNNs cannot be
applied. The results are summarized in Table 3. Despite the reduced number of
subgraphs, Subgraphormer achieves the best performance on Peptides-struct,
outperforming all Graph Transformers, which excel on tasks of this kind, and
offer comparable results over Peptides-func.

Table 3: Results on the Peptides datasets demonstrate the effectiveness of the
stochastic variant of Subgraphormer in tasks where Graph Transformers excel.
Graph Transformers and Subgraph GNNs are highlighted in gray and light blue.
The top three results are reported as First, Second, and Third.

Model $\downarrow$ / Dataset $\rightarrow$ | Peptides-func | Peptides-struct
---|---|---
(AP $\uparrow$) | (MAE $\downarrow$)
GCN Kipf and Welling (2016) |  $0.5930$$\pm 0.0023$ |  $0.3496$$\pm 0.0013$
GIN Xu et al. (2018) |  $0.5498$$\pm 0.0079$ |  $0.3547$$\pm 0.0045$
GatedGCN Bresson and Laurent (2017) |  $0.5864$$\pm 0.0077$ |  $0.3420$$\pm 0.0013$
GatedGCN+RWSE Dwivedi et al. (2022) |  $0.6069$$\pm 0.0035$ |  $0.3357$$\pm 0.0006$
Transf.+LapPE Dwivedi et al. (2022) |  $0.6326$$\pm 0.0126$ |  $0.2529$$\pm 0.0016$
SAN+LapPE Kreuzer et al. (2021) |  $0.6384$$\pm 0.0121$ |  $0.2683$$\pm 0.0043$
SAN+RWSE Kreuzer et al. (2021) |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{0.6439}}$$\pm 0.0075$ |  $0.2545$$\pm 0.0012$
GPS Rampášek et al. (2022) |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.6535}}$$\pm 0.0041$ |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.2500}}$$\pm 0.0005$
GNN-SSWL+ Zhang et al. (2023a) | 30% |  $0.5847$$\pm 0.0050$ |  $0.2570$$\pm 0.0006$
Subgraphormer | 30% |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.6415}}$$\pm 0.0052$ |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{0.2494}}$$\pm 0.0020$
Subgraphormer + PE | 30% |  $0.6373$$\pm 0.0110$ |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.2475}}$$\pm 0.0007$

##### Ablation Study: Product Graph PE.

We assess the impact of our product graph PE on the performance of the
stochastic variant of Subgraphormer under common sampling rates Bevilacqua et
al. (2022) ($100\%$, $50\%$, $20\%$, $5\%$) across four datasets. Table 4
shows that the inclusion of our product graph PE improves the results of
Subgraphormer in 13 out of 16 dataset-sampling combinations. Its effectiveness
is especially noticeable when combined with $20\%$ and $5\%$ ratios,
indicating its role in compensating information loss due to low sampling
rates.

Table 4: Ablation Study over our product graph PE. For each dataset, the best
result for each sampling ratio is in Bold.

Dataset $\downarrow$ / Sampling Ratio $\rightarrow$ |  Subgraphormer / Subgraphormer + PE
---|---
100% | 50% | 20% | 5%
ZINC-12k | (MAE $\downarrow$) |  $0.067$$\pm 0.007$ |  $\mathbf{0.063}$$\pm 0.001$ |  $0.084$$\pm 0.002$ |  $\mathbf{0.084}$$\pm 0.002$ |  $0.121$$\pm 0.007$ |  $\mathbf{0.120}$$\pm 0.002$ |  $0.200$$\pm 0.017$ |  $\mathbf{0.175}$$\pm 0.006$
molhiv | (ROC-AUC $\uparrow$) |  $\mathbf{80.38}$$\pm 1.92\phantom{0}$ |  $79.48$$\pm 1.28$ |  $\mathbf{79.66}$$\pm 0.79\phantom{0}$ |  $79.61$$\pm 1.30$ |  $76.48$$\pm 2.38\phantom{0}$ |  $\mathbf{76.68}$$\pm 1.07\phantom{0}$ |  $70.87$$\pm 0.90\phantom{0}$ |  $\mathbf{71.02}$$\pm 0.79\phantom{0}$
molbace | (ROC-AUC $\uparrow$) |  $81.62$$\pm 3.55\phantom{0}$ |  $\mathbf{84.35}$$\pm 0.65\phantom{0}$ |  $79.49$$\pm 2.38\phantom{0}$ |  $\mathbf{83.82}$$\pm 2.62\phantom{0}$ |  $75.27$$\pm 5.63\phantom{0}$ |  $\mathbf{78.77}$$\pm 4.10\phantom{0}$ |  $63.05$$\pm 8.70\phantom{0}$ |  $\mathbf{67.73}$$\pm 5.50\phantom{0}$
molesol | (RMSE $\downarrow$) |  $0.832$$\pm 0.043$ |  $\mathbf{0.826}$$\pm 0.010$ |  $0.829$$\pm 0.013$ |  $\mathbf{0.812}$$\pm 0.001$ |  $1.093$$\pm 0.009$ |  $\mathbf{1.041}$$\pm 0.030$ |  $\mathbf{1.266}$$\pm 0.019$ |  $1.270$$\pm 0.007$

##### Discussion.

In what follows, we address research questions Q1 to Q5.

A1. Tables 2 and 2 show Subgraphormer outperforming all transformer-based and
subgraph-based baselines. A similar trend is observed on the Alchemy-12k
dataset in Table 7 in Section C.3.

A2. Tables 2 and 3 clearly demonstrate the importance of the attention, as
Subgraphormer always outperforms GNN-SSWL+, from which it is built by adding
SABs. On the OGB (Table 2) the attention mechanism proves particularly
beneficial when coupled with the product graph PE.

A3. Table 4 demonstrates the effectiveness of the PE, especially when
considering lower sampling regimes.

A4. The stochastic variant of Subgraphormer proves particularly advantageous
in settings where full-bag Subgraph GNNs cannot be otherwise applied, such as
in Table 3. Additional results can be found in Table 8 in Appendix C.

A5. Table 3 demonstrates the ability of Subgraphormer to capture long-range
dependencies, as it outperforms all baselines on the Peptides-struct dataset,
and performs comparably over Peptides-func.

##  6 Conclusions

In this work, we introduce Subgraphormer, a novel architecture that merges the
capabilities of Subgraph GNNs and Graph Transformers. Building upon our
observation that views Subgraph GNNs as MPNNs operating on product graphs, we
propose: (1) a subgraph-based attention mechanism, which can be implemented by
leveraging optimized sparse attention blocks operating on the product graph;
and (2) a positional encoding scheme capturing the connectivity of the product
graph computed in a time complexity equivalent to computing positional
encodings on the original, small graph. Empirically, we demonstrate that
Subgraphormer outperforms Subgraph GNNs and Graph Transformers over a wide
range of datasets. We also investigated the capabilities of the stochastic
variant of our approach, demonstrating impressive performance on long-range
datasets, where Graph Transformers excel, and full-bag Subgraph GNNs cannot be
applied.

## References

  * Barik et al. (2015) Sasmita Barik, Ravindra B Bapat, and Sukanta Pati.  On the laplacian spectra of product graphs.  _Applicable Analysis and Discrete Mathematics_ , pages 39–58, 2015\.
  * Bause et al. (2023) Franka Bause, Fabian Jogl, Patrick Indri, Tamara Drucks, David Penz, Nils Kriege, Thomas Gärtner, Pascal Welke, and Maximilian Thiessen.  Maximally expressive gnns for outerplanar graphs.  In _NeurIPS 2023 Workshop: New Frontiers in Graph Learning_ , 2023\.
  * Bevilacqua et al. (2022) Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron.  Equivariant subgraph aggregation networks.  _International Conference on Learning Representations_ , 2022.
  * Bevilacqua et al. (2023) Beatrice Bevilacqua, Moshe Eliasof, Eli Meirom, Bruno Ribeiro, and Haggai Maron.  Efficient subgraph gnns by learning effective selection policies.  _International Conference on Learning Representations_ , 2023.
  * Biewald (2020) Lukas Biewald.  Experiment tracking with weights and biases, 2020.  URL https://www.wandb.com/.  Software available from wandb.com.
  * Bodnar et al. (2021) Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein.  Weisfeiler and lehman go cellular: Cw networks.  _Advances in Neural Information Processing Systems_ , 34:2625–2640, 2021.
  * Bouritsas et al. (2022) Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein.  Improving graph neural network expressivity via subgraph isomorphism counting.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(1):657–668, 2022.
  * Bresson and Laurent (2017) Xavier Bresson and Thomas Laurent.  Residual gated graph convnets.  _arXiv preprint arXiv:1711.07553_ , 2017.
  * Brody et al. (2021) Shaked Brody, Uri Alon, and Eran Yahav.  How attentive are graph attention networks?  _arXiv preprint arXiv:2105.14491_ , 2021.
  * Chen et al. (2022) Dexiong Chen, Leslie O’Bray, and Karsten Borgwardt.  Structure-aware transformer for graph representation learning.  In _International Conference on Machine Learning_ , pages 3469–3489. PMLR, 2022.
  * Chen et al. (2019) Guangyong Chen, Pengfei Chen, Chang-Yu Hsieh, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, et al.  Alchemy: A quantum chemistry dataset for benchmarking ai models.  _arXiv preprint arXiv:1906.09427_ , 2019.
  * Choromanski et al. (2022) Krzysztof Choromanski, Han Lin, Haoxian Chen, Tianyi Zhang, Arijit Sehanobish, Valerii Likhosherstov, Jack Parker-Holder, Tamas Sarlos, Adrian Weller, and Thomas Weingarten.  From block-toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked transformers.  In _International Conference on Machine Learning_ , pages 3962–3983. PMLR, 2022.
  * Corso et al. (2020) Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković.  Principal neighbourhood aggregation for graph nets.  _Advances in Neural Information Processing Systems_ , 33:13260–13271, 2020.
  * Cotta et al. (2021) Leonardo Cotta, Christopher Morris, and Bruno Ribeiro.  Reconstruction for powerful graph representations.  In _Advances in Neural Information Processing Systems_ , volume 34, 2021.
  * Cybenko (1989) George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * Dosovitskiy et al. (2020) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Dupty and Lee (2022) Mohammed Haroon Dupty and Wee Sun Lee.  Graph representation learning with individualization and refinement.  _arXiv preprint arXiv:2203.09141_ , 2022.
  * Dupty et al. (2021) Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee.  Pf-gnn: Differentiable particle filtering based approximation of universal graph representations.  In _International Conference on Learning Representations_ , 2021.
  * Dwivedi et al. (2021) Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Graph neural networks with learnable structural and positional representations.  _International Conference on Learning Representations_ , 2021.
  * Dwivedi et al. (2022) Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini.  Long range graph benchmark.  _Advances in Neural Information Processing Systems_ , 35:22326–22340, 2022.
  * Dwivedi et al. (2023) Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Benchmarking graph neural networks.  _Journal of Machine Learning Research_ , 24(43):1–48, 2023.
  * Fey and Lenssen (2019) Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  _arXiv preprint arXiv:1903.02428_ , 2019.
  * Frasca et al. (2022) Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron.  Understanding and extending subgraph gnns by rethinking their symmetries.  _Advances in Neural Information Processing Systems_ , 35:31376–31390, 2022.
  * Gómez-Bombarelli et al. (2018) Rafael Gómez-Bombarelli, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Aguilera-Iparraguirre, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik.  Automatic chemical design using a data-driven continuous representation of molecules.  _ACS central science_ , 4(2):268–276, 2018.
  * Harary (2018) Frank Harary.  _Graph Theory (on Demand Printing Of 02787)_.  CRC Press, 2018.
  * Hornik (1991) Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  _Neural networks_ , 4(2):251–257, 1991.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  _Advances in neural information processing systems_ , 33:22118–22133, 2020.
  * Huang et al. (2022) Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang.  Boosting the cycle counting power of graph neural networks with i2-gnns.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Jogl et al. (2022) Fabian Jogl, Maximilian Thiessen, and Thomas Gärtner.  Weisfeiler and leman return with graph transformations.  In _18th International Workshop on Mining and Learning with Graphs_ , 2022.
  * Jogl et al. (2023) Fabian Jogl, Maximilian Thiessen, and Thomas Gärtner.  Expressivity-preserving gnn simulation.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Kalyan et al. (2021) Katikapalli Subramanyam Kalyan, Ajit Rajasekharan, and Sivanesan Sangeetha.  Ammus: A survey of transformer-based pretrained models in natural language processing.  _arXiv preprint arXiv:2108.05542_ , 2021.
  * Khan et al. (2022) Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah.  Transformers in vision: A survey.  _ACM computing surveys (CSUR)_ , 54(10s):1–41, 2022.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _International Conference on Learning Representations_ , 2016.
  * Kitaev et al. (2020) Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  _arXiv preprint arXiv:2001.04451_ , 2020.
  * Kong et al. (2023) Lecheng Kong, Jiarui Feng, Hao Liu, Dacheng Tao, Yixin Chen, and Muhan Zhang.  Mag-gnn: Reinforcement learning boosted graph neural network.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Kreuzer et al. (2021) Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou.  Rethinking graph transformers with spectral attention.  _Advances in Neural Information Processing Systems_ , 34:21618–21629, 2021.
  * Kwon et al. (2021) Jungmin Kwon, Jeongseop Kim, Hyunseo Park, and In Kwon Choi.  Asam: Adaptive sharpness-aware minimization for scale-invariant learning of deep neural networks.  In _International Conference on Machine Learning_ , 2021.
  * Lanczos (1950) Cornelius Lanczos.  An iteration method for the solution of the eigenvalue problem of linear differential and integral operators1.  _Journal of Research of the National Bureau of Standards_ , 45(4), 1950.
  * Lee et al. (2009) Jongwon Lee, Venkataramanan Balakrishnan, Cheng-Kok Koh, and Dan Jiao.  From o (k 2 n) to o (n): A fast complex-valued eigenvalue solver for large-scale on-chip interconnect analysis.  In _2009 IEEE MTT-S International Microwave Symposium Digest_ , pages 181–184. IEEE, 2009.
  * Lehoucq et al. (1998) Richard B Lehoucq, Danny C Sorensen, and Chao Yang.  _ARPACK users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods_.  SIAM, 1998.
  * Li et al. (2022a) Han Li, Dan Zhao, and Jianyang Zeng.  Kpgt: knowledge-guided pre-training of graph transformer for molecular property prediction.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 857–867, 2022a.
  * Li et al. (2022b) Yanghao Li, Chao-Yuan Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer.  Mvitv2: Improved multiscale vision transformers for classification and detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4804–4814, 2022b.
  * Lim et al. (2022) Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka.  Sign and basis invariant networks for spectral graph representation learning.  _The Eleventh International Conference on Learning Representations_ , 2022.
  * Luo et al. (2022) Shengjie Luo, Shanda Li, Shuxin Zheng, Tie-Yan Liu, Liwei Wang, and Di He.  Your transformer may not be as powerful as you expect.  _Advances in Neural Information Processing Systems_ , 35:4301–4315, 2022.
  * Maron et al. (2018) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  _arXiv preprint arXiv:1812.09902_ , 2018.
  * Mialon et al. (2021) Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal.  Graphit: Encoding graph structure in transformers.  _arXiv preprint arXiv:2106.05667_ , 2021.
  * Morris et al. (2019) Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 4602–4609, 2019.
  * Morris et al. (2020) Christopher Morris, Gaurav Rattan, and Petra Mutzel.  Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.  _Advances in Neural Information Processing Systems_ , 33:21824–21840, 2020.
  * Morris et al. (2021) Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt.  Weisfeiler and leman go machine learning: The story so far.  _arXiv preprint arXiv:2112.09992_ , 2021.
  * Morris et al. (2022) Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh.  Speqnets: Sparsity-aware permutation-equivariant graph networks.  In _International Conference on Machine Learning_ , pages 16017–16042. PMLR, 2022.
  * Papp and Wattenhofer (2022) Pál András Papp and Roger Wattenhofer.  A theoretical comparison of graph neural network extensions.  In _International Conference on Machine Learning_ , pages 17323–17345. PMLR, 2022.
  * Papp et al. (2021) Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer.  Dropgnn: Random dropouts increase the expressiveness of graph neural networks.  _Advances in Neural Information Processing Systems_ , 34:21997–22009, 2021.
  * Park et al. (2022) Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntae Kim, and Seung-won Hwang.  Grpe: Relative positional encoding for graph transformer.  _arXiv preprint arXiv:2201.12787_ , 2022.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Puny et al. (2023) Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman.  Equivariant polynomials for graph neural networks.  In _International Conference on Machine Learning_ , pages 28191–28222. PMLR, 2023.
  * Qian et al. (2022) Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris.  Ordered subgraph aggregation networks.  _Advances in Neural Information Processing Systems_ , 35:21030–21045, 2022.
  * Rampášek et al. (2022) Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini.  Recipe for a general, powerful, scalable graph transformer.  _Advances in Neural Information Processing Systems_ , 35:14501–14515, 2022.
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling.  Modeling relational data with graph convolutional networks.  In _The Semantic Web: 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3–7, 2018, Proceedings 15_ , pages 593–607. Springer, 2018.
  * Shirzad et al. (2023) Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop.  Exphormer: Scaling graph transformers with expander graphs.  _International Conference on Machine Learning_ , 2023.
  * Sterling and Irwin (2015) Teague Sterling and John J Irwin.  Zinc 15–ligand discovery for everyone.  _Journal of chemical information and modeling_ , 55(11):2324–2337, 2015.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Veličković (2022) Petar Veličković.  Message passing all the way up.  _arXiv preprint arXiv:2202.11097_ , 2022.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _International Conference on Learning Representations_ , 2017.
  * Virtanen et al. (2020) Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors.  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  _Nature Methods_ , 17:261–272, 2020.  doi: 10.1038/s41592-019-0686-2.
  * Vizing (1963) Vladim G Vizing.  The cartesian product of graphs.  _Vycisl. Sistemy_ , 9(30-43):33, 1963.
  * Wang et al. (2022) Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li.  Equivariant and stable positional encoding for more powerful graph neural networks.  _International Conference on Learning Representations_ , 2022.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _International Conference on Learning Representations_ , 2018.
  * Ying et al. (2021) Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform badly for graph representation?  _Advances in Neural Information Processing Systems_ , 34:28877–28888, 2021.
  * Yun et al. (2019) Chulhee Yun, Suvrit Sra, and Ali Jadbabaie.  Small relu networks are powerful memorizers: a tight analysis of memorization capacity.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Zhang et al. (2023a) Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang.  A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests.  _International Conference on Machine Learning_ , 2023a.
  * Zhang et al. (2023b) Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He.  Rethinking the expressive power of gnns via graph biconnectivity.  _International Conference on Learning Representations_ , 2023b.
  * Zhang and Li (2021) Muhan Zhang and Pan Li.  Nested graph neural networks.  In _Advances in Neural Information Processing Systems_ , volume 34, 2021.
  * Zhao et al. (2022) Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah.  From stars to subgraphs: Uplifting any GNN with local structure awareness.  In _International Conference on Learning Representations_ , 2022.

##  Appendix A Subgraph GNNs as Cartesian Product Graphs

In this section, we delve into the relationship between the Cartesian product
graph and Subgraphormer (Appendix A.1). Additionally, we explore the broader
connection between Cartesian product graphs and Subgraph GNNs in general
(detailed in Section A.2).

###  A.1 The Cartesian Product Graph and its Application for Subgraphormer

######  Definition A.1 (Cartesian Product Graph).

Given two graphs $G_{1}$ and $G_{2}$, their Cartesian product $G_{1}\square
G_{2}$ is defined as:

  * •

The vertex set $V(G_{1}\square G_{2})=V(G_{1})\times V(G_{2})$.

  * •

Vertices $(u_{1},u_{2})$ and $(v_{1},v_{2})$ in $G_{1}\square G_{2}$ are
adjacent if:

    * –

$u_{1}=v_{1}$ and $u_{2}$ is adjacent to $v_{2}$ in $G_{2}$, or

    * –

$u_{2}=v_{2}$ and $u_{1}$ is adjacent to $v_{1}$ in $G_{1}$.

Thus, we observe the following,

######  Corollary A.1.

Let $G$ be a given graph, defined by an adjacency $A$, and assume $A$ doesn’t
include self loops. The adjacency matrix of the Cartesian product of $G$ with
itself; namely, $G\square G$, is given by

$\mathcal{A}_{G\square G}\triangleq A\otimes I+I\otimes A,$ (12)

where by $\otimes$ we denote the Kronecker product.

Therefore, we claim, See 3.2 The proof is available in Appendix E.

Thus, given Proposition 3.2, our objective is to diagonalize the Laplacian of
$G\square G$, which is defined by,

$\displaystyle\mathcal{L}_{G\square G}$
$\displaystyle=\operatorname{diag}\Big{(}\mathcal{A}_{G\square
G}\vec{1}_{n^{2}}\Big{)}-\mathcal{A}_{G\square G}$ (13)
$\displaystyle=\operatorname{diag}\Big{(}(A\otimes I+I\otimes
A)\vec{1}_{n^{2}}\Big{)}-A\otimes I+I\otimes A,$

where by $\vec{1}_{n^{2}}$ we refer to a vector of $n^{2}$ ones.

The eigendecomposition of $\mathcal{L}_{G\square G}$, is given in the
following proposition, See 4.1

The proof is available in Appendix E.

We conclude with the following result, stating the complexity of our product
graph PE.

######  Proposition A.1 (Product Graph PE Complexity).

Let $G=(A,X)$ be an undirected graph with $n$ vertices, and consider its
Cartesian product graph $G\square G$.

  1. 1.

The time complexity for diagonalizing the Laplacian matrix of $G\square G$ is
$\mathcal{O}(n^{4})$.

  2. 2.

For calculating $k$ eigenvectors, where $k\leq n$, the time complexity is
$\mathcal{O}(k\cdot n^{2})$. This is equivalent to the complexity of computing
$k$ eigenvectors for the original graph $G$.

The proof is available in Appendix E.

###  A.2 Establishing the General Relationship Between Cartesian Product
Graphs and Subgraph GNNs

In this section we develop the connection between Subgraph GNNs and the Graph
Cartesian Product (GCP); the results are summarized in Table 5. We focus
specifically on the node-based (Node-Marking) generation policy, over an
original graph $G=(A,X)$, and specify the formulation of the following four
main connectivities: Internal Subgraph connectivity, External Subgraph
connectivity, Global Internal Subgraph connectivity, Global External Subgraph
connectivity.

Before delving into the derivation details, we define two graphs, $G_{s}$ and
$G_{c}$, corresponding to the “set graph” and the “clique graph”,
respectively. The “set graph” corresponds to a graph with no edges, thus:

$\displaystyle A_{G_{s}}=\vec{0}\vec{0}^{T},$ (14)

and the “clique graph” corresponds to a graph where every pair of nodes is
connected by an edge, hence:

$\displaystyle A_{G_{c}}=\vec{1}\vec{1}^{T}-I.$ (15)

Recalling the definition of the Cartesian product graph
(LABEL:{def:_Graph_Cartesian_Product}), we introduce a relevant corollary:

######  Corollary A.2 (Adjacency of Cartesian Product Graph).

Consider two distinct graphs, $G_{1}=(A_{1},X_{1})$ and $G_{2}=(A_{2},X_{2})$,
with $n$ and $m$ vertices, respectively. The adjacency matrix of their
Cartesian product, denoted as $G_{1}\square G_{2}$, is given by:

$\mathcal{A}_{G_{1}\square G_{2}}=A_{G_{1}}\otimes I_{m}+I_{n}\otimes
A_{G_{2}},$ (16)

where $\otimes$ denotes the Kronecker product, and $I_{n}$ and $I_{m}$ are
identity matrices in $\mathbb{R}^{n\times n}$ and $\mathbb{R}^{m\times m}$,
respectively.

In this subsection, as our focus is on graphs each containing $n$ nodes, we
will omit the subscripts $n/m$ from the identity matrix for simplicity.

Internal Subgraph Connectivity. The adjacency matrix corresponding to the
internal subgraph connectivity, $\mathcal{A}_{G}$, arises from the Cartesian
product of the graphs $G_{s}$ and $G$, that is,

$\displaystyle\mathcal{A}_{G}\triangleq\mathcal{A}_{G_{s}\square
G}=A_{G_{s}}\otimes I+I\otimes A.$ (17)

By substituting Equation 14, we obtain:

$\displaystyle\mathcal{A}_{G_{s}\square G}=I\otimes A.$ (18)

This results is in line with Proposition 3.2.

External Subgraph Connectivity. Similarly, the adjacency matrix for external
subgraph connectivity, $\mathcal{A}_{G^{S}}$, results from the Cartesian
product of the graphs $G$ and $G_{s}$, that is,

$\displaystyle\mathcal{A}_{G^{S}}\triangleq\mathcal{A}_{G\square
G_{s}}=A\otimes I+I\otimes A_{G_{s}}.$ (19)

After substituting Equation 14, we find:

$\displaystyle\mathcal{A}_{G\square G_{s}}=A\otimes I.$ (20)

We note that this is also in line with Proposition 3.2.

As derived in Section 3.2 in the main paper, the connectivity that combines
both Internal and External updates can be given by the Cartesian product of
$G$ with itself, as given in Equation 5.

Global Internal Subgraph Connectivity. Following the literature Zhang et al.
[2023a], Frasca et al. [2022], assuming no self loops, the adjacency matrix
corresponding to the global internal subgraph connectivity is defined as
follows:

$\displaystyle\mathcal{A}^{\text{Global}}_{G}\Big{(}(s,v),(s^{\prime},v^{\prime})\Big{)}=\delta_{ss^{\prime}},$
(21)

where $\delta$ denotes the Kronecker delta.

This matrix results from the Cartesian product of $G_{s}$ and $G_{c}$:

$\displaystyle\mathcal{A}^{\text{Global}}_{G}\triangleq\mathcal{A}_{G_{s}\square
G_{c}}=A_{G_{s}}\otimes I+I\otimes A_{G_{c}}.$ (22)

Substituting Equations 15 and 14, we obtain:

$\displaystyle\mathcal{A}_{G_{s}\square G_{c}}=\vec{0}\vec{0}^{T}\otimes
I+I\otimes(\vec{1}\vec{1}^{T}-I)=I\otimes(\vec{1}\vec{1}^{T}-I).$ (23)

Global External Subgraph Connectivity. Again, assuming no self loops, the
adjacency matrix for global external subgraph connectivity is defined by:

$\displaystyle\mathcal{A}^{\text{Global}}_{G^{S}}\Big{(}(s,v),(s^{\prime},v^{\prime})\Big{)}=\delta_{vv^{\prime}}.$
(24)

This matrix can be obtained from the Cartesian product of $G_{c}$ and $G_{s}$:

$\displaystyle\mathcal{A}^{\text{Global}}_{G^{S}}\triangleq\mathcal{A}_{G_{c}\square
G_{s}}=A_{G_{c}}\otimes I+I\otimes A_{G_{s}}.$ (25)

Upon substituting Equations 15 and 14, we get:

$\displaystyle\mathcal{A}_{G_{s}\square G_{c}}=(\vec{1}\vec{1}^{T}-I)\otimes
I+I\otimes\vec{0}\vec{0}^{T}=(\vec{1}\vec{1}^{T}-I)\otimes I.$ (26)

Analogously to the adjacency that unifies the internal and external
aggregations, we also show that the following Cartesian Graph product results
in a unifying adjacency for the global internal connectivity and the global
external connectivity. This Cartesian product graph is given by $G_{c}\square
G_{c}$, and therefore, its corresponding adjacency is,

$\displaystyle\mathcal{A}_{G_{c}\square G_{c}}=(\vec{1}\vec{1}^{T}-I)\otimes
I+I\otimes(\vec{1}\vec{1}^{T}-I).$ (27)

Table 5: Table summarizing the connection between Cartesian Product Graphs and
Subgraph GNNs.

Connectivity type  | GCP | Adjacency |  Visualization | GCP – unified | Adjacency – unified | Visualization – unified
---|---|---|---|---|---|---
Internal Subgraph Connectivity  | $G_{s}\square G$ | $\mathcal{A}_{G_{s}\square G}\triangleq\mathcal{A}_{G}=I\otimes A$ |  | $G\square G$ | $\mathcal{A}_{G\square G}=A\otimes I+I\otimes A$ |
External Subgraph Connectivity  | $G\square G_{s}$ | $\mathcal{A}_{G\square G_{s}}\triangleq\mathcal{A}_{G^{S}}=A\otimes I$ |
Global Internal Subgraph Connectivity  | $G_{s}\square G_{c}$ | $\mathcal{A}_{G_{s}\square G_{c}}=I\otimes(\vec{1}\vec{1}^{T}-I)$ |  | $G_{c}\square G_{c}$ | $\mathcal{A}_{G_{c}\square G_{c}}=(\vec{1}\vec{1}^{T}-I)\otimes I+I\otimes(\vec{1}\vec{1}^{T}-I)$ |
Global External Subgraph Connectivity  | $G_{c}\square G_{s}$ | $\mathcal{A}_{G_{c}\square G_{s}}=(\vec{1}\vec{1}^{T}-I)\otimes I$ |

##  Appendix B Extending Subgraphormer to any k-tuple

In this section, we extend the formulation of Subgraphormer, which was given
for 2-tuples of nodes, to any $k$-tuple. We start in Section B.1, by
formulating the product graph PE for any $k$-tuple. This sets the required
exposition for Section B.2, where we formulate a SAB update to by applied to
$k$-tuples.

###  B.1 k-tuple Product Graph PE

In this section, we extend the concept of product graph PE to encompass any
$k$-tuple for arbitrary values of $k$. This generalization stems from an
essential observation that arises from the definition of the Cartesian Product
Graph (Definition A.1).

See A.2 In this paper, our primary focus lies on a specific scenario where the
Cartesian Product Graph is applied iteratively to the same graph. For this
purpose, we introduce the Cartesian product operator. This operator, when
applied to an adjacency matrix $A$ of a graph $G$, yields the adjacency matrix
corresponding to $G^{\square^{k}}$ \- the graph resulting from $k$-fold
recursive Cartesian product of $G$ with itself.

######  Definition B.1 (Cartesian Product Operator).

The Cartesian product operator is defined as:

$\mathcal{C}^{k}:\mathbb{R}^{n^{k}\times
n^{k}}\rightarrow\mathbb{R}^{n^{k+1}\times n^{k+1}},$ (28)

applied to an adjacency matrix $A\in\mathbb{R}^{n\times n}$, recursively
defined as:

$\mathcal{C}^{k}(A)=\mathcal{C}^{k-1}(A)\otimes I_{n}+I_{n^{k-1}}\otimes A,$
(29)

with the base case being:

$\mathcal{C}^{1}(A)=A.$ (30)

It is apparent that for a graph $G$ with adjacency matrix $A$, applying the
operator $\mathcal{C}^{2}$ to $A$ results in $\mathcal{C}^{2}(A)=A\otimes
I_{n}+I_{n}\otimes A$, which is the adjacency matrix corresponding to the
Cartesian Product of the graph with itself – Equation 11.

We propose the following proposition regarding the applicability of the
Cartesian operator $\mathcal{C}$ across any power $k$:

######  Proposition B.1 (Adjacency matrix of $G^{\square^{k}}$).

For a graph $G=(A,X)$ with adjacency matrix $A$, the adjacency matrix of
$G^{\square^{k}}$—the graph formed by $k$-fold Cartesian product of $G$ with
itself—is given by:

$\mathcal{A}_{G^{\square^{k}}}=\mathcal{C}^{k}(A).$ (31)

The proof is given in Appendix E.

Utilizing Proposition B.1, we establish that $\mathcal{C}^{k}$ effectively
constructs the adjacency matrix corresponding to the graph $G^{\square^{k}}$.

Notably, this operator functions recursively, therefore, to extend positional
encoding to any $k$-tuple, our goal is to formulate a closed-form expression
for the adjacency matrix of $G^{\square^{k}}$; we first introduce the
necessary definition.

######  Definition B.2 ($\mathcal{A}^{k}_{\mathcal{K}}$).

Given an adjacency matrix $A\in\mathbb{R}^{n\times n}$ and an index
$k\in[\mathcal{K}]$, define $\mathcal{A}^{k}_{\mathcal{K}}$ to be the tensor
resulting from the Cartesian product of $\mathcal{K}$ matrices, where each
matrix is the identity matrix $I_{n}\in\mathbb{R}^{n\times n}$, except for the
$k$-th factor which is $A$. That is,

$\mathcal{A}^{k}_{\mathcal{K}}=I_{n}\otimes I_{n}\otimes\cdots\otimes
A\otimes\cdots\otimes I_{n},$ (32)

where $A$ occupies the $k$-th position in the Cartesian product.

Thus, we propose the following,

######  Proposition B.2 (Adjacency matrix of $G^{\square^{k}}$ – closed form).

Given a graph $G=(A,X)$, with an adjacency matrix $A$, it holds that,

$\mathcal{C}^{\mathcal{K}}(A)=\sum_{k=0}^{\mathcal{K}-1}\mathcal{A}^{k}_{\mathcal{K}}.$
(33)

The proof is given in Appendix E.

Having Proposition B.1 and Proposition B.2, we straight forwardly infer the
following Corollary,

######  Corollary B.1.

For a graph $G=(A,X)$, the adjacency matrix of $G^{\square^{k}}$—the graph
formed by $k$-fold Cartesian product of $G$ with itself—is given by:

$\mathcal{A}_{G^{\square^{\mathcal{K}}}}=\sum_{k=0}^{\mathcal{K}-1}\mathcal{A}^{k}_{\mathcal{K}}.$
(34)

In what follows, we prove that the matrix $\mathcal{A}_{G^{\square^{k}}}$ is a
valid, binary adjacency matrix.

######  Proposition B.3 ($\mathcal{A}_{G^{\square^{k}}}$ – Valid binary
adjacency matrix).

Given a graph $G=(A,X)$ with an adjacency matrix $A$, with no self loops, the
matrix given by,

$\mathcal{A}_{G^{\square^{\mathcal{K}}}}=\sum_{k=0}^{\mathcal{K}-1}\mathcal{A}^{k}_{\mathcal{K}},$
(35)

is a binary adjacency matrix.

The proof is given in Appendix E.

Having developed this closed form expression for the (binary) adjacency matrix
of $G^{\square^{k}}$, we have the following Proposition, which generalizes
Proposition 4.1 to any $k$-tuple,

######  Proposition B.4 ($k$-tuple – Product graph eigendecomposition).

Consider a graph $G=(A,X)$ without self-loops. Define $G^{\square^{k}}$ as the
Cartesian product of $G$ repeated $k$ times, with its adjacency matrix denoted
by $\mathcal{A}_{G^{\square^{k}}}$. The eigenvectors and eigenvalues of the
Laplacian matrix for $G^{\square^{k}}$ can be characterized as follows: for
each set of indices $\\{i_{1},i_{2},\ldots,i_{k}\\}$, where
$i_{j}\in\\{1,2,\ldots,n\\}$ for each $j$, there exists an eigenvector-
eigenvalue pair given by $(v_{i_{1}}\otimes v_{i_{2}}\otimes\ldots\otimes
v_{i_{k}},\lambda_{i_{1}}+\lambda_{i_{2}}+\ldots+\lambda_{i_{k}})$. Here,
$\\{(v_{i},\lambda_{i})\\}_{i=1}^{n}$ represent the eigenvectors and
eigenvalues of the Laplacian matrix of the original graph $G$.

The proof is given in Appendix E.

The above Proposition enables the computation of positional encodings for any
$k$-tuple, offering significantly more efficiency compared to the conventional
method of directly diagonalizing a matrix in $\mathbb{R}^{n^{k}\times n^{k}}$.

######  Theorem B.1 ($k$-tuple PE efficiency).

Consider a graph $G=(A,X)$ without self-loops. Define $G^{\square^{k}}$ as the
Cartesian product of $G$ repeated $k\geq 2$ times.

The time complexity of computing the eigendecomposition of the Laplacian
matrix of $G^{\square^{k}}$ is $\mathcal{O}(n^{2k})$.

The proof is given in Appendix E.

We note that diagonalizing directly the Laplacian matrix of $G^{\square^{k}}$
would instead take $\mathcal{O}(n^{3k})$.

###  B.2 k-tuple SAB

Building upon the derivation of the adjacency matrix obtained from the
Cartesian product of graph $G$ applied recursively $k$ times, as outlined in
Equation 34, we can extend the node update mechanisms, initially
conceptualized for 2-tuples in Section 4.1, to support $k$-tuples.

Generalization of Internal/External updates. We recall the $2$-tuple case,
where the two matrices corresponding the Internal and External aggregations of
Subgraphormer are given in Equation 5. In our new formalism, using the
Cartesian Product Operator, we can write,

$\mathcal{A}_{G\square G}=\mathcal{A}^{0}_{2}+\mathcal{A}^{1}_{2},$ (36)

where $\mathcal{A}^{0}_{2}=\mathcal{A}_{G^{S}}$ and
$\mathcal{A}^{1}_{2}=\mathcal{A}_{G}$. Thus the Internal and External updates
are given as $\\{\mathcal{A}^{0}_{2},\mathcal{A}^{1}_{2}\\}$.

Building on Equation 34, we can extend to a $\mathcal{K}$-tuple scenario where
the “Internal/External” updates correspond to a series of adjacencies, denoted
by $\\{\mathcal{A}^{i}_{\mathcal{K}}\\}_{i=0}^{\mathcal{K}-1}$.

Generalization of Point-wise update. As defined in Section 3, the point-wise
update should allow a node $v$ in subgraph $s$ to have access to the root
representation, where the roots in the case of a $2$-tuple are defined to be,
$\\{(v,v);v\in V\\}$.

While the root nodes in the case of $k$-tuples can be defined as
$\\{(\overbrace{v,\ldots,v}^{\text{$k$ elements}});v\in V\\}$, the
correspondence between nodes and subgraphs is not clear.

Consequently, for a $k$-tuple scenario, we define the point-wise update by
mapping the “subgraph” to a subset of $k-1$ nodes within the tuple, and
designating the “node” as the remaining element in the tuple. Take, for
instance, the tuple $(s_{1},s_{2},\ldots,s_{i},v,s_{i+1},\ldots,s_{k})$: here,
the “subgraph” comprises the indices
$(s_{1},s_{2},\ldots,s_{i},s_{i+1},\ldots,s_{k})$, while the “node” is
represented by $v$.

Accordingly, we establish $k$ such point-wise updates. To be precise, for each
$i\in\\{1,2,\ldots,k\\}$, we define the update as follows:

$\displaystyle\mathcal{A}^{i}_{\text{point}}\big{(}(v_{1},\ldots,v_{k}),(v^{\prime}_{1},\ldots,v^{\prime}_{k})\big{)}=\begin{cases}1&\text{if
}v^{\prime}_{1}=\ldots=v^{\prime}_{k}\text{ and }v^{\prime}_{1}=v_{j}\text{
for all }j\neq i;\\\ 0&\text{otherwise}.\end{cases}$ (37)

This equation defines the function $\mathcal{A}^{i}_{\text{point}}$, which
evaluates the adjacency between two $k$-tuples of vertices,
$(v_{1},\ldots,v_{k})$ and $(v^{\prime}_{1},\ldots,v^{\prime}_{k})$. The
function returns $1$, indicating a specific type of adjacency, if the second
tuple is a root node – all vertices in the second tuple are identical
($v^{\prime}_{1}=v^{\prime}_{2}=\ldots=v^{\prime}_{k}$), and simultaneously,
all vertices in the first tuple match this root node for all indices except
$i$, denoted as $v^{\prime}_{1}=v_{j}$ for all $j\neq i$. In other instances,
where these conditions are not satisfied, the function returns $0$, signifying
the absence of such adjacency.

##  Appendix C Extended Experimental Section

###  C.1 Dataset Description

In this section we overview the eight different datasets considered; this is
summarized in Table 6.

Table 6: Overview of the graph learning datasets.

Dataset | # Graphs | Avg. # nodes | Avg. # edges | Directed | Prediction task | Metric
---|---|---|---|---|---|---
ZINC-12k Sterling and Irwin [2015] | 12,000 | 23.2 | 24.9 | No | Regression | Mean Abs. Error
ZINC-Full Sterling and Irwin [2015] | 249,456 | 23.2 | 49.8 | No | Regression | Mean Abs. Error
Alchemy-12k Chen et al. [2019] | 12,000 | 10.12 | 20.9 | No | 12-task Regression | Mean Abs. Error
ogbg-molhiv Hu et al. [2020] | 41,127 | 25.5 | 27.5 | No | Binary Classification | AUROC
ogbg-molbace Hu et al. [2020] | 1513 | 34.1 | 36.9 | No | Binary Classification | AUROC
ogbg-molesol Hu et al. [2020] | 1,128 | 13.3 | 13.7 | No | Regression | Root Mean Squ. Error
Peptides-func Dwivedi et al. [2022] | 15,535 | 150.9 | 307.3 | No | 10-task Classification | Avg. Precision
Peptides-struct Dwivedi et al. [2022] | 15,535 | 150.9 | 307.3 | No | 11-task Regression | Mean Abs. Error

ZINC-12k and ZINC-Full Datasets Sterling and Irwin [2015], Gómez-Bombarelli et
al. [2018], Dwivedi et al. [2023]. The ZINC-12k dataset comprises 12,000
molecular graphs, extracted from the ZINC database, which is a collection of
commercially available chemical compounds. These molecular graphs vary in
size, ranging from 9 to 37 nodes each. In these graphs, nodes correspond to
heavy atoms, encompassing 28 distinct atom types. Edges in the graphs
represent chemical bonds, with three possible bond types. The primary
objective when using this dataset is to perform regression analysis on the
constrained solubility (logP) of the molecules. The dataset is pre-partitioned
into training, validation, and test sets, containing 10,000, 1,000, and 1,000
molecular graphs, respectively. In its full form, namely, ZINC-Full, it
contains approximately 250,000 molecular graphs. These graphs vary in
complexity, with each graph containing again between 9 to 37 nodes, and 16 to
84 edges. The nodes in these graphs also represent heavy atoms, and the
dataset includes 28 different types of atoms. The edges, on the other hand,
represent bonds between these atoms, and there are 4 distinct types of bonds
in the dataset.

ogbg-molhiv, ogbg-molbace, ogbg-molesol Datasets Hu et al. [2020]. Those
datasets are molecular property prediction datasets, adopted by the Open Graph
Benchmark (OGB) from MoleculeNet. These datasets employ a unified
featurization for nodes (atoms) and edges (bonds), encapsulating various
chemophysical properties.

Alchemy-12k Dataset Chen et al. [2019]. The Alchemy-12k dataset includes
quantum mechanical properties of 12,000 organic molecules containing up to 14
heavy atoms like Carbon (C), Nitrogen (N), Oxygen (O), Fluorine (F), Sulfur
(S), and Chlorine (Cl). These properties were computed using the Python-based
Simulations of Chemistry Framework (PySCF).

Peptides-func and Peptides-struct Datasets Dwivedi et al. [2022]. The
Peptides-func and Peptides-struct datasets consist of atomic graphs
representing peptides. In Peptides-func, the task involves multi-label graph
classification into ten non-exclusive peptide functional classes. Conversely,
Peptides-struct focuses on graph regression to predict eleven three-
dimensional structural properties of the peptides.

###  C.2 Experimental Details

Our experiments were conducted using the PyTorch Paszke et al. [2019] and
PyTorch Geometric Fey and Lenssen [2019] frameworks, using a single NVIDIA L40
GPU, and for every considered experiment, we show the mean $\pm$ std. of 3
runs with different random seeds. Hyperparameter tuning was performed
utilizing the Weight and Biases framework Biewald [2020] – see Section C.4.
All our MLPs feature a single hidden layer equipped with a ReLU non-linearity
function. For the encoding of atom numbers and bonds, we utilized learnable
embeddings indexed by their respective numbers. An exception was made for the
Alchemy-12k dataset, where instead we employed a linear layer, as done in
Morris et al. [2022]. For all our datasets, we used a fixed value of $H=4$
attention heads.

In the case of the ogbg-molhiv, ogbg-molesol, ogbg-molbace, Alchemy-12k
datasets, we follow Frasca et al. [2022], therefore adding a residual
connection between different layers. Additionally, for those datasets, we used
linear layers instead of MLPs inside the GIN layers. Moreover, for these four
datasets, and for the Peptides datasets, the following pooling mechanism was
employed, instead of the one mentioned in Equation 9 (which was used for
ZINC-12k and ZINC-Full),

$\rho(\mathcal{X})=\texttt{MLP}\left(\sum_{s=1}^{n}\left(\frac{1}{n}\sum_{v=1}^{n}\mathcal{X}(s,v)\right)\right).$
(38)

For the Peptides datasets, we also used a residual connection between layers.

###  C.3 Additional Results

Alchemy-12k. The results regarding the Alchemy-12k dataset [Chen et al., 2019]
is summarized in Table 7, showcasing Subgraphormer outperforming Subgraph GNNs
methods.

Table 7: Test results over the Alchemy-12k dataset. Subgraph-based baselines are highlighted in light blue. The top three results are reported as First, Second, and Third. Model | Alchemy-12k
---|---
(MAE $\downarrow$)
GIN Xu et al. [2018] |  $0.180$$\pm 0.006$
SignNet Lim et al. [2022] |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.113}}$$\pm 0.002$
$\delta$-2-GNN Morris et al. [2020] |  $0.118$$\pm 0.001$
$\delta$-2-LGNN Morris et al. [2020] |  $0.122$$\pm 0.003$
SpeqNet Morris et al. [2022] |  $0.115$$\pm 0.001$
GNN-IR Dupty and Lee [2022] |  $0.119$$\pm 0.002$
PF-GNN Dupty et al. [2021] |  ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{0.111}}$$\pm 0.010$
PPGN$++$(6) Puny et al. [2023] |  ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.109}}$$\pm 0.001$
Recon. GNN Cotta et al. [2021] |  $0.125$$\pm 0.001$
DS-GNN (NM) Bevilacqua et al. [2023] |  $0.116$$\pm 0.001$
Subgraphormer |  $0.114$$\pm 0.001$
Subgraphormer + PE |  ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\mathbf{0.113}}$$\pm 0.002$

Stochastic Subgraph Sampling. The comparison of our stochastic sampling
approach against the proposed method by Bevilacqua et al. [2022] over the
Zinc-12k dataset is given in Table 8.

Table 8: Comparison of the stochastic variant of Subgraphormer and Subgraphormer PE to DSS-GNN. Best result for each sampling ratio is in Bold. Model |  | ZINC-12k
---|---|---
| (MAE $\downarrow$)
DSS-GNN (EGO+) Bevilacqua et al. [2022] | 100% |  $0.102$$\pm 0.003$
50% |  $0.155$$\pm 0.007$
20% |  $0.166$$\pm 0.005$
5% |  $0.179$$\pm 0.001$
Subgraphormer | 100% |  $0.067$$\pm 0.007$
50% |  $\mathbf{0.084}$$\pm 0.002$
20% |  $0.121$$\pm 0.007$
5% |  $0.200$$\pm 0.017$
Subgraphormer + PE | 100% |  $\mathbf{0.063}$$\pm 0.0003$
50% |  $\mathbf{0.084}$$\pm 0.002$
20% |  $\mathbf{0.120}$$\pm 0.002$
5% |  $\mathbf{0.175}$$\pm 0.006$

####  C.3.1 Product Graph PE vs Concatenation PE

For completeness, we expand on the other valid choice of subgraph positional
encodings, also introduced in LABEL:{sec:_Subgraph_Positional_Encoding} –
_concatenation PE_ , which is a more general subgraph positional encoding
scheme. Specifically, given the Laplacian matrix of $G$, $L$, and its
eigendecomposition, $L=U^{T}\Lambda U$, we define the _concatenation PE_ for
node $(s,v)$ to be the output of an MLP acting on the concatenation of
$\mathbf{p}_{s}^{:k}\triangleq[U_{s1},\ldots,U_{sk}]$ and
$\mathbf{p}_{v}^{:k}\triangleq[U_{v1},\ldots,U_{vk}]$.

######  Proposition C.1 (_Concatenation PE_ can approximate _product graph
PE_).

The _concatenation PE_ can approximate (up to an ordering) the _product graph
PE_ uniformly.

The proof is given in Appendix E.

Nevertheless, in this paper, we opt for the _product graph PE_ , as it
demonstrates better performance in general. As an example, we provide a
comparison between the _product graph PE_ and the _Concatenation PE_ over the
ZINC-12k dataset in Table 9.

Table 9: A Comparison between different PE variants; including Subgraphormer
alone. Best results are in Bold.

Model | ZINC-12k
---|---
(MAE $\downarrow$)
Subgraphormer |  $0.067$$\pm 0.007$
Subgraphormer + concatenation PE |  $0.071$$\pm 0.003$
Subgraphormer + product graph PE |  $\mathbf{0.063}$$\pm 0.0003$

Notably, Subgraphormer + product graph PE exhibits superior performance.
Interestingly, despite the theoretical capability of concatenation PE to
implement product graph PE (as discussed in Proposition C.1), our empirical
findings reveal that concatenation PE actually reduces the effectiveness of
Subgraphormer.

###  C.4 HyperParameters

In this section, we detail the hyperparameter search conducted for our
experiments. We use the same hyperparameter grid for both Subgraphormer and
Subgraphormer + PE. The hyperparameter search configurations for the full bag
and stochastic bag settings are presented in Tables 10 and 12, respectively.
Additionaly, we report the final selected hyperparameters for Subgraphormer +
PE in both settings in Tables 11 and 13. Notably, in the stochastic bag
setting with sampling ratios of 20% and 5% over the Zinc-12k dataset, our
model failed to converge, leading us to extend the training to 800 epochs.

Optimizers and Schedulers. For the Zinc-12k and Zinc-Full datasets, we employ
the Adam optimizer paired with a ReduceLROnPlateau scheduler (factor set to
0.5, patience at 20, and a minimum learning rate of 0). A similar setup was
used for the Alchemy-12k dataset, except the minimum learning rate which was
set to $1\times 10^{-7}$. For the ogbg-molhiv dataset, we utilized the ASAM
optimizer [Kwon et al., 2021] without a scheduler. For both ogbg-molesol and
ogbg-molbace, we employed a constant learning rate without any scheduler.
Lastly, for the Peptides-func and Peptides-struct datasets, the AdamW
optimizer was chosen in conjunction with a cosine annealing scheduler,
incorporating 10 warmup epochs.

Table 10: Hyperparameters search for Subgraphormer and Subgraphormer + PE in
full bag settings.

Dataset | Num. layers | Learning rate | Embedding size | Epochs | Batch size | Dropout | Num. Eigenvectors
---|---|---|---|---|---|---|---
Zinc-12k | $\\{6\\}$ | $\\{0.001,0.0005,0.0003,0.0001\\}$ | $\\{96\\}$ | $\\{400\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$
Zinc-full | $\\{6\\}$ | $\\{0.001,0.0005,0.0003,0.0001\\}$ | $\\{96\\}$ | $\\{400\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$
molhiv | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molsol | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molbace | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3\\}$ | $\\{0,1,2,8,16\\}$
Alchemy-12k | $\\{5\\}$ | $\\{0.01,0.001\\}$ | $\\{96\\}$ | $\\{400\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$

Table 11: Best hyperparameters for Subgraphormer + PE in full bag settings.

Dataset | Num. layers | Learning rate | Embedding size | Epochs | Batch size | Dropout | Num. Eigenvectors
---|---|---|---|---|---|---|---
Zinc-12k | $6$ | $0.0005$ | $96$ | $400$ | $128$ | $0$ | $8$
Zinc-full | $6$ | $0.0005$ | $96$ | $400$ | $128$ | $0$ | $16$
molhiv | $2$ | $0.1$ | $60$ | $100$ | $32$ | $0.3$ | $8$
molsol | $3$ | $0.001$ | $60$ | $100$ | $32$ | $0.5$ | $2$
molbace | $3$ | $0.001$ | $60$ | $100$ | $32$ | $0.3$ | $16$
Alchemy-12k | $5$ | $0.01$ | $96$ | $400$ | $128$ | $0$ | $16$

Table 12: Hyperparameters search for Subgraphormer and Subgraphormer + PE in
stochastic sampling settings.

Dataset | Sampling Ratio | Num. layers | Learning rate | Embedding size | Epochs | Batch size | Dropout | Num. Eigenvectors
---|---|---|---|---|---|---|---|---
Zinc-12k | 50% | $\\{6\\}$ | $\\{0.001,0.0005,0.0003,0.0001\\}$ | $\\{96\\}$ | $\\{400\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$
molhiv | 50% | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molsol | 50% | $\\{3,6,12\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molbace | 50% | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3\\}$ | $\\{0,1,2,8,16\\}$
Peptides-func | 30% | $\\{5\\}$ | $\\{0.005,0.003,0.001\\}$ | $\\{96\\}$ | $\\{200\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$
Peptides-struct | 30% | $\\{4\\}$ | $\\{0.005,0.003,0.001\\}$ | $\\{96\\}$ | $\\{200\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$
Zinc-12k | 20% | $\\{6\\}$ | $\\{0.001,0.0005,0.0003,0.0001\\}$ | $\\{96\\}$ | $\\{400,800\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$
molhiv | 20% | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molsol | 20% | $\\{3,6,12\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molbace | 20% | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3\\}$ | $\\{0,1,2,8,16\\}$
Zinc-12k | 5% | $\\{6\\}$ | $\\{0.001,0.0005,0.0003,0.0001\\}$ | $\\{96\\}$ | $\\{400,800\\}$ | $\\{128\\}$ | $\\{0\\}$ | $\\{0,1,2,8,16\\}$
molhiv | 5% | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molsol | 5% | $\\{3,6,12\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3,0.5\\}$ | $\\{0,1,2,8,16\\}$
molbace | 5% | $\\{2,3\\}$ | $\\{0.1,0.01,0.001\\}$ | $\\{60\\}$ | $\\{100\\}$ | $\\{32\\}$ | $\\{0.3\\}$ | $\\{0,1,2,8,16\\}$

Table 13: Best hyperparameters for Subgraphormer + PE in stochastic sampling
settings.

Dataset | Sampling Ratio | Num. layers | Learning rate | Embedding size | Epochs | Batch size | Dropout | Num. Eigenvectors
---|---|---|---|---|---|---|---|---
Zinc-12k | 50% | $6$ | $0.0005$ | $96$ | $400$ | $128$ | $0$ | $8$
molhiv | 50% | $2$ | $0.1$ | $60$ | $100$ | $32$ | $0.3$ | $8$
molsol | 50% | $3$ | $0.001$ | $60$ | $100$ | $32$ | $0.5$ | $2$
molbace | 50% | $3$ | $0.001$ | $60$ | $100$ | $32$ | $0.3$ | $8$
Peptides-func | 30% | $5$ | $0.003$ | $96$ | $200$ | $128$ | $0$ | $16$
Peptides-struct | 30% | $4$ | $0.005$ | $96$ | $200$ | $128$ | $0$ | $16$
Zinc-12k | 20% | $6$ | $0.0005$ | $96$ | $800$ | $128$ | $0$ | $8$
molhiv | 20% | $2$ | $0.1$ | $60$ | $100$ | $32$ | $0.3$ | $8$
molsol | 20% | $12$ | $0.001$ | $60$ | $100$ | $32$ | $0.5$ | $1$
molbace | 20% | $3$ | $0.001$ | $60$ | $100$ | $32$ | $0.3$ | $8$
Zinc-12k | 5% | $6$ | $0.0005$ | $96$ | $800$ | $128$ | $0$ | $8$
molhiv | 5% | $2$ | $0.1$ | $60$ | $100$ | $32$ | $0.3$ | $8$
molsol | 5% | $12$ | $0.001$ | $60$ | $100$ | $32$ | $0.5$ | $2$
molbace | 5% | $3$ | $0.001$ | $60$ | $100$ | $32$ | $0.3$ | $2$

##  Appendix D Complexity

This section provides an analysis of the computational complexity associated
with each aggregation method we presented, as illustrated in Sections 3.1, 3.1
and 3.1. Consider a graph $G=(A,X)$; with notes and edges denoted as $V$, $E$,
respectively. Our product graph always encompasses $|V|^{2}$ nodes, and the
number of edges is different for each considered aggregation as follows,

  1. 1.

Internal: For $\mathcal{A}_{G}$, the number of edges is computed by
$\sum_{s\in V}\sum_{v\in V}\big{(}1+d(v)\big{)}$, where $d(v)$ denotes the
degree of vertex $v$ (in the original graph $G$). This simplifies to
$|V|\cdot(|V|+|E|)=|V|^{2}+|V|\cdot|E|$.

  2. 2.

External: Similarly, for $\mathcal{A}_{G^{S}}$, the number of edges is given
by $\sum_{v\in V}\sum_{s\in V}\big{(}1+d(s)\big{)}$, which also simplifies to
$|V|\cdot(|V|+|E|)=|V|^{2}+|V|\cdot|E|$.

  3. 3.

Point: For $\mathcal{A}_{\text{Point}}$, the number of edges is $|V|^{2}$.

The complexities are summarized in Table 14.

Table 14: Complexity analysis of our aggregations. Aggregation Type | Number of edges
---|---
$\mathcal{A}_{G}$ | $\mathcal{O}(|V|^{2}+|V|\cdot|E|)$
$\mathcal{A}_{G^{S}}$ | $\mathcal{O}(|V|^{2}+|V|\cdot|E|)$
$\mathcal{A}_{\text{Point}}$ | $\mathcal{O}(|V|^{2})$

Subgraphormer Complexity. We utilized the GAT convolution for our attention-
based aggregations, as introduced by Veličković et al. [2017]. Given a graph
$G^{\prime}=(A^{\prime},X^{\prime})$ , with nodes and edges denoted as
$V^{\prime}$, $E^{\prime}$, respectively, the time complexity for a single GAT
attention head555The feature dimension is considered a constant. is
$\mathcal{O}(|V^{\prime}|+|E^{\prime}|)$. Thus, the overall complexity depends
on the number of nodes $|V^{\prime}|$ and the number of edges $|E^{\prime}|$
in the graph. Specifically, the product graph we process always has $|V|^{2}$
nodes, while the number of edges are given in Table 14. Thus, SAB exhibits the
complexity of $\mathcal{O}(|V|^{2}+|V|\cdot|E|)$.

As elaborated in Section 4.2, the computational complexity associated with
calculating the product graph PE, which involves $k$ eigenvectors, is
expressed as $\mathcal{O}(k\cdot|V|^{2})$.

Therefore, the total complexity of Subgraphormer is
$\mathcal{O}(k\cdot|V|^{2}+|V|\cdot|E|)$.

Run-time in Seconds. The run-time performance was evaluated on the Zinc-12k
dataset, where the average run-time, calculated over three different seeds,
was 2 hours, 5 minutes, and 24 seconds, with a standard deviation of $\pm$29
seconds. It is important to highlight that the _product graph PE_ computation
can be executed as a preprocessing step. Notably, this process required less
than 10 minutes for the Zinc-12k dataset.

##  Appendix E Proofs

See 3.1

###### Proof.

We consider an unnormalized variant of RGCN, defined as:

$\displaystyle\mathcal{X}^{t+1}$
$\displaystyle=\text{RGCN}^{t}\Big{(}\mathcal{X}^{t},\\{\mathcal{A}_{i}\\}_{i=1}^{M}\Big{)},$
(39)
$\displaystyle\text{RGCN}^{t}\Big{(}\mathcal{X}^{t},\\{\mathcal{A}_{i}\\}_{i=1}^{M}\Big{)}$
$\displaystyle=\mathcal{X}^{t}\mathbf{W}_{0}^{t}+\sum_{i=1}^{M}\mathcal{A}_{i}\mathcal{X}^{t}\mathbf{W}_{i}^{t}.$
(40)

We assume the input features at the first layer, $\mathcal{X}^{t}$, are
provided as 1-hot vectors, and that the parameterized function $f^{t}$, which
is applied in Section 3.1 also outputs 1-hot vectors.

We aim to show that any given layer $t$ of a GNN-SSWL$+$, as per Section 3.1,
can be implemented by this RGCN model. The proof involves the following steps:

  1. 1.

Encode uniquely each of the inputs (individually) to the parameterized
function $f^{t}$ in Section 3.1,

$\mathcal{X}(s,v)^{t},\mathcal{X}(v,v)^{t},\\{\mathcal{X}(s,v^{\prime})^{t}\\}_{v^{\prime}\sim_{G}v},\\{\mathcal{X}(s^{\prime},v)^{t}\\}_{s^{\prime}\sim_{G}s}.$
(41)

  2. 2.

Encode uniquely the input of $f^{t}$ as a whole,

$\big{(}\mathcal{X}(s,v)^{t},\mathcal{X}(v,v)^{t},\\{\mathcal{X}(s,v^{\prime})^{t}\\}_{v^{\prime}\sim_{G}v},\\{\mathcal{X}(s^{\prime},v)^{t}\\}_{s^{\prime}\sim_{G}s}\big{)}.$
(42)

  3. 3.

Implement the parameterized function $f^{t}$.

  4. 4.

Ensure the output features are 1-hot features – to maintain generality across
layers.

Step 1: The unique encoding of the inputs can be achieved as follows:

$\displaystyle\mathcal{X}(s,v)^{t}$
$\displaystyle\rightarrow\mathcal{X}(s,v)^{t},$ (43)
$\displaystyle\mathcal{X}(v,v)^{t}$
$\displaystyle\rightarrow(\mathcal{A}_{\text{point}}\mathcal{X}^{t})~{}(s,v),$
(44) $\displaystyle\\{\mathcal{X}(s,v^{\prime})^{t}\\}_{v^{\prime}\sim_{G}v}$
$\displaystyle\rightarrow(\mathcal{A}_{G}\mathcal{X}^{t})~{}(s,v),$ (45)
$\displaystyle\\{\mathcal{X}(s^{\prime},v)^{t}\\}_{s^{\prime}\sim_{G}s}$
$\displaystyle\rightarrow(\mathcal{A}_{G^{S}}\mathcal{X}^{t})~{}(s,v),$ (46)

For Equations 45 and 46, the right-hand sides effectively count the number of
each element in the set, since the input features are 1-hot vectors. For
Equations 43 and 44, the right hand side is actually equal to the left hand
side.

Step 2: Assuming that $\mathcal{X}\in\mathbb{R}^{n^{2}\times d}$, the RGCN
that uniquely encodes the input of $f^{t}$ as a whole is defined as follows,

$\displaystyle\text{RGCN}^{t}\Big{(}\mathcal{X}^{t},\\{\mathcal{A}_{G},\mathcal{A}_{G^{S}},\mathcal{A}_{\text{point}}\\}\Big{)}$
(47)
$\displaystyle=\mathcal{X}^{t}\mathbf{W}_{0}^{t}+\mathcal{A}_{\text{point}}\mathcal{X}^{t}\mathbf{W}_{\text{point}}^{t}+\mathcal{A}_{G}\mathcal{X}^{t}\mathbf{W}_{G}^{t}+\mathcal{A}_{G^{S}}\mathcal{X}^{t}\mathbf{W}_{G^{S}}^{t},$

where the weight matrices are defined as:

$\displaystyle\mathbf{W}_{0}^{t}$ $\displaystyle=\begin{pmatrix}I_{d\times
d}&0_{d\times d}&0_{d\times d}&0_{d\times d}\end{pmatrix},$ (48)
$\displaystyle\mathbf{W}_{\text{point}}^{t}$
$\displaystyle=\begin{pmatrix}0_{d\times d}&I_{d\times d}&0_{d\times
d}&0_{d\times d}\end{pmatrix},$ (49) $\displaystyle\mathbf{W}_{G}^{t}$
$\displaystyle=\begin{pmatrix}0_{d\times d}&0_{d\times d}&I_{d\times
d}&0_{d\times d}\end{pmatrix},$ (50) $\displaystyle\mathbf{W}_{G^{S}}^{t}$
$\displaystyle=\begin{pmatrix}0_{d\times d}&0_{d\times d}&0_{d\times
d}&I_{d\times d}\end{pmatrix},$ (51)

More specifically, it holds that,

$\displaystyle\mathcal{X}^{t}\mathbf{W}_{0}^{t}$
$\displaystyle=\begin{pmatrix}\mathcal{X}^{t}&0_{d\times d}&0_{d\times
d}&0_{d\times d}\end{pmatrix},$ (52)
$\displaystyle\mathcal{A}_{\text{point}}\mathcal{X}^{t}\mathbf{W}_{\text{point}}^{t}$
$\displaystyle=\begin{pmatrix}0_{d\times
d}&\mathcal{A}_{\text{point}}\mathcal{X}^{t}&0_{d\times d}&0_{d\times
d}.\end{pmatrix},$ (53)
$\displaystyle\mathcal{A}_{G}\mathcal{X}^{t}\mathbf{W}_{G}^{t}$
$\displaystyle=\begin{pmatrix}0_{d\times d}&0_{d\times
d}&\mathcal{A}_{G}\mathcal{X}^{t}&0_{d\times d}\end{pmatrix},$ (54)
$\displaystyle\mathcal{A}_{G^{S}}\mathcal{X}^{t}\mathbf{W}_{G^{S}}^{t}$
$\displaystyle=\begin{pmatrix}0_{d\times d}&0_{d\times d}&0_{d\times
d}&\mathcal{A}_{G^{S}}\mathcal{X}^{t}\end{pmatrix}.$ (55)

Thus, since RGCN is the sum of those, it holds that,

$\displaystyle\text{RGCN}^{t}\Big{(}\mathcal{X}^{t},\\{\mathcal{A}_{G},\mathcal{A}_{G^{S}},\mathcal{A}_{\text{point}}\\}\Big{)}$
$\displaystyle=\begin{pmatrix}\mathcal{X}^{t}&\mathcal{A}_{\text{point}}\mathcal{X}^{t}&\mathcal{A}_{G}\mathcal{X}^{t}&\mathcal{A}_{G^{S}}\mathcal{X}^{t}\end{pmatrix}.$

This concatenation is a unique encoding of the input for $f^{t}$.

Step 3: To prove this step, we start with the following theorem from Yun et
al. [2019] about the memorization power of ReLU networks:

######  Theorem E.1.

Consider a dataset
$\\{x_{i},y_{i}\\}_{i=1}^{N}\in\mathbb{R}^{d}\times\mathbb{R}^{d_{y}}$, with
each $x_{i}$ being distinct and every $y_{i}\in\\{0,1\\}^{d_{y}}$, for all
$i$. There exists a 4-layer fully connected ReLU neural network
$f_{\theta}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d_{y}}$ that perfectly maps
each $x_{i}$ to its corresponding $y_{i}$, i.e., $f_{\theta}(x_{i})=y_{i}$ for
all $i$.

Employing this theorem, we define the $x_{i}$s as all possible (distinct) rows
derived from the output of Step 2, represented as:

$\displaystyle\begin{pmatrix}\mathcal{X}^{t}&\mathcal{A}_{\text{point}}\mathcal{X}^{t}&\mathcal{A}_{G}\mathcal{X}^{t}&\mathcal{A}_{G^{S}}\mathcal{X}^{t}\end{pmatrix},$

with each corresponding $y_{i}$ being the output of the parameterized function
$f^{t}$ over the original input that is represented by this $x_{i}$. Given the
finite nature of our graph set, the input set is also finite, i.e., $N$ is
finite.

Hence, in light of Theorem E.1, a 4-layer fully connected ReLU neural network
capable of implementing $f^{t}$ exists. This network can be equivalently
realized using four layers of RGCN. Specifically, by setting
$\\{\mathbf{W}^{t}_{i}\\}_{{i=1}^{M}}$ to zero and utilizing only
$\mathbf{W}^{t}_{0}$ for $t\in\\{0,1,2,3\\}$, we effectively mimic the
operation of this 4-layer fully connected ReLU network.

Step 4: Finally, employing this same logic, we can again use Theorem E.1 and
map those outputs of step 3 back to 1-hot vectors. ∎

See 3.2

###### Proof.

Without loss of generality, consider the matrix $(I\otimes A)$ indexed at
$\big{(}(s,v),(s^{\prime},v^{\prime})\big{)}$, we have,

$(I\otimes A)\big{(}(s,v),(s^{\prime},v^{\prime})\big{)}\triangleq
I(s,s^{\prime})\cdot A(v,v^{\prime}).$ (56)

In this context, edges exist if and only if $s=s^{\prime}$ and $v,v^{\prime}$
are neighbors in the original graph $G$. This is in direct correspondence with
the definition of $\mathcal{A}_{G}$, as outlined in Equation 2. The proof for
$A\otimes I=\mathcal{A}_{G^{S}}$ follows a similar line of reasoning. ∎

See 4.1

###### Proof.

By definition,

$\mathcal{L}_{G\square G}=\mathcal{D}_{G\square G}-\mathcal{A}_{G\square G},$
(57)

where $\mathcal{D}_{G\square G}$ is defined as

$\mathcal{D}_{G\square G}\triangleq\operatorname{diag}(\mathcal{A}_{G\square
G}\vec{1}_{n^{2}}),$ (58)

and recalling Equation 12,

$\mathcal{D}_{G\square G}=\operatorname{diag}\Big{(}(A\otimes I+I\otimes
A)\vec{1}_{n^{2}}\Big{)}.$ (59)

Using tensor product rules, we have,

$\displaystyle\mathcal{D}_{G\square G}$
$\displaystyle\triangleq\operatorname{diag}\Big{(}A\otimes I+I\otimes
A)\vec{1}_{n^{2}}\Big{)}$ $\displaystyle=\operatorname{diag}\Big{(}A\otimes
I+I\otimes A)(\vec{1}_{n}\otimes\vec{1}_{n})\Big{)}$
$\displaystyle=\operatorname{diag}\Big{(}A\vec{1}_{n}\otimes
I\vec{1}_{n}+I\vec{1}_{n}\otimes A\vec{1}_{n}\Big{)}$ $\displaystyle=D\otimes
I+I\otimes D,$ (60)

where $D=A\vec{1}_{n}$.

Substituting Equation 60 and Equation 12 in Equation 57 we have,

$\mathcal{L}_{G\square G}=D\otimes I+I\otimes D-A\otimes I+I\otimes A.$ (61)

Therefore,

$\displaystyle\mathcal{L}_{G\square G}$ $\displaystyle=D-A\otimes I+I\otimes
D-A$ $\displaystyle=L\otimes I+I\otimes L.$ (62)

Thus, the eigenspace of $\mathcal{L}_{G\square G}$ is given by
$\\{(v_{i}\otimes v_{j},\lambda_{i}+\lambda_{j})\\}_{i,j=1}^{n^{2}}$. ∎

See A.1

###### Proof.

The proof stems directly from the arguments established in Proposition 4.1,
which states that the computation of the eigendecomposition of
$\mathcal{L}_{G\square G}$ primarily involves diagonalizing the Laplacian
matrix of the original graph $G$, which incurs a computational cost of
$\mathcal{O}(n^{3})$. Additionally, to obtain the complete set of $n^{2}$
eigenvectors for the graph $G\square G$, an extra $\mathcal{O}(n^{4})$
operations are necessary, resulting in a total complexity of
$\mathcal{O}(n^{4})$.

It is important to note that when the objective is to compute only $k$
eigenvectors, where $k\leq n$, the computational complexity is reduced to
$\mathcal{O}(k\cdot n^{2})$, since in this case we only need to obtain $k$
eigenvectors. This is congruent with the complexity involved in calculating
the same number of eigenvectors for the original graph $G$, which is also
$\mathcal{O}(k\cdot n^{2})$, for example by applying the Lanczos Algorithm
[Lanczos, 1950] or the Implicitly Restarted Arnoldi Methods [Lehoucq et al.,
1998, Lee et al., 2009], as done by widely used libraries such as Scipy
[Virtanen et al., 2020]. Therefore, our approach offers a computational
advantage in scenarios where a subset of eigenvectors ($k\leq n$) suffices;
which consist of most cases in practice. ∎

See B.1

###### Proof.

The proof proceeds by induction.

Base Case: For $k=2$, we must show that
$\mathcal{A}_{G^{\square^{2}}}\triangleq\mathcal{C}^{2}(A)$.

From Corollary A.1, we have:

$\mathcal{A}_{G^{\square^{2}}}\triangleq\mathcal{A}_{G\square G}=A\otimes
I_{n}+I_{n}\otimes A.$ (63)

Using Equation 29 and Equation 30, we get:

$\mathcal{C}^{2}(A)=\mathcal{C}^{1}(A)\otimes I_{n}+I_{n}\otimes A=A\otimes
I_{n}+I_{n}\otimes A.$ (64)

Thus, from Equation 63 and Equation 64 we obtain,

$\mathcal{A}_{G^{\square^{2}}}=\mathcal{C}^{2}(A),$ (65)

this verifies the base case.

Inductive Assumption: Assume the proposition holds for some integer $k$, i.e.,

$\mathcal{A}_{G^{\square^{k}}}\triangleq\mathcal{C}^{k}(A),$ (66)

then we must demonstrate its validity for $k+1$:

$\mathcal{A}_{G^{\square^{k+1}}}\triangleq\mathcal{C}^{k+1}(A).$ (67)

Inductive Step: Let $G_{1}=G^{\square^{k}}$ and $G_{2}=G$. Given that $G$ has
$n$ nodes, $G_{1}$ has $n^{k}$ nodes, and $G_{2}$ has $n$ nodes. Recalling
Equation 16, we deduce:

$\mathcal{A}_{G^{\square^{k+1}}}=\mathcal{A}_{G^{\square^{k}}\square
G}=\mathcal{A}_{G_{1}\square G_{2}}=\mathcal{A}_{G^{\square^{k}}}\otimes
I_{n}+I_{n^{k}}\otimes A,$ (68)

where $\mathcal{A}_{G^{\square^{k}}}$ is the adjacency of $G_{1}$ and $A$ is
the adjacency of $G_{2}$.

Applying the inductive assumption from Equation 66 to Equation 68, we obtain:

$\mathcal{A}_{G_{1}\square G_{2}}=\mathcal{C}^{k}(A)\otimes
I_{n}+I_{n^{k}}\otimes A.$ (69)

The right-hand side of Equation 69 corresponds exactly to the definition of
$\mathcal{C}^{k+1}$ as specified in Equation 29.

Hence, we conclude that:

$\mathcal{A}_{G^{\square^{k+1}}}=\mathcal{A}_{G^{\square^{k}}\square
G}=\mathcal{A}_{G_{1}\square G_{2}}=\mathcal{C}^{k+1}(A).$ (70)

This concludes the proof. ∎

See B.2

###### Proof.

We will prove by induction.

Base Case: The base case, for $\mathcal{K}=2$, is obtained straight-forwardly
from the definition of $\mathcal{A}^{k}_{\mathcal{K}}$, recalling Equation 32.
Formally, by the definition of $\mathcal{C}^{k}$ – Definition B.1, we have,

$\mathcal{C}^{2}(A)=A\otimes I_{n}+I_{n}\otimes A.$ (71)

We note that,

$\displaystyle\mathcal{A}^{0}_{2}$ $\displaystyle=A\otimes I_{n},$ (72)
$\displaystyle\mathcal{A}^{1}_{2}$ $\displaystyle=I_{n}\otimes A,$ (73)

thus, it holds that,

$\displaystyle\mathcal{C}^{2}(A)$ $\displaystyle=A\otimes I_{n}+I_{n}\otimes
A$ $\displaystyle=\mathcal{A}^{0}_{2}+\mathcal{A}^{1}_{2}$
$\displaystyle=\sum_{k=0}^{1}\mathcal{A}^{k}_{2},$ (74)

which completes the base case.

Inductive Assumption: Assume the proposition holds for some integer
$\mathcal{K}$, i.e.,

$\mathcal{C}^{\mathcal{K}}(A)=\sum_{k=0}^{\mathcal{K}-1}\mathcal{A}^{k}_{\mathcal{K}},$
(75)

then we must demonstrate its validity for $\mathcal{K}+1$:

$\mathcal{C}^{\mathcal{K}+1}(A)=\sum_{k=0}^{\mathcal{K}}\mathcal{A}^{k}_{\mathcal{K}+1}.$
(76)

Inductive Step: By the definition of the Cartesian operator – Definition B.1,
it holds that,

$\mathcal{C}^{\mathcal{K}+1}(A)=\mathcal{C}^{\mathcal{K}}(A)\otimes
I_{n}+I_{n^{\mathcal{K}}}\otimes A.$ (77)

Substituting Equation 75 to Equation 77 we obtain,

$\mathcal{C}^{\mathcal{K}+1}(A)=\Big{(}\sum_{k=0}^{\mathcal{K}-1}\mathcal{A}^{k}_{\mathcal{K}}\Big{)}\otimes
I_{n}+I_{n^{\mathcal{K}}}\otimes A.$ (78)

Since the tensor product operator, $\otimes$, is linear, and recalling the
definition of Equation 32 it holds that,

$\displaystyle\mathcal{C}^{\mathcal{K}+1}(A)$
$\displaystyle=\Big{(}\sum_{k=0}^{\mathcal{K}-1}\overbrace{\mathcal{A}^{k}_{\mathcal{K}}\otimes
I_{n}}^{\triangleq\mathcal{A}^{k}_{\mathcal{K}+1}}\Big{)}+\overbrace{\triangleq
I_{n^{\mathcal{K}}}\otimes
A}^{\triangleq\mathcal{A}^{\mathcal{K}}_{\mathcal{K}+1}}$
$\displaystyle=\sum_{k=0}^{\mathcal{K}-1}\mathcal{A}^{k}_{\mathcal{K}+1}+\mathcal{A}^{\mathcal{K}}_{\mathcal{K}+1}$
$\displaystyle=\sum_{k=0}^{\mathcal{K}}\mathcal{A}^{k}_{\mathcal{K}+1}.$ (79)

This completes the proof. ∎

See B.3

###### Proof.

Since for any $k$ the matrix given by $\mathcal{A}^{k}_{\mathcal{K}}$ is
binary, it is sufficient to show that given $k,k^{\prime}$, such that $k\neq
k^{\prime}$, it holds that,

$\langle\mathcal{A}^{k}_{\mathcal{K}},\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\rangle_{F}=0,$
(80)

where by $\langle\cdot,\cdot\rangle_{F}$ we denote the Frobenius inner
product.

Recalling Definition B.2, we have,

$\displaystyle\langle\mathcal{A}^{k}_{\mathcal{K}},\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\rangle_{F}$
$\displaystyle=\left\langle I\otimes I\otimes\cdots\otimes
A\otimes\cdots\otimes I,I\otimes\cdots\otimes A\otimes\cdots\otimes I\otimes
I\right\rangle_{F}$ $\displaystyle=\text{Tr}\bigg{(}(I\otimes
I\otimes\cdots\otimes A\otimes\cdots\otimes I)\cdot(I\otimes\cdots\otimes
A\otimes\cdots\otimes I\otimes I)^{T}\bigg{)}$
$\displaystyle=\text{Tr}\bigg{(}(I\otimes I\otimes\cdots\otimes
A\otimes\cdots\otimes I)\cdot(I^{T}\otimes\cdots\otimes
A^{T}\otimes\cdots\otimes I^{T}\otimes I^{T})\bigg{)}$

Using the the fact that $k\neq k^{\prime}$, we obtain that,

$\displaystyle\langle\mathcal{A}^{k}_{\mathcal{K}},\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\rangle_{F}$
$\displaystyle=\text{Tr}\bigg{(}II^{T}\otimes\cdots\otimes
II^{T}\otimes\cdots\otimes II^{T}\otimes AI^{T}\otimes
II^{T}\otimes\cdots\otimes II^{T}\otimes IA^{T}\otimes
II^{T}\otimes\cdots\otimes II^{T}\bigg{)}$
$\displaystyle=\text{Tr}\big{(}II^{T}\big{)}\cdot\text{Tr}\big{(}II^{T}\big{)}\cdot\ldots\cdot\text{Tr}\big{(}AI^{T}\big{)}\cdot\text{Tr}\big{(}II^{T}\big{)}\cdot\ldots\cdot\text{Tr}\big{(}II^{T}\big{)}\cdot\text{Tr}\big{(}IA^{T}\big{)}\cdot\text{Tr}\big{(}II^{T}\big{)}\cdot\ldots\cdot\text{Tr}\big{(}II^{T}\big{)}.$

Since we assume no self loops in the original graph $G$, we know that the
diagonal of $A$ and $A^{T}$ is zero, therefore, the Trace of both $AI^{T}$ and
$IA^{T}$ is zero. Thus, for any $k\neq k^{\prime}$, it holds that,

$\langle\mathcal{A}^{k}_{\mathcal{K}},\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\rangle_{F}=0.$
(81)

∎

See B.4

###### Proof.

We are looking for the eigenvectors of $L_{G^{\square^{k}}}$, defined as

$L_{G^{\square^{k}}}=D_{G^{\square^{k}}}-\mathcal{A}_{G^{\square^{k}}},$ (82)

where $D_{G^{\square^{k}}}$ can be written as

$\displaystyle D_{G^{\square^{k}}}$
$\displaystyle\triangleq\operatorname{diag}{(\mathcal{A}_{G^{\square^{k}}}\vec{1}_{n^{k}})}$
$\displaystyle=\operatorname{diag}{\Bigg{(}\sum_{k^{\prime}=0}^{\mathcal{K}-1}\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\vec{1}_{n^{k}}\Bigg{)}}$
$\displaystyle=\sum_{k^{\prime}=0}^{\mathcal{K}-1}\operatorname{diag}{\Bigg{(}\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\vec{1}_{n^{k}}\Bigg{)}},$
(83)

where the last equality is obtained from the linearity of the
$\operatorname{diag}$ operator.

Recalling Definition B.2, for a given $k^{\prime}$, it holds that,

$\displaystyle\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\vec{1}_{n^{k}}$
$\displaystyle=(I_{n}\otimes I_{n}\otimes\ldots\otimes I_{n}\otimes A\otimes
I_{n}\otimes\ldots\otimes
I_{n})\cdot(\vec{1}_{n}\otimes\vec{1}_{n}\otimes\ldots\otimes\vec{1}_{n})$
$\displaystyle=I_{n}\vec{1}_{n}\otimes I_{n}\vec{1}_{n}\otimes\ldots
I_{n}\vec{1}_{n}\otimes A\vec{1}_{n}\otimes I_{n}\vec{1}_{n}\otimes\ldots
I_{n}\vec{1}_{n}$
$\displaystyle=\vec{1}_{n}\otimes\vec{1}_{n}\otimes\ldots\vec{1}_{n}\otimes
A\vec{1}_{n}\otimes\vec{1}_{n}\otimes\ldots\otimes\vec{1}_{n}.$

Since the degree matrix $D$ of the original graph $G$ satisfies
$D=\operatorname{diag}{A\vec{1}_{n}}$ we obtain,

$\operatorname{diag}{\bigg{(}\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\vec{1}_{n^{k}}\bigg{)}}=I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n}\otimes D\otimes I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n}.$ (84)

For simplicity, we will extend Definition B.2 to any calligraphic matrix;
i.e., we define,

$\mathcal{D}^{k^{\prime}}_{\mathcal{K}}\triangleq I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n}\otimes D\otimes I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n},$ (85)

such that the matrix $D$ occupies the $k^{\prime}$-th slot.

Substituting Equation 85 and Equation 84 to Appendix E, we obtain,

$D_{G^{\square^{k}}}=\sum_{k^{\prime}=0}^{\mathcal{K}-1}\mathcal{D}^{k^{\prime}}_{\mathcal{K}}.$
(86)

Plugging Equation 86 and Equation 34 to Equation 82,

$L_{G^{\square^{k}}}=\sum_{k^{\prime}=0}^{\mathcal{K}-1}\bigg{(}\mathcal{D}^{k^{\prime}}_{\mathcal{K}}-\mathcal{A}^{k^{\prime}}_{\mathcal{K}}\bigg{)}.$
(87)

For a given $k^{\prime}$, recalling Definition B.2 and Equation 85 it holds
that,

$\displaystyle\mathcal{D}^{k^{\prime}}_{\mathcal{K}}-\mathcal{A}^{k^{\prime}}_{\mathcal{K}}$
$\displaystyle\triangleq I_{n}\otimes I_{n}\otimes\ldots\otimes I_{n}\otimes
D\otimes I_{n}\otimes I_{n}\otimes\ldots\otimes I_{n}-I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n}\otimes A\otimes I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n}$ $\displaystyle=I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n}\otimes L\otimes I_{n}\otimes
I_{n}\otimes\ldots\otimes I_{n}$
$\displaystyle\triangleq\mathcal{L}^{k^{\prime}}_{\mathcal{K}}.$ (88)

Thus,

$L_{G^{\square^{k}}}=\sum_{k^{\prime}=0}^{\mathcal{K}-1}\mathcal{L}^{k^{\prime}}_{\mathcal{K}},$
(89)

which states that the eigenvector-eigenvalue pairs are given by
$(v_{i_{1}}\otimes v_{i_{2}}\otimes\ldots\otimes
v_{i_{k}},\lambda_{i_{1}}+\lambda_{i_{2}}+\ldots+\lambda_{i_{k}})$, for any
$i_{j}\in[n]$, where $j\in[k]$; given that
$\\{(v_{i},\lambda_{i})\\}_{i=1}^{n}$ represents the eigenvectors and
eigenvalues of the Laplacian matrix of the original graph $G$. ∎

See B.1

###### Proof.

We begin by diagonalizing the Laplacian matrix of the graph $G$. This process
requires $\mathcal{O}(n^{3})$ time complexity.

Following this, we utilize the results in Proposition B.4 to determine the
eigenvectors and eigenvalues of the Cartesian power of the graph, denoted as
$G^{\square^{k}}$. The computation of these eigenvectors and their
corresponding eigenvalues requires $\mathcal{O}(n^{2k})$ operations.

Therefore, the overall computational complexity for this procedure is
$\mathcal{O}(n^{2k}+n^{3})$. However, since $k\geq 2$ the dominating term is
$\mathcal{O}(n^{2k})$. Thus, we can conclude that the total complexity is
$\mathcal{O}(n^{2k})$. ∎

See C.1

###### Proof.

The full embedding of a node $v$ in the graph is defined as

$\displaystyle\mathbf{p}_{v}\triangleq[U_{v,0},\ldots,U_{v,n-1}].$ (90)

The function $F^{\text{prod}}:\mathbb{R}^{2n}\rightarrow\mathbb{R}^{n^{2}}$ is
defined as follows:

$\displaystyle
F^{\text{prod}}(\mathbf{p}_{s}\parallel\mathbf{p}_{v})_{i}=\texttt{flatten}(\mathbf{p}_{s}\cdot\mathbf{p}_{v}^{T}).$
(91)

This function is defined over the compact set $[-1,1]^{2n}$, and maps to the
compact set $[-1,1]^{n^{2}}$. Thus is due to the fact that the entries of
$\mathbf{p}_{v^{\prime}}$ for any node $v^{\prime}$ are components of
normalized eigenvectors.

Therefore, the function $F^{\text{prod}}$ is continuous and defined over a
compact set, implying that it can be approximated by a MLP via the Universal
Approximation Theorem Hornik [1991], Cybenko [1989] acting on the input
$(\mathbf{p}_{s}\parallel\mathbf{p}_{v})$. This completes the proof. ∎

##  Appendix F Subgraphormer Figure

We present a detailed figure illustrating the architecture of our
Subgraphormer model – Figure 3. We begin with the construction of the Product
Graph. Subsequently, we apply product graph PE and node-marking, as detailed
in Section 4.2. This step is followed by stacking of $K$ Subgraph Attention
Blocks (see Section 4.1). Finally, the process concludes with the integration
of a pooling layer that returns a graph representation.

Figure 3: A deep overview of Subgraphormer. Given an input graph, the process
begins with the construction of the product graph. This is followed by the
computation of product graph PE, illustrated through varying colors on the
nodes. Node-Marking is then implemented, depicted by black exes on diagonal
nodes. The process continues with the application of $K$ Subgraph Attention
Blocks (SABs), characterized by three distinct connectivities: Internal,
External, and Point. The final stage involves the pooling layer, which
initially aggregates data across the node dimension to form subgraph
representations, and subsequently across the subgraph dimension.