# Improving Graph Neural Networks on Multi-node Tasks with Labeling Tricks

Xiyuan Wang<EMAIL_ADDRESS>
Institute for Artificial Intelligence
Peking University
Beijing, China Pan Li<EMAIL_ADDRESS>
School of Electrical and Computer Engineering
Georgia Institute of Technology
Atlanta, USA Muhan Zhang<EMAIL_ADDRESS>
Institute for Artificial Intelligence
Peking University
Beijing, China

###### Abstract

In this paper, we provide a theory of using graph neural networks (GNNs) for
multi-node representation learning, where we are interested in learning a
representation for a set of more than one node such as a link. Existing GNNs
are mainly designed to learn single-node representations. When we want to
learn a node-set representation involving multiple nodes, a common practice in
previous works is to directly aggregate the single-node representations
obtained by a GNN. In this paper, we show a fundamental limitation of such an
approach, namely the inability to capture the dependence among multiple nodes
in a node set, and argue that directly aggregating individual node
representations fails to produce an effective joint representation for
multiple nodes. A straightforward solution is to distinguish target nodes from
others. Formalizing this idea, we propose labeling trick, which first labels
nodes in the graph according to their relationships with the target node set
before applying a GNN and then aggregates node representations obtained in the
labeled graph for multi-node representations. The labeling trick also unifies
a few previous successful works for multi-node representation learning,
including SEAL, Distance Encoding, ID-GNN, and NBFNet. Besides node sets in
graphs, we also extend labeling tricks to posets, subsets and hypergraphs.
Experiments verify that the labeling trick technique can boost GNNs on various
tasks, including undirected link prediction, directed link prediction,
hyperedge prediction, and subgraph prediction. Our work explains the superior
performance of previous node-labeling-based methods and establishes a
theoretical foundation for using GNNs for multi-node representation learning.

Keywords: Graph Neural Networks, Multi-node Representation, Subgraph.

##  1 Introduction

Graph neural networks (GNNs) (Scarselli et al., 2009; Bruna et al., 2013;
Duvenaud et al., 2015; Li et al., 2015; Kipf and Welling, 2016a; Defferrard et
al., 2016; Dai et al., 2016; Veličković et al., 2017; Zhang et al., 2018b;
Ying et al., 2018) have achieved great successes in recent years. While GNNs
have been well studied for single-node tasks (such as node classification) and
whole-graph tasks (such as graph classification), using GNNs on tasks that
involve multi-nodes is less studied and less understood. Among such multi-node
representation learning problems, link prediction (predicting the link
existence/class/value between a set of two nodes) is perhaps the most
important one due to its wide applications in practice, such as friend
recommendation in social networks (Adamic and Adar, 2003), movie
recommendation in Netflix (Bennett et al., 2007), protein interaction
prediction (Qi et al., 2006), drug response prediction (Stanfield et al.,
2017), and knowledge graph completion (Nickel et al., 2015). Besides link
prediction, other multi-node tasks, like subgraph classification and hyperedge
prediction, are relatively new but have found applications in gene set
analysis (Wang et al., 2020), user profiling (Alsentzer et al., 2020a), drug
interaction prediction (Srinivasan et al., 2021), temporal network modeling
(Liu et al., 2022), group recommendation Amer-Yahia et al. (2009), etc. In
this paper, we study the ability of GNNs to learn multi-node representations.
As the link task is the simplest multi-node case, we mainly use link
prediction in this paper to visualize and illustrate our method and theory.
However, our theory and method apply generally to all multi-node
representation learning problems such as subgraph (Alsentzer et al., 2020b),
hyperedge (Zhang et al., 2018a) and network motif (Liu et al., 2022)
prediction tasks.

Starting from the link prediction task, we illustrate the deficiency of
existing GNN models for multi-node representation learning which motivates our
labeling trick. There are two main classes of GNN-based link prediction
methods: Graph AutoEncoder (GAE) (Kipf and Welling, 2016b) and SEAL (Zhang and
Chen, 2018b; Li et al., 2020). GAE and its variational version VGAE (Kipf and
Welling, 2016b) first apply a GNN to the entire graph to compute a
representation for each node. The representations of the two end nodes of the
link are then aggregated to predict the target link. On the contrary, SEAL
assigns node labels according to their distances to the two end nodes before
applying the GNN on the graph. SEAL often shows much better practical
performance than GAE. The key lies in SEAL’s node labeling step.

We first give a simple example to show when GAE fails. In Figure 1(a), $v_{2}$
and $v_{3}$ have symmetric positions in the graph—from their respective views,
they have the same $h$-hop neighborhood for any $h$. Thus, without node
features, GAE will learn the same representation for $v_{2}$ and $v_{3}$.
Therefore, when predicting which one of $v_{2}$ and $v_{3}$ is more likely to
form a link with $v_{1}$, GAE will aggregate the representations of $v_{1}$
and $v_{2}$ as the link representation of $(v_{1},v_{2})$, and aggregate the
representations of $v_{1}$ and $v_{3}$ to represent $(v_{1},v_{3})$, thus
giving $(v_{1},v_{2})$ and $(v_{1},v_{3})$ the same representation and
prediction. The failure to distinguish links $(v_{1},v_{2})$ and
$(v_{1},v_{3})$ that have different structural roles in the graph reflects one
key limitation of GAE-type methods: by computing $v_{1}$ and $v_{2}$’s
representations independently of each other, GAE cannot capture the dependence
between two end nodes of a link. For example, $(v_{1},v_{2})$ has a much
smaller shortest path distance than that of $(v_{1},v_{3})$; and
$(v_{1},v_{2})$ has both nodes in the same hexagon, while $(v_{1},v_{3})$ does
not.

(a)

(b)

Figure 1: (a) In this graph, nodes $v_{2}$ and $v_{3}$ are isomorphic; links
$(v_{1},v_{2})$ and $(v_{4},v_{3})$ are isomorphic; link $(v_{1},v_{2})$ and
link $(v_{1},v_{3})$ are not isomorphic. However, if we aggregate two node
representations learned by a GNN as the link representation, we will give
$(v_{1},v_{2})$ and $(v_{1},v_{3})$ the same prediction. (b) In this graph,
nodes $v_{3}$ and $v_{4}$ are isomorphic. Aggregating the node embeddings
within the subgraph, GNN will produce equal embeddings for subgraphs
$(v_{1},v_{2},v_{3})$ and $(v_{1},v_{2},v_{4})$, while the two subgraphs are
not isomorphic. This problem was first observed by You et al. (2019), which
was interpret as the failure of GNNs to capture node positions, and later
became more formalized in (Srinivasan and Ribeiro, 2020).

Take common neighbor (CN) (Liben-Nowell and Kleinberg, 2007), one elementary
heuristic feature for link prediction, as another example. CN counts the
number of common neighbors between two nodes to measure their likelihood of
forming a link. It is the foundation of many other successful heuristics such
as Adamic-Adar (Adamic and Adar, 2003) and Resource Allocation (Zhou et al.,
2009), which are also based on neighborhood overlap. However, GAE cannot
capture such neighborhood-overlap-based features. As shown in Figure 1(a),
there is $1$ common neighbor between $(v_{1},v_{2})$ and $0$ between
$(v_{1},v_{3})$, but GAE always gives $(v_{1},v_{2})$ and $(v_{1},v_{3})$ the
same representation. The failure to learn common neighbor demonstrates GAE’s
severe limitation for link prediction. The root cause still lies in that GAE
computes node representations independently of each other, and when computing
the representation of one end node, it is unaware of the other end node.

In fact, GAE represents a common practice of using GNNs to learn multi-node
representations. That is, obtaining individual node representations through a
GNN and then aggregating the representations of those target nodes as the
multi-node representation. Similar failures caused by independence of node
representation learning also happen in general multi-node representation
learning problems. In the subgraph representation learning task, which is to
learn representations for subgraphs inside a large graph (Alsentzer et al.,
2020a), representations aggregated from independently computed node
representations will fail to differentiate nodes inside and outside the
subgraph. Figure 1(b) (from Wang and Zhang (2022)) shows an example. Directly
aggregating node embeddings produced by a GNN will lead to the same
representation for subgraphs $(v_{1},v_{2},v_{3})$ and $(v_{1},v_{2},v_{4})$.
However, the former subgraph forms a triangle while the latter one does not.

This paper solves the above type of failures from a structural representation
learning point of view. We adopt and generalize the notion most expressive
structural representation (Srinivasan and Ribeiro, 2020), which gives multi-
node substructure the same representation if and only if they are isomorphic
(a.k.a. symmetric, on the same orbit) in the graph. For example, link
$(v_{1},v_{2})$ and link $(v_{4},v_{3})$ in Figure 1(a) are isomorphic, and a
most expressive structural representation should give them the same
representation. On the other hand, a most expressive structural representation
will discriminate all non-isomorphic links (such as $(v_{1},v_{2})$ and
$(v_{1},v_{3})$). According to our discussion above, GAE-type methods that
directly aggregate node representations cannot learn a most expressive
structural representation. Then, how to learn a most expressive structural
representation of node sets?

To answer this question, we revisit the other GNN-based link prediction
framework, SEAL, and analyze how node labeling helps a GNN learn better node
set representations. We find that two properties of the node labeling are
crucial for its effectiveness: 1) target-nodes-distinguishing and 2)
permutation equivariance. With these two properties, we define set labeling
trick, which considers each multi-node substructure as a node set and unifies
previous node labeling methods into a single and most general form.
Theoretically, we prove that with set labeling trick, a sufficiently
expressive GNN can learn most expressive structural representations of node
sets (Theorem 12), which reassures GNN’s node set prediction ability. It also
closes the gap between the nature of GNNs to learn node representations and
the need of multi-node representation learning in node-set-based inference
tasks.

Set labeling trick is for multi-node structure of a node set and can be used
on a wide range of tasks including link prediction and subgraph
classification. However, to describe and unify even more tasks and methods, we
propose three extensions of set labeling trick. One is poset labeling trick.
In some tasks, target nodes may have intrinsic order relations in real-world
problems. For example, in citation graphs, each link is from the citing
article to the cited one. In such cases, describing multi-node substructures
with node sets leads to loss of order information. This motivates us to add
order information to the label and use poset instead to describe
substructures. Another extension is subset labeling trick. It unifies labeling
methods besides SEAL (Zhang and Chen, 2018a), like ID-GNN (You et al., 2021)
and NBFNet (Zhu et al., 2021). These works label only a subset of nodes each
time. We formalize these methods and analyze the expressivity: when using GNNs
without strong expressivity, subset labeling trick exhibits higher
expressivity than labeling tricks in some cases. Last but not least, by
converting hypergraph to bipartite graph, we straightforwardly extend labeling
trick to hypergraph.

##  2 Preliminaries

In this section, we introduce some important concepts that will be used in the
analysis of the paper, including permutation, poset isomorphism and most
expressive structural representation.

We consider a graph ${\mathcal{G}}=(V,E,{\bm{\mathsfit{A}}})$, where
$V=\\{1,2,\ldots,n\\}$ is the set of $n$ vertices, $E\subseteq V\times V$ is
the set of edges, and ${\bm{\mathsfit{A}}}\in\mathbb{R}^{n\times n\times k}$
is a 3-dimensional tensor containing node and edge features. The diagonal
components ${\bm{\mathsfit{A}}}_{i,i,:}$ denote features of node $i$, and the
off-diagonal components ${\bm{\mathsfit{A}}}_{i,j,:}$ denote features of edge
$(i,j)$. The node/edge types can also be expressed in ${\bm{\mathsfit{A}}}$
using integers or one-hot encoding vectors for heterogeneous graphs. We
further use ${\bm{A}}\in\\{0,1\\}^{n\times n}$ to denote the adjacency matrix
of ${\mathcal{G}}$ with ${\bm{A}}_{i,j}=1$ iff $(i,j)\in E$, where it is
possible ${\bm{A}}_{i,j}\neq{\bm{A}}_{j,i}$. We let ${\bm{A}}$ be the first
slice of ${\bm{\mathsfit{A}}}$, i.e., ${\bm{A}}={\bm{\mathsfit{A}}}_{:,:,1}$.
Since ${\bm{\mathsfit{A}}}$ contains the complete information of a graph, we
also directly denote the graph by ${\bm{\mathsfit{A}}}$.

###  2.1 Permutation

###### Definition 1

A permutation $\pi$ is a bijective mapping from $\\{1,2,\ldots,n\\}$ to
$\\{1,2,\ldots,n\\}$. All $n!$ possible $\pi$’s constitute the permutation
group $\Pi_{n}$.

Depending on the context, permutation $\pi$ can mean assigning a new index
$\pi(i)$ to node $i\in V$, or mapping node $i$ to node $\pi(i)$ of another
graph. Slightly extending the notation, we let the permutation of a
set/sequence denote permuting each element in the set/sequence. For example,
permutation $\pi$ maps a set of nodes $S\subseteq V$ to $\pi(S)=\\{\pi(i)|i\in
S\\}$ and maps a set of node pairs $S^{\prime}\subseteq V\times V$ to
$\pi(S^{\prime})=\\{\pi((i,j))|(i,j)\in
S^{\prime}\\}=\\{(\pi(i),\pi(j))|(i,j)\in S^{\prime}\\}$. The permutation of a
graph’s tensor ${\bm{\mathsfit{A}}}$, denoted as $\pi({\bm{\mathsfit{A}}})$,
can also be defined. As $i$-th node and $j$-th node will have new index
$\pi(i),\pi(j)$ while keeping the features of the pair,
$\pi({\bm{\mathsfit{A}}})_{\pi(i),\pi(j)}={\bm{\mathsfit{A}}}_{i,j}$.

Permutation is closely related to graph isomorphism, whether two graphs
describe the same structure. Intuitively, as nodes in graphs have no order, no
matter what permutation is applied to a graph, the transformed graph should be
isomorphic to the original graph. Similarly, if one graph can be transformed
into another under some permutation, the two graphs should also be isomorphic.
Formally speaking,

###### Definition 2

Two graphs ${\bm{\mathsfit{A}}}\in{\mathbb{R}}^{n\times n\times
d},{\bm{\mathsfit{A}}}^{\prime}\in{\mathbb{R}}^{n^{\prime}\times
n^{\prime}\times d^{\prime}}$ are isomorphic iff there exists $\pi\in\Pi_{n}$,
$\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime}$.

In whole graph classification tasks, models should give isomorphic graphs the
same prediction as they describe the same structure, and differentiate non-
isomorphic graphs.

###  2.2 Poset isomorphism

To describe a substructure defined by a subset of nodes with internal
relation, like a directed edge, we introduce poset. A poset is a set with a
partial order. Partial order is a reflexive, antisymmetric, and transitive
homogeneous relation on the set (Davey and Priestley, 2002).

###### Definition 3

A poset $S$ is a tuple $(U,\leq_{S})$, where $U$ is a set, and
$\leq_{S}\subseteq U\times U$ is a relation on $U$. Let $u\leq_{S}v$ denote
$(u,v)\in\leq_{S}$. $\leq_{S}$ fulfills the following conditions.

  1. 1.

Reflexivity. $\forall v\in U,v\leq_{S}v$.

  2. 2.

Antisymmetry. $\forall u,v\in U$, if $u\leq_{S}v$ and $v\leq_{S}u$, then
$u=v$.

  3. 3.

Transitivity. $\forall u,v,w\in U$, if $u\leq_{S}v$ and $v\leq_{S}w$, then
$u\leq_{S}w$.

The permutation operation on partial order relation and poset is defined as
follows.

$\displaystyle\pi(\leq_{S})=\pi(\\{(u,v)~{}|~{}(u,v)\in\leq_{S}\\})$
$\displaystyle=\\{(\pi(u),\pi(v))~{}|~{}(u,v)\in\leq_{S}\\},$ (1)
$\displaystyle\pi(S)=\pi((U,\leq_{S}))$
$\displaystyle=(\pi(U),\pi(\leq_{S})).$ (2)

To describe when two posets derive the same substructure, we define poset
isomorphism, which generalizes graph isomorphism to arbitrary node posets in a
graph.

###### Definition 4

