Inductive Link Prediction for Nodes Having Only Attribute Information

1 Introduction

Link prediction is a fundamental task in graph data analytics [Liben-Nowell and Kleinberg, 2007]. Many real-world applications can benefit from link prediction, such as recommendations, knowledge graph completion, etc [Bhagavatula et al., 2018; Kazemi and Poole, 2018; Xu et al., 2019b]. Graph embedding, which represents the nodes on the graph by low-dimensional vectors, has been proved as an effective approach for link prediction on attributed graphs (e.g., [Kipf and Welling, 2017; Bojchevski and G¨unnemann, 2018]).

Generally, there are two types of link prediction, i.e., transductive and inductive, as shown in Figure 1. Most existing (attributed) graph embedding approaches focus on transductive link prediction, where both nodes are already in the given graph and can be seen during the training process, such as GCN [Kipf and Welling, 2017], GAE [Kipf and Welling, 2016], and SEAL [Zhang and Chen, 2018]. However, many real-world applications need inductive link prediction which requires embeddings to be quickly generated for new nodes with only attribute information (e.g., a new user in a recommender system). SDNE [Wang et al., 2016] and GraphSage [Hamilton et al., 2017] can compute embeddings for new nodes but the edges of nodes are required. G2G [Bojchevski and G¨unnemann, 2018] can perform inductive link prediction for the unseen nodes without local structures. However, it cannot well distinguish the nodes with similar attributes, because this model does not well capture the structure information in the node representations.

∗Corresponding author

In this work, we propose a novel graph embedding model called Dual-Encoder graph embedding with ALignment (DEAL) for inductive link prediction of new nodes with only attribute information. We aim to learn the connections between the nodes' attributes and the graph structure through this model. The model embeds the graph nodes into the vector space, and it can compute an embedding vector for the new query node with only attributes which is compared to another node's embedding for link prediction.

As shown in Figure 2, DEAL has three components: an attribute-oriented encoder Ha, a structure-oriented encoder Hs, and an alignment mechanism. The attribute-oriented encoder Ha maps the nodes' attributes to embeddings in the vector space. Given two linked attributed nodes, the similarity of their embedding vectors computed by Ha is high. Ha is used for computing the embedding vectors of the new nodes with attributes. Hs computes the node embeddings that preserve the structure information. Given two linked nodes, the similarity of their embedding vectors computed by Hs is high. The alignment mechanism aligns the two types of embeddings to build the connections between the attributes and graph structure. The two encoders keep being updated during the training process such that their embeddings produced are aligned. In addition, we use a novel ranking-motivated loss that can be regularized by hyper-parameters, which is not considered in existing ranking loss-based graph embedding models. Although DEAL focuses on inductive link prediction with only attribute information, it can perform transductive link prediction using both structural and attribute information as well. The main contributions of our approach are summarized as follows:

• We design a model DEAL for inductive link prediction of the new nodes with only attribute information given.
• The proposed alignment mechanism builds the connections between attributes and graph structure, and improves the representation ability of node embeddings.
• The experimental results on several real-world datasets show that our proposed model consistently outperforms the state-of-the-art models on both inductive (with at least 6% AP score improvement) as well as transductive link prediction.

2 RelatedWorks

The early studies on link prediction usually have strong assumptions on when links may exist, and they are mainly based on different similarity measures such as the number of common neighbours, Jaccard coefficient, and Adamic-Adar to measure the node proximity [Liben-Nowell and Kleinberg, 2007; Zhou et al., 2009; Zhao et al., 2016]. They assume that the probability of the existence of the link between two nodes increases with their similarity. However, such assumptions may not hold in some real-world networks such as the protein-protein interaction (PPI) networks, because two proteins sharing many common neighbours are actually less likely to interact [Kov´acs et al., 2019].

Recently, researchers have shown an increasing interest in solving the link prediction problem via graph embedding method [Zhang and Chen, 2018]. Graph embedding has been used widely [Gao and Huang, 2018; Gao et al., 2019; Qiu et al., 2019; Xu et al., 2019c], and it aims to map nodes V to l-dimensional vectors Z = {z1 , ..., zn }, zi ∈ Rl . Some graph embedding methods only capture the structural information of the graph, such as the random walk-based graph embedding approaches DeepWalk [Perozzi et al., 2014] and node2vec [Grover and Leskovec, 2016] that adapt the SkipGram model and treat each generated path of nodes as the sequence of words, and SDNE [Wang et al., 2016] that learns node embedding preserving both local and global structures. They do not leverage the attribute information and thus cannot be used for link prediction in attributed graphs.

