Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction
Authors: Yang Hu
Xiyuan Wang
Zhouchen Lin
Pan Li
Muhan Zhang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Link prediction is one important application of graph neural networks (GNNs). Most existing GNNs for link prediction are based on one-dimensional Weisfeiler-Lehman ($1$-WL) test. $1$-WL-GNNs first compute node representations by iteratively passing neighboring node features to the center, and then obtain link representations by aggregating the pairwise node representations. As pointed out by previous works, this two-step procedure results in low discriminating power, as $1$-WL-GNNs by nature learn node-level representations instead of link-level. In this paper, we study a completely different approach which can directly obtain node pair (link) representations based on \textit{two-dimensional Weisfeiler-Lehman ($2$-WL) tests}. $2$-WL tests directly use links (2-tuples) as message passing units instead of nodes, and thus can directly obtain link representations. We theoretically analyze the expressive power of $2$-WL tests to discriminate non-isomorphic links, and prove their superior link discriminating power than $1$-WL. Based on different $2$-WL variants, we propose a series of novel $2$-WL-GNN models for link prediction. Experiments on a wide range of real-world datasets demonstrate their competitive performance to state-of-the-art baselines and superiority over plain $1$-WL-GNNs.

Under review as a conference paper at ICLR 2023
TWO-DIMENSIONAL WEISFEILER-LEHMAN GRAPH NEURAL NETWORKS FOR LINK PREDICTION
Anonymous authors Paper under double-blind review
ABSTRACT
Link prediction is one important application of graph neural networks (GNNs). Most existing GNNs for link prediction are based one-dimensional Weisfeiler- Lehman (1-WL) test. As pointed out by previous works, 1-WL-GNNS by nature learn node-level representations thereby have poor expressive power links. Some node labeling methods relieve this weakness but introduce low efficiency. In this paper, we study a completely different approach which directly obtain node pair (link) representations based on iro-dimensional Weisfeiler-Lehne Lehman (2-WL) tests. 2-WI. tests directly use links (2-tuples) as message passing units instead of nodes, and thus can directly obtain link representations. We theoretically analyze the expressive power of 2-WL tests to discriminate non-isomorphic links, and prove their superior link discriminating power than 1-WL. Based on different 2- 2-WL variants, we propose series novel 2-WL-GNN models for link prediction. Experiments wide range of real-world datasets demonstrate their competitive performance to state-of-thed -fet---rr- baselines.
INTRODUCTION
Link prediction is a key problem of graph-structured data (Al Hasan al. 2006 Liben-Nowell & Kleinberg] 2007: Menon & Elkan 2011:: Trouillon et al. (016). It refers to utilizing node characteristics and graph topology measure how likely link exists between a pair of nodes. Due to the importance of predicting pairwise relations, it has wide applications in various domains, such as recommendation in social networks (Adamic Adar 2003)) knowledge graph completion (Nickel et al. 2015), and metabolic network reconstruction (Oyetunde et al.) 2017).
One class of traditional link prediction methods are heuristic methods, which use manually designed graph structural features of target node pair such as number of common neighbors (CN) (Liben Nowell & Kleinberg 2007), preferential attachment (PA) (Barabási Albert 1999), and resource allocation (RA) (Zhou et al. 2009) estimate the likelihood of link existence. Another class of methods, embedding methods, including Matrix Factorization (MF) (Menon & Elkan 201T) and node2vec (Grover & Leskovee 2016), learn node embeddings from the graph structure in transductive manner, which cannot generalize to unseen nodes or new graphs. Recently, with the popularity GNNs, their application link prediction brings a number of cutting-edge models (Kipf
& Welling 2016 Zhang & Chen 2018 Zhang et al. 2021 Zhu et al. 2021).
Most existing GNN models for link prediction are based on one-dimensional Weisfeiler-Lehman (1-WL) test (Weisfeiler & Leman 1968) Shervashidze et al. 201T). 1-WL test is a popular heuristic for detecting non-isomorphic graphs In each update, it obtains all nodes' new colors by hashing their own colors and multisets of their neighbors' colors. Vanilla GNNs simulate 1-WL test by iteratively aggregating neighboring node features to the center node to update node representations, which we call 1-WL-GNNSs With the node representations, 1-WL-GNNS compute link prediction scores by aggregating pairwise node representations. Graph Auto-encoder (GAE, and its variant VGAE) (Kipf) & WWlling 2016) is such model. However, 1-WL-GNNs can only discriminate links on the "node" level. This is illustrated by Figure left: V22 and Uy are symmetric nodes in the graph thus having the same representation by 1-WL-GNN, but links (V1, 02) and (01, U3)) are not symmetric. However, 1-WL-GNNs are unable to discriminate links (i), 22)) and (vy, U2)., though (v), 02) has a shorter path between them than (v1, U3). Although positional node embeddings random features alleviate

---

