Graph as Point Set

Xiyuan Wang 1 Pan Li 2 Muhan Zhang 1

Abstract this category include Message Passing Neural Network

Graph is a fundamental data structure to model (MPNN) (Gilmer et al., 2017), a foundational framework
interconnections between entities. Set, on the con- for GNNs such as GCN (Kipf & Welling, 2017), GIN (Xu
arXiv:2405.02795v2 [[Link]] 30 May 2024

trary, stores independent elements. To learn graph et al., 2019a), and GraphSAGE (Hamilton et al., 2017).
representations, current Graph Neural Networks Subgraph-based GNNs (Zhang & Li, 2021; Huang et al.,
(GNNs) primarily use message passing to encode 2023b; Bevilacqua et al., 2022; Qian et al., 2022; Frasca
the interconnections. In contrast, this paper in- et al., 2022; Zhao et al., 2022; Zhang et al., 2023a) select
troduces a novel graph-to-set conversion method subgraphs from the whole graph and run MPNN within
that bijectively transforms interconnected nodes each subgraph. These models aggregate messages from
into a set of independent points and then uses neighbors to update the central nodes’ representations. Ad-
a set encoder to learn the graph representation. ditionally, Graph Transformers (GTs) integrate adjacency
This conversion method holds dual significance. information into the attention matrix (Mialon et al., 2021;
Firstly, it enables using set encoders to learn from Kreuzer et al., 2021; Wu et al., 2021; Dwivedi & Bresson,
graphs, thereby significantly expanding the de- 2020; Ying et al., 2021; Shirzad et al., 2023) (note that some
sign space of GNNs. Secondly, for Transformer, early GTs have options to not use adjacency matrix by using
a specific set encoder, we provide a novel and only positional encodings, but the performance is signif-
principled approach to inject graph information icantly worse (Dwivedi & Bresson, 2020)). Some recent
losslessly, different from all the heuristic struc- GTs even directly incorporate message-passing layers into
tural/positional encoding methods adopted in pre- their architectures (Rampásek et al., 2022; Kim et al., 2021).
vious graph transformers. To demonstrate the In summary, this paradigm relies on adjacency relationships
effectiveness of our approach, we introduce Point to facilitate information exchange among nodes.
Set Transformer (PST), a transformer architecture The second paradigm designs permutation-equivariant neu-
that accepts a point set converted from a graph as ral networks that directly take adjacency matrices as in-
input. Theoretically, PST exhibits superior expres- put. This category includes high-order Weisfeiler-Leman
sivity for both short-range substructure counting tests (Maron et al., 2019a), invariant graph networks (Maron
and long-range shortest path distance tasks com- et al., 2019b), and relational pooling (Chen et al., 2020).
pared to existing GNNs. Extensive experiments Additionally, various studies have explored manual feature
further validate PST’s outstanding real-world per- extraction from the adjacency matrix, including random
formance. Besides Transformer, we also devise walk structural encoding (Dwivedi et al., 2022a; Li et al.,
a Deepset-based set encoder, which achieves per- 2020), Laplacian matrix eigenvectors (Wang et al., 2022;
formance comparable to representative GNNs, af- Lim et al., 2023; Huang et al., 2023a), and shortest path dis-
firming the versatility of our graph-to-set method. tances (Li et al., 2020). However, these approaches typically
serve as data augmentation steps for other models, rather
than constituting an independent paradigm.
1. Introduction
Both paradigms heavily rely on adjacency information in
Graph, composed of interconnected nodes, has a wide range graph encoding. In contrast, this paper explores whether
of applications and has been extensively studied. In graph we can give up adjacency matrix in graph models while
machine learning, a central focus is to effectively lever- achieving competitive performance. As shown in Figure 1,
age node connections. Various architectures have arisen our innovative graph-to-set method converts interconnected
for graph tasks, exhibiting significant divergence in their nodes into independent points, subsequently encoded by a
approaches to utilizing adjacency information. set encoder like Transformer. Leveraging our symmetric
Two primary paradigms have evolved for encoding adja- rank decomposition, we break down the augmented adja-
cency information. The first paradigm involves message cency matrix A + D into QQT , wherein Q is constituted
passing between nodes via edges. Notable methods in by column-full-rank rows, each denoting a node coordinate.

1
 Graph As Point Set

𝑟 dimensions • SRD enables a practical conversion of graph problems

into set problems. SRD of a matrix is unique up to a single

Set Encoder
orthogonal transformation, while EVD is unique up to a
combination of orthogonal transformations within each
eigenspace. This difference allows SRD-based models to
Input Graph Point Set Set Encoder easily maintain symmetry, ensuring consistent predictions
Interlinked nodes Independent points with O(r)–equivariant for isomorphic graphs, while EVD-based methods (Lim
coordinates containing Transformer
full adjacency information et al., 2023) struggle because they need to deal with each
eigenspace individually, making them less suitable for
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-
graph-level tasks where eigenspaces vary between graphs.
dimension orthogonal transformations. • Due to the advantage of SRD, we can utilize set encoder
with coordinates to capture graph structure, thus expand-
This representation enables us to express the presence of ing the design space of GNN. Moreover, our method pro-
edges as inner products of coordinate vectors (Qi and Qj ). vides a principled way to add graph information to Trans-
Consequently, interlinked nodes can be transformed into formers. Note that previous GTs usually require multiple
independent points and supplementary coordinates without heuristic encodings together. Besides node positional en-
information loss. Theoretically, two graphs are isomorphic codings, they also use adjacency matrices: Grit (Ma et al.,
iff the two converted point sets are equal up to an orthogo- 2023) and graphit (Mialon et al., 2021) use random walk
nal transformation (because for any QQT = A + D, QR matrix (normalized adjacency) as relative positional en-
is also a solution where R is any orthogonal matrix). This coding (RPE). Graph Transformer (Dwivedi & Bresson,
equivalence empowers us to encode the set with coordinates 2020), Graphormer (Ying et al., 2021), and SAN (Kreuzer
in an orthogonal-transformation-equivariant manner, akin et al., 2021) use adjacency matrix as RPE. Dwivedi &
to E(3)-equivariant models designed for 3D geometric deep Bresson (2020)’s ablation shows that adjacency is crucial.
learning. Importantly, our approach is versatile, allowing GPS (Rampásek et al., 2022), Exphormer (Shirzad et al.,
for using any equivariant set encoder, thereby significantly 2023), higher-order Transformer (Kim et al., 2021), and
expanding the design space of GNNs. Furthermore, for GraphVit/MLP-Mixer (He et al., 2023) even directly in-
Transformer, a specific set encoder, our method offers a corporate message passing blocks which use adjacency
novel and principled way to inject graph information loss- matrix to guide message passing between nodes.
lessly. In Appendix D, we additionally show that it unifies In summary, this paper introduces a novel approach to graph
various heuristic structural/positional encodings in previous representation learning by converting interconnected graphs
GTs, including random walk (Li et al., 2020; Dwivedi et al., into independent points and subsequently encoding them
2023; Rampásek et al., 2022), heat kernel (Mialon et al., using an orthogonal-transformation-equivariant set encoder
2021), and resistance distance (Zhang et al., 2023b). like our Point Set Transformer. This innovative approach
To instantiate our method, we introduce an orthogonal- outperforms existing methods in both long- and short-range
transformation-equivariant Transformer, namely Point Set tasks, as validated by comprehensive experiments.
Transformer (PST), to encode the point set. PST provably
surpasses existing models in long-range and short-range ex-
2. Preliminary
pressivity. Extensive experiments verify these claims across For a matrix Z → Ra→b , we define Zi → Rb as the i-th row
synthetic datasets, graph property prediction datasets, and (as a column vector), and Zij → R as its (i, j) element. For a
long-range graph benchmarks. Specifically, PST outper- vector ! → Ra , diag(!) → Ra→a is the diagonal matrix with !
forms all baselines on QM9 (Wu et al., 2017) dataset. More- as its diagonal elements. And for S → Ra→a , diagonal(S) →
over, our graph-to-set method is not constrained to only one Ra represents the vector of its diagonal elements.
specific set encoder. We also propose a Deepset (Segol &
Lipman, 2020)-based model, which outperforms compara- Let G = (V, E, X) denote an undirected graph. Here, V =
ble to GIN (Xu et al., 2019b) on our datasets. {1, 2, 3, ..., n} is the set of n nodes, E ↑ V ↓ V is the
set of edges, and X → Rn→d is the node feature matrix,
Differences from eigendecomposition. Note that our whose v-th row Xv is of node v. The edge set E can also be
graph-to-set method is distinct from previous approaches represented using the adjacency matrix A → Rn→n , where
that decompose adjacency matrices for positional encod- Auv is 1 if the edge exists (i.e., (u, v) → E) and 0 otherwise.
ings (Dwivedi et al., 2023; Wang et al., 2022; Lim et al., A graph G can also be represented by the pair (V, A, X) or
2023; Bo et al., 2023). The key differences root in that (A, X). The degree matrix D is a diagonal matrix with node
previous methods primarily relied on eigendecomposition degree (sum of a row of matrix A) as the diagonal elements.
(EVD), whereas our method is based on symmetric rank
decomposition (SRD). Their differences are as follows: Given a permutation function ω : {1, 2, 3, ..., n} ↔

2
 Graph As Point Set

