Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning
Authors: Muhan Zhang
Pan Li
Yinglong Xia
Kai Wang
Long Jin
Venue: NeurIPS 2021 Poster (2021)
Keywords: theory
GNN
link prediction

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 link). We know that GNN is 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 into a joint node set representation. In this paper, we show a fundamental constraint of such an approach, namely the inability to capture the dependence between nodes in the node set, and argue that directly aggregating individual node representations does not lead to an effective joint representation for multiple nodes. Then, we notice that a few previous successful works for multi-node representation learning, including SEAL, Distance Encoding, and ID-GNN, all used node labeling. These methods first label nodes in the graph according to their relationships with the target node set before applying a GNN. Then, the node representations obtained in the labeled graph are aggregated into a node set representation. By investigating their inner mechanisms, we unify these node labeling techniques into a single and most general form---labeling trick. We prove that with labeling trick a sufficiently expressive GNN learns the most expressive node set representations, thus in principle solves any joint learning tasks over node sets. Experiments on one important two-node representation learning task, link prediction, verified our theory. Our work explains the superior performance of previous node-labeling-based methods, and establishes a theoretical foundation of using GNNs for multi-node representation learning.

Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning
Muhan Zhang .2, 1.2. Pan Liat Yinglong Xia Kai Wang' Long Jin
Institute for Artificial Intelligence, Peking University Beijing Institute for General Artificial Intelligence Department of Computer Science, Purdue University Faccbbook AI
Abstract
In this paper, we provide theory of using graph neural networks (GNNs) for multi- node representation learning (where we are interested in learning a representation for set of more than one node, such as link). We know that GNN is designed to learn single-node representations. When we want to learn node set representation involving multiple nodes, common practice in previous works is to directly aggregate the single-node representations obtained by a GNN into a joint node set representation. In this paper, we show fundamental constraint of such an approach, namely the inability to capture the dependence between nodes the node set, and argue that directly aggregating individual node representations does not lead to an effective joint representation for multiple nodes. Then, we notice that few previous successful works for multi-node representation learning, including SEAL, Distance Encoding, and ID-GNN, all used node labeling. These methods first label nodes in the graph according their relationships with the target node set before applying a GNN. Then, the node representations obtained in the labeled graph aggregated into node set representation. By investigating their inner mechanisms, we unify these node labeling techniques into a single and most general form-labeling trick. We prove that with labeling trick a sufficiently expressive GNN learns the most expressive node set representations, thus in principle solves any joint learning tasks over node sets. Experiments on one important two-node representation learning task, link prediction, verified our theory. Our work explains the superior performance of previous node-labeling- sabeling-based based methods, and establishes a theoretical foundation of using GNNs for multi-node representation learning.
Introduction
Graph neural networks (GNNs) 1110 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 graph classification), using GNNs to predict a set of multiple nodes is less studied and less understood. Among such multi-node representation learning problems, link prediction (predicting the link existence/clas//aalle between set of two nodes) is perhaps the most important one due to its wide applications in practice, including friend recommendation in social networks [Л] movie recommendation in Netflix [12), protein interaction prediction [3], drug response prediction (14), knowledge graph completion [5), etc. In this paper, we use link prediction as a medium to study GNN's 'ss multi-node representation learning ability. Note that although
examples and experiments are all around link prediction, our theory applies generally to all multi node representation learning problems such triplet [16), motif [17) and subgraph [8] prediction tasks.
"Corresponding author: Muhan Zhang (muhan@pku.c edu. en). Work done as a research scientist at Facehook. 1 Pan Li inspires study of labeling tricks, proves Theorem 2
and helps check the theoretical framework.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

There are two main classes of GNN-based link prediction methods: Graph AutoEncoder (GAE) 19 and SEAL 20 2T) GAE (and its variational version VGAE [9] first applies GNN to the entire network to compute representation for each node. The representations of the two end nodes of the link are then aggregated to prediet the target link. GAE represents a common practice of using GNNs to learn multi-node representations. That is, first obtaining individual node representations through a GNN as usual, and then aggregating the representations of those nodes of interest as the multi-node representation. On the contrary, SEAL applies a GNN to enclosing subgraph around each link, where nodes in the subgraph are labeled differently according to their distances to the two end nodes before applying the GNN. Despite both using GNNs for link prediction, SEAL often shows much better practical performance than GAE. As we will see, the key lies in SEAL's node labeling step.
We first give a simple example to show when GAE fails. In Figure [ 02 and d3 have symmetrie positions in the graph from their respective views, they have exactly the same hi-hop neighborhood for any h. Thus, without node features, GAE will learn the same representation for 02 and U3. However, when we want to predict which one of U2 and is more likely to form link with v1, GAE will aggregate the representations of 1/ and 1/2 as the link representation of (01, U2), and aggregate the representa- tions of 01 and bl to represent (U1, U3), thus giving (U1, U2) and (v), U3) the same representation and prediction. The failure to distinguish links (r1, 02) and (v1. va) that have apparently different structural roles in the graph reflects one key limitation of GAE-type methods: by computing U1 and U2 's representations independently of each other, GAE cannot capture the dependence between two end nodes of link. For example, (v 02) has a much shorter path between them than that of (u1, and (v1, U2) has both nodes in the same hexagon, while (v), v3) does not.
Figure I: In this graph, nodes U2 and Vy are isomorphic; links (V1, U2) and (t4, va) are isomorphic: link (2) and link (V1, vs) are not isomorphic. However, if we aggre- gate two node representations learned hy a GNN as the link representation, we will give (oi, v2) and (v), 0g) the same prediction.
another Take common neighbor (CN) 22 one elementary heuristic feature for link prediction, example. CN counts the number of common neighbors between two nodes to measure their likelihood of forming link, which is widely used in social network friend recommendation. CN is the foundation of many other successful heuristics such as Adamic-Adat [ and Resource Allocation (3). which also based neighborhood overlap. However, GAE cannot capture such neighborhood-overlap- based features. This can be seen from Figure 1 too. There is common neighbor between (11, U2)
and O between (U1, U3), but GAE always gives (V1, U2) and U3) 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-when computing the representation of one end node, it is not aware of the other end node.
One way to alleviate the above failure is to use one-hot encoding of node indices random features as input node features [24] (25). With such node-discriminating features, V/2 and E3s will have different node representations, thus (2) 12) and (Uz, 0z) may also have different link representations after aggregation, enabling GAE to discriminate (U1, U2) and (V1, v2). However, using pode-discriminating features loses GNN's inductive learning ability map nodes and links with identical neighborhoods (such as nodes 22 and eg and links (V1, 22) and (va, 03)) to the same representation, which results in a great loss of generalization ability. The resulting model is no longer permutation invariant/equivariant, violating the fundamental design principle of GNNs, Is there way to improve GNNs' link discrimi- nating power (so that links like (r), U2) and (v), va) can be distinguished), while maintaining their inductive learning ability (so that links (v1. 02) and (va, Uz) have the same representation)?
In this paper, we analyze the above problem from structural representation learning point of view. Srinivasan and Ribeiro 26) prove that the multi-node prediction problem on graphs ultimately only requires finding most expressive structural representation of node sets, which gives two node sets the same representation if and only if they are isomorphic (a.k.a. symmetric, on the same orbit) in the graph. For example, link (11, 12) and link (va, 03) in Figure 1 are isomorphie. A most expressive structural representation for links should give any two isomorphic links the same representation while discriminating all non-isomorphic links (such as (vi, 02) and (vi, v3)). According to our discussion above, GAE-type methods that directly aggregate node representations cannot learn a most expressive structural representation. Then, how to learn most expressive structural representation of node sets?
2