For link prediction in attributed graphs, most existing studies focus on transductive link prediction, where both nodes are already in the graph. For example, GCN [Kipf and Welling, 2017] requires that the full graph Laplacian is known during training; GAE [Kipf and Welling, 2016] learns the node embeddings with a GCN encoder and an inner product decoder. SEAL [Zhang and Chen, 2018] is another GCNbased framework that solves the link prediction problem using local sub-graphs. To our best knowledge, only G2G [Bojchevski and G¨unnemann, 2018] is able to perform the task of inductive link prediction with only attribute information. It relies on a deep encoder that embeds each node as a Gaussian distribution. However, the output of its encoder is primarily based on the nodes' attributes, and thus it cannot well distinguish the nodes with similar attributes. G2G will embed these nodes nearby in the vector space, because their structure information is not fully utilized.

In our model DEAL, the alignment mechanism aligns the attribute embedding and the structure embedding, and both attribute and structure information can be well captured by the learned node representations, and thus it can achieve better link prediction performance.

3 Problem Statement

We study the problem on an attributed graph G = (V, E, X ), with a node set V = {v1, ..., vn} (n = |V|), an edge set E ⊆ V × V, and an attribute feature matrix X = {x1, ..., xn}, where xi ∈ Rm is the attribute feature vector of node vi (m is the number of attributes in the graph).

Given a graph G as well as a pair of nodes (vp, vq), the link prediction task aims to predict the existence of the link between vp and vq. In transductive link prediction, both nodes vp and vq are already in the graph G (i.e., vp, vq ∈ V and thus they can be seen during the training process). In this work, we focus on the inductive link prediction, where either or both vp and vq are not seen during the training process. During the prediction, only the attribute information of the new nodes is available, i.e., their local structures are unknown.

We propose to utilize the node embedding approach, which embeds the graph nodes into the vector space, to solve this problem. When performing prediction, for a new node vq with its attribute feature vector xq ∈ Rm, the model outputs the node embedding for this node vq from xq and then compares vq's embedding with another node's embedding to predict their relationship.

4 Our Model DEAL

4.1 Overview

Figure 2 illustrates our model DEAL, which consists of three components: two node embedding encoders and one alignment mechanism. We aim to predict the links for new nodes with only attribute information. This requires us to build the connections between the attributes and the links between nodes, which means that we need to compute an embedding vector for a given set of attributes. Our attribute-oriented encoder Ha performs this task. It maps the nodes' attributes to embeddings in the vector space. Given two linked nodes with their attributes, the similarity of their embedding vectors computed by Ha is high.

However, when the nodes attributes are too uninformative or similar, such a single encoder is not sufficient to output useful embeddings to distinguish nodes with similar attributes, because they are all embedded nearby in the vector space. To remedy this issue, we use another structureoriented encoder Hs to compute node embeddings that preserve the graph structure information. As a result, given two linked nodes, the similarity of their embedding vectors computed by Hs is high. Next, we propose an alignment mechanism to align the two types of embeddings. During the training process, the two encoders keep being updated in order to produce node embeddings that are aligned in the vector space. Finally, the connections between the attributes and the links are captured by the two encoders, yielding better embedding vector computation during the link prediction.

4.2 Attribute-oriented Encoder

The attribute-oriented encoder Ha takes a node attribute vector xi (attributes of the node vi) as the input and outputs a node embedding, denoted as zia , i.e., zia = Ha(xi).

There are many neural network choices for learning Ha, and we choose the multilayer perceptron (MLP) with nonlinear activation layer [Goodfellow et al., 2016] in this paper as follows:

with trainable parameters W1a , W2a , b1a and b2a , and the exponential linear unit σ(·) [Clevert et al., 2015]. It is to be noted that the layer number of Ha varies with different datasets. Here, we do not use GCN in Ha, because we observe that aggregating too much information from a node's neighbours may affect the representation ability of the node's attributes for the link prediction task in attributed graphs. As shown in Section 5.5, we tried GCN-like encoders to obtain node embeddings from attributes, and the performance is not as good as using MLP. In addition, without aggregating the information from neighbours, the training process can be speeded up significantly.