(Poset isomorphism) Given two graphs
${\mathcal{G}}=(V,E,{\bm{\mathsfit{A}}})$,
${\mathcal{G}}^{\prime}=(V^{\prime},E^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
and two node posets $S=(U,\leq_{S}),U\subseteq V$,
$S^{\prime}=(U^{\prime},\leq_{S^{\prime}}),U^{\prime}\subseteq V^{\prime}$, we
say substructures $(S,{\bm{\mathsfit{A}}})$ and
$(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$ are isomorphic (denoted by
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$) iff
$\exists\pi\in\Pi_{n},S=\pi(S^{\prime})$ and
${\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})$.

Set is a particular case of poset, where the partial order only contains
reflexive relations $u\leq_{S}u,u\in U$. It can describe substructures without
order, like undirected edges and subgraphs. Abusing the notation of poset, we
sometimes also use $S$ to denote a set and omit the trivial partial order
relation. Then, set isomorphism is defined in the following.

###### Definition 5

(Set isomorphism) Given two graphs ${\mathcal{G}}=(V,E,{\bm{\mathsfit{A}}})$,
${\mathcal{G}}^{\prime}=(V^{\prime},E^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
and two node sets $S\subseteq V$, $S^{\prime}\subseteq V^{\prime}$, we say
substructures $(S,{\bm{\mathsfit{A}}})$ and
$(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$ are isomorphic (denoted by
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$) iff
$\exists\pi\in\Pi_{n},S=\pi(S^{\prime})$ and
${\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})$.

Note that both set and poset isomorphism are more strict than graph
isomorphism. They not only need a permutation which maps one graph to the
other but also require the permutation to map a specific node poset $S$ to
$S^{\prime}$.

In practice, when the target node poset does not contain all nodes in the
graph, we are often more concerned with the case of
${\bm{\mathsfit{A}}}={\bm{\mathsfit{A}}}^{\prime}$, where isomorphic node
posets are defined in the same graph. For example, when
$S=\\{i\\},S^{\prime}=\\{j\\}$ and
$(i,{\bm{\mathsfit{A}}})\simeq(j,{\bm{\mathsfit{A}}})$, we say nodes $i$ and
$j$ are isomorphic in graph ${\bm{\mathsfit{A}}}$ (or they have symmetric
positions/same structural role in graph ${\bm{\mathsfit{A}}}$). An example is
$v_{2}$ and $v_{3}$ in Figure 1(a). Similarly, edge and subgraph isomorphism
can also be defined as the isomorphism of their node posets.

###  2.3 Structural Representations

Graph models should produce the same prediction for isomorphic substructures.
We define permutation invariance and equivariance to formalize this property.
A function $f$ defined over the space of $(S,{\bm{\mathsfit{A}}})$ is
permutation invariant (or invariant for abbreviation) if
$\forall\pi\in\Pi_{n}$,
$f(S,{\bm{\mathsfit{A}}})=f(\pi(S),\pi({\bm{\mathsfit{A}}}))$. Similarly, $f$
is permutation equivariant if $\forall\pi\in\Pi_{n}$,
$\pi(f(S,{\bm{\mathsfit{A}}}))=f(\pi(S),\pi({\bm{\mathsfit{A}}}))$.
Permutation invariance/equivariance ensures that representations learned by a
GNN are invariant to node indexing, a fundamental design principle of GNNs.

Now we define the most expressive structural representation of a substructure
$(S,{\bm{\mathsfit{A}}})$, following (Srinivasan and Ribeiro, 2020; Li et al.,
2020). It assigns a unique representation to each equivalence class of
isomorphic substructures.

###### Definition 6

Given an invariant function $\Gamma(\cdot)$, $\Gamma(S,{\bm{\mathsfit{A}}})$
is a most expressive structural representation for $(S,{\bm{\mathsfit{A}}})$
if $\forall
S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime},~{}\Gamma(S,{\bm{\mathsfit{A}}})=\Gamma(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})\Leftrightarrow(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$.

For simplicity, we will directly use structural representation to denote most
expressive structural representation in the rest of the paper. We will omit
${\bm{\mathsfit{A}}}$ if it is clear from context. For a graph
${\bm{\mathsfit{A}}}$, we call
$\Gamma({\bm{\mathsfit{A}}})=\Gamma(\emptyset,{\bm{\mathsfit{A}}})$ a
structural graph representation, $\Gamma(i,{\bm{\mathsfit{A}}})$ a structural
node representation for node $i$, and call
$\Gamma(\\{i,j\\},{\bm{\mathsfit{A}}})$ a structural link representation for
link $(i,j)$. For a general node poset $S$, we call
$\Gamma(S,{\bm{\mathsfit{A}}})$ a structural multi-node representation for
$S$.

Definition 6 requires that the structural representations of two substructures
are the same if and only if the two substructures are isomorphic. That is,
isomorphic substructures always have the same structural representation, while
non-isomorphic substructures always have different structural representations.
Due to the permutation invariance requirement, models should not distinguish
isomorphic substructures. This implies that structural representations can
discriminate all substructures that any invariant model can differentiate, and
structural representations reach the highest expressivity.

##  3 The limitation of directly aggregating node representations

In this section, taking GAE for link prediction as an example, we show the
critical limitation of directly aggregating node representations as a multi-
node representation.

###  3.1 GAE for multi-node representation

GAE (Kipf and Welling, 2016b) is a kind of link prediction model with GNN.
Given a graph ${\bm{\mathsfit{A}}}$, GAE first uses a GNN to compute a node
representation ${\bm{z}}_{i}$ for each node $i$, and then use the inner
product of ${\bm{z}}_{i}$ and ${\bm{z}}_{j}$ to predict link $\\{i,j\\}$:

$\displaystyle\hat{{\bm{A}}}_{i,j}=\text{sigmoid}({\bm{z}}_{i}^{\top}{\bm{z}}_{j}),~{}\text{where}~{}{\bm{z}}_{i}\\!=\\!\text{GNN}(i,{\bm{\mathsfit{A}}}),{\bm{z}}_{j}\\!=\\!\text{GNN}(j,{\bm{\mathsfit{A}}}).$

Here $\hat{{\bm{A}}}_{i,j}$ is the predicted score for link $\\{i,j\\}$. The
model is trained to maximize the likelihood of reconstructing the true
adjacency matrix. The original GAE uses a two-layer GCN (Kipf and Welling,
2016a) as the GNN. In principle, we can replace GCN with any GNN, use any
aggregation function over the set of target node embeddings including mean,
sum, and Hadamard product other than inner product, and substitute the sigmoid
with an MLP. Then, GAE can be used for multi-node tasks. It aggregates target
node embeddings produced by the GNN:

${\bm{z}}_{S}=\text{MLP}(\text{AGG}(\\{{\bm{z}}_{i}|i\in
S\\}))~{}\text{where}~{}{\bm{z}}_{i}\\!=\\!\text{GNN}(i,{\bm{\mathsfit{A}}}),$
(3)

where AGG is an aggregation function. We will use GAE to denote this general
class of GNN-based multi-node representation learning methods in the
following. Two natural questions are: 1) Is the node representation learned by
the GNN a structural node representation? 2) Is the multi-node representation
aggregated from a set of node representations a structural representation for
the node set? We answer them respectively in the following.

###  3.2 GNN and structural node representation

Practical GNNs (Gilmer et al., 2017) usually simulate the 1-dimensional
Weisfeiler-Lehman (1-WL) test (Weisfeiler and Lehman, 1968) to iteratively
update each node’s representation by aggregating its neighbors’
representations. We use 1-WL-GNN to denote a GNN with 1-WL discriminating
power, such as GIN (Xu et al., 2018).

A 1-WL-GNN ensures that isomorphic nodes always have the same representation.
However, the opposite direction is not guaranteed. For example, a 1-WL-GNN
gives the same representation to all nodes in an $r$-regular graph, in which
non-isomorphic nodes exist. Despite this, 1-WL is known to discriminate almost
all non-isomorphic nodes (Babai and Kucera, 1979), which indicates that a
1-WL-GNN can give different representations to almost all non-isomorphic
nodes.

To study GNN’s maximum expressivity, we define a node-most-expressive (NME)
GNN, which gives different representations to all non-isomorphic nodes.

###### Definition 7

A GNN is node-most-expressive (NME) if $\forall
i,{\bm{\mathsfit{A}}}$,$j,{\bm{\mathsfit{A}}}^{\prime}$,
$~{}\text{GNN}(i,{\bm{\mathsfit{A}}})=\text{GNN}(j,{\bm{\mathsfit{A}}}^{\prime})\Leftrightarrow(i,{\bm{\mathsfit{A}}})\simeq(j,{\bm{\mathsfit{A}}}^{\prime})$.

NME GNN learns structural node representations 111Although a polynomial-time
implementation is not known for NME GNNs, many practical softwares can
discriminate all non-isomorphic nodes quite efficiently (McKay and Piperno,
2014), which provides a promising direction.. We define such a GNN because our
primary focus is multi-node representation. NME GNN ignores the single-node
expressivity limitation and simplifies our analysis.

###  3.3 GAE cannot learn structural multi-node representations

Suppose GAE is equipped with an NME GNN producing structural node
representations. Then the question becomes: does the aggregation of structural
node representations of the target nodes result in a structural representation
of the target node set? The answer is no. We have already illustrated this
problem in the introduction: In Figure 1(a), we have two isomorphic nodes
$v_{2}$ and $v_{3}$, and thus $v_{2}$ and $v_{3}$ will have the same
structural node representation. By aggregating structural node
representations, GAE will give $(v_{1},v_{2})$ and $(v_{1},v_{3})$ the same
link representation. However, $(v_{1},v_{2})$ and $(v_{1},v_{3})$ are not
isomorphic in the graph. Figure 1(b) gives another example on the multi-node
case involving more than two nodes. Previous works have similar examples
(Srinivasan and Ribeiro, 2020; Zhang and Chen, 2020). All these results
indicate that:

###### Proposition 8

GAE cannot learn structural multi-node representations no matter how
expressive node representations a GNN can learn.

The root cause of this problem is that GNN computes node representations
independently without being aware of the other nodes in the target node set
$S$. Thus, even though GNN learns the most expressive single-node
representations, there is never a guarantee that their aggregation is a
structural representation of a node set. In other words, the multi-node
representation learning problem is not breakable into multiple independent
single-node representation learning problems. We need to consider the
dependency between the target nodes when computing their single-node
representations.

##  4 Labeling trick for set

Starting from a common case in real-world applications, we first describe the
multi-node substructure defined by a node set (instead of a poset) in the
graph and define set labeling trick. The majority of this part is included in
our conference paper (Zhang et al., 2021a).

###  4.1 Definition of set labeling trick

The set labeling trick is defined as follows.

###### Definition 9

(Set labeling trick) Given a graph ${\bm{\mathsfit{A}}}$ and a set $S$ of
nodes in the graph, we stack a labeling tensor
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})\in\mathbb{R}^{n\times n\times d}$
in the third dimension of ${\bm{\mathsfit{A}}}$ to get a new
${\bm{\mathsfit{A}}}^{(S)}\in\mathbb{R}^{n\times n\times(k+d)}$, where
${\bm{\mathsfit{L}}}$ satisfies: $\forall
S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime},\pi\in\Pi_{n}$,

  1. 1.

(target-nodes-distinguishing)
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))\Rightarrow
S=\pi(S^{\prime})$.

  2. 2.

(permutation equivariance)
$S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})\Rightarrow{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$.

To explain a bit, labeling trick assigns a label vector to each node/edge in
graph ${\bm{\mathsfit{A}}}$, which constitutes the labeling tensor
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})$. By concatenating
${\bm{\mathsfit{A}}}$ and ${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})$, we get
the new labeled graph ${\bm{\mathsfit{A}}}^{(S)}$. By definition, we can
assign labels to both nodes and edges. However, in this paper, we consider
node labels only by default for simplicity, i.e., we let the off-diagonal
components ${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})_{i,j,:},i\neq j$ be all
zero.

The labeling tensor ${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})$ should
satisfy two properties in Definition 9. Property 1 requires that if a
permutation $\pi$ preserving node labels (i.e.,
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$)
exists between nodes of ${\bm{\mathsfit{A}}}$ and
${\bm{\mathsfit{A}}}^{\prime}$, then the nodes in $S^{\prime}$ must be mapped
to nodes in $S$ by $\pi$ (i.e., $S=\pi(S^{\prime})$). A sufficient condition
for property 1 is to make the target nodes $S$ have distinct labels from those
of the rest nodes so that $S$ is distinguishable from others. Property 2
requires that when $(S,{\bm{\mathsfit{A}}})$ and
$(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$ are isomorphic under $\pi$ (i.e.,
$S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})$),
the corresponding nodes $i\in S,j\in S^{\prime},i=\pi(j)$ must always have the
same label (i.e.,
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$).
A sufficient condition for property 2 is to make the labeling function
permutation equivariant, i.e., when the target $(S,{\bm{\mathsfit{A}}})$
changes to $(\pi(S),\pi({\bm{\mathsfit{A}}}))$, the labeling tensor
${\bm{\mathsfit{L}}}(\pi(S),\pi({\bm{\mathsfit{A}}}))$ should equivariantly
change to $\pi({\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}}))$.

###  4.2 How labeling trick works

Obviously, labeling trick puts extra information into the graph, while the
details remain unclear. To show some intuition on how labeling trick boosts
graph neural networks, we introduce a simplest labeling trick satisfying the
two properties in Definition 9.

###### Definition 10

(Zero-one labeling trick) Given a graph ${\bm{\mathsfit{A}}}$ and a set of
nodes $S$ to predict, we give it a diagonal labeling matrix
${\bm{\mathsfit{L}}}_{zo}(S,{\bm{\mathsfit{A}}})\in\mathbb{R}^{n\times n\times
1}$ such that

${\bm{\mathsfit{L}}}_{zo}(S,{\bm{\mathsfit{A}}})_{i,i,1}=\begin{cases}1&\text{if
}i\in S\\\ 0&\text{otherwise}\end{cases}.$ (4)

In other words, the zero-one labeling trick assigns $1$ to nodes in $S$ and
labels $0$ to all other nodes in the graph. It is a valid labeling trick
because nodes in $S$ get distinct labels from others, and the labeling
function is permutation equivariant by always giving nodes in the target node
set label $1$. These node labels serve as additional node features fed to a
GNN together with the original node features.

Let’s return to the example in Figure 1(a) to see how the zero-one labeling
trick helps GNNs learn better multi-node representations. This time, when we
want to predict link $(v_{1},v_{2})$, we will label $v_{1},v_{2}$ differently
from the rest nodes, as shown by the distinct colors in Figure 2 left. When
computing $v_{2}$’s representation, GNN is also “aware” of the source node
$v_{1}$ with nodes $v_{1}$ and $v_{2}$ labeled, rather than treating $v_{1}$
the same as other nodes. Similarly, when predicting link $(v_{1},v_{3})$, the
model will again label $v_{1},v_{3}$ differently from other nodes as shown in
Figure 2 right. This way, $v_{2}$ and $v_{3}$’s node representations are no
longer the same in the two differently labeled graphs (due to the presence of
the labeled $v_{1}$), and the model can predict $(v_{1},v_{2})$ and
$(v_{1},v_{3})$ differently. The key difference of model with labeling trick
from GAE is that the node representations are no longer computed
independently, but are conditioned on each other in order to capture the
dependence between nodes.

Figure 2: When predicting $(v_{1},v_{2})$, we will label these two nodes
differently from the rest so that a GNN is aware of the target link when
learning $v_{1}$ and $v_{2}$’s representations. Similarly, when predicting
$(v_{1},v_{3})$, nodes $v_{1}$ and $v_{3}$ will be labeled differently. This
way, the representation of $v_{2}$ in the left graph will be different from
that of $v_{3}$ in the right graph, enabling GNNs to distinguish the non-
isomorphic links $(v_{1},v_{2})$ and $(v_{1},v_{3})$.

###  4.3 Expressivity of GNN with labeling trick

We include all proofs in the appendix.

Labeling trick first bridges the gap between whole-graph representation (the
focus of graph level GNNs) and node set representations.

###### Theorem 11

For any node set $S$ in graph ${\bm{\mathsfit{A}}}$ and $S^{\prime}$ in graph
${\bm{\mathsfit{A}}}^{\prime}$, given a set labeling trick,
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})\Leftrightarrow{\bm{\mathsfit{A}}}^{(S)}\simeq{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime})}$.

Therefore, the problem of graph-level tasks on a labeled graph is equivalent
to that of multi-node tasks. However, the complexity of these graph-level GNNs
prevent their application. We further want to connect node set representations
with node representations. Now we introduce our main theorem showing that with
a valid labeling trick, an NME GNN can learn structural representations of
node sets.

###### Theorem 12

Given an NME GNN and an injective set aggregation function AGG, for any
$S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime}$,
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})\Leftrightarrow(S,{\bm{\mathsfit{A}}})\\!\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
where $\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)}):=\text{
AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{(S)})|i\in S\\})$.

Remember that directly aggregating the structural node representations learned
from the original graph ${\bm{\mathsfit{A}}}$ does not lead to structural
representations of node sets (Section 3.3). In contrast, Theorem 12 shows that
aggregating the structural node representations learned from the labeled graph
${\bm{\mathsfit{A}}}^{(S)}$, somewhat surprisingly, results in a structural
representation for $(S,{\bm{\mathsfit{A}}})$.

The significance of Theorem 12 is that it closes the gap between the nature of
GNNs for single-node representations and the requirement of multi-node
representations for node set prediction problems. Although GNNs alone have
severe limitations for multi-node representations, GNNs + labeling trick can
learn structural representations of node sets by aggregating structural node
representations obtained in the labeled graph.

Theorem 12 assumes an NME GNN. To augment Theorem 12, we give the following
theorems, which demonstrate the power of labeling trick for 1-WL-GNNs on link
prediction.

