Link Prediction with Contextualized Self-Supervision

Link prediction aims to infer the link existence between pairs of nodes in networks/graphs. Despite their wide application, the success of traditional link prediction algorithms is hindered by three major challenges -- link sparsity, node attribute noise and dynamic changes -- that are faced by many real-world networks. To address these challenges, we propose a Contextualized Self-Supervised Learning (CSSL) framework that fully exploits structural context prediction for link prediction. The proposed CSSL framework learns a link encoder to infer the link existence probability from paired node embeddings, which are constructed via a transformation on node attributes. To generate informative node embeddings for link prediction, structural context prediction is leveraged as a self-supervised learning task to boost the link prediction performance. Two types of structural context are investigated, i.e., context nodes collected from random walks vs. context subgraphs. The CSSL framework can be trained in an end-to-end manner, with the learning of model parameters supervised by both the link prediction and self-supervised learning tasks. The proposed CSSL is a generic and flexible framework in the sense that it can handle both attributed and non-attributed networks, and operate under both transductive and inductive link prediction settings. Extensive experiments and ablation studies on seven real-world benchmark networks demonstrate the superior performance of the proposed self-supervision based link prediction algorithm over state-of-the-art baselines, on different types of networks under both transductive and inductive settings. The proposed CSSL also yields competitive performance in terms of its robustness to node attribute noise and scalability over large-scale networks.


INTRODUCTION
Link prediction is an increasingly important task on graph-structured data with broad applications, such as friend recommendation [1], knowledge graph completion [2], entity resolution [3], and targeted advertising [4], etc. A straightforward solution to link prediction is to calculate some heuristic metrics, such as Common Neighbors [5], Adamic-Adar Index [6] and Katz Index [7], etc., to infer the link existence. Recently, learning based link prediction methods [8], [9] have been proved more effective, as they are able to leverage not only richer structure semantics but also essential node attributes of networks.
Nevertheless, the success of learning based link prediction methods relies heavily on the quality and static property of targeted networks. However, performing link prediction on real-world networks are usually confronted with three key challenges as follows: • Link sparsity. Due to access restrictions or privacy concerns, most of real-world networks are sparse in the sense that the number of unconnected node pairs in an observed network grows quadratically as the number of links grows linearly [10]. Akin to supervised learning for non-relational data, link sparsity incurs insufficient supervision for link prediction, resulting in poor performance.
• Node attribute noise. Real-world networks are often corrupted with node attribute noise, for example, inaccurate user profiles in social networks. This compromises the link prediction accuracy, particularly for learning based methods that highly rely on node attributes, for which incorrect mappings from node attributes to link existence could be learned.
• Dynamic changes. In many cases, networks are not static but dynamically changing with new nodes joining constantly, where no or only few links are observed. For these out-of-sample nodes, the absence or sparsity of their neighborhood structure makes it difficult for many learning based methods to perform link prediction accurately.
As a paradigm of semi-supervised learning, selfsupervised learning (SSL) [11] has been leveraged as an effective strategy in computer vision to favor the supervised learning task through learning high-quality data representations from the unlabeled data. This has motivated us to exploit self-supervision to tackle the link sparsity challenge for link prediction. Although recent attempts have been made to exploit self-supervision on graphs for node classification via node-oriented pretext tasks such as node attribute prediction [12], they are not designed in an effective way to capture structural patterns that are essential for link prediction. To address the node attribute noise challenge, we propose to bridge self-supervised learning with structural context modeling to reinforce link prediction, as structural context has been proved beneficial to node representation learning [13] and attribute selection [14]. To Robust Link Prediction with CSSL. The similar structure context shared by nodes 2 and 3 is leveraged by the embedding encoder to rectify the discrepancy in noisy attributes for accurate link inference (addressing the node attribute noise challenge). effectively predict the links of out-of-sample nodes (addressing the dynamic changes challenge), we design the main link prediction task as an end-to-end learning framework that leverages attributes of paired nodes to infer their link existence probability. With the structural context modeling based self-supervised learning, we can learn the link prediction model as an accurate mapping from node attributes to link existence, with stronger generalization ability for handling out-of-sample nodes. As such, the links of outof-sample nodes can be accurately predicted by applying the trained model to the attributes of out-of-sample nodes, which effectively overcomes the negative impact caused by the absence or sparsity of their neighborhood structure. Based on the above insights, we propose a new contextualized self-supervised learning (CSSL) framework for link prediction. The proposed CSSL framework exploits the power of structural context prediction based selfsupervision to enable context-aware link prediction. Specifically, CSSL formulates a general learning framework that learns a link encoder to infer the link existence probability from paired node embeddings constructed from node attributes. The link encoder predicts the link existence probability through constructing edge embeddings from node embeddings, which effectively capture the attribute difference/similarity between connected nodes. This new formulation enables us to exploit the power of the homophily property [15] for link prediction-the fact that connected node pairs usually have similar attributes. The structural context prediction is modeled as a self-supervised learning task to boost the link prediction performance. We investigate two types of contextualized self-supervised learning tasks-context node prediction and context subgraph prediction, where context nodes and context subgraphs are sampled through short random walks. The proposed CSSL framework can be trained efficiently with stochastic gradient descent by sampling a minibatch of edges at each iteration and thus have a time complexity linear to the number of edges. As CSSL learns a mapping function from node attributes to the link existence, it has the ability to inductively predict the links for out-of-sample nodes, by applying the learned mapping function to the attributes of out-of-sample nodes. Besides, CSSL can be naturally extended to nonattributed networks through using one-hot encodings as node attributes. Fig. 1 provides an illustration to elaborate how the proposed CSSL framework addresses the three aforementioned link prediction challenges. To handle the link sparsity challenge, CSSL trains a probabilistic link prediction model more effectively via contextualized self-supervision. This is accomplished by leveraging the auxiliary link existence evidence conveyed in structural context, which can help train a high-quality embedding encoder to generate informative node embeddings for link prediction. To tackle the attribute noise challenge, CSSL makes the best of structural context to rectify the discrepancy in noisy node attributes for robust link inference. In case of predicting the link existence between nodes 2 and 3, where attributes of node 3 are corrupted with noise, the well-trained embedding encoder allows CSSL to generate similar node embeddings from their common structural context, thereby alleviating the adverse impact of attribute noise on link prediction. To address the dynamic changes challenge, CSSL can inductively infer the link existence between out-of-sample nodes (e.g., node 6) and in-sample nodes (e.g., node 5) from their attributes, without the dependence on their neighborhood structure.
We conduct extensive experiments on seven real-world attributed networks, which show that the proposed CSSL framework outperforms the state-of-the-art methods by large margins, under both transductive and inductive settings. This proves the advantages of CSSL in making the best of network structure and extracting useful information from noisy node attributes towards high-quality link prediction. In addition, we verify its scalability to large-scale networks and its significant advantages over competitive baselines for link prediction on non-attributed networks.
The contribution of this paper is threefold: • We analyze the negative impact of link sparsity, node attribute noise and dynamic changes on link prediction, which motivates the design of structural context prediction based self-supervised learning task for link prediction.

