Neural Link Prediction with Walk Pooling
Authors: Liming Pan
Cheng Shi
Ivan Dokmanić
Venue: ICLR 2022 Poster (2022)
Keywords: Graph neural network
Link prediction
Random walk
Graph topology.

Abstract: Graph neural networks achieve high accuracy in link prediction by jointly leveraging graph topology and node attributes. Topology, however, is represented indirectly; state-of-the-art methods based on subgraph classification label nodes with distance to the target link, so that, although topological information is present, it is tempered by pooling. This makes it challenging to leverage features like loops and motifs associated with network formation mechanisms. We propose a link prediction algorithm based on a new pooling scheme called WalkPool. WalkPool combines the expressivity of topological heuristics with the feature-learning ability of neural networks. It summarizes a putative link by random walk probabilities of adjacent paths. Instead of extracting transition probabilities from the original graph, it computes the transition matrix of a ``predictive'' latent graph by applying attention to learned features; this may be interpreted as feature-sensitive topology fingerprinting. WalkPool can leverage unsupervised node features or be combined with GNNs and trained end-to-end. It outperforms state-of-the-art methods on all common link prediction benchmarks, both homophilic and heterophilic, with and without node attributes. Applying WalkPool to a set of unsupervised GNNs significantly improves prediction accuracy, suggesting that it may be used as a general-purpose graph pooling scheme.   