###### Theorem 13

Given an $h$-layer 1-WL-GNN, in any non-attributed graph with $n$ nodes, if
the degree of each node in the graph is between $1$ and
$\big{(}(1-\epsilon)\log n\big{)}^{1/(2h+2)}$ for any constant $\epsilon>0$,
there exists $\omega(n^{2\epsilon})$ pairs of non-isomorphic links
$(u,w),(v,w)$ such that 1-WL-GNN gives $u,v$ the same representation, while
with 1-WL-GNN + zero-one labeling trick gives $u,v$ different representations.

Theorem 13 shows that in any non-attributed graph there exists a large number
($\omega(n^{2\epsilon})$) of link pairs (like the examples $(v_{1},v_{2})$ and
$(v_{1},v_{3})$ in Figure 1(a)) which are not distinguishable by 1-WL-GNNs
alone but distinguishable by 1-WL-GNNs + labeling trick. This means, labeling
trick can boost the expressive power of 1-WL-GNNs on link prediction tasks.

How labeling trick boosts link prediction can also be shown from another
perspective: 1-WL-GNN + zero-one labeling trick can learn various link
prediction heuristics while vanilla 1-WL-GNN cannot.

###### Proposition 14

Given a link prediction heuristic of the following form,

$\displaystyle h(\\{i,j\\},{\bm{\mathsfit{A}}})=f\big{(}\big{\\{}\sum_{v\in
N(i)}g_{2}(\text{deg}(v,{\bm{\mathsfit{A}}})),\sum_{v\in
N(j)}g_{2}(\text{deg}(v,{\bm{\mathsfit{A}}}))\big{\\}},\\!\\!\sum_{v\in
N(i)\bigcap N(j)}\\!\\!g_{1}(\text{deg}(v,{\bm{\mathsfit{A}}}))\big{)},$ (5)

where $deg(v,{\bm{\mathsfit{A}}})$ is the degree of node $v$ in graph
${\bm{\mathsfit{A}}}$, $g_{1},g_{2}$ are positive functions, and $f$ is
injective w.r.t. the second input with the first input fixed. There exists a
1-WL-GNN + zero-one labeling trick implementing $h$. In contrast, 1-WL-GNN
cannot implement $h$.

The $h$ function defined in the above proposition covers many widely-used and
time-tested link prediction heuristics, such as common neighbors (CN)
(Barabási and Albert, 1999), resource allocation(RA) (Zhou et al., 2009), and
Adamic-Adar(AA) (Adamic and Adar, 2003). These important structural features
for link prediction are not learnable by vanilla GNNs but can be learned if we
augment 1-WL-GNNs with a simple zero-one labeling trick.

Labeling trick can also boost graph neural networks in subgraph tasks with
more than two nodes. The following theorem from Wang and Zhang (2022)
illustates it.

###### Theorem 15

Given an $h$-layer 1-WL-GNN, in any non-attributed graph with $n$ nodes, if
the degree of each node in the graph is between $1$ and
$\big{(}(1-\epsilon)\log n\big{)}^{1/(2h+2)}$ for any constant $\epsilon>0$,
there exists $w(2^{n}n^{2\epsilon-1})$ pairs of non-isomorphic subgraphs such
that that 1-WL-GNN produces the same representation, while 1-WL-GNN + labeling
trick can distinguish them.

Theorem 15 extends Theorem 13 to more than 2 nodes. It shows that an even
larger number of node set pairs need labeling tricks to help 1-WL-GNNs
differentiate them.

###  4.4 Complexity

Despite the expressive power, labeling trick may introduce extra computational
complexity. The reason is that for every node set $S$ to predict, we need to
relabel the graph ${\bm{\mathsfit{A}}}$ according to $S$ and compute a new set
of node representations within the labeled graph. In contrast, GAE-type
methods compute node representations only in the original graph.

Let $m$ denote the number of edges, $n$ denote the number of nodes, and $q$
denote the number of target node sets to predict. As node labels are usually
produced by some fast non-parametric method, we neglect the overhead for
computing node labels. Then we compare the inference complexity of GAE and GNN
with labeling trick. For small graphs, GAE-type methods can compute all node
representations first and then predict multiple node sets at the same time,
which saves a significant amount of time. In this case, GAE’s time complexity
is $O(m+n+q)$, while GNN with labeling trick takes up to $O(q(m+n))$ time.
However, for large graphs that cannot fit into the GPU memory, extracting a
neighborhood subgraph for each node set to predict has to be used for both
GAE-type methods and labeling trick, resulting in similar computation cost
$O(q(n_{s}+m_{s}))$, where $n_{s},m_{s}$ are the average number of nodes and
edges in the segregated subgraphs.

Figure 3: Set labeling trick cannot differentiate directed links between the
same nodes.

##  5 Labeling trick for poset

The previous section describes multi-node substructures
$(S,{\bm{\mathsfit{A}}})$ defined by node set $S$, which assumes that nodes in
$S$ have no order relation. However, the assumption may lose some critical
information in real-world tasks. For example, the citing and cited articles
should be differentiated in citation graphs. As shown in Figure 3, using set
labeling trick cannot discriminate the link direction by giving the two
directed links the same representation, yet the two directed links are
obviously non-isomorphic. Therefore, introducing order relation into node set
is necessary for substructures with internal relation. In this section, we use
poset to define multi-node substructures and extend set labeling trick to
poset labeling trick. Note that node order is only additionally introduced for
$S$ because the graph ${\bm{\mathsfit{A}}}$ already allows directed edges in
our definition.

###### Definition 16

(Poset labeling trick) Given a graph ${\bm{\mathsfit{A}}}$ and a poset $S$ of
nodes in it, we stack a labeling tensor
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})\in\mathbb{R}^{n\times n\times d}$
in the third dimension of ${\bm{\mathsfit{A}}}$ to get a new
${\bm{\mathsfit{A}}}^{(S)}\in\mathbb{R}^{n\times n\times(k+d)}$, where
${\bm{\mathsfit{L}}}$ satisfies: for all poset $S$ of nodes in graph
${\bm{\mathsfit{A}}}$, poset $S^{\prime}$ of nodes in graph
${\bm{\mathsfit{A}}}^{\prime}$, and $\pi\in\Pi_{n}$,

  1. 1.

(target-nodes-and-order-distinguishing)
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}))\Rightarrow
S=\pi(S^{\prime})$.

  2. 2.

(permutation equivariance)
$S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})\Rightarrow{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$.

The definition of poset labeling trick is nearly the same as that of set
labeling trick, except that we require permutation of poset and poset
isomorphism (Definition 3 and 4). Poset labeling trick still assigns a label
vector to each node/edge in graph ${\bm{\mathsfit{A}}}$. The labels
distinguish the substructure from other parts of the graph and keep
permutation equivariance. As we will show, poset labeling trick enables
maximum expressivity for poset learning. Below we first discuss how to design
poset labeling tricks that satisfy the two above properties.

###  5.1 Poset labeling trick design

To describe general partial order relations between nodes in a poset, we
introduce Hasse diagram, a graph that uniquely determines the partial order
relation.

###### Definition 17

The Hasse diagram of a poset $S=(U,\leq_{S})$, denoted as ${\mathcal{H}}_{S}$,
is a directed graph $(V_{H},E_{H})$, $V_{H}=U$, $E_{H}=\\{(u,v)~{}|~{}v\neq
u\text{ and }v\text{ covers }u\\}$, where $v$ covers $u$ means that
$u\leq_{S}v$ and there exists no $w\in U,w\notin\\{u,v\\}$, $u\leq_{S}w$ and
$w\leq_{S}v$.

Figure 4: Different Hasse diagrams

Figure 4 shows some examples of Hasse diagram. The reason we use Hasse diagram
to encode partial order relation is that we prove any poset labeling trick
satisfying Definition 16 must give non-isomorphic nodes in a Hasse diagram
different labels.

###### Proposition 18

Let ${\bm{\mathsfit{L}}}$ be the labeling function of a poset labeling trick.
If
$\exists\pi\in\Pi_{n},{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$,
then for all $v^{\prime}\in S^{\prime}$, $\pi(v^{\prime})$ is in $S$, and
$(\\{v^{\prime}\\},{\mathcal{H}}_{S^{\prime}})\simeq(\\{\pi(v^{\prime})\\},{\mathcal{H}}_{S})$.
Furthermore, in the same ${\mathcal{H}}_{S}$, non-isomorphic nodes must have
different labels.

Proposition 18 shows that a valid poset labeling trick should differentiate
non-isomorphic nodes in a Hasse diagram. Theoretically, we can run an NME GNN
on the Hasse diagram so that the node embeddings can serve the purpose. Such a
poset labeling trick is defined as follows.

###### Definition 19

Given an NME GNN, Hasse embedding labeling trick is

${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})_{u,u,:}=\begin{cases}\text{sigmoid}(\text{GNN}(u,{\mathcal{H}}_{S}))&\text{if
}u\in S\\\ 0&\text{otherwise}\end{cases}$ (6)

This labeling trick fulfills the two requirements in Definition 16. Note that
sigmoid prevents GNN from producing zero embeddings thus losing the
distinguishing power from non-target nodes. Hasse embedding labeling trick is
similar to the zero-one labeling trick for set in Definition 10. It assigns
nodes outside the target poset the same label and distinguishes nodes inside
based on their isomorphism class in the Hasse diagram, while the zero-one
labeling trick does not differentiate nodes inside the poset.

The above poset labeling trick can work on posets with arbitrary complex
partial orders, at the cost of first running an NME GNN on the Hasse diagram.
However, in most real-world tasks, differentiating non-isomorphic nodes in
Hasse diagrams is usually quite easy. For example, in the directed link
prediction task, the target posets all have same simple Hasse diagram: only
two roles exist in the poset—source node and target node of the link, which is
shown in Figure 4(a). Then we can assign a unique color to each equivalent
class of isomorphic nodes in the Hasse diagram as the node labels, e.g.,
giving 1 to the source node, 2 to the target node, and 0 to all other nodes in
directed link prediction.

However, in some cases, we need to learn representations for posets with
different Hasse diagrams. The Hasse embedding labeling trick still works for
these cases yet is difficult to implement. Can we design some simpler labeling
tricks for some special cases of poset representation learning problems where
the posets are not restricted to have the same Hasse diagram? Two cases are
discussed in the following.

Linear Order Set. Linear order set means a poset whose each pair of nodes are
comparable, so that the Hasse diagram is a chain as shown in Figure 4(b).
Therefore, $S$ can be sorted in
$u_{1}\leq_{S}u_{2}\leq_{S}u_{3}\leq_{S}...\leq_{S}u_{k}$, where
$S=(U,\leq_{S}),U=\\{u_{1},u_{2},...,u_{k}\\}$. Then we can assign $u_{i}$
label $i$ and give nodes outside $S$ $0$ label. Such a labeling trick is a
valid poset labeling trick and can be used to learn paths with different
lengths.

Nearly Linear Order Set. Nearly linear order set means there exists a
partition of $S$, $\\{S_{1},S_{2},...,S_{l}\\}$,
$\leq_{S}=\bigcup_{i=1}^{l-1}S_{i}\times S_{i+1}$. As shown in Figure 4(c),
the Hasse diagram is nearly a chain whose nodes are replaced with a set of
nodes with no relations. We can assign nodes in $S_{i}$ label $i$ and give
nodes outside $S$ $0$ label. It is still a valid poset labeling trick. Nearly
linear order set can describe a group in an institute, where the top is the
leader.

###  5.2 Poset labeling trick expressivity

We first show that poset labeling trick enables maximum expressivity for poset
learning.

###### Theorem 20

For any node poset $S$ in graph ${\bm{\mathsfit{A}}}$ and $S^{\prime}$ in
graph ${\bm{\mathsfit{A}}}^{\prime}$, given a set labeling trick,
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})\Leftrightarrow{\bm{\mathsfit{A}}}^{(S)}\simeq{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime})}$.

Theorem 20 shows that structural poset representation is equivalent to the
structural whole graph representation of labeled graph. Poset labeling trick
can also bridge the gap between node representations and poset
representations.

###### Theorem 21

Given an NME GNN and an injective aggregation function AGG, for any node
posets $S,S^{\prime}$ in graphs
${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}$,
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})\Leftrightarrow(S,{\bm{\mathsfit{A}}})\\!\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
where
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})=\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{(S)}|u\in
S\\}))$.

Theorem 21 shows that with an NME GNN, poset labeling trick will produce
structural representations of posets. To augment this theorem, we also discuss
1-WL-GNNs with poset labeling trick. 1-WL-GNNs cannot capture any partial
order information and cannot differentiate arbitrary different posets with the
same set of nodes. Differentiating different posets with different sets is
also hard for 1-WL-GNNs as they fail to capture relations between nodes. Poset
labeling trick can help in both cases.

###### Theorem 22

In any non-attributed graph with $n$ nodes, if the degree of each node in the
graph is between $1$ and $\big{(}(1-\epsilon)\log n\big{)}^{1/(2h+2)}$ for any
constant $\epsilon>0$, there exist $w(n^{2\epsilon})$ pairs of links and
$w((n!)^{2})$ pairs of non-isomorphic node posets such that any $h$-layer
1-WL-GNN produces the same representation, while with Hasse embedding labeling
trick 1-WL-GNN can distinguish them.

Theorem 22 illustrates that poset labeling trick can help 1-WL-GNNs
distinguish significantly more pairs of node posets.

##  6 Subset labeling trick for multi-node representation learning

Besides set labeling trick, there exist other methods that append extra
features to the adjacency to boost GNNs. Among them, ID-GNN (You et al., 2021)
and NBFNet (Zhu et al., 2021) assign special features to only one node in the
target node set and also achieve outstanding performance. In this section, we
propose subset labeling trick. As its name implies, subset labeling trick
assigns labels only to a subset of nodes in the target node set. We compare
set labeling trick with subset labeling trick in different problem settings.
In some cases, subset labeling trick is even more expressive than set labeling
trick.

###  6.1 Subset labeling trick

###### Definition 23

(subset labeling trick) Given set $S$ in graph ${\bm{\mathsfit{A}}}$ and its
subset $P\subseteq S$, we stack a labeling tensor
${\bm{\mathsfit{L}}}(P,{\bm{\mathsfit{A}}})\in\mathbb{R}^{n\times n\times d}$
in the third dimension of ${\bm{\mathsfit{A}}}$ to get a new
${\bm{\mathsfit{A}}}^{(P)}\in\mathbb{R}^{n\times n\times(k+d)}$, where
${\bm{\mathsfit{L}}}$ satisfies: $\forall
S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime},P\subseteq
S,P^{\prime}\subseteq S^{\prime},\pi\in\Pi_{n}$,

  1. 1.

(target-subset-distinguishing)
${\bm{\mathsfit{L}}}{(P,{\bm{\mathsfit{A}}})}=\pi({\bm{\mathsfit{L}}}{(P^{\prime},{\bm{\mathsfit{A}}}^{\prime})})\Rightarrow
P=\pi(P^{\prime})$.

  2. 2.

(permutation equivariance)
$P=\pi(P^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})\Rightarrow{\bm{\mathsfit{L}}}{(P,{\bm{\mathsfit{A}}})}=\pi({\bm{\mathsfit{L}}}{(P^{\prime},{\bm{\mathsfit{A}}}^{\prime})})$.

Like set labeling trick, subset labeling trick distinguishes the selected
subset in the target set and keeps permutation equivariance. However, it does
not need to distinguish all target nodes. Subset($k$) labeling trick means the
subset size is $k$.

Subset zero-one labeling trick is a simplest subset labeling trick fulfilling
the requirements in Definition 23.

###### Definition 24

(Subset zero-one labeling trick) Given a graph ${\bm{\mathsfit{A}}}$, a set of
nodes $S$ to predict, and a subset $P\subseteq S$, we give it a diagonal
labeling matrix
${\bm{\mathsfit{L}}}(P,{\bm{\mathsfit{A}}})\in\mathbb{R}^{n\times n\times 1}$
such that ${\bm{\mathsfit{L}}}(P,{\bm{\mathsfit{A}}})_{i,i,1}=1$ if $i\in P$
and ${\bm{\mathsfit{L}}}(P,{\bm{\mathsfit{A}}})_{i,i,1}=0$ otherwise.

To explain a bit, the subset zero-one labeling trick assigns label $1$ to
nodes in the selected subset $P$, and label $0$ to all nodes not in $P$. It
only contains the subset identity information.

Then a natural problem arises: how to select subset $P$ from the target node
set $S$? Motivated by previous methods, we propose two different routines:
subset-pooling and one-head.

###  6.2 How to select subset

##### Subset pooling

ID-GNN (You et al., 2021) proposes an a GNN for node set learning. For each
node in the target node set, it labels the node one and all other nodes zero.
Then, it uses a 1-WL-GNN to produce the representations of the node. By
pooling all node representations, ID-GNN produces the node set representation.
As isomorphic node sets can have different embeddings due to different subset
selections, choosing only one node randomly can break permutation
equivariance. But pooling the representation of all subset selection
eliminates the non-determinism caused by selection and solves this problem.
Generalizing this method, we propose the subset pooling routine. Subset($k$)
pooling enumerates all size-$k$ subsets and then pools the embeddings of them.

