Neural Link Prediction with Walk Pooling
Year: 2021

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.

heading: 1 Introduction
text: Graphs are a natural model for relational data such as coauthorship networks or the human protein interactome. Since real-world graphs are often only partially observed, a central problem 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 responses (Stanfield et al., 2017), or completing the knowledge graph (Nickel et al., 2015). It underpins recommender systems in social networks (Adamic & Adar, 2003) and online marketplaces (Lü et al., 2012). Successful link prediction demands an understanding of the principles behind graph formation.
Observed graph Candidate links
Subgraph
Prefer triangles with large weights
Prefer quadrangles with large weights
Completed graph
see Figure 1 for an illustration. But organizing rules are not universal across graphs and
1Mathematical topology studies (global) properties of shapes that are preserved under homeomorphisms. Our use of “topology” to refer to local patterns is common in the network literature.
they need to be learned. The centerpiece of our algorithm is a new random-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 (e.g., Triangle lattice in Figure 1) graphs unlike hardcoded heuristics or 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-ofthe-art link prediction results on all common benchmark datasets, sometimes by a significant margin, even on datasets like USAir (Batagelj & Mrvar, 2006) where the previous state of the art is as high as 97%.

heading: 1.1 Related work
text: Early studies on link prediction use heuristics from social network analysis (Lü & Zhou, 2011). The homophily mechanism for example (McPherson et al., 2001) asserts that “similar” nodes connect. Most heuristics are based on connectivity: the common-neighbor index (CN) scores a pair of nodes by the number of shared neighbors, yielding predicted graphs with many triangles; Adamić–Adar index (AA) assumes that a highly-connected neighbor contributes less to the score of a focal link (Adamic & Adar, 2003). CN and AA rely on paths of length two. Others heuristics use longer paths, explicitly accounting for long-range correlations (Lü & 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 a link by the probability that a walker starting at one end of the link reaches the other in the stationary state under a 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, 2016b) or SEAL Zhang & Chen (2018) use learned node-level representations that capture both the structure and the features, yielding 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, 2017). 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., 2020).
Algorithms based on two-body score functions achieved state-of-the-art performance when they appeared, but real networks brim with many-body correlations. Graphs in biochemistry, neurobiology, ecology, and engineering (Milo et al., 2004) exhibit motifs—distinct patterns occuring much more often than in random graphs. Motifs may correspond to basic 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 as 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 classification 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. Nevertheless, 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.

heading: 1.2 Our contribution
text: Following Zhang & Chen (2018), we approach link prediction from via subgraph classification. Instead of encoding relative topological information through node labels, we design a new pooling mechanism called WalkPool. WalkPool extracts higher-order structural information by encoding node representations and graph topology into random-walk transition 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 descriptors 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 highly-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 GNNs and trained in end-to-end. It achieves stateof-the-art results on all common link prediction benchmarks. Our code and data are available online at https://anonymous.4open.science/r/WalkPooling_Ano.

heading: 2 Link prediction on graphs
text: We consider an observed graph with N nodes (or vertices), Go = (V, Eo), with V being the node set and Eo the set of observed links (or edges). The observed link set Eo is a subset Eo ⊂ E∗ of the set of all true links E∗. The target of link prediction is to infer missing links from a candidate set Ec, which contains both true (in E∗) and false (not in E∗) missing links. Problem 1. (Link prediction) Design an algorithm LearnLP that takes an observed graph Go ⊂ G and produces a link predictor LearnLP(Go) = Π : V × V → {True,False} which accurately classifies links in Ec.
Well-performing solutions to Problem 1 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 1, . . . , N and represent G by its adjacency matrix, A = (aij)Ni,j=1 ∈ {0, 1}N×N with aij = 1 if {i, j} ∈ Eo and aij = 0 otherwise. Nodes may have associated feature vectors (xi ∈ RF , i ∈ {1, . . . , N}); we collect all feature vectors in the feature matrix X = [x1, · · · ,xN ]T ∈ RN×F . Integer powers of the adjacency matrix reveal structural information: [Aτ ]ij 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−1A where D = diag(d1, . . . , dN ) and di = ∑ j aij = |N (i)| is the degree of the node i. Thus the probability pij = d −1 i aij that a random walker at node i transitions to node j is inversely proportional to the number of neighbors of i. An extension to graphs with non-negative edge weights W = (wij) is straightforward by replacing aij by wij . Powers of P are interpretable: [Pτ ]ij is the probability that a random walker starting at node i will reach node j in τ hops.
As we show in Section 3.2, transition probabilities in WalkPool are determined as coefficients of an attention mechanism applied to learned node features. The node features are in turn extracted by a parameterized function fθ, which distills input attributes and to an extent graph topology into an embedding (a vector) for each node. The feature extractor fθ : {0, 1}N×N ×RN×F → RN×F ′
takes as input the adjacency matrix (which encodes the graph topology) and the input feature matrix, and outputs a distilled node feature matrix. It should thus be equivariant to node ordering in A which is satisfied by GNNs.