•
We propose the first end-to-end contextualized selfsupervision based link prediction framework that is inductive with the ability to predict the links for both in-sample and out-of-sample nodes and has the flexibility to handle both attributed and nonattributed networks.
• Comprehensive experiments and ablation studies show the superiority of our approach over competitive baselines under both transductive and inductive settings, as well as its robustness to node attribute noise and scalablity to large-scale networks.
The rest of this paper is organized as follows. In Section 2, we review related work on link prediction. The link prediction problem is then formally defined in Section 3. In Section 4, we elaborate our proposed self-supervision based link prediction framework. Extensive experimental results are then reported in Section 5 to evaluate the proposed algorithm. Finally, in Section 6, we conclude this paper.

RELATED WORK
This section briefly reviews two branches of related work on link prediction and self-supervised learning.
However, heuristic methods simply define rigid and onesided structural measures to infer the link existence between node pairs, failing to capture the richer structural context and the essential information conveyed by node attributes. Recently, learning based methods have been proposed to advance link prediction under two categories.

Network embedding based methods
Network embedding based methods first learn node embeddings via network embedding techniques, and then train a classifier to perform link prediction by taking edge embeddings aggregated from node embeddings as features. A series of network embedding algorithms can be used to learn node embeddings. DeepWalk [20] and Node2Vec [21] learn node embeddings by using them to predict random walk context nodes. LINE [22] learns node embeddings by modeling the similarity between connected nodes and the similarity between nodes sharing common neighbors. SDNE [23] and DNGR [24] learn deep node embeddings with a deep auto-encoder neural network. GraphSAGE [25] and Graph Convolutional Networks (GCNs) [26] learn node embeddings through aggregating the attributes/embeddings of neighboring nodes. CANE [27] learns context-aware node embeddings by capturing the attribute attention between connected nodes. MVC-DNE [28] fuses network structure and node attributes into node embeddings with a deep multi-view auto-encoder. Attri2Vec [29] learns node embeddings by projecting node attributes into a structureaware subspace. Most of the existing network embedding algorithms are agnostic to the downstream link prediction task in a way that specific contextual information required for link prediction is not well captured. Moreover, these methods lack the ability to accurately infer embeddings of out-of-sample nodes that have few or no links for performing link prediction inductively.

