Graph Neural Networks for Link Prediction with Subgraph Sketching
Authors: Benjamin Paul Chamberlain
Sergey Shirobokov
Emanuele Rossi
Fabrizio Frasca
Thomas Markovich
Nils Yannick Hammerla
Michael M. Bronstein
Max Hansmire
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Graph Neural Networks
Link Prediction
Data Sketching

Abstract: Many Graph Neural Networks (GNNs) perform poorly compared to simple heuristics on Link Prediction (LP) tasks. This is due to limitations in expressive power such as the inability to count triangles (the backbone of most LP heuristics) and because they can not distinguish automorphic nodes (those having identical structural roles). Both expressiveness issues can be alleviated by learning link (rather than node) representations and incorporating structural features such as triangle counts. Since explicit link representations are often prohibitively expensive, recent works resorted to subgraph-based methods, which have achieved state-of-the-art performance for LP, but suffer from poor efficiency due to high levels of redundancy between subgraphs. We analyze the components of subgraph GNN (SGNN) methods for link prediction. Based on our analysis, we propose a novel full-graph GNN called ELPH (Efficient Link Prediction with Hashing) that passes subgraph sketches as messages to approximate the key components of SGNNs without explicit subgraph construction. ELPH is provably more expressive than Message Passing GNNs (MPNNs).  It outperforms existing SGNN models on many standard LP benchmarks while being orders of magnitude faster. However, it shares the common GNN limitation that it is only efficient when the dataset fits in GPU memory. Accordingly, we develop a highly scalable model, called BUDDY, which uses feature precomputation to circumvent this limitation without sacrificing predictive performance. Our experiments show that BUDDY also outperforms SGNNs on standard LP benchmarks while being highly scalable and faster than ELPH.