$\text{AGG}(\\{\text{GNN}(S,{\bm{\mathsfit{A}}}^{(P)})|P\subseteq
S,|P|=k\\}),$ (7)

where AGG is an injective set aggregation function.

As for all $\pi\in\Pi_{n}$ and target node set $S$ in graph
${\bm{\mathsfit{A}}}$,

$\text{AGG}(\\!\\{\text{GNN}(S,{\bm{\mathsfit{A}}}^{\\!(P)\\!})|P\\!\subseteq\\!S,|P|\\!=\\!k\\}\\!)=\text{AGG}(\\!\\{\text{GNN}(\pi(S),\pi({\bm{\mathsfit{A}}})^{\\!(P)\\!})|P\\!\subseteq\\!\pi(S),|P|\\!=\\!k\\}\\!),$
(8)

the subset pooling routine keeps permutation equivariance.

##### One head routine

Contrary to the subset pooling routine, link prediction model NBFNet (Zhu et
al., 2021) labels only one head of the link. This design breaks permutation
equivariance but improves the scalability. We propose the one head routine to
generalize this method to general node set tasks. It selects only one subset
to label. Some policies are shown in the following.

Selection Policies

Random Selection. For a target set, we can select a subset in it randomly. For
example, we can randomly choose one head of each target edge in link
prediction task.

Graph Structural Selection. We can select a node with maximum degree in the
target node set. Note that it cannot keep permutation equivariance either.

Partial Order Relation Selection. If the least element exists in a poset, we
can choose it as the subset. For example, in directed link prediction task,
the source node of each link can be the subset. This method can keep
permutation equivariance.

Complexity

The efficiency gain of subset labeling trick compared with set labeling trick
comes from sharing results across target node sets. GNN with set labeling
trick has to compute the representations of each target node set separately.
With the target node distinguishing property, no labeling trick can remain
unchanged across different target nodes sets. Therefore, the input adjacency
will change and node representations have to be reproduced by the GNN.

In contrast, GNN with subset labeling trick can compute the representations of
multiple node sets with the same selected subset simultaneously. The subset
label is only a function of the selected subset and the graph, so we can
maintain the subset label for different target node sets by choosing the same
subset. For example, in link prediction task, all links originating from a
node share this same source node. By choosing the source node as the subset,
these links have the same label and input adjacency to GNN, so the node
representations produced by the GNN can be reused. This routine is especially
efficient in the knowledge graph completion setting, where a query involves
predicting all possible tail entities connected from a head entity with a
certain relation.

###  6.3 Expressivity

When the subset size $k$ equals the target node set size $|S|$, subset
labeling trick is equivalent to set labeling trick. What is more interesting
is, when $k=|S|-1$, subset labeling trick with the subset pooling routine can
achieve the same power as set labeling trick.

###### Theorem 25

Given an NME GNN, for any graph
${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}$, and node sets
$S,S^{\prime}$ in ${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}$
respectively, we have

$\text{AGG}(\\!\\{\\!\text{GNN}(S,{\bm{\mathsfit{A}}}^{(\\!P\\!)})|P\\!\subseteq\\!S,|P|\\!=\\!|S|-1\\!\\}\\!)\\!=\\!\text{AGG}(\\!\\{\\!\text{GNN}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime(\\!P^{\prime}\\!)})|P^{\prime}\\!\subseteq\\!S^{\prime},|P^{\prime}|\\!=\\!|S^{\prime}|-1\\!\\}\\!)\\\
\Leftrightarrow(S,{\bm{\mathsfit{A}}})\\!\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}).$
(9)

Theorem 25 illustrates that when the selected subset is of $|S|-1$ size, GNNs
can produce structural representation with the subset-pooling routine. This
theorem is especially useful when $|S|=2$, in other words, link prediction
task. Labeling only one node each time and pooling the two results can achieve
the same high expressivity.

Under the one head routine, we have the following theorem.

###### Theorem 26

Given an NME GNN, for any graph
${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}$, and node sets
$S,S^{\prime}$ in ${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}$
respectively, we have

$(S,{\bm{\mathsfit{A}}})\\!\not\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})\Rightarrow\forall
P\subseteq S,P^{\prime}\subseteq
S^{\prime},|P|=|S|-1,|P^{\prime}|=|S^{\prime}|-1,\\\
\text{GNN}(S,{\bm{\mathsfit{A}}}^{(P)})\neq\text{GNN}(S,{\bm{\mathsfit{A}}}^{\prime(P^{\prime})}).$
(10)

Though one-head routine may produce different representations for isomorphic
sets, the above theorem shows that it maintains the capacity to differentiate
non-isomorphic sets.

For larger target node set, subset($|S|-1$) labeling trick is of little use,
as the $|S|-1$ labeling can hardly be reused by other target sets. In
contrast, we focus on the expressivity of subset($1$) labeling trick, since it
is much more common for target node sets to share node rather than sharing
another $(|S|-1)$ node set.

When using NME GNN, according to Theorem 12, set labeling trick leads to the
highest expressivity. The problem left is whether subset($1$) labeling trick
can help NME GNN produce structural representations.

###### Proposition 27

Given an NME GNN, there exists pairs of set $S$ in graph ${\bm{\mathsfit{A}}}$
and set $S^{\prime}$ in graph ${\bm{\mathsfit{A}}}^{\prime}$ such that
$\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{(u)})|u\in
S\\})=\text{AGG}(\\{\text{GNN}(u^{\prime},{\bm{\mathsfit{A}}}^{\prime(u^{\prime})})|u^{\prime}\in
S^{\prime}\\})$ while
$(S,{\bm{\mathsfit{A}}})\\!\not\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$.

Proposition 27 shows that with NME GNN, subset($1$) labeling trick cannot
learn structural representation and is less expressive than set labeling
trick. However, using 1-WL-GNNs, the expressivity of subset($1$) labeling
trick is incomparable to that of set labeling trick. In other words, there
exists non-isomorphic node sets which are distinguishable by subset($1$)
labeling trick and indistinguishable by set labeling trick, and vice versa.

###### Proposition 28

Given a 1-WL-GNN, there exists
$S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime}$ such that
$(S,{\bm{\mathsfit{A}}})\\!\not\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
$\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{(u)})|u\in
S\\})\neq\text{AGG}(\\{\text{GNN}(u^{\prime},{\bm{\mathsfit{A}}}^{\prime(u^{\prime})})|u^{\prime}\in
S^{\prime}\\})$ while
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{S})=\text{GNN}(S^{\prime},{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime})})$.
There also exists
$S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime}$ such that
$(S,{\bm{\mathsfit{A}}})\\!\not\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
$\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{(u)})|u\in
S\\})=\text{AGG}(\\{\text{GNN}(u^{\prime},{\bm{\mathsfit{A}}}^{\prime(u^{\prime})})|u^{\prime}\in
S^{\prime}\\})$ while
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})\neq\text{GNN}(S^{\prime},{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime})})$.

And 1-WL-GNN with subset($1$) labeling trick can also differentiate many pairs
of node sets that 1-WL-GNN cannot differentiate, as shown in the following
theorem.

###### Theorem 29

In any non-attributed graph with $n$ nodes, if the degree of each node in the
graph is between $1$ and $\big{(}(1-\epsilon)\log n\big{)}^{1/(2h+2)}$ for any
constant $\epsilon>0$, there exist $n^{2\epsilon}$ pairs of links and
$w(2^{n}n^{3\epsilon-1})$ pairs of non-isomorphic node sets such that any
$h$-layer 1-WL-GNN produces the same representation, while with subset(1)
labeling trick 1-WL-GNN can distinguish them.

####  6.3.1 Why subset labeling trick outperforms labeling trick in some
cases?

In this section, we take a closer look at some special cases and then give
some intuitions on subset labeling trick and set labeling trick. NME GNN is
too expressive to show some weakness of set labeling trick, so we focus on
1-WL-GNN.

Subset labeling trick helps differentiate nodes with the same label. Taking
the two graphs in Figure 5 as an example, the target set is the whole graph.
With zero-one labeling trick, 1-WL-GNN cannot differentiate them as all nodes
in the two graphs have the same rooted subtree (see Figure 5a). However,
subset zero-one labeling trick can solve this problem. The rooted subtree in
the first graph always contains a nodes with label $1$, whereas in the second
graph, the rooted subtree may sometimes contain no labeled nodes, leading to
different 1-WL-GNN embeddings.

Figure 5: An example of when subset labeling trick differentiates two node
sets, while set labeling trick does not. First row: labeled graphs. Second
row: rooted subtrees of $v$. Figure 6: An example of when subset labeling
trick fails to differentiate two node sets while set labeling trick does.
First row: labeled graphs. Second row: rooted subtrees of $v$.

The drawback of subset labeling trick is that it captures pair-wise relation
only and loses high-order relations. As shown in Figure 6, the two target node
sets (each containing three nodes) are non-isomorphic, but every node pair
from the first set is isomorphic to a node pair from the second set. This
difference is also reflected in the rooted subtree of target nodes (see the
bottom of Figure 6), where set labeling trick (Figure 6a) can differentiate
$v$ while subset($1$) labeling trick (Figure 6b) cannot.

##  7 Labeling trick for hypergraph

Graph is appropriate to describe bilateral relations between entities.
However, high-order relations among several entities are also worth studying
(Agarwal et al., 2006). Hypergraph, composed of nodes and hyperedges, can
model such high-order relations naturally. In this section, we study multi-
node representation learning in hypergraphs.

We consider a hypergraph
$H:=(V,E,{\bm{H}},{\bm{\mathsfit{X}}}^{V},{\bm{\mathsfit{X}}}^{E})$, where $V$
is the node set $\\{1,2,...,n\\}$, $E$ is the hyperedge set $\\{1,2,...,m\\}$,
and ${\bm{H}}\in\\{0,1\\}^{n\times m}$ is the incidence matrix with
${\bm{H}}_{i,j}=1$ if node $i$ is in hyperedge $j$ and $0$ otherwise. Each
hyperedge contains at least one node.
${\bm{\mathsfit{X}}}^{V}\in{\mathbb{R}}^{n\times d}$ and
${\bm{\mathsfit{X}}}^{E}\in{\mathbb{R}}^{m\times d}$ are node and hyperedge
features respectively, where ${\bm{\mathsfit{X}}}^{V}_{i,:}$ is of node $i$,
and ${\bm{\mathsfit{X}}}^{E}_{j,:}$ is of hyperedge $j$.

We define a hypergraph permutation
$\pi=(\pi_{1},\pi_{2})\in\Pi_{n}\times\Pi_{m}$. Its action on a hypergraph
$H=(V,E,{\bm{H}},{\bm{\mathsfit{X}}}^{V},{\bm{\mathsfit{X}}}^{E})$ is
$\pi(H)=(\pi_{1}(V),\pi_{2}(E),\pi({\bm{H}}),\pi_{1}({\bm{\mathsfit{X}}}^{V}),\pi_{2}({\bm{\mathsfit{X}}}^{E}))$,
where incidence matrix permutation is
$\pi({\bm{H}})_{\pi_{1}(i),\pi_{2}(j)}={\bm{H}}_{i,j}$.

The isomorphism and poset isomorphism of hypergraph are defined as follows.

###### Definition 30

Hypergraphs $H,H^{\prime}$ are isomorphic iff there exists
$\pi\in\Pi_{n}\times\Pi_{m}$, $\pi(H)=H^{\prime}$. Given node posets $S$ in
$H$ and $S^{\prime}$ in $H^{\prime}$, $(S,H),(S^{\prime},H^{\prime})$ are
isomorphic iff there exists $\pi=(\pi_{1},\pi_{2})\in\Pi_{n}\times\Pi_{m}$,
$(\pi_{1}(S),\pi(H))=(S^{\prime},H^{\prime})$.

We can define labeling trick for hypergraph similar to that of graph from
scratch. However, converting the hypergraph problem to a graph problem is more
convenient. We formalize the known convertion (Bretto, 2013) as follows.

###### Definition 31

(Incidence graph) Given a hypergraph
$H=(V,E,{\bm{H}},{\bm{\mathsfit{X}}}^{V},{\bm{\mathsfit{X}}}^{E})$,
$V=\\{1,2,...,n\\}$, $E=\\{1,2,...,m\\}$, ${\bm{H}}\in\\{0,1\\}^{n\times m}$,
${\bm{\mathsfit{X}}}^{V}\in{\mathbb{R}}^{n\times
d}$,${\bm{\mathsfit{X}}}^{E}\in{\mathbb{R}}^{m\times d}$, its incidence graph
is $IG_{H}=(V_{H},E_{H},{\bm{\mathsfit{A}}})$, where the node set
$V_{H}=\\{1,2,...,n,n\\!+\\!1,...,n\\!+\\!m\\}$, edge set $E_{H}=\\{(i,j)|i\in
V,j\in E,{\bm{H}}_{i,j}=1\\}$, adjacency tensor
${\bm{\mathsfit{A}}}\in{\mathbb{R}}^{(n+m)\times(n+m)\times(d+1)}$. For all
$i\in V,j\in E$, ${\bm{\mathsfit{A}}}_{i,i,:d}={\bm{\mathsfit{X}}}^{V}_{i,:}$,
${\bm{\mathsfit{A}}}_{i,i,d+1}={\bm{\mathsfit{X}}}^{V}_{i,:}$,
${\bm{\mathsfit{A}}}_{n+j,n+j,:d}={\bm{\mathsfit{X}}}^{E}_{j,:}$,
${\bm{\mathsfit{A}}}_{i,n+j,d+1}={\bm{H}}_{i,j}$. All other elements in
${\bm{\mathsfit{A}}}$ are $0$.

The incidence graph $IG_{H}$ considers $H$’s nodes and hyperedges both as its
nodes. Two nodes in $IG_{H}$ are connected iff one is a node and the other is
a hyperedge containing it in $H$.

The incidence graph contains all information in the hypergraph. Hypergraph’s
isomorphism and poset isomorphism are equivalent to the isomorphism and poset
isomorphism in the corresponding incidence graphs.

###### Theorem 32

Given node posets $S$ in hypergraph $H$, $S^{\prime}$ in hypergraph
$H^{\prime}$, $(S,H)\simeq(S^{\prime},H^{\prime})$ iff
$(S,IG_{H})\simeq(S^{\prime},IG_{H^{\prime}})$.

Therefore, a hypergraph task can be converted to a graph task. Labeling tricks
can be extended to hypergraph by using them on the corresponding incidence
graph.

###### Corollary 33

Given an NME GNN, and an injective aggregation function AGG, for any
$S,H,S^{\prime},H^{\prime}$, let
${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}$ denote the adjacency
tensors of graphs $IG_{H},IG_{H^{\prime}}$ respectively. Then
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})\Leftrightarrow(S,H)\\!\simeq\\!(S^{\prime},H^{\prime})$.

With NME GNN, set labeling trick can still produce structural representations
on hypergraph. This enables us to boost the representation power of hyperedge
prediction tasks.

##  8 Related work

There is emerging interest in recent study of graph neural networks’
expressivity. Xu et al. (2018) and Morris et al. (2019) first show that the
1-WL test bounds the discriminating power of GNNs performing neighbor
aggregation. Many works have since been proposed to increase the power of GNNs
by simulating higher-order WL tests (Morris et al., 2019; Maron et al., 2019a;
Chen et al., 2019; Azizian and Lelarge, 2021), approximating permutation
equivariant functions (Maron et al., 2019b; Geerts, 2020; Maron et al., 2019a;
Puny et al., 2022; Chen et al., 2020), , encoding subgraphs (Frasca et al.,
2022; Zhang and Li, 2021; Feng et al., 2022), utilizing graph spectral
features (Kreuzer et al., 2021; Lim et al., 2022), etc. However, most previous
works focus on improving GNN’s whole-graph representation power. Little work
has been done to analyze GNN’s substructure representation power. Srinivasan
and Ribeiro (2020) first formally studied the difference between structural
representations of nodes and links. Although showing that structural node
representations of GNNs cannot perform link prediction, their way to learn
structural link representations is to give up GNNs and instead use Monte Carlo
samples of node embeddings learned by network embedding methods. In this
paper, we show that GNNs combined with labeling tricks can also learn
structural link representations, which reassures using GNNs for link
prediction.

Many works have implicitly assumed that if a model can learn node
representations well, then combining the pairwise node representations can
also lead to good node set (for example link) representations (Grover and
Leskovec, 2016; Kipf and Welling, 2016b; Hamilton et al., 2017). However, we
argue in this paper that simply aggregating node representations fails to
discriminate a large number of non-isomorphic node sets (links), and with
labeling trick the aggregation of structural node representations leads to
structural representations.