Link modeling based methods
Link modeling based methods directly learn a model to infer link labels from the inputs of paired nodes with node attributes and/or node neighborhood structure. Various techniques are proposed to devise end-to-end link inference models. Fact [30] predicts the link existence between paired nodes from their attributes by using the bilinear regression model [31]. NARM [32] designs a Bayesian probabilistic generative model to infer links from node attributes. However, Fact and NARM use only node attributes to predict links. VGAE [8] reconstructs network links from node embeddings obtained by graph convolution via Variational Auto-encoder (VAE) [33]. SEAL [9] extracts local subgraphs around nodes and learns a function that maps the extracted subgraphs to link existence. SEAL is claimed to be able to learn heuristics that suit the current network, thus achieving better performance as compared to various heuristics. However, SEAL can only use node attributes as side information, but not in an integrated framework for link prediction. DEAL [34] predicts links by ensembling the link existence probabilities respectively estimated from node attribute-oriented embeddings and structure-oriented embeddings, where the two types of embeddings are aligned by maximizing their consistency. VGAE and SEAL require rich neighborhood structure to predict the links of out-ofsample nodes, whereas Fact, NARM and DEAL predict links from only node attributes, warranting their inductive ability.
In summary, all of these learning based link prediction methods rely merely on a single link existence prediction task for model training. As a consequence, they are ineffective with few training links and noisy node attributes.

Self-supervised Learning
Self-supervised learning (SSL) is a promising learning paradigm for deep neural networks (DNNs) in the domains of computer vision [35], [36] and natural language processing [37], [38]. The central theme of SSL is focused on defining self-supervised pretext tasks to assist DNNs in learning more generalized and robust data representations from the unlabeled data. The training strategies fall into two categories. 1) Pretraining: A DNN model is first pretrained with self-supervised pretext tasks and then finetuned with the target supervision task. 2) Joint training: The self-supervised tasks and the target supervision task are jointly trained with a multi-task learning objective.
Recently, SSL has been explored to boost the performance of machine learning tasks on graph-structured data through defining various pretext tasks [39], [40]. Inspired by image inpainting in computer vision [41], node attribute reconstruction has been utilized to enhance the effectiveness of node embeddings learned by GCNs [12], [40], [42], [43]. On the other hand, node structural properties have also been leveraged to design pretext tasks, such as node degree [40], structural distance between nodes [40], graph partition affiliations of nodes [12], [44], node subgraph motifs [45], and node centrality [46]. The above-mentioned self-supervised pretext tasks are designed with the pipeline of predicting attribute/structure properties from the learned node embeddings, which mainly favor the node classification task. Pioneered by DIG [47], another line of graph self-supervised learning focuses on maximizing the mutual information between node embeddings and the embeddings of their highlevel graph summaries. DIG [47] and MVGRL [48] achieve this objective by contrasting node embeddings and the global graph representation. Extensions are also explored to contrast node embeddings and the embeddings of their surrounding subgraphs [42], [49], [50], [51], [52]. Moreover, the idea has been generalized to improve graph representation learning by contrasting local subgraph embeddings and the global graph representation [53], [54], [55].
To date, the current graph self-supervised learning algorithms are primarily designed to favor node-level and graph-level classification tasks. However, how to leverage self-supervision to facilitate link prediction is still underexplored. To fill this research gap, our work thoroughly analyses the roles of structural context in link-forming mechanisms on graphs and explicitly exploits structural context prediction as self-supervision to boost the link prediction performance.

PROBLEM DEFINITION
Assume we are given an attributed network G = (V, E, X), where V is the set of nodes, E is the set of edges, and X ∈ R m×|V| is node attribute matrix with m being the attribute dimension and the i-th column of X, x i ∈ R m , being the attribute vector of the i-th node v i in V. For the edge set E, we have E = E tr ∪ E te , where E tr and E te are the sets of training and test links, respectively. For transductive link prediction, we assume that all nodes in V, connected by training and test links, are available, so we have the training graph as G tr = (V, E tr , X). In contrast, for inductive link prediction, we assume that only nodes connected by training links are available, forming the set V tr , so we have the training graph as G tr = (V tr , E tr , X tr ), where X tr ∈ R m×|Vtr| stores the attributes of nodes in V tr .
Our objective is to learn a link prediction model on the training graph G tr = (V, E tr , X) or (V tr , E tr , X tr ) by training the link prediction and contextualized self-supervised learning tasks jointly, with sparse training links in E tr and noisy node attributes X/X tr . The main link prediction task aims to train a function f : R m × R m → [0, 1], a mapping from m-dimensional attributes of paired nodes to the link existence probability between them, which can be used to predict the existence of unseen test links in E te . By leveraging the contextualized self-supervision, the trained link prediction model is expected to have the following three properties: 1) the ability to capture the link existence evidence carried by links, node attributes and their interactions; 2) the robustness against link sparsity and node attribute noise; 3) the inductive ability to accurately predict the links of out-of-sample nodes.

