Improving Graph Neural Networks on Multi-node Tasks with Labeling Tricks
In this paper, we provide a theory of using graph neural networks (GNNs) for
\textit{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 \text{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.
Xiyuan Wang, Pan Li, Muhan Zhang
# Improving Graph Neural Networks on Multi-node Tasks with Labeling Tricks

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

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, 2016; Defferrard et al., 2016; Dai et al., 2016;
Velickovic et al., 2017; Zhang et al., 2018; 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., 2020), 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., 2020), hyperedge (Zhang et al., 2018) 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, 2016) and SEAL (Zhang and Chen, 2018; Li et al., 2020). **GAE** and its variational version VGAE (Kipf and Welling, 2016) 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 1a, \(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.

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 0(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., 2020), representations aggregated from independently computed node representations will fail to differentiate nodes inside and outside the subgraph. Figure 0(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 0(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

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

### 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 \(\mathsf{A}\), denoted as \(\pi(\mathsf{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(\mathsf{A})_{\pi(i),\pi(j)}=\mathsf{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 \(\mathsf{A}\in\mathbb{R}^{n\times n\times d},\mathsf{A}^{\prime}\in\mathbb{R}^ {n^{\prime}\times n^{\prime}\times d^{\prime}}\) are **isomorphic** iff there exists \(\pi\in\Pi_{n}\), \(\pi(\mathsf{A})=\mathsf{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.

### 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. _Reflexivity._ \(\forall v\in U,v\leq_{S}v\)_._
2. _Antisymmetry._ \(\forall u,v\in U\)_, if_ \(u\leq_{S}v\) _and_ \(v\leq_{S}u\)_, then_ \(u=v\)_._
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.

\[\pi(\leq_{S})=\pi(\{(u,v)\ |\ (u,v)\in \leq_{S}\}) =\{(\pi(u),\pi(v))\ |\ (u,v)\in \leq_{S}\}, \tag{1}\] \[\pi(S)=\pi((U,\leq_{S})) =(\pi(U),\pi(\leq_{S})). \tag{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,\mathsf{A})\), \(\mathcal{G}^{\prime}=(V^{\prime},E^{\prime},\mathsf{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,\mathsf{A})\) and \((S^{\prime},\mathsf{A}^{\prime})\) are isomorphic (denoted by \((S,\mathsf{A})\simeq(S^{\prime},\mathsf{A}^{\prime})\)) iff \(\exists\pi\in\Pi_{n},S=\pi(S^{\prime})\) and \(\mathsf{A}=\pi(\mathsf{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,\boldsymbol{\mathsf{A}})\), \(\mathcal{G}^{\prime}=(V^{\prime},E^{\prime},\boldsymbol{\mathsf{A}}^{\prime})\), and two node sets \(S\subseteq V\), \(S^{\prime}\subseteq V^{\prime}\), we say substructures \((S,\boldsymbol{\mathsf{A}})\) and \((S^{\prime},\boldsymbol{\mathsf{A}}^{\prime})\) are isomorphic (denoted by \((S,\boldsymbol{\mathsf{A}})\simeq(S^{\prime},\boldsymbol{\mathsf{A}}^{\prime})\)) iff \(\exists\pi\in\Pi_{n},S=\pi(S^{\prime})\) and \(\boldsymbol{\mathsf{A}}=\pi(\boldsymbol{\mathsf{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 \(\boldsymbol{\mathsf{A}}=\boldsymbol{\mathsf{A}}^{\prime}\), where isomorphic node posets are defined **in the same graph**. For example, when \(S=\{i\},S^{\prime}=\{j\}\) and \((i,\boldsymbol{\mathsf{A}})\simeq(j,\boldsymbol{\mathsf{A}})\), we say nodes \(i\) and \(j\) are isomorphic in graph \(\boldsymbol{\mathsf{A}}\) (or they have symmetric positions/same structural role in graph \(\boldsymbol{\mathsf{A}}\)). An example is \(v_{2}\) and \(v_{3}\) in Figure 0(a). Similarly, edge and subgraph isomorphism can also be defined as the isomorphism of their node posets.

### 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,\boldsymbol{\mathsf{A}})\) is _permutation invariant_ (or _invariant_ for abbreviation) if \(\forall\pi\in\Pi_{n}\), \(f(S,\boldsymbol{\mathsf{A}})=f(\pi(S),\pi(\boldsymbol{\mathsf{A}}))\). Similarly, \(f\) is _permutation equivariant_ if \(\forall\pi\in\Pi_{n}\), \(\pi(f(S,\boldsymbol{\mathsf{A}}))=f(\pi(S),\pi(\boldsymbol{\mathsf{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,\boldsymbol{\mathsf{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,\boldsymbol{\mathsf{A}})\) is a **most expressive structural representation** for \((S,\boldsymbol{\mathsf{A}})\) if \(\forall S,\boldsymbol{\mathsf{A}},S^{\prime},\boldsymbol{\mathsf{A}}^{\prime},\ \Gamma(S,\boldsymbol{\mathsf{A}})=\Gamma(S^{\prime},\boldsymbol{\mathsf{A}}^{ \prime})\Leftrightarrow(S,\boldsymbol{\mathsf{A}})\simeq(S^{\prime}, \boldsymbol{\mathsf{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 \(\boldsymbol{\mathsf{A}}\) if it is clear from context. For a graph \(\boldsymbol{\mathsf{A}}\), we call \(\Gamma(\boldsymbol{\mathsf{A}})=\Gamma(\emptyset,\boldsymbol{\mathsf{A}})\) a _structural graph representation_, \(\Gamma(i,\boldsymbol{\mathsf{A}})\) a _structural node representation_ for node \(i\), and call \(\Gamma(\{i,j\},\boldsymbol{\mathsf{A}})\) a _structural link representation_ for link \((i,j)\). For a general node poset \(S\), we call \(\Gamma(S,\boldsymbol{\mathsf{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.

### GAE for multi-node representation

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

\[\boldsymbol{\hat{A}}_{i,j}=\text{sigmoid}(\boldsymbol{z}_{i}^{\top} \boldsymbol{z}_{j}),\text{ where }\boldsymbol{z}_{i}\!=\!\text{GNN}(i, \boldsymbol{\mathsf{A}}),\boldsymbol{z}_{j}\!=\!\text{GNN}(j,\boldsymbol{ \mathsf{A}}).\]

Here \(\boldsymbol{\hat{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:

\[\boldsymbol{z}_{S}=\text{MLP}(\text{AGG}(\{\boldsymbol{z}_{i}|i\in S\})) \text{ where }\boldsymbol{z}_{i}\!=\!\text{GNN}(i,\boldsymbol{\mathsf{A}}), \tag{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.

### 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,\boldsymbol{\mathsf{A}}\!,\!j,\boldsymbol{\mathsf{A}}^{\prime},\)\(GNN(i,\boldsymbol{\mathsf{A}})=\text{GNN}(j,\boldsymbol{\mathsf{A}}^{\prime}) \Leftrightarrow(i,\boldsymbol{\mathsf{A}})\simeq(j,\boldsymbol{\mathsf{A}}^{ \prime}).\)_
NME GNN learns _structural node representations_1. 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.

Footnote 1: Although 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.

### 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 0(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 0(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).

### Definition of set labeling trick

The set labeling trick is defined as follows.

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

1. _(target-nodes-distinguishing)_ \(\mathsf{L}(S,\mathsf{A})=\pi(\mathsf{L}(S^{\prime},\mathsf{A}^{\prime})) \Rightarrow S=\pi(S^{\prime})\)_._
2. _(permutation equivariance)_ \(S=\pi(S^{\prime}),\mathsf{A}=\pi(\mathsf{A}^{\prime})\Rightarrow\mathsf{L}( S,\mathsf{A})=\pi(\mathsf{L}(S^{\prime},\mathsf{A}^{\prime}))\)_._
To explain a bit, labeling trick assigns a label vector to each node/edge in graph \(\mathsf{A}\), which constitutes the labeling tensor \(\mathsf{L}(S,\mathsf{A})\). By concatenating \(\mathsf{A}\) and \(\mathsf{L}(S,\mathsf{A})\), we get the new labeled graph \(\mathsf{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 \(\mathsf{L}(S,\mathsf{A})_{i,j,:},i\neq j\) be all zero.

The labeling tensor \(\mathsf{L}(S,\mathsf{A})\) should satisfy two properties in Definition 9. Property 1 requires that if a permutation \(\pi\) preserving node labels (i.e., \(\mathsf{L}(S,\mathsf{A})=\pi(\mathsf{L}(S^{\prime},\mathsf{A}^{\prime}))\)) exists between nodes of \(\mathsf{A}\) and \(\mathsf{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,\mathsf{A})\) and \((S^{\prime},\mathsf{A}^{\prime})\) are isomorphic under \(\pi\) (i.e., \(S=\pi(S^{\prime}),\mathsf{A}=\pi(\mathsf{A}^{\prime})\)), the corresponding nodes \(i\in S,j\in S^{\prime},i=\pi(j)\) must always have the same label (i.e., \(\mathsf{L}(S,\mathsf{A})=\pi(\mathsf{L}(S^{\prime},\mathsf{A}^{\prime}))\)). A sufficient condition for property 2 is to make the labeling function _permutation equivariant_, i.e., when the target \((S,\mathsf{A})\) changes to \((\pi(S),\pi(\mathsf{A}))\), the labeling tensor \(\mathsf{L}(\pi(S),\pi(\mathsf{A}))\) should equivariantly change to \(\pi(\mathsf{L}(S,\mathsf{A}))\).

### 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 \(\mathsf{A}\) and a set of nodes \(S\) to predict, we give it a diagonal labeling matrix \(\mathsf{L}_{zo}(S,\mathsf{A})\in\mathbb{R}^{n\times n\times 1}\) such that_

\[\mathsf{L}_{zo}(S,\mathsf{A})_{i,i,1}=\begin{cases}1&\text{if }i\in S\\ 0&\text{otherwise}\end{cases}. \tag{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 0(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.
### 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 \(\mathbf{A}\) and \(S^{\prime}\) in graph \(\mathbf{A}^{\prime}\), given a set labeling trick, \((S,\mathbf{A})\simeq(S^{\prime},\mathbf{A}^{\prime})\Leftrightarrow\mathbf{A} ^{(S)}\simeq\mathbf{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,\mathbf{A},S^{\prime},\mathbf{A}^{\prime}\), \(\text{GNN}(S,\mathbf{A}^{(S)})=\text{GNN}(S^{\prime},\mathbf{A}^{\prime(S^{ \prime})})\Leftrightarrow(S,\mathbf{A})\simeq(S^{\prime},\mathbf{A}^{\prime})\), where \(\text{GNN}(S,\mathbf{A}^{(S)}):=\text{AGG}(\{\text{GNN}(i,\mathbf{A}^{(S)})|i \in S\})\)._

Remember that directly aggregating the structural node representations learned from the original graph \(\mathbf{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 \(\mathbf{A}^{(S)}\), somewhat surprisingly, results in a structural representation for \((S,\mathbf{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

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})\).
\(\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 1a) 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,_

\[h(\{i,j\},\mathbf{\mathsf{A}})=f\big{(}\big{\{}\sum_{v\in N(i)}g_{2 }(\mbox{deg}(v,\mathbf{\mathsf{A}})),\sum_{v\in N(j)}g_{2}(\mbox{deg} (v,\mathbf{\mathsf{A}}))\big{\}},\hskip-14.226378pt\sum_{v\in N(i) \bigcap N(j)}\hskip-14.226378ptg_{1}(\mbox{deg}(v,\mathbf{\mathsf{A}})) \big{)}, \tag{5}\]

_where \(\mbox{deg}(v,\mathbf{\mathsf{A}})\) is the degree of node \(v\) in graph \(\mathsf{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) (Barabasi 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) illustrates 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.

### 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 \(\mathsf{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.

## 5 Labeling trick for poset

The previous section describes multi-node substructures \((S,\mathbf{\mathsf{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 \(\mathsf{A}\) already allows directed edges in our definition.

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

1. _(target-nodes-and-order-distinguishing)_ \(\mathsf{L}(S,\mathsf{A})=\pi(\mathsf{L}(S^{\prime},\mathsf{A}))\Rightarrow S =\pi(S^{\prime})\)_._
2. _(permutation equivariance)_ \(S=\pi(S^{\prime}),\mathsf{A}=\pi(\mathsf{A}^{\prime})\Rightarrow\mathsf{L}( S,\mathsf{A})=\pi(\mathsf{L}(S^{\prime},\mathsf{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 \(\mathsf{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.

### 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 3: Set labeling trick cannot differentiate directed links between the same nodes.
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 \(\mathbf{L}\) be the labeling function of a poset labeling trick. If \(\exists\pi\in\Pi_{n},\mathbf{L}(S,\mathbf{A})=\pi(\mathbf{L}(S^{\prime},\mathbf{ 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_

\[\mathbf{L}(S,\mathbf{A})_{u,u,:}=\begin{cases}\text{sigmoid}(\text{GNN}(u, \mathcal{H}_{S}))&\text{if }u\in S\\ 0&\text{otherwise}\end{cases} \tag{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.

### 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 \(\mathsf{A}\) and \(S^{\prime}\) in graph \(\mathsf{A}^{\prime}\), given a set labeling trick, \((S,\mathsf{A})\simeq(S^{\prime},\mathsf{A}^{\prime})\Leftrightarrow\mathsf{A} ^{(S)}\simeq\mathsf{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 \(\mathsf{A},\mathsf{A}^{\prime}\), \(\mbox{GNN}(S,\mathsf{A}^{(S)})=\mbox{GNN}(S^{\prime},\mathsf{A}^{\prime(S^{ \prime})})\Leftrightarrow(S,\mathsf{A})\simeq(S^{\prime},\mathsf{A}^{\prime})\), where \(\mbox{GNN}(S,\mathsf{A}^{(S)})=\mbox{AGG}(\{\mbox{GNN}(u,\mathsf{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 \(\left((1-\epsilon)\log n\right)^{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.
### Subset labeling trick

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

1. _(target-subset-distinguishing)_ \(\mathsf{L}(P,\mathsf{A})=\pi(\mathsf{L}(P^{\prime},\mathsf{A}^{\prime})) \Rightarrow P=\pi(P^{\prime})\)_._
2. _(permutation equivariance)_ \(P=\pi(P^{\prime}),\mathsf{A}=\pi(\mathsf{A}^{\prime})\Rightarrow\mathsf{L}(P,\mathsf{A})=\pi(\mathsf{L}(P^{\prime},\mathsf{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 \(\mathsf{A}\), a set of nodes \(S\) to predict, and a subset \(P\subseteq S\), we give it a diagonal labeling matrix \(\mathsf{L}(P,\mathsf{A})\in\mathbb{R}^{n\times n\times 1}\) such that \(\mathsf{L}(P,\mathsf{A})_{i,i,1}=1\) if \(i\in P\) and \(\mathsf{L}(P,\mathsf{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.

### How to select subset

Subset poolingID-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,\mathsf{A}^{(P)})|P\subseteq S,|P|=k\}), \tag{7}\]

where AGG is an injective set aggregation function.

As for all \(\pi\in\Pi_{n}\) and target node set \(S\) in graph \(\mathsf{A}\),

\[\text{AGG}(\{\text{GNN}(S,\mathsf{A}^{(P)})|P\!\subseteq\!S,|P|\!=\!k\})= \text{AGG}(\{\text{GNN}(\pi(S),\pi(\mathsf{A})^{(P)}|P\!\subseteq\!\pi(S),|P| \!=\!k\}), \tag{8}\]

the subset pooling routine keeps permutation equivariance.

One head routineContrary 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.

### 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 \(\mathbf{A},\mathbf{A}^{\prime}\), and node sets \(S,S^{\prime}\) in \(\mathbf{A},\mathbf{A}^{\prime}\) respectively, we have_

\[\text{AGG}(\{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
**Theorem 26**: _Given an NME GNN, for any graph \(\mathbf{A},\mathbf{A}^{\prime}\), and node sets \(S,S^{\prime}\) in \(\mathbf{A},\mathbf{A}^{\prime}\) respectively, we have_

\[(S,\mathbf{A})\!\not\simeq\!(S^{\prime},\mathbf{A}^{\prime})\Rightarrow \forall P\subseteq S,P^{\prime}\subseteq S^{\prime},|P|=|S|-1,|P^{\prime}|=|S ^{\prime}|-1,\\ \text{GNN}(S,\mathbf{A}^{(P)})\neq\text{GNN}(S,\mathbf{A}^{\prime (P^{\prime})}). \tag{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, \(\text{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 \(\mathbf{A}\) and set \(S^{\prime}\) in graph \(\mathbf{A}^{\prime}\) such that \(\text{AGG}(\{\text{GNN}(u,\mathbf{A}^{(u)})|u\in S\})=\text{AGG}(\{\text{GNN} (u^{\prime},\mathbf{A}^{\prime(u^{\prime})})|u^{\prime}\in S^{\prime}\})\) while \((S,\mathbf{A})\!\not\simeq\!(S^{\prime},\mathbf{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,\mathbf{A},S^{\prime},\mathbf{A}^{\prime}\) such that \((S,\mathbf{A})\not\simeq(S^{\prime},\mathbf{A}^{\prime})\), \(\text{AGG}(\{\text{GNN}(u,\mathbf{A}^{(u)})|u\in S\})\neq\text{AGG}(\{\text{ GNN}(u^{\prime},\mathbf{A}^{\prime(u^{\prime})})|u^{\prime}\in S^{\prime}\})\) while \(\text{GNN}(S,\mathbf{A}^{S})=\text{GNN}(S^{\prime},\mathbf{A}^{\prime(S^{ \prime})})\). There also exists \(S,\mathbf{A},S^{\prime},\mathbf{A}^{\prime}\) such that \((S,\mathbf{A})\!\not\simeq\!(S^{\prime},\mathbf{A}^{\prime})\), \(\text{AGG}(\{\text{GNN}(u,\mathbf{A}^{(u)})|u\in S\})=\text{AGG}(\{\text{GNN} (u^{\prime},\mathbf{A}^{\prime(u^{\prime})})|u^{\prime}\in S^{\prime}\})\) while \(\text{GNN}(S,\mathbf{A}^{(S)})\neq\text{GNN}(S^{\prime},\mathbf{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.

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,

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\).
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,\mathbf{H},\mathbf{\mathsf{X}}^{V},\mathbf{\mathsf{X}}^{E})\), where \(V\) is the node set \(\{1,2,...,n\}\), \(E\) is the hyperedge set \(\{1,2,...,m\}\), and \(\mathbf{H}\in\{0,1\}^{n\times m}\) is the incidence matrix with \(\mathbf{H}_{i,j}=1\) if node \(i\) is in hyperedge \(j\) and \(0\) otherwise. Each hyperedge contains at least one node. \(\mathbf{\mathsf{X}}^{V}\in\mathbb{R}^{n\times d}\) and \(\mathbf{\mathsf{X}}^{E}\in\mathbb{R}^{m\times d}\) are node and hyperedge features respectively, where \(\mathbf{\mathsf{X}}^{V}_{i,:}\) is of node \(i\), and \(\mathbf{\mathsf{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,\mathbf{H},\mathbf{\mathsf{X}}^{V},\mathbf{\mathsf{X}}^{E})\) is \(\pi(H)=(\pi_{1}(V),\pi_{2}(E),\pi(\mathbf{H}),\pi_{1}(\mathbf{\mathsf{X}}^{V}),\pi_{2} (\mathbf{\mathsf{X}}^{E}))\), where incidence matrix permutation is \(\pi(\mathbf{H})_{\pi_{1}(i),\pi_{2}(j)}=\mathbf{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,\mathbf{H},\mathbf{\mathsf{X}}^{V},\mathbf{\mathsf{X}}^{E})\), \(V=\{1,2,...,n\}\), \(E=\{1,2,...,m\}\), \(\mathbf{H}\in\{0,1\}^{n\times m}\), \(\mathbf{\mathsf{X}}^{V}\in\mathbb{R}^{n\times d}\),\(\mathbf{\mathsf{X}}^{E}\in\mathbb{R}^{m\times d}\), its incidence graph is \(IG_{H}=(V_{H},E_{H},\mathbf{\mathsf{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,\mathbf{H}_{i,j}=1\}\), adjacency tensor \(\mathbf{\mathsf{A}}\in\mathbb{R}^{(n+m)\times(n+m)\times(d+1)}\). For all \(i\in V,j\in E\), \(\mathbf{\mathsf{A}}_{i,i,:d}=\mathbf{\mathsf{X}}^{V}_{i,:}\), \(\mathbf{\mathsf{A}}_{i,i,d+1}=\mathbf{\mathsf{X}}^{V}_{i,:}\), \(\mathbf{\mathsf{A}}_{n+j,n+j,:d}=\mathbf{\mathsf{X}}^{E}_{j,:}\), \(\mathbf{\mathsf{A}}_{i,n+j,d+1}=\mathbf{H}_{i,j}\). All other elements in \(\mathbf{\mathsf{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 \(\mathbf{\mathsf{A}},\mathbf{\mathsf{A}}^{\prime}\) denote the adjacency tensors of graphs \(IG_{H},IG_{H^{\prime}}\) respectively. Then \(\text{GNN}(S,\mathbf{\mathsf{A}}^{(S)})=\text{GNN}(S^{\prime},\mathbf{\mathsf{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., 2019; Chen et al., 2019; Azizian and Lelarge, 2021), approximating permutation equivariant functions (Maron et al., 2019; Geerts, 2020; Maron et al., 2019; 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, 2016; 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., 2021), various forms of specific labeling tricks have already been used in previous works. To our best knowledge, SEAL (Zhang and Chen, 2018) 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.

### 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, 2018), 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, 2018). 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.

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.

### 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., 2020), DiGCN and DiGCNIB (Tong et al., 2020), and MagNet (Zhang et al., 2021). 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., 2021) 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.

### 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 (fam

\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & USAir & NS & PB & Yeast & Cele & Power & Router & Ecoli \\ \hline 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}\) & \(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 3.44}\) & \(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}\) \\ \hline 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}\) \\ \hline 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.0_{\pm 0.34}}\) & \(97.20_{\pm 0.64}\) & \(86.54_{\pm 2.04}\) & \(84.18_{\pm 1.82}\) & \(95.68_{\pm 1.22}\) & \(97.22_{\pm 0.28}\) \\ \hline SZO & \(96.15_{\pm 1.06}\) & \(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}\) & \(97.48_{\pm 0.23}\) \\ SDE & \(94.97_{\pm 0.61}\) & \(\mathbf{99.29_{\pm 0.14}}\) & \(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}\) & \(97.46_{\pm 0.06}\) & \(\mathbf{88.04_{\pm 0.52}}\) & \(84.95_{\pm 0.30}\) & \(93.77_{\pm 0.20}\) & \(95.53_{\pm 0.62}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Results on undirected link prediction task: auroc (%) \(\pm\) standard deviation.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Dataset & collab & ddi & citation2 & ppa \\ \hline metrics & Hits@50 & Hits@20 & MRR & Hits@100 \\ \hline SZO & \(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}\) & \(37.07_{\pm 5.07}\) & \(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}\) & \(43.27_{\pm 1.19}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Results on undirected link prediction task.
ily 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.

### Subgraph prediction task

We use the datasets and baselines in (Alsentzer et al., 2020). We use three synthetic datasets, namely density, coreness, and cutratio. SubGNN (Alsentzer et al., 2020) 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

\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & NDC-c & NDC-s & tags-m & tags-a & email-Enemail-EU & congress \\ \hline 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 & \(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}\) \\ \hline 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}\) \\ \hline 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}}\) & \(66.1_{\pm 1.2}\) & \(72.1_{\pm 1.1}\) & \(\mathbf{65.1_{\pm 0.2}}\) \\ SZO & \(75.8_{\pm 0.7}\) & \(62.2_{\pm 1.2}\) & \(71.0_{\pm 0.4}\) & \(69.6_{\pm 0.7}\) & \(\mathbf{67.7_{\pm 1.8}}\) & \(\mathbf{73.3_{\pm 0.5}}\) & \(64.2_{\pm 0.3}\) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Results on hyperedge prediction tasks: f1-score (%) \(\pm\) standard deviation.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Method & density & coreness & cutratio \\ \hline 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}\) \\ \hline \hline \end{tabular}
\end{table}
Table 5: Results on subgraph tasks: f1-score (%) \(\pm\) standard deviation.
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.
## Appendix A Proofs

### Proof of Theorem 12

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

We need to show \(\operatorname{AGG}(\{\operatorname{GNN}(i,\boldsymbol{\mathsf{A}}^{(S)})|i \in S\})=\operatorname{AGG}(\{\operatorname{GNN}(i,\boldsymbol{\mathsf{A}}^{ \prime(S^{\prime})}|i\in S^{\prime}\})\Leftrightarrow(S,\boldsymbol{\mathsf{ A}})\simeq(S^{\prime},\boldsymbol{\mathsf{A}}^{\prime})\).

To prove \(\Rightarrow\), we notice that with an injective \(\operatorname{AGG}\),

\[\operatorname{AGG}(\{\operatorname{GNN}(i,\boldsymbol{\mathsf{A}}^{(S)}) )|i\in S\})=\operatorname{AGG}(\{\operatorname{GNN}(i,\boldsymbol{\mathsf{A}} ^{\prime(S^{\prime})}))|i\in S^{\prime}\})\] \[\implies\exists\ v_{1}\in S,v_{2}\in S^{\prime},\ \text{such that}\ \operatorname{GNN}(v_{1},\boldsymbol{\mathsf{A}}^{(S)})=\operatorname{GNN}(v_{2},\boldsymbol{\mathsf{A}}^{\prime(S^{\prime})}) \tag{11}\] \[\implies(v_{1},\boldsymbol{\mathsf{A}}^{(S)})\simeq(v_{2}, \boldsymbol{\mathsf{A}}^{\prime(S^{\prime})})\ \ \ \ (\text{because GNN is node- most-expressive})\] (12) \[\implies\exists\ \pi\in\Pi_{n},\ \text{such that}\ v_{1}=\pi(v_{2}), \boldsymbol{\mathsf{A}}^{(S)}=\pi(\boldsymbol{\mathsf{A}}^{\prime(S^{\prime})}). \tag{13}\]

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

\[\boldsymbol{\mathsf{A}}=\pi(\boldsymbol{\mathsf{A}}^{\prime}),\ \boldsymbol{\mathsf{L}}(S,\boldsymbol{\mathsf{A}})=\pi( \boldsymbol{\mathsf{L}}(S^{\prime},\boldsymbol{\mathsf{A}}^{\prime})).\]

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

\[\operatorname{AGG}(\{\operatorname{GNN}(i,\boldsymbol{\mathsf{A}} ^{(S)})|i\in S\})=\operatorname{AGG}(\{\operatorname{GNN}(i,\boldsymbol{ \mathsf{A}}^{\prime(S^{\prime})})|i\in S^{\prime}\})\] \[\implies\exists\ \pi\in\Pi_{n},\ \text{such that}\ \boldsymbol{\mathsf{A}}=\pi( \boldsymbol{\mathsf{A}}^{\prime}),\ \boldsymbol{\mathsf{L}}(S,\boldsymbol{\mathsf{A}})=\pi( \boldsymbol{\mathsf{L}}(S^{\prime},\boldsymbol{\mathsf{A}}^{\prime})) \tag{14}\] \[\implies\exists\ \pi\in\Pi_{n},\ \text{such that}\ \boldsymbol{\mathsf{A}}=\pi( \boldsymbol{\mathsf{A}}^{\prime}),\ S=\pi(S^{\prime})\] (15) \[\implies(S,\boldsymbol{\mathsf{A}})\simeq(S^{\prime}, \boldsymbol{\mathsf{A}}^{\prime}). \tag{16}\]

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

\[(S,\boldsymbol{\mathsf{A}})\simeq(S^{\prime},\boldsymbol{\mathsf{A}}^{ \prime})\] \[\implies\exists\ \pi\in\Pi_{n},\ \text{such that}\ S=\pi(S^{\prime}), \boldsymbol{\mathsf{A}}=\pi(\boldsymbol{\mathsf{A}}^{\prime}) \tag{17}\] \[\implies\exists\ \pi\in\Pi_{n},\ \text{such that}\ S=\pi(S^{\prime}), \boldsymbol{\mathsf{A}}=\pi(\boldsymbol{\mathsf{A}}^{\prime}),\boldsymbol{ \mathsf{L}}(S,\boldsymbol{\mathsf{A}})=\pi(\boldsymbol{\mathsf{L}}(S^{\prime}, \boldsymbol{\mathsf{A}}^{\prime}))\] (18) \[\implies\exists\ \pi\in\Pi_{n},\ \text{such that}\ S=\pi(S^{\prime}), \boldsymbol{\mathsf{A}}^{(S)}=\pi(\boldsymbol{\mathsf{A}}^{\prime(S^{\prime})})\] (19) \[\implies\exists\ \pi\in\Pi_{n},\ \text{such that}\ \forall v_{2}\in S^{\prime},v_{1}=\pi(v_{2})\in S, \operatorname{GNN}(v_{1},\boldsymbol{\mathsf{A}}^{(S)})=\operatorname{GNN}(v_{2},\boldsymbol{\mathsf{A}}^{\prime(S^{\prime})})\] (20) \[\implies\operatorname{AGG}(\{\operatorname{GNN}(v_{1}, \boldsymbol{\mathsf{A}}^{(S)})|v_{1}\in S\})=\operatorname{AGG}(\{ \operatorname{GNN}(v_{2},\boldsymbol{\mathsf{A}}^{\prime(S^{\prime})})|v_{2} \in S^{\prime}\}), \tag{21}\]

which concludes the proof.

### 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,\mathbf{\mathsf{A}},S^{\prime},\mathbf{\mathsf{A}}^{\prime}\), \((S,\mathbf{\mathsf{A}})\) and \((S^{\prime},\mathbf{\mathsf{A}}^{\prime})\) are locally \(h\)-isomorphic iff \((S,\mathbf{\mathsf{A}}_{S,h})\simeq(S^{\prime},\mathbf{ \mathsf{A}}_{S^{\prime},h})\), where \(\mathbf{\mathsf{A}}_{S,h}\) means the subgraph of \(\mathsf{A}\) induced by the node set \(\{v\in V|\exists u\in S,d_{\mathit{sp}}(u,v,\mathbf{\mathsf{A}})\leq h\}\), and \(d_{\mathit{sp}}(u,v,\mathbf{\mathsf{A}})\) means the shortest path distance between node \(u,v\) in graph \(\mathsf{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\left((1-\epsilon)\log n\right)^{1/(2h+2)}\), then the number of nodes in \(G_{v}^{(h)}\), denoted by \(|V(G_{v}^{(h)})|\), satisfies

\[|V(G_{v}^{(h)})|\leq\sum_{i=0}^{h}d^{i}\leq d^{h+1}=\left((1-\epsilon)\log n \right)^{1/2}.\]

We set \(K=\max_{v\in V}|V(G_{v}^{(h)})|\) and thus \(K\leq\left((1-\epsilon)\log n\right)^{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^{\binom{K}{2}}\leq 2^{(1-\epsilon)\log n}=n^{1-\epsilon}. \tag{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_{\mathit{iso}}\), which consist of nodes that are all locally \(h\)-isomorphic to each other.

**Step 2.** Let us partition \(V_{\mathit{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:

\[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]. \tag{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

\[1\leq|V_{i}|\leq d_{w}\leq\left((1-\epsilon)\log n\right)^{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

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

which concludes the proof. 

### 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 }). \tag{24}\]

\(\blacksquare\)

### 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
\(\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{)}. \tag{25}\]

### Proof of Proposition 14

As shown in Figure 0(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 \(\blacktriangle\) 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}. \tag{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} \tag{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} \tag{28}\]

The pooling layer is

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

### Proof of Theorem 21

**Proof**\(\Leftarrow\): When \((S,\blacktriangle)\simeq(S^{\prime},\blacktriangle^{\prime})\), there exists a permutation \(\pi\), \(\pi(S)=S^{\prime},\pi(\blacktriangle)=\blacktriangle^{\prime}\).
\[\mathrm{GNN}(S,\mathbf{\mathsf{A}}^{(S)}) =\mathrm{AGG}(\{\mathrm{GNN}(v,\mathbf{\mathsf{A}}^{(S)}|v \in S\}) \tag{30}\] \[=\mathrm{AGG}(\{\mathrm{GNN}(\pi(v),\pi(\mathbf{\mathsf{A}$ }^{(S)}))|v\in S\})\] (31) \[=\mathrm{AGG}(\{\mathrm{GNN}(\pi(v),\mbox{\boldmath$\mathsf{A}}^ {\prime(S^{\prime})}|v\in S\})\] (32) \[=\mathrm{AGG}(\{\mathrm{GNN}(v^{\prime},\mathbf{\mathsf{ A}}^{\prime(S^{\prime})})|v^{\prime}\in S^{\prime}\})\] (33) \[=\mathrm{GNN}(S^{\prime},\mathbf{\mathsf{A}}^{\prime(S^{ \prime})})\] (34) \[\Rightarrow:\] \[\mathrm{GNN}(S,\mathbf{\mathsf{A}}^{(S)})=\mathrm{GNN}(S^{ \prime},\mathbf{\mathsf{A}}^{\prime(S^{\prime})}) \tag{35}\]

\[\mathrm{AGG}(\{\mathrm{GNN}(v,\mathbf{\mathsf{A}}^{(S)})|v\in S\}) =\mathrm{AGG}(\{\mathrm{GNN}(v^{\prime},\mathbf{\mathsf{A}}^{\prime (S^{\prime})})|v^{\prime}\in S^{\prime}\}) \tag{36}\]

As \(\mathrm{AGG}\) is injective, There exist \(v_{0}\in S,v_{0}^{\prime}\in S^{\prime}\),

\[\mathrm{GNN}(v_{0},\mathbf{\mathsf{A}}^{(S)})=\mathrm{GNN}(v_{0}^{ \prime},\mathbf{\mathsf{A}}^{(S^{\prime})}) \tag{37}\]

As \(\mathrm{GNN}\) is node most expressive,

\[\exists\pi,\pi(v_{0})=v_{0}^{\prime},\pi(\mathbf{\mathsf{A}})=\mathbf{\mathsf{A}}^{\prime},\pi(\mathbf{\mathsf{L}}(S,\mathbf{\mathsf{A}}))=\mathbf{\mathsf{L}}(S^{\prime},\mathbf{\mathsf{A}}^{\prime}).\]

Therefore, \(\pi(\mathbf{\mathsf{L}}(S,\mathbf{\mathsf{A}}))=\mathbf{\mathsf{L}}(S^{\prime},\mathbf{\mathsf{A}}^{\prime}))\).

### Proof of Theorem 25

**Proof**\(\Leftarrow\): When \((S,\mathbf{\mathsf{A}})\simeq(S^{\prime},\mathbf{\mathsf{A}}^ {\prime})\), there exists a permutation \(\pi\), \(\pi(S)=S^{\prime},\pi(\mathbf{\mathsf{A}})=\mathbf{\mathsf{A }}^{\prime}\).

\[\mathrm{AGG}\left(\left\{\mathrm{AGG}(\{\mathrm{GNN}(u,\mathbf{\mathsf{A}}^{(S-\{v\})})|u\in S\})|v\in S\right\}\right) \tag{38}\] \[=\mathrm{AGG}(\{\mathrm{AGG}(\{\mathrm{GNN}(\pi(u),\pi(\mathbf{\mathsf{A}}^{(S-\{v\})})|u\in S\})|v\in S\})\] (39) \[=\mathrm{AGG}(\{\mathrm{AGG}(\{\mathrm{GNN}(\pi(u),\mathbf{\mathsf{A}}^{\prime(\pi(S)-\{\pi(v)\})}|u\in S\})|v\in S\})\] (40) \[=\mathrm{AGG}(\{\mathrm{AGG}(\{\mathrm{GNN}(u^{\prime},\mathbf{\mathsf{A}}^{(S^{\prime}-\{v^{\prime}\})})|u^{\prime}\in S^{\prime}\})| v^{\prime}\in S^{\prime}\})\] (41) \[\Rightarrow:\] \[\mathrm{AGG}(\{\mathrm{AGG}(\{\mathrm{GNN}(u,\mathbf{ \mathsf{A}}^{(S-\{v\})})|u\in S\})|v\in S\})\] \[=\mathrm{AGG}(\{\mathrm{AGG}(\{\mathrm{GNN}(u^{\prime},\mathbf{\mathsf{A}}^{\prime(S^{\prime}-\{v^{\prime}\})})|u^{\prime}\in S^{ \prime}\})|v^{\prime}\in S^{\prime}\}).\]

As \(\mathrm{AGG}\) is injective,

\[\{\mathrm{AGG}(\{\mathrm{GNN}(u,\mathbf{\mathsf{A}}^{(S-\{v\})})|v \in S\})|u\in S\}=\{\{\mathrm{AGG}(\{\mathrm{GNN}(u^{\prime},\mathbf{ \mathsf{A}}^{(S^{\prime}-\{v^{\prime}\})})|v^{\prime}\in S^{\prime}\})\}. \tag{42}\]

There exist \(v_{0}\in S,v_{0}^{\prime}\in S^{\prime}\),

\[\mathrm{AGG}(\{\mathrm{GNN}(u,\mathbf{\mathsf{A}}^{(S-\{v_{0}\})})|u \in S\})=\mathrm{AGG}(\{\mathrm{GNN}(u^{\prime},\mathbf{\mathsf{A}}^{( S^{\prime}-\{v_{0}^{\prime}\})})|u^{\prime}\in S^{\prime}\}). \tag{43}\]

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

\[\mathrm{GNN}(v_{0},\mathbf{\mathsf{A}}^{(S-\{v_{0}\})})=\mathrm{GNN}(u_ {0}^{\prime},\mathbf{\mathsf{A}}^{(S^{\prime}-\{v_{0}^{\prime}\})}). \tag{44}\]
As GNN is node most expressive,

\[\exists\pi,\pi(v_{0})=u^{\prime}_{0},\pi(\textbf{A})=\textbf{A}^{\prime},\pi( \textbf{L}(S-\{v_{0}\},\textbf{A}))=\textbf{L}(S^{\prime}-\{v^{\prime}_{0}\}, \textbf{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(\textbf{A})=\textbf{A}^{\prime}\), so \((S,\textbf{A})\simeq(S^{\prime},\textbf{A}^{\prime})\).

### Proof of Theorem 26

We prove it by contradiction: If \(\exists v_{0}\in S,v^{\prime}_{0}\in S^{\prime}\),

\[\operatorname{GNN}(S,\textbf{A}^{(S-\{v_{0}\})})=\operatorname{GNN}(S^{\prime },\textbf{A}^{\prime(S^{\prime}-\{v^{\prime}_{0}\})}) \tag{45}\]

Therefore, there exists \(u_{0}\in S,u^{\prime}_{0}\in S^{\prime}\)

\[\operatorname{GNN}(v_{0},\textbf{A}^{(S-\{v_{0}\})})=\operatorname{GNN}(u^{ \prime}_{0},\textbf{A}^{(S^{\prime}-\{v^{\prime}_{0}\})}). \tag{46}\]

As GNN is node most expressive,

\[\exists\pi,\pi(v_{0})=u^{\prime}_{0},\pi(\textbf{A})=\textbf{A}^{\prime},\pi( \textbf{L}(S-\{v_{0}\},\textbf{A}))=\textbf{L}(S^{\prime}-\{v^{\prime}_{0}\},\textbf{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(\textbf{A})=\textbf{A}^{\prime}\), so \((S,\textbf{A})\simeq(S^{\prime},\textbf{A}^{\prime})\), which contradicts to that \((S,\textbf{A})\not\simeq(S^{\prime},\textbf{A}^{\prime})\).

### Proof of Proposition 18

Due to the property 1 in Definition 16, \(\textbf{L}(S,\textbf{A})=\pi(\textbf{L}(S^{\prime},\textbf{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 \(\textbf{L}(S,\textbf{A})_{u,u,:}=\textbf{L}(S,\textbf{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}. \tag{47}\]

\(\pi(\textbf{L}(S,\textbf{A}))=\textbf{L}(S,\textbf{A})\Rightarrow\pi(S)=S \Rightarrow(v,\mathcal{H}_{S})\simeq(u,\mathcal{H}_{S})\). Equivalently, non-isomorphic nodes in the same hase diagram should have different labels.
### 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} \tag{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}})) \tag{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 \(\textbf{A},\textbf{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,

\[\textbf{A}=\pi_{0}(\textbf{A}^{\prime})\Rightarrow\textbf{A}_{\pi_{0}(i),\pi_ {0}(i),d+1}=\textbf{A}^{\prime}_{i,i,d+1},\forall i\in\{1,2,...,m+n\}. \tag{50}\]

As the nodes in \(\textbf{A},\textbf{A}^{\prime}\) are sorted, \(\textbf{A}_{i,i,d+1}=1,\textbf{A}^{\prime}_{i,i,d+1}=1\) if \(i\leq n\), and \(\textbf{A}_{i,i,d+1}=0,\textbf{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\} \tag{51}\]

\[\pi_{2}(i)=\pi_{0}(i+n)-n,i\in\{1,2,...,m\} \tag{52}\]

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

## Appendix 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, 2018), 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.

## Appendix C More details about the datasets

### Undirected Link Prediction

We use eight real-world datasets from SEAL (Zhang and Chen, 2018): 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).

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

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Dataset** & **\#Nodes** & **\#Edges** & **Avg. node deg.** & **Split ratio** & **Metric** \\ \hline 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 \\ \hline \hline \end{tabular}
\end{table}
Table 6: Statistics and evaluation metrics of undirected link prediction datasets.
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.

### 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 committee or cosponsoring a bill. Their statistics are shown in Table 8.

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Dataset** & **\#Nodes** & **\#Edges** & **Avg. node deg.** & **Split ratio** & **Metric** \\ \hline 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 \\ \hline \hline \end{tabular}
\end{table}
Table 7: Statistics and evaluation metrics of directed link prediction datasets.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Dataset** & **\#Nodes** & **\#Hyperdges** & **Split ratio** & **Metric** \\ \hline 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 \\ \hline \hline \end{tabular}
\end{table}
Table 8: Statistics and evaluation metrics of directed link prediction datasets.
### 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.