{1, 2, 3, ..., n}, the permuted graph is ω(G) = to poor generalization. To address this, we show that Sym-
(ω(A), ω(X)), where ω(A) → Rn→n , ω(A)ω(u)ω(v) = Auv , metric Rank Decomposition (SRD) can convert graph-level
and ω(X) → Rn→d , ω(X)ω(v) = Xv for all u, v → V . tasks into set-level tasks with perfect alignment. Since SRD
Essentially, the permutation ω reindex each node v to ω(v) only applies to positive semi-definite matrices, we use the
while preserving the original graph structure and node augmented adjacency matrix D + A, which is always posi-
features. Two graphs are isomorphic iff they can be mapped tive semi-definite (proof in Appendix A.2).
to each other through a permutation. Theorem 3.1. Given two graphs G = (V, A, X) and
Definition 2.1. Graphs G1 = (A1 , X1 ) and G2 = (A2 , X2 ) G ↑ = (V ↑ , A↑ , X ↑ ) with respective degree matrices D and
are isomorphic, denoted as G1 ↗ G2 , if there exists a permu- D↑ , G ↗ G ↑ iff ↘R → O(r), {{(Xv , RQv )|≃v → V }} =
tation ω such that ω(A1 ) = A2 and ω(X1 ) = X2 . {{(Xv↑ , Q↑v )|v → V ↑ }}, where Q and Q↑ are the SRD of D+A
and D↑ + A↑ respectively, and r is the rank of Q.
Isomorphic graphs can be transformed into each other by
merely reindexing their nodes. In graph tasks, models In this theorem, the graph G = (V, A, X) is converted to a
should assign the same prediction to isomorphic graphs. set of points {(Xv , Qv )|v → V }, where Xv is the original
node feature of v, and Qv , the v-th row of SRD of D + A,
Symmetric Rank Decomposition (SRD). Decomposing an is the r-dimensional coordinate of node v. Consequently,
matrix into two full-rank matrices is well-known (Puntanen two graphs are isomorphic iff their point sets are equal up to
et al., 2011). We further show that a positive semi-definite an orthogonal transformation. Intuitively, we can imagine
matrix can be decomposed into a full-rank matrix. that the graph is mapped into an r-dimensional space, where
Definition 2.2. (Symmetric Rank Decomposition, SRD) each node has a coordinate, and the inner product between
Given a (symmetric) positive semi-definite matrix L → two coordinates represents edge existence. This mapping
Rn→n of rank r, its SRD is Q → Rn→r , where L = QQT . is not unique, since we can freely rotate the coordinates
through an orthogonal transformation without changing in-
As L = QQT , rank(Q) = rank(L) = r, which implies that ner products. This conversion can be loosely likened to the
Q must be full column rank. Moreover, two SRDs of the reverse process of constructing molecular graph from atoms’
same matrix are equal up to an orthogonal transformation. 3D coordinates, where Euclidean distances between atoms
Let O(r) denote the set of orthogonal matrices in Rr→r . determine node connections in the graph.
Proposition 2.3. Matrices Q1 and Q2 in Rn→r are SRD of
Leveraging Theorem 3.1, we can convert a graph into a
the same matrix iff there exists R → O(r), Q1 = Q2 R.
set and employ a set encoder for encoding it. Our method
SRD is closely related to eigendecomposition. Let L = consistently produces representations for isomorphic graphs
U diag(!)U T denote the eigendecomposition of L, where when the encoder is orthogonal transformation-invariant.
! → Rr is the vector of non-zero eigenvalues, and U → The method’s expressivity hinges on the set encoder’s ability
Rn→r is the matrix whose columns are the corresponding to differentiate non-equal sets, with greater encoder power
eigenvectors. Q = U diag(!1/2 ) yields an SRD of L, where enhancing overall performance on graph tasks.
the superscript denotes element-wise square root operation.
3.2. Parameterized Coordinates
3. Graph as Point Set In this section, we enhance SRD’s practical performance
through parameterization. As shown in Section 2, SRD
In this section, we present our innovative method for convert-
can be implemented via eigendecomposition: Q =
ing graphs into sets of points. We first show that Symmetric
U diag(!1/2 ), where ! → Rr denotes non-zero eigenvalues
Rank Decomposition (SRD) can theoretically achieve this
of the decomposed matrix, and U → Rn→r denotes corre-
transformation: two graphs are isomorphic iff the sets of
sponding eigenvectors. To parameterize SRD, we replace
coordinates generated by SRD are equal up to orthogonal
the element-wise square root with a function f : Rr ↔ Rr .
transformations. Additionally, we parameterize SRD for bet-
This alteration further eliminates the constraint of non-
ter real-world performance. Proof details are in Appendix A.
negativity on eigenvalues and enables the use of various
symmetric matrices containing adjacency information to
3.1. Symmetric Rank Decomposition for Coordinates generate coordinates. Additionally, for model flexibility,
A natural approach to breaking down the interconnections the coordinates can include multiple channels, with each
between nodes is to decompose the adjacency matrix. While channel corresponding to a distinct eigenvalue function.
previous methods often used eigendecomposition outputs as Definition 3.2. (Parameterized SRD, PSRD) With a d-
supplementary node features, these features are not unique. channel eigenvalue functionf : Rr ↔ Rr→d and an adjacency
Consequently, models relying on them fail to provide con- function Z : Rn→n ↔ Rn→n producing symmetric matrices,
sistent predictions for isomorphic graphs, ultimately leading PSRD coordinate of a graph G = (V, A, X) is Q(Z(A), f) →

3
 Graph As Point Set

Rn→r→d , whose i-th channel is U diag(fi (!)) → Rn→r , nal transformations, and vectors, which adapt equivariantly
where ! → Rr , U → Rn→r are non-zero eigenvalues and to coordinate changes. For a point i, its scalar representation
corresponding eigenvectors of Z(A), and fi : Rr ↔ Rr is the is si → Rd , and its vector representation is vi → Rr→d , where
i-th channel of f . d is the hidden dimension, and r is the rank of coordinates.
si and vi are initialized with the input node feature Xi and
In the definition, Z maps adjacency matrix to its vari- PSRD coordinates (detailed in Section 3.2) containing graph
ants like Laplacian matrix, and f transforms eigenvalues. structure information, respectively.
Q(Z(A), f )u → Rr→d is node u’s coordinate. Similar to
SRD, PSRD can also convert the graph isomorphism prob- Similar to conventional transformers, PST comprises multi-
lems to set equality problems. ple layers. Each layer incorporates two key components:
Theorem 3.3. Given a permutation-equivariant adjacency Scalar-Vector Mixer. This component, akin to the feed-
function Z, for graphs G = (V, A, X) and G ↑ = (V ↑ , A↑ , X ↑ ) forward network in Transformer, individually transforms
• If eigenvalue function f is permutation-equivariant and point features. To enable information exchange between
G ↗ G ↑ , then two point sets with PSRD coordinates are vectors and scalars, we employ the following architecture.
equal up to an orthogonal transformation, i.e., ↘R → O(r),
{{Xv ,RQ(Z(A),f )v |v → V}}={{X↑v ,Q(Z(A↑),f )v |v → V ↑}}, s↑i ⇒ MLP1 (si ⇑diagonal(W1 viT vi W2T )), (1)
where r is the rank of coordinates. vi↑ ⇒ vi diag(MLP2 (si ))W3 + vi W4 (2)
• If Z is injective, for all d ⇐ 2, there exists a continuous
permutation-equivariant function f : Rr ↔ Rr→d that if Here, W1 , W2 , W3 , and W4 → Rd→d are learnable matri-
two point sets with PSRD coordinates are equal up to an ces for mixing different channels of vector features. Addi-
orthogonal transformation, G ↗ G ↑ . tionally, MLP1 : R2d↓d and MLP2 : Rd↓d represent two
multi-layer perceptrons transforming scalar representations.
Given permutation equivariant f and Z, the point sets with The operation diagonal(W1 viT vi W2 ) takes the diagonal ele-
PSRD coordinates are equal up to an orthogonal transforma- ments of a matrix, which translates vectors to scalars, while
tion for isomorphic graphs. Moreover, there exists f making vi diag(MLP2 (si )) transforms scalar features into vectors.
reverse true. Therefore, we can safely employ permutation- As viT RT Rvi = viT vi , ≃R → O(r), the scalar update is
equivariant eigenvalue functions, ensuring consistent pre- invariant to orthogonal transformations of the coordinates.
dictions for isomorphic graphs. An expressive eigenvalue Similarly, the vector update is equivariant to O(r).
function also allows for the lossless conversion of graph- Attention Layer. Akin to ordinary attention layers, this
level tasks into set problems. In implementation, we utilize component compute pairwise attention score to linearly
DeepSet (Segol & Lipman, 2020) due to its universal expres- combine point representations.
sivity for permutation-equivariant set functions. Detailed
architecture is shown in Figure 3 in Appendix G. Attenij = MLP((Wqs si → Wks sj )↑diagonal(Wqv viT vj Wkv )) (3)
In summary, we use SRD and its parameterized generaliza-
tion to decompose the adjacency matrix or its variants into Here, Wqs and Wqv denote the linear transformations for
coordinates. Thus, we transform a graph into a point set scalars and vectors queries, respectively, while Wks and Wkv
where each point represents a node and includes both the are for keys. The equation computes the inner products of
original node feature and the coordinates as its features. queries and keys, similar to standard attention mechanisms.
It is easy to see Attenij is also invariant to O(r).
4. Point Set Transformer Then we linearly combine point representations with atten-
tion scores as the coefficients:
Our method, as depicted in Figure 1, comprises two steps: ! !
converting the graph into a set of independent points and si ↓ Attenij s→j , vi ↓ Attenij vj→ (4)
encoding the set. Section 3 demonstrates the bijective trans- j j

formation of the graph into a set. To encode this point set,

we introduce a novel architecture, Point Set Transformer Each transformer layer is of time complexity O(n2 r) and
(PST), designed to maintain orthogonality invariance and space complexity O(n2 + nr).
deliver remarkable expressivity. Additionally, to highlight
Pooling. After several layers, we pool all points’ scalar
our method’s versatility, we propose a DeepSet (Segol &
representations as the set representation s.
Lipman, 2020)-based set encoder in Appendix K.
PST’s architecture is depicted in Figure 4 in Appendix G. s ⇒ Pool({si |i → V }), (5)
PST operates with two types of representations for each
point: scalars, which remain invariant to coordinate orthogo- where Pool is pooling function like sum, mean, and max.

4
 Graph As Point Set

5. Expressivity Theorem 5.2. Let ck (G)ij denote the color of node tuple
(i, j) of graph G at iteration k. Given graphs G = (A, X)
In this section, we delve into the theoretical expressivity and G ↑ = (A↑ , X ↑ ), for all K → N+ , if two node tuples (i, j)
of our methods. Our PSRD coordinates and the PST archi- in G and (i↑ , j ↑ ) in G ↑ have spd(i, j, A) < spd(i↑ , j ↑ , A↑ ) ∝
tecture exhibit strong long-range expressivity, allowing for 2K , then cK (G)ij ′= cK (G ↑ )i→ j → . Moreover, for all
efficient computation of distance metrics between nodes, L > 2K , there exists i, j, i↑ , j ↑ , such that spd(i, j, A) >
as well as short-range expressivity, enabling the counting spd(i↑ , j ↑ , A↑ ) ⇐ L while cK (G)ij = cK (G ↑ )i→ j → .
of paths and cycles rooted at each node. Therefore, our
model is more expressive than many existing models, in- In other words, K iterations of 2-FWL can distinguish pairs
cluding GIN (equivalent to the 1-WL test) (Xu et al., 2019b), of nodes with different spds, as long as that distance is at
PPGN (equivalent to the 2-FWL test, more expressive in most 2K . Moreover, K-iteration 2-FWL cannot differenti-
some cases) (Maron et al., 2019a), GPS (Rampásek et al., ate all tuples with spd > 2K from other tuples with different
2022), and Graphormer (Ying et al., 2021) (two representa- spds, which indicates that K-iteration 2-FWL is effective in
tive graph transformers). More details are in Appendix B. counting shortest path distances up to a maximum of 2K .
MPNN. Intuitively, each MPNN layer uses AX to update
5.1. Long Range Expressivity node representations X. However, this operation in general
This section demonstrates that the inner products of PSRD cannot compute AK unless the initial node feature X = I.
coordinates exhibits strong long-range expressivity, which K layers
" #$ %
PST inherits by utilizing inner products in attention layers.
X ↔ AX ↔ A2 X=AAX ↔ ... ↔ AK X=AAK↔1 X (8)
When assessing a model’s capacity to capture long-range
interactions (LRI), a key measure is its ability to compute Theorem 5.3. A graph pair exists that MPNN cannot dif-
shortest path distance (spd) between nodes. Since formally ferentiate, but their sets of all-pair spd are different.
characterizing LRI can be challenging, we focus on analyz-
ing models’ performance concerning this specific measure. If MPNNs can compute spd between node pairs, they should
We observe that existing models vary significantly in their be able to distinguish this graph pair from the sets of spd.
capacity to calculate spd. Moreover, we find an intuitive However, we show no MPNNs can distinguish the pair, thus
explaination for these differences: spd between nodes can proving that MPNNs cannot compute spd.
be expressed as spd(i, j, A) = arg mink {k|Akij > 0}, and Graph Transformers (GTs) are known for their strong long-
the ability to compute AK , the K-th power of the adjacency range capacities (Dwivedi et al., 2022b), as they can ag-
matrix A, can serve as a straightforward indicator. Different gregate information from the entire graph to update each
models need different number of layers to compute AK . node’s representation. However, aggregating information
PSRD coordinates. PSRD coordinates can capture arbitrar- from the entire graph is not equivalent to capturing the dis-
ily large shortest path distances through their inner products tance between nodes, and some GTs also fail to compute
in one step. To illustrate it, we decompose the adjacency spd between nodes. Details are in Appendix C. Note that
matrix as A = U diag(!)U T , and employ coordinates as U this slightly counter-intuitive results is because we take a
and U diag(!K ). Their inner products are as follows: new perspective to study long range interaction rather than
1 step showing GTs are weak in long range capacity.
" #$ %
U diag(!K )U T ↔ AK (6) Besides shortest path distances, our PSRD coordinates also
enables the unification of various structure encodings (dis-
Theorem 5.1. There exists permutation-equivariant func-
tance metrics between nodes), including random walk (Li
tions fk , k = 0, 1, 2, ..., K, such that for all graphs G =
et al., 2020; Dwivedi et al., 2023; Rampásek et al., 2022),
(A, X), the shortest path distance between node i, j is a
heat kernel (Mialon et al., 2021), resistance distance (Zhang
function of ⇓Q(A, f0 )i , Q(A, fk )j ⇔, k = 0, 1, 2, ...K, where
& Li, 2021; Zhang et al., 2023b). Further insights and details
Q(A, f ) is the PSRD coordinate defined in Section 3.2, K
are shown in Table 5 in Appendix D.
is the maximum shortest path distance between nodes.
2-FWL. A powerful graph isomorphic test, 2-Folklore- 5.2. Short Range Expressitivity
Weisfeiler-Leman Test (2-FWL), and its neural network
version PPGN (Maron et al., 2019a) produce node pair rep- This section shows PST’s expressivity in representative
resentations in a matrix X → Rn→n . X is initialized with A. short-range tasks: path and cycle counting.
Each layer updates X with XX. So intuitively, computing
AK takes ↖log2 K↙ layers. 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
↑log K↓ layers
" 2
#$ % 4, and a four-layer PST can count paths of length 5 and 6.
A ↔ A =AA ↔ A =A A ↔ ... ↔ AK =AK/2 AK/2
2 4 2 2
(7) Here, “count” means that the (i, j) element of the attention