CSSL FOR LINK PREDICTION
Existing learning based link prediction approaches [8], [9], [30], [32], [34] mainly focus on minimizing the link classification loss on training links using edge embeddings as features, with the existing edges labeled with 1 and unseen edges labeled with 0. The edge embeddings are constructed from node attributes. However, the existing methods rely heavily on a large quantity of edge labels. On sparse networks, they tend to perform poorly without sufficient edge label supervision. With only a single type of supervision, they are also vulnerable to node attribute noise.
In this section, we present the proposed contextualized self-supervised learning (CSSL) framework for link prediction. In the proposed CSSL framework, node embeddings constructed from node attributes are aggregated into edge embeddings for link prediction. Meanwhile, node embeddings are used to predict the corresponding structural context. Through joint learning, the useful information in sparse links and noisy node attributes can be extracted and fully utilized to improve the link prediction performance.
The architecture of the proposed CSSL framework is shown in Fig. 2. Given a node pair v i , v j , we first transform their node attributes into a low-dimensional latent space to obtain their node embeddings. Using their node embeddings, we simultaneously perform two learning tasks. The first is a link prediction task supervised by the training links, which predicts the link existence probability between nodes v i and v j from the edge embedding aggregated from their node embeddings. The second is to predict the occurrence probability of their structural contexts. The structural context prediction is used in a self-supervised manner to boost the link prediction performance.

Supervised Link Prediction Task
Following traditional learning based algorithms [30], [32], we cast the link prediction problem as a binary classification task on edge embeddings constructed from the attributes of paired nodes. With the carefully designed architecture, the constructed edge embeddings well capture node attribute difference/similarity, exerting the power of the homophily property [15] towards high-quality link prediction. The overall pipeline from node attributes to the link existence likelihood prediction is end-to-end, which can be taken as a generalization of the existing learning based attributedriven link prediction methods [30], [32].
For nodes v i and v j , their node embeddings are respectively constructed from their attribute vectors where Φ(v i ) and Φ(v j ) ∈ R d are the embeddings of node v i and node v j with d dimensions, W emb ∈ R d×m is the weight matrix for constructing node embeddings from node attributes, and σ(·) is the sigmoid function. From node with the following aggregation operators [21]: where where W link ∈ R 1×d is the weight matrix for predicting the link existence probability. The link prediction task aims to minimize the following loss: where (·, ·) is the binary cross entropy loss and y vi,vj ∈ {0, 1} is the ground-truth edge existence label, where 1 indicates nodes v i and v j are connected and 0 indicates otherwise. To enable the model to learn non-linkage patterns, we augment the training set with a set of negative edges E neg with size |E tr |, where each element is the sampled node pair with no observed links between them in G tr , and is labeled with 0.

Contextualized Self-supervised Learning Task
To enable the learned node and edge embeddings to better capture specific contextual information beneficial to link prediction, we incorporate the contextualized selfsupervised learning task to predict structural context. Specifically, we use node embeddings Φ(v i ) and Φ(v j ) to respectively predict their structural contexts. For nodes v i and v j , we respectively sample their structural contexts as where Similarly, the existence probability of structural context where Ψ(c(v j )) is the embedding of structural context c(v j ).
To explore the contextual information, we consider two specific strategies to sample structural contexts c(v i ) and c(v j ) for nodes v i and v j . The details are provided below: • Context/neighboring nodes. Following Deep-Walk [20], we consider nodes occurring in random walk context as structural context. To construct context node embeddings, a possible solution is to perform a transformation on context node attributes similarly using Eq. (1). However, the attribute proximity among context nodes would override the structural proximity between nodes v i and v j reflected by their common neighbors. This could be exacerbated in case of attribute noise. To retain context node identity, as a better way to construct context node embeddings, we perform a linear transformation on one-hot encodings of node IDs, which is equivalent to looking up a learnable embedding table Ψ ∈ R |V|×d with node IDs.
• Context subgraphs. For each node, we also consider its surrounding subgraphs as structural context, as they provide a macroscopic view to measure the structural similarity between nodes. Following [56], we use a short random walk with fixed length starting from each node as a sample of its context subgraph. For a sampled context subgraph G c , its context embedding is constructed by summing the context embeddings of its nodes: For node pair v i , v j , the contextualized self-supervised learning task aims to minimize the following loss: L context vi,vj = (z vi,c(vi) ,ẑ vi,c(vi) ) + (z vj ,c(vj ) ,ẑ vj ,c(vj ) ), (7) where z vi,c(vi) and z vj ,c(vj ) ∈ {0, 1} are the ground-truth labels that respectively indicate whether c(v i ) and c(v j ) are nodes v i 's and v j 's structural contexts, with 1 for true and 0 for false. To allow the contextualized self-supervised Algorithm 1 CSSL for Link Prediction (Joint Training) Input: A given training network Gtr = (V, Etr, X); Output: Link existence probability for each unseen edge vi, vj ∈ V × V \ Etr; 1: Sample a list of positive and negative structural contexts for each node vi ∈ V; 2: Sample a negative edge set Eneg from Gtr; 3: repeat 4: Sample a minibatch of edges { vi 1 , vj 1 , · · · , vi n , vj n } together with their labels {yv i 1 ,v j 1 , · · · , yv in ,v jn } from Etr ∪ Eneg;