heading: 3 WalkPool for link prediction by subgraph classification
text: 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 Gk{i,j} ⊂ G o enclosing the target link; and
then computes random-walk profiles for sampled subgraphs with and without the target link. Random walk profiles are then fed into a link classifier.
Computing walk profiles entails
1. Feature extraction: Z = fθ(A,X), where fθ is a GNN; 2. Transition matrix computation: P = AttentionCoefficientsθ(Z;G); 3. Walk profiles: Extract entries from Pτ for 2 ≤ τ ≤ τc related to the focal link.
We emphasize that we do not use attention to compute per-node linear combinations of features like Veličković et al. (2017) (which is analogous to Vaswani et al. (2017)), but rather interpret the attention coefficients 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 a GNN which is trained jointly with WalkPool.
3.1 Sampling the enclosing subgraphs
2
34
1
1 2 1 1 4 1 1 3 1
1 3 2
sons beyond diminishing returns: a large k greatly increases memory and compute demands. The size of a 2-hop neighborhood is graph-dependent, but for the highly-connected E.coli and PB datasets we already need to enforce a maximum number of nodes per hop to fit the subgraphs in memory.
Let d(x, y) be the shortest-path distance between nodes x and y. The k-hop enclosing subgraph Gk{i,j} for {i, j} is defined as the subgraph induced from G o by the set of nodes
Vk{i,j} = {x ∈ V : d(x, i) ≤ k or d(x, j) ≤ k}.
Then Gk{i,j} = (V k {i,j}, E k {i,j}), where {x, y} ∈ E k i,j when x, y ∈ Vk{i,j} and {x, y} ∈ E o. We omit the dependence on k and write G{i,j} = (V{i,j}, E{i,j}) for simplicity.
We fix an arbitrary order of the nodes in V{i,j} and denote the corresponding adjacency matrix by A{i,j}. Without loss of generality, we assume that under the chosen order of nodes, the nodes i and j are labeled as 1 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 Z{i,j}, with values inherited from the full graph (the rows of Z{i,j} are a subset of rows of Z).
For the candidate set of links Ec, we construct a set of enclosing subgraphs Sc = {G{i,j} : {i, j} ∈ Ec}, thus transforming the link prediction problem into classifying these k-hop enclosing subgraphs. For training, we sample a set of known true and false edges Et and construct its corresponding enclosing subgraph set St = {Gi,j : (i, j) ∈ Et}.