5
 Graph As Point Set

matrix in the last layer can express the number of paths share resemblances: both involve unordered sets of 3-D co-
between nodes i and j. ordinate points as input and require models to produce pre-
dictions invariant/equivariant to orthogonal transformations
Therefore, with enough layers, our PST models can count and translations of coordinates. Several works (Chen et al.,
the number of paths of length ∝ 6 between nodes. Further- 2021; Winkels & Cohen, 2018; Cohen et al., 2018; Gasteiger
more, our PST can also count cycles. et al., 2021) introduce specialized equivariant convolution
Theorem 5.5. A one-layer PST can count cycles of length operators to preserve prediction symmetry, yet are later sur-
3, a three-layer PST can count cycles of length 4 and 5, and passed by models that learn both invariant and equivariant
a five-layer PST can count cycles of length 6 and 7. Here, representations for each point, transmitting these represen-
“count” means the representation of node i in the last layer tations between nodes. Notably, certain models (Satorras
can express the number of cycles involving node i. et al., 2021; Schütt et al., 2021; Deng et al., 2021; Wang &
Zhang, 2022) directly utilize vectors mirroring input coordi-
Therefore, with enough layers, PST can count the number of nate changes as equivariant features, while others (Thomas
cycles of length ∝ 7 between nodes. Given that even 2-FWL et al., 2018; Batzner et al., 2022; Fuchs et al., 2020; Hutchin-
is restricted to counting cycles up to length 7 (Fürer, 2017), son et al., 2021; Worrall et al., 2017; Weiler et al., 2018)
the cycle counting power of our Point Set Transformer is at incorporate high-order irreducible representations of the
least on par with 2-FWL. orthogonal group, achieving proven universal expressiv-
ity (Dym & Maron, 2021). Our Point Set Transformer
6. Related Work (PST) similarly learns both invariant and equivariant point
representations. However, due to the specific conversion
Graph Neural Network with Eigen-Decomposition. Our of point sets from graphs, PST’s architecture varies from
approach employs coordinates derived from the symmet- existing models. While translation invariance characterizes
ric rank decomposition (SRD) of adjacency or related ma- point clouds and molecules, graph properties are sensitive to
trices, differing from prior studies that primarily rely on coordinate translations in our method. Hence, we adopt in-
eigendecomposition (EVD). While both approaches have ner products of coordinates. Additionally, these prior works
similarities, SRD transforms the graph isomorphism prob- center on 3D point spaces, whereas our coordinates exist in
lem into a set problem bijectively, which is challenging high-dimensional space, rendering existing models and the-
for EVD, because SRD of a matrix is unique up to a single oretical expressivity results based on high-order irreducible
orthogonal transformation, while EVD is unique up to mul- representations incompatible with our framework.
tiple orthogonal transformations in different eigenspaces.
This key theoretical difference has profound implications for
model design. Early efforts, like Dwivedi et al. (2023), intro-
7. Experiments
duce eigenvectors into MPNNs’ input node feature (Gilmer In our experiments, we evaluate our model across three
et al., 2017), and subsequent works, such as Graph Trans- dimensions: substructure counting for short-range expres-
formers (GTs) (Dwivedi & Bresson, 2020; Kreuzer et al., sivity, real-world graph property prediction for practical per-
2021), incorporate eigenvectors as node positional encod- formance, and Long-Range Graph Benchmarks (Dwivedi
ings. However, due to the non-uniqueness of eigenvectors, et al., 2022b) to assess long-range interactions. Our primary
these models produce varying predictions for isomorphic model, Point Set Transformer (PST) with PSRD coordi-
graphs, limiting their generalization. Lim et al. (2023) par- nates derived from the Laplacian matrix, performs well
tially solve the non-uniqueness problem. However, their on all tasks. Moreover, our graph-to-set method is adapt-
solutions are limited to cases with constant eigenvalue mul- able to various configurations. In ablation study (see Ap-
tiplicity in graph tasks due to the property of EVD. On pendix H), another set encoders Point Set DeepSet (PSDS,
the other hand, approaches like Wang et al. (2022), Bo introduced in Appendix K), SRD coordinates different from
et al. (2023), and Huang et al. (2024) completely solve non- PSRD, and coordinates decomposed from the adjacency ma-
uniqueness and even apply permutation-equivariant func- trix and normalized adjacency matrix all demonstrate good
tions to eigenvalues, similar to our PSRD. However, these performance, highlighting the versatility of our approach.
methods aim to enhance existing MPNNs and GTs with Although PST has higher time complexity compared to ex-
heuristic features. In contrast, we perfectly align graph- isting Graph Transformers and is slower on large graphs,
level tasks with set-level tasks through SRD, allowing us to it shows similar scalability to our baselines in real-world
convert orthogonal-transformation-equivariant set encoders graph property prediction datasets (see Appendix I). Our
to graph encoders and to inject graph structure information PST uses fewer or comparable parameters than baselines
into Transformers in a principled ways. across all datasets. Dataset details, experiment settings, and
Equivariant Point Cloud and 3-D Molecule Neural Net- hyperparameters are provided in Appendix E and F.
works. Equivariant point cloud and 3-D molecule tasks

6
 Graph As Point Set

Table 1. Normalized MAE (↗) on substructure counting tasks. Following Huang et al. (2023b), models can count the structure if the test
loss ↘ 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±0.1 2.6±0.4 4.9±0.8 9.9±0.5 15.8±0.2 0.6±0.7 2.2±0.3 5.8±0.6 25.1±0.7 57.7±0.3 6.0±1.3 29.8±3.0 56.4±4.7
PST 0.7±0.1 1.1±0.1 1.5±0.1 2.2±0.1 3.3±0.3 0.8±0.1 1.9±0.2 3.1±0.3 4.9±0.3 8.6±0.5 3.0±0.1 4.0±0.7 9.2±0.9