Li et al. (2020) proposed distance encoding (DE), whose implementations based
on $S$-discriminating distances can be shown to be specific labeling tricks.
You et al. (2019) also noticed that structural node representations of GNNs
cannot capture the dependence (in particular distance) between nodes. To learn
position-aware node embeddings, they propose P-GNN, which randomly chooses
some anchor nodes and aggregates messages only from the anchor nodes. In
P-GNN, nodes with similar distances to the anchor nodes, instead of nodes with
similar neighborhoods, have similar embeddings. Thus, P-GNN cannot learn
structural node/link representations. P-GNN also cannot scale to large
datasets.

Finally, although labeling trick is formally defined in our conference paper
(Zhang et al., 2021a), various forms of specific labeling tricks have already
been used in previous works. To our best knowledge, SEAL (Zhang and Chen,
2018b) proposes the first labeling trick, which is designed to improve GNN’s
link prediction power. It is later adopted in inductive knowledge graph
completion (Teru et al., 2020) and matrix completion (Zhang and Chen, 2020),
and is generalized into DE (Li et al., 2020) and GLASS (Wang and Zhang, 2022)
which works for $|S|>2$ cases. Wan et al. (2021) use labeling trick for
hyperedge prediction. Besides these set labeling tricks, some labeling methods
similar to the subset labeling trick also exist in existing works. ID-GNN (You
et al., 2021) and NBFNet (Zhu et al., 2021) both use a mechanism equivalent to
the one head routine of subset labeling trick.

##  9 Experiments

Our experiments include various multi-node representation learning tasks:
undirected link prediction, directed link prediction, hyperlink prediction,
and subgraph prediction. Labeling trick boosts GNNs on all these tasks. All
metrics in this section are the higher the better. Datasets are detailed in
Appendix C.

###  9.1 Undirected link prediction

In this section, we use a two-node task, link prediction, to empirically
validate the effectiveness of set and subset labeling trick.

Following the setting in SEAL (Zhang and Chen, 2018a), we use eight datasets:
USAir, NS, PB, Yeast, C.ele, Power, Router, and E.coli. These datasets are
relatively small. So we additionally use four large datasets in Open Graph
Benchmark (OGB) (Hu et al., 2020): ogbl-ppa, ogbl-collab, ogbl-ddi, ogbl-
citation2. To facilitate the comparison, we use the same metrics, including
auroc, Hits@$K$, and MRR, as in previous works.

We use the following baselines for comparison. We use $4$ non-GNN methods: CN
(Common-Neighbor), AA (Adamic-Adar), MF (matrix factorization) and Node2vec
(Grover and Leskovec, 2016). CN and AA are two simple link prediction
heuristics based on counting common neighbors. MF uses free-parameter node
embeddings trained end-to-end as the node representations. Two set labeling
trick methods are used: ZO and SEAL. ZO uses the zero-one labeling trick, and
SEAL uses the DRNL labeling trick (Zhang and Chen, 2018b). Three subset
labeling trick methods are compared: subset zero-one labeling trick with
subset pooling (SZO), subset distance encoding labeling trick with subset
pooling (SDE), subset zero-one labeling trick with one-head routine (OSZO).

Results and discussion. We present the main results in Table 1. Compared with
all non-GNN methods, vanilla 1-WL-GNN with no labeling trick (NO) gets lower
auroc on almost all datasets. However, with labeling trick or subset labeling
trick, 1-WL-GNN can outperform the baselines on almost all datasets. ZO, SEAL
use set labeling trick and outperform non-GNN methods by $4\%$ and $9\%$
respectively on average. The performance difference between ZO and SEAL
illustrates that labeling trick implementation can still affect the
expressivity of 1-WL-GNN. However, even the simplest labeling trick can still
boost 1-WL-GNNs by $6\%$. Subset($1$) labeling trick SZO and SDE also achieve
$9\%$ and $11\%$ score increase on average. Compared with ZO, though SZO also
uses only the target set identity information, it distinguishes nodes in the
target node set and achieves up to $5\%$ performance increase on average,
which verifies the usefulness of subset labeling trick. Last but not least,
though subset labeling trick with one-head routine (OSZO) loses permutation
invariance compared with subset pooling routine (SZO), it still achieves
outstanding performance and even outperforms SZO on 4/8 datasets.

Table 1: Results on undirected link prediction task: auroc (%) $\pm$ standard deviation. | USAir | NS | PB | Yeast | Cele | Power | Router | Ecoli
---|---|---|---|---|---|---|---|---
CN | $93.80_{\pm 1.22}$ | $94.42_{\pm 0.95}$ | $92.04_{\pm 0.35}$ | $89.37_{\pm 0.61}$ | $85.13_{\pm 1.61}$ | $58.80_{\pm 0.88}$ | $56.43_{\pm 0.52}$ | $93.71_{\pm 0.39}$
AA | $95.06_{\pm 1.03}$ | $94.45_{\pm 0.93}$ | $92.36_{\pm 0.34}$ | $89.43_{\pm 0.62}$ | $\underline{86.95_{\pm 1.40}}$ | $58.79_{\pm 0.88}$ | $56.43_{\pm 0.51}$ | $95.36_{\pm 0.34}$
NV | $91.44_{\pm 1.78}$ | $91.52_{\pm 1.28}$ | $85.79_{\pm 0.78}$ | $93.67_{\pm 0.46}$ | $84.11_{\pm 1.27}$ | $76.22_{\pm 0.92}$ | $65.46_{\pm 0.86}$ | $90.82_{\pm 1.49}$
MF | $94.08_{\pm 0.80}$ | $74.55_{\pm 4.34}$ | $94.30_{\pm 0.53}$ | $90.28_{\pm 0.69}$ | $85.90_{\pm 1.74}$ | $50.63_{\pm 1.10}$ | $78.03_{\pm 1.63}$ | $93.76_{\pm 0.56}$
NO | $89.04_{\pm 2.14}$ | $74.10_{\pm 2.62}$ | $90.87_{\pm 0.56}$ | $83.04_{\pm 0.93}$ | $73.25_{\pm 1.67}$ | $65.89_{\pm 1.65}$ | $92.47_{\pm 0.76}$ | $93.27_{\pm 0.49}$
ZO | $94.08_{\pm 1.43}$ | $95.60_{\pm 0.93}$ | $91.82_{\pm 1.26}$ | $94.69_{\pm 0.45}$ | $74.94_{\pm 2.01}$ | $73.85_{\pm 1.37}$ | $93.21_{\pm 0.66}$ | $92.09_{\pm 0.67}$
SEAL | $\mathbf{97.09_{\pm 0.70}}$ | $97.71_{\pm 0.93}$ | $\mathbf{95.01_{\pm 0.34}}$ | $97.20_{\pm 0.64}$ | $86.54_{\pm 2.04}$ | $84.18_{\pm 1.82}$ | $\underline{95.68_{\pm 1.22}}$ | $97.22_{\pm 0.28}$
SZO | $\underline{96.15_{\pm 1.06}}$ | $\underline{98.10_{\pm 0.67}}$ | $94.15_{\pm 0.50}$ | $97.41_{\pm 0.37}$ | $86.31_{\pm 1.80}$ | $78.31_{\pm 0.91}$ | $94.52_{\pm 0.72}$ | $\underline{97.48_{\pm 0.23}}$
SDE | $94.97_{\pm 0.61}$ | $\mathbf{99.29_{\pm 0.14}}$ | $\underline{94.44_{\pm 0.52}}$ | $\mathbf{98.17_{\pm 0.41}}$ | $85.95_{\pm 0.36}$ | $\mathbf{94.16_{\pm 0.14}}$ | $\mathbf{99.33_{\pm 0.09}}$ | $\mathbf{98.91_{\pm 0.08}}$
OSZO | $94.62_{\pm 0.63}$ | $97.42_{\pm 0.49}$ | $94.36_{\pm 0.26}$ | $\underline{97.46_{\pm 0.06}}$ | $\mathbf{88.04_{\pm 0.52}}$ | $\underline{84.95_{\pm 0.30}}$ | $93.77_{\pm 0.20}$ | $95.53_{\pm 0.62}$

We also conduct experiments on some larger datasets as shown in Table 2. GNN
augmented by labeling tricks achieves the best performance on all datasets.

Table 2: Results on undirected link prediction task. Dataset | collab | ddi | citation2 | ppa
---|---|---|---|---
metrics | Hits@50 | Hits@20 | MRR | Hits@100
SZO | $\underline{54.69_{\pm 0.51}}$ | $29.27_{\pm 0.53}$ | $82.45_{\pm 0.62}$ | $36.04_{\pm 4.50}$
ZO | $53.29_{\pm 0.23}$ | $23.90_{\pm 0.75}$ | $78.50_{\pm 1.08}$ | $37.75_{\pm 3.42}$
SEAL | $\mathbf{54.71_{\pm 0.49}}$ | $30.56_{\pm 3.86}$ | $\mathbf{87.67_{\pm 0.32}}$ | $\mathbf{48.80_{\pm 3.16}}$
NO | $44.75_{\pm 1.07}$ | $\underline{37.07_{\pm 5.07}}$ | $\underline{84.74_{\pm 0.21}}$ | $18.67_{\pm 1.32}$
OSZO | $49.17_{\pm 3.29}$ | $\mathbf{41.24_{\pm 1.49}}$ | $82.85_{\pm 0.43}$ | $\underline{43.27_{\pm 1.19}}$

###  9.2 Directed link prediction tasks

To illustrate the necessity of introducing partial order to labeling trick, we
compare set labeling trick and poset labeling trick on the directed link
prediction task. Following previous work (He et al., 2022), we use six
directed graph datasets, namely Cornell, Texas, Wisconsin, CoraML, Citeseer,
and Telegram. Our baselines includes previous state-of-the-art GNNs for
directed graph, including DGCN (Tong et al., 2020b), DiGCN and DiGCNIB (Tong
et al., 2020a), and MagNet (Zhang et al., 2021c). Our models include NO
(vanilla 1-WL-GNN), PL (poset labeling trick which labels the source node as
$1$, target node as $2$, other nodes as $0$), ZO (zero-one labeling trick).

The results are shown in Table 3. The existing state-of-the-art method MAGNet
(Zhang et al., 2021b) outperforms 1-WL-GNN by $0.25\%$ on average. However,
1-WL-GNN with labeling trick outperforms all baselines. Moreover, poset
labeling trick (PL) achieves $2\%$ performance gain compared with the set
labeling trick (ZO). These results validate the power of poset labeling trick
and show that modeling partial order relation is critical for some tasks.

Table 3: Results on directed link prediction tasks: accuracy (%) $\pm$ standard deviation. | Cornell | Texas | Wisconsin | CoraML | CiteSeer | Telegram
---|---|---|---|---|---|---
DGCN | $70.4_{\pm 9}$ | $69.7_{\pm 6}$ | $69.8_{\pm 6}$ | $77.2_{\pm 1}$ | $71.2_{\pm 2}$ | $86.4_{\pm 1}$
DiGCN | $69.3_{\pm 7}$ | $69.7_{\pm 7}$ | $66.2_{\pm 7}$ | $75.1_{\pm 1}$ | $73.0_{\pm 1}$ | $78.2_{\pm 1}$
DiGCNIB | $65.7_{\pm 3}$ | $63.7_{\pm 6}$ | $67.6_{\pm 6}$ | $75.9_{\pm 4}$ | $73.7_{\pm 2}$ | $79.8_{\pm 2}$
MagNet | $70.4_{\pm 8}$ | $73.1_{\pm 7}$ | $70.4_{\pm 7}$ | $77.3_{\pm 1}$ | $71.8_{\pm 1}$ | $\underline{86.7_{\pm 1}}$
NO | $67.5_{\pm 7}$ | $72.0_{\pm 4}$ | $71.6_{\pm 5}$ | $78.7_{\pm 1}$ | $74.3_{\pm 1}$ | $84.1_{\pm 1}$
PL | $\mathbf{71.5_{\pm 4}}$ | $\mathbf{78.0_{\pm 4}}$ | $\mathbf{79.0_{\pm 3}}$ | $\mathbf{82.2_{\pm 1}}$ | $\underline{79.8_{\pm 1}}$ | $\mathbf{91.7_{\pm 1}}$
ZO | $\underline{71.1_{\pm 5}}$ | $\underline{77.6_{\pm 5}}$ | $\underline{74.0_{\pm 2}}$ | $\underline{79.4_{\pm 1}}$ | $\mathbf{79.9_{\pm 1}}$ | $85.6_{\pm 1}$
Table 4: Results on hyperedge prediction tasks: f1-score ($\%$) $\pm$ standard deviation. | NDC-c | NDC-s | tags-m | tags-a | email-En | email-EU | congress
---|---|---|---|---|---|---|---
ceGCN | $61.4_{\pm 0.5}$ | $42.1_{\pm 1.4}$ | $59.9_{\pm 0.9}$ | $54.5_{\pm 0.5}$ | $61.8_{\pm 3.2}$ | $66.4_{\pm 0.3}$ | $41.2_{\pm 0.3}$
ceSAGE | $65.7_{\pm 2.0}$ | $47.9_{\pm 0.7}$ | $63.5_{\pm 0.3}$ | $59.7_{\pm 0.7}$ | $59.4_{\pm 4.6}$ | $65.1_{\pm 1.9}$ | $53.0_{\pm 5.5}$
seRGCN | $67.6_{\pm 4.9}$ | $52.5_{\pm 0.6}$ | $57.2_{\pm 0.3}$ | $54.5_{\pm 0.6}$ | $59.9_{\pm 4.0}$ | $66.1_{\pm 0.6}$ | $54.4_{\pm 0.4}$
FS | $\underline{76.8_{\pm 0.4}}$ | $51.2_{\pm 3.2}$ | $64.2_{\pm 0.6}$ | $60.5_{\pm 0.2}$ | $68.5_{\pm 1.6}$ | $68.7_{\pm 0.2}$ | $56.6_{\pm 1.1}$
No | $60.2_{\pm 2.3}$ | $45.6_{\pm 0.8}$ | $56.6_{\pm 1.4}$ | $56.5_{\pm 1.8}$ | $56.9_{\pm 1.7}$ | $57.2_{\pm 0.9}$ | $54.1_{\pm 0.5}$
ZO | $\mathbf{82.5_{\pm 1.3}}$ | $\mathbf{63.6_{\pm 1.5}}$ | $\mathbf{71.4_{\pm 0.5}}$ | $\mathbf{70.4_{\pm 0.8}}$ | $\underline{66.1_{\pm 1.2}}$ | $\underline{72.1_{\pm 1.1}}$ | $\mathbf{65.1_{\pm 0.2}}$
SZO | $75.8_{\pm 0.7}$ | $\underline{62.2_{\pm 1.2}}$ | $\underline{71.0_{\pm 0.4}}$ | $\underline{69.6_{\pm 0.7}}$ | $\mathbf{67.7_{\pm 1.8}}$ | $\mathbf{73.3_{\pm 0.5}}$ | $\underline{64.2_{\pm 0.3}}$
Table 5: Results on subgraph tasks: f1-score ($\%$) $\pm$ standard deviation. Method | density | coreness | cutratio
---|---|---|---
ZO | $\mathbf{98.4_{\pm 1.2}}$ | $\mathbf{87.3_{\pm 15.0}}$ | $\mathbf{93.0_{\pm 1.3}}$
SZO | $94.3_{\pm 6.9}$ | $75.8_{\pm 7.0}$ | $85.6_{\pm 2.5}$
No | $47.8_{\pm 2.9}$ | $47.8_{\pm 5.3}$ | $81.4_{\pm 1.5}$
SubGNN | $91.9_{\pm 0.6}$ | $65.9_{\pm 3.1}$ | $62.9_{\pm 1.3}$
Sub2Vec | $45.9_{\pm 1.2}$ | $36.0_{\pm 1.9}$ | $35.4_{\pm 1.4}$

###  9.3 Hyperedge prediction task

We use the datasets and baselines in (Srinivasan et al., 2021). Our datasets
includes two drug networks (NDC-c, NDC-s), two forum networks (tags-m,
tags-a), two email networks (email-En, email-Eu), and a network of congress
members (congress). We use four GNNs designed for hypergraph as baselines,
including ceGCN, ceSAGE, seRGCN, and FS (family set) (Srinivasan et al.,
2021). Our models include ZO (zero-one labeling trick), SZO (subset($1$)
labeling trick with subset pooling), No (vanilla 1-WL-GNN).ZO and SZO
outperform all other methods significantly.

###  9.4 Subgraph prediction task

We use the datasets and baselines in (Alsentzer et al., 2020a). We use three
synthetic datasets, namely density, coreness, and cutratio. SubGNN (Alsentzer
et al., 2020a) and Sub2Vec (Adhikari et al., 2018) are models designed for
subgraph. Our models include ZO (zero-one labeling trick), SZO (subset($1$)
labeling trick with subset pooling), and No (vanilla 1-WL-GNN). Labeling
tricks boost vanilla 1-WL-GNN significantly. ZO improves $34\%$ score and SZO
achieves $26\%$ performance gain. Moreover, vanilla GNN augmented by labeling
trick also outperforms GNN designed for subgraph on all datasets. Moreover, ZO
outperforms SZO, which illustates that subset($1$) labeling tricks captures
pair-wise relation, while ZO can capture high-order relations better as shown
in Section 6.3.1.