---

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 out that two properties of a node labeling are crucial for its effectiveness: 1) target-noles-disiinniiise and 2) permutation equivariance. With these two properties, we define labeling trick (Section (4.1), which unifies previous node labeling methods into single and most general form. Theoretically. we prove that with labeling trick a sufficiently expressive GNN can learn most expressive structural representations of node sets (Theorem D.. which reassures GNN's ' node set prediction ability. It also closes the gap between GNN's node representation learning nature and node set tasks' multi-node representation learning requirement. We further extend our theory to local isomorphism (Section 5 And finally, experiments on four OGB link existence prediction datasets [27] verified our theory.
Note that the labeling trick theory allows the presence of node/edge features/types, thus is not restricted to non-attributed and homogeneous graphs. Previous works on heterogeneous graphs, such as knowledge graphs (28] and recommender systems (29) have already seen successful applications of labeling trick. Labeling trick is also not restricted to two-node link representation learning tasks,
but generally applies to any multi-node representation learning tasks.
2 Preliminaries
In this section, we introduce some important concepts that will be used in the analysis of the paper, including permulation, set isomorphism and most expressive structural represenlation.
We consider a graph G = (V, where == {1. n is the set of n vertices, E V x V is the set of edges, and A Raxxxk a 3-dimensional tensor containing node and edge features. The diagonal components Ai, denote features of node i, and the off-diagonal components A.j.: denote features of edge (i.j). j). For heterogeneous graphs, the node/edge types can also be expressed in A using integers or one-hot encoding vectors. We further use A E {0, 1) j to denote the adjacency matrix of G with A. = 1 iff (i.j) E E. We let A be the first slice of A, i.e., A = A...1- Since contains the complete information of graph, we sometimes directly use A to denote the graph.
Definition 1. permutation a is a bijective mapping from (1, (1,2.....n) to (1,2.....,n) n). Depending
on the context, æ()) can mean assigning new index to node E V. or mapping node to node π (i) of another graph, All n! possible π 's constitute the permutation group 11g For joint prediction tasks over a set of nodes, predict the link between i, We define T(S) = (x))) E S}. We further define the permutation of A as TT (A), where x (()))) Ai...-
use S to denote the target node set. For example, S = ji if we want to
Next, we define set isomorphism, which generalizes graph isomorphism to arbitrary node sets. Definition 2. (Set isomorphism) Given two n-node graphs G = =(V,E,A), g' = FV', A'), and two node sets S C V, S" C V', we say (5, and (S', A') are isomorphic (denoted by AS (S', A if 3ग E II, such that TSS') and A ((A').
When (V. = (V', A'), we say two graphs G and G' are isomorphic (abbreviated as A = A' because V= (V') for any r). Note that set isomorphism is more strict than graph isomorphism, because it not only requires graph isomorphism, but also requires the permutation maps specific node set to another node set S'. In practice, when S of V. we are often more concerned with the case of A = A', where isomorphic node sets are defined in the same graph (automorphism). For example, when = {i), S' = {j} and (i, A) = (j, A), we say nodes i and j are isomorphic in graph A (or they have symmetric positions/same structural role in graph A). An example is U2 and i's in Figure
We say a function f defined over the space of (S. A) is permutation invariant (or invariant for abbreviation) if V' E II,, f(S, A) = (ST( T (A)). Similarly, f is permutation equivariant if VT e II, (S{(S A)) = (T)(S,, n (A)). Permutation invariance/equivariane ensures representations learned by GNN is invariant to node indexing, which is fundamental design principle of GNNs.
Now we define most expressive structural representation of node set, following (26] 221. Basically, it assigns a unique representation to each equivalence class of isomorphic node sets.
Definition 3. Given an invariant function I(-), I(S, A) is a most expressive structural representa- tion for (S, A) if AS S' A', r(S, A) r(S' A') + (S, A) ~ (S', A').
3

---

For simplicity, we will briefly use structural representation to denote most expressive structural representation in the rest of the paper. We will omit A if is clear from context. We call [ A) structural node representation for i, and call i({i,j), A) structural link representation for (i. j).
Definition 3 requires that the structural representations of two node sets are the same if and only if the two node sets are isomorphic. That is, isomorphic node sets always have the same structural repre- sentation, while non-isomorphic node sets always have different structural representations. This is in contrast to positional node embeddings such as DeepWalk [30] and matrix factorization [31, where two isomorphic nodes can have different node embeddings features also learns positional node embeddings.
32
GAE using disermmiiini
Why do study structural representations? Formally speaking, Srinivasan and Ribeiro 226 prove that any joint prediction task over node sets only requires a structural representation of node sets. They show that positional node embeddings carry no more information beyond that of structural representations. Intuitively speaking, it is because two isomorphic nodes in a network are perfectly symmetric and interchangeable with each other, and should be indistinguishable from any perspective. Learning a structural node representation guarantees that isomorphic nodes are always classified into the same class. Similarly, learning a structural link representation guarantees isomorphic links, such as (U1, U2) and (va, vz) in Figure [ are always predicted the same, while non-isomorphic links, such as (V1, U2) and (V1, 03),, are always distinguishable, which is not guaranteed by positional node embeddings. Structural representation characterizes the maximum representation power model can reach on graphs. We use study GNNs' multi-node representation learning ability.
3 The limitation of directly aggregating node representations
In this section, using GAE for link prediction as an example, we show the key limitation of directly aggregating node representations as a node representation.
3.1 GAE for link prediction
19 first use a GNN compute a node representation z; for each node i, and then use an aggregation function f({ zz1) to predict link (i,j):
Given graph A, GAE methods
Á.
where 2, = GNN(i, A), GNN(J A).
Here A., 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 (5) as the GNN, and let f([z), z,}) := az 2,). In principle, we can replace GCN with any GNN, and replace (2, 2j) with an MLP over any aggregation function over {z:, }j}. Besides inner product, other aggregation choices include mean, sum, bilinear product, concatenation, and Hadamard product. In the following, we will use GAE to denote general class of CNN-based link prediction methods.
GAE uses GNN to learn node representations and then aggregates pairwise node representations as link representations. Two natural questions to ask are: 1) Is the node representation learned by the GNN a structural node representation? 2) Is the link representation aggregated from two node representations a structural link representation? We answer them respectively in the following.
3.2
GNN and structural node representation
Practical GNNs
[3
usually simulate the 1-dimensional Weisfeiler-Lehman (1-WL) test +4 to
iteratively update each node's 's representation by aggregating neighbors' representations, We use 1-WL-GNN to denote GNN with 1-WL discriminating power, such as GIN [35].
A 1-WL-GNN ensures that isomorphic nodes always have the same representation. But the opposite direction is not guaranteed. For example, a I-WL-GNN gives the same representation to all nodes in an r-regular graph. Despite this, 1-WL is known to discriminate almost all non-isomorphic nodes [3].. This indicates that 1-WL-GNN can always give the same representation to isomorphic nodes, and can give different representations almost all non-isomorphic nodes.
To study GNN's maximum expressive power for multi-node representation learning, we also define a node-most--xppresivve GNN, which gives different representations to all non-isomorphic nodes.

---

Definition 4. A GNN is node-most-expreesive if Vi, V.j..,A, GN = GNN A') (i, A) = A.
+
That is, mode-most-express
GNN learns structural node representations" } because we want to answer: whether GAE, even equipped with GNN's node representation power not a bottleneck), can learn structural link representations.
We define such a GNN GNN (so that
3.3 GAE cannot learn structural link representations
Suppose GAE is equipped with mode-most-cxprestee GNN which outputs structural node repre- sentations. Then the question becomes: does the aggregation structural node representations of i and j result in structural link representation of [i, The answer is no, as shown in previous works [26] 29). We have also illustrated nodes 22 and U3, thus 222 and V/ will have the same structural node representation. By aggregating structural node representations. GAE will give (v1, 02) and (V), v3) the same link representation. However, (UI, U2) and (VI, 03) not isomorphic in the graph. This indicates:
the introduction: In Figure we have two isomorphic
Proposition GAE cannot learn structural link representations matter how expressive node representations a GNN can learn.
Similarly, we can give examples like Figure I for multi-node representation learning problems involving more than two nodes to show that directly aggregating node representations from a GNN does not lead a structural representation for node sets. 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 Thus, even GNN learns the most expressive single-node representations, there never guarantee that their aggregation is structural representation of node set. In other words, the multi-node representation learning problem is not breakable into multiple independent single-node representation learning problems. If we have to break it, the multiple single-node representation learning problems should dependent on each other.
4 Labeling trick for multi-node representation learning
In this section, we first define the general form of labeling trick, and use specific implementa- tion, zero-one labeling trick, to intuitively explain why labeling trick helps GNNs learn better link representations. Next, we present our main theorem showing that labeling trick enables a node-most- expressive GNN learn structural representations of node sets, which formally characterizes GNN's maximum multi-node representation learning ability. Then, we review SEAL and show it exactly uses one labeling trick. Finally, discuss other labeling trick implementations in previous works.
4.1 Labeling trick
Definition 5. (Labeling trick) Given A), we stack a labeling tensor L (()) Raaxxd the third E (k+d), where L satisfies: VS, A, S', A E I.,
dimension of A to get a new A(8)
1. (largelnuaee--diiiinnisiiir L (S) T( (5)) 5 = and (permutation equivariance) = (S') ((A) + (8) =T(()) (S))
To explain bit, labeling trick assigns label vector each node/edge in graph A, which constitutes
the labeling tensor L (5) By concatenating A and L
(S), we get the new labeled graph A (S) By definition we can assign labels to both nodes and edges. However, in this paper, we only consider
(8) node labels for simplicity, i.e., we let the off-diagonal components Lig. be all zero
The labeling tensor L (5) should satisfy two properties in Definition 5 Property requires that if
permutation preserving node labels (i.e., (S) (LL()))) exists between nodes of A and A', then the nodes in S" must be mapped to nodes in S by π (i.c., S = n (S')). A sufficient condition for property make the target nodes S have distinct labels from those of the rest nodes, that is
Although polynomial-ting time implementation is not known for eese--oo----pssivveeee GNNs, many practical softwares can discriminate all noniisomopphic nodes quite efficiently (37]. which provides promising direction.
5

---

Figure 2:
When we predict (M1, v2), we will label these two nodes differently from the rest, so that a GNN is aware of the target link when learning "i and 12 's representations. Similarly, when predicting (m) va). nodes 11 and my will be laheled differently. This way, the representation of in the left graph will be different from that of vy in the right graph, enabling GNNs distinguish the non-isomorphic links (v1,02) and (v1, vy).
distinguishable from others. Property 2 requires that when (S, A) and (S", A') are isomorphic under t (i.e., S = <T(S)) = π (A))), the corresponding nodes E S.j E , -i=(()) must always have the same label (i.e., L (S) x ()))). A sufficient condition for property 2 is to make the labeling function permutation equivariant, i.e., when the target (S, A) changes to (S)) x (A)). the labeling tensor L (5) should equivariantly change to π (s)).
5| and use it to Now introduce simplest labeling trick satisfying the two properties in Definition illustrate how labeling trick helps GNNs learn better node set representations.
Definition 6. (Zero-one labeling trick) Given a graph A and a set of nodes S to predict, we give it diagonal labeling matrix L (S) Rnxax1 such that L (S)
(S) 1 1 if E S and i =0 otherwise.
In other words, the zero-one labeling trick assigns label to nodes in S, and label 0 to all nodes not in S. is a valid labeling trick because firstly, nodes in get distinct labels, and secondly, the labeling function is permulation 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 to see how the zero-one labeling trick helps GNNs learn better link representations. This time, when we want to predict link (V,, 02), we will label v1, U2 differently from the rest nodes, as shown by the different color in Figure lleft. With nodes 11 and U/2 labeled, when the GNN is computing V2 representation, it also "aware" of the source node 21, instead of the previous agnostic way that treats U1 the same as other nodes. Similarly, when we want to predict link (w1, 0z), we will again label v1, 0g differently from other nodes as shown Figure 2 right. This way, 02 and V3 is node representations are no longer the same in the two differently labeled graphs (due to the presence of the labeled V1), and we are able to predict (v1, #2) and (v1, e3) differently. The key difference 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.
FlgureJleft.
At the same time, isomorphic links, such as (ii, U2) and (v4, v3), will still have the same representa- tion, since the zero-one labeled graph for (v1, 02) is still symmetric to the zero-one labeled graph for (Va, Us). This brings an exclusive advantage over GAE using pode-discriminatiin features.
With iy and U2 labeled, GNN can also learn their common neighbor easily: in the first iteration, only (v), 02)'s common neighbors will receive the distinct message from both ei and ne; then in the next iteration, all common neighbors will pass their distinct messages back to both i and u2, which effectively encode the number of common neighbors into ii and V2 's updated representations.
Now we introduce our main theorem showing that with valid labeling trick, node-most-exppeesive GNN can learn structural representations of node sets.
Theorem 1. Given a mode-most-expressivv GNN and an injective set aggregation function AGG, for any S, S, A', GNN(S, (8)) = GNN(S', (8")) + (5, =z (S', A'), where GNN(S, A ()))= = AGG((GNN(i,, A (5) E S}).
We include all proofs in the appendix. Theorem 1 implies that AGG A () E S)) is structural representation for (S, A). Remember that directly aggregating the structural node representations learned from the original graph A does not lead structural representations of node sets (Section 3.3). Theorem shows that aggregating the structural node representations learned from the labeled graph A (5). somewhat surprisingly, results in structural representation for (S, A).
The significance of Theorem iis that it closes the gap between GNN's ' single-node representation nature and node set prediction problems' multi-node representation requirement. It demonstrates that

---

GNNs are able to learn most expressive structural representations of node sets, thus are suitable for joint prediction tasks over node sets too. This answers the open question raised in [26] questioning GNNs' link prediction ability: are structural node representations in general-and GNNs in particular- fundamentally incapable of performing link (dyadic) and multi-ary (polyadic) prediction tasks? With Theorem 1 we argue the answer is no. Although GNNs alone have severe limitations for learning joint representations of multiple nodes, GNNs + labeling trick can learn structural representations of node sets too by aggregating structural node representations obtained in the labeled graph.
Theorem assumes& a sedde-most-expeeee
GNN. To augment Theorem we give the following theorem, which demonstrates labeling trick's power for 1-WL-GNNS.
Theorem 2. In any non-attributed graph with n nodes, if the degree of each node the graph is I-t between 1 and Ollog 20 n)) for any constant E >> O, then there exists w(n²)) many pairs of non- isomorphic links (u, w), (w, w) such that an h-layer 1-WL-GNN gives u, u the same representation. while with labeling trick the 1-WL-GNN gives different representations.
Theorem shows that in any non-attributed graph there exists large number (w)n²)) of link pairs (like the examples (vi, 02) and (01, v3) in Figure I which are not distinguishable by I-WL-GNNs alone but distinguishable by I-WL-GNNs + labeling trick.
4.2 SEAL uses labeling trick
SEAL 20 a state-of-the-art link prediction method based on GNNs. It first extracts an enclosing subgraph (h-hop subgraph) around each target link to predict.
Definition 7. (Enclosing subgraph) Given (S, A), the h-hop enclosing subgraph A(s.M) of S is the subgraph induced from A by Uje (i| d(i,j) S h),, where j) is the shortest path distance between nodes i and) j.
Then, SEAL applies Double Radius Node Labeling (DRNL) to give an integer label to each node in the enclosing subgraph. DRNL assigns different labels to nodes with different distances to the two end nodes of the link. It works as follows: The two end nodes are always labeled Nodes farther away from the two end nodes get larger labels (starting from 2). For example, nodes with distances {1, 1} to the two end nodes will get label 2, and nodes with distances (1, 2) to the two end nodes will get label 3. So on and so forth. Finally the labeled enclosing subgraph is fed to GNN to learn the link representation and output the probability of link existence.
Theorem 3. DRNL is labeling trick.
Theorem 3 is easily proved by noticing: across different subgraphs, 1) nodes with label are always those in the target node set S. and 2) nodes with the same distances to S always have the same label, while distances are permutation equivariant. Thus, SEAL exactly uses a specific labeling trick to enhance its power, which explains its often superior performance than GAE 20)
SEAL only uses subgraph (sS,)) within h hops from the target link instead of using the whole graph. This is not a constraint but rather a practical consideration (just like GAE typically uses less than 3 message passing layers in practice), and its benefits will be discussed in detail in Section 5 When h + oc, the subgraph becomes the entire graph, and SEAL is able to learn structural link representations from the labeled (entire) graph.
Proposition 2. When h + co, SEAL can learn structural link representations with node-most- expressive GNN.
4.3 Discussion
DE and DRNL In (2I], SEAL's distance-based node labeling scheme is generalized to Distance Encoding (DE) that can be applied to |S| > 2 problems. Basically, DRNL is equivalent to DE-2 using shortest path distance. Instead of encoding two distances into one integer label, DE injectively aggregates the embeddings of two distances into label vector. DE is also valid labeling trick, as it can also distinguish S and is permutation equivariant. However, there are some subtle differences between DE and DRNL's implementations, which are discussed in Appendix D.
ID-GNN You et al. 3 propose ldentity-aware GNN (ID-GNN), which assigns a unique color to the "identity" nodes and performs message passing for them with different set of parameters.
7