4.3 Structure-oriented Encoder

The structure-oriented encoder Hs aims to generate node embeddings that preserve the structural information of the graph without considering the attributes. We expect that the vectors of two linked nodes computed by Hs can have high similarity. To achieve this, we use the one-hot encoding of the nodes IV = {I1, ..., In} (can be regarded as nodes' identifiers [You et al., 2019]) as the input of Hs. Hs can be seen as a function that maps node vi to its node embedding vector zis : zis = Hs(Ii). From the perspective of Occam's razor, we adopt a linear model as the encoder Hs:

where the weight normalization [Salimans and Kingma, 2016] g(·) is employed to reparameterize the parameter Ws. In addition, g(·) is able to accelerate the convergence of stochastic gradient descent optimization. By minimizing the ranking-motivated loss which will be presented in details in Section 4.4, the final embedding Zs is able to capture the structural information.

Note that the encoder Hs can be another node embedding method in DEAL that focuses on learning graph structure with corresponding input, such as GCN with the adjacency matrix as the input. However, we find that using GCN in Hs decreases the link prediction performance, which is shown in Tables 2 and 3 in Section 5.

4.4 Alignment Mechanism andModel Training

We propose an alignment mechanism to align the embeddings generated by the two types of encoders to learn the connections between the node attributes and the graph structure. During the model training, the two encoders keep being updated in order to be able to produce the embeddings that are aligned in the vector space. We first introduce the loss functions we used, and then we describe the proposed alignment mechanism in our model, and we finally present the training algorithm for DEAL.

Loss Function. Learning graph embedding via ranking is based on the ranking-motivated loss, which has been proved to be effective in many studies [Bojchevski and G¨unnemann, 2018; Bhagavatula et al., 2018]. In this paper, we propose a novel mini-batch learning method with a personalized ranking-motivated loss to learn the node embeddings with comprehensive representation performance.

Optimizing a ranking-motivated loss can help to capture the relationships between each pair of training samples. Contrastive loss [Hadsell et al., 2006] is one kind of rankingmotivated loss, and it is originally proposed to solve the dimensionality reduction problem. Given k pairs of samples {(p1, q1), ..., (pk, qk)}, the loss is shown as follows:

where d(·, ·) is a distance function, yi = 1 if the samples pi and qi are deemed similar and yi = 0 otherwise, max(0, ·) is the hinge function, and τ is the margin. The learning objective of Eq. 3 is to map similar input samples to nearby points in the output vector space and map dissimilar samples to distant points.

We have a similar learning objective in our problem that is to map the linked nodes (positive sample) in the graph to points that are close in the output vector space and map the unlinked nodes (negative sample) to points that are far away from each other. However, there is a problem when directly adapting contrastive loss for link prediction. The negative pair-wise samples have different distances in the graph, and thus using a fixed margin for all the negative samples in Eq. 3 is not appropriate, but it is difficult to set proper margins for the negative samples with different distances. Moreover, neither the existing work [Bojchevski and G¨unnemann, 2018; Bhagavatula et al., 2018] nor Eq. 3 considers the regularization in the loss function, which is important and can further improve the prediction performance. Motivated by the above observations, we propose the following loss to be optimized for a given mini-batch of node pair samples B = {(vp1 , vq1 ), ..., (vpk , vqk )} where pi ̸= qi with i ∈ [1, k] (obtained by sampling k pairs of nodes from the graph):

where s(·, ·) is the function to measure the similarity between node embeddings (zpi and zqi ), yi is the link relation label with yi = 1 if vpi and vqi are connected and yi = 0 otherwise, α(·, ·) is a weight function, and φ1(·) and φ2(·) are derived from the function φ(·) with different hyper-parameters. Specifically, there are many choices of s(·, ·), such as dot product, cosine similarity, etc. A high score of s(·, ·) indicates that the nodes are similar, and vice versa. We find that using the cosine similarity have good results in our model.

We use φ1(·) and φ2(·) because the regularization is not considered in Eq. 3. Inspired by that the logistic loss can be seen as a "soft" version of the hinge loss with an infinite margin [LeCun et al., 2006] and is differentiable, we adopt the generalized logisitic loss function φ(x) as follows:

where γ > 0 and b are loss margin parameters that can tune regularization [Masnadi-Shirazi and Vasconcelos, 2015].

α(·, ·) is a weight function to measure the importance of negative samples with different distances. Specifically, we define α(·, ·) as follows:

where β > 0 is a hyper-parameter, and dsp(·, ·) denotes the shortest path distance between a node pair. If node vp cannot reach node vq, dsp(vp, vq) = ∞. This weight aims to help the model pay more attention to the close negative neighbours during the training process.

Alignment Mechanism. By minimizing LB(Zs) and LB(Za), we can lean structure-oriented node embedding Zs and attribute-oriented node embedding Za, respectively. However, if we learn them separately, the two types of embeddings are isolated and cannot well represent the connections between attributes and graph structure. We propose to align the two types of embeddings during the training process and learn the two encoders simultaneously. We design two alignment methods:

1. Tight Alignment (T-align) aims to maximize the similarity between zis and zia for each node vi. Mathematically, the objective of the tight alignment is to minimize

Algorithm 1 The learning process of DEAL

Input: Graph G = (V, E,X); a set of mini-batches B; loss

weight θ and other hyper-parameters;

Output: Node embeddings Zs and Za

• 1: for B ∈ B do
• 2: Zs ←Hs(IV)
• 3: Za ←Ha(X)
• 4: L← θ · [LB(Zs),LB(Za),Lalign(Zs,Za)]
• 5: Update Hs and Ha with stochastic gradient ▽L
• 6: end for
• 7: Update Zs and Za via Hs and Hs
• 8: return Zs and Za

However, the tight method sometimes is too strict during the aligning the two types of embeddings.

2. Loose Alignment (L-align) aims to maximize the similarity between zpi s and zqi a of two linked nodes vpi and vqi , and it adopts the loss function in Eq. 4. Mathematically, the objective of the loose alignment is to minimize

Putting everything all together, the final objective of our model is as below:

• (9)

where θ = [θ1, θ2, θ3] is a hyper-parameter vector to parameterize the weights of different losses.

Training algorithm and prediction. Algorithm 1 summarizes the training process of the proposed model.

To predict whether there is a link between two nodes vp

and vq, we can calculate a score with Zs and Za as follows score(vp, vq) = λ1s(zps , zqs ) +λ2s(zpa , zqa ) +λ3s(zps , zqa ), (10)

where λ = [λ1, λ2, λ3] is another hyper-parameter vector used to give each similarity score a different weight. In inductive link prediction, for a new node vq, zqa is computed by Ha, and λ1 = 0. Our model can also perform transductive link prediction by setting λ1 to a non-zero value.

5 Experiments

5.1 Datasets

For link prediction tasks, we evaluate our proposed model and baselines on four types of real-world datasets, i.e., the coauthorship graph (CS), the protein-protein interactions graph (PPI), co-purchase graphs (Computers and Photo), and citation network datasets (Cora, CiteSeer and PubMed). Details of these datasets are summarised in Table 1.

5.4 Results of Inductive Link Prediction

As GCN-based models cannot aggregate neighbours' information in the inductive link prediction scenario, we compare our proposed model with MLP and G2G, and the experimental results are shown in Table 2. It shows that DEAL significantly outperforms MLP and G2G across all datasets. On the Computers dataset, for instance, DEAL improves AUC and AP scores by 6.12% and 17.98%, respectively. By comparing GCN-DEAL with DEAL, it shows that using GCN-layer as Hs cannot improve the link prediction performance. Also, it is observed that G2G performs worse when the graphs contain a small number of feature dimensions (compared with the number of nodes), such as Computers and Photo. The reason is that the node embedding encoder of G2G solely takes feature matrix X as the input. As an extreme example, when the features of all the nodes are similar, it will be difficult to distinguish different nodes for G2G.

5.5 Results of Transductive Link Prediction

The experimental results of transductive link prediction are summarized in Table 3. The results show that our proposed model DEAL achieves the best performance. For the baselines, G2G performs well on the citation networks and coauthorship graph, which have informative node attributes. It is worth noting that the number of node attributes in PPI is less than 10% of that in other datasets. In the PPI graph, where each node contains limited attribute information, G2G has the worst performance, while SEAL achieves outstanding performance.

Interestingly, the remaining GAE baseline models achieve comparable performance on all the datasets, although they have different methods of aggregating neighbours' information. Moreover, the attention mechanism of GAT does not outperform other GNN layers in this scenario. The reason may be that the GAE variants are insensitive to the different information aggregation methods on the link prediction problem. Compared to the baselines, DEAL is more robust and shows stronger generalization ability on different types of datasets. In addition, the DEAL framework enables GAEs to achieve better performance.

5.6 Comparison of Alignment Methods

To compare different alignment methods in Section 4.4, we conduct both inductive and transductive link prediction experiments on three representative datasets, i.e., Cora, CS, and PubMed. The experimental results (Table 4) show that, on these three datasets, both two alignment methods are effective, and the loose alignment method slightly outperforms the

5.2 Baseline Methods

We compare our model DEAL with MLP and several state-of-the-art graph embedding methods, including SEAL [Zhang and Chen, 2018], G2G [Bojchevski and G¨unnemann, 2018] and GAE [Kipf and Welling, 2016]. In addition, the original GAE takes GCN as the encoder. We also consider other GAE variants, which replace the GCN encoder with GIN [Xu et al., 2019a], GAT [Veliˇckovi´c et al., 2018] and SAGE [Hamilton et al., 2017] respectively. The GAE variants are denoted as their encoder model names.

Moreover, DEAL variants can use different graph embedding models as structure-oriented or attributed-oriented encoders. DEAL denotes the proposed encoders presented in Section 4. A DEAL variant is denoted as X-Y , using the X model as the structure-oriented and the Y model as the attribute-oriented encoder. We select three representative variants. All the DEAL variants aim to minimize Eq. 9. To ensure fairness, we set all models with a similar amount of parameters and train them for the same number of epochs.

5.3 Experimental Setup

We evaluate the proposed model DEAL and baseline models under both inductive and transductive learning settings.

Inductive link prediction. For the inductive case, the nodes in the test set are unseen during the training process. Similar to the dataset split setting of [Bojchevski and G¨unnemann, 2018], we randomly hide 10% nodes and use the edges between them for the test set. The remaining nodes and edges are used for training and validation.

Transductive link prediction. For the transductive case, all the nodes on the graph can be seen during the training. Similar to the dataset split setting of [You et al., 2019], we randomly sample 10%/10% edges and an equal number of non-edges as validation/test set. The remaining non-edges and 80% edges are used as the training set.

The test set performance will be reported when the model achieves the best performance on the validation set. For the experimental results, we report the mean area under the ROC curve (AUC) and the average precision (AP) scores over ten trials with different random seeds and train/validation splits. In all the experiments, the default embedding size is 64. For each training mini-batch, the linked node pairs account for 40%. We tune the hyper-parameters of baseline models and our proposed DEAL with the grid search algorithm on the validation set.

tight alignment method, especially for the inductive link prediction task. The reason is that the loose alignment method places fewer restrictions on the node embedding alignment. The loose one also provides flexibility that the node embed-

dings Za and Zs need by adjusting the hyper-parameters.

5.7 Parameter Analysis

We here conduct experiments to analyse two key parameters, γ (Eq. 5) and α(·, ·) (Eq. 6), in DEAL. Table 5 indicates that the performance can be improved with tuning both of them, and γ plays a more important role than α. The reason is that varying γ is able to regularize the loss (Eq. 4). It is interesting to note that different γ can also change the similarity of node pairs in the embedding space, as shown in Figure 3. It also indicates that the same node pair tends to have a higher similarity score in the structure-oriented embedding space than the one in the attribute-oriented embedding space. The reason is that the node embeddings in Zs are separate, while there are correlations between the ones in Za, especially for those who have certain common attributes.

6 Conclusions

In this work, we propose a novel model DEAL to address the inductive link prediction problem on attributed graphs, where the local structure of the new node is unknown. Different from the typical GCNs that aggregate information from neighbours, DEAL learns comprehensive node representations via two encoders and an alignment mechanism. We have experimentally shown that our proposed model DEAL consistently outperforms state-of-the-art methods. In the future, we will develop more efficient training algorithms, so that our model can process large-scale datasets.

Acknowledgments

Xin Cao is supported by ARC DE190100663. Xike Xie is supported by NSFC (No. 61772492), Jiangsu NSF (No. BK20171240) and the CAS Pioneer Hundred Talents Program. Sibo Wang is supported by Hong Kong RGC ECS Grant (No. 24203419), CUHK Direct Grant (No. 4055114), and NSFC (No. U1936205).