##  10 Conclusions

In this paper, we proposed a theory of using GNNs for multi-node
representation learning. We first pointed out the key limitation of a common
practice in previous works that directly aggregates node representations as a
node-set representation. To address the problem, we proposed set labeling
trick which gives target nodes distinct labels in a permutation equivariant
way and characterized its expressive power. We further extended set labeling
trick to poset and subset labeling trick, as well as extending graph to
hypergraph. Our theory thoroughly discusses different variants and scenarios
of using labeling trick to boost vanilla GNNs, and provides a solid foundation
for future researchers to develop novel labeling tricks.

### Acknowledgments

M. Zhang is supported by the NSF China (No.62276003). P. Li is supported by
the National Science Foundation (NSF) award OAC-2117997.

##  A Proofs

###  A.1 Proof of Theorem 12

We restate Theorem 12: Given an NME GNN and an injective set aggregation
function AGG, for any
$S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime}$,
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})\Leftrightarrow(S,{\bm{\mathsfit{A}}})\\!\simeq\\!(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
where
$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)}):=\text{AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{(S)})|i\in
S\\})$.

Proof

We need to show $\text{AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{(S)})|i\in
S\\})=\text{AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{\prime(S^{\prime})}|i\in
S^{\prime}\\})$ $\Leftrightarrow$
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$.

To prove $\Rightarrow$, we notice that with an injective AGG,

$\displaystyle\text{AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{(S)}))|i\in
S\\})=\text{AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{\prime(S^{\prime})}))|i\in
S^{\prime}\\})$ $\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}v_{1}\in S,v_{2}\in S^{\prime},~{}\text{such
that}~{}\text{GNN}(v_{1},{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(v_{2},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})$
(11) $\displaystyle\Longrightarrow~{}$
$\displaystyle(v_{1},{\bm{\mathsfit{A}}}^{(S)})\simeq(v_{2},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})~{}~{}~{}~{}\text{(because
GNN is node-most-expressive)}$ (12) $\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}\pi\in\Pi_{n},~{}\text{such
that}~{}v_{1}=\pi(v_{2}),{\bm{\mathsfit{A}}}^{(S)}=\pi({\bm{\mathsfit{A}}}^{\prime(S^{\prime})}).$
(13)

Remember ${\bm{\mathsfit{A}}}^{(S)}$ is constructed by stacking
${\bm{\mathsfit{A}}}$ and ${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})$ in the
third dimension, where ${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})$ is a
tensor satisfying: $\forall\pi\in\Pi_{n}$,  (1)
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))\Rightarrow
S=\pi(S^{\prime})$, and  (2)
$S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})\Rightarrow{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$.
With
${\bm{\mathsfit{A}}}^{(S)}=\pi({\bm{\mathsfit{A}}}^{\prime(S^{\prime})})$, we
have both

$\displaystyle{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime}),~{}{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})).$

Because
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))\Rightarrow
S=\pi(S^{\prime})$, continuing from Equation (13), we have

$\displaystyle\text{AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{(S)})|i\in
S\\})=\text{AGG}(\\{\text{GNN}(i,{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})|i\in
S^{\prime}\\})$ $\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}\pi\in\Pi_{n},~{}\text{such
that}~{}{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime}),~{}{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$
(14) $\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}\pi\in\Pi_{n},~{}\text{such
that}~{}{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime}),~{}S=\pi(S^{\prime})$
(15) $\displaystyle\Longrightarrow~{}$
$\displaystyle(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}).$
(16)

Now we prove $\Leftarrow$. Because
$S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})\Rightarrow{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$,
we have:

$\displaystyle(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$
$\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}\pi\in\Pi_{n},~{}\text{such
that}~{}S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime})$
(17) $\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}\pi\in\Pi_{n},~{}\text{such
that}~{}S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}=\pi({\bm{\mathsfit{A}}}^{\prime}),{\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$
(18) $\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}\pi\in\Pi_{n},~{}\text{such
that}~{}S=\pi(S^{\prime}),{\bm{\mathsfit{A}}}^{(S)}=\pi({\bm{\mathsfit{A}}}^{\prime(S^{\prime})})$
(19) $\displaystyle\Longrightarrow~{}$
$\displaystyle\exists~{}\pi\in\Pi_{n},~{}\text{such that}~{}\forall v_{2}\in
S^{\prime},v_{1}=\pi(v_{2})\in
S,\text{GNN}(v_{1},{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(v_{2},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})$
(20) $\displaystyle\Longrightarrow~{}$
$\displaystyle\text{AGG}(\\{\text{GNN}(v_{1},{\bm{\mathsfit{A}}}^{(S)})|v_{1}\in
S\\})=\text{AGG}(\\{\text{GNN}(v_{2},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})|v_{2}\in
S^{\prime}\\}),$ (21)

which concludes the proof.

###  A.2 Proof of Theorem 13 and Theorem 29

As an $h$-layer 1-WL-GNN only encodes an $h$-hop neighbors for each node, we
define locally $h$-isomorphism.

###### Definition 34

For all $S,{\bm{\mathsfit{A}}},S^{\prime},{\bm{\mathsfit{A}}}^{\prime}$,
$(S,{\bm{\mathsfit{A}}})$ and $(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$ are
locally $h$-isomorphic iff
$(S,{\bm{\mathsfit{A}}}_{S,h})\simeq(S^{\prime},{\bm{\mathsfit{A}}}_{S^{\prime},h})$,
where ${\bm{\mathsfit{A}}}_{S,h}$ means the subgraph of ${\bm{\mathsfit{A}}}$
induced by the node set $\\{v\in V|\exists u\in
S,d_{sp}(u,v,{\bm{\mathsfit{A}}})\leq h\\}$, and
$d_{sp}(u,v,{\bm{\mathsfit{A}}})$ means the shortest path distance between
node $u,v$ in graph ${\bm{\mathsfit{A}}}$.

We restate Theorem 13(Theorem 29): In any non-attributed graph with $n$ nodes,
if the degree of each node in the graph is between $1$ and
$\left((1-\epsilon)\log n\right)^{1/(2h+2)}$ for any constant $\epsilon>0$,
then there exists $\omega(n^{2\epsilon})$ many pairs of non-isomorphic links
$(u,w),(v,w)$ such that an $h$-layer 1-WL-GNN gives $u,v$ the same
representation, while with zero-one labeling trick (subset zero-one labeling
trick) the 1-WL-GNN gives $u,v$ different representations. These two theorems
can be proved together because the special cases we build can be solved by
both of them.

Proof

Our proof has two steps. First, we would like to show that there are
$\omega(n^{\epsilon})$ nodes that are locally $h$-isomorphic to each other.
Then, we prove that among these nodes, there are at least
$\omega(n^{2\epsilon})$ pairs of nodes such that there exists another node
constructing locally $h$ non-isomorphic links with either of the two nodes in
each node pair.

Step 1. Consider an arbitrary node $v$ and denote the node set induced by the
nodes that are at most $h$-hop away from $v$ as $G_{v}^{(h)}$ (the $h$-hop
enclosing subgraph of $v$). As each node is with degree
$d\leq\big{(}(1-\epsilon)\log n\big{)}^{1/(2h+2)}$, then the number of nodes
in $G_{v}^{(h)}$, denoted by $|V(G_{v}^{(h)})|$, satisfies

$\displaystyle|V(G_{v}^{(h)})|\leq\sum_{i=0}^{h}d^{i}\leq
d^{h+1}=\big{(}(1-\epsilon)\log n\big{)}^{1/2}.$

We set $K=\max_{v\in V}|V(G_{v}^{(h)})|$ and thus
$K\leq\big{(}(1-\epsilon)\log n\big{)}^{1/2}$.

Now we expand subgraphs $G_{v}^{(h)}$ to $\bar{G}_{v}^{(h)}$ by adding
$K-|V(G_{v}^{(h)})|$ independent nodes for each node $v\in V$. Then, all
$\bar{G}_{v}^{(h)}$ have the same number of nodes, which is $K$, though they
may not be connected graphs. Next, we consider the number of non-isomorphic
graphs over $K$ nodes. Actually, the number of non-isomorphic graph structures
over $K$ nodes is bounded by

$2^{K\choose 2}\leq 2^{(1-\epsilon)\log n}=n^{1-\epsilon}.$ (22)

Therefore, due to the pigeonhole principle, there exist
$\omega(n/n^{1-\epsilon})=\omega(n^{\epsilon})$ many nodes $v$ whose
$\bar{G}_{v}^{(h)}$ are isomorphic to each other. Denote the set of these
nodes as $V_{iso}$, which consist of nodes that are all locally $h$-isomorphic
to each other.

Step 2. Let us partition $V_{iso}=\cup_{i=1}^{q}V_{i}$ so that for all
$i\in\\{1,2,...,q\\}$, nodes in $V_{i}$ share the same first-hop neighbor
sets. Then, consider any pair of nodes $u,v$ such that $u,v$ are from
different $V_{i}$’s. Since $u,v$ share identical $h$-hop neighborhood
structures, an $h$-layer 1-WL-GNN will give them the same representation.
Then, we may pick one $u$’s first-hop neighbor $w$ that is not $v$’s first-hop
neighbor. We know such $w$ exists because of the definition of $V_{i}$. As $w$
is $u$’s first-hop neighbor and is not $v$’s first-hop neighbor, $(u,w)$ and
$(v,w)$ are not isomorphic. With labeling trick, the $h$-layer 1-WL-GNN will
give $u,v$ different representations immediately after the first message
passing round due to $w$’s distinct label. Therefore, we know such a
$(u,w),(v,w)$ pair is exactly what we want.

Based on the partition $V_{iso}$, we know the number of such non-isomorphic
link pairs $(u,w)$ and $(v,w)$ is at least:

$\displaystyle Y\geq\sum_{i,j=1,i\neq
j}^{q}|V_{i}||V_{j}|=\frac{1}{2}\left[(\sum_{i=1}^{q}|V_{i}|)^{2}-\sum_{i=1}^{q}|V_{i}|^{2}\right].$
(23)

Because of the definitions of the partition,
$\sum_{i=1}^{q}|V_{i}|=|V_{iso}|=\omega(n^{\epsilon})$ and the size of each
$V_{i}$ satisfies

$\displaystyle 1\leq|V_{i}|\leq d_{w}\leq\big{(}(1-\epsilon)\log
n\big{)}^{1/(2h+2)},$

where $w$ is one of the common first-hop neighbors shared by all nodes in
$V_{i}$ and $d_{w}$ is its degree.

By plugging in the range of $|V_{i}|$, Eq.23 leads to

$\displaystyle Y$
$\displaystyle\geq\frac{1}{2}[(\sum_{i=1}^{q}|V_{i}|)^{2}-\sum_{i=1}^{q}|V_{i}|(\max_{j\in\\{1,2,...,q\\}}|V_{j}|)]$
$\displaystyle=\frac{1}{2}(\omega(n^{2\epsilon})-\omega(n^{\epsilon})\mathcal{O}\Big{(}\big{(}(1-\epsilon)\log
n\big{)}^{1/(2h+2)}\Big{)}$ $\displaystyle=\omega(n^{2\epsilon}),$

which concludes the proof.

###  A.3 Proof of Theorem 15

Proof  This proof shares the same first step as Appendix A.2.

Step 2. Let us partition
${\mathbb{V}}_{iso}=\bigcup_{i=1}^{q}{\mathbb{V}}_{i}$, nodes in each $V_{i}$
share the same one-hop neighbor. Consider two nodes
$u\in{\mathbb{V}}_{i},v\in{\mathbb{V}}_{j},i\neq j$. There exists a node $w\in
N(u),w\notin N(v)$. Let $\tilde{\mathbb{V}}_{u,v,w}$ denote
${\mathbb{V}}-\\{u,v,w\\}-N(u)$. $|{\mathbb{V}}_{v}|\geq
n-3-\big{(}(1-\epsilon)\log n\big{)}^{1/(2h+2)}$. Consider arbitrary subset
${\mathbb{V}}^{\prime}$ of $\tilde{\mathbb{V}}_{u,v,w}$. Let
${\mathcal{S}}_{1}$ denote the subgraph induced by
${\mathbb{V}}^{\prime}\bigcup\\{u,w\\}$, ${\mathcal{S}}_{2}$ denote the
subgraph induced by ${\mathbb{V}}^{\prime}\bigcup\\{v,w\\}$. The density of
${\mathcal{S}}_{1}$ is higher than ${\mathcal{S}}_{2}$. And 1-WL-GNN with
zero-one labeling trick can fit density perfectly (Theorem 1 in (Wang and
Zhang, 2022)), so 1-WL-GNN with labeling trick can distinguish
${\mathcal{S}}_{1}$ and ${\mathcal{S}}_{2}$, while 1-WL-GNNs cannot.

The number of pair $(u,v,w)$ is $w(n^{2\epsilon})$. Therefore, the number of
these pairs of subgraphs is bounded by

$w(n^{2\epsilon})2^{n-3-((1-\epsilon)\log
n)^{1/(2h+2)}}=w(2^{n}n^{3\epsilon-1}).$ (24)

###  A.4 Proof of Theorem 22

This proof shares the same first step as Appendix A.2.

Number of link: the same as the step 2 in Appendix A.2.

Number of subgraph: similar to the step 2 in Appendix A.3. Let us partition
${\mathbb{V}}_{iso}=\bigcup_{i=1}^{q}{\mathbb{V}}_{i}$, nodes in each $V_{i}$
share the same one-hop neighbor. Consider two nodes
$u\in{\mathbb{V}}_{i},v\in{\mathbb{V}}_{j},i\neq j$. There exists a node $w\in
N(u),w\notin N(v)$. Let $\tilde{\mathbb{V}}_{u,v,w}$ denote
${\mathbb{V}}-\\{u,v,w\\}-N(u)$. $|{\mathbb{V}}_{v}|\geq
n-3-\big{(}(1-\epsilon)\log n\big{)}^{1/(2h+2)}$. Consider arbitrary subset
${\mathbb{V}}^{\prime}$ of $\tilde{\mathbb{V}}_{u,v,w}$ and a partial order
$\leq_{{\mathbb{V}}^{\prime}}$. Let ${\mathcal{S}}_{1}$ denote the subgraph
induced by poset
$\big{(}({\mathbb{V}}^{\prime}\bigcup\\{u,w\\}),\leq_{{\mathbb{V}}^{\prime}}\cup\\{(u,a)|a\in
sV^{\prime}\\}\cup\\{(w,a)|a\in sV^{\prime}\cup\\{u\\}\\}\big{)}$,
${\mathcal{S}}_{2}$ denote the subgraph induced by poset
$\big{(}{\mathbb{V}}^{\prime}\bigcup\\{v,w\\},\leq_{{\mathbb{V}}^{\prime}}\cup\\{(v,a)|a\in
sV^{\prime}\\}\cup\\{(w,a)|a\in sV^{\prime}\cup\\{v\\}\\}\big{)}$. 1-WL-GNN
with labeling trick can distinguish ${\mathcal{S}}_{1}$ and
${\mathcal{S}}_{2}$ as the edges between $(u,w)$ and $(v,w)$ are distinct,
while 1-WL-GNNs cannot.

The number of pair $(u,v,w)$ is $w(n^{2\epsilon})$. Therefore, the number of
these pairs of subgraphs is bounded by

$w(n^{2\epsilon})w(n-3-\big{(}(1-\epsilon)\log
n\big{)}^{1/(2h+2)})!=w\Big{(}\big{(}(1-\epsilon)n\big{)}!\Big{)}.$ (25)

###  A.5 Proof of Proposition 14

As shown in Figure 1(a), 1-WL-GNN cannot count common neighbor and thus fail
to implement $h$. Now we prove that with zero-one labeling trick, 1-WL-GNN can
implement $h$.

Given a graph ${\bm{\mathsfit{A}}}$ and a node pair $(i,j)$, let $z_{k}^{(k)}$
denote the embedding of node $i$ at $k^{\text{th}}$ message passing layer.

$z_{k}^{(0)}=\begin{bmatrix}1\\\ \delta_{ki}+\delta_{kj}\end{bmatrix}.$ (26)

The first dimension is all $1$ (vanilla node feature), and the second
dimension is zero-one label.

The first layer is,

$z_{k}^{(1)}=\begin{bmatrix}g_{1}(a_{k}^{(1)}[1])\\\ g_{2}(a_{k}^{(1)}[1])\\\
a_{k}^{(1)}[2]>2\end{bmatrix}$ (27)

where $a_{k}^{(1)}=\sum_{l\in N(k)}z_{l}^{(0)}$, $[1]$ means the first element
of vector, and $[2]$ means the second element.

The second layer is

$z_{k}^{(2)}=\begin{bmatrix}\sum_{l\in N(k)}z_{k}^{(1)}[3]z_{k}^{(1)}[2]\\\
\sum_{l\in N(k)}(1-z_{k}^{(1)}[3])z_{k}^{(1)}[1]\\\ \end{bmatrix}$ (28)

The pooling layer is

$z_{ij}=f(\\{z_{i}[2],z_{j}[2]\\},\frac{z_{i}[1]+z_{j}[1]}{2})$ (29)

###  A.6 Proof of Theorem 21

Proof  $\Leftarrow$: When
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
there exists a permutation $\pi$,
$\pi(S)=S^{\prime},\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime}$.

$\displaystyle\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})$
$\displaystyle=\text{AGG}(\\{\text{GNN}(v,{\bm{\mathsfit{A}}}^{(S)}|v\in
S\\})$ (30)
$\displaystyle=\text{AGG}(\\{\text{GNN}(\pi(v),\pi({\bm{\mathsfit{A}}}^{(S)}))|v\in
S\\})$ (31)
$\displaystyle=\text{AGG}(\\{\text{GNN}(\pi(v),{\bm{\mathsfit{A}}}^{\prime(S^{\prime})}|v\in
S\\})$ (32)
$\displaystyle=\text{AGG}(\\{\text{GNN}(v^{\prime},{\bm{\mathsfit{A}}}^{\prime(S^{\prime})})|v^{\prime}\in
S^{\prime}\\})$ (33)
$\displaystyle=\text{GNN}(S^{\prime},{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime})})$
(34)