heading: 3.2 Random-walk profile
text: The next step is to classify the sampled subgraphs from their adjacency relations A{i,j} and node representations Z{i,j}. Inspired by the walk-based heuristics, we employ random walks to infer higher-order topological information. Namely, for a subgraph (G = (V, E),Z) (either in Sc or St) we encode the node representations Z 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 yield a profile of the focal link.
We first encode two-node correlations as effective edge weights,
ωx,y = Qθ(zx) TKθ(zy) /√ F ′′, (1)
for all {x, y} ∈ E , where Qθ : RF ′ → RF ′′ and Kθ : RF ′ → RF ′′ are two multilayer perceptrons (MLPs) and F ′′ is the output dimension of the MLPs. In order to include higherorder topological information, we compute the random-walk transition matrix P = (px,y) from the two-body correlations. We set
px,y = [ softmax ( (ωx,z)z∈N (x) )] y := exp(ωx,y) / ∑ z∈N (x) exp(ωx,z) (2)
for {x, y} ∈ E and px,y = 0 otherwise, with N (x) the set of neighbors of x in the enclosing subgraph. The encoding (2) is analogous to graph attention coefficients (Veličković 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 τ -th power [Pτ ]ij are interpreted as probabilities that a random walker goes from i to j in τ hops. These probabilities thus concentrate the topological and node attributes relevant for the focal link into the form of random-walks:
• Topology is included indirectly through the GNN-extracted node features Z, and directly by the fact that P encodes zero probabilities for non-neighbors 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 Qθ, Kθ.
As a result, WalkPool2 can be interpreted as trainable heuristics.
From the matrix P and its powers, we now read a list of features to be used in graph classification. We compute node-level, link-level, and graph-level features:
nodeτ = [Pτ ]1,1 + [P τ ]2,2, link τ = [Pτ ]1,2 + [P τ ]2,1, graph τ = tr[Pτ ]. (3)
Computation of all features is illustrated for τ = 2 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 is invariant to the ordering of i and j, consistent with the fact that we study undirected graphs. Link-level features linkτ give the symmetrized probability that a length-τ random walk goes from node 1 to 2. Finally, graph-level features graphτ are related to the total probability of length-τ loops. All features depend on the node representation Z; we omit this dependence for simplicity. The use of P
2The output of pooling (e.g., in a CNN) is a often an object of the same type (e.g., a downsampled image). The last layer of a CNN or GNN involves global average pooling which is a graph summarization mechanism similarly as WalkPool, hence the name.
in WalkPool is different from how graph matrices (e.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; WalkPool encodes graph signals into effective edge weights and directly extracts topological information from the entries of Pτ .

heading: 3.3 Perturbation extraction
text: A true link is by definition always present in its enclosing subgraph while a negative link is always absent. This leads to overfitting if we directly compute the features (3) on the enclosing subgraphs since the presence or absence of the link has a strong effect on walk profiles. For a normalized comparison of true and false links, we adopt a perturbation approach. Given an enclosing subgraph G = (V, E), we define its variants G+ = (V, E∪{1, 2}) (resp. G− = (V, E\{1, 2})) with the candidate link forced to be present (resp. absent). We denote the node-level features (3) computed on G+ and G− by nodeτ,+ 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 introduction: the information related to the presence of {i, j} is obfuscated by the summation over the entire subgraph (by taking the trace).
SEAL attempts to remedy a similar issue for average (as opposed to tr(Pτ )) pooling by labeling nodes by distance from the link. Here we propose a principled alternative. Since transition probabilities are normalized and have clear topological meaning, we can suppress irrelevant information by measuring the perturbation of graph-level features, ∆graphτ = graphτ,+ − graphτ,−. This “background subtraction” induces a data-driven soft limit on the longest loop length so that, by design, ∆graphτ concentrates around the focal link. In Appendix E, we demonstrate locality of WalkPool. Compared to node labeling, the perturbation approach does not manually assign a 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 G ∈ {G{i,j} : {i, j} ∈ Ec}, we read a list of features as
WPθ(G,Z) = [ ω1,2, ( nodeτ,+, nodeτ,−, linkτ,+, linkτ,−,∆graphτ )τc τ=2 ] , (4)
where τc is the cutoff of the walk length and we treat it as a hyperparameter. The features are finally fed into a classifier; we use an MLP Πθ with a sigmoid activation in the output. The ablation study in Table 5 (Appendix B) shows that all the computed features contribute relevant predictive information. Walk profile computation is summarized in Figure 2.

heading: 3.4 Training the model
text: The described model contains trainable parameters θ which are fitted on the given observed set Et of positive and negative training links and their enclosing subgraphs. We train WalkPool with MSE loss (see Appendix G for a discussion of the loss),
θ∗ = arg min θ
1 |Et| ∑
{i,j}∈Et
( y{i,j} −Πθ ( WPθ(G{i,j},Z{i,j} ))2 where y{i,j} = 1 if {i, j} ∈ Eo and 0 otherwise is the label indicating whether the link {i, j} is true or false. The fitted model is then deployed on the candidate links Ec; the predicted label for {x, y} ∈ Ec is simply ŷ{x,y} = Πθ∗(WPθ∗(G{x,y}),Z{x,y}).

heading: 4 Performance of WalkPool on benchmark datasets
text: 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 + FP).

heading: 4.1 Datasets
text: 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, if we assume that network formation is driven by the similarity (or dissimilarity) of node attributes, then a homophilic graph will favor triangles while a heterophilic graph will inhibit triangles. Following this intuition, we adopt the average clustering coefficient ACC (Watts & Strogatz, 1998) as a 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 (Newman, 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 (viii) E.coli (Zhang et al., 2018). Properties and statistics of the datasets, including number of nodes and edges, edge density and ACC can be found in Table 4 of Appendix A.
In graphs with a very low average clustering coefficient like Power and Router (ACC = 0.080 and 0.012, respectively, see Appendix A), topology-based heuristics usually perform poorly (Lü & Zhou, 2011) (cf. Table 2), since heuristics often adopt the homophily assumption and rely on triangles. We show that by learning the topological organizing patterns, WalkPool performs well even for these graphs.
For a fair comparison, we use the exact same training and testing sets (including positive and negative links) as SEAL 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) Citeseer (Giles et al., 1998), (iii) Pubmed (Namata et al., 2012), (iv) Chameleon (Rozemberczki et al., 2021), (v) Cornell (Craven et al., 1998), (vi) Texas (Craven et al., 1998), and (vii) Wisconsin (Craven et al., 1998). The properties and statistics of the datasets can be found in Table 4 of Appendix A; further details are provided in 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, we compare WalkPool with eight other methods. We consider three walk-based heuristics: AA, Katz and PR; two subgraphbased heuristic learning methods: Weisfeiler–Lehman graph kernel (WLK) (Shervashidze et al., 2011) and WLNM (Zhang & Chen, 2017); and latent feature methods: node2vec (N2V) (Grover & Leskovec, 2016), spectral clustering (SPC) (Tang & Liu, 2011), matrix factorization (MF) (Koren et al., 2009) and LINE (Tang et al., 2015). We additionally consider the GNN-based SEAL, which is the previous state-of-the-art.
For datasets with node attributes, we combine WalkPool with three unsupervised GNN-based models: the VGAE, adversarially regularized variational graph autoencoder (ARGVA) (Pan et al., 2018) and Graph InfoClust (GIC) (Mavromatis & Karypis, 2020).

heading: 4.3 Implementation details
text: In the absence of node attributes, we initialize the node representation Z(0) as an N ×F (0) all-ones matrix, with F (0) = 32. We generate node representations by a two-layered Graph
Convolutional Network (GCN) (Kipf & Welling, 2016a): Z(k) = GCN ( Z(k−1) ) , k ∈ {1, 2}, where Z(0) = X. We then concatenate the outputs as Z = [Z(0) | Z(1) | Z(2)] to obtain the final node representation used to compute WP(G,Z) and classify. While a node labeling scheme like the one in SEAL is not needed for the strong perfomance of WalkPool, we 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 to generate an initial node representation Z(0). This is because standard 2-layer GCNs are not 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(0) | Z(1) | Z(2)] 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.e., Z = Z(2). The hyperparameters of the model are explained in detail in Appendix C. The runtime of WalkPool can be found in Appendix H.

heading: 4.4 Results
text: 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 1. In these regular graphs the topological organizing rules are known explicitly. It is therefore clear that a common-neighbor-based heuristic (such as CN or AA) should fail for 2D-grid 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 in all other experiments. For Triangle lattice and 2D-grid, WalkPool achieves a near-100% AUC. Small errors are due to 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 ten 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.
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 significance 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 is stable on independent data splits (unlike competing learning methods). Among all methods, WalkPool with DL performs the best; the second-best method slightly below is WalkPool without DL. In other words, although DRNL slightly improves WalkPool, 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-art performance on all. Remarkably, on Power and Router where topology-based heuristics such as AA and Katz fail, WalkPool shows strong performance (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.
Datasets with node attributes We apply WalkPool to extract higher-order information 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 3; for AP see Appendix D. In Table 3, we show the results of unsupervised models with and without WalkPool. For all the unsupervised models and datasets, WalkPool improves the prediction accuracy. On the Pubmed dataset where the relative importance of topology over features is greater, WalkPool brings about the most significant gains.
While traditional heuristics cannot include node attributes, 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 WalkPool yields the highest accuracy for all three datasets. Importance of initial node representations is plain since WalkPool is not designed to uncover structure in node attributes. Nonetheless, WalkPool greatly improves performance of unsupervised GNN on the downstream link prediction task.

heading: 5 Discussion
text: The topology of a graph plays a 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 coefficients as transition probabilities of a 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-theart performance on a broad range of benchmarks with diverse structural characteristics. Remarkably, WalkPool achieves this with the same set of hyperparameters on all tasks regardless of the network type and generating mechanism.

heading: Appendix A. Benchmark datasets description
text: Brief description of the benchmark datasets is as follows. For the datasets without node attributes, we have considered:
• USAir (Batagelj & Mrvar, 2006): a 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., 2005): a graph of hyperlinks between weblogs on US politics with 1222 nodes and 16714 edges; ACC = 0.320.
• Yeast (Von Mering et al., 2002): a protein-protein interaction graph in 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 = 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, we consider three citation graphs with publications described by binary vectors indicating the absence/presence of the corresponding dictionary word:
• Cora (McCallum et al., 2000): a citation graph with 2708 scientific publications and 5278 links. The dictionary consists of 1433 unique words; ACC = 0.241.
• Citeseer (Giles et 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., 2012): the dataset consists of 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 represent 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.
• Cornell (Craven et al., 1998): a webpage graph with 183 nodes and 277 edges, and the node attribute has dimension 1703; ACC = 0.167.
• Texas (Craven et al., 1998): a webpage graph with 183 nodes and 279 edges, and the node attribute has dimension 1703; ACC = 0.198.
• Wisconsin (Craven et al., 1998): a 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 4.

heading: Appendix B. Ablation study
text: We conduct ablation studies of WalkPool by excluding or including only each of the node-, link- and graph-level features in (4). We used short notations {nodeτ} ≡ {nodeτ,+, nodeτ,− :
τ ∈ {2, · · · , τc}}, and similarly for {linkτ}, {∆graphτ}. The ablation results for the C.ele dataset is shown in the In Table. 5.

heading: Appendix C. Hyperparamters
text: 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. we 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 testing and 5% for validation. The observed graph is built only based on the training edges. Some studies 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 is connected.
For sampling the enclosing subgraphs, we set the number of hops as 2 except 3 for the Power dataset. 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 τc = 7 for the cutoff of walk length in all experiments. When τc becomes large, the transition probabilities converges to a constant, as the random walk reaches stationary. Therefore, a larger value of τ introduces little further information. From experiments, we find that introducing a larger τc 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 as the activation function for the hidden layers, and sigmoid function for the output layer.

heading: Appendix D. Results measured by AP and statistical significance of results
text: The prediction accuracy measured by AP for datasets with and without node attributes are shown in Table 8 and Table 9, respectively. From the tables, WalkPool still performs best with the AP metric.
To verified the statistical significance of the results, we 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 corresponding 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
the second best is 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 it 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 as SEAL for a fair comparisons.

heading: Appendix E. Locality of graph-level features
text: Let G = (V, E) be an enclosing subgraph, and {1, 2} be the candidate link. We denote the random walk transition matrices on G+ and G− as P and Q, respectively. For any node x, y ∈ V, let d(x, y) be the shortest path distance on the graph. We define the distance from x to the candidate link to be d̄(x) = min{d(x, 1), d(x, 2)}. We have the following result. Proposition 1. Let Vτ = {x ∈ V, d̄(x) > τ}, then [Pτ ]x,y = [Qτ ]x,y for all x, y ∈ Vτ .
Proof. We prove the result via induction. When τ = 1, after the node-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., V1 = {x ∈ V, d̄(x) > 1}. Now suppose the claim holds for τ . Let I = {x ∈ V, d̄(x) ≤ τ}, let ∂I be the set of nodes that are adjacency to but not in I, and let Ic 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
P = ( PI,I PI,∂I 0 P∂I,I P∂I,∂I P∂I,Ic
0 PIc,∂I PIc,Ic
) , Pτ = PτI,I PτI,∂I PτI,IcPτ∂I,I Pτ∂I,∂I Pτ∂I,Ic PτIc,I P τ Ic,∂I P τ Ic,Ic ,  (5) where PI,I is the block matrix confined to I and other blocks are defined similarly. By definition, PI,Ic = 0 and PIc,I = 0. Multiplication of the block matrices gives
Pτ+1Ic,Ic = PIc,∂IP τ ∂I,Ic + PIc,IcP τ Ic,Ic . (6)
We can do a similar computation to obtain Qτ+1Ic,Ic , with all P replaced by Q in the above equation. By assumption, we have
PIc∂I = QIc∂I P τ ∂I,Ic = Q τ ∂I,Ic PIc,Ic = QIc,Ic , P τ Ic,Ic = Q τ Ic,Ic , (7)
as ∂I, Ic ∈ Vτ , therefore we obtain Pτ+1Ic,Ic = Q τ+1 Ic,Ic . As Ic = Vτ+1, the claim follows by induction.
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 11, respectively.

heading: Appendix G. MSE loss and BCE loss
text: As link prediction is a classification problem, we usually adopt a classification loss such as binary cross-entropy (BCE). We opted for MSE based on the following heuristic. In node classification, categories are usually clearly defined. For example, in a citation graph, the category of a paper is near-definite. Meanwhile, the topology of real graphs is often fuzzy and evolving. In a co-authorship graph, some authors who have not published together today
may have submitted a paper that will come out tomorrow. We therefore expect a less peaky distribution of link probabilities than node classes, and we choose a loss that minimizes the miscalibration of the model. In this context where we want to predict probabilities as accurately as possible, the MSE loss is known as 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 attributes (the last line of Table 2), accuracies measured by AUC when using MSE/BCE loss are: 98.68/98.68; 98.95/98.85; 95.60/95.69; 98.37/98.37; 92.79/92.83; 92.56/92.58; 97.27/97.35; 98.58/98.67.

heading: Appendix H. Runtime of WalkPool
text: 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 enclosing subgraphs—this is true for WalkPool and any other subgraph-based link prediction algorithm.

Review summaries:
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.

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.

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

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.