5:
for each edge vi k , vj k in the minibatch do 6: Sample a vi k 's structural context c(vi k ) and its label z v i k ,c(v i k ) from vi k 's structural context list; 7: Sample a vj k 's structural context c(vj k ) and its label z v j k ,c(v j k ) from vj k 's structural context list; 8: end for 9: Update the weight matrix W link by descending its stochastic gradient ∇ W link 1 n n k=1 Lv i k ,v j k ; 10: Update the context embedding matrix Ψ by descending its stochastic gradient ∇ Ψ 1 n n k=1 Lv i k ,v j k ; 11: Update the weight matrix W emb by descending its stochastic gradient ∇ W emb 1 n n k=1 Lv i k ,v j k ; 12: until convergence or a fixed number of epochs expire; 13: Infer the link existence for each unseen link vi, vj ∈ V × V \ Etr with the trained parameters using Eq. (3).
learning task to learn non-context patterns, for each sampled positive structual context, we sample k negative contexts with label 0. Negative context nodes are sampled as nodes not occurring in random walk context and negative context subgraphs are sampled as the sets of negative context nodes with the same node number as positive context subgraphs, which are unnecessarily connected in the training graph.

Multi-task Learning
To boost the link prediction task, the contextualized selfsupervised learning task can be leveraged with two training strategies as follows: • Joint Training. We jointly train the supervised link prediction task and the self-supervised learning task by minimizing the joint loss: • Pretraining. We can also first train the weight matrix W emb used for constructing node embeddings by minimizing the contextualized self-supervised learning loss in Eq. (7), and then finetune the model paremeters W emb and W link by minimizing the link prediction loss in Eq. (4).
Algorithm 1 details the training procedure of CSSL with the joint training strategy. In Step 1, we sample a list of positive and negative structural contexts for each node v i ∈ V with the following procedure: we first generate γ random walks with length l starting from node v i ; then nodes that occur following the starting node v i in random walks are collected as its positive context nodes with size γ · (l − 1), or γ positive context subgraphs are sampled for it by assembling its l − 1 context nodes along each random walk; finally we sample k negative context nodes/subgraphs for each positive context node/subgraph,

5:
for each edge vi k , vj k in the minibatch do 6: Sample a vi k 's structural context c(vi k ) and its label Sample a vj k 's structural context c(vj k ) and its label z v j k ,c(v j k ) from vj k 's structural context list; 8: end for 9: Update the context embedding matrix Ψ by descending its stochastic gradient ∇ Ψ and v i 's context node/subgraph list is formed by combining all sampled positive and negative context nodes/subgraphs. In Step 2, the algorithm samples a set of negative edges with size |E tr | that are not observed in G tr . Then, the model is trained with stochastic gradient descent by sampling a minibatch of edges iteratively in Steps 3-12, where at each iteration, before performing stochastic gradient descent, for each sampled edge v i , v j , we respectively sample a context node/subgraph c(v i ) and c(c j ) together with the corresponding context label z vi,c(vi) and z vj ,c(vj ) for nodes v i and v j from their context node/subgraph lists. Finally, the existence of the unobserved links are inferred with the learned model parameters in Step 13. Algorithm 2 details the training procedure of CSSL with the pretraining strategy. The algorithm first samples a list of positive and negative structural contexts for each node in V (Step 1), as well as a set of negative edges with size |E tr | that are not observed in G tr (Step 2), as is done in Algorithm 1. Then, in Steps 3-11, the model is pretrained with stochastic gradient descent by sampling a minibatch of edges and descending their context prediction loss at each iteration. After that, in Steps 12-16, the model is finetuned with the supervised link prediction task, by sampling a minibatch of edges and descending their link classification loss iteratively. Finally, in Step 17, the existence of the unobserved links is inferred with the learned model parameters. Time Complexity. In Algorithm 1, the time complexity of sampling context nodes and context subgraphs is O(|V|). The time complexity of the training process in Steps 3-12 is O(I|E tr |md), where I is the number of epochs and m is the averaged number of non-zero attributes for each node. Hence, the overall time complexity of CSSL with joint training strategy is O(|V|+I|E tr |md). CSSL with pretraining strategy in Algorithm 2 shares the same time complexity.