$\Rightarrow$:

$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(S^{\prime},{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime})})\\\
$ (35) $\text{AGG}(\\{\text{GNN}(v,{\bm{\mathsfit{A}}}^{(S)})|v\in
S\\})=\text{AGG}(\\{\text{GNN}(v^{\prime},{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime})})|v^{\prime}\in
S^{\prime}\\})$ (36)

As AGG is injective, There exist $v_{0}\in S,v^{\prime}_{0}\in S^{\prime}$,

$\text{GNN}(v_{0},{\bm{\mathsfit{A}}}^{(S)})=\text{GNN}(v_{0}^{\prime},{\bm{\mathsfit{A}}}^{(S^{\prime})})$
(37)

As GNN is node most expressive,

$\exists\pi,\pi(v_{0})=v_{0}^{\prime},\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime},\pi({\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}}))={\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}).$

Therefore,
$\pi({\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}}))={\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))$.

###  A.7 Proof of Theorem 25

Proof  $\Leftarrow$: When
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
there exists a permutation $\pi$,
$\pi(S)=S^{\prime},\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime}$.

AGG
$\displaystyle\left(\left\\{\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{(S-\\{v\\})})|u\in
S\\})|v\in S\right\\}\right)$ (38)
$\displaystyle=\text{AGG}(\\{\text{AGG}(\\{\text{GNN}(\pi(u),\pi({\bm{\mathsfit{A}}}^{(S-\\{v\\})})|u\in
S\\})|v\in S\\})$ (39)
$\displaystyle=\text{AGG}(\\{\text{AGG}(\\{\text{GNN}(\pi(u),{\bm{\mathsfit{A}}}^{\prime(\pi(S)-\\{\pi(v)\\})}|u\in
S\\})|v\in S\\})$ (40)
$\displaystyle=\text{AGG}(\\{\text{AGG}(\\{\text{GNN}(u^{\prime},{\bm{\mathsfit{A}}}^{\prime(S^{\prime}-\\{v^{\prime}\\})})|u^{\prime}\in
S^{\prime}\\})|v^{\prime}\in S^{\prime}\\})$ (41)

$\Rightarrow$:

$\displaystyle\text{AGG}($
$\displaystyle\\{\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{(S-\\{v\\})})|u\in
S\\})|v\in S\\})$
$\displaystyle=\text{AGG}(\\{\text{AGG}(\\{\text{GNN}(u^{\prime},{\bm{\mathsfit{A}}}^{\prime(S^{\prime}-\\{v^{\prime}\\})})|u^{\prime}\in
S^{\prime}\\})|v^{\prime}\in S^{\prime}\\}).$

As AGG is injective,

$\\{\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{\\!(S-\\{\\!v\\!\\})\\!})|v\in
S\\})|u\in
S\\}=\\{\\{\text{AGG}(\\{\text{GNN}(u^{\prime},{\bm{\mathsfit{A}}}^{\\!(S^{\prime}-\\{\\!v^{\prime}\\!\\})\\!})|v^{\prime}\in
S^{\prime}\\})\\}.$ (42)

There exist $v_{0}\in S,v^{\prime}_{0}\in S^{\prime}$,

$\text{AGG}(\\{\text{GNN}(u,{\bm{\mathsfit{A}}}^{(S-\\{v_{0}\\})})|u\in
S\\})=\text{AGG}(\\{\text{GNN}(u^{\prime},{\bm{\mathsfit{A}}}^{(S^{\prime}-\\{v^{\prime}_{0}\\})})|u^{\prime}\in
S^{\prime}\\}).$ (43)

Similarly, there exists $u_{0}^{\prime}\in S^{\prime}$

$\text{GNN}(v_{0},{\bm{\mathsfit{A}}}^{(S-\\{v_{0}\\})})=\text{GNN}(u_{0}^{\prime},{\bm{\mathsfit{A}}}^{(S^{\prime}-\\{v^{\prime}_{0}\\})}).$
(44)

As GNN is node most expressive,

$\exists\pi,\pi(v_{0})=u_{0}^{\prime},\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime},\pi({\bm{\mathsfit{L}}}(S-\\{v_{0}\\},{\bm{\mathsfit{A}}}))={\bm{\mathsfit{L}}}(S^{\prime}-\\{v^{\prime}_{0}\\},{\bm{\mathsfit{A}}}^{\prime})).$

Therefore, $\pi(S-\\{v_{0}\\})=S^{\prime}-\\{v^{\prime}_{0}\\}$. Note that
$v_{0}\notin S-\\{v_{0}\\}$, so $u^{\prime}_{0}=\pi(v_{0})\notin
S^{\prime}-\\{v^{\prime}_{0}\\}$, while $u^{\prime}_{0}\in S^{\prime}$,
therefore $u^{\prime}_{0}=v^{\prime}_{0}$.

Therefore, $\pi(S)=S^{\prime}$, and
$\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime}$, so
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$.

###  A.8 Proof of Theorem 26

We prove it by contradiction: If $\exists v_{0}\in S,v_{0}^{\prime}\in
S^{\prime}$,

$\text{GNN}(S,{\bm{\mathsfit{A}}}^{(S-\\{v_{0}\\})})=\text{GNN}(S^{\prime},{{\bm{\mathsfit{A}}}^{\prime}}^{(S^{\prime}-\\{v_{0}^{\prime}\\})})$
(45)

Therefore, there exists $u_{0}\in S,u_{0}^{\prime}\in S^{\prime}$

$\text{GNN}(v_{0},{\bm{\mathsfit{A}}}^{(S-\\{v_{0}\\})})=\text{GNN}(u_{0}^{\prime},{\bm{\mathsfit{A}}}^{(S^{\prime}-\\{v^{\prime}_{0}\\})}).$
(46)

As GNN is node most expressive,

$\exists\pi,\pi(v_{0})=u_{0}^{\prime},\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime},\pi({\bm{\mathsfit{L}}}(S-\\{v_{0}\\},{\bm{\mathsfit{A}}}))={\bm{\mathsfit{L}}}(S^{\prime}-\\{v^{\prime}_{0}\\},{\bm{\mathsfit{A}}}^{\prime})).$

Therefore, $\pi(S-\\{v_{0}\\})=S^{\prime}-\\{v^{\prime}_{0}\\}$. Note that
$v_{0}\notin S-\\{v_{0}\\}$, so $u^{\prime}_{0}=\pi(v_{0})\notin
S^{\prime}-\\{v^{\prime}_{0}\\}$, while $u^{\prime}_{0}\in S^{\prime}$,
therefore $u^{\prime}_{0}=v^{\prime}_{0}$.

Therefore, $\pi(S)=S^{\prime}$, and
$\pi({\bm{\mathsfit{A}}})={\bm{\mathsfit{A}}}^{\prime}$, so
$(S,{\bm{\mathsfit{A}}})\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$,
which contradicts to that
$(S,{\bm{\mathsfit{A}}})\not\simeq(S^{\prime},{\bm{\mathsfit{A}}}^{\prime})$.

###  A.9 Proof of Proposition 18

Due to the property 1 in Definition 16,
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})=\pi({\bm{\mathsfit{L}}}(S^{\prime},{\bm{\mathsfit{A}}}^{\prime}))\Rightarrow
S=\pi(S^{\prime})$. Therefore, for all $v\in S$, $\pi^{-1}(v)\in S$. Moreover,
$\forall v^{\prime}\in S^{\prime}$, $\exists v\in S,\pi^{-1}(v)=v^{\prime}$.

Consider an edge $(u,v)$ in ${\mathcal{H}}_{S}$. According to Definition 17,
$u\neq v$,$u\leq_{S}v$, and there exists no node $w\in S,w\notin{u,v}$ that
$u\leq_{S}w$ and $w\leq_{S}v$. As $\pi(S^{\prime})=S$,
$\pi^{-1}(u)\neq\pi^{-1}(v)$,$\pi^{-1}(u)\leq_{S^{\prime}}\pi^{-1}(v)$, and
there exists no node $\pi^{-1}(w)\in
S^{\prime},\pi^{-1}(w)\notin{\pi^{-1}(u),\pi^{-1}(v)}$ that
$\pi^{-1}(u)\leq_{S^{\prime}}\pi^{-1}(w)$ and
$\pi^{-1}(w)\leq_{S^{\prime}}\pi^{-1}(v)$. Therefore, when
$S=\pi(S^{\prime})$, for all edge $(u,v)$ in ${\mathcal{H}}_{S}$, edge
$(\pi^{-1}(u),\pi^{-1}(v))$ exists in ${\mathcal{H}}_{S^{\prime}}$.

Similarly, as $S^{\prime}=\pi^{-1}(S)$, for all edge
$(\pi^{-1}(u),\pi^{-1}(v))$ in ${\mathcal{H}}_{S^{\prime}}$, edge

$((\pi^{-1})^{-1}(\pi^{-1}(u)),(\pi^{-1})^{-1}(\pi^{-1}(v)))=(u,v),$

exists in ${\mathcal{H}}_{S^{\prime}}$. So
${\mathcal{H}}_{S}=\pi({\mathcal{H}}_{S^{\prime}})$. Equivalently, for all
$v\in S^{\prime}$, $\pi(v)$ is in $S$, and
$(\\{v\\},{\mathcal{H}}_{S^{\prime}})\simeq(\\{\pi(v)\\},{\mathcal{H}}_{S})$.

Assume that $u,v$ are not isomorphic in $S$, but
${\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})_{u,u,:}={\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})_{v,v,:}$.
Define permutation $\pi:V\to V$ as follows,

$\pi(i)=\begin{cases}v&\text{if }i=u\\\ u&\text{if }i=v\\\
i&\text{otherwise}\end{cases}.$ (47)

$\pi({\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}}))={\bm{\mathsfit{L}}}(S,{\bm{\mathsfit{A}}})\Rightarrow\pi(S)=S\Rightarrow(v,{\mathcal{H}}_{S})\simeq(u,{\mathcal{H}}_{S})$.
Equivalently, non-isomorphic nodes in the same hasse diagram should have
different labels.

###  A.10 Proof of Theorem 32

The main gap between hypergraph isomorphism and corresponding graph
isomorphism is that hypergraph permutation is composed of two permutation
transforms node and edge order independently, while corresponding graph
isomorphism is only related to one node permutation, so we first define ways
to combine and split permutations.

Sorting of corresponding graph: Let
$I_{V}(IG_{H})=\\{i|(IG_{H})_{i,i,d+1}=1\\}$ denote nodes in $G(H)$
corresponding to nodes in $H$. Let
$I_{E}(IG_{H})=\\{i|(IG_{H})_{i,i,d+1}=0\\}$ denote the nodes representing
hypergraph edges. We define a permutation $\pi^{I_{V},I_{E}}\in\Pi_{n+m}$,
$\pi^{I_{V},I_{E}}$,
$\pi^{I_{V},I_{E}}(I_{V})=[n],\pi^{I_{V},I_{E}}(I_{E})=\\{n+1,n+2,...,n+m\\}$.

Concatenation of permutation: Let $\pi_{1}\in\Pi_{n},\pi_{2}\in\Pi_{m}$. Their
concatenation $\pi_{1}|\\!|\pi_{2}\in\Pi_{m+n}$

$\pi_{1}|\\!|\pi_{2}(i)=\begin{cases}\pi_{1}(i)&i\leq n\\\
n+\pi_{2}(i-n)&\text{otherwise}\end{cases}$ (48)

When $S_{1},S_{2}$ have different sizes, or $H_{1}$, $H_{2}$ have different
number of nodes or hyperedges, two poset are non-isomorphic. So we only
discuss the case that the poset and hypergraph sizes are the same. Let $n,m$
denote the number of nodes and hyperedges in the hypergraph. Then the
corresponding graph has $n+m$ nodes.

We first prove $\Rightarrow$: When $(S,H)\sim(S^{\prime},H^{\prime})$,
according to Definition 30, there exists
$\pi_{1}\in\Pi_{n},\pi_{2}\in\Pi_{m},(\pi_{1},\pi_{2})(H)=H^{\prime},\pi_{1}(S)=S^{\prime}$.
Then, $(\pi_{1}|\\!|\pi_{2})(IG_{H})=IG_{H^{\prime}}$ and
$(\pi_{1}|\\!|\pi_{2})(S)=S^{\prime}$.

Then we prove $\Leftarrow$: When
$(S,IG_{H})\simeq(S^{\prime},IG_{H^{\prime}})$. We can first sort two
incidence graph. Let $\pi=\pi^{I_{V}(IG_{H}),I_{E}(IG_{H})}$ and
$\pi^{\prime}=\pi^{I_{V}(IG_{H^{\prime}}),I_{E}(IG_{H^{\prime}})}$. Then two
posets and graphs are still isomorphic.

$(\pi(S),\pi(IG_{H}))\simeq(\pi^{\prime}(S^{\prime}),\pi^{\prime}(IG_{H^{\prime}}))$
(49)

Therefore, $\exists\pi_{0}\in\Pi_{n+m}$,
$\pi(S)=\pi_{0}(\pi^{\prime}(S^{\prime})),\pi(IG_{H})=\pi_{0}(\pi^{\prime}(IG_{H^{\prime}}))$.
Let
${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}\in{\mathbb{R}}^{(n+m)\times(n+m)\times
d+1}$ denote the adjacency tensor of
$\pi(IG_{H}),\pi^{\prime}(IG_{H^{\prime}})$ respectively. Therefore,

${\bm{\mathsfit{A}}}=\pi_{0}({\bm{\mathsfit{A}}}^{\prime})\Rightarrow{\bm{\mathsfit{A}}}_{\pi_{0}(i),\pi_{0}(i),d+1}={\bm{\mathsfit{A}}}^{\prime}_{i,i,d+1},\forall
i\in\\{1,2,...,m+n\\}.$ (50)

As the nodes in ${\bm{\mathsfit{A}}},{\bm{\mathsfit{A}}}^{\prime}$ are sorted,
${\bm{\mathsfit{A}}}_{i,i,d+1}=1,{\bm{\mathsfit{A}}}^{\prime}_{i,i,d+1}=1$ if
$i\leq n$, and
${\bm{\mathsfit{A}}}_{i,i,d+1}=0,{\bm{\mathsfit{A}}}^{\prime}_{i,i,d+1}=0$ if
$i>n$. Therefore, $\pi_{0}$ maps $\\{1,2,...,n\\}$ to $\\{1,2,...,n\\}$ and
$\\{n+1,n+2,...,n+m\\}$ to $\\{n+1,n+2,...,n+m\\}$. Therefore, we can
decompose $\pi_{0}$ into two permutation $\pi_{1},\pi_{2}$.

$\pi_{1}(i)=\pi_{0}(i),i\in\\{1,2,...,n\\}$ (51)
$\pi_{2}(i)=\pi_{0}(i+n)-n,i\in\\{1,2,...,m\\}$ (52)

Then, $S=\pi_{1}(S^{\prime})$ and $H=(\pi_{1},\pi_{2})(H^{\prime})$.

##  B Experimental settings

##### Computing infrastructure.

We leverage Pytorch Geometric and Pytorch for model development. All our
models run on an Nvidia 3090 GPU on a Linux server.

##### Model Implementation.

For undirected link prediction tasks, our implementation is based on the code
of SEAL (Zhang and Chen, 2018a), which segregates an ego subgraph from the
whole graph for each link. For other tasks, our model runs on the whole graph.
We use optuna to perform random search. Hyperparameters were selected to
optimize scores on the validation sets. We will release the code later.

##  C More details about the datasets

###  C.1 Undirected Link Prediction