7.1. Graph substructure counting et al., 2023b), 2-DRFWL(2) GNN (Zhou et al., 2023)). For
fair comparsion, we introduce two versions of our model:
As Chen et al. (2020) highlight, the ability to count sub-
PST without Euclidean distance (PST) and PST with Eu-
structures is a crucial metric for assessing expressivity. We
clidean distance (PST*). Results in Table 2 show PST out-
evaluate our model’s substructure counting capabilities on
performs all baseline models without Euclidean distance
synthetic graphs following Huang et al. (2023b). The con-
on 11 out of 12 targets, with an average 11% reduction in
sidered substructures include paths of lengths 2 to 6, cycles
loss compared to the strongest baseline, 2-DRFWL(2) GNN.
of lengths 3 to 7, and other substructures like tailed triangles
PST* outperforms all Euclidean distance-based baselines
(TT), chordal cycles (CC), and triangle-rectangle (TR). Our
on 8 out of 12 targets, with an average 4% reduction in
task involves predicting the number of paths originating
loss compared to the strongest baseline, 1-2-3-GNN. Both
from each node and the cycles and other substructures in
models rank second in performance for the remaining tar-
which each node participates. We compare our Point Set
gets. PSDS without Euclidean distance also outperforms
Transformer (PST) with expressive GNN models, including
baselines on 6 out of 12 targets.
ID-GNNs (You et al., 2021), NGNNs (Zhang & Li, 2021),
GNNAK+(Zhao et al., 2022), I2 -GNN(Huang et al., 2023b), For ZINC, ZINC-full, and ogbg-molhiv datasets, we have
and PPGN (Maron et al., 2019a). Baseline results are from conducted an evaluation of PST and PSDS in comparison to
Huang et al. (2023b), where uncertainties are unknown. a range of expressive GNNs and graph transformers (GTs).
This set of models includes expressive MPNN and subgraph
Results are in Table 1. Following Huang et al. (2023b), a
GNNs: GIN (Xu et al., 2019b), SUN (Frasca et al., 2022),
model can count a substructure if its normalized test Mean
SSWL (Zhang et al., 2023a), 2-DRFWL(2) GNN (Zhou
Absolute Error (MAE) is below 10↔2 (10 units in the table).
et al., 2023), CIN (Bodnar et al., 2021), NGNN (Zhang
Remarkably, our PST counts all listed substructures, which
& Li, 2021), and GTs: Graphormer (Ying et al., 2021),
aligns with our Theorem 5.4 and Theorem 5.5, while the
GPS (Rampásek et al., 2022), Graph MLP-Mixer (He et al.,
second-best model, I2 -GNN, counts only 10 out of 13 sub-
2023), Specformer (Bo et al., 2023), SignNet (Lim et al.,
structures. PSDS can also count 8 out of 13 substructures,
2023), and Grit (Ma et al., 2023). Performance results
showcasing the versatility of our graph-to-set method.
for the expressive GNNs are sourced from (Zhou et al.,
2023), while those for the Graph Transformers are extracted
7.2. Graph properties prediction from (He et al., 2023; Ma et al., 2023; Lim et al., 2023). The
We conduct experiments on four real-world graph datasets: comprehensive results are presented in Table 3. Notably, our
QM9 (Wu et al., 2017), ZINC, ZINC-full (Gómez- PST outperforms all baseline models on ZINC-full datasets,
Bombarelli et al., 2016), and ogbg-molhiv (Hu et al., 2020). achieving reductions in loss of 18%. On the ogbg-molhiv
PST excels in performance, and PSDS performs comparable dataset, our PST also delivers competitive results, with only
to GIN (Xu et al., 2019a). PST also outperforms all base- CIN and Graphormer surpassing it. Overall, PST demon-
lines on TU datasets (Ivanov et al., 2019) (see Appendix J). strates exceptional performance across these four diverse
datasets, and PSDS also performs comparable to representa-
For the QM9 dataset, we compare PST with various ex- tive GNNs like GIN (Xu et al., 2019a).
pressive GNNs, including models considering Euclidean
distances (1-GNN, 1-2-3-GNN (Morris et al., 2019), 7.3. Long Range Graph Benchmark
DTNN (Wu et al., 2017), PPGN (Maron et al., 2019a)) and
those focusing solely on graph structure (Deep LRP (Chen To assess the long-range capacity of our Point Set Trans-
et al., 2020), NGNN (Zhang & Li, 2021), I2 -GNN (Huang former (PST), we conducted experiments using the Long

7
 Graph As Point Set

Table 2. MAE (↗) 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 I2 GNN DF PSDS PST 1GNN* DTNN* 123* PPGN* PST*
↔1
µ 10 D 3.64 4.28 4.28 3.46 3.53±0.05 3.19±0.04 4.93 2.44 4.76 2.31 0.23±0.01
ω 10↔1 a30 2.98 2.90 2.30 2.22 2.05±0.02 1.89±0.04 7.80 9.50 2.70 3.82 0.78±0.05
εhomo 10↔2 meV 6.91 7.21 7.10 6.15 6.56±0.03 5.98±0.09 8.73 10.56 9.17 7.51 2.98±0.08
εlumo 10↔2 meV 7.54 8.08 7.27 6.12 6.31±0.05 5.84±0.08 9.66 13.93 9.55 7.81 2.20±0.07
”ε 10↔2 meV 9.61 10.34 10.34 8.82 9.13±0.04 8.46±0.07 13.33 30.48 13.06 11.05 4.47±0.09
R2 a20 19.30 20.50 18.64 15.04 14.35±0.02 13.08±0.16 34.10 17.00 22.90 16.07 0.93±0.03
ZPVE 10↔2 meV 1.50 0.54 0.38 0.46 0.41±0.02 0.39±0.01 3.37 4.68 0.52 17.42 0.26±0.01
U0 meV 11.24 8.03 5.74 4.24 3.53±0.11 3.46±0.17 63.13 66.12 1.16 6.37 3.33±0.19
U meV 11.24 9.82 5.61 4.16 3.49±0.05 3.55±0.10 56.60 66.12 3.02 6.37 3.26±0.05
H meV 11.24 8.30 7.32 3.95 3.47±0.04 3.49±0.20 60.68 66.12 1.14 6.23 3.29±0.21
G meV 11.24 13.31 7.10 4.24 3.56±0.14 3.55±0.17 52.79 66.12 1.28 6.48 3.25±0.15
Cv 10↔2 cal/mol/K 12.90 17.40 7.30 9.01 8.35±0.09 7.77±0.15 27.00 243.00 9.44 18.40 3.63±0.13

Table 3. Results on graph property prediction tasks. Table 4. Results on Long Range Graph Benchmark. * means using
Random Walk Structural Encoding (Dwivedi et al., 2022a), and **
zinc zinc-full molhiv means Laplacian Eigenvector Encoding (Dwivedi et al., 2023).
MAE↗ MAE↗ AUC≃
Model PascalVOC-SP Peptides-Func Peptides-Struct
GIN 0.163±0.004 0.088±0.002 77.07±1.49
F1 score ≃ AP ≃ MAE ↗
GNN-AK+ 0.080±0.001 – 79.61±1.19
ESAN 0.102±0.003 0.029±0.003 78.25±0.98 GCN 0.1268±0.0060 0.5930±0.0023 0.3496±0.0013
SUN 0.083±0.003 0.024±0.003 80.03±0.55 GINE 0.1265±0.0076 0.5498±0.0079 0.3547±0.0045
SSWL 0.083±0.003 0.022±0.002 79.58±0.35 GatedGCN 0.2873±0.0219 0.5864±0.0077 0.3420±0.0013
DRFWL 0.077±0.002 0.025±0.003 78.18±2.19 GatedGCN* 0.2860±0.0085 0.6069±0.0035 0.3357±0.0006
CIN 0.079±0.006 0.022±0.002 80.94±0.57 Transformer** 0.2694±0.0098 0.6326±0.0126 0.2529±0.0016
NGNN 0.111±0.003 0.029±0.001 78.34±1.86 SAN* 0.3216±0.0027 0.6439±0.0075 0.2545±0.0012
Graphormer 0.122±0.006 0.052±0.005 80.51±0.53 SAN** 0.3230±0.0039 0.6384±0.0121 0.2683±0.0043
GPS 0.070±0.004 - 78.80±1.01 GraphGPS 0.3748±0.0109 0.6535±0.0041 0.2500±0.0005
GMLP-Mixer 0.077±0.003 - 79.97±1.02 Exphormer 0.3975±0.0037 0.6527±0.0043 0.2481±0.0007
SAN 0.139±0.006 - 77.75±0.61 GMLP-Mixer - 0.6970±0.0080 0.2475±0.0015
Specformer 0.066±0.003 - 78.89±1.24 Graph ViT - 0.6942±0.0075 0.2449±0.0016
SignNet 0.084±0.006 0.024±0.003 - Grit - 0.6988±0.0082 0.2460±0.0012
Grit 0.059±0.002 0.024±0.003 - PSDS 0.2134±0.0050 0.5965±0.0064 0.2621±0.0036
PSDS 0.162±0.007 0.049±0.002 74.92±1.18 PST 0.4010±0.0072 0.6984±0.0051 0.2470±0.0015
PST 0.063±0.003 0.018±0.001 80.32±0.71

Range Graph Benchmark (Dwivedi et al., 2022b). Follow- 8. Conclusion

ing He et al. (2023), we compared our model to a range of
baseline models, including GCN (Kipf & Welling, 2017), We introduce a novel approach employing symmetric rank
GINE (Xu et al., 2019a), GatedGCN (Bresson & Laurent, decomposition to transform interconnected nodes in graph
2017), SAN (Kreuzer et al., 2021), Graphormer (Ying et al., into independent points with coordinates. Additionally, we
2021), GMLP-Mixer, Graph ViT (He et al., 2023), and propose the Point Set Transformer to encode the point set.
Grit (Ma et al., 2023). PST outperforms all baselines on Our approach demonstrates remarkable theoretical expres-
the PascalVOC-SP and Peptides-Func datasets and achieves sivity and excels in real-world performance, addressing both
the third-highest performance on the Peptides-Struct dataset. short-range and long-range tasks effectively. It extends the
PSDS consistently outperforms GCN and GINE. These re- design space of GNN and provides a principled way to inject
sults showcase the remarkable long-range interaction cap- graph structural information into Transformers.
turing abilities of our methods across various benchmark
datasets. Note that a contemporary work (Tönshoff et al., 9. Limitations
2023) points out that even vanilla MPNNs can achieve sim-
ilar performance to Graph Transformers on LRGB with PST’s scalability is still constrained by the Transformer
better hyperparameters, which implies that LRGB is not a architecture. To overcome this, acceleration techniques such
rigor benchmark. However, for comparison with previous as sparse attention and linear attention could be explored,
work, we maintain the original settings on LRGB datasets. which will be our future work.

8
 Graph As Point Set

Impact Statement Deng, C., Litany, O., Duan, Y., Poulenard, A., Tagliasacchi,
A., and Guibas, L. J. Vector neurons: A general frame-
This paper presents work whose goal is to advance the field work for so(3)-equivariant networks. In ICCV, 2021.
of graph representation learning and will improve the design
of graph generation and prediction models. There are many Dwivedi, V. P. and Bresson, X. A generalization of trans-
potential societal consequences of our work, none which we former networks to graphs, 2020.
feel must be specifically highlighted here.
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bres-
Acknowledgement son, X. Graph neural networks with learnable structural
and positional representations. In ICLR, 2022a.
Xiyuan Wang and Muhan Zhang are partially sup-
ported by the National Key R&D Program of China Dwivedi, V. P., Rampásek, L., Galkin, M., Parviz, A., Wolf,
(2022ZD0160300), the National Key R&D Program of G., Luu, A. T., and Beaini, D. Long range graph bench-
China (2021ZD0114702), the National Natural Science mark. In NeurIPS, 2022b.
Foundation of China (62276003), and Alibaba Innovative
Research Program. Pan Li is supported by the National Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio,
Science Foundation award IIS-2239565. Y., and Bresson, X. Benchmarking graph neural networks.
J. Mach. Learn. Res., 24:43:1–43:48, 2023.

References Dym, N. and Maron, H. On the universality of rotation

equivariant point cloud networks. In ICLR, 2021.
Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M.
Optuna: A next-generation hyperparameter optimization Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M. How
framework. In SIGKDD, 2019. powerful are k-hop message passing graph neural net-
Batzner, S., Musaelian, A., Sun, L., Geiger, M., Mailoa, works. In NeurIPS, 2022.
J. P., Kornbluth, M., Molinari, N., Smidt, T. E., and
Fey, M. and Lenssen, J. E. Fast graph representation learning
Kozinsky, B. E (3)-equivariant graph neural networks for
with pytorch geometric. CoRR, abs/1903.02428, 2019.
data-efficient and accurate interatomic potentials. Nature
communications, 13(1):1–11, 2022. Frasca, F., Bevilacqua, B., Bronstein, M. M., and Maron, H.
Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, Understanding and extending subgraph gnns by rethink-
C., Balamurugan, G., Bronstein, M. M., and Maron, H. ing their symmetries. In NeurIPS, 2022.
Equivariant subgraph aggregation networks. In ICLR,
Fuchs, F., Worrall, D., Fischer, V., and Welling, M. Se(3)-
2022.
transformers: 3d roto-translation equivariant attention
Bo, D., Shi, C., Wang, L., and Liao, R. Specformer: Spectral networks. NeurIPS, 2020.
graph neural networks meet transformers. In ICLR, 2023.
Fürer, M. On the combinatorial power of the weisfeiler-
Bodnar, C., Frasca, F., Otter, N., Wang, Y., Liò, P., Montúfar, lehman algorithm. In CIAC, volume 10236, pp. 260–271,
G. F., and Bronstein, M. M. Weisfeiler and lehman go 2017.
cellular: CW networks. In NeurIPS, 2021.
Gasteiger, J., Becker, F., and Günnemann, S. Gemnet: Uni-
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. versal directional graph neural networks for molecules.
Improving graph neural network expressivity via sub- In NeurIPS, 2021.
graph isomorphism counting. TPAMI, 45(1), 2023.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and
Bresson, X. and Laurent, T. Residual gated graph convnets, Dahl, G. E. Neural message passing for quantum chem-
2017. istry. In ICML, 2017.
Chen, H., Liu, S., Chen, W., Li, H., and Jr., R. W. H. Equiv-
Gómez-Bombarelli, R., Duvenaud, D., Hernández-Lobato,
ariant point network for 3d point cloud analysis. In CVPR,
J. M., Aguilera-Iparraguirre, J., Hirzel, T. D., Adams,
2021.
R. P., and Aspuru-Guzik, A. Automatic chemical de-
Chen, Z., Chen, L., Villar, S., and Bruna, J. Can graph sign using a data-driven continuous representation of
neural networks count substructures? In NeurIPS, 2020. molecules, 2016.

Cohen, T. S., Geiger, M., Köhler, J., and Welling, M. Spher- Hamilton, W. L., Ying, Z., and Leskovec, J. Inductive repre-
ical cnns. In ICLR, 2018. sentation learning on large graphs. In NeurIPS, 2017.

9
 Graph As Point Set

He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y.
Bresson, X. A generalization of vit/mlp-mixer to graphs. Invariant and equivariant graph networks. In IGN, 2019b.
In ICML, 2023.
Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit:
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Encoding graph structure in transformers, 2021.
Catasta, M., and Leskovec, J. Open graph benchmark:
Datasets for machine learning on graphs. In NeurIPS, Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen,
2020. J. E., Rattan, G., and Grohe, M. Weisfeiler and leman
go neural: Higher-order graph neural networks. In AAAI,
Huang, Y., Lu, W., Robinson, J., Yang, Y., Zhang, M., 2019.
Jegelka, S., and Li, P. On the stability of expressive
positional encodings for graph neural networks. arXiv Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J.,
preprint arXiv:2310.02579, 2023a. Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga,
L., Desmaison, A., Köpf, A., Yang, E. Z., DeVito, Z.,
Huang, Y., Peng, X., Ma, J., and Zhang, M. Boosting Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B.,
the cycle counting power of graph neural networks with Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative
i$ˆ2$-gnns. In ICLR, 2023b. style, high-performance deep learning library. In NeurIPS,
pp. 8024–8035, 2019.
Huang, Y., Lu, W., Robinson, J., Yang, Y., Zhang, M.,
Jegelka, S., and Li, P. On the stability of expressive Perepechko, S. and Voropaev, A. The number of fixed length
positional encodings for graph neural networks. ICLR, cycles in an undirected graph. explicit formulae in case
2024. of small lengths. MMCP, 148, 2009.
Hutchinson, M. J., Lan, C. L., Zaidi, S., Dupont, E., Teh, Puntanen, S., Styan, G. P., and Isotalo, J. Matrix tricks
Y. W., and Kim, H. Lietransformer: Equivariant self- for linear statistical models: our personal top twenty.
attention for lie groups. In ICML, 2021. Springer, 2011.
Ivanov, S., Sviridov, S., and Burnaev, E. Understanding iso-
Qian, C., Rattan, G., Geerts, F., Niepert, M., and Morris,
morphism bias in graph data sets. CoRR, abs/1910.12091,
C. Ordered subgraph aggregation networks. In NeurIPS,
2019.
2022.
Kim, J., Oh, S., and Hong, S. Transformers generalize
Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf,
deepsets and can be extended to graphs & hypergraphs.
G., and Beaini, D. Recipe for a general, powerful, scal-
In NeurIPS, 2021.
able graph transformer. In NeurIPS, 2022.
Kipf, T. N. and Welling, M. Semi-supervised classification
with graph convolutional networks. In ICLR, 2017. Satorras, V. G., Hoogeboom, E., and Welling, M. E (n)
equivariant graph neural networks. In ICML, 2021.
Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V.,
and Tossou, P. Rethinking graph transformers with spec- Schütt, K., Unke, O., and Gastegger, M. Equivariant mes-
tral attention. In NeurIPS, 2021. sage passing for the prediction of tensorial properties and
molecular spectra. In ICML, 2021.
Li, P., Wang, Y., Wang, H., and Leskovec, J. Distance en-
coding: Design provably more powerful neural networks Segol, N. and Lipman, Y. On universal equivariant set
for graph representation learning. In NeurIPS, 2020. networks. In ICLR, 2020.

Lim, D., Robinson, J. D., Zhao, L., Smidt, T. E., Sra, S., Shervashidze, N., Schweitzer, P., van Leeuwen, E. J.,
Maron, H., and Jegelka, S. Sign and basis invariant Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-lehman
networks for spectral graph representation learning. In graph kernels. JMLR, 2011.
ICLR, 2023.
Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland,
Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, D. J., and Sinop, A. K. Exphormer: Sparse transformers
P. K., Coates, M., Torr, P. H. S., and Lim, S. Graph for graphs. In ICML, 2023.
inductive biases in transformers without message passing.
In ICML, 2023. Thomas, N., Smidt, T., Kearnes, S., Yang, L., Li, L.,
Kohlhoff, K., and Riley, P. Tensor field networks:
Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Rotation-and translation-equivariant neural networks for
Provably powerful graph networks. In NeurIPS, 2019a. 3d point clouds. arXiv preprint arXiv:1802.08219, 2018.

10
 Graph As Point Set

Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Zhang, M., Cui, Z., Neumann, M., and Chen, Y. An end-to-
Where did the gap go? reassessing the long-range graph end deep learning architecture for graph classification. In
benchmark. CoRR, abs/2309.00367, 2023. AAAI, 2018.

Wang, H., Yin, H., Zhang, M., and Li, P. Equivariant and Zhao, L., Jin, W., Akoglu, L., and Shah, N. From stars
stable positional encoding for more powerful graph neural to subgraphs: Uplifting any GNN with local structure
networks. In ICLR, 2022. awareness. In ICLR, 2022.

Wang, X. and Zhang, M. Graph neural network with local Zhou, J., Feng, J., Wang, X., and Zhang, M. Distance-
frame for molecular potential energy surface. LoG, 2022. restricted folklore weisfeiler-leman gnns with provable
cycle counting power, 2023.
Weiler, M., Geiger, M., Welling, M., Boomsma, W., and
Cohen, T. 3d steerable cnns: Learning rotationally equiv-
ariant features in volumetric data. In NeurIPS, 2018.

Wijesinghe, A. and Wang, Q. A new perspective on ”how

graph neural networks go beyond weisfeiler-lehman?”.
In ICLR, 2022.

Winkels, M. and Cohen, T. S. 3d g-cnns for pulmonary

nodule detection, 2018.

Worrall, D. E., Garbin, S. J., Turmukhambetov, D., and

Brostow, G. J. Harmonic networks: Deep translation and
rotation equivariance. In CVPR, 2017.

Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge-

niesse, C., Pappu, A. S., Leswing, K., and Pande, V. S.
Moleculenet: A benchmark for molecular machine learn-
ing, 2017.

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, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful
are graph neural networks? In ICLR, 2019a.

Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful
are graph neural networks? In ICLR, 2019b.

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, J., Selman, J. M. G., Ying, R., and Leskovec, J.

Identity-aware graph neural networks. In AAAI, 2021.

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, B., Luo, S., Wang, L., and He, D. Rethinking the
expressive power of gnns via graph biconnectivity. In
ICLR, 2023b.

Zhang, M. and Li, P. Nested graph neural networks. In

NeurIPS, 2021.

11
 Graph As Point Set

A. Proof
A.1. Proof of Proposition 2.3
The matrices QT1 Q1 and QT2 Q2 in Rr→r are full rank and thus invertible. This allows us to derive the following equations:
L = Q1 QT1 = Q2 QT2 (9)

Q1 QT1 = Q2 QT2 ∞ QT1 Q1 QT1 = QT1 Q2 QT2 (10)

∞ = (QT1 Q1 )↔1 QT1 Q2 QT2
QT1 (11)
∞ ↘R → Rm→m , QT1 = RQT2 (12)
∞ ↘R → Rm→m , Q1 = Q2 R (13)

Q1 QT1 = Q2 RRT QT2 = Q2 QT2 ∞ QT2 Q2 RRT QT2 Q2 = QT2 Q2 QT2 Q2 (14)
∞ RR = T
(QT2 Q2 )↔1 QT2 Q2 QT2 Q2 (QT2 Q2 )↔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 RRT = I, then Q1 = Q2 R, and L = Q1 QT1 = Q2 RRT QT2 = Q2 QT2 .

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

≃x → Rn ,
! ! !
xT (D + A)x = xi xj + ( Aij )x2i (16)
(i,j)↗E i↗V j↗V
! 1 ! 2 1 ! 2
= xi xj + xi + xj (17)
2 2
(i,j)↗E (i,j)↗E (i,j)↗E
1 !
= (xi + xj )2 ⇐ 0 (18)
2
(i,j)↗E

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 G = (V, A, X) and G ↑ = (V ↑ , A↑ , X ↑ ) with degree matrices D and D↑ , respectively, the
two graphs are isomorphic (G ↗ G ↑ ) if and only if ↘R → O(r), {{(Xv , RQv )|≃v → V }} = {{(Xv , Q↑v )|v → V ↑ }}, where r
denotes the rank of matrix Q, and Q and Q↑ are the symmetric rank decompositions of D + A and D↑ + A↑ respectively.

Proof. Two graphs are isomorphic ∈ ↘ω → ”n , ω(A) = A↑ and ω(X) = X ↑ .

Now we prove that ↘ω → ”n , ω(A) = A↑ and ω(X) = X ∈ ↘R → O(r), {{(Xv , RQv )|v → V }} = {{(Xv , Q↑v )|v → V ↑ }}.
When ↘ω → ”n , ω(A) = A↑ and ω(X) = X ↑ , as
T
ω(Q)ω(Q)T = ω(A + D) = A↑ + D↑ = Q↑ Q↑ , (19)
according to Proposition 2.3, ↘R → O(r), ω(Q)RT = Q↑ . Moreover, ω(X) = X ↑ , so
{{(Xv , RQv )|v → V }} = {{(Xv↑ , Q↑v )|v → V ↑ }} (20)

When ↘R → O(r), {{(Xv , RQv )|v → V }} = {{(Xv↑ , Q↑v )|v → V ↑ }}, there exists permutation ω → ”n , ω(X) =
X ↑ , ω(Q)RT = Q↑ . Therefore,
T
ω(A + D) = ω(Q)ω(Q)T = ω(Q)RT Rω(Q)T = Q↑ Q↑ = A↑ + D↑ (21)

12
 Graph As Point Set

As A = D + A ∋ 12 diag((D + A)ε1), A↑ = D + A ∋ 12 diag((D + A)ε1), where ε1 → Rn is an vector with all elements = 1.

ω(A) = A↑ (22)

A.4. Proof of Theorem 3.3

Now we restate the theorem.
Theorem A.2. Given two graphs G = (V, A, X) and G = (V ↑ , A↑ , X ↑ ), and an injective permutation-equivariant function
Z mapping adjacency matrix to a symmetric matrix: (1) For all permutation-equivariant function f , if G ↗ G ↑ , then the
two sets of PSRD coordinates are equal up to an orthogonal transformation, i.e., ↘R → O(r), {{Xv , RQ(Z(A), f )v |v →
V }} = {{Xv↑ , Q(Z(A↑ ), f )v |v → V ↑ }}, where r is the rank of A, Q, Q↑ are the PSRD coordinates of A and A↑ respectively.
(2) There exists a continuous permutation-equivariant function f : Rr ↔ Rr→2 , such that G ↗ G ↑ if ↘R → O(r), ≃i =
1, 2, ..., d, {{(Xv , RQ(Z(A), f1 )v , RQ(Z(A), f2 )v )|v → V }} = {{(Xv↑ , Q(Z(A↑ ), f1 )v , Q(Z(A↑ ), f2 )v )|v → V ↑ }}, where
f1 : Rr ↔ Rr and f2 : Rr ↔ Rr are two output channels of f .

Proof. First, as Z is an injective permutation equivariant function, forall permutation ω → ”n

ω(Z(A)) = Z(A↑ ) ∈ Z(ω(A)) = Z(A↑ ) ∈ ω(A) = A↑ . (23)

Therefore, two matrix are isomorphic ∈ ↘ω → ”n , ω(X) = X ↑ , ω(Z) = Z ↑ , where Z, Z ↑ denote Z(A), Z(A↑ ) respectively.
T
In this proof, we denote eigendecomposition as Z = U diag(!)U T and Z ↑ = U ↑ diag(!↑ )U ↑ , where elements in ! and
!↑ are sorted in ascending order. Let the multiplicity of eigenvalues in Z be r1 , r2 , ..., rl , corresponding to eigenvalues
ϑ1 , ϑ2 , ..., ϑi .
(1) If G ↗ G ↑ , there exists a permutation ω → ”n , ω(X) = X ↑ , ω(Z) = Z ↑ .
T
ω(Z) = Z ↑ ∞ Z ↑ = ω(U )diag(!)ω(U )T = U ↑ diag(!↑ )U ↑ . (24)

ω(U )diag(!)ω(U )T is also an eigendecomposition of Z ↑ , so ! = !↑ as they are both sorted in ascending order. Moreover,
since ω(U ), U ↑ 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 V1 → O(r1 ), V2 → O(r2 ), ..., Vl → O(rl ) as diagonal blocks that
ω(U )V = U ↑ .
As f is a permutation equivariant function,

!i = !j ∞ ↘ω → ”r , ω(i) = j, ω(j = i), ω(!) = ! (25)

∞ ↘ω → ”r , ω(i) = j, ω(j = i), ω(f (!)) = f (ω(!)) = f (!) (26)
∞ f (!)i = f (!)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 f1 Ir1 , f2 Ir2 , ..., fl Irl as diagonal blocks, where fi → R is f (!)pi , pi is a position that !pi = ϑi , and
Ir is an identity matrix → Rr→r .
Therefore,
V diag(f (!)) = diag(f1 V1 , f2 V2 , ..., fl Vl ) = diag(f (!))V. (28)
Therefore,

ω(Q(Z, f ))V = ω(U )diag(f (!))V (29)

= ω(U )V diag(f (!)) (30)
= U ↑ diag(f (!↑ )) (31)
↑
= Q(Z , f ) (32)

As V V T = I, V → O(r),

↘R → O(r), {{Xv , RQ(Z(A), f )v |v → V }} = {{Xv↑ , Q(Z(A↑ ), f )v |v → V ↑ }} (33)

13
 Graph As Point Set
"
(2) We simply define f1 is element-wise
" abstract value and square root |.|, f1 is element-wise abstract value and square
root multiplied with its sign sgn(|.|) |.|. Therefore, f1 , f2 are continuous and permutation equivariant.
if ↘R → O(r),
{{Xv , RQ(Z(A), f1 )v , RQ(Z(A), f2 )v |v → V }} = {{Xv↑ , Q(Z(A↑ ), f1 )v , Q(Z(A↑ ), f2 )v |v → V ↑ }}. then there exist ω →
”n , so that
ω(X) = X ↑ (34)

ω(U )diag(f1 (!))RT = U ↑ diag(f1 (!↑ )) (35)

ω(U )diag(f2 (!))RT = U ↑ diag(f2 (!↑ )). (36)

Therefore,

ω(Z) = ω(U )diag(f1 (!))diag(f2 (!))ω(U ↑ )T (37)

T ↑ T
= ω(U )diag(f1 (!))RR diag(f2 (!))ω(U ) (38)
↑ ↑ ↑ ↑T
= U diag(f1 (! ))diag(f2 (! ))U (39)
↑
=Z. (40)

As ω(Z) = Z ↑ , ω(X) = X ↑ , two graphs are isomorphic.

A.5. Proof of Theorem 5.3

Let Hl denote a circle of l nodes. Let Gl denote a graph of two connected components, one is H↘l/2≃ and the other is H⇐l/2⇒ .
Obviously, there exists a node pair in Gl with shortest path distance equals to infinity, while Hl 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 Gl , Hl , they have the same representation produced by k-layer MPNN, forall k → 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 ϖ ϖ △ g = f , which is equivalent to
given arbitrary input H, G, f (H) = f (G) ∞ g(H) = g(G). We use f ↔ g to denote that f can be expressed with g. If
both f ↔ g and g ↔ f , there exists a bijective mapping between the output of f to the output of g, denoted as f ▽ g.
Here are some basic rule.

• g ↔ h ∞ f △ g ↔ f △ h.

• g ↔ h, f ↔ s ∞ f △ g ↔ s △ h.

• f is bijective, f △ g ↔ g

14
 Graph As Point Set

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

ht+1 t t t
ij = hash(hij , {{(hik , hkj )|k → V }}). (42)

The color of the the whole graph is

htG = hash({{htij |(i, j) → V ↓ V }}). (43)

Initially, tuple color hashes the node feature and edge between the node pair, h0ij ↔ ϱij , Aij , Xi , Xj .
We are going to prove that
Lemma A.4. Forall t → N, htij can express Akij , k = 0, 1, 2, ..., 2t , where A is the adjacency matrix of the input graph.

Proof. We prove it by induction on t.

• When t = 0, h0ij ↔ Aij , Iij in initialization.

→ → →
• If t > 0, ≃t↑ < t, htij ↔ Ak , k ↑ = 0, 1, 2, ..., 2t . For all k = 0, 1, 2,

htij ↔ hash(htij , {{(htik , htkj )|k → V }}) (44)

↘k/2≃ ⇐k/2⇒
↔ hash(htij , {{(Aik , Akj )|k → V }}) (45)
! ↘k/2≃ ⇐k/2⇒
↔ Aik Akj (46)
k↗V

↔ Akij (47)

→
To prove that t-iteration 2-FWL cannot compute shortest path distance larger than 2t , we are going to construct an example.
Lemma A.5. Let Hl denote a circle of l nodes. Let Gl denote a graph of two connected components, one is H↘l/2≃ and the
other is H⇐l/2⇒ . ≃K → N+ , 2-FWL can not distinguish HlK and GlK , where lK = 2 ↓ 2 ↓ (2K ). However, GlK contains
node tuple with 2K + 1 shortest path distance between them while HlK does not, any model count up to 2K + 1 shortest
path distance can count it.

Proof. Given a fixed t, we enumerate the iterations of 2-FWL. Given two graphs HlK , GlK , we partition all tuples in
each graph according to the shortest path distance between nodes: c0 , c1 , ..., cl , ..., c2K , where cl contains all tuples with
shortest path distance between them as l, and c>2K contains all tuples with shortest path distance between them larger than
2K . We are going to prove that at k-th layer k <= K, all ci , i ∝ 2k nodes have the same representation (denoted as hki )
c2k +1 , c2k +2 , ..., c2K , c>K nodes all have the same representation (denoted as hk2k +1 ).
Initially, all c0 tuples have representation h00 , all c1 tuples have the same representation h01 in both graph, and all other tuples
have the same representation h02 .
Assume at k-th layer, all ci , i ∝ 2k nodes have the same representation hki , c2k +1 , c2k +2 , ..., c2K , c>2K tuples all have the
same representation hk2k +1 . At k + 1-th layer, each representation is updated as follows.

ht+1 t t t
ij ⇒ hij , {{(hiv , hvj )|v → V }} (48)

For all tuples, the multiset has lK elements in total.

For c0 tuples, the multiset have 1 (hk0 , hk0 ) as v = i, 2 (hkt , hkt ) for t = 1, 2, .., 2k respectively as v is the k-hop neighbor of
i, and all elements left are (hk2k +1 , hk2k +1 ) as v is not in the k-hop neighbor of i.
For ct , t = 1, 2, ..., 2k tuples: the multiset have 1 (hka , hkt↔a ) for a = 0, 1, 2, .., t respectively as v is on the shortest path
between (i, j), and 1 (hka , hk2k +1 ) for a = 1, 2, ..., 2k respectively, and 1 (hk2k +1 , hka ) for a = 1, 2, ..., 2k respectively, with
other elements are (hk2k +1 , hk2k +1 ).

15
 Graph As Point Set

For ct , t = 2k + 1, 2k + 2, ..., 2k+1 tuples: the multiset have 1 (hka , hkt↔a ) for a = t ∋ 2k , t ∋ 2k + 1, ..., 2k respectively
as v is on the shortest path between (i, j), 1 (hka , hkt↔a ) for a → {0, 1, 2, ..., t ∋ 2k ∋ 1} ̸ {2k + 1, 2k + 2, ..., 2k+1 }
respectively as v is on the shortest path between (i, j), and 1 (hka , hk2k +1 ) for a = 1, 2, ..., 2k respectively, and 1 (hk2k +1 , hka )
for a = 1, 2, ..., 2k respectively, with other elements are (hk2k +1 , hk2k +1 ).
For ct , t = 2k+1 + 1, ..., 2K , > 2K : the multiset are all the same : 2 (hka , hk2k +1 ) and 2 (hk2k +1 , hka ) for a = 1, 2, 3, ..., 2k ,
respectively.

A.7. Proof of Theorem 5.1

We can simply choose fk (!) = !k . Then ⇓Q(A, f0 )i , Q(A, fk )j ⇔ = Akij . The shortest path distance is

spd(i, j, A) = arg min{k → N|Akij > 0} (49)

k

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 AT = A, A 7 A = A
An L-path is a sequence of edges [(i1 , i2 ), (i2 , i3 ), ..., (iL , iL+1 )], where all nodes are different from each other. An L-cycle
is an L-path except that i1 = iL+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 i1 = u, iL+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 PL denote path matrix whose (u, v) elements denote the
number of L-pathes from u to v, Perepechko & Voropaev (2009) provides formula to express PL 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:

s↑i ⇒ MLP1 (si ⇑diag(W1 viT vik W2 )) (50)

vi↑ ⇒ vi diag(MLP2 (s↑i ))W3 + v i W4 (51)

Attention layer:
Yij = MLP3 (Kij ), Kij = (Wqs si 7 Wks sj )⇑diag(Wqv viT vi Wkv ), (52)
As s↑i and vi↑ can express si , vi , so the weaken version can be expressed with the original version.
!
si ⇒ MLP4 (s↑j ⇑ Attenij s↑j ) (53)
j
!
vi ⇒ W5 (vj↑ ⇑ Attenij vj↑ ) (54)
j

Let Y k denote the attention matrix at k-th layer. Y k is a learnable function of A. Let Yk denote the polynomial space of A
that Y k can express. Each element in it is a function from Rn→n ↔ Rn→n
We are going to prove some lemmas about Y.
Lemma A.6. Yk ↑ Yk+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 y1 , y2 , ..., ys → Yk , their hadamard product y1 7 y2 7 ... 7 ys → Yk .

16
 Graph As Point Set
#s
Proof. As (y1 7 y2 7 ... 7 ys )ij = l=1 (yl )ij is a element-wise polynomial on compact domain, an MLP (denoted as
g) exists that takes (i, j) elements of the y1 , y2 , ..., ys to produce the corresponding elements of their hadamard product.
Assume g0 is the MLP3 in Equation 53 to produce the concatenation of y1 , y2 , .., ys , use g △ g0 (the composition of two
mlps) for the MLP3 in Equation 53 produces the hadamard product.
$s
Lemma A.8. If y1 , y2 , ..., ys → Yk , their linear combination l=1 al yl → Yk , where al → R.
$s $s
Proof. As ( l=1 al yl )ij = l=1 al (yl )ij is a element-wise linear layer (denoted as g). Assume g0 is the MLP3 in
Equation 53 to produce the concatenation of y1 , y2 , .., ys , use g △ g0 for the MLP3 in Equation 53 produces the linear
combination.

Lemma A.9. ≃s > 0, As → Y1 .

Proof. As shown in Section 5.1, the inner product of coordinates can produce As .

Lemma A.10. ≃y1 , y2 , y3 → Yk , s → N+ , d(y1 )y2 , y2 d(y1 ), d(y1 )y2 d(y3 ), y1 As , As y1 , y1 As y2 → Yk

Proof. According to Equation 50 and Equation 52, s↑i at k-th layer can express yii for all y → Yk . Therefore, at k + 1-th
layer in Equation 52, MLP3 can first compute element (i, j) (y2 )ij from si , sj , vi , vj , then multiply (y2 )ij with (y1 )ii from
si , (y3 )jj from sj and thus produce d(y1 )y2 , y2 d(y1 ), d(y1 )y2 d(y3 ).
$ $
Moreover, according to$ Equation 53, vi at k +1-th
$ layer can express k$ (y1 )ik vk , k (y2 )ik vk . So at k +1-th layer, the (i, j)
element can express ⇓ k (y1 )ik vk , vj ⇔, ⇓vi , k (y1 )jk vk ⇔, ⇓(y1 )ik vk , k (y2 )jk vk ⇔, corresponds to y1 As , As y2 , y1 As y2 ,
respectively.

Therefore,
Lemma A.11. • ≃s > 0, l > 0, ai > 0, 7li=1 Aai → Y1 .

• ≃s1 , s2 > 0, l > 0, As1 d(7li=1 Aai ), d(7li=1 Aai )As1 , d(7li=1
1
Abi )As1 d(7li=1
2
Ab i ) → Y 2 .

• ≃s1 , s2 , s3 > 0, As1 d(7li=1 Aai )

Therefore, we come to our main theorem.

Theorem A.12. The attention matrix of 1-layer PST can express P2 , 2-layer PST can express P3 , 3-layer PST can express
P4 , P5 , 5-layer PST can express P6 .

Proof. As shown in (Perepechko & Voropaev, 2009),

P2 = A 2 (55)

Only one kind basis 7li=1 Aai . 1-layer PST can express it.

P3 = A3 + A ∋ Ad(A2 ) ∋ d(A2 )A (56)

Three kind of basis 7li=1 Aai (A3 , A), As1 d(7li=1 Aai )(Ad(A2 )), and d(7li=1 Aai )As1 . 2-layer PST can express it.

P4 = A4 + A2 + 3A 7 A2 ∋ d(A3 )A ∋ d(A2 )A2 ∋ Ad(A3 ) ∋ A2 d(A2 ) ∋ Ad(A2 )A (57)

Four kinds of basis 7li=1 Aai (A4 , A2 , A7A2 ), As1 d(7li=1 Aai ) (Ad(A3 ), A2 d(A2 )), d(7li=1 Aai )As1 (d(A3 )A, d(A2 )A2 ),
and As1 d(7li=1 Aai )As3 (Ad(A2 )A). 3-layer PST can express it.

17
 Graph As Point Set

P5 = A5 + 3A3 + 4A (58)
2 2 3 2
+ 3A 7 A 7 A + 3A 7 A ∋ 4A 7 A (59)
4 3 2 2 3 2 2 2 2
∋ d(A )A ∋ d(A )A ∋ d(A )A + 2d(A ) A ∋ 2d(A )A ∋ 4d(A )A (60)
4 2 3 3 2 2 2 2 2
∋ Ad(A ) ∋ A d(A ) ∋ A d(A ) + 2Ad(A ) ∋ 2Ad(A ) ∋ 4Ad(A ) (61)
2 2
+ d(A )Ad(A ) (62)
2
+ 3(A 7 A )A (63)
2
+ 3A(A 7 A ) (64)
3 2 2 2 2
∋ Ad(A )A ∋ Ad(A )A ∋ A d(A )A (65)
2
+ d(Ad(A )A)A (66)
(67)

Basis are in

• Y1

– 7li=1 Aai : A5 , A3 , A, A2 7 A2 7 A, A 7 A3 , A 7 A2 .

• Y2

– As1 d(7li=1 Aai ):Ad(A4 ), A2 d(A3 ), A3 d(A2 ), Ad(A2 )2 , Ad(A2 ), Ad(A2 ).

– d(7li=1 Aai )As1 : Ad(A4 ), A2 d(A3 ), A3 d(A2 ), Ad(A2 )2 , Ad(A2 ), Ad(A2 ).

– d(7li=1
1
Aai )As1 d(7li=1
1
Abi ): d(A2 )Ad(A2 ).

– As1 (7li=1 Aai ): A(A 7 A2 ).

– (7li=1 Aai )As1 : (A 7 A2 )A

• Y3 :

– As Y2 : Ad(A3 )A, Ad(A2 )A2 , A2 d(A2 )A.

– d(Y2 )As : d(Ad(A2 )A)A

3-layer PST can express it.

18
 Graph As Point Set

Formula for 6-path matrix is quite long.

P6 = A6 + 4A4 + 12A2 (68)

4 2 3 2 2 2 2 2 2
+ 3A 7 A + 6A 7 A 7 A + A 7 A 7 A ∋ 4A 7 A + 44A 7 A (69)
5 4 2 3 3 3 2 4 2 2
∋ d(A )A ∋ d(A )A ∋ d(A )A ∋ 5d(A )A ∋ d(A )A ∋ 7d(A )A (70)
2 2 2 2 3
+ 2d(A ) A + 4(d(A ) 7 d(A ))A (71)
5 4 2 3 3 3 2 4 2 2
∋ Ad(A ) ∋ A d(A ) ∋ A d(A ) ∋ 5Ad(A ) ∋ A d(A ) ∋ 7A d(A ) (72)
2 2 2 2 3
+ 2A d(A ) + 4A(d(A ) 7 d(A )) (73)
2 3 3 2 2 2 2
+ d(A )Ad(A ) + d(A )Ad(A ) + d(A )A d(A ) (74)
3 2 2 2 2 2 3
+ 2(A 7 A )A + 2(A 7 A 7 A )A + (A 7 A 7 A)A ∋ 3(A 7 A )A + (A 7 A )A (75)
2 2 2 2 2
+ (A 7 A )A + 2(A 7 A )A ∋ (A 7 A )A (76)
3 2 2 2 2 2 3
+ 2A(A 7 A ) + 2A(A 7 A 7 A ) + A(A 7 A 7 A) ∋ 3A(A 7 A ) + A(A 7 A ) (77)
2 2 2 2 2
+ A (A 7 A ) + 2A (A 7 A ) ∋ A(A 7 A ) (78)
2 2
∋ 8A 7 (A(A 7 A )) ∋ 8A 7 ((A 7 A )A) (79)
2 2 2 2
∋ 12d(A )(A 7 A ) ∋ 12(A 7 A )d(A ) (80)
4 2 3 3 2 3 2 2 3 2 2 2
∋ Ad(A )A ∋ Ad(A )A ∋ A d(A )A ∋ Ad(A )A ∋ A d(A )A ∋ A d(A )A (81)
2 2 2
∋ 10Ad(A )A + 2Ad(A ) A (82)
2 2 2 2
+ d(A )Ad(A )A + Ad(A )Ad(A ) (83)
2
∋ 3A 7 (Ad(A )A) (84)
2 2
∋ 4Ad((A 7 A )A) ∋ 4Ad(A(A 7 A )) (85)
2
+ 3A(A 7 A )A (86)
2 2
∋ 4d(A(A 7 A ))A ∋ 4d((A 7 A )A)A (87)
3 2 2 2 2 2 2
+ d(Ad(A )A)A + d(Ad(A )A)A + d(Ad(A )A )A + d(A d(A )A)A (88)
3 2 2 2 2 2 2
+ Ad(Ad(A )A) + A d(Ad(A )A) + Ad(A d(A )A) + Ad(Ad(A )A ) (89)
2
+ Ad(Ad(A )A)A (90)
(91)

Basis are in

• Y1
– 7li=1 Aai : A6 , A4 , A2 , A 7 A4 , A 7 A2 7 A3 , A2 7 A2 7 A2 , A2 7 A2 , A 7 A2 .
• Y2
– As1 d(7li=1 Aai ):Ad(A5 ), A4 d(A2 ), A3 d(A3 ), Ad(A3 ), A2 d(A4 ), A2 d(A2 ), A2 d(A2 )2 , A(d(A2 ) 7 d(A3 )).
– d(7li=1 Aai )As1 : d(A5 )A, d(A4 )A2 , d(A3 )A3 , d(A3 )A, d(A2 )A4 , d(A2 )A2 , d(A2 )2 A2 , (d(A2 ) 7 d(A3 ))A.
– d(7li=1
1
Aai )As1 d(7li=1
1
Abi ): d(A2 )Ad(A3 ), d(A3 )Ad(A2 ), d(A2 )A2 d(A2 ).
– As1 (7li=1 Aai ): A(A 7 A3 ), A(A 7 A2 7 A2 ), A(A2 7 A2 7 A), A(A 7 A2 ), A(A 7 A3 ), A2 (A 7 A2 ),
A2 (A 7 A2 ), A(A 7 A2 ).
– (7li=1 Aai )As1 : (A 7 A3 )A, (A 7 A2 7 A2 )A, (A2 7 A2 7 A)A, (A 7 A2 )A, (A 7 A3 )A, (A 7 A2 )A2 ,
(A 7 A2 )A2 , (A 7 A2 )A
– Y2 7 Y2 : A 7 ((A 7 A2 )A), A 7 ((A 7 A2 )A).
– d(Y1 )Y1 : d(A2 )(A 7 A2 )
– Y1 d(Y1 ): (A 7 A2 )d(A2 )
• Y3 :

19
 Graph As Point Set

– As Y2 : Ad(A4 )A, Ad(A2 )A3 , A3 d(A2 )A, Ad(A3 )A2 , A2 d(A3 )A, A2 d(A2 )A2 , Ad(A2 )A, Ad(A2 )2 A,
Ad(A2 )Ad(A2 ), A(A 7 A2 )A.
– Y2 As : d(A2 )Ad(A2 )A.
– Y3 7 Y3 : A 7 (Ad(A2 )A).
– d(Y2 )Y2 : d(Ad(A2 )A)A,d(A(A 7 A2 ))A,d((A 7 A2 )A)A
– Y2 d(Y2 ):Ad((A 7 A2 )A),Ad(A(A 7 A2 ))

• Y4 :
– d(Y3 )Y3 : d(Ad(A3 )A)A, d(Ad(A2 )A)A2 , d(Ad(A2 )A2 )A, d(A2 d(A2 )A)A.
– Y3 d(Y3 ): Ad(Ad(A3 )A), A2 d(Ad(A2 )A), Ad(A2 d(A2 )A), Ad(Ad(A2 )A2 ).

• Y5 :
– As1 d(Y3 )As2 :Ad(Ad(A2 )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 CL+1 = diagonal(APL )
Theorem A.13. The diagonal elements of attention matrix of 2-layer PST can express C3 , 3-layer PST can express C4 ,
4-layer PST can express C5 , C6 , 6-layer PST can express C7 .

Proof. It is a direct conjecture of Theorem A.12 as CL+1 = diagonl(APL ) and ≃k, PL → Yk ∞ APL → Yk+1

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 si and vi . Without loss of generality, we can assume that one channel of vi contains U diag(!1 /2). The
sv-mixer can simulate an MLP function applied to si . Leading to s↑i . A GIN layer will then update node representations as
follows,

!
si ⇒ s↑i + s↑j (92)
j↗N (i)

By inner products of coordinates, the attention matrix can express the adjacency matrix. By setting Wqs , Wks = 0, and
Wqv , Wkv be a diagonal matrix with only the diagonal elements at the row corresponding the the channel of U diag(!1 /2).

Kij = (Wqs si 7 Wks sj )⇑diagonal(Wqv viT vj Wkv ) ↔ ⇓diag(!1 /2)Ui , diag(!1 /2)Uj ⇔ = Aij (93)

Let MLP express an identity function.

Attenij = MLP(Kij ) ↔ Aij (94)

20
 Graph As Point Set

The attention layer will produce ! !

si ⇒ Aij s↑j = s↑j (95)
j j↗N (i)

with residual connection, the layer can express GIN

!
si ⇒ s↑i + si = s↑i + s↑j (96)
j↗N (i)

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 ⇒ MLP1 (si ⇑diagonal(W1 viT vi W2T )) (97)

Here, diagonal(W1 vi viT W2T ) 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,

Attenij = MLP(Kij ), Kij = (Wqs si 7 Wks sj )⇑diagonal(Wqv viT vj Wkv ) ↔ ⇓diag(!1 /2)Ui , diag(!1 /2)Uj ⇔ (98)

The Hadamard product (Wqs si 7 Wks sj ) 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
ˆ k )Û T ), k = 1, 2, 3, ...,
diagonal(Û diag(! (99)

where the eigendecomposition of normalized adjacency matrix D↔1/2 AD↔1/2 is Û . By computation, we find that two
graphs share the same !.ˆ Moroever, diagonal(Û diag(! ˆ k )Û T ) are equal in two graphs for k = 0, 1, 2, ..., 9, where 9 is the
number of nodes in graphs. ! and diagonal(Û diag(!
k ˆ k )Û T ) with larger k are only linear combinations of !k and thus
diagonal(Û diag(!ˆ )Û ) for k = 0, 1, ..., 9. So the RWSE in the two graphs are equal and equivalent to simply assigning
k T

feature h1 to the center node and feature h2 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.

21
 Graph As Point Set

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 v2 and v3 will share identical representations. Consequently,
the pairs (v1 , v2 ) and (v1 , v3 ) 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.

Attenij = ⇓si , sj ⇔||Aij . (100)

This element is equal for the node pair (v1 , v2 ) and (v1 , v3 ) 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 → 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 Hl denote a circle of l nodes. Let Gl denote a graph of two components, one is H↘l/2≃ and the other is H⇐l/2⇒ .
Let Hl↑ denote adding a unique feature 1 to a node in Hl (as all nodes are symmetric for even l, the selection of node does
not matter), and G↑l denote adding a unique feature 1 to one node in Gl . All other nodes have feature 0. Now we prove that
Lemma C.3. For all K → N, (K + 1)-layer MPNN can distinguish H4(K+1)
↑
and G↑4(K+1) , while K-layer MPNN and
K-layer vanilla Graph Transformer cannot distinguish.

Given H4(K+1)
↑
, G↑4(K+1) , we assign each node a color according to its distance to the node with extra label 1: c0 (the
labeled node itself), c1 (two nodes connected to the labeled node), c2 (two nodes whose shortest path distance to the labeled
node is 2),..., cK (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,
≃i ∝ k, ci nodes have the same representation (denoted as hki ), respectively, ck+1 , ck+2 , ..., cK , c>K nodes all have the
same representation (denoted as hkk+1 ).
Initially, all c0 nodes have representation h00 , all other nodes have representation h01 in both graph.
Assume at k-th layer, ≃i ∝ k, ci nodes have the same representation hki , respectively, ck+1 , ck+1 , ..., cK , c>K nodes all
have the same representation hkk+1 . At k + 1-th layer, c0 node have two neighbors of representation hk1 . all ci , 1 < i <= k
node two neighbors of representations hki↔1 and hki+1 , respectively. ck+1 nodes have two neighbors of representation hkk and
hkk+1 . All other nodes have two neighbors of representation hkk+1 . So ci , i ∝ k + 1 nodes have the same representation
(denoted as hk+1
i ), respectively, ck+1+1 , ..., cK , c>K nodes all have the same representation (denoted as hkk+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 G4(K+1) is of shortest path distance K + 1 to the labeled
node. It also have two neighbors of representation hK
K . While such a node is not exist in H4(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

22
 Graph As Point Set

Figure 2. The failure of using inner products of permutation-equivariant node representations to predict shortest path distance. v2
and v3 have equal node representations due to symmetry. Therefore, (v1 , v2 ) and (v1 , v3 ) 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  ↓ Û !
˜ T T
D ⇐ A ↓ Ũ !Ũ , A ↓ U !U . di denote the degree of node i.

Method Description Connection

Random walk matrix (Li k-step random walk matrix is (D A) , whose
↔1 k
(D↔1 A)kij
et al., 2020; Dwivedi et al., element (i, j) is the probability that a k-step ran- = (D
&
↔1/2
(Â)k D1/2 )ij
2023; Rampásek et al., dom walk starting from node i ends at node j. =
dj ˆ k )Ûj ⇑
⇒Ûi , diag(!
di
2022)

Heat kernel matrix (Mi- Heat kernel is a solution of the heat equation. Its ˜
(I + Ũ (diag(exp(⇐t!))⇐I) Ũ T )ij
alon et al., 2021) element (i, j) represent how much heat diffuse ˜
=ϑij +⇒Ũi , (diag(exp(⇐t!))⇐I) Ũj ⇑
from node i to node j
Resistance dis- Its element (i, j) is the resistance between node (Ũ diag(!˜ ↔1 )Ũ T )ij
tance (Zhang & Li, i, j considering the graph as an electrical network. = ⇒Ũi , diag(!˜ ↔1 )Ũj ⇑
2021; Zhang et al., 2023b) It is also the pseudo-inverse of laplacian matrix L,
Equivariant and stable The encoding of node pair i, j is ⇑1K 7(Ui ∋Uj )⇑, ↑1K → (Ui ⇐ Uj )↑2
laplacian PE (Wang et al., where 1K means a vector → Rr with its elements = ⇒Ui , diag(1K )Ui ⇑
2022) coresponding to K largest eigenvalue of L +⇒Uj , diag(1K )Uj ⇑
⇐2⇒Ui , diag(1K )Uj ⇑
Degree and number of tri- di is the number of edges, and ti is the number of di = ⇒Ui , diag(!2 )Uj ⇑.
angular (Bouritsas et al., triangular rooted in node i. ti = ⇒Ui , diag(!3 )Uj ⇑
2023)

path distance as a feature. However, our analysis highlights that aggregating information from the entire graph is insufficient
for capturing long-range interactions.

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).

E. Datasets
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

23
 Graph As Point Set

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

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

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.

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

24
 Graph As Point Set

Table 8. Results on peptide-func and peptide-struct dataset with 1M parameter budget.

peptide-func peptide-struct
Graph-MLPMixer 0.6970 ± 0.0080 0.2475 ± 0.0015
GraphGPS 0.6535 ± 0.0041 0.2500 ± 0.0005
PST 0.6984 ± 0.0051 0.2470 ± 0.0015

Rank 𝑟 Rank 𝑟
Hidden
Batch Matrix Multiplication

#node 𝑛
dimension 𝑑

#node 𝑛
2 −1 −1 0 0 0 Eigen-
−1 2 −1 0 0 0
decomposition Diagonal
−1 −1 2 0 0 0
0 0 0 2 −1 −1 Eigenvector 𝑉 matrice
0 0 0 −1 2 −1
Rank 𝑟 Rank 𝑟

DeepSet
0 0 0 −1 −1 2
Hidden
Laplacian Matrix
dimension 𝑑
Eigenvalue Λ
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.

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

G. Architecture
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.

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

25
 Graph As Point Set

(a) (b) (c)

𝑠 =𝑥 𝑣 =𝑄 𝑠 𝑣 𝑠 𝑣 𝑠 𝑣
MLP
sv mixer 𝑊 𝑊 𝑊 𝑊
𝑊 𝑊 𝑊 𝑊 ⟨⋅,⋅⟩
N× ⟨⋅,⋅⟩ MLP
Attention MLP Atten

𝑠 𝑣 𝑠 𝑣′ 𝑠 𝑣
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. si and s→i denote the scalar
representations of node i, and ϖvi and ϖvi→ denote the vector representations. xi is the initial features of node i. Qi and point coordinates of
node i produced by parameterized SRD in Section 3.2.

Table 9. Ablation study on qm9 dataset.

µ ω εhomo εlumo ”ε R2 ZPVE U0 U H G Cv
Unit 10↔1 D 10↔1 a30 10↔2 meV 10↔2 meV 10↔2 meV a20 10↔2 meV meV meV meV meV 10↔2 cal/mol/K
PST 3.19±0.04 1.89±0.04 5.98±0.09 5.84±0.08 8.46±0.07 13.08±0.16 0.39±0.01 3.46±0.17 3.55±0.10 3.49±0.20 3.55±0.17 7.77±0.15
PST-onelayer 3.72±0.02 2.25±0.05 6.62±0.11 6.67±0.07 9.37±0.15 15.95±0.29 0.55±0.01 3.46±0.06 3.50±0.14 3.50±0.03 3.45±0.07 9.62±0.24
PST-gc 3.34±0.02 1.93±0.03 6.08±0.11 6.10±0.10 8.65±0.10 13.71±0.12 0.40±0.01 3.38±0.13 3.43±0.12 3.33±0.08 3.29±0.11 8.04±0.15
PST-adj 3.16±0.02 1.86±0.01 6.31±0.06 6.10±0.05 8.84±0.01 13.60±0.09 0.39±0.01 3.59±0.12 3.73±0.08 3.65±0.06 3.60±0.016 7.62±0.21
PST-normadj 3.22±0.04 1.85±0.02 5.97±0.23 6.15±0.07 8.79±0.04 13.42±0.15 0.41±0.01 3.36±0.25 3.41±0.24 3.46±0.18 3.38±0.23 8.10±0.12
PSDS 3.53±0.05 2.05±0.02 6.56±0.03 6.31±0.05 9.13±0.04 14.35±0.02 0.41±0.02 3.53±0.11 3.49±0.05 3.47±0.04 3.56±0.14 8.35±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

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.

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.

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.

26
 Graph As Point Set

Table 10. Ablation study on Long Range Graph Benchmark dataset.

Model PascalVOC-SP Peptides-Func Peptides-Struct
PST 0.4010±0.0072 0.6984±0.0051 0.2470±0.0015
PST-onelayer 0.3229±0.0051 0.6517±0.0076 0.2634±0.0019
PST-gc 0.4007±0.0039 0.6439±0.0342 0.2564±0.0120

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

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 si → Rd , and its
vector representation is denoted by vi → Rr→d , where d is the hidden dimension, and r is the rank of coordinates. si
is initialized with the input node feature Xi , and vi 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.

s↑i ⇒ MLP1 (si ⇑diagonal(W1 viT vi W2T )), (101)

vi↑ ⇒ vi diag(MLP2 (si ))W3 + vi W4 (102)

Here, W1 , W2 , W3 , and W4 → Rd→d are learnable matrices for mixing different channels of vector features. Additionally,
MLP1 : R2d↓d and MLP2 : Rd↓d represent two multi-layer perceptrons transforming scalar representations. The operation
diagonal(W1 viT vi W2 ) takes the diagonal elements of a matrix, which translates vectors to scalars, while diag(MLP2 (si ))vi
transforms scalar features into vectors. As viT RT Rvi = viT vi , ≃R → 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.
!
s↓ MLP3 (si ) (103)
i↗V
!
v↓ vi W 5 (104)
i↗V
!
vsq ↓ vi W6 W7 viT (105)
i↗V

Here, W5 , W6 and W7 → Rd→d denote the linear transformations vectors. MLP3 : Rd ↔ Rd is an MLP converting scalars.
Global feature s → Rd is scalar, vRr→d is vector, and vsq → Rr→r is the sum of square for each vector.
Point Representation Update. Each point representation is updated by combining global features.
si ↓ MLP4 (si + s) (106)
vi ↓ vsq vi + vW8 (107)

si is combined with global scalar s and transformed with an MLP MLP4 : Rd ↔ Rd . vi is combined with vsq and v with
linear layer W8 → Rd→d .

27
 Graph As Point Set

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

Table 13. TU dataset evaluation result.

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

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

s ⇒ Pool({si |i → V }), (108)

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

28