Published a conference paper at ICLR 2022
NEURAL LINK PREDICTION WITH WALK POOLING
Liming Pan"
Cheng Shi" & Ivan Dokmanić Departement. Mathematik und Informatik, Universität Basel,
School of Computer and Electronic Information, Nanjing Normal University, 210023 Nanjing, China.
4051 Basel, Switzerland.
pan. liming@njnu.ee edu. cn
edu.
[firstname 1astname Santtaammeeunbaassse @unibas ch
ABSTRACT
Graph neural networks achieve high accuracy in link prediction by jointly leveraging graph topology and node attributes. Topology, however, is repre- sented indirectly; state-of-ther ofetttearrtttto methods based on subgraph classification label nodes with distance to the target link, that, although topological information is present, it is tempered by pooling. This makes it challenging leverage features like loops and motifs associated with network formation mechanisms.. We propose a link prediction algorithm based on a new pool- ing scheme called WALKPOOL. WALKPOOL combines the expressivity of topological heuristics with the feature-learni ability of neural networks. It summarizes a putative link by random walk probabilities of adjacent paths. Instead of extracting transition probabilities from the original graph, it computes the transition matrix of "predictive" latent graph by applying attention to learned features; this may be interpreted seature-sensitive topology fingerprinting. WALKPOOL can leverage unsupervised node fea- tures or be combined with GNNs and trained end-to-end. It outperforms stato-of-the-art methods on all common link prediction benchmarks, both homophilic and heterophilic, with and without node attributes. Applying WALK to a set of unsupervised GNNs significantly improves predic- tion accuracy, suggesting that it may be used as general-purpose graph pooling scheme.
INTRODUCTION
Graphs are a natural model for relational data such as coauthorship networks or the human pro- tein interactome. Since real-world graphs are often only partially observed, central prob- lem across all scientific domains is to predict missing links (Liben-Nowell & Kleinberg 2007 Link prediction finds applications in predicting protein interactions (Qi et al. 2006). drug sponses (Stanfield et al.] 2017 ) or completing the knowledge graph (Nickel et al., 2015). Tt underpins recommender systems in social net- works (Adamic & Adar 2003) and online market- places (Lü et al. 2012). Successful link prediction demands an understanding of the principles behind graph formation.
triangess large weights
Subgraph
Prefer quadrangles large weights
Observed graph
Candidate links
Completed graph
The lopological organizing rules not universal across graphs.
Figure 1:
In this paper we propose link prediction algorithm which builds on two distinct traditions: (1) complex networks, from which we borrow ideas about the importance of topology, and (2) the emerging domain of graph neural networks (GNNs), on which we rely to learn op- timal features. We are motivated by the fact that the existing GNN-based link prediction algorithms encode topologica features only indirectly, while link prediction is a strongly
"These two authors have equal contribution.
Too whom correspondence should be addressed.
'Mathematical topology studies (global) properties of shapes that are preserved under homeo- morphisms. Our use of "topology" to refer local patterns common in the network literature.

---

Published as a conference paper at ICLR 2022
topological task (Li & Zhou 2011 Traditional heuristics assume certain topological orga- nizing rules, such as preference for triangles or quadrangles; see Figure 1 for an illustration. But organizing rules are not universal across graphs and they need to be learned. The cen- terpiece of our algorithm is a new random-wall walk-based pooling mechanism called WALKPOOL which may be interpreted as a learnable version of topological heuristics. Our algorithm is universal in the sense of Chien et al. (2020) in that it models both heterophilic (e.g., 2D- grid in Figure 1 and homophilic (c.g. Triangle lattice in Figure 1 graphs unlike hardcoded heuristics standard GNNs which often work better on homophilic graphs. WALKPOOL can learn the topological organizing rules in real graphs (for further discussion of lattices from Figure 1 see also Section 4.4), and achieves state-of-the-art, link prediction results on all common benchmark datasets, sometimes by significant margin, even on datasets like USAir (Batagelj & Mrvar 2006 where the previous state of the art is as high as 97%.
1.1
RELATED WORK
Early studies on link prediction use heuristics from social network analysis LL & Zhou 2011 The homophily mechanism for example (McPherson et al. 2001] asserts that "simi- lar" nodes connect. Most hcuristics are based on connectivity: the common- index (CN) scores a pair of nodes by the number of shared neighbors, yielding predicted graphs with many triangles; Adamić Adar index (AA) assumes that highly-connected neighbor contributes less to the score of focal link (Adamic
Adar 2003). CN and AA rely on paths of length two. Others heuristies use longer paths, explicitly accounting for long-range correlations (Lü & Zhou 2011]. The Katz index (Katz, 1953) scores a pair of nodes by a weighted sum of the number of walks of all possible lengths. PageRank scores link by the probability that a walker starting at one end of the link reaches the other in the stationary state under random walk model with restarts.
Heuristics make strong assumptions such as a particular parametric decay of path weights with length, often tailored to either homophilic or heterophilic graphs. Moreover, they cannot be easily used on graphs with node or edge features. Instead of hard-coded structural features, link prediction algorithms based on GNNs like the VGAE (Kipf & Welling 2016bb or SEAL Zhang & Chen 2018) use learned node-level representations that capture both the structure and the fcatures, yiclding unprecedented accuracy.
Two strategies have proved successful for GNN-based link prediction. The first is to devise a score function which only depends on the two nodes that define a link. The second is to extract a subgraph around the focal link and solve link prediction by (sub)graph classification (Zhang Chen (017).- In both cases the node representations are either
learned in an unsupervised way (Kipf & Welling 2016b Mavromatis & Karypis 2020) or
computed by a GNN trained joinly with the link classifier (Zhang & Chen 2018 Zhang
et al. )
Algorithms based on two-body score functions achieved state-of-the-arl performance when they appeared, but real networks brim with many-body correlations. Graphs in biochem- distinct
istry, neurobiology, ecology, and engineering (Milo et al. (004)) exhibit patterns occuring much more often than in random graphs Motifs may correspond to ba- sic computational elements and relate to function (Shen-Orr et al. 2002). A multilayer GNN generates node representation by aggregating information from neighbors, capturing to some extent many-body and long-range correlations. This dependence is however indirect and complex topological properties such frequency of motifs are smoothed out.
The current. state-of-the-art link prediction algorithm, SEAL (Zhang & Chen 2018 is based on subgraph classification and thus may account for higher-order correlations. Unlike in vanilla graph classification where a priori all links are equaly important, in graph classi- fication for link prediction the focal link plays a special role and the relative placement of other links with respect to it matters. SEAL takes this into account by labeling each node of the subgraph by its distance to the focal link. This endows the GNN with first-order topological information and helps distinguish relevant nodes in the pooled representation. Zhang and Chen show that node labeling is essential for SEAL's exceptional accuracy. Nev- ertheless, important structural motifs are represented indirectly (if at all) by such labeling schemes, even less so after average pooling. We hypothesize that a major bottleneck in link prediction comes from suboptimal pooling which fails to account for topology.
2

---

Published a conference paper at ICLR 2022
1.2 OUR CONTRIBUTION
Following Zhang & Chen 2018 we approach link prediction from via subgraph classifica- tion. Instead of encoding relative topological information through node labels, we design new pooling mechanism called WALKPOO1. WALK extracts higher-order structural information by encoding node representations and graph topology into random-waa tran- sition probabilities on some effective latent graph, and then using those probabilities to compute features we call walk profiles. WALKPOOL generalizes loop-counting ideas used to build expressive graph models (Pan et al. 2016). Computing expressive topological de- scriptors which are simultaneously sensitive to node features is the key difference between WALKPOOL and SEAL. Using normalized probabilities tuned by graph attention mitigates the well-known issue in graph learning that sighly-connected nodes may bias predictions. Transition probabilities and the derived walk profiles have simple topological interpretations.
WALKPOOL can be applied to node representations generated by any unsupervised graph representation models or combined with GNNss and trained in and-to-end. It achieves state- of-tho-art results on all common link prediction benchmarks. Our code and data are available online at https: g/tt:/b/gttubb com SaaDaCheng/WalkPPn
2 LINK PREDICTION ON GRAPHS
We consider an observed graph with N nodes (or vertices), go = (V,E%) with V being the node set and Eo the set of observed links (or edges). The obscrved link sot E a subset go C of the set of all true links E The larget of link prediction is to infer missing links from a candidate set E", which cont contains both true (in E*) and false (not in E*) missing links.
Problem 1. (Link prediction) Design on algorithm LearnLP that takes an observed graph G C G and produces a link predictor LearnLP(G") = II VXV + {True, False} which accurately classifies links in E
Well-performing solutions to Problem | exploit structural and functional regularities in the observed graph to make inferences about unobserved links.
Path counts and random walks For simplicity we identify the N vertices with integers IV and represent G by its adjacency matrix, A (o {0, NN with agj- = 1 if (i,j} E 8" and az otherwise. Nodes may have associated feature vectors (x, R NN):..,NN); we collect all feature vectors in the feature matrix X [x1, x,N]" E NXF.
Integer powers of the adjacency matrix reveal structural information: [A7]y is the number of paths of length connecting nodes i and j. WALKPOOL relies on random walk transition matrices. For an adjacency matrix A the transition matrix is defined as P = D "A where D diag(d1..... ........................ dN) and d, Σ, ais = [W(i) is the degree of the node i. Thus the probability Pıj = d; d''a.; aig that a random walker at node transitions to node j is inversely proportional to the number of neighbors of i. An extension to graphs with non-negative edge weights W = (w,y) is straightforward by replacing dz by wzy. Powers of P are interpretable: [PT is the probability that a random walker starting at node i will reach node j in r hops.
As we show in Section 3.2 transition probabilities in WALKPOOL are determined coeffi- cients of an attention mechanism applied to learned node features. The node features are in turn extracted by a parameterized function fe, which distills input attributes and to extent graph topology into an embedding (a vector) for each node. The feature extractor fe {0, 1] N x RRNX + NxF' takes as input the adjacency matrix (which encodes the graph topology) and the input feature matrix, and outputs distilled node feature matrix. It should thus be equivariant to node ordering in A which is satisfied by GNNs.
3 WALKPOOL FOR LINK PREDICTION BY SUBGRAPH CLASSIFICATION
We now describe WALKPOOL which directly leverages higher-order topological correlations without resorting to link labeling schemes and without making strong a priori assumptions. WALKPOOL first samples the k-hop subgraph ( C Go enclosing the target link; and then computes random-walk profiles for sampled subgraphs with and without the target
3

---

Published conference paper at ICLR 2022
A
(wiL ((mnda de .iink in Incs. Agrape )
WALKPOO
GNN
((P ((P)))
P'=
Figure 2: Illustration of WALKPOOL. A: The input graph and the focal link e; B: enclosing subgraphs with and without E; C: intentiion-poocssee features random walk transition probabilities; D: extracted walk profile.
link. Random walk profiles are then fed into a link classifier. Computing walk profiles entails
1. Feature extraction: = So X), where So is a GNN;
2. Transition matrix computation: P = AttentionCoeffiiietss,, ();
3. Walk profiles: Extract entries from P for 2 S S To related to the focal link.
We emphasize that we do not use allention to compute per-node linear combinations of features like Veličković et al. (2017) (which analogous to Vaswani al. (2017)), ) but rather interpret the attention coefficiends as random walk transition probabilities. The features Z may be obtained either by an unsupervised GNN such as VGAE (Kipf & Welling 2016b), or they may be computed by GNN which is trained jointly with WALKPOOL.
3.1 SAMPLING THE ENCLOSING SUBGRAPHS
Following earlier work we make the assumption that the presence of a link only depends on its neigh- bors within (small) radius k. It is known that simple hcuris- tics like AA may already perform well many graphs, with longer walks not bringing about signisi- cant gains. Indeed, SEAL (Zhang & Chen 2018 exploits the fact that order k heuristic can be accurately calculated from a k-hop subgraph; optimal k is related to the underlying generative model. Keeping & small (as small as in this paper) is pragmatic for rea- sons beyond diminishing returns: large greatly increases memory and compute demands. The size of a 2-hop neighborhood is graph-dependent, but for the highly-connecter E.coli and PR datasets we already need enforce maximum number of nodes per hop the subgraphs in memory.
2
Features
T-2
Boda
3 3'3
C-0-0
0-0-0
3
linki
E/T
3 O-G-O
1/3
1/3
1/31
1/2
1/2
0
graph"
nodef codo] + modee + mode
1/3
1/3
1/3
Figure 3: Illsstaation of walk profiles for 2. We assume Pia 1//d, where d; is the degree of node i.
Let d(æ, y) be the shortest-path distance between nodes and y. The k-hop enclosing subgraph Gt ((,)) for {i,}} is defined as the subgraph induced from Go by the set of nodes
(ios = fx E d(x,i) S or d(x,j) S
Then 9 1 (vk {f Ek omit the dependence on & and write G(is) = () (1.s),C())) for simplicity.
{} where (x, v} E Eh when x,y E Dt (1.13 and {2,0) E 8", We
We fix an arbitrary order of the nodes in V((s) and denote the corresponding adjacency matrix by A(,))- Without loss of generality, assume that under the chosen order of
4

---

Published a conference paper at ICLR 2022
nodes, the nodes and j are labeled as and 2 so that the candidate link {i.j} is mapped to (1,2) in its enclosing subgraph. We denote the corresponding node feature matrix (1.i)) with values inherited from the full graph (the rows of (i.)) are a subset of rows of Z).
For the candidate set of links E", we construct a set of enclosing subgraphs = [G {i,}} E } thus transforming the link prediction problem into classifying these k- k-hop enclosing subgraphs. For training, sample set of known true and false edges Et and construct its corresponding enclosing subgraph set S = (Gr, : (i.j) E E").
3.2 RANDOM-WAR WALK PROFILE
The next step is to classify the sampled subgraphs from their adjacency relations A (a,)) and node representations ((,)). Inspired by the walk-bassd heuristics, we employ random walks to infer higher-order topological information. Namely, for a subgraph (g = (V,E), Z) (either in 8 or 8*) we encode the node representations into edge weights and use these edge weights to compute transition probabilities of a random walk on the underlying graph. Probabilities of walks of various lengths under this model yicld a profile of the focal link.
We first encode two-node correlations as effective edge weights
Wayy = Qe(z.)) Ke (ozz))//
(1)
for all {x,g} E E, where Qo RF - RF and Ko R + F are two multilayer perceptrons (MLPs) and F" is the output dimension of the MLPs. In order to include higher- order topological information, we compute the random-walk transition matrix P (Po.)) from the two-body correlations. We set
Px, = [softmax ((wa, ((w))))=NNt))),, == exp(wx.)) / (xEN(()) exp(w2,2)
(2)
for {x.y) E E and Pr.y otherwise, with .Vxx) the set of neighbors of in the enclosing subgraph. The encoding (2) is analogous to graph attention coefficients (Veličković et al. 2017 Shi et al., 2020); unlike graph attention, however, we directly use the coefficients instead of computing linear combinations; this framework also allows multi-head attention.
Entries of the 7-th power [Prly are interpreted as probabilities that a random walker goes from i to in hops. These probabilities thus concentrate the topological and node at- tributes relevant for the focal link into the form of mndomm-wllss.
Topology is included indirectly through the GNN-cxtracted node features Z, and directly by the fact that P encodes zero probabilities for non-ncighbors and that its powers thus encode probabilities of paths and loops;
Input features are included directly through the GNN-extracted node features, and refined and combined with topology by the key and value functions Qo, Kg.
As a result, WALKPOO1
2 can be interpreted as trainable heuristics.
From the matrix P and its powers, we now read list of features to be used in graph classification. We compute node-level, link-level, and graph-level features:
(3) Computation of all features is illustrated for r = in Figure 3 Node-level features node" describe the loop structure around the candidate link (recall that {1,2] is the focal link in the subgraph). The summation ensures that the feature invariant to the ordering of i and j, consistent with the fact. that we study undirected graphs. Link-level features link" give the symmetrical probability that a length-r random walk goes from node to 2. Finally, graph-level features graph" are related to the total probability of leugth-r loops. All features depend on the node representation Z; we omit this dependence for simplicity. The use of P in WALKPOOL is different from how graph matrices (c.g., A) are used in GNNs. In GNNs, the powers A serve as shift operators between neighborhoods that are multiplied by filter weights and used to weigh node features; WALKPOO1 encodes graph signals into effective edge weights and directly extracts topological information from the entries of P".
node = | [P')2,2 link = =PP)),, + [P'
graph" = graph"=tr(P")
"The output of pooling (e.g., in CNN) is often an object of the same type (e.g., down- sampled image). The last layer of a CNN or GNN involves global average pooling which is graph summarization mechanism similarly WALKPOOL, hence the name.
5

---

Published a conference paper at ICLR 2022
3.3 PERTURBATION EXTRACTION
A true link is by definition always present in its enclosing subgraph while negative link is always absent. This leads to overfitting if we directly compute the features (3) on the enclosing subgraphs since the presence absence of the link has strong effect on walk profiles. For a normalized comparison of true and false links, we adopt a perturbation approach. Given an enclosing subgraph == (V, E), we define its variants G = (V, (resp. G = (P,,)(122)) with the candidate link forced to be present (resp. absent). We denote the node-level features (3) computed on G and g by node":t and node"." respectively, and analogously for the link- and graph-level features.
While the node- and link-level features are similar to the heuristics of counting walks, graph and graph".- are not directly useful for link prediction as discussed in the intro- duction: the information related to the presence of {i,j} is obfuscated by the summnation over the entire subgraph (by laking the trace).
SEAL attempts remedy a similar issue for average (as opposed to tr(P")) pooling by labeling nodes by distance from the link. Here propose principled alternative. Since transition probabilities are normalized and have clear topological meaning, we can suppress irrelevant information by mcasuring the perturbation of graph-level features, Agraph" graph -graph:". This "background subtraction" induces a data-driven soft limit on the longest loop length that, by design, Agraph" concentrates around the focal link. In Appendix E, we demonstrate locality of WALKPOOL. Compared to node labeling, the perturbation approach does not. manually assign relative position (which may wrongly suggest that nodes at the same distance from the candidate link are of equal importance).
In summary, with WALKPOOL, for all (9te)) : {i,j 8 we read a list of features as
wPo (G, Z) = W1,2, (node" Ti nodee link link" "Agraph")" To )
(4)
where To is the cutoff of the walk length and we treat it as hyperparameter. The features are finally fed into a classifier; we use an MLP H. with a sigmoid activation in the output. The ablation study in TableB3 (Appendix B) shows that all the computed features contribute relevant predictive information. Walk profile computation is summarized Figure 2
3.4 TRAINING THE MODEL
The described model contains trainable parameters which are fitted on the given observed set E of positive and negative training links and their enclosing subgraphs. We train WALKPOOL with MSE loss (see Appendix for a discussion of the loss),
0r arg min
Σ (iJ)E8
(VU.)) II (WPo(S ((.))))
where V(s,2) = if (i,j} E 80 and otherwise the label indicating whether the link {i, is true or false. The fitted model is then deployed the candidate links E the predicted label for {x,y} E" is simply D[z.0) = 1lg- (WPa- (9(,,))); (
4 PERFORMANCE OF WALKPOOL ON BENCHMARK DATASETS
We use area under the curve (AUC) (Bradley 1997 and average precision (AP) as metrics. Precision is the fraction of true positives among predictions, Letting TP (FP) be the number of true (false) positive links, AP = TP TP/(TP- + FP).
4.1 DATASETS
In homophilic (heterophilic) graphs, nodes that are similar (dissimilar) are more likely to connect. For node classification, a homophily index is defined formally as the average fraction of neighbors with identical labels (Pei et al. 2020). In the context of link prediction, we assume that network formation driven by the similarity (or dissimilarity) of node attributes, then homophilic graph will favor triangles while heterophilic graph will inhibit.

---

Published a conference paper at ICLR 2022
triangles. Following this intuition, we adopt the average clustering coefficient ACC (Watts & Strogatz 1998) as topological correlate of homophily.
We experiment with eight datasets without node attributes and seven with attributes. As
graphs without attributes we use: (i) USAir (Batagelj & Mrvar 2006 (ii) NS (Nwman
2006 (iii) PB (Ackland et al. 2005), (iv) Yeast (Von Mering et al. 2002), (v) C.ele Watts
& Strogatz 1998), [vi) Power Watts & Strogatz 1998) (vii) Router (Spring et al. 2002
and (vii) E.coli iZhag et al. 2018). Properties and statistics of the datasets, including
number of nodes and edges, edge density and ACC can be found in Table 1 of Appendix A.
In graphs with a very low average clustering coefficient like Power and Router (ACC = 0.080 and 0.012, respectively, poorly (Lü & Zhou, 2011] (cf. Table 2). since hcuristics often adopt the homophily assump- tion and rely trianglos. We show that by learning the topological organizing patterns, WALKPOOL performs well even for these graphs.
Appendix A); topology-based heuristics usually perform
For fair comparison, we the exact same training and lesting sets (including positive and negative links) as SEAT. in [Zhang & Chen (2018). 90% of edges are taken as positive training edges and the remaining 10% are the positive test edges. The same number of
additionally sampled nonexistent links are taken as training and testing negative edges.
As graphs with node attributes, we use: (i) Cora
McCallum et al., 2000 (ii) Cite-
seer (Giles et al.
1998), (iii) Pubmed (Namata et al. 2012). (iv) Chamelcon Rozember-
czki et al. 2021).
vv) Cornell (Craven et al.) 1998p. (vi) Texas (Craven al.
1998). and
(vii) Wisconsin Cravenn et al. 1998). The properties and statisticcs of the datasels can be
found in Table 4 of Appendix A; further details are provided Appendix A
Following the experimental protocols in [Kipf& & Welling 2016b: Pan et al.
2018 Mavromatis
& Karypis 2020), we split the links in three parts: 10% testing, 5% validation, 85% training.
We sample the same number of nonexisting links in each group as negative links.
4.2 BASELINES
On benchmarks without node attributes, compare WALKPOOL with eight other methods. We consider three walk-
100.0
97.5
based heuristics: AA, Katz and PR; two subgraph-based heuristic learning meth- ods: Weisfeller-Lehmann graph kernel (WLK) (Shervashidze et al. 2011) ) and
95.0
92.5
90.0
WLNM (Zhang & Chen 2017 and latent feature methods: node2vec (N2V) (Grover Leskovec 2016). spectral clustering (SPC) Tang & Liu 2011p. matrix fac- torization (MF) Koren et al. 2009) and
85.0
Router
0.012
Power
0,080
Cole
0.292
Yeast
0.306
Ecol
USAr
0.625
0,638
Figure 4: Comparison of mean and variance of AUC between SEAL and WP with 90% ob- served links. The datasets are sorted by their clustering coefficients.
LINE (Tnng et al. 2015). We additionally consider the GNN- SEAL, which is the previous stale-of-the-art.
For datasets with node attributes, we com- bine WALKPOOL with three unsupervised regularized variational graph autoencoder (ARGVA) (Pan et al. 2018) and Graph Info- Clust (GIC) (Mavromatis & Karypis 2020).
GNN-based models: the VGAF, adversarially
4.3 IMPLEMENTATION DETAILS
In the absence of node attributes, we initialize the node representation ( as an N x F()) all-ones matrix, with FrO) = 32. We generate node representations by two-layered Graph Convolutional Network (GCN) (Kipf & Welling 2016a): (k) = GCN (z (1))), , E (1,2),
where ()) X. We then concatenate the outputs Z (Z) ( [ to obtain
the final node representation used to compute WP(G, Z) and classify. While a node labeling
scheme like the in SEAL is not needed for the strong performance of WALKPOOL.
7

---

Published a conference paper at ICLR 2022
WP
SEAL
AA
CN
VGAE
Triangle lattice 50)
99.77-0.11
90.54.10.11
95.16_1.900
95.15.10.87
37.14_1.47
2D-grid (50 x 50)
99.86+0.09
90.51+0.09
40.90+0.00
40.90+0.09
32.43-1.12
Hypercube (2"")
100,00++0.00
00:00000110
48.01=0.33
48.0140.35
37.81=1.19
Star (1000)
100.00+0.00
90.57+0.110
14.50+2.40
14.50+2.40
100.00+0.000
Table 1: AUC for synthetic graphs over 10 independent trials.
find that labeling nodes by distance to focal link slightly improves results; we thus evaluate WALKPOOL with and without distance labels.
For the three datasets with node attributes, we first adopt an unsupervised model generate an initial node representation ()) This is because standard 2-layer GCNs are not ex expressive enough to extract useful node features in the presence of node attributes Zhang et al. (2019).
The initial node representation is fed into the same two-layered GCN above, and we take the concatenated representation Z (Z) ( Z as the input to WALKPOOL. The concatenation records local multi-hop information and facilitates training by providing skip connections. It gives a small improvement over only using the last-layer embeddings, i.c., Z = (() The hyperparameters of the model are explained in detail in Appendix C. The runtime of WALKPOOL can be found in Appendix H.
4.4 RESULTS
Synthetic datasets To show that WALKPOOL successfully learns topology, we use four synthetic datasets: Triangle lattice (ACC 0.415), 2D-Grid (ACC 0), Hypercube (ACC = 0), and Star (ACC 0). We randomly remove 10% links from each graph and run link prediction algorithms. AUC for WALKPOOL, SEAL, AA, and CN is shown in Table [ In these regular graphs the topological organizing rules are known explicitly. is therefore clear that a common- settroonnniggho--bbeeseee since none of the connected nodes have common neighbors. WalkPool successfully learns the organizing patterns without prior knowledge about the graph formation rules, using the same hyperparameters as all other experiments. For Triangle lattice and 2D-grid, WalkPool achieves 100%-100%-ooo AUC. Small errors are due hidden the test edges which act as noise; for fewer withheld links the error would vanish. In hypercube and Star, WalkPool achieves an AUC of 100% in all len trials. The star graph is heterophilic in the sense that no triangles are present; we indeed observe that AA and CN have AUC below 50% since they (on average) flip true and false edges.
heuristic (such as CN or AA) should fail for 2D-grid
Datasets without attributes We perform 10 random splits of the data. The average AUCs with standard deviations are shown in Table 2 the AP results and statistical signifi- cance of the results can be found in Appendix D. For WALKPOOL, we have considered both the cases with and without the DL node labels as input features.
From Table 2 WALKPOOL significantly improves the prediction accuracy on all the datasets we have considered. It also has a smaller standard deviation, indicating that WALKPOOL stable on independent data splits (unlike competing learning methods). Among all meth- ods, WALKPOOL with DL performs the best; the second-best method slightly below is WALKPOOL. without DI. In other words, although DRNL, slightly improves WALKPOO1, nonetheless, WALKPOOL achieves SOTA performance already without it.
WALKPOOL performs stably on both homophilic (high ACC) and heterophilic (low ACC) datasets, achieving state-of-the-ar performance where topology-base based houristics such as AA and Katz fail, WALKPOOL shows strong perfor- mance (it also outperforms SEAL by about 5% on Power). This confirms that walk profiles are expressive descriptors of the local network organizing patterns, and that WALKPOOL, can fit their parameters from data without, making prior topological assumptions. Experiments with 50% observed training edges can be found in Appendix F.
all. Remarkably, on Power and Router
Datasets with node attributes We apply WALKPOOL to extract higher-order informa- tion from node representations generated via unsupervised learning. We again perform 10 random splits of the data and report the average AUC with standard deviations in Table for AP see Appendix D. In Table g we show the results of unsupervised models with and
8

---

Published a conference paper at ICLR 2022
Data
USAir
NS
PB
Yeast
C.cle
Power
Router
E.coli
AA
95.0611.00 133
94.45:0.933
02.36:00.34
89.43:10.22
86.96111:00
58.79:10.88
56. 06.43330.51
06.36:00.34
Katz
92.88+1.0
91.83=1.10
92. 02.2220.33
92.21=0.61
86.31+1.89
65.39++1.9
38 03.6221..3 1.35
93.50=0.41
PR
916741.0
9189=1108
93.5440:10
92.7620.35
90.8221.209
66.00:1159
88.76111
06.57=0.41
WLK
96.63+0.11 73
98.57=0.51
03 83.03300.. 59
96.86+0.54
89.72+1.60
82.41+3.43
87.42+2.08
96,91+0.29
WLNM
95.96+1 10
98.61=0.19
93. 19:09.9001 17
96.02 96.02:0.52
66.18+111
81.76:20.98
91-11=0088
97 97.21=0.27
N2V
01.44+1.77
91.52-11.28
85.79+-0.78
93.67-00.6
84.11++1.27
76.22-40.02
65.46+00.0
90.82++1.49
SPC
74.2243.11
89.91=2.39
03.96=+0.96 8G
93.26=00400
51.90+2..77
91.78+00.11
09.79+2-42
94.92=0032
MF
94.08-+0.80
74.55-14.34
94.30+-0.53
90.28 0.699
85.901 1.74
50.63:41.110
78.03:11.63
93.76-
LINE
$1.47:+10071
80.63+1.90
76.95+-2.70 76
87.45+3333
09.21 40.21143.114
55.63++1.47
67. 07.154-2.11
29
SEAL
97.09
08.85.10.47
95.01
97.91
90.30111:35
87.61.1.57
96.38.11.45
97. 07.64
98.52110.85
00.422::000
06.16:10.33
12.4421:12
91.71:10.00
97.18100220
08.54:1:220
(P(DL)
98.68100.48
98.95:1:0.41
95.60:10337
96.37:10.25
92.79: 1.09
92.56:10.60
9..271:.228 96.58100.19
Table 2: Prediction accuracy measured by AUC on eight datasets (90% observed links)
without node attributes. Boldface marks the best, underline the second best results.
VGAE
ARGVA
GIC
NO WP
WP
NO WP
WP
NO WP
WP
Cora
91,98+0.54
94.64+0.55
92.45+1111
94.71+00.85
83.68=0.59
95.90-10.50
Citeseer
91.21+1.14
94.32+00.00
91.71+1.38
94.53+1.77
95.03=0.65
95.94:10.53
Pubmed
96.5110.14
19:1.11
96.62:10.12
98.5240.14
93.00=0.36
98.72++0.10
Chameleon
98.79+0.188
99.51100.08
98.23:+0.24
99.51++0.08
94.13=0.38
99.52:t0.08
Cornell
70.50-19.03
78.2147.51
81.73:44.82
8.93
03.32=7.47
80.6917.22
Texas
73.71499.29
76.02=7.05
8..05:88.29
75.62-45.80
65.13-+00.39
71.49-6.88.
Wisconsin
75.05++6.88
77.07++6.11
75.69+7.91
79.34++6.2
74.74 6.28
82.27:66.27
Table 3: Prediction accuracy (AUC) on datasets with node attributes (90% observed links).
without WALKPOOL. For all the unsupervised models and datasots, WALKPOOL improves the prediction accuracy. On the Pubmed dataset where the relative importance of topology over features greater, WALKPOOL brings about the most significant gains.
While traditional heuristics cannot include node altribules, WALKPOOL encodes the node attributes into random walk transition probabilities via the attention mechanism, which allows it to capture structure and node attributes simultaneously. The prediction accuracy relies on the unsupervised GNN which generates the inital node representation. We find that the combination of GIC and WALKPOOK yiclds the highost accuracy for all throe datascts. Importance of initial node representations is plain since WALKPOOL is not designed to un- cover structure in node attribules. Nonetheless, WALKPOOL greatly improves performance of unsupervised GNN on the downstream link prediction task.
DISCUSSION
The topology of graph plays much more important role in link prediction than node classification, even with node attributes. Link prediction and topology are entangled, so to speak, since topology is defined by the links. Most GNN-based link prediction methods work with node representations and do not adequately leverage topological information.
Our proposed WALKPOOL, to the contrary, jointly encodes node representations and graph topology into learned topological features. The central idea is how to leverage learning: we apply attention to the node representations and interpret the attention cocfficients as transition probabilities of graph random walk. WALKPOOL is a trainable topological heuristic, thus explicitly considering long-range correlations, but without making ad hoc assumptions like the classical heuristics. This intuition is borne out in practice: combining supervised or unsupervised graph neural networks with WALKPOOL yields state-of- the- art performance Remarkably, WALKPOOL achieves this with the same set of hyperparameters on all tasks regardless of the network type and gencrating mechanism.
broad range of benchmarks with diverse structural characteristics.
ACKNOWLEDGCENNTS
LP would like to acknowledge support from National Natural Science Foundation of China under Grand No. 62006122, CS and ID were supported by the European Research Council (ERC) Starting Grant 852821 SWING.

---

Published a conference paper at ICLR 2022
REFERENCES
Robert Ackland et al. Mapping the us political blogosphere: Are conservative bloggers more prominent? In BlogTalk Downunder 2005 Conference, Sydney, 2005.
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25 (3):211-22)) 2003.
Vladimir Batagelj and Andrej Mrvar. Pajek datasets website. http://vlado fmf uni uni-lj. si
2006.
Andrew P Bradley. The of the area under the curve in the evaluation of machine learning algorithms. Paltern recognilion, 30(7):1145 11114-5-111,,,,, 1997.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint urXie:2006.01 07988,, 2020.
Mark Craven, Andrew McCallum, Dan PiPasquo, Tom Mitchell, and Dayne Freitag, Learn- ing to extract symbolic knowledge from the world wide web. Technical report, Carnegio- mellon univ pittsburgh pa school of computer Science, 1998.
C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citescor: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital librories, pp. 89 98, 1998.
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 864, 2016.
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 networks. ar preprint arXie:1609.02000 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXim:1611.07300 2016b.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8))30-31) 37, 2009.
David Liben-Nowell and Jon Kleinberg. The link iin-prrdiction problem for social networks. Journal of the Americon society for information science and technology, 1811111019,, 2007.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390(6):1150-1170, 2011.
Linyuan Lü, Matús Medo, Chi Ho Yeung, Yi-Cheng Zhang, Zi-Ke Zhang, and Tao Zhou.
Rocommender systems. Physics Reports, 519(1):1-49, 2012.
Costas Mavromatis and George Karypis. Graph infoclust: Leveraging cluster-level node information for unsupervised graph representation learning. arXiv:2009.00 069466 2020.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automat- ing the construction of internet portals with machine learning. Information Retrieval, (2):127-163, 2000.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415 2001.
Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzen- shtat, Michal Sheffer, and Uri Alon. Superfamilies of evolved and designed networks. Science, 303(3663):1538 1542, 2004.
10

---

Published a conference paper at ICLR 2022
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification ion. In 10th International Workshop on Mining and Learning with Graphs, volume 8, pp- 1, 2012.
Mark EJJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3))036104, 2006.
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.
Liming Pan, Tao Zhou, Linyuan Lü, and Chin-Kun Hu. Predicting missing links and iden- tifying spurious links via likelihood analysis. Scientific Reports, 6(1):1 10, 2016.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adver- sarially regularized graph autoencoder for graph embedding. 1r0i::1802 04407, 2018.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen:
Geometric graph convolutional networks. Xiv preprint ar arXiv:2002.05555 2020.
Yanjun Qi, Ziv Bar-Joseph, and Judith Klein-Seetharand Evaluation of different biological data and computational classification methods for use in protein interaction prediction. Proteins: Structure, Functãon, and Bioinformatics, 63(3):490-500 2006.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Compler Networks, 9(2)xnnab014, 2021.
Shai S Shen-Orr, Ron Milo, Shmoolik Mangan, and Uri Alon. Network motifs in the tran- scriptional regulation network of escherichia coli. Nature genetics, 31 (1)):64-- 2002.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weiseeiler-Ichman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Yunsheng Shi. Zhengjie Huang, Wenjin Wang, Hui Zhong, Shikun Feng, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classifica- lion. arXiv:2009.0330 03509, 2020.
Neil Spring, Ratul Mahajan, and David Wetherall, Mcasuring isp topologies with rocketfuel. ACM SIGCOMM Compuler Commmmicatiin Review, 32(4):133 145, 2002.
Zachary Stanfield, Mustafa Coskun, and Mehmet Koyutürk. Drug response prediction as link prediction problem. Scientific Reports, 7(1):1-13, 2017.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In Proceedings of the 24th International Conference on World Wide web, pp. 1067-1077, 2015.
Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery. (333):447477,, 2011.
Ashish Vaswani, Noam Shazcer, Niki Parmar, Jakob Uszkorcit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv:1710.10900 2017.
Christian Von Mering, Roland Krause, Berend Snel, Michael Cornell, Stephen G Oliver, Stanley Fields, and Peer Bork. Comparative assessment of large-scale data sets of protein- protein interactions. Nature, 317(6687):399 -39--433, 2002.
11

---

Published a conference paper at ICLR 2022
Duncan Watts and Steven H Strogatz. Collective dynamics of "small-world networks. nature, (96664)):4440414 1998.
Muhan Zhang and Yixin Chen. Weisfelle-leeman neural machine for link prediction. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 575- 583, 2017.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances Neural Information Processing Systems, 31:5165-511 5175, 2018.
Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. Beyond link prediction: Pre- dicting hyperlinks in adjacency space. In Thirty-Seane Second AAAT Conference on Artificial Intelligence, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. or Nin: 16103, 2020.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: comprehensive review. Computational Social Networks, 6(1):1-23, 2019.
12

---

Published a conference paper at ICLR 2022
APPENDIX A. BENCHMARK DATASETS DESCRIPTION
Brief description of the benchmark datasets is as follows. For the datasets without node attributes, we have considered:
USAir [Batagelj & Mrvar 2006: graph of US airlines with 332 nodes and 2126
edges; ACC 0.625.
NS (Newman 2006 the collaboration relation of network science researchers with 1589 nodes and 2742
edges; ACC = 0.638.
PB (Ackland et al.
graph of hyperlinks between weblogs US politics with 1222 nodes and 167 14 edges; ACC = 0.320.
2005
Yeast (Von Mcring et al.
2002 a protcin-protein interaction graph yeast with
2375 nodes and 11693 edges;
ACC = 0.306.
C.ele (Watts Strogatz 1998): the biological neural network of C.elegans with
297 nodes and 2148 edges; ACC 0.292.
Power (Watts & Strogatz
1998): the topology of the Western States Power Grid
of the United States with 4941 nodes and 6594 edges; ACC 0.080.
Router (Spring et al. 2002 the router-level Internet with 5022 nodes and 6258
edges; ACC ACC 0.012.
E.coli (Zhang et al
2018 the pairwise reaction relation of metabolites in E.coli
with 1805 nodes and 15660 edges; ACC = 0.516.
As graphs with node attributes, consider three citation graphs with publications described by binary vectors indicating the absence absence/preseecee of the corresponding dictionary word:
Cora [McCallum al. 2000): citation graph with 2708 scientific publications
and 5278 links. The dictionary consists of 1433 unique words; ACC 0.241.
Citeseer (Giles al.
1998):
: the dataset consists of 3312 scientific publications
with 4552 links; the dictionary consists of 3703 unique words; ACC = 0.141.
Pubmed Namata et al.) 2 the dataset consists 19717 scientific publications with 44324 links. The dictionary consists of 500 unique words; ACC 0.060.
We also consider a Wikipedia page graph where nodes represent. web pages and edges rep- resent hyperlinks between them. Node features represent several informative nouns in the pages:
Chameleon Rozemberczki et al. 2021 Wikipedia page-page graph under the topic chameleon. The graph consists of 2277 nodes and 31371 edges where each node has an attribute vector of dimension 2325; ACC = 0.377.
Finally, we consider three webpage graphs which include web pages from computer science departments of various universities, node features are the bag-of-words representation of web pages.
1998 webpage graph with 183 nodes and 277 edges, and the node attribute has dimension 1703; ACC 0.167.
Cornell Craven et al.
Texas (Craven et al.
1998): webpage graph with 183 nodes and 279 edges, and
the node attribute has dimension 1703; ACC 0.198.
Wisconsin (Craven et al. 1998): : webpage graph with 251 nodes and 450 edges, and the node attribute has dimension 1703; ACC = 0.208.
The benchmark dataset properties and statistics are summarized in Table
APPENDIX B. ABLATION STUDY
We conduct ablation studies of WALKPOOL by excluding or including only each the node-,
link- and graph-level features in 4 We used short notations (node") {node" _ode
13

---

Published a conference paper at ICLR 2022
Dataset
USAir
N8
PD
Yeast
C.cle
Power
Router
E.coll
Cora.
Citeseer
Pubmed Chamcleon
Cornell
Toxas
Wisconsla
Nodee
332
1589
1222
2375
297
1911
6022
1806
2705
S312
19717
2277
185
183
251
Edges
2126
2742
16714
11690
10000
1278
46324
227
ACC
0,025
0.638
0,320
0.005
0.292
0,080
0,012
0,536
0241
0.41
0.000
0.77
0.167
0.198
0.208
Deneity
3.66e2
2.17
2.21e-2
4.16-3
5.00e4
9.61e-
1.4e-3
2.26e44
1.35-2
1.46-2
Attributed
No
No
No
No
No
No
No
No
Yos
Yes
Yes
Yes
Yes
Yes
Yes
Table 4: Benchmark dataset properties and statisties.
;T)), and similarly for [link"), (Agraph") ). The ablation results for the C.ele dataset is shown in the In Table.
E {2,
Feature feat
W12
[node"}
[link"]
{Agraph"}
AUC (using only feat)
87.90
91.88
92.44 91.08
92.29
AUC (using WP)
92.69
92.66
92.65
92.82
Table 5: Ablation study in C.ele
APPENDIX C. HYPERPARAMTERS
The hyperparamters to reproduce the results are summarized in Table 6
For the split of training, validation and testing edges, we have adopted different setups for datasets with and without node attributes to consist with previous studies. In particular, for datasets without node attributes, 90% of edges are taken as training positive edges and the remaining 10% are for testing positive edges. The corresponding same number of negative edges are sampled randomly for training and testing. Then among the training edges. randomly selected 5% for validation. The observed graph from which the enclosing subgraphs are sampled consists of all the training positive edges. For the datasets with node attributes, all the edges are divided into 85% for training, 10% for lesting and 5% for validation. The observed graph is built only based on the training edges. Some sludies of link prediction choose to keep the observed graph connected when sampling the test edges, while others do not adopt this option. For the experiment results shown in the paper, we sample the test edges uniformly random without ensuring the observed graph connected.
For sampling the enclosing subgraphs, we set the number of hops as 2 except 3 for the Power datasct. The 2-hop subgraphs sampled from E.coli and PB datasets and Pubmed are relatively numerous in nodes. Thus we set a maximum number nodes per hop for these two datasets to fit. into memory. In particular, for each hop during sampling, we randomly select a maximum of 100 nodes if the sampled nodes exceeds.
For WALKPOOL, We set To = for the cutoff of walk length in all experiments. When To becomes large, the transition probabilities converges to constant, as the random walk reaches stationary. Therefore, a larger value of introduces little further information. From experiments, we find that introducing larger To will not increase the accuracy notably.
For the classifer, we use a MLP with layer sizes 72 1440 1440 - 720 - 72 - 1. We use Relu the activation function for the hidden layers, and sigmoid function for the output layer.
APPENDIX D. RESULTS MEASURED BY AP AND STATISTICAL SIGNIPICANCE OF RESULTS
The prediction accuracy measured by AP for datasets with and without node attributes are shown in Table & and Table g respectively. From the tables, WALKPOOL still performs best with the AP metric.
To verified the statistical significance of the results, performed a two-sided hypothesis test with the null hypothesis that two independent samples (corresponding to the results of WalkPool and the second best algorithm) have identical average. We compute the corre- sponding p-value on a per dataset basis for the eight datasets without node attributes. The results are shown in Table 7 The second best algorithm is SEAL except in C.ele (where
14

---

Published conference paper at ICLR 2022
Name
With attributes
No attributes
optimizer
Adam
Adam
learning rate weight decay
50-5
50-5
0
0
test ratio
0.1
0.1
validation ratio batch size
0.05 of training edges
0.05 of all edges
32
32
epochs
50
50
hops of enclosing subgraph dimension of initial representation (
(+) 2
2
16
32
initial representation (
ones or DL
unsupervised models
hidden layers of GCN
32
32
output layers GCN hidden layers of attention MLP
32
32
32
32
output layers of attention MLP
32
32
walk length cutoff Te heads
7
7
2
2
Table 6: Default hyperparameters for reproducing the reults. (+): 3-hop for the Power dataset.
Data
USAir
NS
PB
Yeast
C.ele
Power
Router
E.coli
Second Best
97 07.0920.77
98 8540
95 00.11
07.91.0552
90. 10.32+1.00
91. 7840.8
96.38+1
07.6440.22 22 98. 58+00.00111
(PLDL)
98 6840..4
98 96+0.41
41
95 05.60=0.37
98.37
00.27
92.70+1.00
92.
02.56+0.660
97.27+0.30
p-value
2.18 10m3 6.18 10 1600 1001000
2.56 10
6.00 10
9.90 10
8.68 10 7,80 10
Table 7: p-valuc by comparing WP and second best algorithm on eight datascts with no attributes.
Data
USAir
NS
PB
Yeust
C.ele
Power
Router
E.coli
95.3611
91.1620.93
22.3620.110 46
89.5320.63
86.461
58.76 58.76:20.89
56.50::0
96.05:20.25
Katz
95.0521.08
05.2320.39
85.9311.60
61.222..5
918320030
PR
95.08+1.J0
1..11
02.97+0077
96.47+0.43
69.56+ 1.57
80.56++0.91
64.91
96.41+0.33
WLK
96.82+0.84
08.79=0040
93.34+0.50
96.82:0.335
88.90122
83.02:+3.19
86.59+2. 23
97:25=20.22
WLNM
95. 05.96=11.11
98.81=0.19
6..99.0066 64
96.10:20.38
85.0842 2.05
87.16:20.77
93.53#11.00
97.50=0.23
N2V
89.71+22.97
04.28-0..11
84.79+ 1.03
94.90-0.38
83.124-1.0 1.90
81.49-+0.88
68.66+
90.87++1.48
SPC
78.0742..2
90.83+22.16
86.57+0.66
94.63+00.56
62.07+-2.40
91.00++0.58
73.53+1.47 1.47
96.08-+0.37
MF
94.36100799
78.4113.85
93.56.10771 71
92.01:00.47
83.63122009
53.50:11.22
82.5911.35
05.5910.31
LINE
79.70.111.76
8..17.1.65
78.82.12771
90.55.12.399
12.72
56.66.11.43
71.92.1.53
86.45.11.82
SEAL
97.13200.80 80
99.06=0.33
91.55 13
98.33=0.37
89. 89.4821.88
89.55 29
96.23=11771 71
98.03=0.20
(onon
98.7420.117
(DLDL)
08.66:20.55
99.09:1:.29
95.28:0041
98.64:2..28
91.53=1.33
93.07::0.99
97.20=0.38
98.7910.221
Table 8: Prediction accuracy measured by AP eight datasets (90% observed links) with- out node attributes. Boldface letters are used to mark the best results while underlined letters indicate the second best results.
the second best PR) and Power (where the second-best is SPC). Recall that a p-value of 0.05 or less is customarily considered statistically significant. We see that for all but the NS and Router datasets the p-value is below 0.05. For most datasets is orders of magnitude below. The AUC on the NS dataset is already very close to 100, thus leaving little space for improvement; for Router it is the large variance of SEAL that gives a p-value a bit above 0.05. Note that even for Router and NS the empirical mean of WalkPool is better. More trials should easily break the statistical tie even in those cases, but we used the same 10 splits SEAL for fair comparisons.
15

---

Published a conference paper at ICLR 2022
VGAE
ARGVA
GIC
NO WP
WP
NO WP
WP
NO WP
WP
Cora
02.65:2.555
96.11=0.53
93.11=1.005
95. 06.2320.81
93. 03.15=0.48
95.97:10.57
Citeseer
02.28-40.22
94.89+0.89
92.69+0.85
95.04+1446
95.11=0.65
96.04=:0.63
Pubmed
96.60++0.13
98.46=0.14
96.52=+0.20
08.49=0.14
92.32=0.37
98.65=00.15
Chameleon
08.79:10.2
99.50=+0.15
96.19:20.22 28
99. 29.4820.15
93.31=0.50
99 1610.15
Cornell
75.34:18.24
82.74=7.89
84.66:25..45
85.92+7.445
06.94=8.20
84.18+8.39
Texas
78.50=18.18
5..78
83.10:8.26
81.21
70.89=9.08
79. 70.0026.31
Wisconsin
79.56:+6.32
82.50=4.96
78.72:+6.24
82.2558.10
78.27=4.78
84.45-144.0
Table 9: Prediction accuracy measured by AP on seven datasets (90% observed links) with node attributes.
APPENDIX E. LOCALITY OF GRAPH-LEVEL FEATURES
Let == CVVV E) be enclosing subgraph, and {1,2) be the candidate link. We denole the random walk Iransition matrices on G and G as and Q, respectively. For any node 2,y E V, let d(x,y) v) be the shortest path distance on the graph. We define the distance from x to the candidate link to be d(z) = min [d(x 1), d(x; 2)}. We have the following result.
Proposition 1. Let V (a e V, d(x) r}, then [P* z.y (Q for all x,y V
Proof. We prove the result via induction. When 1, after the node- wode-wise normalization from the softmax function in (2), the elements of P and Q are identical among nodes that. not neighbors of the candidate link, i.e., V (ar V,d(x) 1}.
Now suppose the claim holds for т. Let I = {a E V. (()) s т), let OI be the set of nodes that are adjacency to but not in I, and let I be the set of rest nodes in the graph. We can arrange the order of the nodes that such that P and P are of the following block form
PIς PI,T P POI.I
P P
III
P7,0
P P P
PøI,ar PAI.I-
=
OI,
Pai,a
(5)
Prçar
Pr-1-/
P77.I
where PI,r is the block matrix confined to I and other blocks are defined similarly. By definition, PI,r- and Prez Multiplication of the block matrices gives
p Z T
= Pre.zrP + PI
(6)
We can do a similar computation to obtain Oft with all replaced by Q in the above equation. By assumption, we have
PI- Qrear
I = VoI
Pzc,Ie Qre,re, P = O
(7)
OI, I' V", therefore we obtain P P induction.
Qr-ze As I== V++1,, the claim follows by
APPENDIX F. RESULTS WITH 50% OBSERVATION
We further test of the performance of WALKPOOL under the setup of sparse training set. In particular, we keep only 50% positive links of the graphs for training and use the rest links for testing. The same number of negative links are sampled randomly for the traning set and test set. The results measure by AUC and AP are shown in Table 10 and respectively.
APPENDIX G. MSE LOSS AND BCE LOSS
As link prediction is a classification problem, usually adopt classification loss such as binary cross-entropy (BCE). We opted for MSE based on the following heuristic. In node classification, categories usually clearly defined. For example, in citation graph, the category a paper is near-definit. Meanwhile, the topology of real graphs often fuzzy and evolving. In co-authorship graph, some authors who have not published together today
16

---

Published conference paper at ICLR 2022
Data
USAir
NS
PB
Yeast
C.ele
Power
Router
E.coli
AA
88.61 +-044
77.13+0.75
87.06+00.17
82.63+0.27
73.37--00.
53.38-+0.22
52.94++0.28
87.66+0.56
Katz
88.91+0.551
82.30+00.03
01.25+0022
88.87+0.22
79:90++0.59
57.3440.51
54.39+0038
80.81=0046
PR
00.37.1062
80.32
92.2311.21
89.35.10.29
84.9510.58
57.34.10.52
54.4410.38
02.96.1.433
WLK
01.93.0.71
$7.27.1.77
02.54.10.33
91.15.10.35
83.2910..8
63.44.1..9
71.25
92.38 10.46
WLNM
91.42:10.95
$7.61 1.63
00.93
92.22 10.32
75.724 1.33
64.09-10.76
86.10-0..52
-..80
N2V
81661:
80.29:1.20
79.2920.65
90.18:0.17
75.534 23
55, 55.40:00.81
62 02.45:0088
81.3320.81
SPC
63.42:3.41 41
79.63:1.34
78.0611.00
89.73:10.28
47.3010.91
56.51
53.87
02.00:20.50
91.28+:0.7
62.95=1.03
03.27=0.10
84.99+0.45
78-19+1773
50.53+0.00
77-19+0.66
91.75=0.33
LINE
12.51+12.19
65.96=1.00
75.53+1.78
19.1147.90
59 59/16#7.08
53.44#1833
62 12.43+3.10
71.50=11.10
00.36++0.67
90.88+11.18
00.79+00.25
93.00+0.54
65.84+1.10
86.64+11.55
94.18+0.44
(onnn)s)
95.16++0.00 70
90.08=11 1.00=1.04 04
94.60+0.20
94 14-00-0.22
87.83=0.83
67.03+0.77
89 09+0.02
95.37:10.22
WP(DL)
95.50:10.74
90.97.1..99
94.57:00116
95.00:10.21
87.62111399
67.72.10.86
88.13:10.61
95.33-10.30
Table 10: Prediction accuracy measured by AUC on eight datasets (50% observed links)
without node attributes. Boldface letters are used to mark the best results while underlined letters indicate the second best results.
USAir
Yeast
C.ole
Power
E.coli
89.39-0.39
77.14.10.74
87.24
82.68.10.27
73.40_0.7
53.37 10.77.0..23
12.24
89.0110.49
Katz
91.29-10.6
62.69100.88
91.54:0.16
02.22.10.11
79.94-0.7
57.6310.52
60.87 1.22
91.93:10335
91.9320.50
62.7310.90
91. 91.9222025
92.31.022
81.15-0.86
57.6110.36
61.01-0.30
916810.28
WLK
93.31:0.51
19.9711002
92.34:0334
98.35100.0 46
03.20000000
63.9711.81
75.19:33448
94.51.0.32
WLNM
92.54.0.81
00.1011.11
91.0110:20
93.933.0.0
76.12 1.08
66.43.10.85
86.12.10.68
94.47.10.21
N2V
82.51=2.08
86.01+0.87
77.21=0.97
92-15:0.22 23
72.91=1.7
00.8340.00 68
66.77=0.57
85.1140.91
SPC
70.18=2.16
81.1611.26
81 81.0020811
92.07:0.27
55.31=0933
59. 19.10:1:06
59.13:3.22
91.1110.29
02.33=0.90
66.62++0.8
92.63+0.33
87.28+0.57
77.82-1.85
52.45+0.63
81. 81.25+0.56
LINE
71.75+11.86
71.53+0.97
78.72+1.22
83.0649.700
60.71-6.26
114:3-40
64.8746.76
76.984 14.45
SEAL
93.42.10.19
05.12.10.38
1..28.11.25
87.79
WP(nnes)
05.39-0.73
12.15-00.81
94.1440.27
96.04+0. 16
96.49.10.97
80.26-40.64
89.21:10.44
96.35-+0.24
WP(DL)
95.87:10.74
92.33-0.76
94.2240.27
96.15:10.13
86.25-1.12
69.79-10.7
89.17:0.555
98.36-10.44
Table 11: Prediction accuracy measured by AP on eight datasets (50% observed links) without node attributes. Boldface letters used to mark the best results while underlined letters indicate the second best results.
17

---

Published a conference paper at ICLR 2022
may have submitted paper that will come out tomorrow. We therefore expect less peaky distribution of link probabilities than node classes, and we choose loss that minimizes the miscalibration the model. In this context where we want predict probabilities as accurately possible, the MSE loss is known the Brier score (another textbook use of the Brier score is to calibrate the chance-of-rain forecasts).
We have experimented with both the binary cross-entropy (BCE) loss and the MSE loss, and we observed no discernible difference. For example, for the eight datasets without node at- tributes (the last line of Table 2), accuracies measured by AUC when using MSE/ AISE/BCE BBCE loss are: 98.68 08: 98.95/98.85; 98.85; 95.60/95.69; 98.37/98.37; 92.79/92.83, 92.56/92.58 97. 07.27/97.33 98.58/98.67.
APPENDIX H. RUNTIME OF WALKPOOL
The runtime of WalkPool is similar to that of SEAL when using the same number of hops to construct the subgraphs. On a classical dataset USAir, WALKPOOL takes 129.62s for 50 epochs with 1-hop subgraph sampling, while SEAL takes 145.94s. The configuration of WALKPOOL used throughout our paper has two GCN layers followed by several linear layers for computing the powers of matrix P, and a four-layer MLP classifier. As such, from the perspective of runtime, the trainable part of WalkPool architecture is no more complex than that of a typical GNN. For very large datasets, the most time-consuming step is to extract the euclosing subgraphs this is true for WalkPool and any other subgraph-based link prediction algorithm.
18


Reviews:
[{"review_id": "l-6rq6O6dJ", "reviewer": "Reviewer_yAGw", "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": "Strengths:\n(1) The paper is clearly written\n(2) I find the walk based approach to be interesting (with several weaknesses)\n\nWeakness:\nNo conceptual difference with GNN: In my understanding, when we compute $P^{\\tau}$, it combines the $\\tau$ hop information around a node to compute its embedding. In this aspect, I did not understand any conceptual difference with GNN. What aspect of it is making the difference?\n\nLoss function: At the end, LP is a classification task. From this aspect, MSE loss minimization may not be suitable--- a simple classification or ranking loss should be more suitable. Did the authors try them?\n\nAUC: I suspect that for most of the datasets, the difference of WALKPOOL with baselines is not statistically significant. Can the authors clarify about it?\n\n", "summary_of_the_paper": "The paper provides a method for link prediction based on random walk based pooling method (WalkPool). It aggregates the probabilities of the adjacent structure of a node or link to design the node embeddings. Finally, it shows superiority of the method against baselines via AUC and AP.", "summary_of_the_review": "The walk based approach is interesting but the paper lacks novelty, clear articulation about high or low level difference of WalkPool with GNN. Also, MSE  loss is chosen for a clear classification task. The results are weak too. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "bOrn5ujjFxw", "reviewer": "Reviewer_C9p9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\nThe paper is well-written; the introduction of the previous work is organized. Description of the SEAL algorithm is very insightful and clear.\n\nWeaknesses:\n\nThe attributed network datasets concsidered is a bit limited. Can there be more datasets available for evaluation?\n\nThe final features extracted are mainly specified by human. Though effective, it leaves an open question that whether thses sorts of features can be leared adaptively?\n\nThe proposed method follows the framework of the SEAL algorithm, and the authors should exphasize the differences between the two methods and what makes the propose method more advantageous. ", "summary_of_the_paper": "This paper proposes a neural architecture for predicting missing links in a graph by designing a so-called WalkPool scheme. WalkPool exploits node features (from a GNN) to compute the transition probability between the nodes, and then manually design a number of links that are extracted from the oder-k encolosing sub-graphs covering a pair of nodes for link prediction. The authors also defined a delta-graph feature that is the sub-graph level feature difference before and after removing the node pairs with which the link is to be predicted. Experimental results are quite optimistic on about 10 benchmark datasets.", "summary_of_the_review": "\nOverall the paper is nicely written and organized, and provides useful thought in the problem of link prediction with or without node features. Experimental results are also promising. However I have a few technical details I would like to discuss.\n\n(1) The authors used feature-based similarty (like in GAT type of algorithms) to define the transition probbaility matrix, which takes the place of the topology-based transitiona matrix by and large. Is there a way to combine the information from both?\n\n(2) The pooling part is a bit confusing to me, in that it seems that the WALKPOOL indeed does not perform pooling but instead use pre-defined features, while pooling is usually for a set (of objects such as nodes) with varying numbe of elements. Can authors add more details of the pooling used in the SEAL and why WALKPOOL is considered a pooling scheme?\n  ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7RA_0Pji2LW", "reviewer": "Reviewer_ye2u", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. Building the latent subgraph from embeddings is an interesting idea. \n2. The extract features somehow encodes path information which may be useful for link prediction.\n3. Comprehensive experiments are conducted.\n\nWeaknesses:\n1. Motivations in the Introduction section are not clearly stated.", "summary_of_the_paper": "The paper proposes a new link prediction method called WP, based on treating link prediction as a subgraph classification problem, where the link of interest is surrounded by the subgraph. Existing GNN architectures could be used for learning node embeddings. With node embeddings, a latent subgraph could be built using self-attention, where attention scores are used for computing the subgraph edge weights. With the latent subgraph, a set of features could be computed to be used as the features for the link of interest. The features will be used for subsequent link prediction. Essentially, the proposed WP method is a feature extractor for links (or its surrounding subgraph).", "summary_of_the_review": "The paper proposes a pooling method (i.e., a latent structure feature extractor) for learning features that describe links (i.e., the surrounding subgraphs of the links). Building the latent subgraph from embeddings turns continuous information back to discrete graph space, which facilitates feature extraction. The framework remains end-to-end learnable. The extracted features summarizes multi-hop path information, which somehow reflect higher order structural information. Experiments on multiple real datasets are conducted.\n\nIn general, the paper proposes a neat idea with good experiment design. The current draft could be further improved by revising its Introduction section, as many claims are not clear and do not seem to motivate the method design. For example, Figure 1 does not provide much information about the idea. Also, I think the word \"topology\" does not well describe the proposed idea.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-CfsYg1iQB1", "reviewer": "Reviewer_MHUH", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n- The paper provides an elegant formulation of the link prediction problem. The execution of the proposed methodology is also interesting.\n- The paper is clearly written, presenting the proposed model in a rigorous way but at the same time providing good motivation.\n- The experimental evaluation is quite thorough. \n\nWeaknesses:\n-\tLack experiments on benchmark (artificial) graphs. This could further increase our understanding of the functioning of the model\n-\tThe baseline models could be enhanced. Although the list is quite complete, some of the used models are not tailored for the link prediction task.\n\n**Detailed comments.**\n\nAs I mentioned above, I really enjoyed reading the paper. Despite building upon ideas presented in  SEAL, the formulation is interesting. Besides, the arguments made seem to be valid. Yet, some points are not very clear and need further elaboration. Next, I summarize key points related to the paper.\n\nTo begin with, although the paper uses standard benchmarks for link prediction, I would expect to have some experiments on artificial datasets in order to better understand the functioning of the model. As I can see, most of the networks used have really high clustering coefficient---which is not the case for the majority of real-world graphs. Having artificial networks where one could control ACC would be very helpful.\n\nIn the case of the absence of node attributes, the paper concatenates the outputs of the three-layer to obtain the final node representation. Aren’t the embeddings of the final layer enough for this? Please elaborate more on this aspect.\n\nAlthough spectral clustering has been widely used before, I think it is not an appropriate baseline for link prediction. I would rather be in favor of using other unsupervised feature learning models (e.g., LINE, NetMF).\n\nThe datasets used are quite small in terms of the number of nodes and edges, and there is no discussion about the running time of the proposed model. How does WalkPool’s running time compare against SEAL?\n\n", "summary_of_the_paper": "The paper introduces WalkPool, a model for link prediction that relies on GNNs. The main idea is to jointly encode node representations and graph topology information into node features which could be learned in an end-to-end-manner. The proposed problem formulation is interesting: the transition probabilities to capture proximity among nodes are computed on top of a latent graph which is the outcome of an attention mechanism on node features. The proposed methodology is presented clearly. Besides, the authors have performed experiments on various graphs, and the performance of WalkPool is compared against state-of-the-art baseline models.", "summary_of_the_review": "Overall, I believe it’s an interesting approach that offers a new perspective on the link prediction task. Despite building upon ideas presented in previous work (SEAL), the paper makes progress in presenting an elegant methodology. Some aspects related to the experimental evaluation should be addressed.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new link prediction algorithm based on a pooling scheme called WalkPool. The main idea is to jointly encode node representations and graph topology information into node features and conduct the learning end-to-end. The paper shows the superiority of the method against the baselines.

Strength
* The paper is generally clearly written.
* A new method is proposed, which is technically sound.
* Many experiments are conducted to verify the effectiveness of the proposed method.

Weakness
* The novelty of the work might not be so significant.  There is a similarity with the SEAL algorithm.

The authors have addressed most of the problems pointed out by the reviewers. They have also conducted additional experiments.
Decision: Accept (Poster)