# Graph as Point Set

Xiyuan Wang  Pan Li  Muhan Zhang

###### Abstract

Graph is a fundamental data structure to model interconnections between
entities. Set, on the contrary, stores independent elements. To learn graph
representations, current Graph Neural Networks (GNNs) primarily use message
passing to encode the interconnections. In contrast, this paper introduces a
novel graph-to-set conversion method that bijectively transforms
interconnected nodes into a set of independent points and then uses a set
encoder to learn the graph representation. This conversion method holds dual
significance. Firstly, it enables using set encoders to learn from graphs,
thereby significantly expanding the design space of GNNs. Secondly, for
Transformer, a specific set encoder, we provide a novel and principled
approach to inject graph information losslessly, different from all the
heuristic structural/positional encoding methods adopted in previous graph
transformers. To demonstrate the effectiveness of our approach, we introduce
Point Set Transformer (PST), a transformer architecture that accepts a point
set converted from a graph as input. Theoretically, PST exhibits superior
expressivity for both short-range substructure counting and long-range
shortest path distance tasks compared to existing GNNs. Extensive experiments
further validate PST’s outstanding real-world performance. Besides
Transformer, we also devise a Deepset-based set encoder, which achieves
performance comparable to representative GNNs, affirming the versatility of
our graph-to-set method.

Graph Neural Network

##  1 Introduction

Graph, composed of interconnected nodes, has a wide range of applications and
has been extensively studied. In graph machine learning, a central focus is to
effectively leverage node connections. Various architectures have arisen for
graph tasks, exhibiting significant divergence in their approaches to
utilizing adjacency information.

Two primary paradigms have evolved for encoding adjacency information. The
first paradigm involves message passing between nodes via edges. Notable
methods in this category include Message Passing Neural Network (MPNN) (Gilmer
et al., 2017), a foundational framework for GNNs such as GCN (Kipf & Welling,
2017), GIN (Xu et al., 2019a), and GraphSAGE (Hamilton et al., 2017).
Subgraph-based GNNs (Zhang & Li, 2021; Huang et al., 2023b; Bevilacqua et al.,
2022; Qian et al., 2022; Frasca et al., 2022; Zhao et al., 2022; Zhang et al.,
2023a) select subgraphs from the whole graph and run MPNN within each
subgraph. These models aggregate messages from neighbors to update the central
nodes’ representations. Additionally, Graph Transformers (GTs) integrate
adjacency information into the attention matrix (Mialon et al., 2021; Kreuzer
et al., 2021; Wu et al., 2021; Dwivedi & Bresson, 2020; Ying et al., 2021;
Shirzad et al., 2023) (note that some early GTs have options to not use
adjacency matrix by using only positional encodings, but the performance is
significantly worse (Dwivedi & Bresson, 2020)). Some recent GTs even directly
incorporate message-passing layers into their architectures (Rampásek et al.,
2022; Kim et al., 2021). In summary, this paradigm relies on adjacency
relationships to facilitate information exchange among nodes.

The second paradigm designs permutation-equivariant neural networks that
directly take adjacency matrices as input. This category includes high-order
Weisfeiler-Leman tests (Maron et al., 2019a), invariant graph networks (Maron
et al., 2019b), and relational pooling (Chen et al., 2020). Additionally,
various studies have explored manual feature extraction from the adjacency
matrix, including random walk structural encoding (Dwivedi et al., 2022a; Li
et al., 2020), Laplacian matrix eigenvectors (Wang et al., 2022; Lim et al.,
2023; Huang et al., 2023a), and shortest path distances (Li et al., 2020).
However, these approaches typically serve as data augmentation steps for other
models, rather than constituting an independent paradigm.

Both paradigms heavily rely on adjacency information in graph encoding. In
contrast, this paper explores whether we can give up adjacency matrix in graph
models while achieving competitive performance. As shown in Figure 1, our
innovative graph-to-set method converts interconnected nodes into independent
points, subsequently encoded by a set encoder like Transformer. Leveraging our
symmetric rank decomposition, we break down the augmented adjacency matrix
$A+D$ into $QQ^{T}$, wherein $Q$ is constituted by column-full-rank rows, each
denoting a node coordinate. This representation enables us to express the
presence of edges as inner products of coordinate vectors ($Q_{i}$ and
$Q_{j}$). Consequently, interlinked nodes can be transformed into independent
points and supplementary coordinates without information loss. Theoretically,
two graphs are isomorphic iff the two converted point sets are equal up to an
orthogonal transformation (because for any $QQ^{T}=A+D$, $QR$ is also a
solution where $R$ is any orthogonal matrix). This equivalence empowers us to
encode the set with coordinates in an orthogonal-transformation-equivariant
manner, akin to E(3)-equivariant models designed for 3D geometric deep
learning. Importantly, our approach is versatile, allowing for using any
equivariant set encoder, thereby significantly expanding the design space of
GNNs. Furthermore, for Transformer, a specific set encoder, our method offers
a novel and principled way to inject graph information losslessly. In Appendix
D, we additionally show that it unifies various heuristic
structural/positional encodings in previous GTs, including random walk (Li et
al., 2020; Dwivedi et al., 2023; Rampásek et al., 2022), heat kernel (Mialon
et al., 2021), and resistance distance (Zhang et al., 2023b).

Figure 1: Our method converts the input graph to a point set first and
encoding it with a set encoder. $O(r)$ denotes the set of $r$-dimension
orthogonal transformations.

To instantiate our method, we introduce an orthogonal-transformation-
equivariant Transformer, namely Point Set Transformer (PST), to encode the
point set. PST provably surpasses existing models in long-range and short-
range expressivity. Extensive experiments verify these claims across synthetic
datasets, graph property prediction datasets, and long-range graph benchmarks.
Specifically, PST outperforms all baselines on QM9 (Wu et al., 2017) dataset.
Moreover, our graph-to-set method is not constrained to only one specific set
encoder. We also propose a Deepset (Segol & Lipman, 2020)-based model, which
outperforms comparable to GIN (Xu et al., 2019b) on our datasets.

Differences from eigendecomposition. Note that our graph-to-set method is
distinct from previous approaches that decompose adjacency matrices for
positional encodings (Dwivedi et al., 2023; Wang et al., 2022; Lim et al.,
2023; Bo et al., 2023). The key differences root in that previous methods
primarily relied on eigendecomposition (EVD), whereas our method is based on
symmetric rank decomposition (SRD). Their differences are as follows:

  * •

SRD enables a practical conversion of graph problems into set problems. SRD of
a matrix is unique up to a single orthogonal transformation, while EVD is
unique up to a combination of orthogonal transformations within each
eigenspace. This difference allows SRD-based models to easily maintain
symmetry, ensuring consistent predictions for isomorphic graphs, while EVD-
based methods (Lim et al., 2023) struggle because they need to deal with each
eigenspace individually, making them less suitable for graph-level tasks where
eigenspaces vary between graphs.

  * •

Due to the advantage of SRD, we can utilize set encoder with coordinates to
capture graph structure, thus expanding the design space of GNN. Moreover, our
method provides a principled way to add graph information to Transformers.
Note that previous GTs usually require multiple heuristic encodings together.
Besides node positional encodings, they also use adjacency matrices: Grit (Ma
et al., 2023) and graphit (Mialon et al., 2021) use random walk matrix
(normalized adjacency) as relative positional encoding (RPE). Graph
Transformer (Dwivedi & Bresson, 2020), Graphormer (Ying et al., 2021), and SAN
(Kreuzer et al., 2021) use adjacency matrix as RPE. Dwivedi & Bresson (2020)’s
ablation shows that adjacency is crucial. GPS (Rampásek et al., 2022),
Exphormer (Shirzad et al., 2023), higher-order Transformer (Kim et al., 2021),
and GraphVit/MLP-Mixer (He et al., 2023) even directly incorporate message
passing blocks which use adjacency matrix to guide message passing between
nodes.

In summary, this paper introduces a novel approach to graph representation
learning by converting interconnected graphs into independent points and
subsequently encoding them using an orthogonal-transformation-equivariant set
encoder like our Point Set Transformer. This innovative approach outperforms
existing methods in both long- and short-range tasks, as validated by
comprehensive experiments.

##  2 Preliminary

For a matrix $Z\\!\in\\!{\mathbb{R}}^{a\times b}$, we define
$Z_{i}\\!\in\\!{\mathbb{R}}^{b}$ as the $i$-th row (as a column vector), and
$Z_{ij}\\!\in\\!{\mathbb{R}}$ as its $(i,j)$ element. For a vector
$\Lambda\\!\in\\!{\mathbb{R}}^{a}$,
$\text{diag}(\Lambda)\\!\in\\!{\mathbb{R}}^{a\times a}$ is the diagonal matrix
with $\Lambda$ as its diagonal elements. And for
$S\\!\in\\!{\mathbb{R}}^{a\times a}$,
$\text{diagonal}(S)\\!\in\\!{\mathbb{R}}^{a}$ represents the vector of its
diagonal elements.

Let $\mathcal{G}=(V,E,X)$ denote an undirected graph. Here,
$V=\\{1,2,3,...,n\\}$ is the set of $n$ nodes, $E\subseteq V\times V$ is the
set of edges, and $X\in\mathbb{R}^{n\times d}$ is the node feature matrix,
whose $v$-th row $X_{v}$ is of node $v$. The edge set $E$ can also be
represented using the adjacency matrix $A\in\mathbb{R}^{n\times n}$, where
$A_{uv}$ is $1$ if the edge exists (i.e., $(u,v)\in E$) and $0$ otherwise. A
graph $\mathcal{G}$ can also be represented by the pair $(V,A,X)$ or $(A,X)$.
The degree matrix $D$ is a diagonal matrix with node degree (sum of a row of
matrix $A$) as the diagonal elements.

Given a permutation function
$\pi\\!:\\!\\{1,2,3,...,n\\}\\!\to\\!\\{1,2,3,...,n\\}$, the permuted graph is
$\pi(\mathcal{G})=(\pi(A),\pi(X))$, where $\pi(A)\in\mathbb{R}^{n\times
n},\pi(A)_{\pi(u)\pi(v)}=A_{uv}$, and $\pi(X)\in\mathbb{R}^{n\times
d},\pi(X)_{\pi(v)}=X_{v}$ for all $u,v\in V$. Essentially, the permutation
$\pi$ reindex each node $v$ to $\pi(v)$ while preserving the original graph
structure and node features. Two graphs are isomorphic iff they can be mapped
to each other through a permutation.

######  Definition 2.1.

Graphs $\mathcal{G}_{1}=(A_{1},X_{1})$ and $\mathcal{G}_{2}=(A_{2},X_{2})$ are
isomorphic, denoted as $\mathcal{G}_{1}\simeq\mathcal{G}_{2}$, if there exists
a permutation $\pi$ such that $\pi(A_{1})=A_{2}$ and $\pi(X_{1})=X_{2}$.

Isomorphic graphs can be transformed into each other by merely reindexing
their nodes. In graph tasks, models should assign the same prediction to
isomorphic graphs.

Symmetric Rank Decomposition (SRD). Decomposing an matrix into two full-rank
matrices is well-known (Puntanen et al., 2011). We further show that a
positive semi-definite matrix can be decomposed into a full-rank matrix.

######  Definition 2.2.

(Symmetric Rank Decomposition, SRD) Given a (symmetric) positive semi-definite
matrix $L\in\mathbb{R}^{n\times n}$ of rank $r$, its SRD is
$Q\in\mathbb{R}^{n\times r}$, where $L\\!=\\!QQ^{T}$.

As $L=QQ^{T}$, $rank(Q)\\!=\\!rank(L)\\!=\\!r$, which implies that $Q$ must be
full column rank. Moreover, two SRDs of the same matrix are equal up to an
orthogonal transformation. Let $O(r)$ denote the set of orthogonal matrices in
$\mathbb{R}^{r\times r}$.

######  Proposition 2.3.

Matrices $Q_{1}$ and $Q_{2}$ in $\mathbb{R}^{n\times r}$ are SRD of the same
matrix iff there exists $R\in O(r),Q_{1}=Q_{2}R$.

SRD is closely related to eigendecomposition. Let
$L=U\text{diag}(\Lambda)U^{T}$ denote the eigendecomposition of $L$, where
$\Lambda\\!\in\\!\mathbb{R}^{r}$ is the vector of non-zero eigenvalues, and
$U\\!\in\\!\mathbb{R}^{n\times r}$ is the matrix whose columns are the
corresponding eigenvectors. $Q=U\text{diag}(\Lambda^{1/2})$ yields an SRD of
$L$, where the superscript denotes element-wise square root operation.

##  3 Graph as Point Set

In this section, we present our innovative method for converting graphs into
sets of points. We first show that Symmetric Rank Decomposition (SRD) can
theoretically achieve this transformation: two graphs are isomorphic iff the
sets of coordinates generated by SRD are equal up to orthogonal
transformations. Additionally, we parameterize SRD for better real-world
performance. Proof details are in Appendix A.

###  3.1 Symmetric Rank Decomposition for Coordinates

A natural approach to breaking down the interconnections between nodes is to
decompose the adjacency matrix. While previous methods often used
eigendecomposition outputs as supplementary node features, these features are
not unique. Consequently, models relying on them fail to provide consistent
predictions for isomorphic graphs, ultimately leading to poor generalization.
To address this, we show that Symmetric Rank Decomposition (SRD) can convert
graph-level tasks into set-level tasks with perfect alignment. Since SRD only
applies to positive semi-definite matrices, we use the augmented adjacency
matrix $D+A$, which is always positive semi-definite (proof in Appendix A.2).

######  Theorem 3.1.

Given two graphs $\mathcal{G}=(V,A,X)$ and
$\mathcal{G^{\prime}}=(V^{\prime},A^{\prime},X^{\prime})$ with respective
degree matrices $D$ and $D^{\prime}$, $\mathcal{G}\simeq\mathcal{G^{\prime}}$
iff $\exists R\in O(r),\\{\\!\\!\\{(X_{v},RQ_{v})|\forall v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{(X^{\prime}_{v},Q_{v}^{\prime})|v\in
V^{\prime}\\}\\!\\!\\}$, where $Q$ and $Q^{\prime}$ are the SRD of $D+A$ and
$D^{\prime}+A^{\prime}$ respectively, and $r$ is the rank of $Q$.

In this theorem, the graph $\mathcal{G}=(V,A,X)$ is converted to a set of
points $\\{(X_{v},Q_{v})|v\in V\\}$, where $X_{v}$ is the original node
feature of $v$, and $Q_{v}$, the $v$-th row of SRD of $D+A$, is the
$r$-dimensional coordinate of node $v$. Consequently, two graphs are
isomorphic iff their point sets are equal up to an orthogonal transformation.
Intuitively, we can imagine that the graph is mapped into an $r$-dimensional
space, where each node has a coordinate, and the inner product between two
coordinates represents edge existence. This mapping is not unique, since we
can freely rotate the coordinates through an orthogonal transformation without
changing inner products. This conversion can be loosely likened to the reverse
process of constructing molecular graph from atoms’ 3D coordinates, where
Euclidean distances between atoms determine node connections in the graph.

Leveraging Theorem 3.1, we can convert a graph into a set and employ a set
encoder for encoding it. Our method consistently produces representations for
isomorphic graphs when the encoder is orthogonal transformation-invariant. The
method’s expressivity hinges on the set encoder’s ability to differentiate
non-equal sets, with greater encoder power enhancing overall performance on
graph tasks.

###  3.2 Parameterized Coordinates

In this section, we enhance SRD’s practical performance through
parameterization. As shown in Section 2, SRD can be implemented via
eigendecomposition: $Q=U\text{diag}(\Lambda^{1/2})$, where
$\Lambda\in{\mathbb{R}}^{r}$ denotes non-zero eigenvalues of the decomposed
matrix, and $U\in\mathbb{R}^{n\times r}$ denotes corresponding eigenvectors.
To parameterize SRD, we replace the element-wise square root with a function
$f:{\mathbb{R}}^{r}\to{\mathbb{R}}^{r}$. This alteration further eliminates
the constraint of non-negativity on eigenvalues and enables the use of various
symmetric matrices containing adjacency information to generate coordinates.
Additionally, for model flexibility, the coordinates can include multiple
channels, with each channel corresponding to a distinct eigenvalue function.

######  Definition 3.2.

(Parameterized SRD, PSRD) With a $d$-channel eigenvalue function
$\\!f\\!:\\!{\mathbb{R}}^{r}\\!\to\\!{\mathbb{R}}^{r\times d}\\!$ and an
adjacency function $\mathcal{Z}\\!:\\!{\mathbb{R}}^{n\times
n}\\!\to\\!{\mathbb{R}}^{n\times n}$ producing symmetric matrices, PSRD
coordinate of a graph ${\mathcal{G}}\\!=\\!(V,A,X)$ is
$\mathcal{Q}(\\!\mathcal{Z}(A),f\\!)\\!\in\\!{\mathbb{R}}^{n\times r\times
d}$, whose $i$-th channel is
$Udiag(f_{i}(\Lambda))\\!\in\\!{\mathbb{R}}^{n\times r}$, where
$\Lambda\\!\in\\!{\mathbb{R}}^{r}$, $U\\!\in\\!{\mathbb{R}}^{n\times r}$ are
non-zero eigenvalues and corresponding eigenvectors of $\mathcal{Z}(\\!A\\!)$,
and $f_{i}\\!:\\!{\mathbb{R}}^{r}\\!\to\\!{\mathbb{R}}^{r}$ is the $i$-th
channel of $f$.

In the definition, $\mathcal{Z}$ maps adjacency matrix to its variants like
Laplacian matrix, and $f$ transforms eigenvalues.
$\mathcal{Q}(\mathcal{Z}(A),f)_{u}\in{\mathbb{R}}^{r\times d}$ is node $u$’s
coordinate. Similar to SRD, PSRD can also convert the graph isomorphism
problems to set equality problems.

######  Theorem 3.3.

Given a permutation-equivariant adjacency function $\mathcal{Z}$, for graphs
${\mathcal{G}}\\!=\\!(V,A,X)$ and
${\mathcal{G}}^{\prime}\\!=\\!(V^{\prime},A^{\prime},X^{\prime})$

  * •

If eigenvalue function $f$ is permutation-equivariant and
${\mathcal{G}}\simeq{\mathcal{G}}^{\prime}$, then two point sets with PSRD
coordinates are equal up to an orthogonal transformation, i.e., $\exists
R\\!\in\\!O(r)$,
$\\{\\!\\!\\{\\!X\\!_{v},\\!R\mathcal{Q}(\mathcal{Z}(\\!A\\!),\\!f)_{v}|v\\!\in\\!V\\!\\}\\!\\!\\}\\!\\!=\\!\\!\\{\\!\\!\\{\\!X\\!_{v}^{\prime},\\!\mathcal{Q}(\mathcal{Z}(\\!A^{\prime}\\!),\\!f)_{v}|v\\!\in\\!V\\!^{\prime}\\!\\}\\!\\!\\}$,
where $r$ is the rank of coordinates.

  * •

If $\mathcal{Z}$ is injective, for all $d\\!\geq\\!2$, there exists a
continuous permutation-equivariant function
$f\\!:\\!{\mathbb{R}}^{r}\\!\to\\!{\mathbb{R}}^{r\times d}$ that if two point
sets with PSRD coordinates are equal up to an orthogonal transformation,
${\mathcal{G}}\simeq{\mathcal{G}}^{\prime}$.

Given permutation equivariant $f$ and $\mathcal{Z}$, the point sets with PSRD
coordinates are equal up to an orthogonal transformation for isomorphic
graphs. Moreover, there exists $f$ making reverse true. Therefore, we can
safely employ permutation-equivariant eigenvalue functions, ensuring
consistent predictions for isomorphic graphs. An expressive eigenvalue
function also allows for the lossless conversion of graph-level tasks into set
problems. In implementation, we utilize DeepSet (Segol & Lipman, 2020) due to
its universal expressivity for permutation-equivariant set functions. Detailed
architecture is shown in Figure 3 in Appendix G.

In summary, we use SRD and its parameterized generalization to decompose the
adjacency matrix or its variants into coordinates. Thus, we transform a graph
into a point set where each point represents a node and includes both the
original node feature and the coordinates as its features.

##  4 Point Set Transformer

Our method, as depicted in Figure 1, comprises two steps: converting the graph
into a set of independent points and encoding the set. Section 3 demonstrates
the bijective transformation of the graph into a set. To encode this point
set, we introduce a novel architecture, Point Set Transformer (PST), designed
to maintain orthogonality invariance and deliver remarkable expressivity.
Additionally, to highlight our method’s versatility, we propose a DeepSet
(Segol & Lipman, 2020)-based set encoder in Appendix K.

PST’s architecture is depicted in Figure 4 in Appendix G. PST operates with
two types of representations for each point: scalars, which remain invariant
to coordinate orthogonal transformations, and vectors, which adapt
equivariantly to coordinate changes. For a point $i$, its scalar
representation is $s_{i}\\!\in\\!{\mathbb{R}}^{d}$, and its vector
representation is $v_{i}\\!\in\\!{\mathbb{R}}^{r\times d}$, where $d$ is the
hidden dimension, and $r$ is the rank of coordinates. $s_{i}$ and $v_{i}$ are
initialized with the input node feature $X_{i}$ and PSRD coordinates (detailed
in Section 3.2) containing graph structure information, respectively.

Similar to conventional transformers, PST comprises multiple layers. Each
layer incorporates two key components:

Scalar-Vector Mixer. This component, akin to the feed-forward network in
Transformer, individually transforms point features. To enable information
exchange between vectors and scalars, we employ the following architecture.

$\displaystyle s_{i}^{\prime}$
$\displaystyle\leftarrow\text{MLP}_{1}(s_{i}\|\text{diagonal}(W_{1}v_{i}^{T}v_{i}W_{2}^{T})),$
(1) $\displaystyle v_{i}^{\prime}$ $\displaystyle\leftarrow
v_{i}\text{diag}(\text{MLP}_{2}(s_{i}))W_{3}+v_{i}W_{4}$ (2)

Here, $W_{1},W_{2},W_{3},$ and $W_{4}\in\mathbb{R}^{d\times d}$ are learnable
matrices for mixing different channels of vector features. Additionally,
$\text{MLP}_{1}:\mathbb{R}^{2d\to d}$ and $\text{MLP}_{2}:\mathbb{R}^{d\to d}$
represent two multi-layer perceptrons transforming scalar representations. The
operation $\text{diagonal}(W_{1}v_{i}^{T}v_{i}W_{2})$ takes the diagonal
elements of a matrix, which translates vectors to scalars, while
$v_{i}\text{diag}(\text{MLP}_{2}(s_{i}))$ transforms scalar features into
vectors. As $v_{i}^{T}R^{T}Rv_{i}=v_{i}^{T}v_{i},\forall R\in O(r)$, the
scalar update is invariant to orthogonal transformations of the coordinates.
Similarly, the vector update is equivariant to $O(r)$.

Attention Layer. Akin to ordinary attention layers, this component compute
pairwise attention score to linearly combine point representations.

$\text{Atten}_{ij}=\text{MLP}((W_{q}^{s}s_{i}\odot
W_{k}^{s}s_{j})\|\text{diagonal}(W_{q}^{v}v_{i}^{T}v_{j}W_{k}^{v}))$ (3)

Here, $W_{q}^{s}$ and $W_{q}^{v}$ denote the linear transformations for
scalars and vectors queries, respectively, while $W_{k}^{s}$ and $W_{k}^{v}$
are for keys. The equation computes the inner products of queries and keys,
similar to standard attention mechanisms. It is easy to see
$\text{Atten}_{ij}$ is also invariant to $O(r)$.

Then we linearly combine point representations with attention scores as the
coefficients:

$s_{i}\leftarrow\sum_{j}\text{Atten}_{ij}s_{j}^{\prime},\quad
v_{i}\leftarrow\sum_{j}\text{Atten}_{ij}v_{j}^{\prime}$ (4)

Each transformer layer is of time complexity $O(n^{2}r)$ and space complexity
$O(n^{2}+nr)$.

Pooling. After several layers, we pool all points’ scalar representations as
the set representation $s$.

$s\leftarrow\text{Pool}(\\{s_{i}|i\in V\\}),$ (5)

where Pool is pooling function like sum, mean, and max.

##  5 Expressivity

In this section, we delve into the theoretical expressivity of our methods.
Our PSRD coordinates and the PST architecture exhibit strong long-range
expressivity, allowing for efficient computation of distance metrics between
nodes, as well as short-range expressivity, enabling the counting of paths and
cycles rooted at each node. Therefore, our model is more expressive than many
existing models, including GIN (equivalent to the 1-WL test) (Xu et al.,
2019b), PPGN (equivalent to the 2-FWL test, more expressive in some cases)
(Maron et al., 2019a), GPS (Rampásek et al., 2022), and Graphormer (Ying et
al., 2021) (two representative graph transformers). More details are in
Appendix B.

###  5.1 Long Range Expressivity

This section demonstrates that the inner products of PSRD coordinates exhibits
strong long-range expressivity, which PST inherits by utilizing inner products
in attention layers.

When assessing a model’s capacity to capture long-range interactions (LRI), a
key measure is its ability to compute shortest path distance (spd) between
nodes. Since formally characterizing LRI can be challenging, we focus on
analyzing models’ performance concerning this specific measure. We observe
that existing models vary significantly in their capacity to calculate spd.
Moreover, we find an intuitive explaination for these differences: spd between
nodes can be expressed as $spd(i,j,A)=\arg\min_{k}\\{k|A^{k}_{ij}>0\\}$, and
the ability to compute $A^{K}$, the $K$-th power of the adjacency matrix $A$,
can serve as a straightforward indicator. Different models need different
number of layers to compute $A^{K}$.

PSRD coordinates. PSRD coordinates can capture arbitrarily large shortest path
distances through their inner products in one step. To illustrate it, we
decompose the adjacency matrix as $A=U\text{diag}(\Lambda)U^{T}$, and employ
coordinates as $U$ and $U\text{diag}(\Lambda^{K})$. Their inner products are
as follows:

$\overbrace{U\text{diag}(\Lambda^{K})U^{T}\rightarrow
A^{K}}^{1~{}~{}\text{step}}$ (6)

######  Theorem 5.1.

There exists permutation-equivariant functions $f_{k},k=0,1,2,...,K$, such
that for all graphs ${\mathcal{G}}=(A,X)$, the shortest path distance between
node $i,j$ is a function of
$\langle\mathcal{Q}(A,f_{0})_{i},\mathcal{Q}(A,f_{k})_{j}\rangle$,
$k\\!=\\!0,1,2,...K$, where $\mathcal{Q}(A,f)$ is the PSRD coordinate defined
in Section 3.2, $K$ is the maximum shortest path distance between nodes.

2-FWL. A powerful graph isomorphic test, 2-Folklore-Weisfeiler-Leman Test
(2-FWL), and its neural network version PPGN (Maron et al., 2019a) produce
node pair representations in a matrix $X\in{\mathbb{R}}^{n\times n}$. $X$ is
initialized with $A$. Each layer updates $X$ with $XX$. So intuitively,
computing $A^{K}$ takes $\lceil\log_{2}K\rceil$ layers.

$\overbrace{A\rightarrow A^{2}\\!\\!=\\!\\!AA\rightarrow
A^{4}\\!\\!=\\!\\!A^{2}A^{2}\rightarrow...\rightarrow
A^{K}\\!\\!=\\!\\!A^{K/2}A^{K/2}}^{\lceil\log_{2}K\rceil~{}~{}\text{layers}}$
(7)

######  Theorem 5.2.

Let $c^{k}({\mathcal{G}})_{ij}$ denote the color of node tuple $(i,j)$ of
graph ${\mathcal{G}}$ at iteration $k$. Given graphs
${\mathcal{G}}\\!=\\!(A,X)$ and
${\mathcal{G}}^{\prime}\\!=\\!(A^{\prime},X^{\prime})$, for all
$K\\!\in\\!{\mathbb{N}}^{+}$, if two node tuples $(i,j)$ in ${\mathcal{G}}$
and $(i^{\prime},j^{\prime})$ in ${\mathcal{G}}^{\prime}$ have
$spd(i,j,A)\\!<\\!spd(i^{\prime},j^{\prime},A^{\prime})\\!\leq\\!2^{K}$, then
$c^{K}({\mathcal{G}})_{ij}\\!\neq\\!c^{K}({\mathcal{G}}^{\prime})_{i^{\prime}j^{\prime}}$.
Moreover, for all $L\\!>\\!2^{K}$, there exists $i,j,i^{\prime},j^{\prime}$,
such that $spd(i,j,A)\\!>\\!spd(i^{\prime},j^{\prime},A^{\prime})\\!\geq\\!L$
while
$c^{K}({\mathcal{G}})_{ij}\\!=\\!c^{K}({\mathcal{G}}^{\prime})_{i^{\prime}j^{\prime}}$.

In other words, $K$ iterations of 2-FWL can distinguish pairs of nodes with
different spds, as long as that distance is at most $2^{K}$. Moreover,
$K$-iteration 2-FWL cannot differentiate all tuples with spd $>2^{K}$ from
other tuples with different spds, which indicates that $K$-iteration 2-FWL is
effective in counting shortest path distances up to a maximum of $2^{K}$.

MPNN. Intuitively, each MPNN layer uses $AX$ to update node representations
$X$. However, this operation in general cannot compute $A^{K}$ unless the
initial node feature $X=I$.

$\overbrace{X\rightarrow AX\rightarrow A^{2}X\\!\\!=\\!\\!AAX\rightarrow...\to
A^{K}X\\!\\!=\\!\\!AA^{K-1}X}^{K~{}~{}\text{layers}}$ (8)

######  Theorem 5.3.

A graph pair exists that MPNN cannot differentiate, but their sets of all-pair
spd are different.

If MPNNs can compute spd between node pairs, they should be able to
distinguish this graph pair from the sets of spd. However, we show no MPNNs
can distinguish the pair, thus proving that MPNNs cannot compute spd.

Graph Transformers (GTs) are known for their strong long-range capacities
(Dwivedi et al., 2022b), as they can aggregate information from the entire
graph to update each node’s representation. However, aggregating information
from the entire graph is not equivalent to capturing the distance between
nodes, and some GTs also fail to compute spd between nodes. Details are in
Appendix C. Note that this slightly counter-intuitive results is because we
take a new perspective to study long range interaction rather than showing GTs
are weak in long range capacity.

Besides shortest path distances, our PSRD coordinates also enables the
unification of various structure encodings (distance metrics between nodes),
including random walk (Li et al., 2020; Dwivedi et al., 2023; Rampásek et al.,
2022), heat kernel (Mialon et al., 2021), resistance distance (Zhang & Li,
2021; Zhang et al., 2023b). Further insights and details are shown in Table 5
in Appendix D.

###  5.2 Short Range Expressitivity

This section shows PST’s expressivity in representative short-range tasks:
path and cycle counting.

######  Theorem 5.4.

A one-layer PST can count paths of length $1$ and $2$, a two-layer PST can
count paths of length $3$ and $4$, and a four-layer PST can count paths of
length $5$ and $6$. Here, “count” means that the $(i,j)$ element of the
attention matrix in the last layer can express the number of paths between
nodes $i$ and $j$.

Therefore, with enough layers, our PST models can count the number of paths of
length $\leq 6$ between nodes. Furthermore, our PST can also count cycles.

######  Theorem 5.5.

A one-layer PST can count cycles of length $3$, a three-layer PST can count
cycles of length $4$ and $5$, and a five-layer PST can count cycles of length
$6$ and $7$. Here, “count” means the representation of node $i$ in the last
layer can express the number of cycles involving node $i$.

Therefore, with enough layers, PST can count the number of cycles of length
$\leq 7$ between nodes. Given that even 2-FWL is restricted to counting cycles
up to length $7$ (Fürer, 2017), the cycle counting power of our Point Set
Transformer is at least on par with 2-FWL.

##  6 Related Work

Graph Neural Network with Eigen-Decomposition. Our approach employs
coordinates derived from the symmetric rank decomposition (SRD) of adjacency
or related matrices, differing from prior studies that primarily rely on
eigendecomposition (EVD). While both approaches have similarities, SRD
transforms the graph isomorphism problem into a set problem bijectively, which
is challenging for EVD, because SRD of a matrix is unique up to a single
orthogonal transformation, while EVD is unique up to multiple orthogonal
transformations in different eigenspaces. This key theoretical difference has
profound implications for model design. Early efforts, like Dwivedi et al.
(2023), introduce eigenvectors into MPNNs’ input node feature (Gilmer et al.,
2017), and subsequent works, such as Graph Transformers (GTs) (Dwivedi &
Bresson, 2020; Kreuzer et al., 2021), incorporate eigenvectors as node
positional encodings. However, due to the non-uniqueness of eigenvectors,
these models produce varying predictions for isomorphic graphs, limiting their
generalization. Lim et al. (2023) partially solve the non-uniqueness problem.
However, their solutions are limited to cases with constant eigenvalue
multiplicity in graph tasks due to the property of EVD. On the other hand,
approaches like Wang et al. (2022), Bo et al. (2023), and Huang et al. (2024)
completely solve non-uniqueness and even apply permutation-equivariant
functions to eigenvalues, similar to our PSRD. However, these methods aim to
enhance existing MPNNs and GTs with heuristic features. In contrast, we
perfectly align graph-level tasks with set-level tasks through SRD, allowing
us to convert orthogonal-transformation-equivariant set encoders to graph
encoders and to inject graph structure information into Transformers in a
principled ways.

Table 1: Normalized MAE ($\downarrow$) on substructure counting tasks. Following Huang et al. (2023b), models can count the structure if the test loss $\leq$ 10 units (yellow cell in the table), measured using a scale of $10^{-3}$. TT: Tailed Triangle. CC: Chordal Cycle, TR: Triangle-Rectangle. Method | 2-Path | 3-Path | 4-Path | 5-path | 6-path | 3-Cycle | 4-Cycle | 5-Cycle | 6-Cycle | 7-cycle | TT | CC | TR
---|---|---|---|---|---|---|---|---|---|---|---|---|---
MPNN | 1.0 | 67.3 | 159.2 | 235.3 | 321.5 | 351.5 | 274.2 | 208.8 | 155.5 | 169.8 | 363.1 | 311.4 | 297.9
IDGNN | 1.9 | 1.8 | 27.3 | 68.6 | 78.3 | 0.6 | 2.2 | 49 | 49.5 | 49.9 | 105.3 | 45.4 | 62.8
NGNN | 1.5 | 2.1 | 24.4 | 75.4 | 82.6 | 0.3 | 1.3 | 40.2 | 43.9 | 52.2 | 104.4 | 39.2 | 72.9
GNNAK | 4.5 | 40.7 | 7.5 | 47.9 | 48.8 | 0.4 | 4.1 | 13.3 | 23.8 | 79.8 | 4.3 | 11.2 | 131.1
I2-GNN | 1.5 | 2.6 | 4.1 | 54.4 | 63.8 | 0.3 | 1.6 | 2.8 | 8.2 | 39.9 | 1.1 | 1.0 | 1.3
PPGN | 0.3 | 1.7 | 4.1 | 15.1 | 21.7 | 0.3 | 0.9 | 3.6 | 7.1 | 27.1 | 2.6 | 1.5 | 14.4
PSDS | $2.2_{\pm 0.1}$ | $2.6_{\pm 0.4}$ | $4.9_{\pm 0.8}$ | $9.9_{\pm 0.5}$ | $15.8_{\pm 0.2}$ | $0.6_{\pm 0.7}$ | $2.2_{\pm 0.3}$ | $5.8_{\pm 0.6}$ | $25.1_{\pm 0.7}$ | $57.7_{\pm 0.3}$ | $6.0_{\pm 1.3}$ | $29.8_{\pm 3.0}$ | $56.4_{\pm 4.7}$
PST | $0.7_{\pm 0.1}$ | $1.1_{\pm 0.1}$ | $1.5_{\pm 0.1}$ | $2.2_{\pm 0.1}$ | $3.3_{\pm 0.3}$ | $0.8_{\pm 0.1}$ | $1.9_{\pm 0.2}$ | $3.1_{\pm 0.3}$ | $4.9_{\pm 0.3}$ | $8.6_{\pm 0.5}$ | $3.0_{\pm 0.1}$ | $4.0_{\pm 0.7}$ | $9.2_{\pm 0.9}$

Equivariant Point Cloud and 3-D Molecule Neural Networks. Equivariant point
cloud and 3-D molecule tasks share resemblances: both involve unordered sets
of 3-D coordinate points as input and require models to produce predictions
invariant/equivariant to orthogonal transformations and translations of
coordinates. Several works (Chen et al., 2021; Winkels & Cohen, 2018; Cohen et
al., 2018; Gasteiger et al., 2021) introduce specialized equivariant
convolution operators to preserve prediction symmetry, yet are later surpassed
by models that learn both invariant and equivariant representations for each
point, transmitting these representations between nodes. Notably, certain
models (Satorras et al., 2021; Schütt et al., 2021; Deng et al., 2021; Wang &
Zhang, 2022) directly utilize vectors mirroring input coordinate changes as
equivariant features, while others (Thomas et al., 2018; Batzner et al., 2022;
Fuchs et al., 2020; Hutchinson et al., 2021; Worrall et al., 2017; Weiler et
al., 2018) incorporate high-order irreducible representations of the
orthogonal group, achieving proven universal expressivity (Dym & Maron, 2021).
Our Point Set Transformer (PST) similarly learns both invariant and
equivariant point representations. However, due to the specific conversion of
point sets from graphs, PST’s architecture varies from existing models. While
translation invariance characterizes point clouds and molecules, graph
properties are sensitive to coordinate translations in our method. Hence, we
adopt inner products of coordinates. Additionally, these prior works center on
3D point spaces, whereas our coordinates exist in high-dimensional space,
rendering existing models and theoretical expressivity results based on high-
order irreducible representations incompatible with our framework.

##  7 Experiments

In our experiments, we evaluate our model across three dimensions:
substructure counting for short-range expressivity, real-world graph property
prediction for practical performance, and Long-Range Graph Benchmarks (Dwivedi
et al., 2022b) to assess long-range interactions. Our primary model, Point Set
Transformer (PST) with PSRD coordinates derived from the Laplacian matrix,
performs well on all tasks. Moreover, our graph-to-set method is adaptable to
various configurations. In ablation study (see Appendix H), another set
encoders Point Set DeepSet (PSDS, introduced in Appendix K), SRD coordinates
different from PSRD, and coordinates decomposed from the adjacency matrix and
normalized adjacency matrix all demonstrate good performance, highlighting the
versatility of our approach. Although PST has higher time complexity compared
to existing Graph Transformers and is slower on large graphs, it shows similar
scalability to our baselines in real-world graph property prediction datasets
(see Appendix I). Our PST uses fewer or comparable parameters than baselines
across all datasets. Dataset details, experiment settings, and hyperparameters
are provided in Appendix E and F.

###  7.1 Graph substructure counting

As Chen et al. (2020) highlight, the ability to count substructures is a
crucial metric for assessing expressivity. We evaluate our model’s
substructure counting capabilities on synthetic graphs following Huang et al.
(2023b). The considered substructures include paths of lengths 2 to 6, cycles
of lengths 3 to 7, and other substructures like tailed triangles (TT), chordal
cycles (CC), and triangle-rectangle (TR). Our task involves predicting the
number of paths originating from each node and the cycles and other
substructures in which each node participates. We compare our Point Set
Transformer (PST) with expressive GNN models, including ID-GNNs (You et al.,
2021), NGNNs (Zhang & Li, 2021), GNNAK+(Zhao et al., 2022), I2-GNN(Huang et
al., 2023b), and PPGN (Maron et al., 2019a). Baseline results are from Huang
et al. (2023b), where uncertainties are unknown.

Results are in Table 1. Following Huang et al. (2023b), a model can count a
substructure if its normalized test Mean Absolute Error (MAE) is below
$10^{-2}$ (10 units in the table). Remarkably, our PST counts all listed
substructures, which aligns with our Theorem 5.4 and Theorem 5.5, while the
second-best model, I2-GNN, counts only 10 out of 13 substructures. PSDS can
also count 8 out of 13 substructures, showcasing the versatility of our graph-
to-set method.

Table 2: MAE ($\downarrow$) on the QM9 dataset. * denotes models with 3D coordinates or features as input. LRP: Deep LRP (Chen et al., 2020). DF: 2-DRFWL(2) GNN (Zhou et al., 2023). 1GNN: 1-GNN. 123: 1-2-3-GNN (Morris et al., 2019). Target | Unit | LRP | NGNN |  I2GNN | DF | PSDS | PST | 1GNN* | DTNN* | 123* | PPGN* | PST*
---|---|---|---|---|---|---|---|---|---|---|---|---
$\mu$ |  $10^{-1}$D | 3.64 | 4.28 | 4.28 | 3.46 | $3.53_{\pm 0.05}$ | $\mathbf{3.19_{\pm 0.04}}$ | 4.93 | 2.44 | 4.76 | 2.31 | $\mathbf{0.23_{\pm 0.01}}$
$\alpha$ |  $10^{-1}$$a_{0}^{3}$ | 2.98 | 2.90 | 2.30 | 2.22 | $2.05_{\pm 0.02}$ | $\mathbf{1.89_{\pm 0.04}}$ | 7.80 | 9.50 | 2.70 | 3.82 | $\mathbf{0.78_{\pm 0.05}}$
$\varepsilon_{\text{homo}}$ |  $10^{-2}$meV | 6.91 | 7.21 | 7.10 | 6.15 | $6.56_{\pm 0.03}$ | $\mathbf{5.98_{\pm 0.09}}$ | 8.73 | 10.56 | 9.17 | 7.51 | $\mathbf{2.98_{\pm 0.08}}$
$\varepsilon_{\text{lumo}}$ |  $10^{-2}$meV | 7.54 | 8.08 | 7.27 | 6.12 | $6.31_{\pm 0.05}$ | $\mathbf{5.84_{\pm 0.08}}$ | 9.66 | 13.93 | 9.55 | 7.81 | $\mathbf{2.20_{\pm 0.07}}$
$\Delta\varepsilon$ |  $10^{-2}$meV | 9.61 | 10.34 | 10.34 | 8.82 | $9.13_{\pm 0.04}$ | $\mathbf{8.46_{\pm 0.07}}$ | 13.33 | 30.48 | 13.06 | 11.05 | $\mathbf{4.47_{\pm 0.09}}$
$R^{2}$ | $a_{0}^{2}$ | 19.30 | 20.50 | 18.64 | 15.04 | $14.35_{\pm 0.02}$ | $\mathbf{13.08_{\pm 0.16}}$ | 34.10 | 17.00 | 22.90 | 16.07 | $\mathbf{0.93_{\pm 0.03}}$
ZPVE |  $10^{-2}$meV | 1.50 | 0.54 | 0.38 | 0.46 | $0.41_{\pm 0.02}$ | $\mathbf{0.39_{\pm 0.01}}$ | 3.37 | 4.68 | 0.52 | 17.42 | $\mathbf{0.26_{\pm 0.01}}$
$U_{0}$ | meV | 11.24 | 8.03 | 5.74 | 4.24 | $3.53_{\pm 0.11}$ | $\mathbf{3.46_{\pm 0.17}}$ | 63.13 | 66.12 | 1.16 | 6.37 | $3.33_{\pm 0.19}$
$U$ | meV | 11.24 | 9.82 | 5.61 | 4.16 | $\mathbf{3.49_{\pm 0.05}}$ | $3.55_{\pm 0.10}$ | 56.60 | 66.12 | 3.02 | 6.37 | $3.26_{\pm 0.05}$
$H$ | meV | 11.24 | 8.30 | 7.32 | 3.95 | $\mathbf{3.47_{\pm 0.04}}$ | $3.49_{\pm 0.20}$ | 60.68 | 66.12 | 1.14 | 6.23 | $3.29_{\pm 0.21}$
$G$ | meV | 11.24 | 13.31 | 7.10 | 4.24 | $3.56_{\pm 0.14}$ | $\mathbf{3.55_{\pm 0.17}}$ | 52.79 | 66.12 | 1.28 | 6.48 | $3.25_{\pm 0.15}$
$C_{v}$ |  $10^{-2}$cal/mol/K | 12.90 | 17.40 | 7.30 | 9.01 | $8.35_{\pm 0.09}$ | $7.77_{\pm 0.15}$ | 27.00 | 243.00 | 9.44 | 18.40 | $\mathbf{3.63_{\pm 0.13}}$

###  7.2 Graph properties prediction

We conduct experiments on four real-world graph datasets: QM9 (Wu et al.,
2017), ZINC, ZINC-full (Gómez-Bombarelli et al., 2016), and ogbg-molhiv (Hu et
al., 2020). PST excels in performance, and PSDS performs comparable to GIN (Xu
et al., 2019a). PST also outperforms all baselines on TU datasets (Ivanov et
al., 2019) (see Appendix J).

For the QM9 dataset, we compare PST with various expressive GNNs, including
models considering Euclidean distances (1-GNN, 1-2-3-GNN (Morris et al.,
2019), DTNN (Wu et al., 2017), PPGN (Maron et al., 2019a)) and those focusing
solely on graph structure (Deep LRP (Chen et al., 2020), NGNN (Zhang & Li,
2021), I2-GNN (Huang et al., 2023b), 2-DRFWL(2) GNN (Zhou et al., 2023)). For
fair comparsion, we introduce two versions of our model: PST without Euclidean
distance (PST) and PST with Euclidean distance (PST*). Results in Table 2 show
PST outperforms all baseline models without Euclidean distance on 11 out of 12
targets, with an average 11% reduction in loss compared to the strongest
baseline, 2-DRFWL(2) GNN. PST* outperforms all Euclidean distance-based
baselines on 8 out of 12 targets, with an average 4% reduction in loss
compared to the strongest baseline, 1-2-3-GNN. Both models rank second in
performance for the remaining targets. PSDS without Euclidean distance also
outperforms baselines on 6 out of 12 targets.

Table 3: Results on graph property prediction tasks. | zinc | zinc-full | molhiv
---|---|---|---
|  MAE$\downarrow$ |  MAE$\downarrow$ |  AUC$\uparrow$
GIN | $0.163_{\pm 0.004}$ | $0.088_{\pm 0.002}$ | $77.07_{\pm 1.49}$
GNN-AK+ | $0.080_{\pm 0.001}$ | – | $79.61_{\pm 1.19}$
ESAN | $0.102_{\pm 0.003}$ | $0.029_{\pm 0.003}$ | $78.25_{\pm 0.98}$
SUN | $0.083_{\pm 0.003}$ | $0.024_{\pm 0.003}$ | $80.03_{\pm 0.55}$
SSWL | $0.083_{\pm 0.003}$ | $\underline{0.022_{\pm 0.002}}$ | $79.58_{\pm 0.35}$
DRFWL | $0.077_{\pm 0.002}$ | $0.025_{\pm 0.003}$ | $78.18_{\pm 2.19}$
CIN | $0.079_{\pm 0.006}$ | $\underline{0.022_{\pm 0.002}}$ | $\mathbf{80.94_{\pm 0.57}}$
NGNN | $0.111_{\pm 0.003}$ | $0.029_{\pm 0.001}$ | $78.34_{\pm 1.86}$
Graphormer | $0.122_{\pm 0.006}$ | $0.052_{\pm 0.005}$ | $\underline{80.51_{\pm 0.53}}$
GPS | $0.070_{\pm 0.004}$ | - | $78.80_{\pm 1.01}$
GMLP-Mixer | $0.077_{\pm 0.003}$ | - | $79.97_{\pm 1.02}$
SAN | $0.139_{\pm 0.006}$ | - | $77.75_{\pm 0.61}$
Specformer | $0.066_{\pm 0.003}$ | - | $78.89_{\pm 1.24}$
SignNet | $0.084_{\pm 0.006}$ | $0.024_{\pm 0.003}$ | -
Grit | $\mathbf{0.059_{\pm 0.002}}$ | $0.024_{\pm 0.003}$ | -
PSDS | $0.162_{\pm 0.007}$ | $0.049_{\pm 0.002}$ | $74.92_{\pm 1.18}$
PST | $\underline{0.063_{\pm 0.003}}$ | $\mathbf{0.018_{\pm 0.001}}$ | $80.32_{\pm 0.71}$

For ZINC, ZINC-full, and ogbg-molhiv datasets, we have conducted an evaluation
of PST and PSDS in comparison to a range of expressive GNNs and graph
transformers (GTs). This set of models includes expressive MPNN and subgraph
GNNs: GIN (Xu et al., 2019b), SUN (Frasca et al., 2022), SSWL (Zhang et al.,
2023a), 2-DRFWL(2) GNN (Zhou et al., 2023), CIN (Bodnar et al., 2021), NGNN
(Zhang & Li, 2021), and GTs: Graphormer (Ying et al., 2021), GPS (Rampásek et
al., 2022), Graph MLP-Mixer (He et al., 2023), Specformer (Bo et al., 2023),
SignNet (Lim et al., 2023), and Grit (Ma et al., 2023). Performance results
for the expressive GNNs are sourced from (Zhou et al., 2023), while those for
the Graph Transformers are extracted from (He et al., 2023; Ma et al., 2023;
Lim et al., 2023). The comprehensive results are presented in Table 3.
Notably, our PST outperforms all baseline models on ZINC-full datasets,
achieving reductions in loss of 18%. On the ogbg-molhiv dataset, our PST also
delivers competitive results, with only CIN and Graphormer surpassing it.
Overall, PST demonstrates exceptional performance across these four diverse
datasets, and PSDS also performs comparable to representative GNNs like GIN
(Xu et al., 2019a).

###  7.3 Long Range Graph Benchmark

To assess the long-range capacity of our Point Set Transformer (PST), we
conducted experiments using the Long Range Graph Benchmark (Dwivedi et al.,
2022b). Following He et al. (2023), we compared our model to a range of
baseline models, including GCN (Kipf & Welling, 2017), GINE (Xu et al.,
2019a), GatedGCN (Bresson & Laurent, 2017), SAN (Kreuzer et al., 2021),
Graphormer (Ying et al., 2021), GMLP-Mixer, Graph ViT (He et al., 2023), and
Grit (Ma et al., 2023). PST outperforms all baselines on the PascalVOC-SP and
Peptides-Func datasets and achieves the third-highest performance on the
Peptides-Struct dataset. PSDS consistently outperforms GCN and GINE. These
results showcase the remarkable long-range interaction capturing abilities of
our methods across various benchmark datasets. Note that a contemporary work
(Tönshoff et al., 2023) points out that even vanilla MPNNs can achieve similar
performance to Graph Transformers on LRGB with better hyperparameters, which
implies that LRGB is not a rigor benchmark. However, for comparison with
previous work, we maintain the original settings on LRGB datasets.

Table 4: Results on Long Range Graph Benchmark. * means using Random Walk Structural Encoding (Dwivedi et al., 2022a), and ** means Laplacian Eigenvector Encoding (Dwivedi et al., 2023).  Model | PascalVOC-SP | Peptides-Func | Peptides-Struct
---|---|---|---
|  F1 score $\uparrow$ |  AP $\uparrow$ |  MAE $\downarrow$
GCN | $0.1268_{\pm 0.0060}$ | $0.5930_{\pm 0.0023}$ | $0.3496_{\pm 0.0013}$
GINE | $0.1265_{\pm 0.0076}$ | $0.5498_{\pm 0.0079}$ | $0.3547_{\pm 0.0045}$
GatedGCN | $0.2873_{\pm 0.0219}$ | $0.5864_{\pm 0.0077}$ | $0.3420_{\pm 0.0013}$
GatedGCN* | $0.2860_{\pm 0.0085}$ | $0.6069_{\pm 0.0035}$ | $0.3357_{\pm 0.0006}$
Transformer** | $0.2694_{\pm 0.0098}$ | $0.6326_{\pm 0.0126}$ | $0.2529_{\pm 0.0016}$
SAN* | $0.3216_{\pm 0.0027}$ | $0.6439_{\pm 0.0075}$ | $0.2545_{\pm 0.0012}$
SAN** | $0.3230_{\pm 0.0039}$ | $0.6384_{\pm 0.0121}$ | $0.2683_{\pm 0.0043}$
GraphGPS | $0.3748_{\pm 0.0109}$ | $0.6535_{\pm 0.0041}$ | $0.2500_{\pm 0.0005}$
Exphormer | $0.3975_{\pm 0.0037}$ | $0.6527_{\pm 0.0043}$ | $0.2481_{\pm 0.0007}$
GMLP-Mixer | - | $0.6970_{\pm 0.0080}$ | $0.2475_{\pm 0.0015}$
Graph ViT | - | $0.6942_{\pm 0.0075}$ | $\mathbf{0.2449_{\pm 0.0016}}$
Grit | - | $\mathbf{0.6988_{\pm 0.0082}}$ | $0.2460_{\pm 0.0012}$
PSDS | $0.2134_{\pm 0.0050}$ | $0.5965_{\pm 0.0064}$ | $0.2621_{\pm 0.0036}$
PST | $\mathbf{0.4010_{\pm 0.0072}}$ | $\mathbf{0.6984_{\pm 0.0051}}$ | $0.2470_{\pm 0.0015}$

##  8 Conclusion

We introduce a novel approach employing symmetric rank decomposition to
transform interconnected nodes in graph into independent points with
coordinates. Additionally, we propose the Point Set Transformer to encode the
point set. Our approach demonstrates remarkable theoretical expressivity and
excels in real-world performance, addressing both short-range and long-range
tasks effectively. It extends the design space of GNN and provides a
principled way to inject graph structural information into Transformers.

##  9 Limitations

PST’s scalability is still constrained by the Transformer architecture. To
overcome this, acceleration techniques such as sparse attention and linear
attention could be explored, which will be our future work.

## Impact Statement

This paper presents work whose goal is to advance the field of graph
representation learning and will improve the design of graph generation and
prediction models. There are many potential societal consequences of our work,
none which we feel must be specifically highlighted here.

## Acknowledgement

Xiyuan Wang and Muhan Zhang are partially supported by the National Key R&D
Program of China (2022ZD0160300), the National Key R&D Program of China
(2021ZD0114702), the National Natural Science Foundation of China (62276003),
and Alibaba Innovative Research Program. Pan Li is supported by the National
Science Foundation award IIS-2239565.

## References

  * Akiba et al. (2019) Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M.  Optuna: A next-generation hyperparameter optimization framework.  In _SIGKDD_ , 2019.
  * Batzner et al. (2022) Batzner, S., Musaelian, A., Sun, L., Geiger, M., Mailoa, J. P., Kornbluth, M., Molinari, N., Smidt, T. E., and Kozinsky, B.  E (3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials.  _Nature communications_ , 13(1):1–11, 2022.
  * Bevilacqua et al. (2022) Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H.  Equivariant subgraph aggregation networks.  In _ICLR_ , 2022.
  * Bo et al. (2023) Bo, D., Shi, C., Wang, L., and Liao, R.  Specformer: Spectral graph neural networks meet transformers.  In _ICLR_ , 2023.
  * Bodnar et al. (2021) Bodnar, C., Frasca, F., Otter, N., Wang, Y., Liò, P., Montúfar, G. F., and Bronstein, M. M.  Weisfeiler and lehman go cellular: CW networks.  In _NeurIPS_ , 2021.
  * Bouritsas et al. (2023) Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M.  Improving graph neural network expressivity via subgraph isomorphism counting.  _TPAMI_ , 45(1), 2023.
  * Bresson & Laurent (2017) Bresson, X. and Laurent, T.  Residual gated graph convnets, 2017.
  * Chen et al. (2021) Chen, H., Liu, S., Chen, W., Li, H., and Jr., R. W. H.  Equivariant point network for 3d point cloud analysis.  In _CVPR_ , 2021.
  * Chen et al. (2020) Chen, Z., Chen, L., Villar, S., and Bruna, J.  Can graph neural networks count substructures?  In _NeurIPS_ , 2020.
  * Cohen et al. (2018) Cohen, T. S., Geiger, M., Köhler, J., and Welling, M.  Spherical cnns.  In _ICLR_ , 2018.
  * Deng et al. (2021) Deng, C., Litany, O., Duan, Y., Poulenard, A., Tagliasacchi, A., and Guibas, L. J.  Vector neurons: A general framework for so(3)-equivariant networks.  In _ICCV_ , 2021.
  * Dwivedi & Bresson (2020) Dwivedi, V. P. and Bresson, X.  A generalization of transformer networks to graphs, 2020.
  * Dwivedi et al. (2022a) Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X.  Graph neural networks with learnable structural and positional representations.  In _ICLR_ , 2022a.
  * Dwivedi et al. (2022b) Dwivedi, V. P., Rampásek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D.  Long range graph benchmark.  In _NeurIPS_ , 2022b.
  * Dwivedi et al. (2023) Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X.  Benchmarking graph neural networks.  _J. Mach. Learn. Res._ , 24:43:1–43:48, 2023.
  * Dym & Maron (2021) Dym, N. and Maron, H.  On the universality of rotation equivariant point cloud networks.  In _ICLR_ , 2021.
  * Feng et al. (2022) Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M.  How powerful are k-hop message passing graph neural networks.  In _NeurIPS_ , 2022.
  * Fey & Lenssen (2019) Fey, M. and Lenssen, J. E.  Fast graph representation learning with pytorch geometric.  _CoRR_ , abs/1903.02428, 2019.
  * Frasca et al. (2022) Frasca, F., Bevilacqua, B., Bronstein, M. M., and Maron, H.  Understanding and extending subgraph gnns by rethinking their symmetries.  In _NeurIPS_ , 2022.
  * Fuchs et al. (2020) Fuchs, F., Worrall, D., Fischer, V., and Welling, M.  Se(3)-transformers: 3d roto-translation equivariant attention networks.  _NeurIPS_ , 2020.
  * Fürer (2017) Fürer, M.  On the combinatorial power of the weisfeiler-lehman algorithm.  In _CIAC_ , volume 10236, pp. 260–271, 2017.
  * Gasteiger et al. (2021) Gasteiger, J., Becker, F., and Günnemann, S.  Gemnet: Universal directional graph neural networks for molecules.  In _NeurIPS_ , 2021.
  * Gilmer et al. (2017) Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E.  Neural message passing for quantum chemistry.  In _ICML_ , 2017.
  * Gómez-Bombarelli et al. (2016) Gómez-Bombarelli, R., Duvenaud, D., Hernández-Lobato, J. M., Aguilera-Iparraguirre, J., Hirzel, T. D., Adams, R. P., and Aspuru-Guzik, A.  Automatic chemical design using a data-driven continuous representation of molecules, 2016.
  * Hamilton et al. (2017) Hamilton, W. L., Ying, Z., and Leskovec, J.  Inductive representation learning on large graphs.  In _NeurIPS_ , 2017.
  * He et al. (2023) He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X.  A generalization of vit/mlp-mixer to graphs.  In _ICML_ , 2023.
  * Hu et al. (2020) Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J.  Open graph benchmark: Datasets for machine learning on graphs.  In _NeurIPS_ , 2020.
  * Huang et al. (2023a) Huang, Y., Lu, W., Robinson, J., Yang, Y., Zhang, M., Jegelka, S., and Li, P.  On the stability of expressive positional encodings for graph neural networks.  _arXiv preprint arXiv:2310.02579_ , 2023a.
  * Huang et al. (2023b) Huang, Y., Peng, X., Ma, J., and Zhang, M.  Boosting the cycle counting power of graph neural networks with i$^2$-gnns.  In _ICLR_ , 2023b.
  * Huang et al. (2024) Huang, Y., Lu, W., Robinson, J., Yang, Y., Zhang, M., Jegelka, S., and Li, P.  On the stability of expressive positional encodings for graph neural networks.  _ICLR_ , 2024.
  * Hutchinson et al. (2021) Hutchinson, M. J., Lan, C. L., Zaidi, S., Dupont, E., Teh, Y. W., and Kim, H.  Lietransformer: Equivariant self-attention for lie groups.  In _ICML_ , 2021.
  * Ivanov et al. (2019) Ivanov, S., Sviridov, S., and Burnaev, E.  Understanding isomorphism bias in graph data sets.  _CoRR_ , abs/1910.12091, 2019.
  * Kim et al. (2021) Kim, J., Oh, S., and Hong, S.  Transformers generalize deepsets and can be extended to graphs & hypergraphs.  In _NeurIPS_ , 2021.
  * Kipf & Welling (2017) Kipf, T. N. and Welling, M.  Semi-supervised classification with graph convolutional networks.  In _ICLR_ , 2017.
  * Kreuzer et al. (2021) Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., and Tossou, P.  Rethinking graph transformers with spectral attention.  In _NeurIPS_ , 2021.
  * Li et al. (2020) Li, P., Wang, Y., Wang, H., and Leskovec, J.  Distance encoding: Design provably more powerful neural networks for graph representation learning.  In _NeurIPS_ , 2020.
  * Lim et al. (2023) Lim, D., Robinson, J. D., Zhao, L., Smidt, T. E., Sra, S., Maron, H., and Jegelka, S.  Sign and basis invariant networks for spectral graph representation learning.  In _ICLR_ , 2023.
  * Ma et al. (2023) Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P. H. S., and Lim, S.  Graph inductive biases in transformers without message passing.  In _ICML_ , 2023.
  * Maron et al. (2019a) Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y.  Provably powerful graph networks.  In _NeurIPS_ , 2019a.
  * Maron et al. (2019b) Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y.  Invariant and equivariant graph networks.  In _IGN_ , 2019b.
  * Mialon et al. (2021) Mialon, G., Chen, D., Selosse, M., and Mairal, J.  Graphit: Encoding graph structure in transformers, 2021.
  * Morris et al. (2019) Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _AAAI_ , 2019.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Köpf, A., Yang, E. Z., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  Pytorch: An imperative style, high-performance deep learning library.  In _NeurIPS_ , pp. 8024–8035, 2019.
  * Perepechko & Voropaev (2009) Perepechko, S. and Voropaev, A.  The number of fixed length cycles in an undirected graph. explicit formulae in case of small lengths.  _MMCP_ , 148, 2009.
  * Puntanen et al. (2011) Puntanen, S., Styan, G. P., and Isotalo, J.  _Matrix tricks for linear statistical models: our personal top twenty_.  Springer, 2011.
  * Qian et al. (2022) Qian, C., Rattan, G., Geerts, F., Niepert, M., and Morris, C.  Ordered subgraph aggregation networks.  In _NeurIPS_ , 2022.
  * Rampásek et al. (2022) Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D.  Recipe for a general, powerful, scalable graph transformer.  In _NeurIPS_ , 2022.
  * Satorras et al. (2021) Satorras, V. G., Hoogeboom, E., and Welling, M.  E (n) equivariant graph neural networks.  In _ICML_ , 2021.
  * Schütt et al. (2021) Schütt, K., Unke, O., and Gastegger, M.  Equivariant message passing for the prediction of tensorial properties and molecular spectra.  In _ICML_ , 2021.
  * Segol & Lipman (2020) Segol, N. and Lipman, Y.  On universal equivariant set networks.  In _ICLR_ , 2020.
  * Shervashidze et al. (2011) Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M.  Weisfeiler-lehman graph kernels.  _JMLR_ , 2011.
  * Shirzad et al. (2023) Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K.  Exphormer: Sparse transformers for graphs.  In _ICML_ , 2023.
  * Thomas et al. (2018) Thomas, N., Smidt, T., Kearnes, S., Yang, L., Li, L., Kohlhoff, K., and Riley, P.  Tensor field networks: Rotation-and translation-equivariant neural networks for 3d point clouds.  _arXiv preprint arXiv:1802.08219_ , 2018.
  * Tönshoff et al. (2023) Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M.  Where did the gap go? reassessing the long-range graph benchmark.  _CoRR_ , abs/2309.00367, 2023.
  * Wang et al. (2022) Wang, H., Yin, H., Zhang, M., and Li, P.  Equivariant and stable positional encoding for more powerful graph neural networks.  In _ICLR_ , 2022.
  * Wang & Zhang (2022) Wang, X. and Zhang, M.  Graph neural network with local frame for molecular potential energy surface.  _LoG_ , 2022.
  * Weiler et al. (2018) Weiler, M., Geiger, M., Welling, M., Boomsma, W., and Cohen, T.  3d steerable cnns: Learning rotationally equivariant features in volumetric data.  In _NeurIPS_ , 2018.
  * Wijesinghe & Wang (2022) Wijesinghe, A. and Wang, Q.  A new perspective on ”how graph neural networks go beyond weisfeiler-lehman?”.  In _ICLR_ , 2022.
  * Winkels & Cohen (2018) Winkels, M. and Cohen, T. S.  3d g-cnns for pulmonary nodule detection, 2018.
  * Worrall et al. (2017) Worrall, D. E., Garbin, S. J., Turmukhambetov, D., and Brostow, G. J.  Harmonic networks: Deep translation and rotation equivariance.  In _CVPR_ , 2017.
  * Wu et al. (2017) Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. S.  Moleculenet: A benchmark for molecular machine learning, 2017.
  * Wu et al. (2021) Wu, Z., Jain, P., Wright, M. A., Mirhoseini, A., Gonzalez, J. E., and Stoica, I.  Representing long-range context for graph neural networks with global attention.  In _NeurIPS_ , 2021.
  * Xu et al. (2019a) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How powerful are graph neural networks?  In _ICLR_ , 2019a.
  * Xu et al. (2019b) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How powerful are graph neural networks?  In _ICLR_ , 2019b.
  * Ying et al. (2021) Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.  Do transformers really perform badly for graph representation?  In _NeurIPS_ , 2021.
  * You et al. (2021) You, J., Selman, J. M. G., Ying, R., and Leskovec, J.  Identity-aware graph neural networks.  In _AAAI_ , 2021.
  * Zhang et al. (2023a) Zhang, B., Feng, G., Du, Y., He, D., and Wang, L.  A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests.  In _ICML_ , 2023a.
  * Zhang et al. (2023b) Zhang, B., Luo, S., Wang, L., and He, D.  Rethinking the expressive power of gnns via graph biconnectivity.  In _ICLR_ , 2023b.
  * Zhang & Li (2021) Zhang, M. and Li, P.  Nested graph neural networks.  In _NeurIPS_ , 2021.
  * Zhang et al. (2018) Zhang, M., Cui, Z., Neumann, M., and Chen, Y.  An end-to-end deep learning architecture for graph classification.  In _AAAI_ , 2018.
  * Zhao et al. (2022) Zhao, L., Jin, W., Akoglu, L., and Shah, N.  From stars to subgraphs: Uplifting any GNN with local structure awareness.  In _ICLR_ , 2022.
  * Zhou et al. (2023) Zhou, J., Feng, J., Wang, X., and Zhang, M.  Distance-restricted folklore weisfeiler-leman gnns with provable cycle counting power, 2023.

##  Appendix A Proof

###  A.1 Proof of Proposition 2.3

The matrices $Q_{1}^{T}Q_{1}$ and $Q_{2}^{T}Q_{2}$ in $\mathbb{R}^{r\times r}$
are full rank and thus invertible. This allows us to derive the following
equations:

$L=Q_{1}Q_{1}^{T}=Q_{2}Q_{2}^{T}$ (9) $\displaystyle
Q_{1}Q_{1}^{T}=Q_{2}Q_{2}^{T}\Rightarrow
Q_{1}^{T}Q_{1}Q_{1}^{T}=Q_{1}^{T}Q_{2}Q_{2}^{T}$ (10)
$\displaystyle\Rightarrow
Q_{1}^{T}=(Q_{1}^{T}Q_{1})^{-1}Q_{1}^{T}Q_{2}Q_{2}^{T}$ (11)
$\displaystyle\Rightarrow\exists R\in\mathbb{R}^{m\times
m},Q_{1}^{T}=RQ_{2}^{T}$ (12) $\displaystyle\Rightarrow\exists
R\in\mathbb{R}^{m\times m},Q_{1}=Q_{2}R$ (13) $\displaystyle
Q_{1}Q_{1}^{T}=Q_{2}RR^{T}Q_{2}^{T}=Q_{2}Q_{2}^{T}\Rightarrow
Q_{2}^{T}Q_{2}RR^{T}Q_{2}^{T}Q_{2}=Q_{2}^{T}Q_{2}Q_{2}^{T}Q_{2}$ (14)
$\displaystyle\Rightarrow
RR^{T}=(Q_{2}^{T}Q_{2})^{-1}Q_{2}^{T}Q_{2}Q_{2}^{T}Q_{2}(Q_{2}^{T}Q_{2})^{-1}=I$
(15)

Since $R$ is orthogonal, any two full rank $Q$ matrices are connected by an
orthogonal transformation. Furthermore, if there exists an orthogonal matrix
$R$ where $RR^{T}=I$, then $Q_{1}=Q_{2}R$, and
$L=Q_{1}Q_{1}^{T}=Q_{2}RR^{T}Q_{2}^{T}=Q_{2}Q_{2}^{T}$.

###  A.2 Matrix D+A is Always Positive Semi-Definite

$\forall x\in{\mathbb{R}}^{n}$,

$\displaystyle x^{T}(D+A)x$ $\displaystyle=\sum_{(i,j)\in
E}x_{i}x_{j}+\sum_{i\in V}(\sum_{j\in V}A_{ij})x_{i}^{2}$ (16)
$\displaystyle=\sum_{(i,j)\in E}x_{i}x_{j}+\frac{1}{2}\sum_{(i,j)\in
E}x_{i}^{2}+\frac{1}{2}\sum_{(i,j)\in E}x_{j}^{2}$ (17)
$\displaystyle=\frac{1}{2}\sum_{(i,j)\in E}(x_{i}+x_{j})^{2}\geq 0$ (18)

Therefore, $D+A$ is always positive semi-definite.

###  A.3 Proof of Theorem 3.1

We restate the theorem here:

######  Theorem A.1.

Given two graphs $\mathcal{G}=(V,A,X)$ and
$\mathcal{G^{\prime}}=(V^{\prime},A^{\prime},X^{\prime})$ with degree matrices
$D$ and $D^{\prime}$, respectively, the two graphs are isomorphic
($\mathcal{G}\simeq\mathcal{G^{\prime}}$) if and only if $\exists R\in
O(r),\\{\\!\\!\\{(X_{v},RQ_{v})|\forall v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{(X_{v},Q_{v}^{\prime})|v\in V^{\prime}\\}\\!\\!\\}$,
where $r$ denotes the rank of matrix $Q$, and $Q$ and $Q^{\prime}$ are the
symmetric rank decompositions of $D+A$ and $D^{\prime}+A^{\prime}$
respectively.

###### Proof.

Two graphs are isomorphic $\Leftrightarrow$ $\exists\pi\in\Pi_{n}$,
$\pi(A)=A^{\prime}$ and $\pi(X)=X^{\prime}$.

Now we prove that $\exists\pi\in\Pi_{n}$, $\pi(A)=A^{\prime}$ and $\pi(X)=X$
$\Leftrightarrow$ $\exists R\in O(r),\\{\\!\\!\\{(X_{v},RQ_{v})|v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{(X_{v},Q_{v}^{\prime})|v\in V^{\prime}\\}\\!\\!\\}$.

When $\exists\pi\in\Pi_{n}$, $\pi(A)=A^{\prime}$ and $\pi(X)=X^{\prime}$, as

$\pi(Q)\pi(Q)^{T}=\pi(A+D)=A^{\prime}+D^{\prime}=Q^{\prime}{Q^{\prime}}^{T},$
(19)

according to Proposition 2.3, $\exists R\in O(r),\pi(Q)R^{T}=Q^{\prime}$.
Moreover, $\pi(X)=X^{\prime}$, so

$\\{\\!\\!\\{(X_{v},RQ_{v})|v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{(X_{v}^{\prime},Q_{v}^{\prime})|v\in
V^{\prime}\\}\\!\\!\\}$ (20)

When $\exists R\in O(r),\\{\\!\\!\\{(X_{v},RQ_{v})|v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{(X_{v}^{\prime},Q_{v}^{\prime})|v\in
V^{\prime}\\}\\!\\!\\}$, there exists permutation $\pi\in\Pi_{n}$,
$\pi(X)=X^{\prime},\pi(Q)R^{T}=Q^{\prime}$. Therefore,

$\pi(A+D)=\pi(Q)\pi(Q)^{T}=\pi(Q)R^{T}R\pi(Q)^{T}=Q^{\prime}{Q^{\prime}}^{T}=A^{\prime}+D^{\prime}$
(21)

∎

As $A=D+A-\frac{1}{2}\text{diag}((D+A)\vec{1})$,
$A^{\prime}=D+A-\frac{1}{2}\text{diag}((D+A)\vec{1})$, where
$\vec{1}\in{\mathbb{R}}^{n}$ is an vector with all elements $=1$.

$\pi(A)=A^{\prime}$ (22)

###  A.4 Proof of Theorem 3.3

Now we restate the theorem.

######  Theorem A.2.

Given two graphs ${\mathcal{G}}=(V,A,X)$ and
${\mathcal{G}}=(V^{\prime},A^{\prime},X^{\prime})$, and an injective
permutation-equivariant function $Z$ mapping adjacency matrix to a symmetric
matrix: (1) For all permutation-equivariant function $f$, if
${\mathcal{G}}\simeq{\mathcal{G}}^{\prime}$, then the two sets of PSRD
coordinates are equal up to an orthogonal transformation, i.e., $\exists R\in
O(r),\\{\\!\\!\\{X_{v},R\mathcal{Q}(\mathcal{Z}(A),f)_{v}|v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{X_{v}^{\prime},\mathcal{Q}(\mathcal{Z}(A^{\prime}),f)_{v}|v\in
V^{\prime}\\}\\!\\!\\}$, where $r$ is the rank of $A$,
$\mathcal{Q},\mathcal{Q}^{\prime}$ are the PSRD coordinates of $A$ and
$A^{\prime}$ respectively. (2) There exists a continuous permutation-
equivariant function $f:{\mathbb{R}}^{r}\to{\mathbb{R}}^{r\times 2}$, such
that ${\mathcal{G}}\simeq{\mathcal{G}}^{\prime}$ if $\exists R\in O(r),\forall
i=1,2,...,d,\\{\\!\\!\\{(X_{v},R\mathcal{Q}(\mathcal{Z}(A),f_{1})_{v},R\mathcal{Q}(\mathcal{Z}(A),f_{2})_{v})|v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{(X_{v}^{\prime},\mathcal{Q}(\mathcal{Z}(A^{\prime}),f_{1})_{v},\mathcal{Q}(\mathcal{Z}(A^{\prime}),f_{2})_{v})|v\in
V^{\prime}\\}\\!\\!\\}$, where $f_{1}:{\mathbb{R}}^{r}\to{\mathbb{R}}^{r}$ and
$f_{2}:{\mathbb{R}}^{r}\to{\mathbb{R}}^{r}$ are two output channels of $f$.

###### Proof.

First, as $\mathcal{Z}$ is an injective permutation equivariant function,
forall permutation $\pi\in\Pi_{n}$

$\pi(\mathcal{Z}(A))=\mathcal{Z}(A^{\prime})\Leftrightarrow\mathcal{Z}(\pi(A))=\mathcal{Z}(A^{\prime})\Leftrightarrow\pi(A)=A^{\prime}.$
(23)

Therefore, two matrix are isomorphic $\Leftrightarrow$
$\exists\pi\in\Pi_{n},\pi(X)=X^{\prime},\pi(Z)=Z^{\prime}$, where
$Z,Z^{\prime}$ denote $Z(A),Z(A^{\prime})$ respectively.

In this proof, we denote eigendecomposition as $Z=U\text{diag}(\Lambda)U^{T}$
and $Z^{\prime}=U^{\prime}\text{diag}(\Lambda^{\prime}){U^{\prime}}^{T}$,
where elements in $\Lambda$ and $\Lambda^{\prime}$ are sorted in ascending
order. Let the multiplicity of eigenvalues in $Z$ be $r_{1},r_{2},...,r_{l}$,
corresponding to eigenvalues $\lambda_{1},\lambda_{2},...,\lambda_{i}$.

(1) If ${\mathcal{G}}\simeq{\mathcal{G}}^{\prime}$, there exists a permutation
$\pi\in\Pi_{n}$, $\pi(X)=X^{\prime},\pi(Z)=Z^{\prime}$.

$\pi(Z)=Z^{\prime}\Rightarrow
Z^{\prime}=\pi(U)\text{diag}(\Lambda)\pi(U)^{T}=U^{\prime}\text{diag}(\Lambda^{\prime}){U^{\prime}}^{T}.$
(24)

$\pi(U)\text{diag}(\Lambda)\pi(U)^{T}$ is also an eigendecomposition of
$Z^{\prime}$, so $\Lambda=\Lambda^{\prime}$ as they are both sorted in
ascending order. Moreover, since $\pi(U),U^{\prime}$ are both matrices of
eigenvectors, they can differ only in the choice of bases in each
eigensubspace. So there exists a block diagonal matrix $V$ with orthogonal
matrix $V_{1}\in O(r_{1}),V_{2}\in O(r_{2}),...,V_{l}\in O(r_{l})$ as diagonal
blocks that $\pi(U)V=U^{\prime}$.

As $f$ is a permutation equivariant function,

$\displaystyle\Lambda_{i}=\Lambda_{j}$
$\displaystyle\Rightarrow\exists\pi\in\Pi_{r},\pi(i)=j,\pi(j=i),\pi(\Lambda)=\Lambda$
(25)
$\displaystyle\Rightarrow\exists\pi\in\Pi_{r},\pi(i)=j,\pi(j=i),\pi(f(\Lambda))=f(\pi(\Lambda))=f(\Lambda)$
(26) $\displaystyle\Rightarrow f(\Lambda)_{i}=f(\Lambda)_{j}$ (27)

Therefore, $f$ will produce the same value on positions with the same
eigenvalue. Therefore, $f$ can be consider as a block diagonal matrix with
$f_{1}I_{r_{1}},f_{2}I_{r_{2}},...,f_{l}I_{r_{l}}$ as diagonal blocks, where
$f_{i}\in{\mathbb{R}}$ is $f(\Lambda)_{p_{i}}$, $p_{i}$ is a position that
$\Lambda_{p_{i}}=\lambda_{i}$, and $I_{r}$ is an identity matrix
$\in{\mathbb{R}}^{r\times r}$.

Therefore,

$V\text{diag}(f(\Lambda))=\text{diag}(f_{1}V_{1},f_{2}V_{2},...,f_{l}V_{l})=\text{diag}(f(\Lambda))V.$
(28)

Therefore,

$\displaystyle\pi(Q(Z,f))V$ $\displaystyle=\pi(U)\text{diag}(f(\Lambda))V$
(29) $\displaystyle=\pi(U)V\text{diag}(f(\Lambda))$ (30)
$\displaystyle=U^{\prime}\text{diag}(f(\Lambda^{\prime}))$ (31)
$\displaystyle=Q(Z^{\prime},f)$ (32)

As $VV^{T}=I,V\in O(r)$,

$\exists R\in O(r),\\{\\!\\!\\{X_{v},R\mathcal{Q}(\mathcal{Z}(A),f)_{v}|v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{X_{v}^{\prime},\mathcal{Q}(\mathcal{Z}(A^{\prime}),f)_{v}|v\in
V^{\prime}\\}\\!\\!\\}$ (33)

(2) We simply define $f_{1}$ is element-wise abstract value and square root
$\sqrt{|.|}$, $f_{1}$ is element-wise abstract value and square root
multiplied with its sign $sgn(|.|)\sqrt{|.|}$. Therefore, $f_{1},f_{2}$ are
continuous and permutation equivariant.

if $\exists R\in O(r)$,

$\\{\\!\\!\\{X_{v},R\mathcal{Q}(Z(A),f_{1})_{v},R\mathcal{Q}(Z(A),f_{2})_{v}|v\in
V\\}\\!\\!\\}=\\{\\!\\!\\{X_{v}^{\prime},\mathcal{Q}(Z(A^{\prime}),f_{1})_{v},\mathcal{Q}(Z(A^{\prime}),f_{2})_{v}|v\in
V^{\prime}\\}\\!\\!\\}$. then there exist $\pi\in\Pi_{n}$, so that

$\pi(X)=X^{\prime}$ (34)
$\pi(U)\text{diag}(f_{1}(\Lambda))R^{T}=U^{\prime}\text{diag}(f_{1}(\Lambda^{\prime}))$
(35)
$\pi(U)\text{diag}(f_{2}(\Lambda))R^{T}=U^{\prime}\text{diag}(f_{2}(\Lambda^{\prime})).$
(36)

Therefore,

$\displaystyle\pi(Z)$
$\displaystyle=\pi(U)\text{diag}(f_{1}(\Lambda))\text{diag}(f_{2}(\Lambda))\pi(U^{\prime})^{T}$
(37)
$\displaystyle=\pi(U)\text{diag}(f_{1}(\Lambda))RR^{T}\text{diag}(f_{2}(\Lambda))\pi(U^{\prime})^{T}$
(38)
$\displaystyle=U^{\prime}\text{diag}(f_{1}(\Lambda^{\prime}))\text{diag}(f_{2}(\Lambda^{\prime})){U^{\prime}}^{T}$
(39) $\displaystyle=Z^{\prime}.$ (40)

As $\pi(Z)=Z^{\prime},\pi(X)=X^{\prime}$, two graphs are isomorphic.

∎

###  A.5 Proof of Theorem 5.3

Let $H_{l}$ denote a circle of $l$ nodes. Let $G_{l}$ denote a graph of two
connected components, one is $H_{\lfloor l/2\rfloor}$ and the other is
$H_{\lceil l/2\rceil}$. Obviously, there exists a node pair in $G_{l}$ with
shortest path distance equals to infinity, while $H_{l}$ does not have such a
node pair. So the multiset of shortest path distance is easy to distinguish
them. However, they are regular graphs with node degree all equals to $2$, so
MPNN cannot distinguish them:

######  Lemma A.3.

For all nodes $v,u$ in $G_{l}$, $H_{l}$, they have the same representation
produced by $k$-layer MPNN, forall $k\in N$.

###### Proof.

We proof it by induction.

$k=0$. Initialization, all node with trivial node feature and are the same.

Assume $k-1$-layer MPNN still produce representation $h$ for all node. At the
$k$-th layer, each node’s representation will be updated with its own
representation and two neighbors representations as follows.

$h,\\{\\!\\!\\{h,h\\}\\!\\!\\}$ (41)

So all nodes still have the same representation. ∎

###  A.6 Proof of Theorem 5.2 and B.3

Given two function $f,g$, $f$ can be expressed by $g$ means that there exists
a function $\phi$ $\phi\circ g=f$, which is equivalent to given arbitrary
input $H,G$, $f(H)=f(G)\Rightarrow g(H)=g(G)$. We use $f\to g$ to denote that
$f$ can be expressed with $g$. If both $f\to g$ and $g\to f$, there exists a
bijective mapping between the output of $f$ to the output of $g$, denoted as
$f\leftrightarrow g$.

Here are some basic rule.

  * •

$g\to h\Rightarrow f\circ g\to f\circ h$.

  * •

$g\to h,f\to s\Rightarrow f\circ g\to s\circ h$.

  * •

$f$ is bijective, $f\circ g\to g$

2-folklore Weisfeiler-Leman test produce a color $h_{ij}^{t}$ for each node
pair $(i,j)$ at $t$-th iteration. It updates the color as follows,

$h_{ij}^{t+1}=\text{hash}(h_{ij}^{t},\\{\\!\\!\\{(h_{ik}^{t},h_{kj}^{t})|k\in
V\\}\\!\\!\\}).$ (42)

The color of the the whole graph is

$h_{G}^{t}=\text{hash}(\\{\\!\\!\\{h_{ij}^{t}|(i,j)\in V\times
V\\}\\!\\!\\}).$ (43)

Initially, tuple color hashes the node feature and edge between the node pair,
$h_{ij}^{0}\to\delta_{ij},A_{ij},X_{i},X_{j}$.

We are going to prove that

######  Lemma A.4.

Forall $t\in{\mathbb{N}}$, $h_{ij}^{t}$ can express $A_{ij}^{k}$,
$k=0,1,2,...,2^{t}$, where $A$ is the adjacency matrix of the input graph.

###### Proof.

We prove it by induction on $t$.

  * •

When $t=0$, $h_{ij}^{0}\to A_{ij},I_{ij}$ in initialization.

  * •

If $t>0,\forall t^{\prime}<t,h_{ij}^{t^{\prime}}\to
A^{k^{\prime}},k^{\prime}=0,1,2,...,2^{t^{\prime}}$. For all $k=0,1,2,$

$\displaystyle h_{ij}^{t}$
$\displaystyle\to\text{hash}(h_{ij}^{t},\\{\\!\\!\\{(h_{ik}^{t},h_{kj}^{t})|k\in
V\\}\\!\\!\\})$ (44)
$\displaystyle\to\text{hash}(h_{ij}^{t},\\{\\!\\!\\{(A_{ik}^{\lfloor
k/2\rfloor},A_{kj}^{\lceil k/2\rceil})|k\in V\\}\\!\\!\\})$ (45)
$\displaystyle\to\sum_{k\in V}A_{ik}^{\lfloor k/2\rfloor}A_{kj}^{\lceil
k/2\rceil}$ (46) $\displaystyle\to A_{ij}^{k}$ (47)

∎

To prove that $t$-iteration 2-FWL cannot compute shortest path distance larger
than $2^{t^{\prime}}$, we are going to construct an example.

######  Lemma A.5.

Let $H_{l}$ denote a circle of $l$ nodes. Let $G_{l}$ denote a graph of two
connected components, one is $H_{\lfloor l/2\rfloor}$ and the other is
$H_{\lceil l/2\rceil}$. $\forall K\in{\mathbb{N}}^{+}$, 2-FWL can not
distinguish $H_{l_{K}}$ and $G_{l_{K}}$, where $l_{K}=2\times 2\times(2^{K})$.
However, $G_{l_{K}}$ contains node tuple with $2^{K}+1$ shortest path distance
between them while $H_{l_{K}}$ does not, any model count up to $2^{K}+1$
shortest path distance can count it.

###### Proof.

Given a fixed $t$, we enumerate the iterations of 2-FWL. Given two graphs
$H_{l_{K}}$, $G_{l_{K}}$, we partition all tuples in each graph according to
the shortest path distance between nodes:
$c_{0},c_{1},...,c_{l},...,c_{2^{K}}$, where $c_{l}$ contains all tuples with
shortest path distance between them as $l$, and $c_{>2^{K}}$ contains all
tuples with shortest path distance between them larger than $2^{K}$. We are
going to prove that at $k$-th layer $k<=K$, all $c_{i},i\leq 2^{k}$ nodes have
the same representation (denoted as $h^{k}_{i}$)
$c_{2^{k}+1},c_{2^{k}+2},...,c_{2^{K}},c_{>K}$ nodes all have the same
representation (denoted as $h^{k}_{2^{k}+1}$).

Initially, all $c_{0}$ tuples have representation $h_{0}^{0}$, all $c_{1}$
tuples have the same representation $h_{1}^{0}$ in both graph, and all other
tuples have the same representation $h_{2}^{0}$.

Assume at $k$-th layer, all $c_{i},i\leq 2^{k}$ nodes have the same
representation $h^{k}_{i}$, $c_{2^{k}+1},c_{2^{k}+2},...,c_{2^{K}},c_{>2^{K}}$
tuples all have the same representation $h^{k}_{2^{k}+1}$. At $k+1$-th layer,
each representation is updated as follows.

$h_{ij}^{t+1}\leftarrow h_{ij}^{t},\\{\\!\\!\\{(h_{iv}^{t},h_{vj}^{t})|v\in
V\\}\\!\\!\\}$ (48)

For all tuples, the multiset has $l_{K}$ elements in total.

For $c_{0}$ tuples, the multiset have 1 $(h_{0}^{k},h_{0}^{k})$ as $v=i$, 2
$(h_{t}^{k},h_{t}^{k})$ for $t=1,2,..,2^{k}$ respectively as v is the $k$-hop
neighbor of $i$, and all elements left are $(h_{2^{k}+1}^{k},h_{2^{k}+1}^{k})$
as $v$ is not in the $k$-hop neighbor of $i$.

For $c_{t},t=1,2,...,2^{k}$ tuples: the multiset have 1
$(h_{a}^{k},h_{t-a}^{k})$ for $a=0,1,2,..,t$ respectively as $v$ is on the
shortest path between $(i,j)$, and 1 $(h_{a}^{k},h_{2^{k}+1}^{k})$ for
$a=1,2,...,2^{k}$ respectively, and 1 $(h_{2^{k}+1}^{k},h_{a}^{k})$ for
$a=1,2,...,2^{k}$ respectively, with other elements are
$(h_{2^{k}+1}^{k},h_{2^{k}+1}^{k})$.

For $c_{t},t=2^{k}+1,2^{k}+2,...,2^{k+1}$ tuples: the multiset have 1
$(h_{a}^{k},h_{t-a}^{k})$ for $a=t-2^{k},t-2^{k}+1,...,2^{k}$ respectively as
$v$ is on the shortest path between $(i,j)$, 1 $(h_{a}^{k},h_{t-a}^{k})$ for
$a\in\\{0,1,2,...,t-2^{k}-1\\}\cup\\{2^{k}+1,2^{k}+2,...,2^{k+1}\\}$
respectively as $v$ is on the shortest path between $(i,j)$, and 1
$(h_{a}^{k},h_{2^{k}+1}^{k})$ for $a=1,2,...,2^{k}$ respectively, and 1
$(h_{2^{k}+1}^{k},h_{a}^{k})$ for $a=1,2,...,2^{k}$ respectively, with other
elements are $(h_{2^{k}+1}^{k},h_{2^{k}+1}^{k})$.

For $c_{t},t=2^{k+1}+1,...,2^{K},>2^{K}$: the multiset are all the same : 2
$(h_{a}^{k},h_{2^{k}+1}^{k})$ and 2 $(h_{2^{k}+1}^{k},h_{a}^{k})$ for
$a=1,2,3,...,2^{k}$, respectively. ∎

###  A.7 Proof of Theorem 5.1

We can simply choose $f_{k}(\Lambda)=\Lambda^{k}$. Then
$\langle\mathcal{Q}(A,f_{0})_{i},\mathcal{Q}(A,f_{k})_{j}\rangle=A_{ij}^{k}$.
The shortest path distance is

$spd(i,j,A)=\arg\min_{k}\\{k\in{\mathbb{N}}|A_{ij}^{k}>0\\}$ (49)

###  A.8 Proof of Theorem 5.4 and 5.5

This section assumes that the input graph is undirected and unweighted with no
self-loops. Let $A$ denote the adjacency matrix of the graph. Note that
$A^{T}=A,A\odot A=A$

An $L$-path is a sequence of edges
$[(i_{1},i_{2}),(i_{2},i_{3}),...,(i_{L},i_{L+1})]$, where all nodes are
different from each other. An $L$-cycle is an $L$-path except that
$i_{1}=i_{L+1}$. Two paths/cycles are considered equivalent if their sets of
edges are equal. The count of $L$ path from node $u$ to $v$ is the number of
non-equivalent pathes with $i_{1}=u,i_{L+1}=v$. The count of $L$-cycle rooted
in node $u$ is the number of non-equivalent cycles involves node $u$.

Perepechko & Voropaev (2009) show that the number of path can be expressive
with a polynomial of $A$, where $A$ is the adjacency matrix of the input
unweight graph. Specifically, let $P_{L}$ denote path matrix whose $(u,v)$
elements denote the number of $L$-pathes from $u$ to $v$, Perepechko &
Voropaev (2009) provides formula to express $P_{L}$ with $A$ for small $L$.

This section considers a weaken version of point cloud transformer. Each layer
still consists of sv-mixer and multi-head attention. However, the multi-head
attention matrix takes the scalar and vector feature before sv-mixer for $Q,K$
and use the feature after sv-mixer for $V$.

At $k$-th layer sv-mixer:

$\displaystyle
s_{i}^{\prime}\leftarrow\text{MLP}_{1}(s_{i}\|\text{diag}(W_{1}v_{i}^{T}v_{i}^{k}W_{2}))$
(50) $\displaystyle v_{i}^{\prime}\leftarrow
v_{i}\text{diag}(\text{MLP}_{2}(s_{i}^{\prime}))W_{3}+v_{i}W_{4}$ (51)

Attention layer:

$Y_{ij}=\text{MLP}_{3}(K_{ij}),K_{ij}=(W_{q}^{s}s_{i}\odot
W_{k}^{s}s_{j})\|\text{diag}(W_{q}^{v}v_{i}^{T}v_{i}W_{k}^{v}),$ (52)

As $s^{\prime}_{i}$ and $v^{\prime}_{i}$ can express $s_{i},v_{i}$, so the
weaken version can be expressed with the original version.

$\displaystyle s_{i}$
$\displaystyle\leftarrow\text{MLP}_{4}(s_{j}^{\prime}\|\sum_{j}\text{Atten}_{ij}s_{j}^{\prime})$
(53) $\displaystyle v_{i}$ $\displaystyle\leftarrow
W_{5}(v_{j}^{\prime}\|\sum_{j}\text{Atten}_{ij}v_{j}^{\prime})$ (54)

Let $Y^{k}$ denote the attention matrix at $k$-th layer. $Y^{k}$ is a
learnable function of $A$. Let ${\mathbb{Y}}^{k}$ denote the polynomial space
of $A$ that $Y^{k}$ can express. Each element in it is a function from
${\mathbb{R}}^{n\times n}\to{\mathbb{R}}^{n\times n}$

We are going to prove some lemmas about ${\mathbb{Y}}$.

######  Lemma A.6.

${\mathbb{Y}}^{k}\subseteq{\mathbb{Y}}^{k+1}$

###### Proof.

As there exists residual connection, scalar and vector representations of
layer $k+1$ can always contain those of layer $k$, so attention matrix of
layer $k+1$ can always express those of layer $k$. ∎

######  Lemma A.7.

If $y_{1},y_{2},...,y_{s}\in{\mathbb{Y}}^{k}$, their hadamard product
$y_{1}\odot y_{2}\odot...\odot y_{s}\in{\mathbb{Y}}^{k}$.

###### Proof.

As $(y_{1}\odot y_{2}\odot...\odot y_{s})_{ij}=\prod_{l=1}^{s}(y_{l})_{ij}$ is
a element-wise polynomial on compact domain, an MLP (denoted as $g$) exists
that takes $(i,j)$ elements of the $y_{1},y_{2},...,y_{s}$ to produce the
corresponding elements of their hadamard product. Assume $g_{0}$ is the
$\text{MLP}_{3}$ in Equation 53 to produce the concatenation of
$y_{1},y_{2},..,y_{s}$, use $g\circ g_{0}$ (the composition of two mlps) for
the $\text{MLP}_{3}$ in Equation 53 produces the hadamard product. ∎

######  Lemma A.8.

If $y_{1},y_{2},...,y_{s}\in{\mathbb{Y}}^{k}$, their linear combination
$\sum_{l=1}^{s}a_{l}y_{l}\in{\mathbb{Y}}^{k}$, where $a_{l}\in{\mathbb{R}}$.

###### Proof.

As $(\sum_{l=1}^{s}a_{l}y_{l})_{ij}=\sum_{l=1}^{s}a_{l}(y_{l})_{ij}$ is a
element-wise linear layer (denoted as $g$). Assume $g_{0}$ is the
$\text{MLP}_{3}$ in Equation 53 to produce the concatenation of
$y_{1},y_{2},..,y_{s}$, use $g\circ g_{0}$ for the $\text{MLP}_{3}$ in
Equation 53 produces the linear combination. ∎

######  Lemma A.9.

$\forall s>0,A^{s}\in{\mathbb{Y}}^{1}$.

###### Proof.

As shown in Section 5.1, the inner product of coordinates can produce $A^{s}$.
∎

######  Lemma A.10.

$\forall
y_{1},y_{2},y_{3}\in{\mathbb{Y}}^{k},s\in{\mathbb{N}}^{+},d(y_{1})y_{2},y_{2}d(y_{1}),d(y_{1})y_{2}d(y_{3}),y_{1}A^{s},A^{s}y_{1},y_{1}A^{s}y_{2}\in{\mathbb{Y}}^{k}$

###### Proof.

According to Equation 50 and Equation 52, $s_{i}^{\prime}$ at $k$-th layer can
express $y_{ii}$ for all $y\in{\mathbb{Y}}^{k}$. Therefore, at $k+1$-th layer
in Equation 52, $\text{MLP}_{3}$ can first compute element $(i,j)$
$(y_{2})_{ij}$ from $s_{i},s_{j},v_{i},v_{j}$, then multiply $(y_{2})_{ij}$
with $(y_{1})_{ii}$ from $s_{i}$, $(y_{3})_{jj}$ from $s_{j}$ and thus produce
$d(y_{1})y_{2},y_{2}d(y_{1}),d(y_{1})y_{2}d(y_{3})$.

Moreover, according to Equation 53, $v_{i}$ at $k+1$-th layer can express
$\sum_{k}(y_{1})_{ik}v_{k},\sum_{k}(y_{2})_{ik}v_{k}$. So at $k+1$-th layer,
the $(i,j)$ element can express
$\langle\sum_{k}(y_{1})_{ik}v_{k},v_{j}\rangle,\langle
v_{i},\sum_{k}(y_{1})_{jk}v_{k}\rangle,\langle(y_{1})_{ik}v_{k},\sum_{k}(y_{2})_{jk}v_{k}\rangle$,
corresponds to $y_{1}A^{s},A^{s}y_{2},y_{1}A^{s}y_{2}$, respectively.

∎

Therefore,

######  Lemma A.11.

  * •

$\forall s>0,l>0,a_{i}>0$, $\odot_{i=1}^{l}A^{a_{i}}\in{\mathbb{Y}}^{1}$.

  * •

$\forall s_{1},s_{2}>0,l>0$,
$A^{s_{1}}d(\odot_{i=1}^{l}A^{a_{i}}),d(\odot_{i=1}^{l}A^{a_{i}})A^{s_{1}},d(\odot_{i=1}^{l_{1}}A^{b_{i}})A^{s_{1}}d(\odot_{i=1}^{l_{2}}A^{b_{i}})\in{\mathbb{Y}}^{2}$.

  * •

$\forall s_{1},s_{2},s_{3}>0$, $A^{s_{1}}d(\odot_{i=1}^{l}A^{a_{i}})$

Therefore, we come to our main theorem.

######  Theorem A.12.

The attention matrix of 1-layer PST can express $P_{2}$, 2-layer PST can
express $P_{3}$, 3-layer PST can express $P_{4},P_{5}$, 5-layer PST can
express $P_{6}$.

###### Proof.

As shown in (Perepechko & Voropaev, 2009),

$\displaystyle P_{2}$ $\displaystyle=A^{2}$ (55)

Only one kind basis $\odot_{i=1}^{l}A^{a_{i}}$. 1-layer PST can express it.

$\displaystyle P_{3}$ $\displaystyle=A^{3}+A-Ad(A^{2})-d(A^{2})A$ (56)

Three kind of basis $\odot_{i=1}^{l}A^{a_{i}}$($A^{3},A$),
$A^{s_{1}}d(\odot_{i=1}^{l}A^{a_{i}})$($Ad(A^{2})$), and
$d(\odot_{i=1}^{l}A^{a_{i}})A^{s_{1}}$. 2-layer PST can express it.

$\displaystyle P_{4}$ $\displaystyle=A^{4}+A^{2}+3A\odot
A^{2}-d(A^{3})A-d(A^{2})A^{2}-Ad(A^{3})-A^{2}d(A^{2})-Ad(A^{2})A$ (57)

Four kinds of basis $\odot_{i=1}^{l}A^{a_{i}}$ ($A^{4},A^{2},A\odot A^{2}$),
$A^{s_{1}}d(\odot_{i=1}^{l}A^{a_{i}})$ ($Ad(A^{3}),A^{2}d(A^{2})$),
$d(\odot_{i=1}^{l}A^{a_{i}})A^{s_{1}}$ ($d(A^{3})A,d(A^{2})A^{2}$), and
$A^{s_{1}}d(\odot_{i=1}^{l}A^{a_{i}})A^{s_{3}}$ ($Ad(A^{2})A$). 3-layer PST
can express it.

$\displaystyle P_{5}$ $\displaystyle=A^{5}+3A^{3}+4A$ (58)
$\displaystyle~{}+3A^{2}\odot A^{2}\odot A+3A\odot A^{3}-4A\odot A^{2}$ (59)
$\displaystyle~{}-d(A^{4})A-d(A^{3})A^{2}-d(A^{2})A^{3}+2d(A^{2})^{2}A-2d(A^{2})A-4d(A^{2})A$
(60)
$\displaystyle~{}-Ad(A^{4})-A^{2}d(A^{3})-A^{3}d(A^{2})+2Ad(A^{2})^{2}-2Ad(A^{2})-4Ad(A^{2})$
(61) $\displaystyle~{}+d(A^{2})Ad(A^{2})$ (62) $\displaystyle~{}+3(A\odot
A^{2})A$ (63) $\displaystyle~{}+3A(A\odot A^{2})$ (64)
$\displaystyle~{}-Ad(A^{3})A-Ad(A^{2})A^{2}-A^{2}d(A^{2})A$ (65)
$\displaystyle~{}+d(Ad(A^{2})A)A$ (66)

Basis are in

  * •

${\mathbb{Y}}^{1}$

    * –

$\odot_{i=1}^{l}A^{a_{i}}$: $A^{5},A^{3},A,A^{2}\odot A^{2}\odot A,A\odot
A^{3},A\odot A^{2}$.

  * •

${\mathbb{Y}}^{2}$

    * –

$A^{s_{1}}d(\odot_{i=1}^{l}A^{a_{i}})$:$Ad(A^{4}),A^{2}d(A^{3}),A^{3}d(A^{2}),Ad(A^{2})^{2},Ad(A^{2}),Ad(A^{2})$.

    * –

$d(\odot_{i=1}^{l}A^{a_{i}})A^{s_{1}}$:
$Ad(A^{4}),A^{2}d(A^{3}),A^{3}d(A^{2}),Ad(A^{2})^{2},Ad(A^{2}),Ad(A^{2})$.

    * –

$d(\odot_{i=1}^{l_{1}}A^{a_{i}})A^{s_{1}}d(\odot_{i=1}^{l_{1}}A^{b_{i}})$:
$d(A^{2})Ad(A^{2})$.

    * –

$A^{s_{1}}(\odot_{i=1}^{l}A^{a_{i}})$: $A(A\odot A^{2})$.

    * –

$(\odot_{i=1}^{l}A^{a_{i}})A^{s_{1}}$: $(A\odot A^{2})A$

  * •

${\mathbb{Y}}^{3}$:

    * –

$A^{s}{\mathbb{Y}}^{2}$: $Ad(A^{3})A$, $Ad(A^{2})A^{2}$, $A^{2}d(A^{2})A$.

    * –

$d({\mathbb{Y}}^{2})A^{s}$: $d(Ad(A^{2})A)A$

3-layer PST can express it.

Formula for $6$-path matrix is quite long.

$\displaystyle P_{6}$ $\displaystyle=A^{6}+4A^{4}+12A^{2}$ (68)
$\displaystyle~{}+3A\odot A^{4}+6A\odot A^{2}\odot A^{3}+A^{2}\odot A^{2}\odot
A^{2}-4A^{2}\odot A^{2}+44A\odot A^{2}$ (69)
$\displaystyle~{}-d(A^{5})A-d(A^{4})A^{2}-d(A^{3})A^{3}-5d(A^{3})A-d(A^{2})A^{4}-7d(A^{2})A^{2}$
(70) $\displaystyle+2d(A^{2})^{2}A^{2}+4(d(A^{2})\odot d(A^{3}))A$ (71)
$\displaystyle~{}-Ad(A^{5})-A^{4}d(A^{2})-A^{3}d(A^{3})-5Ad(A^{3})-A^{2}d(A^{4})-7A^{2}d(A^{2})$
(72) $\displaystyle+2A^{2}d(A^{2})^{2}+4A(d(A^{2})\odot d(A^{3}))$ (73)
$\displaystyle~{}+d(A^{2})Ad(A^{3})+d(A^{3})Ad(A^{2})+d(A^{2})A^{2}d(A^{2})$
(74) $\displaystyle~{}+2(A\odot A^{3})A+2(A\odot A^{2}\odot
A^{2})A+(A^{2}\odot A^{2}\odot A)A-3(A\odot A^{2})A+(A\odot A^{3})A$ (75)
$\displaystyle~{}+(A\odot A^{2})A^{2}+2(A\odot A^{2})A^{2}-(A\odot A^{2})A$
(76) $\displaystyle~{}+2A(A\odot A^{3})+2A(A\odot A^{2}\odot
A^{2})+A(A^{2}\odot A^{2}\odot A)-3A(A\odot A^{2})+A(A\odot A^{3})$ (77)
$\displaystyle+A^{2}(A\odot A^{2})+2A^{2}(A\odot A^{2})-A(A\odot A^{2})$ (78)
$\displaystyle~{}-8A\odot(A(A\odot A^{2}))-8A\odot((A\odot A^{2})A)$ (79)
$\displaystyle~{}-12d(A^{2})(A\odot A^{2})-12(A\odot A^{2})d(A^{2})$ (80)
$\displaystyle~{}-Ad(A^{4})A-Ad(A^{2})A^{3}-A^{3}d(A^{2})A-Ad(A^{3})A^{2}-A^{2}d(A^{3})A-A^{2}d(A^{2})A^{2}$
(81) $\displaystyle-10Ad(A^{2})A+2Ad(A^{2})^{2}A$ (82)
$\displaystyle~{}+d(A^{2})Ad(A^{2})A+Ad(A^{2})Ad(A^{2})$ (83)
$\displaystyle~{}-3A\odot(Ad(A^{2})A)$ (84) $\displaystyle~{}-4Ad((A\odot
A^{2})A)-4Ad(A(A\odot A^{2}))$ (85) $\displaystyle~{}+3A(A\odot A^{2})A$ (86)
$\displaystyle~{}-4d(A(A\odot A^{2}))A-4d((A\odot A^{2})A)A$ (87)
$\displaystyle~{}+d(Ad(A^{3})A)A+d(Ad(A^{2})A)A^{2}+d(Ad(A^{2})A^{2})A+d(A^{2}d(A^{2})A)A$
(88)
$\displaystyle~{}+Ad(Ad(A^{3})A)+A^{2}d(Ad(A^{2})A)+Ad(A^{2}d(A^{2})A)+Ad(Ad(A^{2})A^{2})$
(89) $\displaystyle~{}+Ad(Ad(A^{2})A)A$ (90)

Basis are in

  * •

${\mathbb{Y}}^{1}$

    * –

$\odot_{i=1}^{l}A^{a_{i}}$: $A^{6},A^{4},A^{2},A\odot A^{4},A\odot A^{2}\odot
A^{3},A^{2}\odot A^{2}\odot A^{2},A^{2}\odot A^{2},A\odot A^{2}$.

  * •

${\mathbb{Y}}^{2}$

    * –

$A^{s_{1}}d(\odot_{i=1}^{l}A^{a_{i}})$:$Ad(A^{5})$, $A^{4}d(A^{2})$,
$A^{3}d(A^{3})$, $Ad(A^{3})$, $A^{2}d(A^{4})$, $A^{2}d(A^{2})$,
$A^{2}d(A^{2})^{2}$, $A(d(A^{2})\odot d(A^{3}))$.

    * –

$d(\odot_{i=1}^{l}A^{a_{i}})A^{s_{1}}$: $d(A^{5})A$, $d(A^{4})A^{2}$,
$d(A^{3})A^{3}$, $d(A^{3})A$, $d(A^{2})A^{4}$, $d(A^{2})A^{2}$,
$d(A^{2})^{2}A^{2}$, $(d(A^{2})\odot d(A^{3}))A$.

    * –

$d(\odot_{i=1}^{l_{1}}A^{a_{i}})A^{s_{1}}d(\odot_{i=1}^{l_{1}}A^{b_{i}})$:
$d(A^{2})Ad(A^{3})$, $d(A^{3})Ad(A^{2})$, $d(A^{2})A^{2}d(A^{2})$.

    * –

$A^{s_{1}}(\odot_{i=1}^{l}A^{a_{i}})$: $A(A\odot A^{3})$, $A(A\odot A^{2}\odot
A^{2})$, $A(A^{2}\odot A^{2}\odot A)$, $A(A\odot A^{2})$, $A(A\odot A^{3})$,
$A^{2}(A\odot A^{2})$, $A^{2}(A\odot A^{2})$, $A(A\odot A^{2})$.

    * –

$(\odot_{i=1}^{l}A^{a_{i}})A^{s_{1}}$: $(A\odot A^{3})A$, $(A\odot A^{2}\odot
A^{2})A$, $(A^{2}\odot A^{2}\odot A)A$, $(A\odot A^{2})A$, $(A\odot A^{3})A$,
$(A\odot A^{2})A^{2}$, $(A\odot A^{2})A^{2}$, $(A\odot A^{2})A$

    * –

${\mathbb{Y}}^{2}\odot{\mathbb{Y}}^{2}$: $A\odot((A\odot A^{2})A)$,
$A\odot((A\odot A^{2})A)$.

    * –

$d({\mathbb{Y}}^{1}){\mathbb{Y}}^{1}$: $d(A^{2})(A\odot A^{2})$

    * –

${\mathbb{Y}}^{1}d({\mathbb{Y}}^{1})$: $(A\odot A^{2})d(A^{2})$

  * •

${\mathbb{Y}}^{3}$:

    * –

$A^{s}{\mathbb{Y}}^{2}$: $Ad(A^{4})A$, $Ad(A^{2})A^{3}$, $A^{3}d(A^{2})A$,
$Ad(A^{3})A^{2}$, $A^{2}d(A^{3})A$, $A^{2}d(A^{2})A^{2}$, $Ad(A^{2})A$,
$Ad(A^{2})^{2}A$, $Ad(A^{2})Ad(A^{2})$, $A(A\odot A^{2})A$.

    * –

${\mathbb{Y}}^{2}A^{s}$: $d(A^{2})Ad(A^{2})A$.

    * –

${\mathbb{Y}}^{3}\odot{\mathbb{Y}}^{3}$: $A\odot(Ad(A^{2})A)$.

    * –

$d({\mathbb{Y}}^{2}){\mathbb{Y}}^{2}$: $d(Ad(A^{2})A)A$,$d(A(A\odot
A^{2}))A$,$d((A\odot A^{2})A)A$

    * –

${\mathbb{Y}}^{2}d({\mathbb{Y}}^{2})$:$Ad((A\odot A^{2})A)$,$Ad(A(A\odot
A^{2}))$

  * •

${\mathbb{Y}}^{4}$:

    * –

$d({\mathbb{Y}}^{3}){\mathbb{Y}}^{3}$: $d(Ad(A^{3})A)A$, $d(Ad(A^{2})A)A^{2}$,
$d(Ad(A^{2})A^{2})A$, $d(A^{2}d(A^{2})A)A$.

    * –

${\mathbb{Y}}^{3}d({\mathbb{Y}}^{3})$: $Ad(Ad(A^{3})A)$, $A^{2}d(Ad(A^{2})A)$,
$Ad(A^{2}d(A^{2})A)$, $Ad(Ad(A^{2})A^{2})$.

  * •

${\mathbb{Y}}^{5}$:

    * –

$A^{s_{1}}d({\mathbb{Y}}^{3})A^{s_{2}}$:$Ad(Ad(A^{2})A)A$

5-layer PST can express it. ∎

Count cycle is closely related to counting path. A $L+1$ cycle contains edge
$(i,j)$ can be decomposed into a $L$-path from $i$ to $j$ and edge $(i,j)$.
Therefore, the vector of count of cycles rooted in each node
$C_{L+1}=\text{diagonal}(AP_{L})$

######  Theorem A.13.

The diagonal elements of attention matrix of 2-layer PST can express $C_{3}$,
3-layer PST can express $C_{4}$, 4-layer PST can express $C_{5},C_{6}$,
6-layer PST can express $C_{7}$.

###### Proof.

It is a direct conjecture of Theorem A.12 as $C_{L+1}=\text{diagonl}(AP_{L})$
and $\forall k,P_{L}\in{\mathbb{Y}}^{k}\Rightarrow
AP_{L}\in{\mathbb{Y}}^{k+1}$ ∎

##  Appendix B Expressivity Comparision with Other Models

Algorithm A is considered more expressive than algorithm B if it can
differentiate between all pairs of graphs that algorithm B can distinguish. If
there is a pair of links that algorithm A can distinguish while B cannot and A
is more expressive than B, we say that A is strictly more expressive than B.
We will first demonstrate the greater expressivity of our model by using PST
to simulate other models. Subsequently, we will establish the strictness of
our model by providing a concrete example.

Our transformer incorporates inner products of coordinates, which naturally
allows us to express shortest path distances and various node-to-node distance
metrics. These concepts are discussed in more detail in Section 5.1. This
naturally leads to the following theorem, which compares our PST with GIN (Xu
et al., 2019a).

######  Theorem B.1.

A $k$-layer Point Set Transformer is strictly more expressive than a $k$-layer
GIN.

###### Proof.

We first prove that one PST layer can simulate an GIN layer.

Given node features $s_{i}$ and $v_{i}$. Without loss of generality, we can
assume that one channel of $v_{i}$ contains $U\text{diag}(\Lambda^{1}/2)$. The
sv-mixer can simulate an MLP function applied to $s_{i}$. Leading to
$s_{i}^{\prime}$. A GIN layer will then update node representations as
follows,

$s_{i}\leftarrow s_{i}^{\prime}+\sum_{j\in N(i)}s_{j}^{\prime}$ (92)

By inner products of coordinates, the attention matrix can express the
adjacency matrix. By setting $W_{q}^{s},W_{k}^{s}=0$, and
$W_{q}^{v},W_{k}^{v}$ be a diagonal matrix with only the diagonal elements at
the row corresponding the the channel of $U\text{diag}(\Lambda^{1}/2)$.

$K_{ij}=(W_{q}^{s}s_{i}\odot
W_{k}^{s}s_{j})\|\text{diagonal}(W_{q}^{v}v_{i}^{T}v_{j}W_{k}^{v})\to\langle\text{diag}(\Lambda^{1}/2)U_{i},\text{diag}(\Lambda^{1}/2)U_{j}\rangle=A_{ij}$
(93)

Let MLP express an identity function.

$\text{Atten}_{ij}=\text{MLP}(K_{ij})\to A_{ij}$ (94)

The attention layer will produce

$s_{i}\leftarrow\sum_{j}A_{ij}s_{j}^{\prime}=\sum_{j\in N(i)}s_{j}^{\prime}$
(95)

with residual connection, the layer can express GIN

$s_{i}\leftarrow s_{i}^{\prime}+s_{i}=s_{i}^{\prime}+\sum_{j\in
N(i)}s_{j}^{\prime}$ (96)

Moreover, as shown in Theorem 5.3, MPNN cannot compute shortest path distance,
while PST can. So PST is strictly more expressive. ∎

Moreover, our transformer is strictly more expressive than some representative
graph transformers, including Graphormer (Ying et al., 2021) and GPS with RWSE
as structural encoding (Rampásek et al., 2022).

######  Theorem B.2.

A $k$-layer Point Set Transformer is strictly more expressive than a $k$-layer
Graphormer and a $k$-layer GPS.

###### Proof.

We first prove that $k$-layer Point Set Transformer is more expressive than a
$k$-layer Graphormer and a $k$-layer GPS.

In initialization, besides the original node feature, Graphormer further add
node degree features and GPS further utilize RWSE. Our PST can add these
features with the first sv-mixer layer.

$s_{i}^{\prime}\leftarrow\text{MLP}_{1}(s_{i}\|\text{diagonal}(W_{1}v_{i}^{T}v_{i}W_{2}^{T}))$
(97)

Here, $\text{diagonal}(W_{1}v_{i}v_{i}^{T}W_{2}^{T})$ add coordinate inner
products, which can express RWSE (diagonal elements of random walk matrix) and
degree (see Appendix D), to node feature.

Then we are going to prove that one PST layer can express one GPS and one
Graphormer layer. PST’s attention matrix is as follows,

$\text{Atten}_{ij}=\text{MLP}(K_{ij}),\quad K_{ij}=(W_{q}^{s}s_{i}\odot
W_{k}^{s}s_{j})\|\text{diagonal}(W_{q}^{v}v_{i}^{T}v_{j}W_{k}^{v})\to\langle\text{diag}(\Lambda^{1}/2)U_{i},\text{diag}(\Lambda^{1}/2)U_{j}\rangle$
(98)

The Hadamard product $(W_{q}^{s}s_{i}\odot W_{k}^{s}s_{j})$ with MLP can
express the inner product of node representations used in Graphormer and GPS.
The inner product of coordinates can express adjacency matrix used in GPS and
Graphormer and shortest path distance used in Graphormer. Therefore, PST’
attention matrix can express the attention matrix in GPS and Graphormer.

To prove strictness, Figure 2(c) in (Zhang et al., 2023b) provides an example.
As PST can capture resistance distance and simulate 1-WL, so it can
differentiate the two graphs according to Theorem 4.2 in (Zhang et al.,
2023b). However, Graphormer cannot distinguish the two graphs, as proved in
(Zhang et al., 2023b).

For GPS, Two graphs in Figure 2(c) have the same RWSE: RWSE is

$\text{diagonal}(\hat{U}\text{diag}(\hat{\Lambda}^{k})\hat{U}^{T}),k=1,2,3,...,$
(99)

where the eigendecomposition of normalized adjacency matrix
$D^{-1/2}AD^{-1/2}$ is $\hat{U}$. By computation, we find that two graphs
share the same $\hat{\Lambda}$. Moroever,
$\text{diagonal}(\hat{U}\text{diag}(\hat{\Lambda}^{k})\hat{U}^{T})$ are equal
in two graphs for $k=0,1,2,...,9$, where $9$ is the number of nodes in graphs.
$\Lambda^{k}$ and
$\text{diagonal}(\hat{U}\text{diag}(\hat{\Lambda}^{k})\hat{U}^{T})$ with
larger $k$ are only linear combinations of $\Lambda^{k}$ and thus
$\text{diagonal}(\hat{U}\text{diag}(\hat{\Lambda}^{k})\hat{U}^{T})$ for
$k=0,1,...,9$. So the RWSE in the two graphs are equal and equivalent to
simply assigning feature $h_{1}$ to the center node and feature $h_{2}$ to
other nodes in two graphs. Then GPS simply run a model be a submodule of
Graphormer on the graph and thus cannot differentiate the two graphs either. ∎

Even against a highly expressive method such as 2-FWL, our models can surpass
it in expressivity with a limited number of layers:

######  Theorem B.3.

For all $K>0$, a graph exists that a $K$-iteration 2-FWL method fails to
distinguish, while a $1$-layer Point Set Transformer can.

###### Proof.

It is a direct corollary of Theorem 5.2. ∎

##  Appendix C Some Graph Transformers Fail to Compute Shortest Path Distance

First, we demonstrate that computing inner products of node representations
alone cannot accurately determine the shortest path distance when the node
representations are permutation-equivariant. Consider Figure 2 as an
illustration. In cases where node representations exhibit permutation-
equivariance, nodes $v_{2}$ and $v_{3}$ will share identical representations.
Consequently, the pairs $(v_{1},v_{2})$ and $(v_{1},v_{3})$ will yield the
same inner products of node representations, despite having different shortest
path distances. Consequently, it becomes evident that the attention matrices
of some Graph Transformers are incapable of accurately computing the shortest
path distance.

######  Theorem C.1.

GPS with RWSE (Rampásek et al., 2022) and Graphormer without shortest path
distance encoding cannot compute shortest path distance with the elements of
adjacency matrix.

###### Proof.

Their adjacency matrix elements are functions of the inner products of node
representations and the adjacency matrix.

$\text{Atten}_{ij}=\langle s_{i},s_{j}\rangle|\\!|A_{ij}.$ (100)

This element is equal for the node pair $(v_{1},v_{2})$ and $(v_{1},v_{3})$ in
Figure 2. However, two pairs have different shortest path distances. ∎

Furthermore, while Graph Transformers gather information from the entire
graph, they may not have the capacity to emulate multiple MPNNs with just a
single transformer layer. To address this, we introduce the concept of a
vanilla Graph Transformer, which applies a standard Transformer to nodes using
the adjacency matrix for relative positional encoding. This leads us to the
following theorem.

######  Theorem C.2.

For all $k\in{\mathbb{N}}$, there exists a pair of graph that $k+1$-layer MPNN
can differentiate while $k$-layer MPNN and $k$-layer vanilla Graph Transformer
cannot.

###### Proof.

Let $H_{l}$ denote a circle of $l$ nodes. Let $G_{l}$ denote a graph of two
components, one is $H_{\lfloor l/2\rfloor}$ and the other is $H_{\lceil
l/2\rceil}$. Let $H_{l}^{\prime}$ denote adding a unique feature $1$ to a node
in $H_{l}$ (as all nodes are symmetric for even $l$, the selection of node
does not matter), and $G_{l}^{\prime}$ denote adding a unique feature $1$ to
one node in $G_{l}$. All other nodes have feature $0$. Now we prove that

######  Lemma C.3.

For all $K\in{\mathbb{N}}$, $(K+1)$-layer MPNN can distinguish
$H^{\prime}_{4(K+1)}$ and $G^{\prime}_{4(K+1)}$, while $K$-layer MPNN and
$K$-layer vanilla Graph Transformer cannot distinguish.

Given $H^{\prime}_{4(K+1)}$, $G^{\prime}_{4(K+1)}$, we assign each node a
color according to its distance to the node with extra label $1$: $c_{0}$ (the
labeled node itself), $c_{1}$ (two nodes connected to the labeled node),
$c_{2}$ (two nodes whose shortest path distance to the labeled node is $2$),…,
$c_{K}$ (two nodes whose shortest path distance to the labeled node is $K$),
$c_{>K}$ (nodes whose shortest path distance to the labeled node is larger
than $K$). Now by simulating the process of MPNN, we prove that at $k$-th
layer $k<=K$, $\forall i\leq k$, $c_{i}$ nodes have the same representation
(denoted as $h^{k}_{i}$), respectively, $c_{k+1},c_{k+2},...,c_{K},c_{>K}$
nodes all have the same representation (denoted as $h^{k}_{k+1}$).

Initially, all $c_{0}$ nodes have representation $h_{0}^{0}$, all other nodes
have representation $h_{1}^{0}$ in both graph.

Assume at $k$-th layer, $\forall i\leq k$, $c_{i}$ nodes have the same
representation $h^{k}_{i}$, respectively, $c_{k+1},c_{k+1},...,c_{K},c_{>K}$
nodes all have the same representation $h^{k}_{k+1}$. At $k+1$-th layer,
$c_{0}$ node have two neighbors of representation $h_{1}^{k}$. all
$c_{i},1<i<=k$ node two neighbors of representations $h^{k}_{i-1}$ and
$h^{k}_{i+1}$, respectively. $c_{k+1}$ nodes have two neighbors of
representation $h^{k}_{k}$ and $h^{k}_{k+1}$. All other nodes have two
neighbors of representation $h^{k}_{k+1}$. So $c_{i},i\leq k+1$ nodes have the
same representation (denoted as $h^{k+1}_{i}$), respectively,
$c_{k+1+1},...,c_{K},c_{>K}$ nodes all have the same representation (denoted
as $h^{k}_{k+1}$).

The same induction also holds for $K$-layer vanilla graph transformer.

However, in the $K+1$-th message passing layer, only one node in $G_{4(K+1)}$
is of shortest path distance $K+1$ to the labeled node. It also have two
neighbors of representation $h^{K}_{K}$. While such a node is not exist in
$H_{4(K+1)}$. So ($K+1$)-layer MPNN can distinguish them. ∎

The issue with a vanilla Graph Transformer is that, although it collects
information from all nodes in the graph, it can only determine the presence of
features in 1-hop neighbors. It lacks the ability to recognize features in
higher-order neighbors, such as those in 2-hop or 3-hop neighbors. A
straightforward solution to this problem is to manually include the shortest
path distance as a feature. However, our analysis highlights that aggregating
information from the entire graph is insufficient for capturing long-range
interactions.

Figure 2: The failure of using inner products of permutation-equivariant node representations to predict shortest path distance. $v_{2}$ and $v_{3}$ have equal node representations due to symmetry. Therefore, $(v_{1},v_{2})$ and $(v_{1},v_{3})$ will have the same inner products of node representations but different shortest path distance. Table 5: Connection between existing structural embeddings and our parameterized coordinates. The eigendecomposition are $\hat{A}\leftarrow\hat{U}\hat{\Lambda}\hat{U}$, $D-A\leftarrow\tilde{U}\tilde{\Lambda}\tilde{U}^{T}$, $A\leftarrow U\Lambda U^{T}$. $d_{i}$ denote the degree of node $i$. Method |  Description |  Connection
---|---|---
Random walk matrix (Li et al., 2020; Dwivedi et al., 2023; Rampásek et al., 2022) |  $k$-step random walk matrix is $(D^{-1}A)^{k}$, whose element $(i,j)$ is the probability that a $k$-step random walk starting from node $i$ ends at node $j$. |  $(D^{-1}A)^{k}_{ij}$ $=(D^{-1/2}(\hat{A})^{k}D^{1/2})_{ij}$ $=\sqrt{\frac{d_{j}}{d_{i}}}\langle\hat{U}_{i},\text{diag}(\hat{\Lambda}^{k})\hat{U}_{j}\rangle$
Heat kernel matrix (Mialon et al., 2021) |  Heat kernel is a solution of the heat equation. Its element $(i,j)$ represent how much heat diffuse from node $i$ to node $j$ |  $\\!(\\!I\\!+\\!\tilde{U}(\text{diag}(\exp(-t\tilde{\Lambda}))\\!-\\!I)\tilde{U}^{T})_{ij}$ $=\\!\\!\delta_{ij}\\!+\\!\langle\tilde{U}_{i},(\text{diag}(\exp(-t\tilde{\Lambda}))\\!-\\!I)\tilde{U}_{j}\rangle$
Resistance distance (Zhang & Li, 2021; Zhang et al., 2023b) |  Its element $(i,j)$ is the resistance between node $i,j$ considering the graph as an electrical network. It is also the pseudo-inverse of laplacian matrix $L$, |  $(\tilde{U}\text{diag}(\tilde{\Lambda}^{-1})\tilde{U}^{T})_{ij}$ $=\langle\tilde{U}_{i},\text{diag}(\tilde{\Lambda}^{-1})\tilde{U}_{j}\rangle$
Equivariant and stable laplacian PE (Wang et al., 2022) |  The encoding of node pair $i,j$ is $\|1_{K}\odot(U_{i}-U_{j})\|$, where $1_{K}$ means a vector $\in{\mathbb{R}}^{r}$ with its elements coresponding to $K$ largest eigenvalue of $L$ |  $\|1_{K}\odot(U_{i}-U_{j})\|^{2}$ $=\langle U_{i},\text{diag}(1_{K})U_{i}\rangle$ $+\langle U_{j},\text{diag}(1_{K})U_{j}\rangle$ $-2\langle U_{i},\text{diag}(1_{K})U_{j}\rangle$
Degree and number of triangular (Bouritsas et al., 2023) |  $d_{i}$ is the number of edges, and $t_{i}$ is the number of triangular rooted in node $i$. |  $d_{i}=\langle U_{i},\text{diag}(\Lambda^{2})U_{j}\rangle$. $t_{i}=\langle U_{i},\text{diag}(\Lambda^{3})U_{j}\rangle$

##  Appendix D Connection with Structural Embeddings

We show the equivalence between the structural embeddings and the inner
products of our PSRD coordinates in Table 5. The inner products of PSRD
coordinates can unify a wide range of positional encodings, including random
walk (Li et al., 2020; Dwivedi et al., 2023; Rampásek et al., 2022), heat
kernel (Mialon et al., 2021), and resistance distance (Zhang & Li, 2021; Zhang
et al., 2023b).

##  Appendix E Datasets

Table 6: Statistics of the datasets. #Nodes and #Edges denote the number of nodes and edges per graph. In split column, ’fixed’ means the dataset uses the split provided in the original release. Otherwise, it is of the formal training set ratio/valid ratio/test ratio. | #Graphs | #Nodes | #Edges | Task | Metric | Split
---|---|---|---|---|---|---
Synthetic | 5,000 | 18.8 | 31.3 | Node Regression | MAE | 0.3/0.2/0.5.
QM9 | 130,831 | 18.0 | 18.7 | Regression | MAE | 0.8/0.1/0.1
ZINC | 12,000 | 23.2 | 24.9 | Regression | MAE | fixed
ZINC-full | 249,456 | 23.2 | 24.9 | Regression | MAE | fixed
ogbg-molhiv | 41,127 | 25.5 | 27.5 | Binary classification | AUC | fixed
MUTAG | 188 | 17.9 | 39.6 | classification | Accuracy | 10-fold cross validataion
PTC-MR | 344 | 14.3 | 14.7 | classification | Accuracy | 10-fold cross validation
PROTEINS | 1113 | 39.1 | 145.6 | classification | Accuracy | 10-fold cross validataion
IMDB-BINARY | 1000 | 19.8 | 193.1 | classification | Accuracy | 10-fold cross validataion
PascalVOC-SP | 11,355 | 479.4 | 2710.5 | Node Classification | Macro F1 | fixed
Peptides-func | 15,535 | 150.9 | 307.3 | Classification | AP | fixed
Peptides-struct 1 | 15,535 | 150.9 | 307.3 | Regression | MAE | fixed

We summarize the statistics of our datasets in Table 6. Synthetic is the
dataset used in substructure counting tasks provided by Huang et al. (2023b),
they are random graph with the count of substructure as node label. QM9 (Wu et
al., 2017), ZINC (Gómez-Bombarelli et al., 2016), and ogbg-molhiv are three
datasets of molecules. QM9 use 13 quantum chemistry property as the graph
label. It provides both the graph and the coordinates of each atom. ZINC
provides graph structure only and aim to predict constrained solubility. Ogbg-
molhiv is one of Open Graph Benchmark dataset, which aims to use graph
structure to predict whether a molecule can inhibits HIV virus replication. We
further use MUTAG, PTC-MR, PROTEINS, and IMDB-BINARY from TU database (Ivanov
et al., 2019). MUTAG comprises 188 mutagenic aromatic and heteroaromatic nitro
compounds. PROTEINS represents secondary structure elements as nodes with
edges between neighbors in amino-acid sequence or 3D space. PTC involves 344
chemical compounds, classifying carcinogenicity for rats. IMDB-BINARY features
ego-networks for actors/actresses in movie collaborations, classifying movie
genre graphs. We also use three datasets in Long Range Graph Benchmark
(Dwivedi et al., 2022b). They consists of larger graphs. PascalVOC-SP comes
from the computer vision domain. Each node in it representation a superpixel
and the task is to predict the semantic segmentation label for each node.
Peptide-func and peptide struct are peptide molecular graphs. Task in
Peptides-func is to predict the peptide function. Peptides-struct is to
predict 3D properties of the peptide. PTC is a collection of 344 chemical
compounds represented as graphs which report the carcinogenicity for rats.
There are 19 node labels for each node.

##  Appendix F Experimental Details

Our code is available in supplementary material. Our code is primarily based
on PyTorch (Paszke et al., 2019) and PyG (Fey & Lenssen, 2019). All our
experiments are conducted on NVIDIA RTX 3090 GPUs on a linux server. We use l1
loss for regression tasks and cross entropy loss for classification tasks. We
select the hyperparameters by running optuna (Akiba et al., 2019) to optimize
the validation score. We run each experiment with 8 different seeds, reporting
the averaged results at the epoch achieving the best validation metric. For
optimization, we use AdamW optimizer and cosine annealing scheduler.
Hyperparameters for datasets are shown in Table 7. All PST and PSDS models
(except these in ablation study) decompose laplacian matrix for coordinates.

Table 7: Hyperparameters of our model for each dataset. #warm means the number of warmup epochs, #cos denotes the number of cosine annealing epochs, gn denotes the magnitude of the gaussian noise injected into the point coordinates, hiddim denotes hidden dimension, bs means batch size, lr represents learning rate, and #epoch is the number of epochs for training.  dataset | #warm | #cos | wd | gn | #layer | hiddim | bs | lr | #epoch | #param
---|---|---|---|---|---|---|---|---|---|---
Synthetic | 10 | 15 | 6e-4 | 1e-6 | 9 | 96 | 16 | 0.0006 | 300 | 961k
qm9 | 1 | 40 | 1e-1 | 1e-5 | 8 | 128 | 256 | 0.001 | 150 | 1587k
ZINC | 17 | 17 | 1e-1 | 1e-4 | 6 | 80 | 128 | 0.001 | 800 | 472k
ZINC-full | 40 | 40 | 1e-1 | 1e-6 | 8 | 80 | 512 | 0.003 | 400 | 582k
ogbg-molhiv | 5 | 5 | 1e-1 | 1e-6 | 6 | 96 | 24 | 0.001 | 300 | 751k
MUTAG | 20 | 1 | 1e-7 | 1e-4 | 2 | 48 | 64 | 2e-3 | 70 | 82k
PTC-MR | 25 | 1 | 1e-1 | 1e-3 | 4 | 16 | 64 | 3e-3 | 70 | 15k
PROTEINS | 25 | 1 | 1e-7 | 3e-3 | 2 | 48 | 8 | 1.5e-3 | 80 | 82k
IMDB-BINARY | 35 | 1 | 1e-7 | 1e-5 | 3 | 48 | 64 | 3e-3 | 80 | 100k
PascalVOC-SP | 5 | 5 | 1e-1 | 1e-5 | 4 | 96 | 6 | 0.001 | 40 | 527k
Peptide-func | 40 | 20 | 1e-1 | 1e-6 | 6 | 128 | 2 | 0.0003 | 80 | 1337k
Peptide-struct | 40 | 20 | 1e-1 | 1e-6 | 6 | 128 | 2 | 0.0003 | 40 | 1337k

ZINC, ZINC-full, PascalVOC-SP, Peptide-func, and Peptide-struct have 500k
parameter budgets. Other datasets have no parameter limit. Graphormer (Ying et
al., 2021) takes 47000k parameters on ogbg-molhiv. 1-2-3-GNN takes 929k
parameters on qm9. Our PST follows these budgets on ZINC, ZINC-full and
PascalVOC-SP. However, on the peptide-func and peptide-struct datasets, we
find that hidden dimension is quite crucial for good performance. So we use a
comparable number of hidden dimension and transformer layers. This leads to
about 1M parameters because our PST employs two sets of parameters (one for
scalar and one for vector), which resulted in twice the parameters with the
same hidden dimension and number of transformer layers. We conduct experiments
with baselines with larger hidden dimensions for these datasets. The results
are shown in Table 8. When the PST and baselines are all to 1M parameters, out
PST outperforms baselines with the same parameter budget 1M, and our method is
effective on the two datasets.

Table 8: Results on peptide-func and peptide-struct dataset with 1M parameter budget. | peptide-func | peptide-struct
---|---|---
Graph-MLPMixer | $0.6970\pm 0.0080$ | $0.2475\pm 0.0015$
GraphGPS | $0.6535\pm 0.0041$ | $0.2500\pm 0.0005$
PST | $0.6984\pm 0.0051$ | $0.2470\pm 0.0015$

Other datasets we explored do not have explicit parameter constraints, and
it’s worth noting that our PST has fewer parameters compared to representative
baselines in these cases. Hyperparameter Configuration:

Our experiments involved tuning seven hyperparameters: depth (4, 8), hidden
dimension (64, 256), learning rate (0.0001, 0.003), number of warmup epochs
(0, 40), number of cosine annealing epochs (1, 20), magnitude of Gaussian
noise added to input (1e-6, 1e-4), and weight decay (1e-6, 1e-1). We observed
that [1] also used seven hyperparameters in their setup. Batch size was
determined based on GPU memory constraints and was not a parameter that we
optimized.

##  Appendix G Architecture

Figure 3: The pipeline of parameterized SRD. We first decompose Laplacian
matrix or other matrice for the non-zero eigenvalue and the corresponding
eigenvectors. Then the eigenvalue is transformed with DeepSet (Segol & Lipman,
2020). Multiply the transformed eigenvalue and the eigenvector leads to
coordinates. Figure 4: Architecture of Point Set Transformer (PST) (a) PST
contains several layers. Each layer is composed of an scalar-vector (sv)-mixer
and an attention layer. (b) The architecture of sv-mixer. (c) The architecture
of attention layer. $s_{i}$ and $s_{i}^{\prime}$ denote the scalar
representations of node $i$, and $\vec{v}_{i}$ and $\vec{v}_{i}^{\prime}$
denote the vector representations. $x_{i}$ is the initial features of node
$i$. $Q_{i}$ and point coordinates of node $i$ produced by parameterized SRD
in Section 3.2.

The architecture of parameterized SRD is shown in Figure 3. As illustrated in
Section 3.2, it first do eigendecomposition for non-zero eigenvalues and the
corresponding eigenvectors, then use DeepSet (Segol & Lipman, 2020) to process
the eigenvalues, leading to coordinates with multiple channels. The
architecture of PST is shown in Figure 4. As illustrated in Section 4, it is
composed of scalar-vector mixers and attention layers.

##  Appendix H Ablation

To assess the design choices made in our Point Set Transformer (PST), we
conducted ablation experiments. First, we replace the PSRD coordinates (see
Section 3.2) with SRD coordinates, resulting in a reduced version referred to
as the PST-gc model. Additionally, we introduced a variant called PST-
onelayer, which is distinct from PST in that it only computes the attention
matrix once and does not combine information in scalar and vector features.
Furthermore, PST decompose Laplacian matrix by default to produce coordinates.
PST-adj uses adjacency matrix instead. Similar to PST, PSDS takes node
coordinates as input. However, it use DeepSet (Segol & Lipman, 2020) rather
than transformer as the set encoder. For better comparison, we also use our
strongest baseline on QM9 dataset, DF (Zhou et al., 2023).

The results of the ablation study conducted on the QM9 dataset are summarized
in Table 2. Notably, PST-gc exhibits only a slight increase in test loss
compared to PST, and even outperforms PST on $4$ out of $12$ target metrics,
highlighting the effectiveness of the Graph as Point Set approach with vanilla
symmetric rank decomposition. In contrast, PST-onelayer performs significantly
worse, underscoring the advantages of PST over previous methods that augment
adjacency matrices with spectral features. PST-adj and PST-normadj achieves
similar performance to PST, illustrating that the choice of matrix to
decompose does not matter. DeepSet performs worse than PST, but it still
outperforms our strongest baseline DF, showing the potential of combining set
encoders other than transformer with our convertion from graph to set. On the
long-range graph benchmark, PST maintains a significant performance edge over
PST-onelayer. However, it’s worth noting that the gap between PST and PST-gc
widens, further confirming the effectiveness of gc in modeling long-range
interactions.

Table 9: Ablation study on qm9 dataset.

| $\mu$ | $\alpha$ | $\varepsilon_{\text{homo}}$ | $\varepsilon_{\text{lumo}}$ | $\Delta\varepsilon$ | $R^{2}$ | ZPVE | $U_{0}$ | $U$ | $H$ | $G$ | $C_{v}$
---|---|---|---|---|---|---|---|---|---|---|---|---
Unit |  $10^{-1}$D |  $10^{-1}$$a_{0}^{3}$ |  $10^{-2}$meV |  $10^{-2}$meV |  $10^{-2}$meV | $a_{0}^{2}$ |  $10^{-2}$meV | meV | meV | meV | meV |  $10^{-2}$cal/mol/K
PST | $3.19_{\pm 0.04}$ | $1.89_{\pm 0.04}$ | $5.98_{\pm 0.09}$ | $5.84_{\pm 0.08}$ | $8.46_{\pm 0.07}$ | $13.08_{\pm 0.16}$ | $0.39_{\pm 0.01}$ | $3.46_{\pm 0.17}$ | $3.55_{\pm 0.10}$ | $3.49_{\pm 0.20}$ | $3.55_{\pm 0.17}$ | $7.77_{\pm 0.15}$
PST-onelayer | $3.72_{\pm 0.02}$ | $2.25_{\pm 0.05}$ | $6.62_{\pm 0.11}$ | $6.67_{\pm 0.07}$ | $9.37_{\pm 0.15}$ | $15.95_{\pm 0.29}$ | $0.55_{\pm 0.01}$ | $3.46_{\pm 0.06}$ | $3.50_{\pm 0.14}$ | $3.50_{\pm 0.03}$ | $3.45_{\pm 0.07}$ | $9.62_{\pm 0.24}$
PST-gc | $3.34_{\pm 0.02}$ | $1.93_{\pm 0.03}$ | $6.08_{\pm 0.11}$ | $6.10_{\pm 0.10}$ | $8.65_{\pm 0.10}$ | $13.71_{\pm 0.12}$ | $0.40_{\pm 0.01}$ | $3.38_{\pm 0.13}$ | $3.43_{\pm 0.12}$ | $3.33_{\pm 0.08}$ | $3.29_{\pm 0.11}$ | $8.04_{\pm 0.15}$
PST-adj | $3.16_{\pm 0.02}$ | $1.86_{\pm 0.01}$ | $6.31_{\pm 0.06}$ | $6.10_{\pm 0.05}$ | $8.84_{\pm 0.01}$ | $13.60_{\pm 0.09}$ | $0.39_{\pm 0.01}$ | $3.59_{\pm 0.12}$ | $3.73_{\pm 0.08}$ | $3.65_{\pm 0.06}$ | $3.60_{\pm 0.016}$ | $7.62_{\pm 0.21}$
PST-normadj | $3.22_{\pm 0.04}$ | $1.85_{\pm 0.02}$ | $5.97_{\pm 0.23}$ | $6.15_{\pm 0.07}$ | $8.79_{\pm 0.04}$ | $13.42_{\pm 0.15}$ | $0.41_{\pm 0.01}$ | $3.36_{\pm 0.25}$ | $3.41_{\pm 0.24}$ | $3.46_{\pm 0.18}$ | $3.38_{\pm 0.23}$ | $8.10_{\pm 0.12}$
PSDS | $3.53_{\pm 0.05}$ | $2.05_{\pm 0.02}$ | $6.56_{\pm 0.03}$ | $6.31_{\pm 0.05}$ | $9.13_{\pm 0.04}$ | $14.35_{\pm 0.02}$ | $0.41_{\pm 0.02}$ | $3.53_{\pm 0.11}$ | $3.49_{\pm 0.05}$ | $3.47_{\pm 0.04}$ | $3.56_{\pm 0.14}$ | $8.35_{\pm 0.09}$
DF | $3.46$ | $2.22$ | $6.15$ | $6.12$ | $8.82$ | $15.04$ | $0.46$ | $4.24$ | $4.16$ | $3.95$ | $4.24$ | $9.01$

Table 10: Ablation study on Long Range Graph Benchmark dataset. Model | PascalVOC-SP | Peptides-Func | Peptides-Struct
---|---|---|---
PST | $0.4010_{\pm 0.0072}$ | $0.6984_{\pm 0.0051}$ | $0.2470_{\pm 0.0015}$
PST-onelayer | $0.3229_{\pm 0.0051}$ | $0.6517_{\pm 0.0076}$ | $0.2634_{\pm 0.0019}$
PST-gc | $0.4007_{\pm 0.0039}$ | $0.6439_{\pm 0.0342}$ | $0.2564_{\pm 0.0120}$

##  Appendix I Scalability

We present training time per epoch and GPU memory consumption data in Table 11
and Table 12. Due to architecture, PST has higher time complexity than
existing Graph Transformers and does not scale well on large graphs like
pascalvoc-sp dataset. However, on the ZINC dataset, PST ranks as the second
fastest model, and its memory consumption is comparable to existing models
with strong expressivity, such as SUN and SSWL, and notably lower than PPGN.

Table 11: Training time per epoch and GPU memory consumption on zinc dataset with batch size 128. | PST | SUN | SSWL | PPGN | Graphormer | GPS | SAN-GPS
---|---|---|---|---|---|---|---
Time/s | 15.20 | 20.93 | 45.30 | 20.21 | 123.79 | 11.70 | 79.08
Memory/GB | 4.08 | 3.72 | 3.89 | 20.37 | 0.07 | 0.25 | 2.00
Table 12: Training time per epoch and GPU memory consumption on pascalvoc-sp dataset with batch size 6. | PST | SUN | SSWL | PPGN | Graphormer | GPS | SAN-GPS
---|---|---|---|---|---|---|---
Time/s | 15.20 | 20.93 | 45.30 | 20.21 | 123.79 | 11.70 | 79.08
Memory/GB | 4.08 | 3.72 | 3.89 | 20.37 | 0.07 | 0.25 | 2.00

##  Appendix J Results on TU datasets

Following the setting of Feng et al. (2022), we test our PST on four TU
datasets (Ivanov et al., 2019). The results are shown in Table 13. Baselines
include WL subtree kernel (Shervashidze et al., 2011), GIN (Xu et al., 2019a),
DGCNN (Zhang et al., 2018), GraphSNN (Wijesinghe & Wang, 2022), GNN-AK+ (Zhao
et al., 2022), and three variants of KP-GNN (Feng et al., 2022) (KP-GCN, KP-
GraphSAGE, and KP-GIN). We use 10-fold cross-validation, where 9 folds are for
training and 1 fold is for testing. The average test accuracy is reported. Our
PST consistently outperforms our baselines.

Table 13: TU dataset evaluation result. Method | MUTAG | PTC-MR | PROTEINS | IMDB-B
---|---|---|---|---
WL | 90.4$\pm$5.7 | 59.9$\pm$4.3 | 75.0$\pm$3.1 | 73.8$\pm$3.9
GIN | 89.4$\pm$5.6 | 64.6$\pm$7.0 | 75.9$\pm$2.8 | 75.1$\pm$5.1
DGCNN | 85.8$\pm$1.7 | 58.6 $\pm$2.5 | 75.5$\pm$0.9 | 70.0$\pm$0.9
GraphSNN | 91.24$\pm$2.5 | 66.96$\pm$3.5 | 76.51$\pm$2.5 | 76.93$\pm$3.3
GIN-AK+ | 91.30$\pm$7.0 | 68.20$\pm$5.6 | 77.10$\pm$5.7 | 75.60$\pm$3.7
KP-GCN | 91.7$\pm$6.0 | 67.1$\pm$6.3 | 75.8$\pm$3.5 | 75.9$\pm$3.8
KP-GraphSAGE | 91.7$\pm$6.5 | 66.5$\pm$4.0 | 76.5$\pm$4.6 | 76.4$\pm$2.7
KP-GIN | 92.2$\pm$6.5 | 66.8$\pm$6.8 | 75.8$\pm$4.6 | 76.6$\pm$4.2
PST | 94.4$\pm$3.5 | 68.8$\pm$4.6 | 80.7$\pm$3.5 | 78.9$\pm$3.6

##  Appendix K Point Set DeepSet

Besides Transformer, we also propose a DeepSet (Segol & Lipman, 2020)-Based
set encoder, Point Set DeepSet (PSDS), for point set to illustrate the
versatility of our graph-to-set method. Similar to PST, PSDS also operates
with points carrying two types of representations: scalars, which remain
invariant to coordinate orthogonal transformations, and vectors, which adapt
equivariantly to coordinate changes. For a point $i$, its scalar
representation is denoted by $s_{i}\in{\mathbb{R}}^{d}$, and its vector
representation is denoted by $v_{i}\in{\mathbb{R}}^{r\times d}$, where $d$ is
the hidden dimension, and $r$ is the rank of coordinates. $s_{i}$ is
initialized with the input node feature $X_{i}$, and $v_{i}$ is initialized
with the parameterized coordinates containing graph structural information, as
detailed in Section 3.2. Similar to DeepSet, PSDS transforms point
representations individually, aggregates them to produce global feature, and
combine global features and individual point representations to update point
representations.

Scalar-Vector Mixer. This component individually transforms point
representations. To enable the information exchange between vector and scalar
features, we design a mixer architecture as follows.

$\displaystyle s_{i}^{\prime}$
$\displaystyle\leftarrow\text{MLP}_{1}(s_{i}\|\text{diagonal}(W_{1}v_{i}^{T}v_{i}W_{2}^{T})),$
(101) $\displaystyle v_{i}^{\prime}$ $\displaystyle\leftarrow
v_{i}\text{diag}(\text{MLP}_{2}(s_{i}))W_{3}+v_{i}W_{4}$ (102)

Here, $W_{1},W_{2},W_{3},$ and $W_{4}\in\mathbb{R}^{d\times d}$ are learnable
matrices for mixing different channels of vector features. Additionally,
$\text{MLP}_{1}:\mathbb{R}^{2d\to d}$ and $\text{MLP}_{2}:\mathbb{R}^{d\to d}$
represent two multi-layer perceptrons transforming scalar representations. The
operation $\text{diagonal}(W_{1}v_{i}^{T}v_{i}W_{2})$ takes the diagonal
elements of a matrix, which translates vectors to scalars, while
$\text{diag}(\text{MLP}_{2}(s_{i}))v_{i}$ transforms scalar features into
vectors. As $v_{i}^{T}R^{T}Rv_{i}=v_{i}^{T}v_{i},\forall R\in O(r)$, the
scalar update is invariant to orthogonal transformations of the coordinates.
Similarly, the vector update is equivariant to $O(r)$.

Aggregator. This component aggregates individual point representations for
global features $s,v,vsq$.

$\displaystyle s$ $\displaystyle\leftarrow\sum_{i\in V}\text{MLP}_{3}(s_{i})$
(103) $\displaystyle v$ $\displaystyle\leftarrow\sum_{i\in V}v_{i}W_{5}$ (104)
$\displaystyle v_{sq}$ $\displaystyle\leftarrow\sum_{i\in
V}v_{i}W_{6}W_{7}v_{i}^{T}$ (105)

Here, $W_{5},W_{6}$ and $W_{7}\in{\mathbb{R}}^{d\times d}$ denote the linear
transformations vectors. $\text{MLP}_{3}:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$
is an MLP converting scalars. Global feature $s\in{\mathbb{R}}^{d}$ is scalar,
$v{\mathbb{R}}^{r\times d}$ is vector, and $v_{sq}\in{\mathbb{R}}^{r\times r}$
is the sum of square for each vector.

Point Representation Update. Each point representation is updated by combining
global features.

$\displaystyle s_{i}$ $\displaystyle\leftarrow\text{MLP}_{4}(s_{i}+s)$ (106)
$\displaystyle v_{i}$ $\displaystyle\leftarrow v_{sq}v_{i}+vW_{8}$ (107)

$s_{i}$ is combined with global scalar $s$ and transformed with an MLP
$\text{MLP}_{4}:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$. $v_{i}$ is combined with
$v_{sq}$ and $v$ with linear layer $W_{8}\in{\mathbb{R}}^{d\times d}$.

Pooling. After several layers, we pool all points’ scalar representations as
the set representation $s$.

$s\leftarrow\text{Pool}(\\{s_{i}|i\in V\\}),$ (108)

where Pool is pooling function like sum, mean, and max.