EXPERIMENTS
In this section, we present experimental results and extensive analyses to verify the effectiveness of the proposed CSSL framework for link prediction. The experiments are conducted on a workstation with an Inter Core i9-9980XE CPU and 32G RAM, without the use of multiprocessing, GPU, or any other accelerators.

Benchmark Datasets and Settings
Seven real-world networks are used in the experiments. The detailed statistics are summarized in Table 1.
• Cora and Citeseer 1 are two citation networks where nodes represent papers and links represent the citations between papers. Each paper is described by a fixed-dimension binary bag-of-words attribute vector, with each dimension indicating the occurrence/absence of each word from a fixed-size dictionary; the value of 1 indicates the corresponding word occurs in the paper, and 0 otherwise.  On Cora, Citeseer, WebKB, Wiki, and Facebook, we perform transductive link prediction experiments. To ensure the training links are sparse (with roughly equal numbers of links and nodes) and prevent generating too many isolated nodes, we randomly split all links into training, validation and test sets, with the ratios as 45%/5%/50%, 67.5%/7.5%/25%, 54%/6%/40%, 9%/1%/90%, and 4.5%/0.5%/95%, respectively. The sizes of the three sets are given in Table 1. Following the standard setting of learning-based link prediction, for each edge, we randomly sample one negative edge, which is not observed in the current network. We repeat the random split ten times to avoid bias in evaluating the link prediction performance. DBLP is used to evaluate the performance of predicting links for out-of-sample nodes in the inductive settings, by using paper publication years to partition in-sample and out-of-sample nodes. We use Google+ to evaluate the scalability of the proposed CSSL framework by extracting subnetworks with varying scales.

Baseline Methods
We compare the proposed CSSL link prediction framework with context/neighboring node prediction (CSSL Neigh) and context subgraph prediction (CSSL Subgraph) with three groups of competitive link prediction baselines: 1) Network embedding based methods that form edge embeddings by aggregating paired node embeddings learned via network embedding, and then convert link prediction into a link classification problem by taking edge embeddings as features. Two traditional attributed network embedding algorithms and two self-supervised based node embedding learning algorithms are compared: • GraphSAGE [25] learns node embeddings through iteratively aggregating the attributes/embeddings of neighboring nodes.
• DIG [47] learns node embeddings with graph convolution and self-supervision that maximizes the mutual information between local node embeddings and the global graph representation.
• GIM [52] learns graph convolution based node embeddings with another self-supervision, i.e., maximizing the consistency between node embeddings and the embeddings of their surrounding subgraphs.
2) Link modeling based methods that directly learn a mapping from attributes and neighborhood structure of paired nodes to the link existence between them, which effectively capture the essential information in both node attributes and network structure for accurate link prediction. Three stateof-the-art methods in this line are considered: • VGAE [8] reconstructs links via node embeddings obtained by graph convolution.
• SEAL [9] learns a mapping from extracted subgraphs including node attributes to the link existence.

3) CSSL ablated variants are also compared to assess the importance of different components of CSSL:
• CSSL Ablated is the ablated variant without the use of self-supervised learning task.
• CSSL Attr is the variant that uses node attribute prediction as the self-supervised learning task. This variant is adapted from attribute prediction based pretext task designed for node classification [12].
For CSSL Neigh, CSSL Subgraph and CSSL Attr, we add the postfix to indicate the training strategies used: " Pretr" for pretraining and " Joint" for joint training.