Under review as a conference paper at ICLR 2023
this problem, they fail to guarantee symmetrical links (such (U1, U2) and (va, vs)) to have the same representation.
In order to surpass 1-WL, plenty of link prediction models apply node labeling inherently, including
SEAL (Zhang & Chen 2018), Distance Encoding (Li et al. 2020), ID-GNN (You et al. (021), and some models for matrix completion (Zhang & Chen 2020) and knowledge graph completion (Trru et al. 2020). raises expressive power from "node" to "link" level by breaking the symmetry between the target node pair and other nodes during the message passing. Figure middle and right illustrated this effect. However, labeling also introduces challenge. It requires repeatedly applying GNN labeled subgraph for every link to predict thereby being inefficient. Therefore, we aim to develop novel GNN models with both full-batch link prediction ability and higher expressive power than 1-W
We propose completely different paradigm for link prediction. We construct GNNs based on two-dimensional Weisfeiler-Lehman (2- WL) tests, which we call 2-WL-GNNs. In 2-WL-GNNs, node pairs are used as the el- emental message passing units so that link representations directly obtained. Figure _ gives an illustration for a particular 2-WL. al- gorithm. We first theoretically study the link discriminating power of different 2-WL test variants, including the plain 2-WL, 2-FWL (Folklore WL), and their newly proposed local version. We show that 2-WL, 2-FWL and local 2-FWL are strictly more expressive than 1-WL for link prediction, while local 2-WL has equivalent power to 1-WL. Based on these 2-WL tests, we construct a series of 2-WL-GNN models. Despite all using node pairs to propagate messages, these models have different aggregation schemes, link discriminating power, time/space complexity, as well as drastically different implementations, which we discuss in Section 4 Extensive experiments on multiple benchmark datasets verify 2-WL-GNNS' power for link prediction. 2-WL-GNNs achieve highly competitive link prediction performance to state-of- the-art models including SEAL (Zhang & Chen 2018) and NBFNet (Zhu et al. 2021). while using significantly less time.
Figure I: I-WL-GNNs cannot distinguish links (vi, U2) and v3) in the left graph. With label- ing trick, I-WL-GNNs can distinguish them in their respective labeled graphs (middle and right).
In this paper, we aim to develop novel GNN models with both full-batch link prediction ability and higher expressive power than 1-WL..
2 LINK-LEVEL TWO-DIMENSIONAL WEISFEILER-LEMMAN TESTS
In this section we introduce various 2- WI. tests which directly use links message passing unit, and define their link-level expressive power. We denote a set by {.}. an ordered set (tuple) by (-) and a multiset by { to have repeated elements. We use [n] to denote the set 21,2,..., n).
2.1 k D-DIMENSIONAL
SEESFFILER-LEHMNEEE TESTS
k-dimensional WL test (k-WL) uses k-tuples of nodes as update unit. In each iteration, every k-tuple updates its color from its newly-defined neighboring k-tuples. There variants of k- algorithms: the plain k-dimensional WL (-WL) and the k-dimensional Folklore WL (k-FWL) CCa
al. 1992 Grohe 2017 Maron et al. 2019). Both k-WL and k-FWL update colors for k-tuples 82, ........ 8k) with $1.... Sy being nodes.
k &-WL defines neighborhood of k-tuple s as N(s)) = (Ni, N2(s) (((())))),,))))) where
(s)s) = (s1,.....511. s 8y.1. sk ss)]s' [m]]]
k-FWL has different definition of neighborhood. k- defines the jth neighborhood of as Nf(s) = ((i 82, 34), (51, ($1, sk). "t.....s-11.j]
j E [n] Essentially, &-WL and And the full neighborhood of s is given by ( = [N (s) F-FWL have the same nk neighbor tuples but differ in how these nk tuples are ordered and grouped.
2

---

Under review as a conference paper at ICLR 2023
This figure illustrates how local 2-FWL works for link prediction. It takes links as message passing units. Given link (a, prediet, it aggregates four orange link pairs in the first iteration (middle), where common neighbor d is learned. Then in the second iteration (right), it aggregates five green link pairs through link (a, c), where a 3-path (a, e, c, b) between a, is captured.
Figure 2:
They result in different expressive power between k- &-WL and k-FWL. In previous work k- k-WL and k- FWL's discriminating power for graphs has been studied that k-FWL has equal graph discriminating power (A: 1)-WL which is strictly stronger than k-WL. for l CCai al. 1992. Grohe 2017).
2.2 VARIANTS OF LINK-LEVEL WEISFEILER- LEEMMAN TESTS
Link-level tasks require representation of one several links within the whole graph. It is natural to investigate the
case as link representation can be directly encoded by its color in test. We use ( (e) to denote the color of link e == (p.g) E [n] x [n] at iteration Then, (e) in 2-WL and
2-FWL tests is updated respectively by:
(e) f(c (c), (c (u, 1u E [n]B. " (p, e (n]B))
(3)
(e) fF (e) 8 (cdt- c(t (p, (m]B):
(4)
where f are injective functions. For unlabeled graphs, we can take (e) to the indicator of whether exists in E. For labeled graphs, additionally consider the initial node features.
When the initial representation for link (p. q) is its edge indicator, 2-FWL can count the common neighbors between p, q by checking how many (1, 1) appear in the multiset. By iterating the third node u. it can actually learn all 3-node structures containing p,
Considering the space complexity and the locality of link prediction problems, also propose local version of 2- WL and 2-FWL tests:
Ht (t (p, up, v) E EB): (e) fr (d (e), He "u, E},
(5)
(e) = f/ (e) (c (dt clt-") u))
(u) (u, E (p.u) E}
(6)
Figure ?? shows how local 2-FWL works. In brief, local version of tests only include neighbouring links that are connected. It's formally different from the local k-WL proposed in (Morris et al. 2019)
Note that such link-level WL test is different from graph-level tests as it directly output color of target units without pooling all units together. Though there has been results of k-WL power on graph isomorphism (Cai al. 1992). The discussion of their link-level expressive power is still missing.
To compare the link discriminating power of 1-WL and different 2-WL variants, we first formally define L-WL-indistinguissaable and 2- WWW--nndistinnuishhbll.
Definition 2.1. [1-WL-indistinguishbbbe Let G EV, == (V', be two graphs, and = (81, 82, ..., 9k), = (sh, s.,,.,, s'r) be two equally sized node tuples, where sj E V, 82,
s/ E V", VjE E [k]. Let cl (i) denote the color of node i after steps of 1-WL update. If
(81, E = (5) E E', Vi,j E [k], and c (s,)
(7)
Vj e [k], Vt 2 0,
(8)
we say (s, G) is L.WL-inndistinguishabll from (s', G'), denoted by G) 2-WL (s).
Note that we are more concerned with the case G = G², = |s'| 2, where we aim to discriminate node pairs (links) the same graph.
3

---

Under review as a conference paper at ICLR 2023
Definition 2.2, (2-WL-indistinguuishhhbb Given graphs G = EV, G' (V', E',,", ,E',") and links e V2, e' (p',g') E (e) the color of after steps 2-WL update, if
(e) = (o V2 0,
we say (e, G) is 2- WL--inddsstiigguishaalll from (e', G"), denoted by (e, 22-WL (c', G').
Similarly, define indistinguishable property for other 2-WL variants that take links update units. Note that for WWL-indistinguishable we only consider the link case, but it can be generalized arbitrary node tuples. Given Definition 2. and Definition 2.2 it possible compare the link discriminating power between 1-WL and 2-WL tests. Below we formally define the relative link discriminating power.
Definition 2.3. (Discriminating Power) Given two lests al and B, if ol distinguishes (e, G) and (e', G¹) only if B distinguishes (e, and (e', G') for any e,e', G.G', and there exists some e1, G,,
G1, G42 such that (1),G1) distinguishable from (e', G)) by B but not by s, then we say test 2 has stronger link discriminating power than test s, denoted by sf 2 B. If of distinguishes (e, G) and (e', G') if and only if 3 distinguishes (e, G) and (e', G') for any e, e' G, G' we say test of has equivalent link discriminating power to test B, denoted by st ~ B.
The set of all link-level tests becomes a partially ordered set with relation <. Now we are able to compare the link expressive power between 1-WL and 2-WL variants.
THE POWER OF 2-WL TESTS FOR LINK PREDICTION
In this section we theoretically characterize the link discriminating power of different 2-WL tests by comparing them with each other and 1-WL. We summarize our results in Table
3.1 2- 2L AND 2-FWL TESTS HAVE STRONGER LINK DISCRIMINATING POWER THAN 1-WL.
We use 2-WL to specifically denote its plain version defined in (3) and 2-FWI. denote the Folklore version defined in (4). We have the following theorems.
Theorem 3.1. 2-WL has stronger link discriminating power than 1-WL.
Theorem 3.2. 2-FWI has stronger link discriminating power than 2-WZ.
Figure 3: Non-isomorphh links (vi, U2) and (va, 04) from their respective graphs can be discrim- inated by 2-WL but not by 1- WL. 2-WL can capture global features like graph size but 1-WL only captures local structures.
Theorem is proved by Theorem 3.3 and the example displayed in Figure The proof of Theorem 3.2 is included in appendix. The two theorems directly derive that 1-WL- 2-WL- 2-FWL. 2-WL is strictly stronger than 1-WL the link level because it still maintains the ability to capture global structure like un- connected component and the number of nodes rather than 1- WL. However, 2-WL still cannot discriminate links like (U1, U2) and (v), Uz) in Figure I or count common neighbors K (u, q)(u E [n]R, [. {
the two branches of neighboring links (p. l E [n]] from (p, q) are still independently aggregated. 2-FWI. integrates links (u.p) and vp (u, w)'s neighbours, therefore it has stronger link expressive power.
3.2 THE LINK DISCRIMINATING POWER OF LOCAL 2-WL AND LOCAL 2-FWL
2-WL and 2-FWL have higher link discriminating power than 1-WL. However, they also bring higher time and space complexity. Given a graph G = (V,E) where [V| = n and E = m, 1-WL takes O(m) time complexity in each iteration and occupies (n)) memory. For 2-WL, it requires O(n²) memory and ( time for each iteration, which unaffordable for large-scale graphs.
The local version of 2-WL and 2-FWL test denoted by 2-WL and 2-FWL, relieve this question. They reduce the neighborhood scope from global to local thereby leveraging the graph sparsity and reducing the complexity. The following theorem characterizes local 2-WL's discriminating power.
4

---

Under review as a conference paper at ICLR 2023
Theorem 3.3. 2- 2-WL, has equivalent link discrininating power 1-WL.
The whole proof is included in the appendix. The main idea is to establish an bijective mapping between the subtrees of 1-WL and those of 2-WL,. Intuitively. the two neighborhoods of (p.9) exactly correspond to the neighborhood of and in 1-WI..
Now we characterize the expressive power of 2-FWI-L.
Theorem 3.4. 2-FWL1 has stronger link discriminating power than 2-WL, but lower than 2-FWL.
The proof is included in the appendix. The rationale is similar that 2-FWL, test groups neighbor links by the shared nodes u, thus capturing higher-order information than 2- 2-WLz, and that 2-FWL, integrates only local information than 2-FWL.
Summarizing previous results, we depict a full picture of the relative link discriminating power of all the tests in Table In general, the origi- nal 2-WL. tests stronger than their local ver- sions, and the Folklore versions are stronger than the plain versions. All 2-WL tests except the 2- WL are stronger than 1-WL. Although the local versions are less powerful, they bring significant complexity reduction, as well as pos- sibly more robustness and better generalizability for link prediction due to their focus on local structure patterns. Our experiments verify that local versions are usually not worse.
Table The below matrix shows relative link dis- criminating power of different tests, where de- notes equal power, < denotes weaker power, and denotes that both are not weaker than the other.
1-WI. 2-WL.1 2-WI. 2-FWI.1 2-FWI.
1-WL
2 2
2-WL.1
2-WL.
2-FWL.1.
2-FWL
4 IMPLEMENTATION BY GNN MODELS
We first use 1-WL-GNN to learn node embeddings with the raw node features inspired by (Morris al. 2019). If raw node features don't exist, we take embeddings of node degrees to keep the inductive property of our model. Then, we obtain the initial link representations by pooling the pairwise node embeddings. Then we implement four link-level 2-WL tests through GNNs in a totally different way due to different neighborhood aggregation form and goal of complexity reduction.
4.1 GNN IMPLEMENTATION OF 2-WL
Constructing a complete graph and apply traditional graph convolutions suffers from O(n²) time complexity unaffordable for large graphs. Therefore, we construct our own aggregation and combination functions. We group the link representations in the tt step into n X tensor (t)),
where the p. indexed vector Ap.. is the representation link (p, 4). For (()), we also include the adjacency matrix as one slice. Then A(++1) is computed by:
B(t) concat ( Σ p.g.:
9(4 P.R.
h( h(A()) ())), (Aggregation) [
Σ
(10)
((+1) f (concat( (())) (Combination)
(11)
where f.g.h are MLPs. Given the ordered node pair (p, q). in each layer we apply two distinct transformations g and respectively aggregate its neighbors fl (u, E [n]]]. {(, v)le [n] B- Directly operating on the dense link representations A saves us from explicitly constructing the complete graph, and allows using MLP to implement the model. The whole algorithm takes ( time and Onn²r) memory.
4.2 GNN IMPLEMENTATION OF 2-
Local 2-WL is realised differently from 2-WL. Due to the reduced neighborhood, is possible to leverage the graph sparsity to memory and time. In training period, let S be the mini- batch containing all positive and negative target links to predict, E' be the existing edges in the original graph (after removing the positive training links). Then construct second-order graph
5

---

Under review as a conference paper at ICLR 2023
( where E(2) denotes "edges" between E' S based the neighborhood definition of 2- 2- We then apply graph convolution on Gg to obtain node representations for S which are used to output their link prediction scores in the original graph. The second-order graph has O((FF) + [S()d) edges, where is the max node degree in the original graph. Therefore, the time complexity of message passing follows to he O(( F'| [S()dr2), where is the hidden dimension. Memory efficiency is also largely improved to O((E') + [))rr).
4.3 GNN IMPLEMENTATION OF 2-FWL
The situation becomes bit more complex for 2-FWL. The join of two links is difficult to implement by standard graph convolution layers. Thus, we apply a model similar to that proposed in Maron et al.) (2019). In each layer, we apply slice-wise matrix multiplication of two reshaped link representation tensors to implement the 2-FWL message passing.
B p.g.:
E
((4 P.i.:
@ h(A Lg:h
(Aggregation)
(12)
iEin]
1 = { (B(t), A()) (Combination)
(13)
where @ is element-wise product and f. are MLPs. The above implementation first joins link representations of (p. and (i. q) through element-wise product, and then performs the aggregation through summing. We also add adjacency matrix into the first layer.
Because 2-FWL uses batched matrix multiplication, has time complexity O(n'r + =22²) and space complexity (n²r), with the third dimension of A It seems to be slower than 2-WL model, but batched matrix multiplication can be efficiently computed in practice.
4.4 GNN IMPLEMENTATION OF 2-FWL.1.
For local 2-FWI., the implementation is the same as 2-FWI. except that we replace the dense matrix multiplications in Equation (2) with sparse matrix multiplications, i.c., initially only those entries Ap.. corresponding to existing edges (p. g) E have nonzero values, and at the tt message passing step we still only track those nonzero p, q entries. We also concatenate n x n x adjacency matrix to embedding in each layer.
Note that this implementation doesn't 't perfectly follow the definition of 2-FWL, in 6 and therefore cannot learn representations for all (intermediate) links (which may fails to cover questioned links). Thus, we concatenate the final link representations with node-pair representations learned by a 1-WL- GNN to give nonzero representation to any questioned link. Although this implementation does not preserve the full representation power 2-FWLL can still learn common neighbor and path- counting features between nodes, and most importantly, it significantly reduces the space complexity from (nnrr) to Omd''r), with d max node degree, number of layers, r hidden dimension.
5 RELATED WORK
Seisfeiler-eehmall tests are family of algorithms to deal with the graph isomorphism problem Cai et al. 1992). In addition to graph isomorphism checking, they have found many applications in machine learning recently (Morris al. (2221) Shervashidze et al. (201T)
the idea construct subtree-based graph kernels. NNepert et al. (2016) and (Zhang & Chen 2017b) use WL to sort nodes and construct neural networks for graphs. Vanilla GNNs have also been shown have limited graph discriminating power bounded by 1-WL (Xu et al. 2019). Many works focus on how to improve GNNs' power by considering high-dimensional WL tests. Morris al. (2019) introduce GNN models simulating 2-WL and 3- WL tests. Maron et al. (2019); Chen et al. (2019b) achieve the same graph discriminating power as 3-WL with a 2-FWL based model. However, these works all deal with the whole-graph representation learning problem. Little work has been done in the link prediction context. The graph-level tasks mainly work on small graph when encoding high- graph structure, but graphs for link prediction be extremely large and more attention should be put their local property. Therefore whether the 2L based models work well in link-level tasks and how to design their variants adapt the locality valuable questions. In this work, also for the first

---

Under review as a conference paper at ICLR 2023
time demonstrate both the theoretical and practical power of 2-Wsed GNNs for link prediction, therefore filling in this blank area.
In the community of using GNN models for link-oriented tasks, various techniques have been proposed to enhance their theoretical power. SEAL (Zhang & Chen 2018) utilizes a distance-based node labeling trick to label the context nodes according to their relationships the target link, which is later formalized into distance encoding (Li et al. 2020). Zhang et al. (2021) further proved that such a labeling trick brings theoretical improvement GNNs' link discriminating power. However, using labeling tricks requires extracting a subgraph for each link and repeatedly applying GNN to the subgraphs, which incurs high computational complexity and prevents full-batch learning. In contrast, our models aim to still apply GNN only once to the entire graph like the traditional GAE methods, while outperforming GAE in terms of link discriminating power: NBFNet (Zhu et al.) (02T) uses type of partial labeling trick which only labels the source node and applies a GNN to predict all links from the source node. Although it does not need to extract a subgraph for every link, needs to apply GNN to large graph for each source node and suffers from low training efficiency. On the basis of SEAL, Pan et al. (2022) encode a transition matrix serving as form of pairwise encoding for each link in the subgraph. However, it still requires extracting subgraphs for all links to predict.
Given original graph G, line graph L(G) represents the adjacency between edges. In L(G), each node corresponds to unique edge in G. By using node representation learning methods (Kipf & Welling 2017) on the line graph, some methods (Zhu et al., 2019 Chen et al., 2019a, Diang et al. 2019] Cai al.; 202T: Liu et al.. 2021) can utilize edge features and topology better, which have achieved outstanding performance on graph tasks like heterogeneous graph learning, community detection, graph classification, and link prediction. Using I-WL-GNNS on line graphs is similar to local 2-WL. However, none of these previous works have noticed the connection between line graph and 2- 2-WL tests. Furthermore, more expressive variants like 2-FWL are not studied.
6 EXPERIMENTS
In this section, we conduct experiments to verify the effectiveness of 2-WL-GNNS for link prediction. We test 2- 2-WL-GNNs based on the proposed four tests: 2-WL, local 2-WL (2-WLL). 2-FWL, and local 2-FWL (2-FWL,). Since these methods do message passing among two-node tuples rather than sets, they can do prediction tasks on both homogeneous graph data and knowledge graph data. To predict the edge between nodes q in former condition, we simply pool (p, q) and pj's embedding to obtain {p. 9)' 's embedding the prediction score. Hyperparameters include learning rate, hidden dimension, number of message passing layers, and dropout rate. Baseline results are taken from (Zhang & Chen 2018). (Liu et al. 202T) and (Zhu al. 202T)
6.1 HOMOGENEOUS GRAPH LINK PREDICTION
The baseline methods choose Matrix Factorization (MF) (Mnih & Salakhutdinov 2008).
Node2 (N2V) (Grover& & Leskovec 2016), Weisfeiler-Lehman Neural Machine (WLNM) Zhhng
& Chen 2017a), TLCC-GN ( Yan et al. 2021). 1-WI-GNNNs including VGAE (Kipf & Welling (016))
and S- SS-VGAR VGA (Davidson et al. 2018). and labeling trick methods including SEAL (Zhang & Chen
2018), NBFNet (Zhu et al.) 2021). WalkPool (Pan et al. (022) and Neo-GNN (Yun al.) 2221) We
use eleven benchmark datasets. Three of them are citation networks with node feature information:
Cora, CiteSeer and Pubmed (Sen al., 2008). The other eight datasets are: USAir, NS, PB, Yeast,
C.ele, Power, Router, and E.coli from SEAL, which are networks from different domains and do not contain node features. For each network, we randomly choose 10% edges as test set and 5% edges as validation set. The remaining are treated as the observed training graph. The same number of randomly sampled nonexistent links are added into each set as the negative data, The performance metric is area under the ROC curve (AUC). We run each model for 10 times and report the average performance and standard deviations. The results are presented in Table and 3
According to the results, our 2-WL-GNNs achieve generally better performance than the baseline models. Specifically, the 2- WL and 2- WL, models perform competitively with SEAL on a large number of datasets and the 2-FWL and 2WFL models obtain overall better results than SEAL. On citation networks our models also achieve competitive results among recent methods. As displayed in Table 3 2-FWI achieves new sfate-of-the-art result of 96.44 on Citeseer. On Cora and Pubmed,
7

---

Under review as a conference paper at ICLR 2023
Table 2: Performance on eight networks without node features
Datoser
WENM
2-WL.
2-WL.,
2-FNI
2-FWI.2
USAir
94.08-0.880
91,4411.78
89.28:1:199
95.95111110
97. 07.09:0.70
92.86.1 1.08
94.651
0.99
98.10.1
0.42
96.06.1 0.51
98.61-0.49
97.71=0.33
97.154
98.85
0.12
94.30:10.53
05.79.10.78
90.70:10.53
93.091047
20.31
93.5111
0.54
98,10.1 0.48
95007 0.87
91.71 0.54
Yeast
90.28=00.99
93.67
90.88=0.211
95.62=0522
57. 2..00:0666
95. 95.76 0.54
96.33 3.34
97.83 0.21
97.44 0.25
85.90::1.74
84.11
21,80:2.118
86.182:1.22
86.54:2200 2,04
81.724 2.15
83,342
2.35
91,25-1 3.82
88.681 1,34
50.63:1
76.22.10.92
1.65
84.7610.98
74.10.1 1,90
$1.02.1:
72.21
85.0010067
Router
78.03=11.66 1.63
65.46:20.86
61.51=1222 222
04.41
95 00.00811122
96,02+ 0.61
96.8
0.50
95. 34-4 0.79
94.91
Ecoli
00.56
00.82:1.449
9081:50.63
97.21
97.22
96.121 0.48
96.51 0.28
98.42 0.21
97.03 0.57
Table 3: Performance citation networks with node features. OOM: Out of memory.
Dalasel
VGAE
S-VGAE TLC-GNN SEAL NBFNet WalkPool Neo Neo-GNN
2-WL
2-WL2
2.FWL
2-FWL,
Cora
91.4
94.1
93.4
93.3
95.6
96.0
96.2
93.15+1.17
95.33+ 0.50
96.03+0.52
95.81=0.00
Citesoer
90.8
94.7
90.9
90.5
92.3
96.0
95.5
94,45++1001
92.10# 0.79
95.284
0.76 96.44-067
Pubmed
94,4
96.0
97.0
97.8
98.3
98.6
99.2
0OM
98.666 0.16 OOM
98.6920.09
2-FWL and 2-FWL1 also obtain second best results respectively. Their competitive performance verifies the effectiveness of directly using links as message passing units learn their representations.
Theoretically, both labeling trick methods and 2-FWL models are more expressive than 1-WL models like VGAE and S-VGAE, which is reflected in their performance comparisons. However, we found even 2-WL and local 2-WL models can sometimes outperform 1-WL-GNNSs by large margins, especially on networks without node features. This might be explained by that the direct learning of link representations and the message passing along edge adjacency might capture better edge topology than node-centered methods. Furthermore, we found that the global versions WI and 2-FWL do not always achieve better performance than their local versions 2-WL and 2-FWLL, despite being theoretically more powerful. This might be because the local versions focus more on local neighborhood around links, which is proved to contain the most useful information for link prediction (Zhang & Chen 2018). Considering the significantly larger memory requirement (OOM in Pubmed), recommend to use the local versions in most cases due their efficiency and scalability.
6.2 KNOWLEDGE GRAPH COMPLETION
we conduct an additional experiments to test 2-WL-GNNs link prediction performance on inductive knowledge graph completion (KGC). We adopt two datasets, FB15K-237 and WNI8RR from (Teru et al. 2020) to evaluate the performance. Each dataset includes four versions v1 to v4 with increasing sizes. The baselines we use state-of-the-ar inductive KGC methods including R- GCN (Schlichtkrull et al.] 2017), Grall. (Teru et af.) 2020), and a recent mnee-graph-bacc based model INDIGO (Liu et al.) 2021). We compare them with our GNN implementations of 2-WL, and 2-FWL, using three metrics: accuracy (ACC), area under the ROC curve (AUROC) and Hits @ 3. The results are given in Table Best and second- -t-bestt results are in bold and with underlines respectively.
As we can see, 2-FWLt generally achieves the strongest performance with 17 highest metric numbers out of 24, and second-to-best metric numbers among the remaining. This again verifies the higher link expressive power brought by the 2-FWL tests. On the other hand, 2-WL, and INDIGO perform competitively too. As discussed in the related work, INDIGO can be understood as special implementation of local 2-WL by leveraging line graphs. The excellent performance of 2- WL methods further verifies the advantage of directly learning link representations. Specifically, notice that these link-centered methods have much higher Hits @3 3 than the other node-centered basclines, indicating that link tink-centered methods are better at ranking the correct links at the top. This is especially important in woal-world applications where we only focus top-ranked predictions.
6.3 TIME COMPLEXITY ANALYSIS
Finally, we compare time complexity between local 2-WL models and labeling trick methods. For each model, we record the time to train an epoch as training, and the computation of prediction scores for all links of test set as the inference time. We use the default batch size: 10% of the number of all existed links in 2- WL models, 32 in SEAL (dynamic train/test), (64, 64, 16) for Cora. Citeseer, Pubmed respectively in NBFNet. Table 5 summarize the results. Best and second-to-ber results are in bold and with underline, respectively. The performance demonstrates that 2-WL. based models
8

---

Under review as a conference paper at ICLR 2023
Table 4: Performance on KG datasets (%). Higher the better.
FB15K-233
WNISRR
v2
vl
v3
v4
R-GCN
$1.0
51.3
54,9
52.1
50.2
52.7
52.2
48.4
GralL
69.0
80.0
81.0
79.3
88.7
81.2
75.7
86.4
ACC
INDIGO
84.3
89.3
89.0
87.8
85.7
85.8
84.3
85.4
2-WLz
85.7
93.2
90.0
91.1
84.7
86.5
79.9
86.8
2-FWL,
90.7
94.7
93.9
91.8
84.7
86.7
81.5
88.7
R-GCN
51.0
50.5
50,5
52.6
49.0
49.8
53.1
50.2
GralL
78.6
90.0
93.1
89.5
92.3
92.7
82.8
94.4
AUROC
INDIGO
93.4
96.3
96.6
95.8
91.2
92.5
92.4
94.7
2-WT-r
87.9
95.7
96.9
86.6
89.1
2-FWL..
95.3
98.2
97.5
96.6
92.8
93.3
8.599
95.4
R-GCN
2.4
3.5
3.3
2.1
11.0
24.5
8.1
GralL
1.0
0.4
6.6
3.0
0.6
10.7
17.5
22.6
Hits@3
INDIGO
53.1
67.6
66.5
66.3
98.4
97.3
91.9
96.1
2-WL,.
70.8
79.0
79.5
79.8
97.8
96.1
83.7
96.2
2-FWL,
71.5
84.2
81.7
78.3
97.4
85.2
97.3
Table 5: Time complexity comparison.
Training Time
Inference Time
Dataset
2 2-WL,,
2-WL
2-FWL, 2-FWL SEAL
NBFNet
2-WL, 2-WL
2-FWL, 2-FWL SEAL
NBFNet
Cora
0.54s
4.59s
9.18s
6.03s
8.44s
48.38s
0.007s
0.29s
1.45s
0.16s
2.30s
1.94s
Citeseer
0.90s
4.32s
5,85s
4.41s
7.69s
49.15s
0.006s
0.59s
0.74s
0.24s
2.11s
1.80s
Pubmed
13.05s
00M
38.43s
0OM
59.67s
3000s
0.05s
OOM
3.9s
OOM
15.4s
95s
have significantly lower time complexity than labeling trick methods. This is because local 2-WL models can predict all the target links by applying the GNN once to the entire graph, while labeling trick methods require repeatedly applying GNNs labeled graph for every target link source node to predict. 2-FWL., is relatively slower due to inefficient sparse matrix operation, but it brings space efficiency.
6.4 LIMITATIONS
A notable problem for 2-WL models is its scalability. Although we purpose local version of the plain 2-WL models, they still suffers from high space complexity and relatively low performance when dealing with large and dense dataset. On Power and Router with nearly 5000 nodes, our models perform not much better than baselines. On Pubmed with 19717 nodes and 44324 edges, 2- WL and 2-FWL used up 48GB memories and their local versions fail to outperform Neo-GNN. All of our models cannot work on OGBL. dataset due to the large size. One possible solution is using graph partition. Despite such weakness, 2- WL models obtain remarkable performance small graph and speed advantages.
7 CONCLUSIONS
This work studies a novel method for link prediction based on two-dimensional Weisfeiler-Lehman graph neural networks. The problems with the prevalent 1-WL based models long-standing. Even though node labeling fundamentally improve the theoretical power, it brings low efficiency training and inference process. 2-WL-GNN can resolve both challenges. Free of any labeling, it doesn't break the symmetry of the whole graph thereby having unique speed advantage. Meanwhile, we theoretically characterize the link discriminating power of different 2- variants, and show that except local 2- WL. all other tests have stronger power than 1-WI.. Besides, we further construct a series of GNNs implementing the 2-WL tests. They follows our proposed 2-WL's patterns and successfully exploit their expressive power. Experiments multiple benchmark datasets show the effectiveness of WL-GNNs for link prediction. Despite scalability problems for large dataset, our results shows their impressive performance small dataset in different tasks. More importantly, present a novel paradigm for link prediction with distinctive advantages, producing new direction to discover.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):111-230,
2003.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp.
2019.
Mohammad Al Hasan, Vineet Chaoji, Saeed Salem, and Mohammed Zaki. Link prediction using supervised learning. In SDM06: workshop on link analysis, coumter-terrorism and security, volume 30, pp. 798-805, 2006.
Albert-Láászóó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512 1999.
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 410, 1992.
Lei Cai, Jundong Li, Jie Wang, and Shuiwang Line graph neural networks for link prediction. IEEE Transactions Pattern Analysis and Machine Intelligence, pp. 1-1, 2021.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations, 2019a.
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, 32, 2019b.
Tim R. Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M. Tomczak. Hyperspherical variational auto-encoders. In Uncertainty in Artificial Intelligence, pp. 356-865. AUAI Press, 2018.
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, volume 47.
Cambridge University Press, 2017.
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, pp. 855- 865-864,77 2016.
Xiaodong Jiang, Pengsheng Ji, and Sheng Li. Censnet: Convolution with edge-node switching in graph neural networks. In Sarit Kraus (ed.), International Joint Conference Artificial Intelligence, pp. 2656-2662, 2019.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/ l..0061..0030888 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017 Conference Truck Proceedings, 2017.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 4478, 2020.
David Liben-Nowell and Jon Kleinberg. The link link- nre-predintion problem for social networks. Journal of the American society for information science and technology. 1117)10119-1011. 2007.
Shuwen Liu, Bernardo Grau, Ian Horrocks, and Egor Kostylev. Indigo: Gnn-based inductive knowledge graph completion using pair-wise encoding. Advances in Neural Information Processing Systems, 34, 2021.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
10

---

Under review as a conference paper at ICLR 2023
Aditya Krishna Menon and Charles Elkan. Link prediction via matrix factorization. In Joint european conference on machine learning and knowledge discovery in databases, pp. 437-452. Springer, 2011.
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, pp. 4602-4609, 2019.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt. Weisfeiler and leman go machine learning: The story so far. CoRR, abs/21 12.09992, 2021.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33 2015.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014-2023, PMLR, 2016.
Tolutola Oyetunde, Muhan Zhang, Yixin Chen, Yinjie Tang, and Cynthia Lo. Boostgapfill: improving the fidelity of metabolic network reconstructions through integrated constraint and pattern-based methods. Bioinformatics, 33(4):608 611, 2017.
Liming Pan, Cheng Shi, and Ivan Dokmanić. Neural link prediction with walk pooling. In Interna- tional Conference on Learning Representations, 2022.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. arXiv preprint 1rXiv:1703.06103, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al magazine, 29(3):93-93, 2008
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pp. 9448-9457. PMLR, 2020.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International conference on machine learning, pp. 2071-2080. PMLR, 2016.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 209):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? 7th International Conference on Learning Representations, 2019.
Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In International Conference on Machine Learning, volume 139, pp. 11659-11669, PMLR, 2021.
Jiaxuan You, Jonathan Michael Gomes Selman, Rex Ying, and Jure Leskovee. Identity-aware graph neural networks. In Proceedings of the AAAI conference artificial intelligence, pp. 10737-10745. 2021.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J. Kim. Neo-gnna Neighborhood overlap-aware graph neural networks for link prediction. In Advances in Neural Information Processing Systems, pp. 13683-13694, 2021.

---

Under review as a conference paper at ICLR 2023
Muhan Zhang and Yixin Chen. Weisfeiler-lemman neural machine for link prediction. In International Conference on Knowledge Discovery and Data Mining, pp. 575-583. ACM, 2017a.
Muhan Zhang and Yixin Chen, Weisfeiler-lehman neural machine for link prediction. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 575-583, 2017b.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. In International Conference Learning Representations, 2020.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34, 2021.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 7 71(4):623 630, 2009.
Shichao Zhu, Chuan Zhou, Shirui Pan, Xingquan Zhu, and Bin Wang. Relation structure-aware heterogeneous graph neural network. In IEEE International Conference on Data Mining, pp- 1534-1539. IEEE, 2019.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal A. C. Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In Advances in Neural Information Processing. pp.
2021.
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM 3.3
Theorem: 2-WL-,, has the same discriminating power as 1-WL for link prediction.
Proof. We measure the link discriminating power by constructing subtrees. Given an undirected graph G = (V, E,,, P. E V. denote edge indicator of (p, g) as (p-9)) and let Tor, Ta be mappings from sets of graph-link tuples (G, (p,4)) to sets of tree-structured graphs with infinite depth, which are defined as follows.
For graph G, P. 9 E G. [ Twe (G, (p. q)) has a root (p. q) labeled as (1(p), (()) ((-n)) with two branches of child nodes i(),)) i) E E, i E [n]} and {(i,4) (i,9) E E, j E [n]] in the left and right side, respectively. For every child node (r,s), it is labeled as (((r),(s)) Its child nodes and their labels are defined in the same way recursively.
Tea (G, (p. ()) has a root (p. q, ((n.)) which is labeled as (())).(g)). It has two branches of child nodes: (i: (p. i) E i E [n]] on the left and (j: (.. E R.j E [n]] on the right. In the following layers node k has children {l: (k, E E, E [n]]. Node k is labeled in the graph as ((k).
Then we define an equivalent class across the tree-structured graphs: Denote ET = {prre,, next, br) next is the child node of prec in branch br in tree T}. If there is bijective mapping π from nodes of finite-depth tree T1 (denoted by V ((T.)) to nodes of a finite-depth tree T2 (denoted by ((T2)) such that 1) I(i) = ( (i)), Vi E V(Ti). (,,j,r) br) E Er, = (I(1), (i), E ETy, Vi,j E ((T)., we say Ti is equivalent to T2, denoted as Ti = T2.
Let Ti refer to the mapping that (G, e) is the first & layers of subtree e(G,e). We define that two infinite-depth trees 7i, T2 satisfy Ti = T3 if and only Ti = Talk, Vk E N.
Given the well defined equivalent class and Definition of local 2-WL and 1-WL test, that is,
2.1 we notice that Tel, T depict the process
((p, 4), G) 22 ((d' G") = To (v. (C, ((p. g). G) 11-LL ((F..'), = (p. ~ (T,
(14)
(15)
Therefore the statement that local 2-WL and 1-WL has equivalent link discriminating power equals to that V(G, e), (G', cd),
(G,
c) = Ta
(16)
According to our definition, we need to prove that for EN, (T, Twla(G e') = (G) = Tall(G ,d), (G,,)) (17)
For k = 0, we have Twlo(G,,) e) ~ T=ll(G", = i(p) = =((p), 1(1) = I(q'), l(p.0) =
((y'a') à Te) = Tello(G',e)
Suppose (15) works for k L, let's consider the situation of k L + 1:
Denote (i,, inght tir,
as neighbors of p,q in G. and (1 E2 ... i }. lil. De.....bb,) neighbors of pl, in G', respectively. According the property of local WL
test, if ( ~ Tall (G", e²), we have l(p) = I(p)). I(4) = I(g'), np = nap: ng = ng
and w.l.o.g.
Taln (p) Txk To (G. ()., = Tw/ ( Vt [mg]
Vs E [mp]
(18)
(19)
Since (15) works for k = L, we have
T (.) ~ (G, ('" As E [mp]
(20)
T l (G. (F.. g)) ~ (G', (l)4)) Vt [n,]
(21)
According to property of 1-WL test, (18), (19) mean T L+1 (G, (p) and Ta L+1 (G', (p','''''')) (P)
have m correspondingly isomorphic I-depth branches. Plus 1(p) = 1(p'), 1(g) = l(g') we
conclude Ta (+1 (G, (p. 9)) ~ T Twl (z/,9)).. The other direction can be similarly proved. Figure 4 gives an illustration.
13

---

Under review as a conference paper at ICLR 2023
(p.
T
2-WL,
9
P. r)
(s.
(p)
1-WL
q'
s'
Figure 4: Update patterns of 2-WI.,, and 1-WL test, and their corresponding mappings from (G, e)
to subtrees in our proof. We can build a one-to-one mapping between subtrees of 2-WLz and 1-WL. We show only part of subtrees.
B PROOF OF THEOREM 3.2 AND THEOREM 3.4
Theorem: 2-FWL. has stronger link discriminating power than 2-WL..
Proof. Let T&c Tg be mappings from sets of graph-link tuples to sets of tree-structured graphs with infinite depth.
Te (p. 9)) has root (p.9) labeled as (I()), (q)), (p-g)) with two branches of child nodes {(p, i) on the left and right side, respectively. For every child node (r, its child nodes are defined in the same way recursively. Node (r, s) is labeled as ((rr),(()) ((re)) ((==))).
For graph G EV, P.q E V. IG
[n]] and {(i.)) : j e [n]]
Ty (G, (p. 9)) has root (p. q) labeled as (()), (n-))) It has n child nodes { ((p, i), (i,
[n] Node ((p,)), (r, 9)) labeled (I(p),((r) (( ((ne), 1(p=r) ((==)) which ((r,,)) (s, E [m]] Each of
has two branches of child nodes ((P,)) t), (t, e [n]] and {
them has its label and child nodes defined in the same way recursively.
Therefore To and Tg depict the process of 2-WL and 2-FWL tests. After defining the equivalent class of tree-structured graph as in the proof of Theorem 3.3 we have
(G, (p. 4)) 21. (G', (1,4)) + (G, 9)) ~ To (G', (G',"'''' (F',')) (G, (p. q)) 2- (G', (p', = Te ~ Ta (G', (p',9')
(22)
(23)
Let Th refer to the mapping such that ()a e) is the first k layers of subtree T(G,e). We will prove that for Vk N.
Te Tala Tolu(G,e) TTl ((G,e),
(24)
Fix (G,e), (G', (G.,)) = (V,E,D, G' = -V", Let = Vl,n' = IV When k = 0, e, To ed) + 1(p) 1(p'), ((9) [(g'), ((g)) 1(g' Telo(G,e)
To Telo(G',el d')
Suppose (24 is true for = LL, 2 0. Let's consider the situation of l: L + According to the property of 2-FWI test, if if I.+ (G, (G', e'), immediately have n' and
14

---

Under review as a conference paper at ICLR 2023
E
A'
D
C'
D'
B
F
B'
F
Figure 5: This figure contains two counterexample. First, links (A, and (A', E") cannot be distinguished by plain 2-WL but can distinguished by (local) 2-FWL and 1-WL with 0/1 labeling trick. In fact due high node-level symmetry 2-WL cannot detect difference between any connected link pairs or unconnected link pairs. The labeling trick breaks such symmetry and help 1-WL to capture the difference of two graph's 's structure. If (C, D) and (C', D') are target node pairs, 0/1 labeling trick no longer works. However, 2-FWL. and local 2-FWL still work (because (D, E) and (D', EE) will have different representations). They can capture triple structure 3-WL test does.
w.l.o.g.
((1) 1(1',, vi e [n]
(25)
(0..)) = loay, Vie [n] ((.0)) = (((4) vi E [n]
(26)
(27)
(G, Twl (o (G, =
((,))) vi e
(28)
Then we have
Ts
~
vi [n]
(29)
= (T Vj [n]
(30)
Due to that (24) is true for k = L, we have
Te L (G. (p. i)) (d.)), vie [n] TEll (G, (j.4) = Telu ()) Vj E [*] According to (23), (24), (25), (29), (30) and the definition of T3, have P (G, (p, 4)) ~ T (G', (v', ,d)),, Vie [n] On the other side the counterexample lies in Figure 5
(31)
(32)
(33)
Theorem: 2-FWL, has stronger link discriminating power than 2- 2-WL
Proof. The proof is the same as the proof of Theorem 3.2 except that (23)-(30) works for p, q and their neighbors instead of all nodes.
C EXTENDED DISCUSSION ON LABELING TRICK
In this section, we compare the link discriminating power between 2-WL tests and 1-WL with labeling tricks. There are two most classic labeling tricks for link prediction: the 0/1 labeling and distance- based labeling, the former labels the target nodes pair with one and other nodes with zero. classic instance of distance-based labeling is DRNL Grouble-Radiu Node Labeling) in (Zhang & Chen 2018). constructs an injective function of distances from current node to two target nodes. Such technique inherently makes of the information of all paths to the target nodes within the extracted subgraph, which itself a strong heuristic of link prediction. Note that node labeling can be directly included in label (feature) l.
Here we mainly discuss 0/1 labeling in the following and leave the discussion on distance- based labeling tricks and more general ones to the future work. Zhang et al. (2021) has discussed the
15

---

Under review as a conference paper at ICLR 2023
theoretical power of 0/1 labeling trick and showed that it enhances 1-WL's link discriminating power. We further compare the link discriminating power of 1-WL with labeling trick and 2- WL tests in the following theorem:
Theorem C.1. For 0/1 labeling trick L. 1-WL test with & and local 2-FWL test both do not have equal or stronger link discriminating power than the other.
Proof. DC, D" in Figure 5 present example that 2-FWL,, can discriminate but 1-WL with L cannot. On the other hand, let's consider 4-order magic square graphs. Below are two 4 x 4 grid graphs without node features. Each node has number from {1, 2. 3, 4} on it. Two nodes have edges if and only if they are 1) in the same row, or 2) in the same column. or 3) holding the same number. The colored node pair (p. q), (p',4)) are the target links. Notice that they are both strongly regular graphs and 2-FWI. cannot discriminate the two links because any node pair with edge has two common neighbors and any node pair without edge also has two common neighbors.
3
1
1-WL with 0/1 labeling can discriminate (p, g), (p'.9'). If not, (r, s), (r', s') (or (r, (s', r'), will be indistinguishable from each other but distinguishable from other node pairs because they are the only nodes that have two labeled children. However they can actually be discriminated since (r', connected but (r', s') isn't, which leads a contradiction.
D MORE DETAILS ON GNN IMPLEMENTATIONS
Four proposed 2- 2- variants are implemented in totally different way. First they all need compute node embedding by 1- I-WL-GNN. Then after pairwisely encoding. our model mimic the 2- WL test pattern to propagate message. Our algorithms engage some tensor operation: given 2D matrix X, we denote A ( that X expands along 1th jhh dimension 3D tensor A. Given vector v, B ( denote that expands along t dimension 3D tensor B. Function sum! (X) means summing X over its hth dimension, and (sp) (A B) means slice-wise (sparse) matrix multiplication of A, B on their first and second dimension. "I" denotes concatenation. Below formally present algorithms:
Computing infrastructure. We leverage Pytorch Geometric V2.0.2 and Pytorch 11.10.0 for model development. We train our models, measure AUROC and the inference time on an A40 GPU with 48GB memory on a Linux server.
Baselines. For AUROC of methods: MF, N2V, VGAE, WLNM, SEAL on non-featured datasets,
we directly use the results in Zhang & Chen (2018). For AUROC of methods: VGAE, S-VGAE TLCC-NN, SEAL,, NBFNet on citation datasets, we directly use the results in Zhu et al. (2021). For performance of KGC methods: R-GCN, Grall., INDIGO on KG datasets, we use the results Liu et al. (2021)
Hyperparameter tuning. Hyperparameters are selected based on validation set performance. The best hyperparameters can be found in our code in the supplement material. Learning rate Ir is chosen from: (5e - 2,
- 4]. hidden dimension for I-WL-GNN hy: (32, 64, 96, 128), number of hidden layers for 1- 1-WL-GNN I;: {1, 2, 3}, number of hidden layers for 2-WL-GNN lg: {1, 2, 3). hidden dimension for 2-WL-GNN hg {16, 24, 32, 64, 96). dropout ratio for embedding layer dp1. 1-WL layer dp2, 2-WL layer dps: (0.1, 0.2, 0.3, 0.4, 0.5). We use Optuna (Akiba et al. 2019) to perform random searching for hyperparameters.
2, 5e 3, le 3,
16

---

Under review as a conference paper at ICLR 2023
Algorithm 2-WL Forward Network
Input: Node embedding: A Raxd Adjacent matrix: A R Number of layers: L, Target link: (p.q).
1: x (N11.3 @ 1n (W @ )
2: for = 0 to L - do
3: X' = -mmp).(Xx=111..)
|um 4: x(++1) = |sum (X') & 11 (xmm) @ 1
5: end for
6: yp x x-L)
7: return y
Algorithm 2 2-WLL Forward Network
Input: Node embedding: N E Raxd, Number of layers: L, Observed edge index: ((Pi, 4m
m+mm' Target links: {(p) q;))
Compute A [0, 1 nnn
s.t. A =1 + p; = Pj. m
2: Compute A22 E [0, 1] 1|m s.t. Ale =1 - = S
3: for = 0 to L do
4: ((++1 = GC ( (CN2)(X(0;;"
5: end for
6: Y = mlp(X((1)
7: return Ymmm+
Algorithm 3 2-FWL Forward Network
Input: Node embedding: A E 12axd, Adjacent matrix: A E RR*x", Number of layers: L, Target link: (P.)).
I: (0) (1/1).3 X 2 @ (W @ 1 |
2: for = 0 L do
3: X' = mlp1.1(X(())
4: X" = (x(1),(((1))
5:
((++1) mm/p. (m(X'X"))
6: end for
7: Yp.q -x x(L)
8: return Yp.
Algorithm 2-FWL, Forward Network
Input: Node embedding: N Raxd Adjacent matrix: A Raxn, Number of layers: L, Observed edge index: {Pi, q:) H2 Target link: (p, 9).
1: Compute sparse matrix: W E Rexxnd s.t. W Wp..g = -No, @ Ng.
2: ( mlpo (W)
3: for = 0 to L 1 do
4: W' = mlp..(WW
5: X' = spmmi (1)) W')
6: ((+1)) = mxlp2
7: end for
8: Ypa mipp (x WV O.))
9: return Y,.
17


Reviews:
[{"review_id": "lpZ-Q_l1eN", "reviewer": "Reviewer_5pff", "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": "The main idea of this paper is to design dedicated models for link & relation prediction: Standard graph neural networks which learn node-wise representations are also used for link-level tasks, but their lack of expressive power is more severe on link-level tasks. One way of alleviating this limitation is to apply a so-called labelling trick, which usually incurs a large computational overhead. This paper proposes directly learning pair-wise representations, grounded in 2-WL and its local variants. Experiments are conducted both on link prediction and on knowledge graph completion benchmarks.", "summary_of_the_review": "In its current state, the paper looks incremental on existing work, and the presentation does not help much in identifying the precise contributions. There are also some concerns outlined in the review, which leads me to suggest a weak reject. ", "strength_and_weaknesses": "Strengths:\n\n- GNNs are still relatively weak on link-level tasks (esp., on knowledge graphs) compared to node-level tasks and there is a strong need for further research in this context.\n- The expressiveness limitations of GNNs are well-understood, but such limitations are more severe on link-level tasks, since the class of pair-wise representations that cannot be distinguished by 1-WL learned features is quite large.\n\nWeaknesses:\n\n- Many of the important points raised in this paper are taken from existing literature, and the authors should do a better job at locating this work in reference to existing works they cite, including [1-4]. The goal of this work is different, but the overlap between these papers  is surprisingly large, which makes it really hard to delineate the exact contribution of this work.\n\n- The algorithms proposed are very close to the algorithms from $k$-GNNs (Morris et al, 2019) are their variations proposed in the literature. The authors also use 1-WL algorithms to learn initial features, and then run the 2-WL variants, which is basically a special case of the idea of using 1-2-3-GNNs from (Morris et al, 2019).\n\n-  Most results are straightforward: $k$-FWL ($=k+1$-WL ) is more expressive than $k$-WL already on node-wise representations, and so this clearly translates to pair-wise representations, making Theorem 3.2 straightforward (and one can actually use this correspondence to show the result). Theorem 3.4  follows the same ideas as Theorem 3.2. Theorem 3.1 is more interesting, which pinpoints the limitations of 1-WL on links, and shows an example which separates 1WL from 2WL on link-level tasks, but then, similar examples are already given in earlier works, so this seem appears also very incremental. \n\n- There are also some technical concerns regarding how WL and FWL algorithms are defined: To my understanding, WL algorithms also aggregate over non-neighbours (even 1-WL); see, e.g., \"Martin Grohe, The logic of graph neural networks, LICS 2021\". While this doesn't seem to make a difference on single graphs, it does make a difference when we consider sets of graphs, as noted in \"Barcelo et al., The logical expressiveness of graph neural networks, ICLR 2020\".\n\n\n[1] Muhan Zhang and Yixin Chen. Weisfeiler-lehman neural machine for link prediction. KDD 2017. (this is cited twice with different structure)\n[2] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurIPS, 2018.\n[3] Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. ICLR, 2020.\n[4] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. NeurIPS, 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K7lG8F-vC5Y", "reviewer": "Reviewer_kWUU", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper deals with the problem of link prediction in graphs. Specifically, it proposes to leverage variations of the 2-dimensional Weisfeiler-Leman algorithm (2-WL) for this problem.  The authors show how the 2-WL and folklore 2-WL (2-FWL) can be leveraged straightforwardly to design GNN-like neural architectures that learn representations for edges and non-edges. Moreover, similarly to [1], they define a local version that only considers a subset of all k-tuples during aggregation. \n\nTheoretically, they compare the above variants in terms of expressive power. That is, they show that the 2-FWL is strictly strong than the 2-WL in distinguishing links. Further, they show that the local variant has the same expressive power as the 1-WL.\n\nEmpirically, the proposed architectures are evaluated on standard link prediction and knowledge completion datasets, showing somewhat promising performance. ", "summary_of_the_review": "This is a solid, incremental paper. The theoretical results are not very surprising and the experimental results are mixed, not clearly indicating why 2-WL-based methods are superior for link prediction problems. ", "strength_and_weaknesses": "**Strengths**\n- Simple approach that sometimes works better than baseline approaches  \n\n**Weaknesses**\n- Presentation needs to be improved \n- Incremental paper\n- Theoretical results are rather obvious\n\n\n**Remarks/Suggestions**\n- The definition in Eq. 2 is slightly confusing as you use j for indices as well as vertices. \n- In section 2.1, you only seem to define the neighborhoods of k-tuples but not the actual algorithm. Hence, readers not familiar with k-WL might have a hard time. \n- In section 2.2, you are not defining the initial coloring of the tuples. That is, the original k-WL uses the atomic type which is crucial for its expressivity. \n- The definition of the local variations is quite close to [1]. That is, [1] requires that the exchanged nodes are adjacent while you require that the non-replaced node and the replacing node are adjacent. Further, note that all your neighboring nodes are edges, non-edges are not considered. \n- Figure 3 hinges on the fact the number of nodes of the graphs is different. You might want to use a pair with the same number of nodes. \n- In section 3.2, a lower bound on the time and memory complexity of the local version is still n^2. You might want to make this more clear in the paper. \n- In section 4.1, it is not clear if the proposed neural architectures indeed possess the same expressive power as the 2-WL. Only a heuristic argument is given. \n- In table 5, for the running time comparison, you only use small-scale datasets, e.g., CORA. It would be interesting to use larger datasets. \n- Theorem 3.1, 3.2, and 3.4 can be proved via simple counterexamples. The pursued proof strategy via unravelings/unrollings seems overly complicated. \n\n**Questions**\n- Can you quantify if your local k-WL is more expressive than the local 2-WL defined in [1]?\n- What are the benefits of using the local 2-WL if it has the same expressive power as the 1-WL?\n- Why don't you prove Theorem 3.1, 3.2, 3.4 via simple counter examples? It seems very plausible that it follows directly from a CFI-like construction for k=2.\n\n**Minor points/Typos**\n- In section 2.1, first paragraph \"k-dimensional WL test\" -> \"The k-dimensional WL test\", also second paragraph\n- In section 2.2, there is a broken reference\n- In section 3.1, \"the Folklore\" -> \"the folklore\"\n- Section 6.2, \"we\" -> \"We\"\n\n[1] Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (Preprint arXiv:1904:01543)\nChristopher Morris, Gaurav Rattan, Petra Mutzel,\nNeural Information Processing Systems (NeurIPS) 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-cynpRoabNA", "reviewer": "Reviewer_aR3Z", "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": "The paper proposes a 2-dimensional WL GNN to be used for link prediction, based on global and local variants of the 2-WL graph isomorphism heuristic. In particular, the paper motivates the use of link-level representations, as opposed to node-level representations in standard 1-WL-based GNNs, so as to directly make inferences for link prediction. To this end, the paper introduces the standard 2-WL algorithm and its more powerful folklore counterpart (2-FWL), as well as their local relaxations 2-WL_L and 2-FWL_L respectively, which only consider existing edges in the graph. The paper then establishes expressive power results among all four variants and standard 1-WL, and shows that, for link discrimination, 1) 2-FWL is stronger than 2-WL, 2) 2-WL is stronger than 1-WL, 3) 2-WL_L is equivalent to 1-WL, and 4) 2-FWL_L is stronger than 1-WL but weaker than 2-FWL. Building on these results, the paper takes inspiration from existing literature, namely k-GNNs and PPGNs, to propose an 2-WL-GNN architecture. More specifically, a standard 1-WL GNN is first run, with its representations then pooled to obtain link-level representations that are subsequently refined by a 2-WL layer. In turn, GNN layers corresponding to each of 2-FWL, 2-WL, and 2-FWL_L are provided. Finally, the paper runs an extensive empirical analysis of the different proposed variants and compared against several state-of-the-art GNNs for link prediction, and shows that 1) 2-WL-GNN models perform strongly, mostly surpassing their competitor models, and 2) achieve this performance with a much smaller computational overhead.", "summary_of_the_review": "All in all, I think that the paper's use of 2-WL-GNNs for link prediction is intuitive and interesting. However, the ideas brought forward in this paper are not novel, but are rather better seen as an evaluation of 2-WL-GNNs from a link prediction perspective. The empirical findings are comprehensive and convincing, but also do not produce any novel insights or analyses that shed new light on our understanding of GNNs for link prediction. Hence, on the balance, I lean towards a weak reject for the paper, as it makes insufficient novel contributions towards producing new techniques for link prediction with GNNs. However, I am happy to change my verdict should the authors address my above concerns. ", "strength_and_weaknesses": "# Strengths: \n- The idea of using pair-wise node representations is intuitive and powerful, and is a natural choice for link prediction tasks. \n- The empirical results and reported runtimes are convincing: The models all perform strongly, and the local variants, despite being theoretically weaker, achieve very good performance with a fraction of the running time required by labelling or sub-graph method, and this due to 2-WL-GNNs' ability to batch predictions and make them jointly.\n- The paper is well-written and the preliminaries are results are well-presented. The figures are also helpful to clarify the main arguments proposed in the paper.\n\n# Weaknesses: \n- I have concerns about the novelty of the approach, as 2-WL-GNNs seem very similar to k-GNN by Morris et al. (cited in the paper). Of course, the k-GNN paper does not evaluate on link prediction tasks, but the models appear to be conceptually identical. Therefore, I do not believe that the paper makes any major novel contribution on the model development side. The main contribution instead lies in running the evaluation with multiple variants and looking at model performance from this perspective: In light of this, I would recommend rephrasing the paper's findings along these lines. \n- The theoretical contribution of the paper also appears insufficient. Indeed, the results about 2-FWL versus 2-WL are relatively easy to prove, and 2-WL versus 1-WL, though interesting as it contrasts with the equivalence at the node level, is also simple. Hence, the paper overall does not provide any major novel insights on the theoretical side, either. \n- Though this approach enables batched predictions, and thus offers efficiency improvements relative to sub-graph and labelling-based link prediction techniques, I believe it is misleading to present this approach as scalable in general. Indeed, local 2-WL efficiency depends explicitly on edge density and graph size, and will not be efficient on large graphs. By contrast, the sub-graph and node labelling methods impose a high overhead and cannot be batched, but can naturally scale to larger graphs, as they consider a relatively fixed-size neighborhood bounded by a fixed number of hops. Hence, the point made about efficiency is only really true for smaller graphs. The true situation appears to be a trade-off: On smaller graphs, sub-graph methods are heavily redundant and the lack of batching is very sub-optimal, making local 2WL a clearly more efficient choice. However, on larger graphs, the redundancies of sub-graph methods are relatively reduced and batching is no longer practically viable. In turn, these methods become more promising from a computational complexity perspective. I thus strongly suggest that these findings be included in the paper and discussed holistically.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject