Revisiting Graph Neural Networks for Link Prediction
Authors: Muhan Zhang
Pan Li
Yinglong Xia
Kai Wang
Long Jin
Venue:  (2021)
Keywords: Graph Neural Networks
Link Prediction

Abstract: Graph neural networks (GNNs) have achieved great success in recent years. Three most common applications include node classification, link prediction, and graph classification. While there is rich literature on node classification and graph classification, GNNs for link prediction is relatively less studied and less understood. Two representative classes of methods exist: GAE and SEAL. GAE (Graph Autoencoder) first uses a GNN to learn node embeddings for all nodes, and then aggregates the embeddings of the source and target nodes as their link representation. SEAL extracts a subgraph around the source and target nodes, labels the nodes in the subgraph, and then uses a GNN to learn a link representation from the labeled subgraph. In this paper, we thoroughly discuss the differences between these two classes of methods, and conclude that simply aggregating \textit{node} embeddings does not lead to effective \textit{link} representations, while learning from \textit{properly labeled subgraphs} around links provides highly expressive and generalizable link representations. Experiments on the recent large-scale OGB link prediction datasets show that SEAL has up to 195\% performance gains over GAE methods, achieving new state-of-the-art results on 3 out of 4 datasets.

Under review as a conference paper at ICLR 2021
REVISITING GRAPH NEURAL NETWORKS FOR LINK PREDICTION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) have achieved great success in recent years. Three most common applications include node classification, link prediction, and graph classificatton.. While there is rich literature on node classification and graph clas- sification, GNNs for link prediction is relatively less studied and less understood. Two representative classes of methods exist: GAE and SEAL. GAE (Graph Au- toencoder) first uses a GNN to learn node embeddings for all nodes, and then aggregates the embeddings of the source and target nodes as their link represen- tation. SEAL extracts subgraph around the source and target nodes, labels the nodes in the subgraph, and then uses GNN to learn link representation from the labeled subgraph. this paper, we thoroughly discuss the differences between these two classes of methods, and conclude that simply aggregating node embed- dings does not lead to effective link representations, while learning from prop- erly labeled subgraphs around links provides highly expressive and generalizable link representations. Experiments on the recent large-scale OGB link prediction datasets show that SEAL has up to 195% performance gains over GAE methods, achieving new statc-of-the-art results on 3 out of 4 datasets.
INTRODUCTION
Link prediction is to predict potential missing links connecting pairwise nodes in network. It has wide applications in various fields, such as friend recommendation in social networks (Adamic
& Adar 2003), movie recommendation in Netflix (Bennett al. 2007), , protein-protein interaction prediction (Qi et al. 2006), and knowledge graph completion (Nickel et al. 2015), etc.
Traditional link prediction approaches include heuristic methods, embedding methods, and feature- based methods. Heuristic methods compute some heuristic node similarity scores as the likeli- hood of links (Liben-Nowell & Kleinberg 2007), such common neighbors, preferential attach- ment (Barabási & Albert 1999). and Katz index (Katz) 1953), which can be regarded as some predefined graph structure features. Embedding methods, including matrix factorization (MF) and Node2vec (Grover & Leskovec 2016), learn free- free- parameter node embeddings from the observed network transductively, thus do not generalize to unseen nodes and networks. Feature-based meth- ods only use explicit node features yet do not consider the graph structure. Recently, graph neural networks (GNNs) emerged to be powerful tools for learning over graph-structured data (Scarselli ct al. 2009 Bruna et al. 2013) Duvenaud et al. 2015 Li al. 2015 Kipf & Welling 2016al Nicpert
ct al. 2016 Dai et al.] 2016), and have been successtully used in link prediction as well (Kipf &
Welling 2016b Zhang & Chen 2018: You et al. 2019 Chami al. 2019 Li et al. 2020).
There are two main types of GNN-based link prediction methods. One is Graph Autoencoder (Kipf & Welling, 20166), where GNN is first applied to the entire network to learn an embedding vector for each node, Then the embeddings of the source and target nodes are aggregated to predict the target link. The second type is SEAL (Zhang & Chen 2018 Li al. 2020), where enclosing subgraph is extracted around each target link. Then the nodes in each enclosing subgraph are labeled differently according their distances the source and target nodes. Finally a GNN applied to each enclosing subgraph to learn link representation for link prediction. At first glance, both methods seem to learn graph structure features associated with the target link, and leverage these structure features for link prediction. However, as we will see, the two methods have fundamentally different power in terms of learning the structural representations of links.

---

Under review as a conference paper at ICLR 2021
We first show that by individually learning source and target node embeddings, GAE methods cannor differentiate links with differ- ent structural roles. To intuitively understand this, we give an ample in Figure | In this graph, nodes v22 and bg have the same structural roles (symmetric/isoorphiic to each other). A GAE will learn the same node embeddings for U2 and U3. thus giving the same predicted probabilities for link (vi, U2) and link (v), va). However, the structural roles of link (21, 02)) and link (V1, Us) are apparently different- - 11 intuitively should have unequal probabil- ities connecting to 02 and ug. Next, we propose a labeling trick, which gives a label to each node as its additional feature, where the source and target nodes are labeled differently from the rest. We show that combined with the labeling trick, sufficiently expressive GNN can learn the same repre- sentations for two links and only if their structural roles are the same within the graph. This way, (U1, 02) and (v1, ()) will be predicted differently in Figure [ We further show that SEAL is such an example. Finally, we give a more practical definition of isomorphism, called local isomorphism, which defines two nodes/links isomorphic if their local neighborhood subgraphs are isomorphic. We argue that GNNs for link prediction should target on pitiissoooopissmiiiiiiiiiiii
Figure 1: The structural roles of link (v1, v2) and link (11, va) are different, hut GAE will assign equal probabilities to them.
We conduct thorough comparison among different link prediction methods, including SEAL and various GAE and emhedding methods, on the recent large-scale Open Graph Benchmark (OGB) datasets (Hu et al., 2020)). We show that SEAL with the labeling trick has up to 195% higher Hits@ 100 than GAE methods, achieving new state-of- tf-t---rrt results on 3 out of 4 datasets.
2 PRELIMINARIES
In this section, we formally define the notions of graph, permutation, isomorphism, and GNN.
Definition 1. (Graph). We consider an undirected graph G (V. A), where V = (1.2..... n) is the set of vertices, E S V x V is the set of edges, and A E Ruxnnk contains the node and edge features with its diagonal components A denoting node attributes and off-diagonal components Ai.j. denoting edge attributes. We further use A E 10,1)xxm to denote the adjacency matrix of G with A.,; = iff (i,j) E E. If there are no nodeledge features, we let A A. Otherwise, A can be regarded as the first slice of A. i.e., A AA...
Definition 2. (Permutation) A node permutation æ is a bijective mapping from {1, 2, 11.2,....7. n2 to {1. 2....... n]. All n! possible πT'S constitute the permutation group II, We define (S)) = { S} when S is subset of {1,2.....n) ..]. We further define the permutation of A as ((A), where T (A) ((())x)); = A....- In other words, T (A),,, A)) (J).:"
Definition 3. (Set isomorphism) Given two n-node graphs G = (V,E,A), G = (V'E', and two node sets S C V, S' C V', we say () and (5", A') are isomorphic (denoted by (S. A) ~ (S', A Ef E IIn such that S = (S') and = A=x(AA) (AA).
When (V,A) (V', A'). we say two graphs G and G' are isomorphic (abbreviated as A A' because V = <VV)) 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 a specific subset S to another subset S'. When S C V and S C V', we are often more concerned with the case of A = A', where we are to find isomorphic node sets in the same graph (automorphism). For example, when S = {i), S' = {i} (single node case) and (i, A), (j. A) are isomorphic, it means i and j are on the same orbit of graph A (i.e., they have symmetric positions/same structural roles within the graph). An example is U/ and 13 in Figure
Definition 4. (Invariant function) A function f defined over the space of (S, is invariant if VI E II, f(S, A) = f(x(S), (A)).
Definition 5. (GNN) GNN is an invariant function mapping from the space (S, A) to Rd. More specifically, a GNN first performs multiple invariant message passing operations to compute node embedding 2; = GNN(i, A) for all i E S, and then performs a set aggregation (pooling) over {z,li E S). written AGG( (z; E S)), as the set S's representation GNN(S, A).
Note that, when |S| = 1, the set aggregation is often an identity mapping. In graph classification (S = V), we use graph pooling layer over node embeddings to compute the graph representation.
2

---

Under review as a conference paper at ICLR 2021
3 GAE AND STRUCTURAL LINK REPRESENTATION
In this section, we review how GAE methods predict links, and show that simply aggregating node embeddings learned by a GNN cannot lead to effective link representations. We use A to denote the incomplete network to perform link prediction.
3.1 GAE FOR LINK PREDICTION
Graph Autoencoder (GAE) methods (Kipf & Welling 2016b) first use a GNN to compute a node embedding 2, for each node and then use fzz 2j) to predict the link (i.
A.j ((z; 2j); where 2; GNN A), 2j GNN(Ú.A)
(1)
where A. is the predicted score for link (i.)). The model trained maximize the likelihood of reconstructing the true adjacency matrix. The original GAE uses two-layer GCN (Kipf & Welling 2016a) as the GNN, and let f(z, := (x 2,). In principle, we can replace GCN with any message passing neural network (Gilmer et al. 2017), and use an MLP over the aggregation of z; and 2j as the [(2,, 2z). Popular aggregation functions include concatenation, mean and Hadamard product, etc. In the following, we will use GAE to denote general class of GNN-based link prediction methods, without differentiating the specific choices of GNN and f.
3.2 GAE CAN LEARN STRUCTURAL NODE REPRESENTATION
Following (Srinivasan & Ribeiro 2020 Li et al. 2020), we first define most expressive structural representations for nodes and links. Then we relate them to GAE-leamnd node embeddings and show that GAE is not capable of learning structural link representations.
Definition 6. Given an invariant function r(.), r(S, A) is most expressive structural representa- tion for (S,A) A) if V(S, A, S", A'), I(S, A) r(S", A') = (S. ~ A')
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 I(í, A) a structural node representation for i, and call [(fi,j), A) structural link representation for (i.
The above definition indicates that two node sets have the same structural representations if and only if they isomorphic to each other. In the same graph A, structural representations uniquely mark the structural roles of nodes or node sets. This is in contrast to positional node embeddings such as Walk (Perozzi al. 2014) and matrix factorization (Mnih & Salakhutdinoy, 2008), where two isomorphic nodes can have different node embeddings (Ribeiro et al. 2017).
So why do need define structural representations? From node classification point of view, it is because two isomorphic nodes in a network are perfectly symmetric to each other, and should be indistinguishable using any labeling functions on graphs (i.e., they should have the same ground truth y). Learning structural node representation can guarantee that isomorphic nodes are always classified into the same class.
Then, a natural question to ask is, do GNNs learn structural node representations? The answer is no. Recall that (i, A) ~ (j,A)= = A A'. If a GNN can learn structural node representations, can always use it for graph isomorphism test by checking whether there exist two nodes in two graphs sharing the same structural node representation. In fact, existing GNNs' graph discriminating power is bounded by the Weisfeiler-Lehmer (WL) test (Morris et al.) 2019 Maron et al., 2019), which provably fails to distinguish certain non non-isomorphic graphs (Cai et al. 1992). Despite this, GNNs/WL. still powerful enough to learn representations that can distinguish almost all non- isomorphic nodes and graphs (Babai & Kucera 1979).
For easy analysis, we assume there exists a node-moste mnde-most-expressiiie GNN that output structural node representations thus able to distinguish all non-isomorphic nodes. Despite this, the techniques will present are not limited to eeeepesss-e GNNs, but also benefit practical GNNs.
Definition 7. A GNN is node-most-expressive if V(i, A. A'), GNN(I, A) GNN A') (i, A) = (j. A').
3

---

Under review as a conference paper at ICLR 2021
Recall that GAE first uses a GNN to compute node embeddings. Therefore, GAE with node-most- expressive GNN is able to leverage structural node representations for link prediction.
3.3 GAE CANNOT LEARN STRUCTURAL LINK REPRESENTATIONS
The next question to ask is whether GAE learns structural link representations. That is, does the aggregation of structural node representations of i and j result in a structural link representation of (i.j)? The answer is no, shown in previous works (Srinivasan & Ribeiro 2020 Zhang & Chen 2020). We have also illustrated it in the introduction. In Figure we have two isomorphic nodes t2 and vg thus 02 and V3 will have the same structural node representation. By aggregating structural node representations as link representations, GAF will assign (U1,"2) representation and predict them to have equal probabilities of forming link. However, (U1, U2) and (U1, v3) apparently have different structural link representations, which indicates that
722) and (U1, U2) the same link
Proposition 1. Even with a node-most node-moos--eppressvvv CNN, GAE cannot learn structural link represen- tations.
The root cause of this problem is that GAE learns representations for the source and target nodes individually, without considering their relative positions and associations. For example, although 22 and Uy are perfectly symmetric in the graph, when considering the source node in to predict link from, U2 and tiy's 's positions w.r.t. U1 are no longer symmetric.
HOW TO LEARN STRUCTURAL LINK REPRESENTATIONS?
In this section, we discuss how to enable GNNs to learn structural link representations with simple labeling trick, and show that SEAL valid example to learn structural link representations.
4.1 LABELING TRICK
We first introduce the labeling trick. Definition 8. (Labeling trick) Given (S, A). we stack a diagonal labeling matrix I(S) E Raxx in the third dimension of A to get new A E (xxxx(*+1), where satisfies: VT In (1)
((5) (())))) = S T(S).. and (2) ((S") A =(A') = [()) =(I(5"), A simplest labeling trick is to let (S) if E S otherwise 0.
Note that the notation À should actually depend on S. For convenience, we omit such dependence on S and infer it from the context. The first condition in Definition Definition&Jrqquires the labeling matrix to identify the target node set S; and the second condition requires the labeling trick to be permutation cquivariant, i.c., when (S, A) and (S", A') are isomorphic under R,, the corresponding nodes i (J) always have the same label. Essentially, the labeling trick distinguishes nodes in S from the rest nodes. It can be as simple as only giving label nodes in and otherwise O. Next, we show that with the labeling trick, a node- node-most-expressin GNN can learn structural link representations.
Theorem 1. Ifa GNN is
then with an injective set aggregation function AGG in Definition 5 GNN(S, A) = GNN(S", A') <> (S,A) = (S', A') for any S, S' A'.
We include all the proofs the appendix. Theorem 1 implies that GNN(S, A) a structural rep- resentation for (S, A). Recall Definition 5 defines GNN A) = AGG (OGG((GNNNNN A)li E S)). The above theorem indicates that although directly aggregating structural node representations learned from the original graph A does not lead to structural link representations, an injective aggregation over the structural node representations learned from the labeled graph À does lead to structural link representations. How intuitively
possible? Let's return to the example Figure T. When we want to predict link (#1, 12), we can mark U1, 2/ with a different label from the rest nodes, as shown by the different color in Figure computing 's embedding, it is also "aware" of the source node U1, instead of the previous agnostic way that treats U1 the same as other nodes. And when we want to predict link (E1, Uy), we can again mark vi, Vy with different label, as shown in Figure right. right. This way, U2 and 's structural node representations are no longer the same in the two differently labeled graphs because of their different relative positions w.r.t. U1, and are able give different predictions to (vi, v2) and (31,
2 left. With the source and target nodes labeled, when the GNN is
4

---

Under review as a conference paper at ICLR 2021
When predict (vi, U2). will label these nodes differently from the rest, that a GNN is aware the target link when computing vi and us embeddings. Similarly, when predicting (vi, vs). nodes on, Uy will be labeled differently. The aggregated embedding of U1 022 in the left graph will be different from the aggregated embedding of v1, Va in the right graph, cnabling GNNs to predict (V1, 22) and (vi, va) differently.
Figure 2:
4.2 SEAL CAN LEARN STRUCTURAL LINK REPRESENTATIONS
In this section, we will review SEAL Zhang & Chen 2018 et al. 2020 and show that SEAL exactly uses valid labeling trick that is able to learn structural link representations.
SEAL first extracts an enclosing subgraph (h-hop ego-network) around the link to predict.
Definition 9. (Enclosing subgraph) Given (S, A), the h-hop enclosing subgraph As of S is the subgraph induced A by Uses( (i j]((jj, i) S h), where d(j, i) is the shortest path distance between nodes} and i.
Then, SEAL applies Double Radius Node Labeling (DRNL) to give an integer label each node within the enclosing subgraph. DRNL assigns different labels to nodes with different distances w.rt. both the source and target nodes, where the source and target nodes are always labeled and nodes farther away from the source and target nodes get larger labels (starting from 2). For example, nodes with distances and I to the source and target nodes will get label 2, and nodes with distances and 2 to the source and target nodes will get label 3. So on and so forth. Finally the labeled enclosing subgraph is fed GNN learn the link representation and output the probability of link existence.
It can be easily proved that DRNL satisfies the definition of the labeling trick, because node distances are invariant under permutation. DRNL not only differentiates the source and target nodes from the rest, but also differentiates nodes of different distances to the source and target nodes. The DRNL-llbeled graphs also satisfy Theorem [ and thus can enable node- mose-expressiiveeee GNN to learn structural link representations. Moreover, SEAL's distance-based node labeling scheme formalized into distance encoding, or DE, in (Li et al.) 2020), which theoretically shows that encoding distances between nodes can increase the representation power of normal GNNs.
SEAL only uses subgraph As (h) within h hops from the source and target nodes instead of using the whole graph. This is for practical concerns (just like GAE typically uses less than 3 message passing layers in practice), and will be discussed in detail Section 5 When h -> oc, SEAL can also leverage the entire graph and learn structural representations for (S, A):
Proposition When h oo, SEAL can learn structural link representations with a node-most- expressive GNN.
Note that although we show a to learn structural link representations, even without a node-most-expressiv GNN, the labeling trick can still benefit most link representation learning tasks. For example, in Figure 2 long as a normal GNN can give different embeddings to and ey in the left and right graphs (which easy for most GNNs), we can still differentiate link (v1, U2) from link (V1, Uz). And this is not possible for GAF.
GNN combining with the labeling trick is able
Despite the power, the labeling trick introduces extra computational complexity. The reason that for every link (i.j) to predict, we need to relabel the graph according to (i. The same node i will be labeled differently depending on the target link, and will be given a different node embedding by the GNN when it appears in different links' labeled graphs. This is different from GAE, where do not relabel the graph and each node only has a single embedding vector. For graph with n nodes and m links predict, GAE needs to apply the GNN (n) times compute embedding for each node, while SEAL needs to apply the GNN (m) times for all links. When m worse time complexity than GAE, which is trade-off for learning structural link representations.
> n, SEAL has
5

---

Under review as a conference paper at ICLR 2021
5 LOCAL ISOMORPHISM: A MORE PRACTICAL VIEW OF ISOMORPHISM
In the previous analysis, we have assumed there exists node-most--xpreesivee GNN that can dis- criminate non-isomorphic nodes. Although a practical GNN can also discriminate almost all non- isomorphic nodes, there is little research discussing how reach this discriminating power. In this section, we analyze GNNs for link prediction from a more practical point of view.
Practical GNNs usually simulate the 1-dimensional Weisfeiler-Lchman (1-WL) test (Weisfeiler & Lehman 1968) to iteratively update each node's hidden state by aggregating its neighbors' states (we call them I-WL-GNN). One most powerful I-WL-GNN is the Graph Isomorphism Network 2018), which achieves theoretically the same discriminating power as 1-WI.
(GIN) (Xu et al.
Although showing 1-WL-GNN's maximum discriminating power, previous GNN research has not discussed how many message passing layers are required to reach this theoretical power. We therefore introduce the following lemma.
Given a graph with n nodes, a most powerful I-WL-GNN takes up to O(n) message passing layers to discriminate all non-isomorphic nodes that I-WL can discriminate.
Lemma 1.
Lemma D suggests that 1-WL-GNNN needs a number of message passing layers of the same order as the number of nodes in the graph to reach its maximum discriminating power. However, prac- tical GNNs usually only use a small number of message passing layers (such as I or 2) while still achieving good performance. This perhaps suggests that in practice, we do not necessarily need to find nodes/links that are exactly isomorphic to each other. Instead, nodes/links which are locally isomorphic could even more strongly suggest they should be classified into the same class.
(h) Definition 10. (Local h-isomorphismm) (S, A, S" A'). (S, A) and (S', A') are locally h-isomorphic
each other if (S, A (l) = (S', )
For two sets S, S", if their tuples with their h-hop enclosing subgraphs (S, A and (S', A (1)) isomorphic, then we say they are locally h-isomorphic. We argue that this is a more useful defini- tion than isomorphism, because isomorphism requires the entire graph looks identical from two sets' separate views, which is often too strict in practice. If we use the strict definition of isomorphism, we may fail to identify a lot of nodes/links that actually have very similar neighborhood structures. In fact. Babai & Kucera (1979) prove that at least (n log n) nodes in almost all n-node graphs are non-isomorphic to each other. Therefore, it is less meaningful to only assign the same repre- sentations nodes/links when they are strictly isomorphic, and GNNs targeting on isomorphism- discriminating tend to overfit. In comparison, local /-isomorphism only cares about whether the h-hopp neighborhoods are isomorphic, which more realistic and allows better generalizability.
are
With local h-isomorphismm all our previous conclusions using the standard isomorphism definition GNN can be used to identify locally
still apply. For example, GAE with h--soomophiic nodes, but cannot discriminate locally i-moo-isommopphic links. And a node-most- expressive GNN with the labeling trick (SEAL) can identify locally h-isomorphic node sets, etc. cawnhoorpiim-dddiiinnatiiii
To enable GNN to focus on local boundary between the h-hop enclosing subgraph and the rest of the graph, and apply the GNN only to the extracted subgraph within the boundary (possibly use more than h message passing layers).
all we need to do is to set
Finally, we want to answer a question: in what chance node local h-isomorphissm also indicates link local h-isomorphism? If in a graph, two nodes being locally li-isomorphic almost always indicates their links with a third node are locally h-isomorphic,, then learning structural link representations with SEAL may longer be necessary, and using GAE to learn structural node representations may already be enough. In other words, we are interested in how often examples like Figure | appear in graphs. Fortunately, we have the following theorem, which shows that there enough links where only identifying locally h-isomorphic nodes is not enough.
Theorem 2. In any graphs with n nodes and without node/edge features, if the degree of each node in the graph is between 1 and Olog 26 n) for any constant O, then there exists w(n?) many pairs of nodes u, v such that u and u are locally h-isomorphic while there exists another node w such that (u, w) and (v, w) are not locally h-isomorphic.

---

Under review as a conference paper at ICLR 2021
Table I: Statistics and evaluation metrics of OGB link prediction datasets.
Dataset
#Nodes
#Edges
Avg. node deg.
Density
Split ratio
Metric
ogb1
$76,289
30,326,273
73.7
0.018%
70/20/10
Hits@ 100
ogbl-collap
235,868
1,285,465
8.2
0.0046%
92/4/4
Hits@
ogbi-da1
4.267
1,334,889
500.5
14.67%
80/10/10
Hits@ 20
ogbl-cilation
2,927,963
30,561.187
20.7
0.00036%
98/1/1
MRR
RELATED WORK
There are emerging interests in studying the expressive power of graph neural networks recently.
Xu et al. (0188) and Morris et al. (2019) first show that the discriminating power of GNNs per-
forming 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 (Morris et al. 2019 Maron
et al. representation power. Little work has been done to analyze GNN's node/link representation power.
2019: Chen et al. 2019). However, most previous works focus on improving GNN graph
Srinivasan & Ribeiro 2020) first formally studied the difference between structural representations
of nodes and links. Although showing that structural node representations alone cannot perform link prediction, their way of learning structural link representations is to give up GNNs and instead use Monte Carlo samples of node embeddings learned by network embedding methods. In this pa- per, we show that GNNs combined with simple labeling trick can as well learn structural link representations, which reassures using GNNs for link prediction.
Many works have implicitly assumed that if a model can learn node embeddings well, then combin- ing the pairwise node embeddings can also lead to good link representations (Grover & Leskovee 2016 Kipf& & Welling, 6b Hamilton et al. 2017). However, we argue in this paper that by con- sidering the source and target nodes explicitly with the labeling trick, we can aggregate better link representations from node embeddings. Li et al. (2020) studied one particular form of the labeling trick based on distance, and proved that distance encoding can improve I-WL-GNNS' expressive power, enabling them distinguish almost all (S, A) tuples sampled from r-regular graphs. In this paper, we do not focus on improving I-WL-GNNS' expressive power, but focus on how to enable a sufficiently expressive GNN to learn structural link representations in any graphs. We also provide a general definition of the labeling trick, and argue that a labeling trick as simple as only giving the source and target nodes 1 and other nodes 0 suffices enable structural link representation learning.
7 EXPERIMENTS
In this section, we compare SEAL, GAE methods, and network embedding methods on the Open Graph Benchmark (OGB) (Hu et al. 2020) datasets. We use all the four link prediction datasets in OGB: ogbl-ppa, ogbl col l ab, ogbl-ddi, and ogbl-ci tat ion. These datasets adopt realistic train//alidation/eess splitting methods, such as by resource cost in laboratory (ogbl -pa),, by time (ogbl-ccs 1opl-collass cab and ogbl-citate ion), and by drug target in the body (ogbl-ddi) They are also large-scall scale (up to 2.9M nodes and 30.6M edges), open-soureed, and have standard evaluation metrics, thus providing an ideal place to benchmark an algorithm's 's realistic link predic- tion 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, aver- aged over all the true source nodes. Both metrics are higher the better. The statistics are in Table [
Baselines.
We consider the following representative models. Except SEAL, all models first compute node embeddings from the original graph and use the Hadamard product between pairwise node embeddings as link representations. The link representations are fed to an MLP for final prediction.
MLP: Input node features are directly used as the node embeddings.
Node2vec (Perozzi et al. 2014; Groverr & Leskovec 2016): The node embeddings are the con- catenation of node features and Node2vec embeddings.
MF: Use free-paramtter node embeddings trained end-to-end as the node embeddings.
GraphSAGE (Hamilton et al. 2017]: A GAE method with GraphSAGE as the GNN.
7

---

Under review as a conference paper at ICLR 2021
Table 2: Results for ogbl oobl--collab.oobl-ddd ogbl-ddi and oobl-ciitation
ogbl-ppa @its@ (S)
egal-collab
agbl-ddi Hits@ 20 (8)
ogbl-cc libltcitation
Hi
MRR (9)
Method
Validation
Test
Validation
Test
Validation
Test
Validation
Test
MLP
0.46:20.00
0.461:000
24.02=1.45
19.27
28.98=0.14
29.04:0.13
Node2vec
22.53:10.88
22.26610:8
57.03
48.88.1054
32.9211.211
23.26.2.09
59.44-0.11
59,6410,11
MF
32.28+:4.28
32.29=00.4
48,96=0.29
38.86:0.29
33.70+2.64
13.68:4.75
53.11=5.65
53.16+5.65
GraphSAGE
17.24112.6
16.55=2.40
56.88
48.10:10.1
62.6210.37
53.90.4.74
82.17-0.86
82.2881084
GCN
18.45+1.40
18.67=1.32
52.63+1.15
44.75=1007
55.50+2208
37.07=5.07
84.49=1008
84.56+1.10
GCN+LRGA
25.75:42.8
26. 16:3552
60.88:0059
52.21
66.7510.58
62.30-9.12
65.05-0.22
65.05:0.22
SEAL
51.25++2.2
48.80=3.16
63.89=0.49
53.71:0047
28.49+2..9
30.56+3.86
85.09=0888
85.27:4091
GCN (Kipf & Welling 2016b); A GAE method with GCN as the GNN.
GCN+LRGA (Puny et al. 2020): A GAE method with LRGA-module--nnanee
GCN.
SEAL (Zhagg & Chen 2018): Learn link representations from labeled subgraphs via GNN.
All the GAE methods' GNNs have 3 message passing layers with 256 hidden dimensions, with tuned dropout ratio in 0.5). The GNN in SEAL follows the original paper, which has 3 GCN layers with 32 hidden dimensions each, with a tuned subgraph hop h in [1,2]. The ogbl-ddi graph contains no node features, so MLP is omitted, and the GAE methods here use free-parameter node embeddings as the GNN input node features and trained them together with the GNN parame- ters. For SEAL, the DRNL node labels are input to an embedding layer and then concatenated with the node features (if any) as the GNN input. More details are in Appendix D
Results and discussion. We compare the baselines' link prediction performance on ogbl "pa, Among them, ogbl-ppa is a protein-
ogbl-col lab, ogbl-ddi, and ogbl-citation protein association graph where the task is to predict biologically meaningful associations between proteins. ogbl-colle lab an author collaboration graph, where the task to predict future collab- orations. ogbl-ddi is drug-drug interaction network, where each edge represents an interaction between drugs which indicates the join effect of taking the two drugs together is considerably dif- ferent from their independent effects. ogbl-citate ion is a paper citation network, where the task is to predict missing citations. We present the ten-time average results in Table [] The results show that SEAL achieves the best performance on 3 out of 4 datasets. It outperforms GAE and network embedding methods, sometimes by surprisingly large margins. For example, in the chal- lenging ogb1 ppa graph, SEAL achieves Hits @ 100 of 48,80, which is over 50% higher than the second-best baseline MF which only has an Hits @ 100 of 32.29. In comparison, all GAE meth- ods achieve Hits @ 100 lower than 30. SEAL has 87%- % improvement over GAE methods in this dataset, which demonstrates the superiority of learning structural link representations over structural node representations for link prediction. SEAL also improves the state-of-the-as results for ogbl-cot 1olllllla lab and ogbi - iititttiinn on in both validation and test performance.
Nevertheless, we observe that SEAL does not perform well on ogbl-ddi. ogbl-ddi is consid- erably denser than the other graphs. It only has 4,267 nodes, but has 1,334,889 edges, which results in an average node degree of 500.5 and density of 14.67%. %. Interestingly, although SEAL is able to beat MF and Node2vec, it falls behind GAE methods with free-parameter node embeddings. One possible reason is that the nodes in ogbl-ddi are so densely connected that practical GNN with limited expressive power is hard to inductively learn any meaningful structural patterns. In compar- ison, the free-parameter node embeddings make GAE methods transductive and no longer focus on learning structural patterns, but focus on optimizing node embeddings. An interesting topic is thus how to improve structural representation learning on dense graphs, which we leave for future work.
8 CONCLUSIONS
In this paper, we have revisited the topic of using graph neural networks for link prediction. We reviewed two popular classes of methods, GAE and SEAL. We first showed that GAE methods cannot learn structural link representations by aggregating individually learned node embeddings. We further showed that combining with simple labeling trick, pode-most-expressii GNN can leam structural link representations, and SEAL is such an example. Experiments on 4 large-scale OGB datasets demonstrate the superiority of learning structural link representations with SEAL..
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):111230,,
2003.
László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In 20th Anmual Symposium on Foundations of Computer Science (sfes 1979), pp. 39-46. IEEE, 1979.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-55) 1999.
James Bennett, Stan Lanning, al. The netflix prize. In Proceedings of KDD cup and workshop, volume 2007, pp. 35. New York, 2007.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 13Xiv:131..6203, 2013.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-411 1992.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In Advances in neural information processing systems, pp. 4868 4879, 2019.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and funetion approximation with gnns. In Advances in Neural Information Processing Systems, pp. 15894-15902, 2019.
Hanjun Dai, Bo Dai. and Le Song. Discriminative embeddings of latent variable models for struc- tured data. In Proceedings of The 33rd International Conference on Machine Learning, pp. 2702- 2711, 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224-2232, 2015.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 022428, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1272-1272. JMLR. org, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems, pp. 1025-1035, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00663 2020.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39 43, 1953.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: 160.002077 2016a.
Thomas N Kipf and Max Welling. arXiv:1611.07308. 2016b.
Variational
graph auto-encoders. arXiv preprint
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding-desice provably
more powerful gnns for structural representation learning. arXiv preprint arXiv:2009.00142. 2020.

---

Under review as a conference paper at ICLR 2021
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:151100492 2015.
David Liben-Nowell and Jon Kleinberg. The link- lnk-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019-1031 2007.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167, 2019.
Andriy Mnih and Ruslan R Salakhutdinov. Probabilistic matrix factorization. In Advances in neural information processing systems, pp. 1257-1264, 2008.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. arXiv preprint arXiv: Ttt:::553.00555 2015.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In Proceedings of the 33rd annual international conference on machine learn- ing. ACM, 2016.
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, pp. 701-710. ACM, 2014.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. From graph low-rank global attention to 2-fwl approximation. arXiv preprint arXiv:2006.0788 078466 2020.
Yanjun Qi, Ziv Bar-Joseph, and Judith Mlenn-Sethhaamman. Evaluation of different biological data and computational classification methods for use in protein interaction prediction. Proteins: Structure, Function, and Bioinformatics, 63(3)490--500 2006.
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, pp. 385-394. ACM, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. JEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node em- beddings and structural graph representations. In International Conference Learning Repre- sentations, 2020. URL https: /ectps://openreeee http///wepeeeeeeeeeeeeeeeeeeeeea net/ www.mooodooooo.ooo...ooo..o.er.e S0x
Boris Weisfeiler and AA Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Pauchno--Technicceskkay Informatsia, 229):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 1 2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. arXiv preprint arXiv:1906.04817, 2019.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. In International Conference on Learning Representations, 2020. URL Utthtttss:///peeeeeza
net/ htt://orumm.ico wiw.:mmmddddxxxxxxxxxxxX
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, pp. 4438-4445, 2018.
10

---

Under review as a conference paper at ICLR 2021
A
PROOF OF THEOREM 1
Recall Definition defines:
GNN(S, A) = AGG((GNN(i A)li S})-
Thus, we only need to show AGG((GNN(i. A)ji S)) AGG([GNN(( A'i E iff A) (S', A)
To prove the first direction, we notice that with an injective AGG, AGN(, A)ji S}) AGG([GNN(i, A E s'H) U1 E S, 02 E S", such that GN A) = GNN( A') U1)
(2)
(U2 A') (because GNN is node-mmostexprrssive)
(3)
π E II, such that 01 T (02), À (À)).
(4)
Remember À constructed by stacking and I (8) the third dimension, where I(5) is a diagonal matrix satisfying: VT E n., (1) I(S) π (I(5') = (SS), and (2) n (S'). A (A')
( xI((s)) With À (AA)). have both
A = A==(A) AAA', (()) π ((((5))
Because 7(9) = =(((5)) = S = TS'), we have
AGG (GNN(,, A) E S)) = AGG((GNN(i, Ā') ('))
3 In, such that S ((S)), A =AA)
(5)
(S = AS', A')
(6)
Now we prove the second direction. We have:
(S, A) = (5", A')
3 E 1h, such that S = ={S"", A = =(A')
(7)
3 II, such that =(S'), (() ((( T(A')
(8)
E TT, such that #(S", À (À')
(9)
Yo E S, 8 E 01 π (122), have GNN(11 A) GNN(22. Ā')
(10)
AGG((GNN((1,) A) E S)) = AGG( 4')IEE
(11)
which concludes the proof.
B PROOF OF LEMMA
We first note that for a most powerful I-WL-GNN, after a message passing layer, gives different embeddings to any two nodes that 1-WL gives different colors to after one iteration. So we only need to show how many iterations 1-WL takes to converge in any graph.
Note that if nodes are given different colors by 1-WL some iteration (they are discriminated by 1-WL), their colors are always different in any future iteration. And if at some iteration, all nodes' colors are the same as their colors in the last iteration, then 1-WI. will stop (1-WI, fails to discriminate any more nodes and has converged). Therefore, before termination. 1-WL will increase its total number colors by at least I after every iteration. Because there are at most n different final colors given n-node graph, 1-WL takes most -1 O(n) iterations before assigning all nodes different colors.
Now it suffices show that there exists n-node graph that 1-WL takes O(n) iterations to verge. Suppose there a linked list n nodes (a path). Then by simple calculation, it takes [n/2]] iterations for 1-WL. converge, which concludes the proof.
11

---

Under review as a conference paper at ICLR 2021
C PROOF OF THEOREM 2
Our proof has two steps. First, we would like to show that there are w(n") nodes that are locally f--soomrrphic to each other. Then, we prove that among these nodes, there least wn) 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 and denote the subgraph induced by the nodes that are at most h--op away from G/a) (the h-hop enclosing subgraph of v). As each node is with degree
= Olog 1
n),, then the number of nodes in G!!) denoted by [V(G(")), ) satisfies
h Σ d' = o(d)) = O(lo - n).
IVGG S
We set the max K max.ev [VGG( and thus K= O(log= + n).
Now we expand subgraphs ! to G(e by adding K IV((!")) independent nodes for each node V. Then, all G(k) 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(5) = exp(O(log* n)) = o(n²-9)
Therefore, due to the pigeonhole principle, there exist n/o(n= G( are isomorphic to each other. Denote the set of these nodes as Viso. which consist of nodes that are all locally h-isomorppic to each other. Next, we focus on looking for other nodes to form locally h-non-isomoophie links with nodes V.S0-
w(n") many nodes whose
Let partition Viso Li=1VV Vi that for all nodes in Vi, they share the same first-hop neighbor sets. Then, consider any pair nodes u, u such that u, v are from different V/'s. Then, may pick one u's first-hop neighbor that is not v's first-hop neighbor. We know such w exists because of the definition of V,. As w is u's first-hop neighbor and is not v's first-hop neighbor, (u, w) and (v, w) are not locally 1-isomorphic and thus not locally h-isomorphic. Therefore, based on this partition, we know the number of node pairs such that there exists another node w making (u, w) and (u, w) not locally h-issmorphic is at least
Step 2.
q Y
II i-=
WII
V?
(12)
2
Because of the definitions of the partition, Σ [i] = Visol = w(n") and the size of each Vi satisfies
1 < Vi S d,, = O(log 25 n).
where is of the common first-hop neighbors shared by all nodes in Vi and duw is its degree.
By plugging in the range of [. Eq 12 leads to
Y (w(n O 1. n)) wn?2t).
2
which concludes the proof.
D MORE DETAILS ABOUT BASELINES
We include baselines achieving top performances on the OGB Link Prediction Leaderboard] All the methods have their open-sourced code and paper available from the leaderboard. We adopt the numbers published on the leaderboard if available, otherwise we run the method ourselves using the
12

---

Under review as a conference paper at ICLR 2021
open-sourced code. For the baseline GCN+LRGA, its default hyperparameters result in out of GPU memory on agbl-citat inn, even we use an NVIDIA V100 GPU with 32GB memory. Thus, have to reduce its hidden dimension to 16 and matrix rank to 10. It is possible that it can achieve better performance with a larger hidden dimension and larger matrix rank using a GPU with larger memory. Despite this, GCN+LRGA generally performs second to best among all methods.
We implemented SEAL using the PyTorch Geometric (Fey Lenssen 2019) package. Following the original paper (Zhang & Chen 2018), we adopt a SortPooling layer (Zhang et al. (018 after the GCN layers to readout the subgraph. For all datasets, SEAL only used fixed 1% to 10% of all the available training edges as the positive training links, and sampled an equal number of negative training links randomly. SEAL showed excellent performance even without using the full training data, which indicates its strong inductive learning ability. Due to using different labeled subgraphs for different links, SEAL generally has longer running time than GAE methods. On the largest ogbl-cital iercciattion on graph, SEAL takes about hours to finishing its training of 10 epochs, and takes another 28 hours to evaluate the validation and test MRR each. For ogbl-ppa SEAL takes about 20 hours to train for epochs and takes about hours for evaluation. The other two datasets finished within hours. We will release all our code for reproducing the experimental results.
13


Reviews:
[{"review_id": "zPdqbT9Ry7H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors tried to explore the key differences between two link prediction methods. However, some statements are not precise. \n\nThe example the authors provided in the introduction is not correct. The GAE will also assign them different probabilities. When we use GAE to learn node embedding in the graphs, we usually have two different inputs: (A) nodes in the graph have input features (B) nodes in the graph do not have features and we assign each a one hot vector. For both two cases, each node in the graph in Figure 1 is unique node. Even node v2 and v3 play the same role in terms of graph structure, they still have different node embeddings considering the node features.\n\nIt is worthy to discuss that why node embeddings learning from exisiting method cannot help SEAL. It can be seen from the experimental results in two SEAL papers[1][2] that the node embedding does not help improve performance.\n\n[1]Inductive Matrix Completion Based on Graph Neural Networks\n[2]Link Prediction Based on Graph Neural Networks", "extra_scores": {}, "extra_text": {}}, {"review_id": "yjAVW19WV5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper presents results of two popular classes of methods for graph neural networks.  Namely, GAE and SEAL.  The paper show results on the Open Graph Benchmark of several existing methods, and concludes that GAE cannot learn structural link representations while SEAL can. \n\nThe paper is descriptive in its presentation, and does a good work on detailing the ideas behind GAE and SEAL.  However, I felt the lack of a contribution on the paper.  As it stands, it reads more as a tutorial and presents key insights of existing methods.\n\nPros:\n- Clear explanations of existing work.\n\nCons:\n- No clear contribution over explaining existing approaches.\n- Experiments show existing results on OGB.\n- No results on the mentioned labeling trick are given.\n\nComments:\n- In Fig. 1 you mentioned that $v_2$ and $v_3$ will get the same representation through a GAE.  Did you train one and observed it?  It will be more conclusive if you show the results and the embeddings to validate your observation.\n\n- Your labeling trick depends on the set of nodes $S$ used.  However, how do you select such sets to produce the labeling? Are you sampling all possible subsets $S$?  Since this seems to be a form of contribution, it should be clear how to use it in any scenario.\n\n- In your experiments, due to the way the paper presents the label trick as the novelty, I was expecting to see the boost of performance of such trick on the existing architectures.  However, Section 7 presents results of existing approaches on the OGB.\n\nMinor comments:\n- \"Following (Srinivasan & Ribeiro, 2020; Li et al., 2020)\" should be a textual citation\n\nOverall rating:\nDue to the main problems stated, I cannot recommend the paper for publication at ICLR.  The manuscript reads more like a tutorial, which may be of interest for readers finding a summary of the advances.  However, as a paper advancing the field of graph neural networks I feel it lacking.", "extra_scores": {}, "extra_text": {}}, {"review_id": "qBiz8ADSDIc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper focuses on the link prediction task for graph neural networks. More specifically, it compares GAE and SEAL by providing theoretical evidence why GAE is not able to learn structural link representations, which as a result leads to suboptimal performance in the link prediction task. The paper also introduces a labeling trick that can help GNNs to learn structural link representations. \n\nStrong points:\n1. The paper is clear, easy to understand, and the definitions and theorems provide good reference and proofs.\n2. A deeper understanding of the link prediction task is indeed needed as a lot of GNN works are mostly using classification as the downstream task.\n3. It provides good argument and clear example why some GNN models would not work well in link prediction by showing that individually learning node representations cannot handle the case where two nodes appear in topologically identical neighborhoods in the graph. It also provides insights as to how to mitigate such issues.\n\nWeak points:\n1. The comparison is oversimplified and overly generalized. The paper mostly compares GAE and SEAL, but there are much more GNN models that should be compared.\n2. The sheer separation of GAE and SEAL model is not convincing. GAE and SEAL are both GNN models which follow the message passing and aggregation approaches. There's no clear argument or theoretical explanation how these two are fundamentally different. \n3. There are a lot of existing work that considers position in encoding nodes (such as position aware gnn [2]) and should be able to learn expressive structural link representations. The paper does not compare with them.\n4. The experiment does not cover the most recent models. In addition, more benchmark datasets should be used. For example, FB15K (this is a widely used knowledge graph link prediction benchmark dataset), PPI, WN18, etc. Since previous work on gnn link prediction uses  \nthose dataset, I'm expecting to see a more comprehensive comparison using those datasets. More dataset can be found here: https://paperswithcode.com/task/link-prediction\n5. The paper should also consider comparing with knowledge graph embedding models which are focusing on the link prediction task. There are also existing work that combine the idea of knowledge graph embedding with GNN models in link prediction [1].\n\nOther comments:\n1. In def 5, gnn does not always have an invariant function mapping, depending on the message passing operations used e.g. in the graph sage paper, there are comparison using lstm message passing operator, which is not permutation invariant.\n2. Section 3.1 mentions that the paper uses GAE to denote the general class of GNN-based link prediction regardless of the choice of GNN and aggregation function. However, research has shown that the specific choices of message passing operations and aggregations have significant impact on the expressiveness of GNN [3]\n3. Section 3.3 mentions that GAE cannot learn structural link representations, but from the example in fig1, it seems like this is caused by the graph isomorphism issue. there are existing work that can mitigate this issue, for example position-aware graph neural network [2].\n\n\nReference:\n1. Schlichtkrull, Michael, et al. \"Modeling relational data with graph convolutional networks.\" European Semantic Web Conference. Springer, Cham, 2018. \n2. You, Jiaxuan, Rex Ying, and Jure Leskovec. \"Position-aware graph neural networks.\" arXiv preprint arXiv:1906.04817 (2019).\n3. Xu, Keyulu, et al. \"How powerful are graph neural networks?.\" arXiv preprint arXiv:1810.00826 (2018).", "extra_scores": {}, "extra_text": {}}, {"review_id": "9VnYmids38L", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides theoretical analysis of graph neural networks for link prediction, following a number of recent papers that have developed the theoretical understanding of graph neural networks. For example, the work of Xu et al (ICLR 2019) draws on the Weisfeiler-Lehman graph isomorphism test to develop a theoretical framework in which to analyse the expressive power of Graph Neural Networks. In particular, they show that architectural features in common graph neural network models limit the expressivity with respect to problems of node and graph classification and show how one can construct graph neural networks whose expressivity matches the Weisfeiler-Lehmam test. In more recent work, Li et al (NeurIPS 2020) show that augmenting node features with a \"distance encoding\" enables a graph neural network to distinguish node sets in cases where the Weisfeiler-Lehman test fails. This submission is perhaps most closely related to this recent paper of Li et al.\n\nIn this work, the authors discuss how GAEs cannot always discriminate between links (node pairs), even when a GAE has maximal expressivity at the node level (it can generate representations which discriminate all non-isomorphic nodes). They provide an enhancement they call a \"labelling trick\" which can be used to enable GAEs to discriminate between node sets. With the labelleing trick, ach node in the GAE has an additional feature corresponding to a node set specific label. That is, when learning representations for a given node set S, this feature takes on a value which is dependent on the node set S and the graph structure. The authors show (Theorem 1) that this enhancement enables any maximally node expressive GNN (a GNN which can discriminate all non-isomorphic nodes) to discriminate between any pair of non-isomorphic node sets. The strong performance of SEAL, a recent SOTA method for link prediction, can be understood in the context of this result. \n\nAs a second theoretical contribution, the authors define a \"local-h isomorphism\" concept, which they propose can be used to explain why practical GNN implementations perform well, despite theoretically requiring the number of layers to be proportional to the number of nodes in order to distinguish all nodes that 1-WL can discriminate (in the worst case).\n\n**Positives**\nStudying the expressive power of Graph Neural Network architectures is an important topic, as can be seen by the increasing number of papers in machine learning conferences over the past couple of years. The analysis in this paper extends the theory with respect to the link prediction problem and provides theoretical justification for the strong performance of SEAL on link prediction benchmarks. \n\n**Concerns**\nHowever, I have some concerns regarding the novelty of the contribution and the significance of the main theoretical result (Theorem 1). \n1. The main methodological contribution in this paper is the concept of the labelling trick, which can be used to improve the representational power of GNNs and explain the strong performance of SEAL. This looks like a special case of the distance encoding method presented in Li et al (NeurIPS 2020). The authors cite this work but do not discuss how their labelling trick relates to the distance encoding. Li et al also provide an explanation of the strong performance of SEAL (as an instance of their distance encoding method) as well as using their analysis to motivate alternative models which give a small performance improvement over SEAL.\n2. The main theoretical result (Theorem 1) assumes the existence of a GNN with maximum node expressivity, in the sense that it can discriminate all non-isomorphic nodes in a graph. By my understanding, this architecture does not exist. Indeed, I believe Theorem 3.7 of Li et al (NeurIPS 2020) shows that the distance encoding method (which seems to be closely related to the labelling trick) is not sufficient for this. In my view, a more useful theoretical result would be something along the lines of Theorem 3.3 of Li et al, which illustrates how the distance encoding method improves the representational power of GNNs for a large number of graphs where methods bounded by 1-WL would fail.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study the expressive power of Graph Neural Network architectures for the link prediction problem and provides theoretical justification for the strong performance of SEAL on link prediction benchmarks. However, The reviewers think the paper needs to improve in several aspects before it can be published: 1. More clearly explain the theoretical analysis and contribution. 2. Extensive and in-depth discussion of the similarities with and difference to the work of Li et al. to show the novelty of current work. 
Decision: Reject