Transductive Link Prediction Performance Comparison
We first compare the proposed CSSL framework with all baselines under the transductive link prediction setting. Ta-ble 2 reports the link prediction AUC scores of CSSL variants and baselines on Cora, Citeseer, WebKB, Wiki and Facebook. The best and the second best performers are respectively highlighted by bold and underline. On each network, we also conduct paired t-test between the best performer and its competitors. The methods that are significantly worse than the best performer at 0.05 level are marked with • 5 . Table 2 shows that the proposed CSSL framework achieves the best overall link prediction performance on the five networks. CSSL Neigh performs best on Cora and Citeseer, while the best performers on WebKB and Wiki are respectively CSSL Neigh Pretr and CSSL Subgraph Pretr. CSSL Neigh Pretr performs slightly worse than the best performer VGAE on Facebook, while VGAE does not perform well on other four networks. The performance gain of CSSL Neigh and CSSL Subgraph over the counterpart without self-supervision (CSSL Ablated) and the single task based link prediction baselines proves the usefulness of structural context prediction as a self-supervised learning task for link prediction, and also the ability of CSSL to mitigate the negative impact of link sparsity via self-supervision to reinforce link prediction.

Inductive Link Prediction Performance Comparison
In reality, networks are often dynamically changing with new nodes constantly joining, which may have only very few or even no connections to the existing nodes. Therefore, we also compare the proposed CSSL framework with the baseline methods in terms of their abilities to infer links for out-of-sample nodes on DBLP. We split the DBLP network according to a threshold on the years when papers were published. Papers published before the threshold year together with citations between these papers form the insample network, and papers published after the threshold year are considered as out-of-sample nodes, with the threshold year varying from 2000 to 2009. The statistics of the splits are summarized in Table 3. We train the link prediction model on in-sample networks and then predict the links of out-of-sample nodes. Two cases are considered for the inductive link prediction setting: 1) no links are observed connecting to out-of-sample nodes. Only Attri2Vec, DEAL and CSSL variants work in this case, and 2) sparse (10%) links of out-of-sample nodes are observed, including the links connecting to the in-sample training graph and the links among the out-of-sample nodes.
Tables 4-5 report the link prediction performance in the two cases, with the best and the second best performers highlighted by bold and underline, respectively. From Tables 4-5, we can observe that the proposed CSSL variants (CSSL Neigh Joint and CSSL Sugbgraph Joint) consistently achieve the best overall performance in predicting the links for out-of-sample nodes in both two cases, while GraphSAGE, DIG, GMI and SEAL fail to achieve satisfactory performance when out-of-sample nodes have sparse  neighborhood structure. By exploiting structural context prediction based self-supervised learning, our approach can learn the mapping from node attributes to link existence with stronger generalization ability than baseline methods, thus enabling its better inductive capacity.

Robustness against Attribute Noise
To validate the robustness of CSSL against attribute noise, on Citeseer and WebKB, we randomly flip the binary attribute values with a ratio for each node. The rational behind is to simulate some real-world cases in social networks, where users might deliberately hide sensitive profile features or provide false profile metadata to protect their privacy, such as fabricating their gender or providing fake affiliations. We vary the ratio from 5% to 25% by an increment of 5%. Tables 6-7 compare CSSL Neigh and CSSL Subgraph with baselines in terms of different attribute noise ratios on Citeseer and WebKB, where the best and the second best performers are respectively highlighted by bold and underline. As can be seen, CSSL Neigh and CSSL Subgraph consistently outperform other baselines with all attribute noise ratios on Citeseer and WebKB, except for the case with very high noise ratios of 20% and 25% on Citeseer. Still for the highly noise ratio, CSSL Subgraph Joint performs comparably with the best performer SEAL that mainly leverages network structure. SEAL learns a mapping from the local neighborhood subgraph of paired nodes to the link existence with a graph neural network [57], where the mapping is dominated by the convolution over node structural label encoding, so the link prediction performance of SEAL is not largely impacted by the increase in attribute noise levels. On the other hand, CSSL has the capability of extracting useful information from noisy node attributes to alleviate the negative impact of noise, leading to the overall better link prediction performance at different noise ratios.

Algorithm Convergence
We also investigate the convergence property of the proposed CSSL framework on Cora, as a case study. Fig. 3 plots the link prediction performance change of all the proposed CSSL variants (CSSL Neigh Joint, CSSL Neigh Pretr, CSSL Subgraph Joint and CSSL Subgraph Pretr), when the number of epochs used for joint training or finetuning after pretraining varies from 1 to 500. We can see that, the performance of all CSSL variants converges fast after no more than 25 epochs, and then retains at a stable level.

Algorithm Scalability
We also study the scalability of the proposed CSSL with an increase of network scale, by evaluating the CPU time consumed by running CSSL Neigh Joint with 10 epochs on the sampled Google+ subnetworks of different scales. Fig. 4 plots the change of the running time as network size (the number of edges) increases from 5000 to 10 7 , with both axes in logarithm scale. As we can see, the proposed CSSL scales almost linearly with network size |E tr |.