We use eight real-world datasets from SEAL (Zhang and Chen, 2018a): USAir is a
network of US Air lines. NS is a collaboration network of researchers. PB is a
network of US political blogs. Power is an electrical grid of western US.
Router is a router-level Internet. Ecoli is a metabolic network in E.coli.
Cele is a neural network of C.elegans. Yeast is a protein-protein interaction
network in yeast.

We also use OGB datasets (Hu et al., 2020): ogbl-ppa, ogbl-collab, ogbl-ddi,
and ogbl-citation2. Among them, ogbl-ppa is a protein-protein association
graph where the task is to predict biologically meaningful associations
between proteins. ogbl-collab is an author collaboration graph, where the task
is to predict future collaborations. ogbl-ddi is a drug-drug interaction
network, where each edge represents an interaction between drugs which
indicates the joint effect of taking the two drugs together is considerably
different from their independent effects. ogbl-citation2 is a paper citation
network, where the task is to predict missing citations. We present the
statistics of these datasets in Table 6. More information about these datasets
can be found in (Hu et al., 2020).

Table 6: Statistics and evaluation metrics of undirected link prediction
datasets.

Dataset | #Nodes | #Edges | Avg. node deg. | Split ratio | Metric
---|---|---|---|---|---
USAir | 332 | 2,126 | 12.81 | 0.85/0.05/0.10 | auroc
NS | 1,589 | 2,742 | 3.45 | 0.85/0.05/0.15 | auroc
PB | 1,222 | 16,714 | 27.36 | 0.85/0.05/0.15 | auroc
Yeast | 2,375 | 11,693 | 9.85 | 0.85/0.05/0.15 | auroc
C.ele | 297 | 2,148 | 14.46 | 0.85/0.05/0.15 | auroc
Power | 4,941 | 6,594 | 2.67 | 0.85/0.05/0.15 | auroc
Router | 5,022 | 6,258 | 2.49 | 0.85/0.05/0.15 | auroc
E.coli | 1,805 | 14,660 | 16.24 | 0.85/0.05/0.15 | auroc
ogbl-ppa | 576,289 | 30,326,273 | 105.25 | fixed | Hits@100
ogbl-collab | 235,868 | 1,285,465 | 10.90 | fixed | Hits@50
ogbl-ddi | 4,267 | 1,334,889 | 625.68 | fixed | Hits@20
ogbl-citation2 | 2,927,963 | 30,561,187 | 20.88 | fixed | MRR

###  C.2 Directed Link Prediction

We use the same settings and datasets as He et al. (2022). The task is to
predict whether a directed link exists in a graph. Texas, Wisconsin, and
Cornell consider websites as nodes and links between websites as edges. Cora-
ML and CiteSeer are citation networks. Telegram is an influence graph between
Telegram channels. Their statistics are shown in Table 7.

Table 7: Statistics and evaluation metrics of directed link prediction datasets. Dataset | #Nodes | #Edges | Avg. node deg. | Split ratio | Metric
---|---|---|---|---|---
wisconsin | 251 | 515 | 4.10 | 0.80/0.05/0.15 | accuracy
cornell | 183 | 298 | 3.26 | 0.80/0.05/0.15 | accuracy
texas | 183 | 325 | 3.55 | 0.80/0.05/0.15 | accuracy
cora_ml | 2,995 | 8,416 | 5.62 | 0.80/0.05/0.15 | accuracy
telegram | 245 | 8,912 | 72.75 | 0.80/0.05/0.15 | accuracy
citeseer | 3,312 | 4,715 | 2.85 | 0.80/0.05/0.15 | accuracy

###  C.3 Hyperedge prediction datasets

We use the datasets and baselines in (Srinivasan et al., 2021). NDC-c (NDC-
classes) and NDC-s (NDC-substances) are both drug networks. NDC-c takes each
class label as a node and the set of labels applied to a drug as a hyperedge.
NDC-s takes substances as nodes and the set of substances contained in a drug
as a hyperedge. Tags-m (tags-math-sx) and tags-a (tags-ask-ubuntu) are from
online Stack Exchange forums, where nodes are tags and hyperedges are sets of
tags for the same questions. Email-En (email-Enron) and email-Eu are two email
networks where each node is a email address and email hyperedge is the set of
all addresses on an email. Congress (congress-bills) takes Congress members as
nodes, and each hyperedge corresponds to the set of members in a committe or
cosponsoring a bill. Their statistics are shown in Table 8.

Table 8: Statistics and evaluation metrics of directed link prediction datasets. Dataset | #Nodes | #Hyperdges | Split ratio | Metric
---|---|---|---|---
NDC-c | 6,402 | 1,048 | 5-fold | f1-score
NDC-s | 49,886 | 6,265 | 5-fold | f1-score
tags-m | 497,129 | 145,054 | 5-fold | f1-score
tags-a | 591,904 | 169,260 | 5-fold | f1-score
email-En | 4,495 | 1,458 | 5-fold | f1-score
email-EU | 85,109 | 24,400 | 5-fold | f1-score
congress | 732,300 | 83,106 | 5-fold | f1-score

###  C.4 Subgraph Prediction Tasks

Following (Wang and Zhang, 2022), we use three synthetic datasets: density,
cut ratio, coreness. The task is to predict the corresponding properties of
randomly selected subgraphs in random graphs. Their statistics are shown in
Table 9.

Table 9: Statistics and evaluation metrics of directed link prediction datasets. Dataset | #Nodes | #Edges | #Subgraphs | Split ratio | Metric
---|---|---|---|---|---
density | 5,000 | 29,521 | 250 | 0.50/0.25/0.25 | f1-score
cut-ratio | 5,000 | 83,969 | 250 | 0.50/0.25/0.25 | f1-score
coreness | 5,000 | 118,785 | 221 | 0.50/0.25/0.25 | f1-score

## References

  * Adamic and Adar (2003) Lada A Adamic and Eytan Adar.  Friends and neighbors on the web.  _Social networks_ , 25(3):211–230, 2003.
  * Adhikari et al. (2018) Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B. Aditya Prakash.  Sub2vec: Feature learning for subgraphs.  In _Advances in Knowledge Discovery and Data Mining_ , volume 10938, pages 170–182. Springer, 2018.
  * Agarwal et al. (2006) Sameer Agarwal, Kristin Branson, and Serge J. Belongie.  Higher order learning with graphs.  In William W. Cohen and Andrew W. Moore, editors, _Machine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006_ , volume 148 of _ACM International Conference Proceeding Series_ , pages 17–24. ACM, 2006\.  doi: 10.1145/1143844.1143847.  URL https://doi.org/10.1145/1143844.1143847.
  * Alsentzer et al. (2020a) Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik.  Subgraph neural networks.  _Advances in Neural Information Processing Systems_ , 33:8017–8029, 2020a.
  * Alsentzer et al. (2020b) Emily Alsentzer, Samuel G Finlayson, Michelle M Li, and Marinka Zitnik.  Subgraph neural networks.  _arXiv preprint arXiv:2006.10538_ , 2020b.
  * Amer-Yahia et al. (2009) Sihem Amer-Yahia, Senjuti Basu Roy, Ashish Chawlat, Gautam Das, and Cong Yu.  Group recommendation: Semantics and efficiency.  _Proceedings of the VLDB Endowment_ , 2(1):754–765, 2009.
  * Azizian and Lelarge (2021) Waïss Azizian and Marc Lelarge.  Expressive power of invariant and equivariant graph neural networks.  In _International Conference on Learning Representations_ , 2021.
  * Babai and Kucera (1979) László Babai and Ludik Kucera.  Canonical labelling of graphs in linear average time.  In _20th Annual Symposium on Foundations of Computer Science (sfcs 1979)_ , pages 39–46. IEEE, 1979.
  * Barabási and Albert (1999) Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  _science_ , 286(5439):509–512, 1999.
  * Bennett et al. (2007) James Bennett, Stan Lanning, et al.  The netflix prize.  In _Proceedings of KDD cup and workshop_ , volume 2007, page 35. New York, 2007.
  * Bretto (2013) Alain Bretto.  _Hypergraph Theory_.  Springer International Publishing, 2013.
  * Bruna et al. (2013) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun.  Spectral networks and locally connected networks on graphs.  _arXiv preprint arXiv:1312.6203_ , 2013.
  * Chen et al. (2019) Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna.  On the equivalence between graph isomorphism testing and function approximation with gnns.  In _Advances in Neural Information Processing Systems_ , pages 15894–15902, 2019.
  * Chen et al. (2020) Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna.  Can graph neural networks count substructures?  In _Advances in Neural Information Processing Systems_ , 2020.
  * Dai et al. (2016) Hanjun Dai, Bo Dai, and Le Song.  Discriminative embeddings of latent variable models for structured data.  In _Proceedings of The 33rd International Conference on Machine Learning_ , pages 2702–2711, 2016.
  * Davey and Priestley (2002) Brian A. Davey and Hilary A. Priestley.  _Introduction to Lattices and Order, Second Edition_.  Cambridge University Press, 2002.  ISBN 978-0-521-78451-1.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  In _Advances in Neural Information Processing Systems_ , pages 3837–3845, 2016.
  * Duvenaud et al. (2015) David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams.  Convolutional networks on graphs for learning molecular fingerprints.  In _Advances in neural information processing systems_ , pages 2224–2232, 2015.
  * Feng et al. (2022) Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang.  How powerful are k-hop message passing graph neural networks.  _Advances in Neural Information Processing Systems_ , 2022.
  * Frasca et al. (2022) Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron.  Understanding and extending subgraph gnns by rethinking their symmetries.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Geerts (2020) Floris Geerts.  The expressive power of kth-order invariant graph networks.  _CoRR_ , abs/2007.12035, 2020.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 1263–1272. JMLR. org, 2017.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855–864. ACM, 2016.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In _Advances in Neural Information Processing Systems_ , pages 1025–1035, 2017.
  * He et al. (2022) Yixuan He, Xitong Zhang, Junjie Huang, Mihai Cucuringu, and Gesine Reinert.  Pytorch geometric signed directed: A survey and software on graph neural networks for signed and directed graphs.  _arXiv preprint arXiv:2202.10793_ , 2022.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  _arXiv preprint arXiv:2005.00687_ , 2020.
  * Kipf and Welling (2016a) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016a.
  * Kipf and Welling (2016b) Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016b.
  * Kreuzer et al. (2021) Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou.  Rethinking graph transformers with spectral attention.  In _Advances in Neural Information Processing Systems_ , pages 21618–21629, 2021.
  * Li et al. (2020) Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec.  Distance encoding–design provably more powerful gnns for structural representation learning.  _arXiv preprint arXiv:2009.00142_ , 2020.
  * Li et al. (2015) Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated graph sequence neural networks.  _arXiv preprint arXiv:1511.05493_ , 2015.
  * Liben-Nowell and Kleinberg (2007) David Liben-Nowell and Jon Kleinberg.  The link-prediction problem for social networks.  _Journal of the American society for information science and technology_ , 58(7):1019–1031, 2007.
  * Lim et al. (2022) Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess E. Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka.  Sign and basis invariant networks for spectral graph representation learning.  _CoRR_ , abs/2202.13013, 2022.
  * Liu et al. (2022) Yunyu Liu, Jianzhu Ma, and Pan Li.  Neural predicting higher-order patterns in temporal networks.  In _Proceedings of the ACM Web Conference 2022_ , pages 1340–1351, 2022.
  * Maron et al. (2019a) Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman.  Provably powerful graph networks.  In _Advances in Neural Information Processing Systems_ , pages 2156–2167, 2019a.
  * Maron et al. (2019b) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  In _International Conference on Learning Representations_ , 2019b.
  * McKay and Piperno (2014) Brendan D McKay and Adolfo Piperno.  Practical graph isomorphism, ii.  _Journal of Symbolic Computation_ , 60:94–112, 2014.
  * Morris et al. (2019) Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 4602–4609, 2019.
  * Nickel et al. (2015) Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich.  A review of relational machine learning for knowledge graphs.  _arXiv preprint arXiv:1503.00759_ , 2015.
  * Puny et al. (2022) Omri Puny, Matan Atzmon, Edward J. Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman.  Frame averaging for invariant and equivariant network design.  In _International Conference on Learning Representations_ , 2022.
  * Qi et al. (2006) Yanjun Qi, Ziv Bar-Joseph, and Judith Klein-Seetharaman.  Evaluation of different biological data and computational classification methods for use in protein interaction prediction.  _Proteins: Structure, Function, and Bioinformatics_ , 63(3):490–500, 2006.
  * Scarselli et al. (2009) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  _IEEE Transactions on Neural Networks_ , 20(1):61–80, 2009.
  * Srinivasan and Ribeiro (2020) Balasubramaniam Srinivasan and Bruno Ribeiro.  On the equivalence between positional node embeddings and structural graph representations.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=SJxzFySKwH.
  * Srinivasan et al. (2021) Balasubramaniam Srinivasan, Da Zheng, and George Karypis.  Learning over families of sets-hypergraph representation learning for higher order tasks.  In _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_ , pages 756–764. SIAM, 2021.
  * Stanfield et al. (2017) Zachary Stanfield, Mustafa Coşkun, and Mehmet Koyutürk.  Drug response prediction as a link prediction problem.  _Scientific reports_ , 7(1):1–13, 2017.
  * Teru et al. (2020) Komal Teru, Etienne Denis, and Will Hamilton.  Inductive relation prediction by subgraph reasoning.  In _International Conference on Machine Learning_ , pages 9448–9457. PMLR, 2020.
  * Tong et al. (2020a) Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David S. Rosenblum, and Andrew Lim.  Digraph inception convolutional networks.  In _Advances in Neural Information Processing Systems_ , 2020a.
  * Tong et al. (2020b) Zekun Tong, Yuxuan Liang, Changsheng Sun, David S. Rosenblum, and Andrew Lim.  Directed graph convolutional network.  _CoRR_ , abs/2004.13970, 2020b.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Wan et al. (2021) Changlin Wan, Muhan Zhang, Wei Hao, Sha Cao, Pan Li, and Chi Zhang.  Principled hyperedge prediction with structural spectral features and neural networks.  _arXiv preprint arXiv:2106.04292_ , 2021.
  * Wang et al. (2020) Sheng Wang, Emily R Flynn, and Russ B Altman.  Gaussian embedding for large-scale gene set analysis.  _Nature machine intelligence_ , 2(7):387–395, 2020.
  * Wang and Zhang (2022) Xiyuan Wang and Muhan Zhang.  GLASS: GNN with labeling tricks for subgraph representation learning.  In _International Conference on Learning Representations_ , 2022.
  * Weisfeiler and Lehman (1968) Boris Weisfeiler and AA Lehman.  A reduction of a graph to a canonical form and an algebra arising during this reduction.  _Nauchno-Technicheskaya Informatsia_ , 2(9):12–16, 1968.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Ying et al. (2018) Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  In _Advances in Neural Information Processing Systems_ , pages 4800–4810, 2018.
  * You et al. (2019) Jiaxuan You, Rex Ying, and Jure Leskovec.  Position-aware graph neural networks.  _arXiv preprint arXiv:1906.04817_ , 2019.
  * You et al. (2021) Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec.  Identity-aware graph neural networks.  _arXiv preprint arXiv:2101.10320_ , 2021.
  * Zhang and Chen (2018a) Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  In _Advances in Neural Information Processing Systems_ , pages 5165–5175, 2018a.
  * Zhang and Chen (2018b) Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  In _Advances in Neural Information Processing Systems_ , pages 5165–5175, 2018b.
  * Zhang and Chen (2020) Muhan Zhang and Yixin Chen.  Inductive matrix completion based on graph neural networks.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=ByxxgCEYDS.
  * Zhang and Li (2021) Muhan Zhang and Pan Li.  Nested graph neural networks.  In _Advances in Neural Information Processing Systems_ , pages 15734–15747, 2021.
  * Zhang et al. (2018a) Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen.  Beyond link prediction: Predicting hyperlinks in adjacency space.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018a.
  * Zhang et al. (2018b) Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen.  An end-to-end deep learning architecture for graph classification.  In _AAAI Conference on Artificial Intelligence_ , pages 4438–4445, 2018b.
  * Zhang et al. (2021a) Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin.  Labeling trick: A theory of using graph neural networks for multi-node representation learning.  _Advances in Neural Information Processing Systems_ , 34:9061–9073, 2021a.
  * Zhang et al. (2021b) Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn.  Magnet: A neural network for directed graphs.  _Advances in Neural Information Processing Systems_ , 34:27003–27015, 2021b.
  * Zhang et al. (2021c) Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew J. Hirn.  Magnet: A neural network for directed graphs.  In _Advances in Neural Information Processing Systems_ , pages 27003–27015, 2021c.
  * Zhou et al. (2009) Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang.  Predicting missing links via local information.  _The European Physical Journal B_ , 71(4):623–630, 2009.
  * Zhu et al. (2021) Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal A. C. Xhonneux, and Jian Tang.  Neural bellman-ford networks: A general graph neural network framework for link prediction.  In _Advances in Neural Information Processing Systems_ , pages 29476–29490, 2021.