Published as a conference paper at ICLR 2023
GRAPH NEURAL NETWORKS FOR LINK PREDICTION WITH SUBGRAPH SKETCHING
Benjamin P. Chamberlain +
Sergey Shirobokov + ShareChat Al
Emanuele Rossi Imperial College London
Charm Therapeutics
Fabrizio Frasca Imperial College London
Thomas Markovich
Nils Hammerla
Michael M. Bronstein t University of Oxford
Twitter Inc.
Twitter Inc.
Max Hansmire
Twitter Inc.
ABSTRACT
Many Graph Neural Networks (GNNs) perform poorly compared to simple heuris- ties on Link Prediction (LP) tasks. This due to limitations in expressive power such as the inability to count triangles (the backbone of most LP heuristics) and because they can not distinguish automorphic nodes (those having identical struc- tural roles). Both expressiveness issues can be alleviated by learning link (rather than node) representations and incorporating structural features such as triangle counts. Since explicit link representations are often prohibitively expensive, recent works resorted to subgraph-base
methods, which have achieved state-of-the-art performance for LP, but suffer from poor efficiency due to high levels of redun- dancy between subgraphs. We analyze the components of subgraph GNN (SGNN) methods for link prediction. Based on analysis, propose novel full- aill-graph GNN called ELPHH (Efficient Link Prediction with Hashing) that passes subgraph sketches messages to approximate the key components of SGNNs without plicit subgraph construction. ELPH is provably more expressive than Message Passing GNNs (MPNNs). outperforms existing SGNN models on many standard LP benchmarks while being orders of magnitude faster. However, it shares the common GNN limitation that it only efficient when the dataset fits in GPU mem- ory. Accordingly, we develop a highly scalable model, called BUDDY, which uses feature precomputation to circumvent this limitation without sacrificing predictive performance. Our experiments show that BUDDY also outperforms SGNNs on standard LP benchmarks while being highly scalable and faster than ELPH.
INTRODUCTION
Link Prediction (LP) is an important problem in graph ML with many industrial applications. For example, recommender systems can be formulated as LP; link prediction is also a key process in drug discovery and knowledge graph construction. There are three main classes of LP methods: (i) heuristics (See Appendix C.I that estimate the distance between two nodes (c.g. personalized page rank (PPR) (Page al. 1999 or graph distance (Zhou et al., 2009)) the similarity of their neighborhoods (e.g Common Neighbors (CN), Adamic-Adar (AA) (Adamic & Adar 2003). or
Resource Allocation (RA) (Zhou et al., 2009)); (ii) unsupervised node embeddings or factorization methods, which encompass the majority of production recommendation systems (Koren et al. 2009)
Chamberlain et al. 2020); and, recently, (iii) Graph Neural Networks, particular of the M Message-
Passing type (MPNNs) Gilmer al. 2017 Kipf & Welling 2017 Hamilton et al. 2017 GNNs excel in graph- and lode-level tasks, but often fail to outperform node embeddings or heuristics on common I. benchmarks such the Open Graph Benchmark (OGB) (Hu et al. 2020
There two related reasons why MPNNs tend to be poor link predictors. Firstly, due to the equivalence of message passing to the Weisfeiler-Leman (WL) graph isomorphism test (Xu ct al. 2019: Morris et al. 2019), standard MPNNs provably incapable of counting trian-
* Equual contribution. Work done while at Twitter Inc. *ben jami n. chamber l n&gma 1 com. 'GNNs are broader category than MPNNs. Since the majority of GNNs used in practice are of the message passing type, we will use the terms synonymously.

---

Published as a conference paper at ICLR 2023
gles (Chen al. 2020) and consequently of counting Common Neighbors or computing one- hop or two-hop LP heuristics such as AA or RA. Secondly, GNN-based LP approaches com- structural node representations (obtained by message passing the graph) and a readout function that maps from two node representations to a link prohability. How- ever, generating link representations as function of equívariant node representations encoun- lers the problem that all nodes u in the same orbit induced by the graph automorphism group have equal representations. Therefore, the link probability p(u, v) the same for all in the orbit independent of e.g. the graph distance d(u, 2) (Figure I]- (Srinivasan & Ribeiro 2019). This is result of GNN's built-in permutation equivariance, which produces equal representations for any nodes whose enclosing subgraphs (corresponding to the receptive field of the GNN) are isomorphic We refer to this phenomenon as the automorphic node problem and define automorphic nodes (denoted u = v) to be those nodes that are indistinguishable by means of given k-layer GNN. On the other hand, transductive node embedding methods such as TransE (Bordes et al., (013)) and DeepWalk (Per- ozzi et al. 2014), or matrix factorization (Koren et al. (2099) do not suffer from this problem as the embeddings not permutation equivariant.
bine cetmmntttiion-quvvaittii
Figure 1: Nodes 2 and 4 are in the same orbit induced by the graph's 's automorphism group. As a result, a conventional GNN will assign the same probability to links (1,2) and (1,4).
Several methods have been proposed to improve GNN expressivity for LP. Most simply, adding unique node IDs immediately makes all structural node representations distinguishable, but at the expense of generalization (Abboud et al. 2021) and training convergence (Sato al., 202I). Substructure counts may act as permutation- cquivariant approximately unique identifiers (Bouritsas et al. 2022), but they require a precomputation step which may be computationally intractable in the worst case. More successfully, family of structural features, sometimes referred to as labeling tricks, have recently been proposed that solve the automorphic node problem while still being equivariant and having good generalization (Li et al. 2020; Zhang et al., 202 1, You et al. 2021). However, adding structural features amounts to computing structural node representations that are conditioned on an edge and so can no longer be efficiently computed in parallel. For the purpose of tractability,
oftth---rt-- methods for LP restrict computation to subgraphs enclosing a link, transforming link prediction into binary subgraph classification (Zhang al. 2021 Zhang & Chen 2018 Yin et al. 2022). Subgraph GNNs (SGNN) are inspired by the strong performance of LP heuristics compared to more sophisticated techniques and are motivated an attempt to learn data-driven LP heuristies.
Despite impressive performance benchmark datasets, SGNNs suffer from some serious limitations: (i) Constructing the subgraphs is expensive; (ii) Subgraphs are irregular and so batching them is inefficient on GPUs (ii); Each step of inference is almost as expensive as each training step because subgraphs must be constructed for every test link. These drawbacks preclude many applications, where scalability or efficient inference are required.
Main contributions. (i) We analyze the relative contributions of SGNN components and reveal which properties of the subgraphs are salient to the LP problem. (ii) Based on our analysis, we develop an MPNN (ELPH) that passes subgraph sketches as messages. The sketches allow the most important qualities of the subgraphs to be summarized in the nodes. The resulting model removes the need for explicit subgraph construction and is a full-graph MPNN with the similar complexity to GCN. (iii) We prove that ELPH is strictly more expressive than MPNNs for LP and that it solves the automorphic node problem. (iv) As full- aill-graph GNNs suffer from scalability issues when the data exceeds GPU memory. we develop BUDDY, a highly scalable model that precomputes sketches and node features. (v) We provide an open source Pytorch library for (sub)graph sketching that generates data sketches via message passing on the GPU. Experimental evaluation shows that our methods compares favorably to state-of-the-att both in terms of accuracy and speed.
2 PRELIMINARIES
Notation.
Let G (V, be undirected graph comprising the set of nodes (vertices) V and links (edges) E. We denote by d(u,v) v) the geodesic distance (shortest walk length) between nodes
Mooe precisely, Wl-equvivl, which is necessary but insufficient condition for isomorphism.
2

---

Published as a conference paper at ICLR 2023
and v. Let S (V's C Es C) be a node-induced subgraph of G satisfying vu,v) E Es iff (u, E E for any u, 8 E Vg. We denote by S = (Vue, Ew)) a k-hop subgraph enclosing the link (u, v), where Van is the union of the k-hop neighbors of u and and Env is the union of the links that can be reached by a k-hop walk originating at u and e (for simplicity, where possible, we omit k). Similarly, S is the k-hop subgraph enclosing node u. The given features of nodes Van denoted by Xuv and the derived structure features by Zue. The probability of link (u, v) is denoted by p(u, v). When nodes u and e have isomorphic enclosing subgraphs (i.e., S. = Sy), we write u 2 v.
Sketches for Intersection Estimation. We use two sketching techniques, HyperLogLog (Fljoolet et al. 2007; Heule et al. 2013) and MinHashing (Broder 1997). Given sets A and B, HyperLogl efficiently estimates the cardinality of the union A BJ and MinHashing estimates the Jaccard index B), I AnAB//AA /I/ B). We combine these approaches estimate the intersection of node sets produced by graph traversals (Pascoe) (013)) These techniques represent sets as sketches, where the sketches are much smaller than the sets they represent. Each technique has a parameter p controlling the trade-off between the accuracy and computational cost. Running times for merging two sets, adding an element to a set, and extracting estimates only depend on p. but they are constant with respect to the size of the set. Importantly, the sketches of the union of sets are given by permutation- invariant operations (element wise min for minhash and element wise max for hyperloglog). More details are provided in Appendix C
Graph Neural Networks for Link Prediction. Message-passingg GNNs (MPNNs) are parametric functions of the form Y = GNN(X), where X and Y are matrix representations (of size x d and n x d', where n is the number of nodes and d, d' are the input and output dimensions, respectively) of input and output node features. Permutation equivariance implies that IIGNN(X) = GNN(II)) for any n x n node permutation matrix II. This is achieved in GNNs by applying a local permutation- invariant aggregation function D (typically sum, mean, max) to the neighbor features of every node ( ("message passing',, ) resulting in a node-wise update of the form
Yu = 7 (xu: (u)) (X..
where , are learnable functions. MPNNs are upperbounded in their discriminative power by the Weisfeiler-Leman isomorphism test (WL) (Weisfeiler & Leman 1968), a procedure iteratively refining the representation of a node by hashing its star-shaped neighborhood. As a consequence, since WL always identically represents automorphic nodes (u _ v), any MPNN would do the same: yu Ye- Given the node representations Y computed by a GNN, link probabilities can then be computed as puu, v) = (.)...Y), where R is a learnable readout function with the property that R(y., v.) = R(y u. v.) for any u ~ w. This node automorphism problem is detrimental for LP as p(u, v) = p(u, w) if u = w even when d(u, v) >> d(u, wr). As an example, F = 4, therefore p(1, 2) p(1, 4) while d(1,2)
2 < d(1, 4) = 3. As result, GNN may suggest to link totally unrelated nodes (u may even be in a separate connected component to u and w, but still have equal probability of connecting to u (Srinivasan & Ribeiro 2019
Subgraph GNNs (SGNN). (Zhang et al., 2021 Zhang & Chen 2018 Yin et al. 2022) convert LP
into binary graph classification. For a pair of nodes u, v and the enclosing subgraph Swe. SGNNS produce node representations Y.. and one desires R(Y ((Ya.))= = if (u, v) E E and zero otherwise. In order to resolve the automorphic node problem, node features are augmented with structural features (Bouritsas et al.) 2022) that improve the ability of networks to count substructures (Chen et al.) 2020). SGNNs were originally motivated by the strong performance of heuristics on benchmark datasets and attempted to learn generalized heuristics. When the graph is large it is not tractable to learn heuristics over the full graph, but global heuristics can be well approximated from subgraphs that augmented with structural features with an approximation error that decays exponentially with the number of hops taken construct the subgraph (Zhang & Chen 2018).
3 ANALYZING SUBGRAPH METHODS FOR LINK PREDICTION
SGNNs can be decomposed into the following steps: (i) subgraph extraction around every pair of nodes for which one desires to perform LP; (ii) augmentation of the subgraph nodes with structure features; (iii) feature propagation over the subgraphs using a GNN, and (iv) learning a graph-level readout function predict the link. Steps (ii)-(iv) rely on the existence of set of subgraphs (i),
3

---

Published as a conference paper at ICLR 2023
HR@110 by structure feature type
HR@ by readout function
85
81:21
84.63
85.53
81.71,
83.89
81.71,
03
80
80
6.6
07
75
75
75
HR81000
HK01000
70
786. 19
67.00
65-
164.74
Cara
55
55
53.02
Pubmed
Citeseer
50
47
50
45
Nore
DRNL
mean
Sum
edge
(a)
(b)
Figure 2: (a) Structure features in SGNNs. (b) LP readout function over the output of all nodes in Suo (sum or mean) or just and (edge).
which is either constructed on the fly or preprocessing step. In the remainder of this section we discuss the inherent complexity of each of these steps and perform ablation studies with the goal of understanding the relative importance of each.
Structure Features Structure features address limi- tations in GNN expressivity stemming from the inher- inability of message passing to distinguish auto- morphic nodes. In SGNNs, permutation equivarrant distances d((u a) and d(e, i) Vi E Vue are used. The three most well known are Zero-One (ZO) encod- ing (You et al. [2211) Double Radius Node Labeling (DRNL) (Zhang & Chen 2018) and Distance Encod- ing (DE) (Li 20000). To solve the automorphic node problem, all that is required is to distinguish and from Vuv \ {u, v). which ZO achieves with binary node labels. DRNL has Su = 2g 1 and
Feature importance by
1.0
Cora
Feature importance
0.8
Citeseer
Pubmed
0.6
0.4
0.2
0.0
(r.1)
(r.2)
(r.3)
(r.4)
(t.5)
Figure 3: The importance of DRNL structure features. Importance is based on the weights in a logistic regression model using DRNL features without node features.
2j = =(d(u,) j), ()) > 1, where f N2 - bijective map. Distance Encoding (DE) gen- eralizes DRNL; each node is encoded with a tuple 2, (d(u, j), d(v.j)) (See Figure Both of these schemes therefore include a unique label for triangles common neighbors (See Appendix C.4 for more details on labeling schemes). The relative performance of ZO, DRNL, DE and structure features is shown in Figure 2a The use of structure features greatly improves performance and DRNL. and DE slightly outperform ZO, with more pronounced outperformance for the larger Pubmed dataset. It is important to note that structure features are conditioned on edges and so can not be easily paralellized in the same way that node features usually are in GNNs and must be calculated for each link at both training and inference time. In particular DRNL requires two full traversals of each subgraph, which for regular graphs is O(deg") ), but for complex networks becomes ((E)).
In Figure we investigate the relative importance of DRNL structure features. Feature importance is measured using the weights in logistic regression link prediction model with only structure feature counts as inputs. We then sum up feature importances corresponding to different max distance and normalize the total sum one. The Figure indicates that most of the predictive performance is concentrated in low distances.
Propagation / GNN In SGNNs, structure features are usually embedded into a continuous space, concatenated to any node features and propagated over subgraphs. While this procedure is necessary for ZO encodings. it is less clear why labels that precisely encode distances and are directly com- parable as distances should be embedded in this way. Instead passing embedded DE or DRNL structure features through GNN, we fixed the number of DE features by setting the max distance to three and trained an MLP directly on the counts of these nine features (e.g. (1,1): 3, (1,2): 1, etc.). Figure Faitee/asshhn showshwws that doing so, while leaving ceteris paribus (node features still propagated over the subgraph) actually improves performance in two out three datasets. We also investigated if any features require SGNN propagation by passing both raw node features and structure feature counts
4

---

Published as a conference paper at ICLR 2023
HR@ 1e0e100 by structure feature propagation
HR@100 by node feature propagation
95
90
89.39
89.39
89.84
Cora
Citeseer
85
93,89
85.19
81
81.19
83.38,
Pubmed
HR
HR@100
80
80
75
75,54
72,21
73.374.66
74.66
71.3
72/21
70
65,79
GNN
MLP
GNN
preprop
no prop
(a) Propagating structure features
(b) Propagating node features.
Figure 4: Examining the extent to which an SGNN is needed to propagate features. (a) An MLP on structure feature counts outperforms SGNN propagation in two of three datasets. (b) An MLP on structure feature counts and raw node features performs poorly (no prop), but performance can be recovered if node features propagated over the graph in preprocessing (preprop).
through MLP. The results in the right columns of Figure 4b indicate that this reduces performance severely, but by pre-propagating the features as x = [u)] Eie (middle columns) is possible to almost recover the performance of propagation with the SGNN (left columns).
Readout Pooling Function Given SGNN node representations Y on the subgraph, readout function R(Sue. Y Yuu) maps rep- resentations link probabilities. For graph classification problems, this is most commonly done by pooling node representations (graph pooling) typically with a mean or sum operation plus an MI.P For LP, alternative is edge pooling with y.)....). usually with the Hadamard product. A major advantage of edge pooling is that can be formulated subgraph free. Figure indiiccas that edge pooling produces better predictive performance than either mean or sum pooling across all nodes in Vuv-
1.2
2,1
12
1.1
Figure 5: The DE node label- ing scheme for link (u, v)
Analysis Summary The main results of Section are that (i) The inclusion of structure features leads to very large improvements across all datasets (Figure 2 (īi) The processing of these features, by embedding them and propagating them with an SGNN sub-optimal both terms of efficiency and performance (Figure 4ab; (iii) Most of the importance of the structure features is located in the lowest distances (Figure 3); and (iv) edge level readout functions greatly outperform mean or sum pooling over subgraphs (Figure 2b). If, one hand, subgraphs are employed
tractable
alternative to the full graph for each training edge, on the other, generating them remains an expensive operation (O(deg* #) time complexity for regular graphs and O(EE) for complex networks with power law degree distributions P see Appendix C.2 Within this context, our analysis shows that the information necessary to compute structure features for an edge can be encoded in the nodes, then it possible recover the predictive performance of SGNNs without the cost of generating a different subgraph for each edge. We build upon this observation to design an efficient yet expressive model in Section
LINK PREDICTION WITH SUBGRAPH SKETCHING
We now develop a full-graph GNN model that uses node-wise subgraph sketches to approximate structure features such as the counts of DE and DRNL labels, which our analysis indicated are sufficient to encompass the salient patterns governing the existence of link (Figure
4.1 STRUCTURE FEATURES COUNTS
Let Auv (dy, Auvidy de be the number of (dg, d.)) labels for the link (u, v), which is equivalent to the number of nodes at distances exactly d,, and dy from and respectively (See Figure 5). We compute
SSbggraphs can be pre-computed, but the subgraphs combined much larger than the original dataset, exceeding available memory for even moderately-sized datasets.
5

---

Published as a conference paper at ICLR 2023
A.. [3.
6
B..[i]
Au
Am!I,,
Aual2,
B,a12
Avx
Figure 6: Blue and red concentric circles indicate and 2-hop neighborhoods of and respectively, Structure features A and B measure the cardinalities of intersections of these neighborhoods.
Auv |d,, dyl for all du. du less than the receptive field k, which guarantees number of counts that do depend on the graph size and mitigates overfitting. To alleviate the loss of information coming 00 from fixed k; we also compute Bu [d] =k+ Aue [d, d..). counting the number of nodes at distance d from u and at distance > & from u. We compute [u][d] for all < d S k. O how A and B relate to the neighborhoods and 2k: counts for B (k for the source and k for the destination node), for a total of ki(k 2) count features. These counts can be computed efficiently without constructing the whole subgraph for each edge. Defining Na..d, d. (u, v) & No., (u) n No. (v), we have
two nodes. Overall, this results in k2 counts for A
Auc [da. d=] [Na..d. do (u, u)]
E ( w)
(2)
"Sdu.y du. (z:
B d [Na(u)] Bun
Auoli, [
(3)
where N&(u) are the d-hop neighbors of u (i.e. nodes at distance S d from 2).
Estimating Intersections and Cardinalities |Na,,d, (u, r)] and [Na(u)] can be efficiently ap- (d)
proximated with the sketching techniques introduced in section Let h! and m be the Hy- perLogLog and MinHash sketches of node u's d-hop neighborhood, obtained recursively from the initial node sketches h and m using the relations m!. mineeN(a) m
(d-1) and
h (d) (a) h (d-1), where min and max elementwise. We can approximate the in- tersection of neighborhood sets as
[N d, (u, v) - |Na,(u) n NNa (v)l=
(4)
(NN,, (u), (v)) ) [Na, (w) U Na.
(5)
H (d.., m (..))) card (max(h(de) (de) (.,,,,(()) h((d)))
(6)
where ((x,y) 1/n ΣJ 8m,,n is the Hamming similarity, card is the HyperLogLog cardinality estimation function (see Appendix C.3.I) and max is taken elementwise. MinHashing approximates the Jaceard similarity (J) between two sets and HyperLogLog approximates set cardinality. [Na(w)
be approximated as [Na(u)) (h(d)) (d)) The cost of this operation only depends additional parameters of HyperLogLog and MinHashing (outlined in more detail Section which allow for tradeoff between speed and accuracy, but is nevertheless independent of the graph size. Using this approximations obtain estimates Á and B of the structure features counts.
4.2 EFFICIENT LINK PREDICTION WITH HASIES (ELPH)
We present ELPH, novel MPNN for link prediction. common with other full-graph GNNs, employs feature propagation component with link-level readout function. However, by augmenting the messages with subgraph sketches, it achieves higher expressiveness for the same asymptotic complexity, ELPH's feature propagation fits the standard MPNN formalism GGimerr et al. 2017):
m!! min m!! (!-1)
(!)
max (1-1)
vEN(()
vEN(u)
( ur
= [Buvll] Anp (d 1. Amill, dol Vd,, d, < <1} (1-1)
(8)
(0) (0)
(x(1 (
x( ,.,
(9)

---

Published as a conference paper at ICLR 2023
where 6,7 y are learnable functions, 0 is local coimuutation-invariann aggregation function (typically sum, mean, or max), x!_ are the original node features, and m and h! are the MinHashing and HyperLogLog single node sketches respectively. Minhash and hyperloglog sketches of (u) are
computed by aggregating with min and max operators respectively the sketches of (1))(u) (Eq. 7)
These sketches can be used to compute the intersection estimations Bue and Aue up to the l-hop neighborhood, which are then used edge features (Eq. [). Intuitively, the role of the edge features is to modulate message transmission based on local graph structures, similarly to how attention is used modulate message transmission based on feature couplings. A link predictor is then applied to the final node representations of the form
p(u, v) vi
(k) (Bav [d], Auv (du, del Vd, du. de E [k])))
(10)
where [k] = = (.......k k). is a receptive field, eh is an MLP and @ is the clement- product. p(u, v) decouples the readout fünction from subgraph generation suggested in Figure 2b This approach moves computation from edgewise operations e.g. generating subgraphs, to nodewise operations (generating sketches) that encapsulate the most relevant subgraph information for LP. We have shown that (i) GNN propagation is either not needed (structure features) or can be preprocessed globally (given features) (ii) structure features can be generated from sketches instead of subgraphs (iii) an edge pooling readout function performs as well as a graph pooling readout. In combination these approaches circumvent the need to explicitly construct subgraphs. The resulting model efficiently combines node features and the graph structure without explicitly constructing subgraphs and is as efficient as GCN (Kipf & Welling 2017).
Expressive power of ELPH ELPH combines advantageous traits of both GNNs and subgraph methods, i.e. tractable computational complexity and access to pair-wise structural features including triangle counts (Appendix C.5). Furthermore, ELPH is more expressive than MPNNs:
Proposition 4.1. Let MELPH be the family of ELPH models per Equations 7 Jand 70 where
estimates are exact (ÁÁ B, B
MELPH does not suffer from the automorphic node problem.
While we rigorously define the automorphic node problem and prove the above in Section A.2, this result states that there exists non-automorphie links with automorphic nodes that an ELPH model is able to discriminate (thanks to structural features). Contrary to ELPHs, MPNNs are not able to distinguish any of these links; we build upon this consideration, as well as the observation that ELPH models subsume MPNNs, to obtain this additional result:
Theorem 4.2. Let MMPNN be the family of Message Passing Neural Networks (Equation 7 MELPH is strictly more powerful than MMPNN (MELPH C MMPNNN-
We prove this in Section A.2
Intuitively, the Theorem states that while all links separated by MPNNS are also separated by ELPH PHs, there also exist links separated by the latter family but not by the former.
SCALING ELPH WITH PREPROCESSING (BUDDY)
Similarly to other full-graph GNNs (e.g. GCN), ELPH is efficient when the dataset fits into GPU memory. When it does not, the graph must be batched into subgraphs. Batching is major challenge associated with scalable GNNs and invariably introduces high levels of redundancy across batches. Here we introduce a large scale version of ELPH, called BUDDY, which uses preprocessing to side-step the need to have the full dataset in GPU memory.
Preprocessing Figure 4bjindicates that fixed and learnable SGNN propagation give almost equiva- lent performance. Fixed propagation can be achieved by efficient sparse scatter operations and done only once in preprocessing. Sketches can also be precomputed in a similar way:
( = scatter caaeeermminnnMr (0 ,G), (O) = scatter scatter_max ( (1-1) G), x (1) = scatter scatter_mean (X (1-1) G)
where scatter (M) G), min m (1-1) and scatter max and scatter_ mean are defined
similarly, ( are the original node features, and (()) and ()) are the MinHashing and Hyper- LogLog single node sketches respectively. Similarly to (Rossi et al. 2020), concatenate features
diffused at different hops to obtain the input node features: Z = X x x()
Forr sufficiently large samples, this result be extended to approximate counts via unbiased estimators.
7

---

Published as a conference paper at ICLR 2023
Link Predictor We now have p(u, u) = - ((
(k) ② 2z.0), [Buoldd [d], Auo [du, do] :Vd, de E
[k]}]
where is an MLP and Aur and B.e are computed using M and H explained in Section 4.1 Doing so effectively converts a GNN into an MLP, removing the need to sample batches of subgraphs when the dataset overflows GPU memory (Rossi et al. 2020). Further improvements in efficiency are possible when multiple computations on the same edge sets are required. In this case, the edge features (Bwv(d) [4], Auol d can be precomputed and cached.
Time Complexity Denoting the complexity of hash operations as h, the node representation dimen- sion d and the number of edges E' = [8 the preprocessing complexity of BUDDY is OkEd EEh). The first term being node feature propagation and the second sketch propagation. Preprocessing for SEAL and NBFNet are (1). A link probability is computed by (i) extracting k(k + 2) k-hop structural features, which costs (k+hh and (ii) An MLP on structural and node features, which results in Okk2h + kdd) operations. Both are independent of the size of the graph. Since SGNNS construct subgraphs for each link they are OEE?) for complex networks (See Section C.2). Finally, the total complexity of NBFNet is OEEd Ndf) with amortized time for a single link prediction
of O(Ed/N + d (Zhu et al. 2021). However, this is only realized in situations where the link
probability p(u, j) is required Vj V. Time complexities are summarized in Table 1 and space
complexities in Appendix B.4
Expressiveness of BUDDY
Similarly to ELPH, BUDDY does not suffer from the automorphic node problem (see Proposition and its Proof in Appendix AA.2.. However, due to its non- non- parametric feature propagation, this class of models does not subsume MPNNs and we cannot exclude the presence of links separated by MPNNs, but not by BUDDY, Nevertheless, BUDDY empirically outperforms common MPNNs by large margins (see Section 7 while also being extremely scalable.
6 RELATED WORK
Table 1: Model time complexity. N and F are the number of nodes and edges respectively. We use d-dimensional node features, k hops for propagation and sketches of size h.
Subgraph methods for link predic- tion were introduced as the Weisfeiler Leman Neural Machine (WLNM) in (Zhang & Chen 2017). As an MLP is used to learn from subgraphs in- stead of a GNN their model is not permutation-eqquiviiin and uses hashing-based WL algorithm (Kerst- ing et al. 2014) generate node indices for the MLP. Note that 'hashing" here refers to injective neighbor aggregation functions, distinct from the data sketching methods employed in the current work. The MLP in WLNM was replaced by a GNN in the seminal SEAL (Zhang & Chen 2018). thus removing the need for hashing scheme. Additional methodological improvements were made in (Zhang et al. 202T Zhang & Li, 202T) and subgraph generation was improved in (Yin et al., 2022). Applications to recommender systems were addressed in (Zhang & Chen 2019) and random walks are used to represent subgraph topology in (Yin et al., 2022 Pan et al. 2022). The DRNL labeling scheme was introduced in SEAL and further labeling schemes are developed in (You et al. 2021 et al. 2020) and generalized with equivariant positional encodings (Wang et al., 2022). Neural Bellman- Ford Networks (Zhu al., 202T) takes a different approach. It is concerned with single source distances where each layer of the neural networks is equivalent to an iteration of the Bellman-Ford algorithm and can be regarded as using a partial labeling scheme. The same graph and augmentation can be shared among multiple destinations and so it is faster (amortized) than SGNNs. However, it suffers from poor space complexity and thus requires impractically high memory consumption. Nco-GNY (Yun et al. 2021)) directly learns a heuristic function using an edgewise and a nodewise neural network. #GNN (Wu et al., (02T) directly hashes node features, instead of graph structure, and is limited to node features that can be interpreted as set memberships. CFL. Zhao ct al. (2022) applies causal inference to LP. Another paradigm for LP uses self-supervised node embeddings combined with an (often) approximate distance metric. Amongst the best known models are TransE (Bordes et al. 2013), DistMult (Yang et al.) 2015), or complEx (Trouilonn et al. 2016). which have been shown to scale to large LP systems in e.g. (Lerer et al. 2019 El-Kishky et al. 2022
Complexity
SEAL
NBENet
BUDDY
Preprocessing Training (1 link)
O(1)
0(1) O(Ed O(Ed+Na Nd4)
OlkE(d h)) 0 + kd))
(
Inference
O(EdP)
O(Ed Nd
0 + kd)
Decoupling feature propagation and learning in GNNs was first implemented in SGC (Wu ct al. 2019) and then scalably in SIGN (Rossi et al. 2020).
8

---

Published as a conference paper at ICLR 2023
Table 2: Results link prediction benchmarks. The top three models are colored by First, Second, Third. Where possible, baseline results are taken directly from the OGB leaderboard.
Cora HR @ 100
Citeseer HR@ @ 100
Pubmed HR@ 100
Collab HR @ 50
PPA HR 100
Citation2 MRR
DDI
Metric
HR@20
CN
33 33.9210.46
29.79.1..90
23. 13.13
56.4410.00
27. 10.000
51.47 1..00
17.73.0..0
AA
1.38
35.19=1 33
27-38#0.11
64.35=0 00
32.45::0000
51.89=0.00
18.61=0
RA
41.0710.48
33.56:2..1 17
27.03
64.00 00
49.33=0000
51.98::0.00
27. 77.60:20
transE
1.640
60.19
10.97
29. 20.4011.11 1.15
22, 12..9910.49
76. 18.1..
6.6510.20
complEx
37.1612.76
42.72.1100 68
37 1.31
53, 03.9111..50
27 42.20.00
72 0..333
8. 8.68110.36
Must
41.38+2.40
47.65
40.32:20.8 80
51.00=0.54 54
28.61
66.9520040
11.01
GCN
66.7911.6
67.00 07.08.12.94
53.02.1139
47. 1:44
18.67
84. 14.7410.22
37.07 07.0
SAGE
55.0214.03
57.0113.74
39.66 19.6610.72
54.6611.12
16,55.12.40
82, 12.60
53.9011.74
Neo-GNN
80.42+1.31
84.67
73. 19
02.13=#0.3
49.13=0.00
87.26+0
63. =..67
SEAL
81.71+1880
83.89+2.15
75. 9..54
64.74=0.48
18.80#3.16
87.67+0.8 32
30.56=3.M6
NBFnet
71.6512.27
74.07
58.7311.99
0OM
0OM
0OM
4.0010.58
ELPH
87.72:2.13
03.44
72.99+1.48
66.3211.40
0OM
0OM
83. 2.119
BUDDY
88.00+0.44
92. 92.93=0.27
74.10#0.78
65.9440.68
49. 00.20
87.56+a.11
78.51=1.36
7 EXPERIMENTS
Datasets, Baselines and Experimental Setup We report results for the most widely used Planetoid citation networks Cora (McCallum et al. 2000), Citeseer (Sen et al. 2008) and Pubmed (Namata
al. 2012) and the OGB link prediction datasets (Hu al.] 2000)) We report results for: Three
heuristics that have been successfully used for LP, Adamic-Adar (AA) (Adamic & Adar 2003). Resource Allocation (RA) (Zhou et al.] 2009) and Common Neighbors (CN); two of the most
popular GNN architectures: Graph Convolutional Network (GCN) (Kipf & Welling] 2017) and
GraphSAGE (Hamilton al. 2017p: the ofate-of-the-art link prediction GNNs Neo-GNN (Yun et al.,
2021), SEAL (Zhang & Chen (0188) and NBFNet (Zhu et al., 2021). Additional details on datasets
and the experimental setup are included in Appendix B. I[nd the code is publid
Results Results are presented in Table 2 with metrics given in the first row. Either ELPH or BUDDY achieve the best performance in five of the seven datasets, with SEAL being the closest competitor. Being full-graph method, ELPH runs out of memory counterpart, BUDDY, performs extremely well on both. Despite ELPH being more general than BUDDY, there is no clear winner between the two in terms of performance, with ELPH outperforming BUDDY in three of the five datasets where we have results for both. Ablation studies for number of hops, sketching parameters and the importance of node and structure features in Appendix [D.2
the two largest datasets, while its scalable
Runtimes Wall times are shown in Table 3 We report numbers for both the static mode of SEAL (all sub- graphs are generated and labeled as preprocessing step), and the dynamic mode (subgraphs are generated on the fly). BUDDY is orders of magnitude faster both in training and inference. In particular, Buddy is 200-1000x faster than SEAL in dynamic mode
Table 3: Wall times. Training time is one epoch. Inference time is the full test set.
dataset
time (s)
SEAL dyn
SEAL stat
ELPH
BUDDY
GCN
prepror
630
0
Pubmed
train
70
30
25
inference
9
0.1
0.06
0.02
prepeoe
3,000,000
1,200
Citation
train
300,000
200,000
1,500
0OM
inference
300,0000
<- 1~100,000
300
for training and inference on the Citation dataset. We also show GCN as baseline. Further runtimes
and breakdown of preprocessing costs are Appendix D.I with learning curves in Appendix F
8 CONCLUSION
We have presented new model for L.P that is based on an analysis of existing sate-of-the-an models, but which achieves better time and space complexity and superior predictive performance on a range of standard benchmarks. The current work is limited to undirected graphs or directed graphs that are first preprocessed to make them undirected as is common in GNN research. We leave future work extensions to directed graphs and temporal/ / dynamically evolving graphs and investigations into the links with graph curvature (See Appendix C.5

---

Published as a conference paper at ICLR 2023
9 ACKNOWLEDGMENTS
We would like to thank Junhyun Lee, Seongjun Yun and Michael Galkin for useful discussions regarding prior works and we are particularly grateful to Junhyun and Seongjun for generating additional Neo-GNN results for Table 2 MB is supported in part by ERC Consolidator grant 724228 (LEMAN).
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In IJCAI, 2021.
Lada A Adamic and Eytan Adar. Friends and neighbors the web. Social networks, 25(3):211-25 2003.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Nips, 2013.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph
neural network expressivity via subgraph isomorphism counting. In PAMI. IEEE, 2022.
Andrei Z Broder. On the resemblance and containment of documents. In Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171), pp. 21-29. IEEE, 1997.
Benjamin P Chamberlain, Josh Levy-Kramer Clive Humby, and Mare P Deisenroth. Real-time community detection in full social networks on a laptop. PloS one. 13(1)xc0188702, 2018.
Benjamin Chamberlain, Emanuele Rossi, Dan Shiebler, Suvash Sedhain, and Michael M Bronstein. Tuning word2vee for large scale recommendation systems. In RecSys, 2020.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count
substructures? In NeurlPS, 2020.
Ahmed El-Kishky, Thomas Markovich, Serim Park, Chetan Verma, Backjin Kim, Ramy Eskander, Yury Malkov, Frank Portman, Soffa Samaniego, Ying Xiao, and Aria Haghighi. Twhin: Embedding the twitter heterogeneous information network for personalized recommendation. In SIGKDD, 2022.
Otmar Ertl. New cardinality estimation methods for hyperloglog sketches. arXiv:1706.072900 2017.
Matthias Fey and Jan Lenssen. Fast graph representation learning with Py PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In AofA: Analysis of Algorithms, DMTCS Proceedings. Discrete Mathematics and Theoretical Computer Science, 2007.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML,
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs In NeurlPS, 2017.
Stefan Heule, Marc Nunkesser, and Alexander Hall. Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. In Proceedings of the 16th International Conference Extending Database Technology, 2013.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS, 2020.
Kristian Kersting, Martin Mladenov, Roman Garnett, and Martin Grohe. Power iterated color refinement. In AAAI, 2014.
10

---

Published as a conference paper at ICLR 2023
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. PyTorch-BigGraph: A Large-scale Graph Embedding System. In SysML, 2019.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In NeurlPS, 2020.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 39006;:150-1170, 2011.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS, 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In Proceedings Mining and Learning with Graphs, 2012.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Liming Pan, Cheng Shi, and Ivan Dokmanić. Neural link prediction with walk pooling. In ICLR, 2022.
Andrew Pascoe. Hyperloglog and minhash-a union for itersections. attps::/tech.nexteee com/medi a 1 1mi nhash. fd 2013. Online; accessed May22y2.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performant deep learning library. In NeurlPS, 2019.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In SIGKDD, 2014.
Emanuele Rossi, Fabrizio Frasca, Benjamin P Chamberlain, Davide Eynard, Michael M Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks. arXiv:2004. // 11198 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-93, 2008.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In ICLR, 2019.
Jake Topping, Francesco Di Giovanni, Benjamin P Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via eurvature. In ICLR, 2022.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In /CMI., 2016.

---

Published as a conference paper at ICLR 2023
Haorui Wang, Haoteng Yin, Muhan Zhang. and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In ICLR, 2022.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI Series, 2(9):12-16, 1968.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In ICML, 2019.
Wei Wu, Bin Li, Chuan Luo, and Wolfgang Nejdl. Hashing-accelerated graph neural networks for link prediction. In The WebConf, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2015.
Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and system co-design for efficient subgraph- graph representation learning. In VLDB, 2022.
Jiaxuan You, Jonathan Gomes- Selme,, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In AAAI, 2021.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo Kim. Neo-gnns: Neigh- borhood overlap- aware graph neural networks for link prediction. In NeurlPS, 2021.
Muhan Zhang and Yixin Chen. Weisfeiler-lehman neural machine for link prediction. In SIGKDD, 2017.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NewrlPS, 2018.
Muhan Zhang and Yixin Chen, Inductive matrix completion based on graph neural networks. In ICLR, 2019.
Muhan Zhang and Pan Li. Nested graph neural networks. In NeurIPS, 2021.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory of using graph neural networks for multi-node representation learning. In NeurlPS, 2021.
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counterfactual links for link prediction. ICML, 2022.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B. 71(():623-6) 6300, 2009.
Zhaocheng Zhu, Zuobai Zhang, Louis- Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In NeurIPS, 2021.

---

Published as a conference paper at ICLR 2023
A THEORETICAL ANALYSES
A.1 PRELIMINARIES
We introduce some preliminary concepts that will be useful in our analysis. Let start with the definition of graph isomorphism and automorphism.
Definition A.1 (Graph isomorphism and automorphism). Lei G, = = (V1, E1), G2 = (V2, E2) be two simple graphs. An isomorphism between G₁, G2 is a bijective map ip Vi + V22 which preserves adjacencies, that is: Vu, v V1 : (u,v) E E1 > ((((), E Ez. J = Gz s is called an automorphism.
In view of the definition above, two graphs also called isomorphic whenever there exists an isomorphism between the two. Intuitively, if two graphs are isomorphic they encode the same exact relational structure, up to relabeling of their nodes. As we shall see next, automorphisms convey slightly different meaning: they allow to define graph symmetries by formalizing the concept of node structural roles.
The above definitions be extended to attributed graphs, more conveniently represented through third-order tensors A E R=nxd, xd, with = |V], d > the number of features (Maron et al. 2019 Zhang et al., 2021). Indexes in the first two dimensions of tensor A univocally correspond to vertexes in V through a bijection e: V . Here, elements (A) correspond to node features, while elements (A) A... j edge features, which include the connectivity information in E. Within this context, a graph is defined as a tuple G (V, E, E, A), and isomorphisms and automorphisms are interpreted as permutations acting on as:
(o ijk A00 Vo E S.
(11)
where S, is the set of all bijections (permutations) over n symbols. We then define the concepts of isomorphism and automorphism as:
Definition A.2 (Graph isomorphism and automorphism on attributed graphs). Ler G1, G2 be two attributed graphs represented by tensors A1, Ag E R=* xd An isomorphism between G1, G1.G2 is bijective map (permutation) E Sn such that o A =A.- For graph G A. E Sn is an automorphism if a A = A.
Let us get back to the information conveyed by automorphisms by introducing the following definition:
Definition A.3 (Graph automorphism group). Lei G be a simple graph and Ag be the set of graph automorphisms defined on its vertex set. Autg = (AG. o) is the group having bG as base set and function composition (o) as its operation.
Group Autg induces an equivalence relation S V x V: Vu,u E V,, ~G 4> 3i E Ag u (pv) (it easily proved that ~a is indeed reflexive, symmetric and transitive, thus qualifying as an equivalence relation). The equivalence classes of ~G partition the vertex set into orbits: (rb = {u E V u NG 2} = structural roles in the graph. Two vertexes belonging to the same orbit have the same structural role in the graph and are called 'symmetric' or 'automorphic'.
{ u E V 3ip E ÅG u = pov) }. The set of orbits identifies all
In fact, it is possible to define automorphisms between node-pairs as well (Srinivasan & Ribeiro 2019 Zhang et al. 202I)
Definition A.4 (Automorphic node pairs). Let G = A be an attributed graph and 4 = (u1, v1), = (u2, 122 E V be two pairs of nodes. We say E,, l2 are automorphic if there exists an automorphism a E Ag such that a f = (o((1), = (uz, 122) lz. We write é -/-6) by.
With the above it is possible to extend the definition of orbits to node-pairs, by considering those node-pair automorphisms which are naturally induced by node ones, i.e.: Vip E Ac, (u, v) + (vp()), ((()).
Notably, for two node pairs 4 (u1, U1), lg (u2, U2) E x V. {ur ~G u2 U1 NG 22 +
(1 ~02) lg, i.e., automorphism between nodes does not imply automorphism between node pairs. For instance, one counter-example of automorphic nodes involved in non-automorphic pairs is depicted in Figure while another one is constituted by pair (Nn, 02), (vo, v3) in Figure 7 whose automorphisms

---

Published as a conference paper at ICLR 2023
reported in Tables 4 Had This 'phenomenon' is the cause of the so-called "automorphic node problem".
Definition A.5 (Automorphic node problem). Let M be a family of models. We say M suffers from the automorphic node problem for any model M E M, and any simple (attributed) gruph G =
(V, E,,, 1, A) we have that V(u,, 01); (w2, v2) EVXV, {ur Na u2, on nG U2) = M ((u1, U1) = M ((#2, 02)).
The above property is identified as 'problem' because there exist examples of non-automorphic node pairs composed by automorphic nodes. A model with this property would inevitably compute the same representations for these non-automorphic pairs, despite they feature significantly different characteristics, e.g. shortest path distance or number of common neighbors.
Importantly, as proved by SSrinivaann & Ribeiro (201)) and restated by Zhang et al. (202T), the model family of Message Passing Neural Networks suffer from the aforementioned problem:
Proposition A.6. Let MMPNN be the family of Message Passing Neural Networks (Equation) !
representing node-pairs function their computed (equivariant) node representations. MMPNN suffers from the automorphic node problem.
We conclude these preliminaries by introducing the concept of link discrimination, which gives (more) fine fine-graing grained measure of the link representational power of model families.
Definition A.7 (Link discrimination). Let G (V, EV,,E, A) be any simple (attributed) graph and M a model belonging to some family M. Let &1 = (U1, 01), l = (u2, 02) E V x V be two node pairs. We say M discriminates pairs L, l2 iff ((1) o M (f2). We write FM L2 If there exists such model M E M, then family M distinguishes between the two pairs and we write ( FM² lz.
Accordingly. M does not discriminate pairs 4, l2 when it contains no model instances which assign distinct representations to the pairs. We write & = 6g.
We can compare model families based on their expressiveness, that is, their ability to discriminate node pairs:
Definition A.8 (More expressive). Let MI, M2 be two model families. We say Mi is more expressive than M2 iff VG AV, HE & e V #M, la & FM, lz. We write Mi M2
Put differently, M1 is more expressive than M2 when for any two node pairs, if there exists a model in M2 which disambiguates between the two pairs, then there exists model in Mj which does so as well. When the opposite is not verified, we say Mi is strictly more expressive than M2:
Definition A.9 (Strictly more expressive). Let M1,M2 2 be two model families. We say M1 is strictly more expressive than M2 iff Mi E M2 A M2 E Mi. Equivalently, Mi C M22 3G
E,, A), (i, A(2) l2 E x V, s.t. E HM, l2 A -M, lz.
In other words, Mi is strictly more expressive than M2 when there exists no model the latter family disambiguating between two non-automorphie pairs while there exist some models in the former which do so.
A.2 DEFERRED THEORETICAL RESULTS AND PROOFS
Let us start by reporting the Proof for Proposition stating that ELPH models do not suffer from the automorphic node problem.
In order to prove the Proposition it is sufficient to exhibit an ELPH model which distinguishes between two node-pairs whose nodes are automorphic. Consider = Co. the chordless cycle graph with 6 nodes, which we depict in Figure 7 Due to the symmetry of this graph, all nodes are in the same orbit, and are therefore automorphic: we report the set of all graph automorphisms Ag in Table 4. Let us then consider pairs & (Va, 222), &g (Ma, 2g). The two pairs satisfy the premise in the definition of the automorphic node problem. as Up ~G Up, U2 ~g Ug. One single ELPH paassig-- layer (k 1) produces the following (exact) structural features. Pair f; Aro. [1, 1] = 1, Bug. [1] = 1; pair E Avo. [1, 1] =]==00 0, Bun [1] 2. Thus, a one-layer ELPH
Proof of Proposition 4.7
model M is such that e, AM l2 if the readout layer p(u, v) = & x + xt, (8... Am. (1, 11)

---

Published as a conference paper at ICLR 2023
Figure 7: Graph Cg with nodes and node-pairs coloured according to the orbit they belong to. Node-pairs corresponding actual edges are depicted solid, dashed otherwise. There are 2 n 12 automorphisms which map any node to any other (see Table Hence all nodes are in the same, single orbit. On the contrary, node-pairs are partitioned into three distinct orbits (see Table As possible to notice, pairs (Vo, 02) and (vo, v3) are not automorphic, while their constituent nodes are.
Table 4: Images, for each node, according to the 12 automorphisms for graph Cg. See Figure
vertex
A
A2
A3
A4
A5
As
A7
Ag
Ag
A10
A1
A12
0
0
1
2
3
3
4
5
5
1
1
2
1
2
4
5
0
4
2
2
4
5
3
0
1
5
2
0
1
3
3
3
4
5
0
0
1
2
2
4
4
2
3
5
4
0
5
1
0
2
3
1
5
5
0
3
2
3
4
0
(1, 1]. An MLP implementing the deseribed da is only required to nullify parts of its input and apply an identity mapping on the remaining ones. This MLP trivially exists (it can even manually constructed).
Auv/1,
We now move to the counterpart of the above result for BUDDY models.
Proposition A.10. Let MBUDDY be the family of BUDDY models as described per Equations and pre-processed features Z = [x(") || x ....] X X(K]], where estimates are exact (AÅ = A, B B). MBUDDY does suffer from the automorphic node problem.
Proof of Proposition A.10 In order to prove the Proposition it is sufficient to notice that the readout in the above Proof completely neglects node features, while only replicating in output the structural features A. This is also valid BUDDY readout function, and allows BUDDY to output the same exact node-pair representations of the ELPH model described above. As we have observed, these are enough to disambiguate (2), proof.
v2), (vo, va) from graph Ce depicted in Figure 7 This concludes the
In these results have leveraged the assumption that A estimates exact. We observe that, if the MinHash and HyperLogLop estimators are unbiased, it would be possible to choose a sample size large enough provide distinct estimates for the counts of interest, so that the above results continue to hold. Unbiased cardinality estimators are, for instance, described in (Ertl 2017).
more precise assessment of the representational power of ELPH can be obtained by considering the node-pairs this model family is able discriminate w.r.t. others.
Lemma A.11. Let MELPH be the family of ELPH models (Equations that of Message Passing Neural Networks (Equation T). MELPH is more powerful than MMPNN MELPH MMPNN).
and T0 MMPNN

---

Published as a conference paper at ICLR 2023
Table Images, for each vode-pair, according the 12 induced node-pair automorphisms for graph C.. Pairs are considered as undirected (sets). See Figure 7
As it is possible to notice, there is no automorphism mapping pair (%o, 02) (Vo, 0/)) hence the two are distinct orbits.
pair
A
A2
As
A4
As
A6
A7
As
A9
A1o
A11
A12
(0. 1)
(0, 1)
00, 5)
(0. 1)
(1,2)
(1, 2)
(2, 3)
(2, 3)
(3, 4)
(3, 4)
(4, (4
(0, 5)
(4, 5)
(0, 2)
(0, 2)
(0, 4)
(1,5)
(1,3)
00, 2)
(2, 4)
(1,3)
(3, 5)
(2, 4)
(0, 4)
(1.5)
(3,5)
(0,3)
(0.3) 3)
(0.3)
(1,4)
(1,4)
(2
(2,
(0,3)
(0,3)
(1.4)
(1,4)
(2
(2,5)
(0, 4) (0, 4)
(0.2)
(1,3)
(1.5)
(2.4)
(0,2)
(3.5)
(1.3)
(0.4)
(2.4)
(3.5)
(1.5)
(0,5) (0, 5) (0,
(1,2)
(0.
(2.3)
(1,2)
(3.4)
(2.3)
(4.5)
(3.4)
(4,5)
(0,5)
(1,2) (1,2) (4.5)
(0.5)
(2.3)
(0,
(3.4)
(1.2)
(4.5)
(2,
(0.
(0.
(3.4)
(1,3) (1.3) (3.5)
(0.4)
(2.
(1.5)
(3.5)
(0.2)
(0.4)
(1.3)
(1.5)
(0.2)
(2,4)
(1,4) (1.4) (2.5)
(0.3)
(2.
(1,4)
(0.3)
(2.
(1.4)
(0.3)
(2.
(0.3)
(1.4)
(1.5) (1.5) (1.5)
(0.2)
(0.2)
(1.3)
(1.3)
(2.4)
4)
(2.4)
(3.5)
(3.5)
(0.4)
(0,4)
(2,3) (2,3) (3,4)
(4.5)
(3.4)
(0.5)
(4.
(0. 1) (0.5)
(1,2)
(0
(1,2)
(2,3)
(2,4) (2.4) (2,4)
(3,5)
(3.5)
(0,4)
4) (0,4)
(1,5)
(1,5)
(0
(0.2)
(1.3)
(1.3)
(2,5) (2.5) (1,4) (2,5)
(0,3)
(0,3)
(1,4)
(1,4)
(2,5)
(2.5)
(0.3)
(1.4)
(0.3)
(3,4) (3.4)
(2.3)
(3.4)
(4.5)
(4.5)
(0,5)
(0.5)
(0.
1)
(0.
(1.2)
(2.3)
(1.2)
(3,5)
(3.5)
(1.3)
(2.4)
(0. 4)
(3.5)
(1,5)
(0, 4)
(0.2)
(1.5)
(1.3)
(2. 4)
(0.2)
(4.5)
(4. 5)
(1.2)
(2,
(0. 5)
(3, 4)
(0, 1)
(4.
5)
(1.2)
(0,
5)
(2. 3)
(3, 4)
(0. 1)
Proof of Lemma-..1 We prove this Lemma by noticing that the ELPH architecture generalizes that of MPNN, so that ELPH model can learn simulate standard MPNN by ignoring the struc-
tural features. Specifically, ELPH defaults to an MPNN with (1) (())
( (1-1)
x
(1-1)
(ll)) Xa (1-1) X ". and (2) v/ (x x [Buv[d), Auoldus du] V dd, dus d, .,...... k)
(xx, O x This entails that, anytime specific MPNN instance distinguishes between two non-aute non-automorphic node-paire there exists an ELPH model which does so as well: the one which exactly simulates such MPNN.
Lemma A.12. There exist node-pairs distinguished by an ELPH or BUDDY model (with exact cardinality estimates) which are not distinguished by any MPNN model.
Proof of Lemma A. The Lemma is proved simply by considering non-automorphic pairs (vo, U2), (Vo. 03) from graph Cg depicted in Figure 7 We have already shown how there exists both ELPH and BUDDY model (computing exact estimates of A, B) which separate the two. On the other hand, we have already observed how the nodes in the pairs are automorphic as all belonging to the same orbit. Thus, the two pairs cannot possibly be distinguished by any MPNN, since they suffer from the automorphic node problem (Srinivasan & Ribeiro 2019 Zhang et al. 2021). as remarked Proposition A.6
Proof of Theorem 4.2
The Theorem follows directly from Lemmas A.11 and A.12
Does this expressiveness result also extend to BUDDY? While have proved BUDDY does not suffer from the automorphic node problem. its non parametric pessage-passing scheme is such that this family of models do not generally subsume MPNNs. On one hand, view of Lemma A.12] we know there exist node-pairs separated by BUDDY but not by any MPNN; on the other, this does not exclude the presence mode-pairs for which the vice-versa is true.
B ADDITIONAL EXPERIMENTAL DETAILS
B. DATASETS AND THEIR PROPERTIES
Table basic properties of the experimental datasets, together with the scaling of subgraph size with hops. Subgraph statistics are generated by expanding k-hop subgraphs around 1000 randomly selected links. Regular graphs scale as deg", however these datasets are all complex networks the size of subgraphs grows far more rapidly than this, which poses serious problems for SGNNs. Furthermore, the size of subgraphs is highly irregular with high standard deviations making efficient

---

Published as a conference paper at ICLR 2023
Table 6: Properties of link prediction benchmarks. Confidence intervals are one standard deviation.
Splits for the Planetoid datasets are random and Collab uses the fixed OGB splits. Where possible, baseline results for Collab are taken directly from the OGB leaderboard
Cora
Citeseer
Pubmed
Collab
PPA
DDI
Citation2
#Nodes 2,708
3,327
18,717
235,868
576,289
4,267
2,927.963
#Edges
5,278
4,676
44,327
1,285,465
30,326,273
1,334,889
30,561,187
splits
rand
rand
rand
time
throughput
time
protein
avg deg
3,9
2.74
4.5
5,45
52.62
312.84
10.44
avg dog"
15.21
7.51
20.25
29.70
2769
97,344
109
1-hop size
12=15
8+8
12
99+251
152=152
901++494
23:
2-hop size
1271131
58192
260
1151571
7790
3830
285
parallelization in scalable architectures challenging. The one exception this pattern is DDI. Due to the very high density of DDI, most two-hop subgraphs include almost every node.
B.2 EXPERIMENTAL SETUP
In all cases, we use the largest connected component of the graph. LP tasks require links play dual roles as both supervision labels and message passing links. For all datasets, at training time the message passing links are equal to the supervision links, while at test and validation time, disjoint sets of links are held out for supervision that are never seen at training time. The test supervision links are also never seen at validation time, but for the Planetoid and ogbl-collat datasets, the message passing edges at test time are the union of the training message passing edges and the validation supervision edges. OGB datasets have fixed splits whereas for Planetoid, random 70-10-20 percent train-val val-test splits were generated. On DDI, NBFnet was trained without learned node embeddings and with a batch size of 5.
B.3 HYPERPARAMETERS
The p parameter used by HyperLogLog was 8 and the number of permutations used by MinHashing was 128. All hyperparameters were tuned using Weights and Biases random search. The search space was over hidden dimension (64-512), learning rate (0.0001-0.01) and dropout (0-1), layers (1-3) and weight decay (0-0.001). Hyperparameters with the highest validation accuracy were chosen and results are reported
set that used only once.
B.4 SPACE COMPLEXITY
The space complexity for ELPH is almost the same as a GCN based link predictor. We define the number of feature as F. the sketch size H (sum of hll and minhash sketch sizes), number of nodes as N, the number of layers L, the batch size B and the number of edges as E. We split link prediction into i) learning node representations and ii) predicting link probabilities from node representations. Learning node representations with GCN has complexity
E+ + LNF,
(12)
where the second and third terms represent the weight matrices and the node representation respec- tively. ELPH has complexity.
LF LN(F + H)
(13)
And so the only difference is the additional space required to store the node sketches. The GCN link predictor has space complexity
BF + F2
(14)
Where the first term is a batch of edges and the second term are the link predictor weight matrices. ELPH also uses structure features, which assuming the number of GNN layers and the number of hops are the same, take up L(L+2) space per node. The link prediction complexity of ELPH is then
B(F + L(L 2)) F2 F(L 2)).
(15)
"The OGB rules allow validation edges be used for the ogbl-collab dataset.

---

Published as a conference paper at ICLR 2023
Typically the number of layers L is 1,2,3 and the additional overhead is small. The space complexity of the BUDDY link predictor is the same as ELPH and node representations are built as a preprocessing step. The preprocessing has space complexity
E LNF + LN LNH,
(16)
which correspond to the adjacency matrix, the propagated node features, the hil cardinality estimates and the minhash and hll sketches respectively. The only difference between this and ELPH that cardinality estimates are cached (LN) and weight matrices used.
B.5 IMPLEMENTATION DETAILS
Our code is implemented in Py PoTch (aszke et al. 2019). using Py geometric (Fey Lenssen 2019). Code and instructions reproduce the experiments are available at Intpp:: gi thub com/ me 1 fluos/ subgraph- ching We utilized either AWS p2 or p3 machines with Tesla K80 and Tesla V100 respectively to perform all the experiments in the paper.
C MORE ON STRUCTURAL FEATURES
C.I HEURISTIC METHODS FOR LINK PREDICTION
Heuristic methods are classified by the receptive field and whether they measure neighborhood similarity path length. The simplest neighborhood similarity method is the 1-hop Common Neighbor (CN) count. Many other heuristics such as cosine similarity. the Jaccard index and the Probabilistic Mutual Information (PMI) differ from CN only by the choice of normalization. Adamic- Adar and Resource Allocation are two closely related second order heuristics that penalize neighbors by a function of the degree
r(u,e)=
E
(17)
(EN( F(IN(I))
where Nuu) are the neighbors of Shortest path based heuristics are generally more expensive to calculate than neighborhood similarity as they require global knowledge of the graph to compute exactly. The Katz index takes into account multiple paths between two nodes. Each path is given a weight of ad, where a is a hyperparameter attenuation factor and d is the path length. Similarly Personalized PageRank (PPR) estimates landing probabilities of a random walker from single source node. For survey comparing 20 different LP heuristics see e.g. (Lü & Zhou 2011
C.2 SUBGRAPH GENERATION COMPLEXITY
The complexity for generating regular k-hop subgraph is Odeg"), where deg is the degree of every node in the subgraph. For graphs that are approximately regular, with well defined mean degree, the situation is slightly worse. However, general we are interested in complex networks (such as social networks, recommendation systems or citation graphs) that are formed as result of preferential attachment. Complex networks are typified by power law degree distributions of the form p( deg) deg As result the mean is only well defined if > 2 and the variance is finite only for 7 > 3. As most real world complex networks fall into the range < 7 < 3, we have that the maximum degree is only bounded by the number of edges in the graph and thus, is the complexity of subgraph generation. Table inccludes the average size of one thousand I-hop and 2-hop randomly generated graphs for each dataset used in our experiments. In all cases, the size of subgraphs greatly exceeds the average degree baseline with very large variances.
C.3 SUBGRAPII SKETCHES
We make use of both the HyperLogLog and MinHash sketching schemes. The former is used to estimate the size of the union, while the latter estimates the Jaccard similarity between two sets. Together they can be used to estimate the size of set intersections.
C.3.1 HYPERLOGLOG
HyperLogLog efficiently estimates the cardinality large sets. It accomplishes this by representing sets using constant size data sketch. These sketches can be combined in time that is constant w.r.t

---

Published as a conference paper at ICLR 2023
the data size and linear in the sketch size using clementwise maximum estimate the size of set union.
The algorithm takes the precision p as a parameter. From p. it determines the number of registers to use. The sketch for set S is comprised of registers M1 .....M,, MM. where 2". A hash function h(s) maps elements from S into an array of 64-bits. The algorithm uses the first p bits the hash to associate elements with a register. From the remaining bits, it computes the number of leading zeros, tracking the maximum number of leading zeros per register. Intuitively a large number of leading zero bits is less likely and indicates higher cardinality and for single register the expected cardinality for a set where the maximum number of leading zeros is n is 2". This estimate is highly noisy and there several methods combine estimates from different registers. We use hyperlogiog++ (Heule et al. 2013), for which the standard error is numerically close to
for large enough m.
Hyperioglog can be expressed in three functions Initialize, Union, and Card. Sketches are easily merged by populating new set of registers with the element-wise max values for each register. To extract the estimate, the algorithm finds the harmonic mean of 2M((m) for each of the the registers. This mean estimates the cardinality of the set divided by m. To find the estimated cardinality we multiply by and Om- O'm is used to correct multiplicative bias. Additional information about the computation of Om along with techniques to improve the estimate can be found in (Flajolet et al. 2007 Heule al. 2013). The full algorithm is presented in Algorithm T
Complexity
The Initialize operation has a (m + (S]) running time. Union and Card are both ((m) operations. The size of the sketch for 64-bit hash is 6 * 2 bits.
C.3.2 MINHASHING
The MinHash algorithm estimates the Jaccard index. can similarly be expressed in three functions Initialize, Union, and J. The p parameter is the number of permutations each element of the set. Pz( computes a permutation of input x where each specifies a different permutation. The algorithm stores the minimum value for each of the p permutations of all hashed elements. The Jaccard estimate of the similarity of two sets is given by the Hamming similarity of their sketches. The full algorithm is presented Algorithm
Complexity
The Initialize operation has ((np) running time. Union and J are both (np) operations, The size of the sketch is up longs. Minhashing gives an unbiased estimate of the Jaccard with variance given by the Cramer-Rao lower bound that scales as O(1mmp) (Chamberlain et al.
2018).
C.4 LABELING SCHEMES
Empirically, we found the best performing labeling scheme be DRNL, which scores each node in Suo based on it's distance to and with the caveat that when scoring the distance to u, node v and all of its edges are masked and vice versa. This improves expressiveness as otherwise for positive edges every neighbor of would always be 2-hop neighbor of u and vice-versa The result of masking is that distances can be very large even for 2-hop graphs (for instance one node may have an egonet that is star graph with a ring around the outside. If the edges of the star are masked then the ring must be traversed). The first few DRNL values are
1. disconnected nodes: (oo, 0), (0, xx) -
2. link nodes: (0, 1), (1,0) -
3. common neighbors: (1, +
4. 12-common-neighboo (1, (2, 1) +
5. 2-hop common neighbors: (2, 2) + 4
and the pattern has a hash function given by
f(ii) = 1 min(dus, + (d/2) + d%2)
(18)
where d == dus + dei- It slightly suboptimal to assign infinite distances to 0, which is at least part of the reason that they are one-hot encode them as labels. Indeed, DE (Li et al. 2020) uses a max distance label, which they claim reduces overfitting.

---

Published as a conference paper at ICLR 2023
Algorithm HgperLogLog: Estimate cardinality
Parameter is used to control precision.
m 2
procedure HLLINITIALIZE(S))
for i range(m)
M =
end for for E do
x = h(v)
idæ (T31, T32 232-p/2
= (T31 pI. 22/2
M (idr] mar(M (dd) o(w))
end for return .M end procedure
procedure HLLUNION(ML, M2) for i range(m) do
Mi = M2
end for return .M end procedure
procedure CARD(M)
return am m2 2 (E 2-Mili-- end procedure
C.5 SUBSTRUCTURE COUNTING AND CURVATURE
The eight features depicted in Figure can be used learn local substructures. Auo [1, counts the number of triangles that (u, 2) participates in assuming that the edge (u, v) exists. Auv 1] and Auv[1, 2] will double count four-cyele and single count a four-cycle with single diagonal. The model can not distinguish a four-clique from two triangles or five-clique from three triangles. Aur12, 2] counts five cycles. LP has also recently been shown to be closely related to notions of discrete Ricci curvature graphs (Topping et al. 2022), connection that we plan exploring in future work.
C.6 EXAMPLE STRUCTURE FEATURES
Figure g provides an example of how structure features are calculated from subgraph. The figure provides the z values for each node in an eight node subgraph. From these the structure features are calculated. As an example
As7 [2, 1] (,, (,,3,4,6,7 (2 =1
(19)
Be7 [2] (,,3,4, (1,7,3,5,6,7888 = -144=1
(20)
The value of As7|2, 1] = 1 indicates that the is one node common between the two-hop neighbors of node 6 and the 1-hop neighbors of node 7. The common node is node 2. Similarly B,7 2 = 1 means there one element in the two-hop neighbors of that not any the k-hop neighbors of 7: node 4.
D ADDITIONAL EXPERIMENTS
D.I RUNTIMES AND DISCUSSION
The results in Tables and are obtained by running methods on a single Tesla K80 GPU on an AWS p2 machine. In all cases SEAL used GCN (fastest GNN) and parameters taken from the

---

Published as a conference paper at ICLR 2023
Algorithm 2 MinHash: Estimate Jaccard Similarity
Parameter npp controls the number of permutations. procedure MINHASHINITTALLZRSS)))
for i E range(mp) do
M -arvaauue end for
for E S do
x h(u)
for E range(np) do
min
= min [i), Pi(x))
end for end for return M end procedure
procedure MINHASHUNION(M1 M2) for i E range(np) do Mi [ end for return M end procedure
procedure J,M1, M2)
numn_equal for i E range(mp) do
M1[i] = [ then
num_eqqull + + end if end for return run_equal/my end procedure
2,10|((3)
(111=(1,223) 2,11,((1.2.3,4,566.7.
2,[0][(1)
2,10=22)
[1]:(11.233444.)
2111((1.23366777
2 2.
(1234.66)
z.[0]=(6)
2,10)=(4)
2,10]=(5)
2,10|=7}
z.(1)=(1.6.8)
(11))_(1.455
2,11)=(2.4.5) 2.125-(1.23344.5.7))
2111=(2.7.88
2/12)=(1.2.3446677888
2.134-(1.2334455.6)
2,121-(1.2233566678.88)
[0]=
(1)=
2 [2)=
Figure 8: Computed features

---

Published as a conference paper at ICLR 2023
Table Wall time of our methods in comparison SEAL in dynamic and static mode. Training time is for one epoch. Inference time is for the full test set. Due to high runtimes, values for SEAL are estimated from samples for the OGB datasets
dataset
Wall time (sec)
SEAL dyn
SEAL stat
ELPH
Buddy
Preprocessing
57
0
0.4
Cora
Training (1 epoch)
2
0.7
Inference
0.05
0.04
Preprocessing
48
0
0.7
Citeseer
Training (1 epoch)
13
0.5
Inference
20
0.03
0.07
Preprocessing
Pubmed
Training (1 epoch)
25
1
inference
0.1
0.06
Preprocessing
25000
0
43
Collab
Training (1 epoch)
555000
~<330
2100
105
Inference
~50000
~160
2
1
Preprocessing
900,000
840
PPA
Training (1 epoch)
130,000
150,000
OOM
75
Inference
~00,000
16,000
18
Preprocessing
3,000,000
1,200
Citation
Training (1 epoch)
~000,000
200,000
OOM
1,450
inference
~300,000
100,000
280
Preprocessing
400,000
0
66
Training (1 epoch) Inference
150,000
250,000
30
27
11,000
199,00
0.6
0.4
Table The three types of preprocessing used in BUDDY and associated wall times. Entity gives the entity associated with the preprocessed features. Each node has a hash and propagated features while each edge requires structure features
Wall time (sec)
Entity
Cora
Citeseer
Pubmed
Collab
PPA
Citation
DDI
hashing
node
0.12
0.1
1.04
26
469
714
20.3
feature propagation
node
0.27
0.60
0.67
4.6
126
NA
structure features
edge
0.02
0.01
3.3
12.0
294
393
45.76
SEAL OGB repo. For the OGB datasets, SEAL runtimes are estimated based on samples due to the high runtimes.
Table g breaks BUDDY preprocessing times down into (i) generating hashes and (ii) propagating features for each node, where the same values are used for training and inference and (ii) constructing structure features from hashes for each query edge, which has a separate cost for inference. We stress that both forms of preprocessing depend only on the dataset and so must only be done once ever for fixed dataset and not e.g. after every epoch. This is akin to the static behavior of SEAL (Zhagg & Chen 2018), where subgraphs are constructed for each edge (both training and inference) as preprocessing step.
D.2 ABLATION STUDIES
This section contains ablation studies for (i) the affect of varying the number of Minhash permutations and the HyperLogLog p parameter and (ii) removing either node features or structure features from BUDDY.
D.2.1 HASHING PARAMETER ABLATION
Figures 9 and 10 are ablation studies of the hashing parameters that trade-off between accuracy and time/space complexity of the intersection estimates. The method is relatively insensitive to both parameters allowing smaller values to chosen when space time complexity is a constraint. Figure shows that good performance is achieved providing more than 16 minhash permutations

---

Published as a conference paper at ICLR 2023
H5g50 by number of minhash permutations
HRD59 by hyperiogiog p parameter
20.0
70
ab
0011
6197
65p3
64/3
69
11.2
10020
100550
575
64-
62-
62.5
51.65
16
22
64
220
226
10
(a) number of minhash permutations.
(h) hyperlogiog p parameter
Figure 9: Ablation study for hashing parameters for Collab dataset
HR8100 by number of minhash peruuaatoons
HR,910 by hyperioging parameter
Curu
100g200
30
32
66
128
255
20
(a) number of minhash permutations.
(b) hyperloglog p parameter
Figure 10: Ablation study for hashing parameters for Planetoid datasets
used, while Figure 9b shows that p can be low in the hyperloglog procedure. For Figure I0 values were calculated with no node features to emphasize the affect of only the hashing parameters. This not required for Figure Segure/Bbecaaee because relatively speaking the node features are less important for Collab (See Table 9)
Data sketching typically introduces a tradeoff between estimation accuracy and time and space complexity. However, in our model, the time complexity for generating structure features from hashes is negligible at both training and inference time compared to the cost of forward pass of the MLP.
HRg50 by number of hops
HR-0300 by numb or of hops
Core
61
15
$2.90
15
20
45
30
60
75
20
(a) Collab dataset
(b) Planetoid datasets
Figure 11: Ablation study for the number of hops

---

Published as a conference paper at ICLR 2023
Cora Citeseer
Collab
1800
140
Pubmed
1600
120
1400
100
800
600
400
16
102
16
10
(a) Planetoid datasets.
Collah
Figure 12: runtime of hash generation against number of minhash permutations
Cora
Citeseer
Pubmed
Collab
Citation2
DDI
#Nodes
2,708
3,327
18,717
235,868
$76,289
2,927,963
4267
#Edges
5,278
4,676
44,327
1,285,465
30,326,273
30,561,187
1,334,889
avg deg
3.9
2.74
4.5
5,45
$2.62
10.44
312.84
metric
HR 100
HR@ 100
HR@ 100
HR@50
HR 100
MRR
HR@20
CN
33.92=0.46
29. 79.000
23.13+0.15
56.44+0.00
27. 27.65+2..00
51.7=
17.73=0.00
AA
39.85 11..34
35.1911.3
27.3810.11
64.3510.00
32. 12.45510.00
51.89.10.0
18.61
RA
41.07:0.48
33.5610.17
27.03
64.00
49.33:10.00
51.98.0.00
27.60=0.00
BUDDY
88. 11.00=a..uu
92. 92.93++0.27
74.10=0.m
65. 16.9440..5
49 19.85=0.200
87 87.56=00
78.51+1.90
w/O Features
48.45 14.83
36.3315.59
53.5012.29
60.4610.88
49 40.85.10.20
82.27.0..
NA
w1O SF
83.90=2.24
91.24:1144
65.57
22.8311.22
1.20
83.69
74.01
Table 9: Ablation table showing the affects of removing both structure features and node features from BUDDY with all hyperparameters held fixed. Core heuristics are shown for comparison with the who features row. Confidence intervals one sd. Planetoid splits random and the OGB splits are fixed.
The only place where these parameters have appreciable impact runtimes is in preprocessing the hashes. When preprocessing the hashes, the cost generating hyperloglog sketches is also negligible compared the cost of the minhash sketches. The relationship between the number of minhash permutations and the runtime to generate the hashes is shown Figure
D.2.2 FEATURE ABLATION
Table shows the degradation in performance of BUDDY with either structure features node features removed with all hyperparameters held fixed. DDI has no node features and BUDDY did use the node features from PPA. which are one-hot species labels. For datasets Collab and PPA. the structure features dominate performance. For the Citation dataset, the contribution of structure features and node features is almost equal, with relatively small incremental benefit of adding second feature class. For the Planetoid datasets adding structure features gives a significant, but relatively small incremental benefit beyond the node features. should also be noted that combining node and structure features dramatically reduces the variance over runs for the Planetoid and Collab datasets.
E FULL BUDDY ALGORITHM
sketch of the full algorithm is given in Algorithm
F LEARNING CURVES
We provide learning curves in terms of number of epochs in Figures 13
19

---

Published as a conference paper at ICLR 2023
Algorithm 3 Complete Procedure
Preprocess structure features and cache propagated node features with Graph G and features X procedure PREPROCESSING(G, X)
H1 MINHHASHINTTALIZE((]
H2 HLLIINIIALIZE(G)
X Propogale(X)
end procedure
Generate edge probability predictions y using an MLP procedure PREDICT((I.H2.X) for edge (u, E epoch do
S u.v Ty = GetN ode eatures X)) Tp Get ode Features X")
Featuresee, v, H1, H2)
Y MLP(S (SF u,y: T.y) X.p)
end for end procedure
90
WAIHENg1100
85
0.3
Tran
70
0.2
60
0.0
10
Epech
Epoch
Epoch
Epoch
Figure 13: Loss and train-val-ter learning curves as function of training epoch, averaged over restarts. Solid line represents mean value and shadowed region shows one standard deviation. Cora dataset.
0.6
0.5
Thin--t---100 1.00000
8D
Tediting (00
0.3
XMC
50
0.0
10
10
20
20
30
Epoch
Epoch
Spoch
Epoch
Figure 14: Loss and train-ver ciii--valtest learning curves as function of training epoch, averaged over restarts. Solid line represents mean value and shadowed region shows one standard deviation. Citeseer dataset.
120
85
0.3
50
VoINet-0000
0.0
0.15
60
0.5
22
10
Epoch
Epach
Epoch
Epoch
Figure 15: Loss and train-val-tess learning curves as function of training epoch, averaged over restarts. Solid line represents mean value and shadowed region shows one standard deviation. Pubmed dataset.

---

Published as a conference paper at ICLR 2023
500
3.30
2.90
06-4
23
20
23
25
15
21
25
Figure 16: Loss and train-val-test learning curves function of training epoch, averaged restarts. Solid line represents mean value and shadowed region shows one standard deviation. ogbl- Collab dataset.
33006
10.0
W
MW
672
TOPNERS
3330
1/
8
33218
03032
22009
22007
Epoch
22007
Figure 17: Loss and train-val-test learning curves as a function of training epoch, averaged over restarts. Solid line represents mean value and shadowed region shows one standard deviation, ogbl- PPA dataset.
K1.0
2.20
38.5
3320
2.12
3316
05.0
Figure 18: Loss and train-val-test learning curves as function of training epoch, averaged over restarts. Solid line represents mean value and shadowed region shows one standard deviation. ogbl- Citation2 dataset.

---

Published as a conference paper at ICLR 2023
70
0.30
025
Owb
20
10
010
50
100
150
50
100
150
50
1.00
150
50
100
150
Epoch
Epoch
Epoch
Figure 19: Loss and train-val-test learning curves as a function of training epoch, averaged over restarts, Solid line represents mean value and shadowed region shows one standard deviation, ogbl- DDI dataset.
G SOCIETAL IMPACT
We study LP graph-structured datasets focusing primarily on methods rather than applications. Our method, in principle, may be employed in industrial recommendation systems. We have evidence that our method enhances biases, but were to be deployed, checks would need to be put in place that existing biases were not amplified.


Reviews:
[{"review_id": "uzJc622Sub", "reviewer": "Reviewer_ucmP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies GNN-based link prediction models. The authors experimentally analyze the components of existing subgraph GNN (SGNN) methods for link prediction, which exhibit some limitations and redundancy. Then propose a novel method that passes subgraph sketches as messages, which mitigates these issues effectively. ", "summary_of_the_review": "The paper investigates the components of existing SGNN link prediction methods and identifies several key limitations and opportunities of improvements. Then proposes a novel method to use subgraph sketches as messages. Empirical results clearly show the advantages of the proposed method. ", "strength_and_weaknesses": "Strength:\n1. The analysis on the components of existing SGNN methods for link prediction is well-conducted and the results are informative, which may inspire new thoughts on SGNN-based link prediction.\n2. The idea that passes subgraph sketches as messages is novel.\n3. The empirical results render the efficiency and effectiveness of the proposed method.\n4. A more scalable variant is implemented, which prepropagates the node features in the preprocessing stage. This further mitigate the scalability issue of SGNN-based link prediction such as SEAL.\n\nWeaknesses:\nI found the expressiveness analysis is less exciting. Here, more powerful means the capability of distinguishing automorphic nodes. But this can be realized by simple techniques such as adding random features. So, I don't think this is a good theoretical justification of better performance. Can you provide some comments on this?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "feoMVOcM-ZU", "reviewer": "Reviewer_jqUA", "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": "", "summary_of_the_paper": "This paper presents a novel Graph Neural Networks, ELPH and BUDDY, that estimates key structural information in subgraph GNN without explicit subgraph construction. Specifically, the proposed method estimates intersection and cardinalities using subgraph sketching and incorporates them into Message Passing type GNNs. The paper provably shows more expressive power than Message Passing GNNs and experiments conducted on six link prediction benchmarks show both effectiveness and efficiency compared to state-of-the-art baselines.\n", "summary_of_the_review": "This paper presents a novel Graph Neural Networks, ELPH and BUDDY, that estimates key structural information in subgraph GNN without explicit subgraph construction. The presentation of the paper is clear and the proposed idea is very interesting and novel.", "strength_and_weaknesses": "Strengths\n\n- The essential factors for the performance of existing subgraph-level GNNs are well analyzed through the experimental observation of the SGNNs.\n\n- The proposed idea of effectively estimating intersections and cardinalities without subgraph construction is interesting and novel.\nBy leveraging structural features, the proposed method addresses the inefficiency of existing subgraph-based methods and the automorphic node problem in MPNN.\n\n- Experiments conducted on six link prediction benchmarks show both the effectiveness and efficiency of ELPH and BUDDY compared to recent GNN-based baselines.\n\nWeakness\n\n- Performance between baselines in ogbl-collab does not seem to be compared fairly. The performance of SEAL in ogbl-collab seems to be the performance using the validation set for training whereas other GNN-based methods (GCN, SAGE, Neo-GNN) don’t seem to use the validation set for training.\n\n- It would be good if there were comparisons with GNNs with existing proposed structural features (e.g., DE [1] and node2vec [2]).\n\n[1] Li, Pan, et al. \"Distance encoding: Design provably more powerful neural networks for graph representation learning.\" Advances in Neural Information Processing Systems (2020)\n\n[2] Grover, Aditya, and Jure Leskovec. \"node2vec: Scalable feature learning for networks.\" Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "W89_GqY2Mu", "reviewer": "Reviewer_9q6R", "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": "", "summary_of_the_paper": "This paper focused on the research problem of link prediction with GNNs. The authors comprehensively analyzed why the subgraph-based GNNs performs good on link prediction, as well as their efficiency problems. The authors then proposed to estimate the key structural information with subgraph sketching. Doing so combined the advantages of effectiveness on SGNNs as well as the efficiency on full-graph GNNs. \n", "summary_of_the_review": "Based on the above comments, I recommend acceptance. But I still encourage the authors to address the weaknesses.", "strength_and_weaknesses": "S1. This paper is overall clearly written and easy to follow.\n\nS2. The proposed method is very well motivated with comprehensive analysis on why subgraph GNNs works well.\n\nS3. The proposed method is able to successfully combine the advantages of SGNN as well as normal GNNs for link prediction. \n\nW1. Part of the notations in Sec. 2 are a bit confusing. For example. is $Z_{uv}$ a matrix / set of node embeddings or a vector of subgraph embedding? And why is the $u$ in $\\mathbf{y}_{\\mathbf{u}}$ (Eq. (1)) bolded, but not bolded elsewhere (e.g., in the following paragraph)?\nI suggest the authors to follow the common way of denoting vectors and matrices. E.g., using bold lowercase for vectors and bold uppercase for matrices. Currently most but no all of the paper follows that.\n\nW2. I assume the complexity in Sec. 5 and Table 1 are time complexity. If yes, it would be nice if the authors can also provide the space complexity analysis.\n\nW3. As one of the goal of the proposed method is to obtain the effectiveness of subgraph GNNs while still being efficient and scalable, I think it would make the evaluation more comprehensive if the authors can also include the runtime of normal GNNs in Table 3 for comparison.  \n\nMinor ones:\n\nW4. Missing some recent relevant link prediction citations. E.g., [1][2]\n\nW5. In the first paragraph of Introduction, why are points i and ii bolded by not iii?\n\n[1] Learning from Counterfactual Links for Link Prediction, ICML 2022 \\\n[2] Neural Link Prediction with Walk Pooling, ICLR 2022", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "PGJYjH0qrLW", "reviewer": "Reviewer_ntmc", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a faster and more powerful GNN dedicated for the link prediction task. It captures the essence of success from previous state-of-the-art link prediction methods: subgraph-based structure encoding, which is essentially counts of various \"common neighbors\". To accelerate subgraph-based structure encoding, the authors sharply draw from its connection with the message passing form of computing graph sketches, and integrate this process into MPNN's framework. Experiments show that the proposed method achieves better performance compared to previous SOTAs in terms of both accuracy and scalability.\n\n", "summary_of_the_review": "I strongly recommend the acceptance of the paper for reasons outlined above. However, it would be great to see the code be made available considering that this is very likely to be an impactful piece of research.", "strength_and_weaknesses": "I am the author of one of the main baselines compared in the paper. I believe that this is an excellent paper with the following significant contributions:\n1. It unifies the several existing state-of-the-art methods for link prediction prediction and does systematic analysis to show their actual strengths of design. \n2. It is fascinating to see how the computational redundancy in subgraph-based neighbor counting can be eliminated by the message passing form of graph sketch using hyperloglog and minhashing. This is one of the most innovative and smartest GNN designs I have seen in a while.\n3. The experiments including those in Appendix D show that the proposed method perform very well by both accuracy and speed. The main claims in the theoretical parts are well substantiated by the experiments.\n\nWeaknesses:\nI don't see it as a strong negative but I have a question about Fig. 2: it is a bit surprising to see that DRNL (SEAL) can outperforms DE by such a huge margin on Pubmed, considering that SEAL's node labeling function is not more expressive that DE's one-hot distance encodings. Can any explanation be provided on that?\nAlso just a minor typo: the citation after \"Distance Encoding (DE)\" on Page 4 seems incorrect.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%