Comparison of Aggregation Operators
As reported, the proposed CSSL uses Weighted-L2 as the aggregation operator to form edge embeddings from paired node embeddings. Now, we compare its link prediction performance using Weighted-L2 against the other three operators, namely, Average, Hadamard and Weighted-L1. Table 8 compares the performance of CSSL variants using different aggregation operators on Cora. For each variant, the result of the best operator is highlighted by bold and paired ttest is used to compare it with other operators. In general, Weighted-L1 and Weighted-L2 deliver the best link prediction performance, while Hadamard performs better than Average. According to the homophily phenomenon, node attribute similarity/difference is the key evidence for predicting the link existence. As Weighted-L1 and Weighted-L2 are better at characterizing node attribute difference, this translates to their superior link prediction performance.

Parameter Sensitivity
We also study the sensitivity of CSSL variants with respect to four important parameters, including the dimension d of node/edge embeddings, the number of random walks γ starting from each node, the random walk length l for sampling structural context, and the number of sampled negative context nodes/subgraphs k for each positive context. We take turns to fix any three parameters as default values and test the sensitivity of CSSL variants to the remaining one. Fig. 5 shows how CSSL variants perform on Cora by varying the four parameters. Compared to other variants, CSSL Neigh Joint is more sensitive to embedding dimension. Yet, all CSSL variants tend to have stable performance with respect to varying values of these parameters.

Generalization to Non-Attributed Networks
So far, we have validated the efficacy of the proposed CSSL framework on attributed networks. As a flexible learning framework, CSSL is also capable of handling non-attributed networks where node attributes are unavailable. In this case, CSSL takes one-hot node representations as node attributes to infer the link existence. The baseline methods DIG, GIM, VGAE, SEAL, and DEAL use the same one-hot representation scheme to construct node features. Furthermore, we compare CSSL variants with three competitive embedding based methods that use only network structure: Node2Vec [21], the first-and second-order LINE (LINE1 and LINE2) [22], and four heuristics-based methods with their definitions provided in Table 9. Table 10 reports the link prediction results on five networks without node attributes, with the best and the second best performers highlighted by bold and underline, respectively. Clearly, as compared to

Common Neighbors
incorporated for all methods except for SEAL. As SEAL does not well leverage node attributes for link prediction, it even achieves better performance on Cora, Citeseer, WebKB and Wiki at the absence of node attributes.
To fully exploit network structure, for CSSL Neigh and CSSL Subgraph, we respectively set the number of random walks starting from per node and the random walk length to 80 and 20, and we use Weighted-L1 aggregation operator to form edge embeddings for all CSSL variants. For Node2Vec, we start 10 random walks with length 80 from each node and collect context nodes with window size 10, with the default random walk setting p = q = 1 used. Default parameters are used to train LINE.
Note that even at the absence of node attributes, CSSL Neigh and CSSL Subgraph still markedly outperform other baselines, with the CSSL Subgraph Pretr variant yielding the best overall performance. Specially, CSSL Neigh and CSSL Subgraph outperform CSSL Ablated without self-supervision by a large margin. Again, this validates the effectiveness of structural context prediction in boosting link prediction, as a self-supervised learning task, especially for the case without node attributes.
Apart from CSSL variants, SEAL generally achieves the second best performance, far superior to other rigid heuristics-based methods. This proves the efficacy of SEAL in extracting useful node neighborhood structure to boost the link prediction performance. Among network embedding based methods, DeepWalk achieves the best performance, which attributes to its special ability in exploring high-order neighborhood structure. As a whole, traditional heuristics-based methods do not exhibit competitive results as compared to other advanced baselines.
On non-attributed networks, the pretraining based CSSL variants overall perform better than the joint training based counterparts, because the pretraining strategy helps better learn informative node structure embeddings, which are essential for link prediction. In comparison, on attributed networks, with the use of informative node attributes to construct node embeddings, the pretraining and joint training variants perform comparably.

CONCLUSION
In this paper, we proposed a novel contextualized selfsupervised learning framework for link prediction, which is achieved by predicting the existence of structural context. The proposed CSSL framework is generic, with the ability to leverage various types of structural context, the capacity to predict links for both in-sample and out-ofsample nodes, and the flexibility to handle both attributed and non-attributed networks. The proposed link prediction framework scales linearly with the number of edges, which endows it with the potential to handle large-scale networks. Through the proposed self-supervised learning task, the CSSL framework makes the best of useful information in sparse links and noisy node attributes to perform link prediction. Comprehensive experiments on seven real-world networks demonstrated that the proposed CSSL framework achieves the state-of-the-art link prediction performance, on the transductive/inductive, attributed/non-attributed, and attribute-clean/attribute-noisy settings.