---

ID-GNN's coloring scheme is similar to the zero-one labeling trick that distinguishes nodes in the target set with 0/1 labels. However, when used for link prediction, ID-GNN only colors the source node, while the zero-one labeling trick labels both the source and destination nodes. Thus, ID-GNNN can be seen as using a partial labeling trick. The idea of conditioning on only the source node also We leave the exploration of partial labeling trick's s power for future work.
used in NBFNet (3)]
Labeling trick for heterogeneous graphs Since our graph definition A allows the presence of node/edge types, our theory applies to heterogeneous graphs, too. In fact, previous works have already successfully used labeling trick for heterogeneous graphs. IGMC 29 uses labeling trick to predict ratings between users and items (recommender systems), where a user node k-hop away from the target link receives a label 2k, and an item node k-hop away from the target link receives a label 2k + 1. It is valid labeling trick since the target user and item always receive distinct labels 0 and 1. On the other hand, GRAIL. 28 applies the DRNI. labeling trick to knowledge graph completion.
Directed case. Despite that we do not restrict our graphs to be undirected, our node set definition (Definition 2 does not consider the order of nodes in the set (i.e., direction of link when |S| = 2). The ordered case assumes S = (1, 2, 3) is different from S = (3, 2, 1). One way to solve this is to define labeling trick respecting the order of S. In fact, if we define (S)) = (T(S(t) i = 1.2,..... |
(where Sli] denotes the th element in the ordered set S) in Definition I and modify our definition of labeling trick using this new definition of permutation, then Theorem I still holds.
Complexity, Despite the 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 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. 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. However, for large graphs that cannot fit into the GPU memory, mini-batch training (which extracts a neighhorhood subgraph for every node set to predict) has to be used for both GAE-type methods and labeling trick, resulting in similar computation cost.
5 Local isomorphism: a more practical view of isomorphism
The concept of most expressive structural representation is based on assigning node sets the same representation if and only if they are isomorphic to each other in the graph. However, exact isomor- phism is not very common. For example, Babai and Kucera (36] prove that at least (n - log n) nodes in almost all n-node graphs are non-isomorphic to each other. In practice, I-WL-GNN also takes up to ((n) message passing layers to reach its maximum power for discriminating non-isomorphic nodes, making it very hard to really target on finding exactly isomorphic nodes/links.
Lemma 1. Given a graph with n nodes, I-WL-GNN takes up to (n)) message passing layers to discriminate all the nodes that 1-WL can discriminate.
In this regard, we propose more practical concept, called local isomorphism.
Definition 8. (Local h-isomorphism) AS, A, S A', we say (S,A) and (S',A') isomorphic to each other (5, A(s.)) = (5', (s)..))
A') are locally h-
Local h-isomorphism only requires the h-hop enclosing subgraphs around S and S' are isomorphic, instead of the entire graphs. We argue that this is a more useful definition than isomorphism, because: 1) Exact isomorphism is rare in real-world graphs. 2) Algorithms targeting on exact isomorphism more likely to overfit. Only assigning the same representations to exactly isomorphic nodes/links may fail to identify a large amount of nodes/links that are not isomorphic but have very similar neighborhoods. Instead, nodes/links locally isomorphic to each other may better indicate that they should have the same representation. With local h- h-isomorphism, all our previous conclusions based on standard isomorphism still apply. For example, GAE (without node-discriminating fcatures) still cannot discriminate locally isomoiicoocppic links. And a node-most- mode-most-eepressive GNN with labeling trick can learn the most expressive structural representations of node sets w.r.t. local h-isomorphism, i..., learn the same representation for two node sets if and only if they are locally h-isomorphic:
Corollary 1. Given a node- dodde--ost-expessivve GNN and an injective set aggregation function AGG, then for any S, A, S', A', h. GNN(S, (S) = GN" A (S') (S)))) + (S. (ss,)) =('', A(grr))) m))-
8

---

Corollary [ demonstrates labeling trick's power in the context of local isomorphism. To switch to local f-isomorphismm all we need to do is extract the h-hop enclosing subgraph around a node set, and apply labeling trick and GNN only to the extracted subgraph. This is exactly what SEAL does.
Related work
There is emerging interest in studying the representation power of graph neural networks recently, Xu et al. [35] and Morris et al. [40] first show that the discriminating power of GNNs performing neighbor aggregation is bounded by the 1-WL test. Many works have since been proposed to increase the power of GNNs by simulating higher-order WL tests 140 However, most previous works focus on improving GNN's 's whole-graph representation power. Little work has been done to analyze GNN's s node/link representation power. Srinivasan and Ribeiro [26] 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 trick can as well learn structural link representations, which reassures using GNNs for link prediction.
Many works have implicitly assumed that if model can learn node representations well, then combining the pairwise node representations can also lead to good link representations [43 19 44) However, argue in this paper that simply aggregating node representations fails to discriminate a large number of non-isomorphic links, and with labeling trick the aggregation of structural node representations leads to structural link representations. Li et al. [2 proposed distance encoding (DE), whose implementations based on S-discriminating distances can be shown to be specific labeling tricks. They proved that DE can improve 1-WL-GNNs' discriminating power, enabling them to differentiate almost all (S, A) tuples sampled from r-regular graphs. Our paper contributes to important aspect that Li al. (2 overlooked: 1) Our theory focuses on the gap between GNN's single-node and multi-node representation power. We show even a GNN has maximum node representation power, still fails to learn structural representations of node sets unless combined with labeling trick. However, the theory of DE cannot explain this. 2) Our theory is not restricted to r-regular graphs, but applies to any graphs. 3) Our theory points out that valid labeling trick is not necessarily distance based-it need only be permutation equivariant and S-discriminating. More discussion on the difference between DE's theory and the theory in this paper is given in Appendix
You et al. also noticed that structural node representations of GNNs cannot capture the de- pendence (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 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 large datasets. You et al. (8 later proposed ID-GNN. As discussed in Section 4.3 ID-GNN's node coloring scheme can be seen as partial labeling trick.
Finally, although labeling trick is formally defined in this paper, various forms of specific labeling tricks have already been used in previous works. To our best knowledge, SEAL 20 proposes the first labeling trick, which is designed to improve GNN's link prediction power. It is later adopted in inductive knowledge graph completion (28) and matrix completion [29]. and is generalized into
DE 21
which works for [S| cases. Wan al. (46) use labeling trick for hyperedge prediction.
7 Experiments
In this section, we use a two-node task, link prediction, to empirically validate the effectiveness of labeling trick for multi-node representation learning. We use four link existence prediction datasets in Open Graph Benchmark (OGB) 27 ogbl-ppa, ogbl-collab, ogbl-dd> and ogbl-co fobl-cinee citatiinn These datasets are ooun-soureed, large-scale (up to 2.9M nodes and 30.6M edges), adopt realistic train//alidationntess splits, and have standard evaluation procedures, thus providing an ideal place to benchmark an algorithm's realistic link prediction power. The evaluation metrics include Hits@ K and MRR. Hits @ K counts the ratio of positive edges ranked at the K-th place or above against all the negative edges. MRR (Mean Reciprocal Rank) computes the reciprocal rank of the true target node against 1,000 negative candidates, averaged over all the true source nodes. Both metries are

---

Table 1: Results for ogbl-ppa, ogbl-collab, ogbl-ddi and ogbl-citation2.
ogbl-ppa
ogbl-collab
ogb1-888
ogb1-ci ogbl-citasion2
His 100 (%)
50 (9)
e0 (%)
MRR (%)
Category
Method
Validation
Test
Validation
Test
Validation
Test
Validation
Test
28,23+0.00
27.6+0.00
00036-00.00
61.37+0000
9:47=0000
17.73+0000
$1.19+0.00
51,47+0.00
AA
32.68.10.00
52.45.0.000
63.4910.00
64.17.10.00
9.66.10.0
18,6110000
51.6710.00
51 89,0000000
Non-GNN
MLP
0,46190.00
0,4620.00
24.02=1.45
19.27=1.29
29.03:0.17
29.0610.16
Node2vec
22.53+0.88
22.26-0085
57.03-0.52
32.92+122
23.26+2..9
61.24+0.11
6141+00:11
MF
32.28::4.25
32.29=
48.96.0.29
38.86=0029
33. 33.70#2264 64
13.68:4475
$1.81
51.36624433
GraphSAGE
17.24122.4
16.55:22.40
56 0,777
14.63:21.12
62. 62.62:1033 37
53.9014.74 74
82.6310:23
02.60:10.36
Plain GAE
GCN
18.4511.40
18.67
1..63
55.50 47.14
37.07.45.07
84.7911023
84.7410.21
GCN+LRGA
25.75+2282
26. 26.12222.35 35
60.88-00.99
52.21
66.78+0058
62.30+9.12
66.48#166
66.49+1.59
GCN+DE
36.3113..99
36 36,48833778
64.1310.16
69,44.10.29
29.8511225
26 26.63.16.22
60.17.10.3
60. 60.30.1..11
Labeling Trick
GCN+DRNL
46.43+3303
45.24
64.51
64.40=0.45
29.47=+154
22.81
81.0700300
27.
SEAL
51.25:12.52
48.80
64.95.0.43
64.74.10.43
28.49.12.09
30.56.13.6
87.57.10.31
87.67.0.32
higher the better. We include more details and statistics of these datasets in Appendix F. Our code is available at ltttps://githuui htctp::///gittuu..mm///aaaaaaaee htt:://aaabboooeeeerarcc///////a
OGB
Baselines. We use the following baselines for comparison. We use 5 non-GNN methods: CN (common neighbor), AA (Adamic-Adar), MI.,, MF (matrix factorization) and Node2vec. Among them, CN and AA are two simple link prediction heuristics based on counting common neighbors, which are used for sanity checking. We use plain GAE baselines: GraphSAGE [44), GCN [9,, and GCN+LRGA 477. These methods use the Hadamard product of pairwise node representations output by a GNN as link representations, without using a labeling trick. Finally, we compare 3 GNN methods using labeling tricks: GCN+DE (21). GCN+DRNL, and SEAL [2]. GCN+DE/GCN+DRNL enhance GCN with the DE/DRNL labeling trick. SEAL uses GCN and the DRNL labeling trick, with an additional subgraph-level readout SortPooling (9. More details are in Appendix G. Moreover, we test the zero-one labeling trick in our ablation experiments. Results can be found in Appendix H.
Results and discussion. We present the main results in Table T Firstly, we can see that GAE methods without labeling trick do not always outperform non-GNN methods. For example, on ogbl-ppa and ogbl-collab, simple heuristics CN and AA outperform plain GAE methods by large margins. This suggests that GAE methods cannot even learn simple neighborhood-overlap based heuristics, verifying our argument in Introduction. In contrast, when GNNs are enhanced by labeling trick, they are able to beat heuristics. With labeling trick, GNN methods achieve new state-of-the-arr performance on 3 out of 4 datasets. In particular, we observe that SEAL outperforms GAE and positional embedding methods, sometimes by surprisingly large margins. For example, in the challenging ogbl-ppa graph, SEAL achieves an Hits @ 100 of 48.80, which is 87 1955% % higher than GAE methods without using labeling trick. On ogbl-ppa, ogbl-collab and cittion,,, labeling trick methods also achieve state-of-the- art results.
Despite obtaining the best results on three datasets, observe that labeling trick methods do not perform well on ogbl-ddi. ogbl-ddi is considerably denser than the other graphs. It has 4,267 nodes and 1,334,889 edges, resulting in an average node degree of 500.5. In ogbl-ddi, labeling trick methods fall behind GAE methods using trainable node embeddings. One possible explanation is that ogbl-ddi ddi is so dense that practical GNN with limited expressive power is hard to inductively learn any meaningful structural patterns. In comparison, the transductive way of learning free- peeepprreeter node embeddings makes GAES no longer focus learning inductive structural patterns, but focus on learning node embeddings. The added parameters also greatly increase GAEs' model capacity. An interesting future topic is study how to improve labeling tricks' performance on dense graphs. Appendix H presents more ablation experiments to study the power of different labeling tricks, the effect of subgraph pooling, and the number of hops/layers.
8 Conclusions
In this paper, we proposed a theory of using GNNs for multi-node representation learning. We first pointed out the key limitation of common practice in previous works that directly aggregates node representations as node set representation. To address the problem, we proposed labeling trick which gives target nodes distinet labels in permutation equívariant way. We proved that labeling trick enables GNNs to learn most expressive structural representations of node sets, which formally characterizes GNNs' maximum multi-node representation learning ability. Experiments on four OGB datasets verified labeling trick's effectiveness.
10

---

Acknowledgements
The authors greatly thank the actionable suggestions from the reviewers. Li is partly supported by the 2021 JP Morgan Faculty Award and the National Science Foundation (NSF) award HDR-2117997.
References
[1] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
[2] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 1rXiv:1312.000. 2013.
[3] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aapuru-Guzike and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In Advances in neural information processing systems, pages 2224- 2232, 2015.
[4] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.054%: 2015.
[5] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609 2016.
[6] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3837-3845, 2016.
[7] Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In Proceedings of The 33rd International Conference on Machine Learning, pages 2702-271 202-271111 1, 2016.
[8] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 1710:11700.0000: 2017.
[9] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAL, pages 4438-4445, 2018.
[10] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovee. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pages 4800-4810 10, 2018.
[11] Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3): 211-230, 2003.
[12] James Bennett, Stan Lanning, et al. The netflix prize. In Proceedings of KDD cup and workshop. volume 2007, page 35. New York, 2007.
[13] Yanjun Qi. Ziv Bor-Joseph, and Judith data and computational classification methods for use in protein interaction prediction. Proteins: Structure, Function, and Bioinformatics, 63(3):990550) 2006.
Evaluation of different biological
[14] Zachary Stanfield, Mustafa Coskun, and Mehmet Koyutürk. Drug response prediction as a link prediction problem. Scientific reports, 701):1-13, 2017.
[15] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. arXiv preprint arXiv: 1503.0099, 2015.
[16] Yunyu Liu, Jianzhu Ma, and Pan Li. Neural higher-order pattern (motif) prediction in temporal networks. arXiv preprint arxii:2/066066 2021.
[17] Maciej Besta, Raphael Grob, Cesare Miglioli, Nicola Bernold, Grzegorz Kwasniewski, Gabriel Gjini, Raghavendra Kanakagiri, Saleh Ashkboos, Lukas Gianinazzi, Nikoli Dryden, et Motif prediction with graph neural networks. arXiv preprint 10000:2200600061,, 2021.
11

---

[18] Emily Alsentzer, Samuel G Finlayson, Michelle M Li, and Marinka Zitnik. Subgraph neural networks. arXiv preprint arXiv:2006.10533, 2020.
[19] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.
[20] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pages 5165-5175, 2018.
[21] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding design provably more powerful gnns for structural representation learning. arXiv preprint wrXiv:2009.00/44 2020.
[22] David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019-1031, 2007.
[23] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71()))22366300 2009.
[24] Andreas Loukas. What graph neural networks cannot learn: depth width. arXiv preprint arXiv:1907.031999 2019.
[25] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. arXiv preprint arXiv:200..03155, 2020.
[26] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference Learning Representations, 2020. URL https://ppneereeieer www/eeetuuunneeee iirrummmddddxxaSSSk
[27] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint 20Xx::2005.00687.. 2020.
[28] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning. pages 9448 11879997 PMLR, 2020.
[29] Muhan Zhang and Yixin Chen. Inductive matrix complction based on graph neural networks. In International Conference on Learning Representations, 2020. URL https://openrrerier net/ www.ooorumndddxgggeee
[30] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710. ACM, 2014.
[31] Andriy Mnih and Ruslan R Salakhutdinov. Probabilistic matrix factorization. In Advances in neural information processing systems, pages 1257-1264, 2008
[32] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 385-394. ACM, 2017.
[33] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1263-1272. JMLR. org, 2017.
[34] Boris Weisfeiler and AA Lehman. A reduction of graph canonical form and algebra arising during this reduction. Nanccho--Tecimiccheskayy Informatsia, 2(9):12-16, 1968.
[35] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.00822 2018.
[36] László Babai and Ludik Kucera. Canonical labelling of graphs linear average time. 20th Annual Symposium on Foundations of Computer Science (sfes 1979), pages 39-46. IEEE, 1979.
12

---

[37] Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of Symbolic Computation, 60:94-112, 2014.
[38] Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. arXiv preprini arXiv:2101.10322 2021.
[39] Zhaocheng Zhu, Zuobai Zhang. Louis-Pascal Xhonneux, and Jian Tang. Neural hellman-ford networks: A general graph neural network framework for link prediction. arXiv preprint arXiv:2/06.06935, 2021.
[40] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe, Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602 4009-4609,40 2019.
[41] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances Neural Information Processing Systems, pages 2156-2167, 2019.
[42] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in Neural Information Processing Systems, pages 15894 15902, 2019.
[43] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864. ACM, 2016.
[44] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1025-1035, 2017.
[45] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. arXiv 1rXiv:1906.048/1
preprint arXiv: 1906. 0481, 2019.
[46] Changlin Wan, Muhan Zhang, Wei Hao, Sha Cao, Pan Li, and Chi Zhang. Principled hy- peredge prediction with structural spectral features and neural networks. arXiv preprint arXiv:2106.04299, 2021.
[47] Omri Puny, Heli Ben-Hamu, and Yaron Lipman. From graph low-rank global attention to 2-fwl approximation. arXiv preprint arXiv:2006.088 07846, 2020.
[48] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903.02428, 2019.
13


Reviews:
[{"review_id": "wjSN7H1evqU", "reviewer": "Reviewer_gL7o", "summary": "This paper studies the problem of using GNN for link prediction. The contributions are mainly two folds. First, it studies the limitation of using GAE for link prediction, which directly aggregate a pair of nodes embedding. Secondly, it proposes the labeling trick which is sufficiently expressive and unifies some of the existing frameworks. The proposed method is general for high-order node set prediction where link prediction is a special case. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper first points out the limitation of GAE for link prediction, showing that GAE learn same representations for isomorphism nodes, this would give non-isomorphism links the same link representation. To address that, this paper proposes a zero-one labeling trick that labels the nodes in the target set $S$. This proposed trick unifies some existing GNN methods for link prediction. The expressive power of the labeling trick is also studied with theoretical guaranteed. I think the proposed method is general enough as it unifies the existing methods such as SEAL and could be applied for high-order link set prediction or hypergraph prediction. My mainly concern for the proposed method, which I also mentioned in the limitation section, is that the labeling trick need to perform node embeddings for each given target set $S$. For GAE, we could first obtain node representations for all nodes and then make link predictions for any pair of nodes. While the labeling trick seems to be link-specific, and should be computationally cost when applying to large scale data and predicting multiple links. I wonder in your experiments, how does the order of computational cost for GAE-based method and labeling based method? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think one major limitation is the computational cost of the proposed labeling framework. In comparison to GAE, where node representation for all nodes are learned first and link prediction could be made for multiple links at the same time, the labeling trick need to compute node representations under a given node $S$. For predicting multiple links, that is computationally cost. Would this be implemented in parallel for link prediction for multiple node pairs?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "EZLdbRarU2O", "reviewer": "Reviewer_4QvJ", "summary": "This paper focuses on the link prediction task of graph neural networks. The authors delve into the structural link representation and propose a labeling trick that enables existing GAE models to distinguish between non-isomorphic links.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors note the performance gap between GAE and SEAL on the link prediction task, and argue that the former can only learn the structural node representation, while the latter can further learn the structural link representation, which is significant for the link prediction problem. Based on the above analysis, the authors put forward the labeling trick, which theoretically proved to be a good solution to this problem. This strategy can be seamlessly integrated with existing GAE approaches so that they can learn structural link representation to distinguish between non-isomorphic links in the graph. The authors also demonstrate that SEAL, ID-GNN, and other methods are essentially special cases of the labeling trick. In general,  the paper examines a very interesting problem and provides a useful but not novel enough solution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "an hour"}, "extra_text": {}}, {"review_id": "8ArUMo_wznL", "reviewer": "Reviewer_b9cR", "summary": "This paper dives into the study of some theoretical properties of GNNs and their training for the task of link prediction. In particular, it addresses the expressive power of GNNs for learning structural link representations, and points out that even with full node representation power, GNNs can fail to represent edges adequately. The authors show that the graph autoencoder method for link prediction cannot learn structural link predictions, resulting in some non-isomorphic graph edges getting the same representation. This is due to the fact that GAE methods learn node representations independently, as opposed to conditioning the representation of the target nodes on each other. The authors continue to describe a labeling trick that helps GNNs learn structural link representations, show that the trick works, and further prove that the SEAL method uses a valid labeling trick. The authors conduct experiments on three datasets to verify their theoretical results, and compare their method with a class of very basic link prediction approaches (MLP, node2vec,...) and another class of popular GNN approaches (GCN, GraphSAGE, SEAL,...). The experiments confirm their findings.\n", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a very good paper that addresses important theoretical questions about GNNs that go beyond WL testing. \nThe paper is very well written. The notation is consistent and laid out with care. Definitions are clear and formal. The authors motivate the reasons for studying their problem with examples, which are very helpful in following the buildup of the lemmas leading to the main conclusions in the paper. In the Related Work section, the authors cover the range of existing work on the topic and place their contribution very nicely among existing work and lay out its differences clearly. \nExperiments are well described and adequate. The authors provide many  details in the appendix, and show results of various ablations that explore questions about number of layers vs number of hops, subgraph-level readout, power of zero-one labeling, ...etc.\n\nThe paper enhances our core understanding of limitations of some GNN methods for link prediction. It also provides a labeling technique that unifies some of the existing attempts to improve the expressive ability of graph link representation. The theoretical discussions are presented general enough to apply to generalized link prediction (e.g. in hypergraphs).\n\n\nMinor comments:\n- Line 210: \"rest nodes\" should be something like \"remaining nodes\"\n- Line 378: \"then\" should be \"them\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations address adequately across the paper/appendix.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "16A1kOc6Fl", "reviewer": "Reviewer_KGAE", "summary": "This paper introduces a new concept \"labeling trick\" along with multiple ways of using or decorating it such as \"valid labeling trick\" and \"zero-one labeling trick\". It proves that popular link prediction algorithms such as SEAL, Distance Encoding, and ID-GNN can all be considered as specific implementations of the labeling trick. So the new concept, though was not explicitly referred in the literature, has demonstrated its significance. The paper offers a theoretical analysis to explain the outperformance of the labeling trick over plain GAE. The authors' response addressed most of my concerns when I had a difficulty to digest the new concepts and combine them with the theory. An important suggestion is offering a figure to illustrate the labeling trick and show the specifications of the three algorithms (how they are sharing the labeling trick philosophy and still having their uniqueness of implementation). That will significantly help broad readers catch the point of this paper at the beginning.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: In the authors' response, they clarified the difference between the labeling trick and graph data augmentation. It's good to know the authors will discuss this point in the paper revision. Quoting from the authors' response:\n\"The labeling tensor L(S) is not “new data added into the original data A”. The labeled tensor “A concat L(S)” is the new data, and this new data is not “added” into the original data. Instead, it replaces the original data A.\"\nI suggest the authors to clarify the difference between \"concat+replace\" and \"add\" - why concatenating labeling tensor and then replacing is not adding the labeling tensor into the original data A.\nAlso, I need to point out that the augmentation techniques were narrowly considered (within the computer vision studies) in the authors' responses. In the two papers I've given as well as Lecture on \"Graph Augmentation\" in Prof. Jure Leskovic's Machine Learning on Graphs course, graph augmentation is looking for the optimal computational graph - some techniques could be adding/dropping node attributes and/or edges beyond flipping or rotating operations in computer vision.\n[1] Data augmentation for graph neural networks. AAAI'21.\n[2] Nodeaug: Semi-supervised node classification with data augmentation. KDD'20.\n\nQuality: \"Structural link representation\" must be well defined. The definition is missing. It looks like this concept must include at least \"count of common neighbors\", but what else? What can GAE learn - and if the things it learned is not about structural links, why it performs better than random guess. The authors' response was not able to address my confusion at this point, though it's not a big case.\n\nClarity: The authors' response has made the idea and contributions of this work much more clear. I appreciate that. I would still suggest several ways to improve the clarify as aforementioned. \n\nSignificance: I encourage exploration on the theory of graph neural networks. It is impactful to generalize the advantage of several algorithms as a new concept and provide theoretical analysis on its advantage over GAE.\n\nI changed my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not included or discussed. ", "review_text": "", "extra_scores": {"ethical_concerns": "I don't have any concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on GNNs for link prediction and sheds light on the performance gap between GAE and SEAL by identifying a key limitation in GAE. To overcome this limitation, a labeling trick is proposed that enables the unification of existing frameworks and that generalizes to high-order node set prediction. 

The AC and reviewers carefully examined the author feedback and all agree that this paper makes some very pertinent contributions leading to a better understanding of GNNs for link prediction. 

It would be important to incorporate into the main text the remark on computational complexity from the author response. As noted by the authors, the labeling trick can result in significant computational overhead, and such a limitation should not be completely relegated to the supplements.
Decision: Accept (Poster)