{'fraction_non_alphanumeric': 0.039412634477132516, 'fraction_numerical': 0.013970325804313465, 'mean_word_length': 4.925679758308157, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sampling Enclosing Subgraphs for Link Prediction

Link prediction is a fundamental problem for graph-structured data (e.g., social networks, drug side-effect networks, etc.). Graph neural networks have offered robust solutions for this problem, specifically by learning the representation of the subgraph enclosing the target link (i.e., pair of nodes). However, these solutions do not scale well to large graphs as extraction and operation on enclosing subgraphs are computationally expensive, especially for large graphs. This paper presents a scalable link prediction solution, that we call ScaLed, which utilizes sparse enclosing subgraphs to make predictions. To extract sparse enclosing subgraphs, ScaLed takes multiple random walks from a target pair of nodes, then operates on the sampled enclosing subgraph induced by all visited nodes. By leveraging the smaller sampled enclosing subgraph, ScaLed can scale to larger graphs with much less overhead while maintaining high accuracy. ScaLed further provides the flexibility to control the trade-off between computation overhead and accuracy. Through comprehensive experiments, we have shown that ScaLed can produce comparable accuracy to those reported by the existing subgraph representation learning frameworks while being less computationally demanding.


INTRODUCTION
Graph-structured data such as user interactions, collaborations, protein-protein interactions, drug-drug interactions are prevalent in natural and social sciences. Link prediction-a fundamental problem on graph-structured data-intends to quantify the likelihood of a link (or interaction) occurring between a pair of nodes (e.g., proteins, drugs, etc.). Link prediction has many diverse applications such as predicting drug side effects, drug-repurposing [14], understanding molecule interactions [18], friendship recommendation [9], and recommender systems [39].
Many solutions to link prediction problem [24,[26][27][28]35] has been proposed ranging from simple heuristics (e.g., common neighbors, Adamic-Adar [1], Katz [19]) to graph neural networks (GNNs) [5,6,17,21,30,45]. Among these solutions, GNNs [15,36,48] have emerged as the widely-accepted and successful solution for learning rich latent representations of graph data to tackle link prediction problems. The early GNNs focused on shallow encoders [13,32] in which the latent nodes' representations was first learnt through a sequence of random walks, and then a likelihood of a link is determined by combining its two-end nodes' latent representations. However, these shallow encoders were limited by not incorporating nodal features and their incompatibility with inductive settings as they require that all nodes are present for training. These two challenges were (partially) addressed with the emergence of message-passing graph neural networks [16,22,37]. These advancements motivate the research on determining and extending the expressive power of GNNs [3,12,[40][41][42]46] for all downstream tasks of link prediction, node classification, and graph classification. For link prediction, subgraph-based representation learning (SGRL) methods [5,6,25,30,45]-by learning the enclosing subgraphs around the two-end nodes rather than independently learning two end-node's embedding-have improved GNNs expressive power, and offered state-of-the-art solutions. However, these solutions suffer from the lack of scalability, thus preventing them to be applied to large-scale graphs. This is primarily due to the computation overhead in extracting, preprocessing, and learning (large) enclosing subgraphs for any pair of nodes. We focus on addressing this scalability issue.
Contribution. We introduce Sampling Enclosing Subgraph for Link Prediction (ScaLed) to extend SGRL methods and enhance their scalability. The crux of ScaLed is to sample enclosing subgraphs using a sequence of random walks. This sampling reduces the computational overhead of large subgraphs while maintaining their key structural information.
can be integrated into any GNN, and also offers parallelizability and model compression that can be exploited for large-scale graphs. Furthermore, the two hyperparameters, walk length and number of walks, in ScaLed provides a way to control the trade-off between scalability and accuracy, if needed. Our extensive experiments on real-world datasets demonstrate that ScaLed produces comparable results to the state-of-the-art methods (e.g, SEAL [45]) in link prediction, but requiring magnitudes less training data, time, and memory. ScaLed combines the benefits of SGRL framework and random walks for link prediction.
Other related work. Graph neural networks have benefited from sampling techniques (e.g, node sampling [7,16,49] and graph sampling [43]) to make training and inference more scalable on large graphs. Also, historical embeddings [8,12] have shown promises in speeding up the aggregation step of GNNs for the downstream task of node classification [7,10,12]. However, little attention is given to scaling up of SGRL methods for link prediction; except a few exceptions [38,42], which do not benefit from GNNs for subgraph learning [38] or is restricted to learning on individual nodes [42].
given the observed tensor A. The learning problem is to find a likelihood (or scoring) function such that it assigns interaction likelihood (or score)ˆto each target pair of nodes ( , ) ∉ , whose relationships to each other are not observed. Largerˆindicates a higher chance of ( , ) forming a link or missing a link. The function can be formulated asˆ= ( , , A| ) with denoting the model parameters. Most link prediction methods differ from each other in the formulation of the likelihood function and its assumptions. The function can be some parameter-free predefined heuristics [1,19,29] or learned by a graph neural network [16,22,33,37] or any other deep learning framework [38]. The likelihood function formulation also varies based on its computation requirement on the maximum hop of neighbors of target nodes. For example, first-order heuristics (e.g., common neighbors and preferential attachment [2]) only require the direct neighbors while graph neural networks methods [16,21] and high-order heuristics (e.g., Katz [19], rooted PageRank [4]) require knowledge of the entire graph.

THE ScaLed MODEL
After describing the SEAL link prediction model and its variants, we detail how our proposed ScaLed model extends these models to maintain their prediction power but offer better scalability.
SEAL and its variants. Rather than learning the target nodes' embeddings independently (as with Graph Convolutional Network [22] or GraphSAGE [16]), SEAL [45] focuses on learning the enclosing subgraph of a pair of target nodes to capture their relative positions to each other in the graph: Definition 1 (Enclosing Subgraph [45]). Given a graph , the ℎ-hop enclosing subgraph around target nodes (u,v) is the subgraph ℎ induced from with the set of nodes { ∥ ( , ) ≤ ℎ ( , ) ≤ ℎ}, where ( , ) is the geodesic distance between node and .
In SEAL, for each pair of the target nodes ( , ), their enclosing subgraph ℎ is found and extracted with two ℎ-hop Breadth-First Search (BFS), where each BFS starts from and . The nodes in the extracted enclosing subgraph are also augmented with labels indicating their distances to the target pair of nodes using the Double-Radius Node Labeling (DRNL) hash function [45]: where represents the nodes in the subgraph ℎ , is the geodesic distance of to in ℎ when node is removed, and ′ = + . Note that the distance of to each target node is calculated in isolation by removing the other target node from the subgraph. The target nodes are labeled as 1 and a node with ∞ distance to at least one of the target nodes is given the label 0. Each node label is then represented by its one-hot encoding, and expands the initial node features, if any. The subgraph ℎ along with the augmented nodal features is fed into a graph neural network, which predicts the presence or absence of the edge. In SEAL, the link prediction is treated as a binary classification over the enclosing subgraphs by determining if the enclosing subgraph will be closed by a link between the pair of target nodes or not. Thus, SEAL uses a graph pooling mechanism (e.g., SortPooling [46]) to compute the enclosing subgraph representation for the classification task. Other variants of SEAL (e.g., DE-GNN [25] and WalkPool [30]) have replaced either its DRNL labeling method [25] or graph aggregation method [25] with some other alternatives to improve its expressivness power. However, SEAL and these variants all suffer from the scalability issue as the subgraph size grows exponentially with the hop size ℎ, and large-degree nodes (e.g., celebrities) possess very large enclosing subgraphs even for a small ℎ. To address these scalablity issues, we propose Sampling Enclosing Subgraph for Link Prediction (ScaLed).
ScaLed. Observing that the computational bottleneck of SEAL and its variants originates from the exponential growth and the size of enclosing subgraphs, we propose Sampled Enclosing Subgraphs with more tractable sizes: Given a graph , the random-walk sampled ℎ-hop enclosing subgraph around target nodes (u,v) is the subgraphˆℎ , induced from with the set of nodesˆℎ , ∈ ℎ, ∪ ℎ, , where ℎ, is the set of nodes visited by many h-length random-walk(s) from node .  Figure  1(b) contains all nodes and edges between nodes inˆℎ , . Comparing Definitions 1 and 2, a few important observations can be made: (i) the sampled enclosing subgraphˆℎ , is the subgraph of the enclosing subgraph ℎ , as the ℎ-length random walks can not reach a node further than ℎ-hop away from the starting node; (ii) the size of the sampled subgraph is bounded to (ℎ ) and controlled by these two parameters compared to the exponential growth of enclosing subgraphs with ℎ in Definition 1. ScaLed, by replacing the dense enclosing subgraphs with their sparse (sub)subgraphs, offers scalability, while still providing flexibility to control the extent of sparsity and scalability with its sampling parameters ℎ and .
The ScaLed model can use any labeling trick (e.g., DRNL, zeroone labeling, etc.) [47] to encode the distances between target nodes and other nodes in the sampled subgraphs; see Figure 1(b) for an example. Similar to SEAL, the one-hot encoding of the distance labels along with the nodal features (if any) of the nodes in the sampled subgraph are fed into a graph neural network with graph pooling operation (e.g., DGCNN with SortPooling operation [46]) for the classification task. The ScaLed model offers easy plug-andplay modularity into most graph neural networks (e.g., GCN [22], GIN [37], GraphSAGE [16], DGCNN [46], etc.), and can also be used alongside any regularization technique or loss function.
Although random walks have been used in unsupervised latent learning of graph data [13,32], ScaLed has used them differently for sparsifying the enclosing subgraphs to enhance scalability. This random-walk subgraph sampling technique can be incorporated into any other subgraph representation learning task to improve scalability by increasing sparsity of the subgraph. This technique does not incur much computational overhead, can be viewed as a preprocessing step, and can benefit from parallelizability. Furthermore, random-walk sampled subgraphs have controllable size and and do not grow exponentially with ℎ.

EXPERIMENTS
We run an extensive set of experiments to compare the prediction accuracy and computational efficiency of ScaLed against a set of state-of-the-art methods for link prediction. We further analyze its hyperparameter sensitivity and its efficacy in improving subgraph sparsity. 1 Datasets. We consider a set of homogeneous, undirected graph datasets (see Table 1), which have been commonly subject to many other link prediction studies [5,6,17,25,30,34,44,45] and are publicly available. Our datasets are categorized into non-attributed and attributed datasets where nodal features are absent or present in the dataset, respectively. The edges in each dataset are randomly split into 85% training, 5% validation, and 10% testing datasets. Each dataset split is also augmented with random negative samples (i.e, absent links) at a 1:1 ratio for positive and negative samples.
Baselines. We compare our ScaLed against a comprehensive set of baselines in four categories: heuristic, graph autoencoder (GAE), latent feature-based (LFB), and SGRL methods. For heuristic methods, we use common neighbors(CN), Adamic Adar(AA) [1], and Personalized PageRank (PPR). GAE baselines include GCN [22], GraphSAGE [16], and GIN [37] encoders with a hadamard product of a pair of nodes' embedding as the decoder. The LFB methods consists of matrix factorization [23] and node2vec [13] with the logistic classifier head. Our SGRL baseline is state-of-the-art method SEAL [45].
Setup. GAE baselines have three hidden layers with dimensionality of 32. The nodal initial features, for non-attributed datasets, are set to one-hot indicators. In MF, the nodal latent feature has 32 dimensions for each node. MF uses a three-layered MLP with 32 hidden dimensions. For node2vec, we set sampling parameters = = 1 and a dimensionality of 32 for the node features. For SEAL, we set ℎ = 2 for non-attributed datasets and ℎ = 3 for attributed datasets. We also use a three-layered DGCNN with a hidden dimensionality of 32 for all datasets. For ScaLed model, we set = 20 while ℎ and all other hyperparameters are set the same as that of SEAL for fair comparison. The learning rate is set to 0.0001 for SEAL and ScaLed and 0.01 for node2vec, MF and GAE baselines. All learning models for both attributed and nonattributed datasets are trained for 50 epochs with a dropout of 0.5 (except for node2vec without dropout) and Adam [20] optimizer (except for node2vec with Sparse Adam). GAE baselines are trained by full-batch gradients; but others are trained with a batch size of 32. The detailed experimental setup used for each baseline and dataset is available in Github. 2 Measurements. For all models, we report the mean of area under the curve (AUC) of the testing data over 5 runs with 5 random seeds. For each model in each run, we test it against testing data with those parameters which achieve highest AUC of validation data over training with 50 epochs. For computational resource measurements, we also report average training-plus-inference time, allocated CUDA memory, model size, and number of parameters.   Results: AUC. Table 2 reports the average AUC over five runs for all datasets and link prediction models. In all attributed and non-attributed datasets, ScaLed is ranked first or second among all baselines. Also, ScaLed gives very comparable results to SEAL or even outperforms SEAL in some datasets (e.g., NS and Yeast). This performance has also been achieved by order of magnitudes less resource consumption.
Results: Resource Consumption. Table 3 reports the average consumption of resources over 5 runs for ScaLed and SEAL. For all datasets, the average runtime of ScaLed is much lower for larger datasets (e.g., Ecoli and PB), but slightly lower for small datasets (USAir and Celegans). For Ecoli and PB, ScaLed gains speed up of 1.90× and 1.69× over SEAL, while using upto 20× less allocated GPU memory, model size and parameters. The sampled subgraphs in ScaLed are sparser than that of SEAL (compare the number of nodes and edges in Table 3). ScaLed requires 7.86× and 5.17× less edges for Cora and CiteSeer, respectively. This compression can be upto 32.18× (see PB). The results in Tables 2 and Tables 3 confirm  our hypothesis that ScaLed is able to match the performance of SEAL with much less computational overhead. We even witness that ScaLed has outperformed SEAL for NS and Yeast while consuming 1.51× and 6.35× less edges in the sampled enclosing subgraphs. These results suggest that random walk based subgraph sampling is beneficial for the learning without compromising the accuracy. Finally, the results on larger and denser datasets such as Ecoli and PB indicates that the largest computational efficiency gains are achieved by ScaLed on larger and denser datasets.
Results: Hyperparameter Sensitivity Analyses. We intend to understand how the walk length ℎ and the number of walks control the computational overhead in ScaLed during training and inference. Thus, we conduct a sensitivity analysis of these two parameters on all of the attributed and non-attributed datasets. We vary ℎ and while keeping other hyperparameters fixed. Figure  2 reports the average AUC and runtime for all the datasets over 5 runs. 3 The AUC results for all datasets are qualitatively similar where the AUC increases with both values of ℎ and . One can also noticeably observe the runtime slightly increases with both walk length ℎ and the number of walks (with a few exceptions due to statistical noise). But, this slight increment of computational overhead elevates ScaLed's accuracy measure and in the case of USAir, NS, Router, Power, Yeast and Cora pushes it towards and beyond that of SEAL. Interestingly, for datasets such as Ecoli and PB, when reaches 20 and any ℎ, the AUC of ScaLed gets very close to that of SEAL. We also observe that AUC increases much faster with the number of walks in comparison to the walk length ℎ. For ℎ = 2 and = 40, ScaLed has outperformed or is comparable to SEAL in terms of AUC, but gained up to 3× speed up, with the exceptions of NS, Router and Power where the runtime is similar to SEAL. The lack of speedup in those datasets might be explained by their low average degrees. Since these graphs are relatively sparse, the random walks discover the (close-to) exact enclosing subgraphs even  with some potential redundancy by revisiting discovered nodes. Another interesting observation is that for large ℎ (e.g., ℎ = 7), ScaLed has not been able to outperform SEAL drastically. This observation confirms that a node's local neighborhood has more information and we get diminishing returns by moving farther away from the target nodes. One practical conclusion is that for reaching high accuracy and maximum speed up, one is better off keeping the walk length ℎ low but increasing the number of walks .

CONCLUSION AND FUTURE WORKS
Link prediction has emerged as an important task for graph-structured data with applications spanning across multiple domains. Existing state-of-the-art link predicion methods use subgraph representation learning (SGRL), which learns the enriched embedding of the enclosing subgraphs around the pair of nodes. However, SGRL methods are not scalable to large real-world graphs. We proposed ScaLed to overcome this scalability shortcomings, which exploits random walks to sample sparser enclosing subgraphs to reduce the computation overhead. The main idea is to preserve the key structural information of subgraphs with less number of nodes and edges, thus yielding smaller computational graphs for GNNs which in turn reduces the runtime and memory consumption. Our extensive experiments demonstrate ScaLed can match the accuracy measures of the state-of-the-art link prediction models while consuming order of magnitudes less resources. For future work, we plan to explore how to adaptively choose the length of the walks and the number of walks depending on the structural positions of two nodes. Another interesting research direction that could be explored is to apply graph augmentation techniques to the sampled subgraphs in ScaLed to further enhance its learning capabilities.