SPINE: Structural Identity Preserved Inductive Network Embedding

1 Introduction

Network embedding has been successfully applied in a wide variety of network-based machine learning tasks, such as node classification, link prediction, and community detection, etc [Cai et al., 2017; Kipf and Welling, 2016]. Different to the primitive network representation, which suffers from overwhelming high dimensionality and sparsity, network embedding aims to learn low-dimensional continuous latent representations of nodes on a network while preserving the structure and the inherent properties of the network, which can then be exploited effectively in downstream tasks.

Most existing network embedding methods approximate local proximities via random walks or specific objective functions, followed by various machine learning algorithms with specific objective functions to learn embeddings [Perozzi et al., 2014; Grover and Leskovec, 2016]. Specifically, the local proximity of a node is approximated with the routine of learning the embedding vector of a node by predicting its neighborhood, inspired by the word embedding principle [Mikolov et al., 2013a; Mikolov et al., 2013b] which learns the embedding vector of a word by predicting its context.

∗Corresponding Author

However, there still exist some potential issues that need further concerns. On the one hand, local proximity preserved methods generally do not model nodes far from each other in practice. Meanwhile, in real-world network mining tasks, nodes that are far apart but close in structural identity, or in other words, take similar roles, should perform similarly on specific tasks. Figure 1 shows an example of how nodes with different roles perform in the information diffusion processes on social networks. Nodes with different colors indicate different roles in social networks, i.e., structural hole spanners (red nodes), opinion leaders (yellow nodes) and ordinary users (blue nodes) respectively [Lou and Tang, 2013; Yang et al., 2015b]. Intuitively, nodes with same roles behave similarly even with a large distance (yellow nodes in Figure 1), which is the property that should be preserved in the embedding space. In the meantime, the local proximity of a node is also crucial in network embedding. For example in Figure 1, nodes in the same community should be clustered tightly in the embedding space. Therefore, a desirable network embedding method should preserve the local proximity and the global structural identity of a node simultaneously to represent the node precisely. Unfortunately, most existing methods fail to consider the local and global structural information at the same time. In principle, it is challenging to interactively integrate the two kinds of information to obtain comprehensive embeddings rather than a trivial linear combination.

On the other hand, most existing network embedding approaches are transductive. To be specific, embeddings are learned on a fixed network, and cannot be directly applied to new joined nodes or other networks. In contrast, inductive methods which are able to generalize to unseen nodes or totally new networks are extensively required in real-world applications, e.g., social recommendation for new users, classification of protein functions in various protein-protein interaction graphs, etc. Unfortunately, traditional network embedding principles such as random walk and matrix factorization are impracticable for unseen nodes or networks, which makes inductive network embedding much more challenging than transductive problems.

In this paper, we propose SPINE, an inductive network embedding framework which jointly preserves local proximities and structural identities of nodes. We show that structural similarities between node pairs can be represented by a highorder proximity of the network known as Rooted PageRank (RPR) [Liben-Nowell and Kleinberg, 2007], and by assigning each node a structural feature vector based on RPR, we can encode structural proximities between nodes by measuring the similarities of their structural features. To construct an inductive framework, we learn an embedding generator rather than directly optimizing a unique embedding for each node, through which local proximities are integrated. To further encode structural identities, we propose a biased SkipGram Negative Sampling (SGNS) approach with a novel positive sampling strategy guided by structural similarities between nodes. Furthermore, the objective function of SPINE is carefully designed to enhance the structural information contained in the embedding generator.

2 SPINE

In this section, we propose Structural Identity Preserved Inductive Network Embedding (SPINE), a novel inductive approach for unsupervised network embedding, which consists of three components: structural feature generation, embedding generation and biased SGNS optimization.

Problem Definition: Given an undirected network G = {V,E,F}, in which a set of nodes V are connected by a set of edges E, and F ∈ R|V |×f is the content matrix of nodes. The adjacency matrix is A where Ai,j = wi,j is the edge weight between node vi and vj, and we denote the corresponding transition matrix as P, where Pi,j = wi,j ∑|V | k=1 wi,k represents the transition probability between node vi and vj. Our goal is to learn E ∈ R|V |×d , where d is a small number of latent dimensions. These low-dimensional representations should well preserve the structural properties of G, including local proximities and structural identities, which can be evaluated with downstream tasks such as node classification.

2.1 Rooted PageRank and Structural Identity

We start with theoretical preliminaries of our structural feature generation algorithm. Here we introduce a well-known high-order proximity of a network named Rooted PageRank (RPR) [Liben-Nowell and Kleinberg, 2007], defined as SRPR = (1 - βRPR)(I - βRPRP)-1 , where βRPR ∈ (0, 1) is the probability of the current node randomly walking to a neighbor rather than jumping back to the start node. The (i, j)-th entry of SRPR is the probability that a random walk from node vi will stop at vj in the steady state, which can be used as an indicator of the node-to-node proximity. Therefore, we can use the i-th row of SRPR , denoted as SRPR i , to represent the global structural information of node vi. We can further rewrite SRPR i in a recursive manner as:

where gi is the index vector of node vi whose i-th element is 1 while others are 0.

Next, we are going to verify that SRPR i is able to represent the structural identity of node vi. We first define the complete structural property [Batagelj et al., 1992] of a node as:

Definition 1. A node property t : V → R is complete structural if for any automorphism ϕ of every node vi ∈ V , it always satisfies:

Examples of complete structural properties include t(vi) = degree of node vi, t(vi) = number of nodes at distance k from vi (k-hop neighbors), t(vi) = the centrality of vi, etc. [Batagelj et al., 1992].

Then the following theorem can be directly derived from [Batagelj et al., 1992]:

Theorem 1. Given a structural description of node vi defined by a set of complete structural node properties as:

where Ti is an n dimensional vector, and n > 0 is the number of chosen properties. Let d(·, ·) denote standard dissimilarities between vectors, and vi ≡ vj indicate node vi and vj have equal structural identity, then for ∀vi, vj ∈ V :

From Theorem 1, we can conclude that the structural identities between nodes can be measured through properly designed structural vectors. Next we are going to show that SRPR i actually represents a complete structural property.

Following the examples in Definition 1, the centrality of vi can be regarded as a complete node property of vi. There are multiple ways to measure the centrality of a node, while the original PageRank [Brin and Page, 2012] is exactly a variant of eigenvector centrality. At each iteration, the PageRank value πi of node vi is updated as in [Langville and Meyer, 2011]:

and M is the Google matrix defined as:

where gi = ( 1 |V | , · · · , 1 |V | )|V | and 1 = (1, · · · , 1)|V |. According to Equation (1), as a variant of PageRank, the only difference between SRPR i and the original PageRank is the choice of gi. Therefore, the target matrix of Rooted PageRank can be written as:

where I is the identity matrix. Thus SRPR i is the leading left hand eigenvector of M RPR i , i.e., SRPR i satisfies: (SRPR i )T = (SRPR i )T MRPR i . As a consequence, SRPR i is also a variant of eigenvector centrality, thus can be further regarded as a complete structural property to represent the structural identity of vi, i.e., Ti = SRPR i .

Algorithm 1 Rooted random walk sampling

• Input: the graph G, the present node vi, the continuation probability βRPR ∈ (0, 1), hyper-parameters k, m, l Output: the structural feature vector Ti of vi 1: Initialize a counter Ci ∈ R|V | 2: repeat 3: Ps = RootedRandomWalk(G, vi, l, βRPR) 4: for vj in Ps do 5: Ci[j] ←Ci[j] +1 6: end for 7: until m times 8: Ci ←Sort Ci in a descending order 9: Ti ←The first k elements of Ci 10: return Ti ←Ti/sum(Ti)

2.2 Structural Feature Generation

In this section we first state our motivation of choosing SRPR i as the structural identity instead of others, based on which the structural feature generation method is introduced.

To construct an inductive method, we expect the length of the structural description of a node is independent of the total number of nodes |V | and fixed at k. In this paper, we use the top k values of SRPR i as the structural description of vi. Compared with other high-order proximities or node properties (e.g., the original PageRank), RPR captures the global structural information of the network, while being tailored to encode the local structural information of root nodes according to the definition, and thus can better represent the importance of neighbors at various distances to the present node [Haveliwala, 2002]. Moreover, it has been theoretically and empirically proven [Litvak et al., 2007] that in a network with power-law degrees, the RPR values also follow a powerlaw distribution. Therefore, the largest k RPR values are able to represent the structural information of a node with a suitably chosen k.

When calculating SRPR i , considering the inductive prerequisite, the transition matrix P which encodes the structure of the network may be unavailable. Alternatively, we approximate SRPR i from the local structure around vi through a Monte Carlo approximation. The complete procedure is summarized in Algorithm 1, where m and l indicate the number of repeats and the length per random walk respectively, and k controls the length of the structural feature vector. The largest k values of SRPR i are taken as the structural description of vi, denoted as Ti in the rest of this paper.

2.3 Embedding Generation

To construct an inductive network embedding framework, we generate embeddings instead of directly optimizing the embedding matrix, through which the structural information and the content information of networks can be jointly incorporated.

As stated above, the k values in Ti indicate k largest structural proximities between vi and nodes co-occurring with vi in rooted random walks. We denote the content matrix of the corresponding k nodes as F k i ∈ Rk×f , which is constructed row by row according to the same order of RPR values in Ti. Given the structural features Ti and node content F k i , we propose an embedding generation method for vi.

Specifically, we first employ a multilayer perceptron (MLP) to map nodes from the content space to the embedding space, then compute a linear combination of the k vectors with respect to the corresponding weights in Ti. Formally, denote the dimensionality of embeddings as d, the weight matrix of the MLP is WM ∈ Rf×d , then the embedding generation process can be written as:

where F k i,j ∈ Rf is the j-th row of F k i , σ is the non-linear activation function, and ei ∈ Rd is the embedding vector of node vi.

2.4 Biased SGNS

The Skip-Gram Negative Sampling (SGNS) model is widely used in representation learning, which is based on the principle of learning the embedding vector of a word/node by predicting its neighbors. More formally, given an embedding vector ei, SGNS is minimizing the objective function as:

where σ(·) is the sigmoid function and K controls the negative sampling number. vp and vn are positive and negative nodes of vi respectively, while ep and en are the corresponding embedding vectors. Technically, negative nodes are sampled from a distribution Pn, and for most network embedding methods, positive nodes are defined as nodes that co-occur with vi in a fixed-size window in random walk sequences.

In SPINE, to encourage the similarity of embeddings to jointly encode the similarity in terms of structural identities and local proximities simultaneously, we design a novel biased positive sampling strategy based on the structural features generated from Algorithm 1. The complete procedure is illustrated in Algorithm 2. Specifically, we define a structural rate α ∈ (0, 1) to control the ratio of structural sampling and local proximity sampling. With probability α, a positive sample of vi is sampled according to the similarities between their structural features (starting from line 2). Otherwise, the positive node is sampled from nodes that co-occur near vi on trivial random walks (starting from line 9), which is preprocessed and stored in Li. The similarity metric in line 4 can be chosen from Euclidean distance, cosine similarity, Dynamic Time Warping (DTW) [Salvador and Chan, 2007], etc. In our experiments, we use DTW which is designed to compare ordered sequences as the similarity metric.

The structural sampling paradigm alleviates the limitation of distance. In practice, it is redundant to compute the structural similarity between vi and all the other nodes, since nodes with completely different local structures are nearly impossible to be sampled as positive pairs through structural sampling. Intuitively, nodes with similar degrees are likely to have similar local structures. Based on this intuition, we reduce the redundancy by only considering nodes which have similar degrees with the present node vi. Specifically, given an ordered list of node degrees, we choose the candidates for structural sampling by taking O(log |V |) nodes in each side from the location of vi. As a consequence, the time complexity of structural sampling for each node is reduced from O(|V |) to O(log |V |).

2.5 Learning and Optimization

We introduce the biased SGNS based objective function of our framework in this section. We propose two types of embeddings for each node vi ∈ V , i.e., a content generated embedding ei as defined in Equation (4), and a structure based embedding si which is the i-th row of an auxiliary embedding matrix WS ∈ R|V |×d . In real-world network-based datasets, the content of nodes is likely to be extremely sparse and weaken the structural information incorporated during the generation process of ei. Therefore we employ a direct interaction between ei and si to strengthen the structural information contained in the learned embeddings.

Formally, given the present node vi and its positive sample vj, which is sampled according to Algorithm 2, the pairwise objective function of SPINE can be written as:

where λ1 and λ2 control weights of different parts, and J(·|·) denotes the pairwise SGNS between two embeddings defined in Equation (5). Intuitively, the generator and the auxiliary embedding matrix should be well trained through their single loss as well as obtaining each other's information through the interaction loss, where λ1 and λ2 determine which one is the primary part.

The structure based embeddings WS and the parameters WM of the MLP constitute all the parameters to be learned in our framework. The final objective of our framework is:

By optimizing the above objective function, the embedding generator is supposed to contain the content information and the structural information as well as local proximities and structural identities simultaneously. Therefore, during inference, we drop the auxiliary embedding matrix WS and only keep the trained embedding generator. In the sequel, embeddings of unseen nodes can be generated by first constructing structural features via Algorithm 1 and then following the paradigm described in Section 2.3.

3 Experiments

3.1 Experimental Setup

We test the proposed model on four benchmark datasets to measure its performance on real-world tasks, and one small scale social network to validate the structural identity preserved in the learned embeddings. For the node classification task, we test our method on Citation Networks [Yang et al., 2016], where nodes and edges represent papers and citations respectively. To test the performance of SPINE while generalizing across networks, we further include PPI [Stark et al., 2006], which consists of multiple networks corresponding to different human tissues. To measure the structural identity preserved in embeddings, we test SPINE on a subset of Facebook dataset [Leskovec and Krevl, 2014], denoted as FB-686, in which nodes and links represent users and their connections, and each user is described by a binary vector.

As for the baselines, we consider unsupervised network embedding methods including node2vec [Grover and Leskovec, 2016], struc2vec [Ribeiro et al., 2017] and their variants. Considering that node2vec and struc2vec are designed to preserve the local proximity and the structural identity respectively, we concatenate the corresponding learned embeddings to form a new baseline, denoted as n+s, to illustrate the superiority of SPINE over the linear combination of the two proximities. In addition, n+s+f denotes the content-incorporated variant of n+s. We also compare with SDNE [Wang et al., 2016] and HOPE with RPR matrix [Ou et al., 2016] to test the performance of our inductive Rooted PageRank approximation. On the other hand, in addition to transductive methods, we also consider the unsupervised variant of Graphsage [Hamilton et al., 2017], an inductive network embedding method which jointly leverages structural and content information. We also report the performance of the state-of-the-art supervised inductive node classification method GAT [Veliˇckovi´c et al., 2017]. Random and raw feature results are also included as baselines in this setting.

For our method, we use SPINE and SPINE-p to indicate the variants with WS randomly initialized and pretrained with node2vec respectively. To make predictions based on the embeddings learned by unsupervised models, we use one-vs-rest logistic regression as the downstream classifier. For all the methods, the dimensionality of embeddings is set to 2001 .

3.2 Node Classification

We first evaluate the performance of SPINE on node classification, a common network mining task. Specifically, we conduct the experiments in both transductive and inductive settings. For the transductive setting, we use the same scheme of training/test partition provided by Yang et al. [2016]. As for the inductive setting, on citation networks, we randomly remove 20%, 40%, 60% and 80% nodes and the corresponding edges, these nodes are then treated as test nodes with the remaining network as the training data. Meanwhile on the PPI network, we follow the same dataset splitting strategy as in [Hamilton et al., 2017], i.e., 20 networks for training, 2 for validation and 2 for testing, where the validation and testing networks remain unseen during training. For both settings we repeat the process 10 times and report the mean score.

Results in the transductive setting are reported in Table 1. We can observe that SPINE outperforms all unsupervised embedding methods, and performs comparably with the state-ofthe-art supervised framework GAT. In addition, n+s performs worse than node2vec, which implies that a simple linear combination of local proximity preserved and structural identity preserved embeddings is incapable of generating a meaningful representation that effectively integrates the two components. The superiority of SPINE over SDNE and HOPE indicates the efficacy of the inductive RPR approximation algorithm as well as the joint consideration of local proximity and structural identity. SPINE also outperforms the contentaugmented variant n+s+f, which shows that the content aggregation method we propose can better consolidate the content and structure information. Furthermore, the comparison between the two variants of SPINE indicates that while the basic model of SPINE already achieves a competitive performance, we can further enhance the model with initializations of WS that are well pretrained by focusing only on local proximity, which also justifies the effectiveness of the paradigm of interactive integration proposed in Section 2.5.

As for the comparison on training and test runtime, results are shown in Figure 2. Obviously, SPINE is more efficient in time complexity, especially in the inference stage. In addition, SPINE is also more compact in space complexity, as the parameter scale of SPINE during inference is O(fd), compared to O(fd + d2 ) and O((f + KC)d) for Graphsage and GAT with two layers respectively, where K is the number of attention heads and C is the number of classes.

1 Code is avaliable at https://github.com/lemmonation/spine

Results in the inductive setting are reported in Table 2 and Figure 3. Note that in this setting we use all the remaining nodes as training data during classification, thus the results are generally larger than that under the transductive setting. One can observe that SPINE outperforms all the baselines, indicating the generalization capability of the embedding generator learned by optimizing our carefully designed objective function. In addition, with the increasing node removal rate which leads to greater loss of local proximities, Graphsage can perform worse than raw features, indicating the limitation of the methods that only preserve local proximities. In contrast, SPINE alleviates the sparsity of local information by incorporating structural identities.

3.3 Structural Identity

We proceed to investigate the structural identity on the FB686 dataset here. We consider the transductive setting here, and the results under inductive setting can be found in the supplementary material. Specifically, for the original network, we construct a mirror network and relabel the nodes, and consider the union of two networks as the input. As a consequence, node pairs between original nodes and their mirror nodes are obviously structurally equivalent, thus should be projected close in the embeddings space. We then evaluate the Euclidean distance distribution between embeddings of the mirror node pairs and all the node pairs connected by edges, denoted as Pm and Pa respectively. Intuitively, if embeddings successfully preserve structural identities of nodes, E[Pm] should be much smaller than E[Pa].

Results of SPINE and struc2vec with respect to the two distributions are shown in Figure 4. Obviously, compared to struc2vec, embeddings learned by SPINE yield smaller distances between both mirrored node pairs and connected node pairs, indicating the structural identity and local proximity are jointly preserved better. In addition, the ratio between E[Pa] and E[Pm] is 13.40 and 5.72 for SPINE and struc2vec respectively, which means SPINE distinguishes the two proximities more clearly.

Further to test the robustness of SPINE to edge removal and changing content, we randomly sample two new networks from the original FB-686 network. Specifically, we preserve each edge in the original network with probability s, and randomly exchange a 1's location with another 0's location in each node's content vector. Consequently, from the view of structure, the probability for an original edge contained both in the two generated networks is s2 , and smaller s indicates less structure correlation between the two generated networks. From the view of content, mirrored nodes are nearly impossible to have identical content due to the sparsity of content vectors. As can be observed in Figure 5, the ratio between E[Pa] and E[Pm] is not significantly affected by the degree of structure perturbation s, which indicates that SPINE can robustly distinguish and preserve structural identity as well as local proximity even with severe perturbations.

4 RelatedWork

Most network embedding methods consider to preserve local proximity between nodes with frameworks based on random walk [Perozzi et al., 2014; Grover and Leskovec, 2016], skip-gram [Tang et al., 2015; Cao et al., 2015], matrix factorization [Yang et al., 2015a; Guo et al., 2017] and deep learning [Wang et al., 2016; Gao and Huang, 2018] respectively. However, it is worth noting that few of the existing works consider the structural identity between nodes, and fail to handle proximities between nodes at distances. Struc2vec [Ribeiro et al., 2017] preserves the structural identity by constructing a multi-layer complete graph and execute random walk on it. HOPE [Ou et al., 2016] captures structural identity through factorizing a global Rooted PageRank matrix. However, while preserving the structural identity, they ignore the basic local proximities of nodes, which limits its applicability on real-world network mining tasks. Similar problems also occur in two recent methods [Tu et al., 2018; Zhang et al., 2018]. SDNE [Wang et al., 2016], a deep learning based method, is only able to take the first- and secondorder proximities into account. Furthermore, most of the methods mentioned above are transductive. Inductive methods [Hamilton et al., 2017; Veliˇckovi´c et al., 2017] tackles this challenge by recursively training a set of aggregators for each node to integrate its neighbors' content as the embedding of the current node in every iteration. As nodes at the k-th iteration contain the structural information from their neighbors within k hops, they cannot deal with nodes at arbitrary distances unless with sufficient iterations, which is costly for real-world tasks.

5 Conclusion

In this paper, we propose SPINE, a network embedding approach which is able to jointly preserve structural identities and local proximities of nodes while being generalized to unseen nodes or networks. We assign a structural feature vector to each node based on Rooted PageRank, and we learn an embedding generator leveraging the structural features of each node to incorporate the structural and content information of nearby nodes. In addition, we propose a biased SGNS algorithm with a novel positive sampling procedure, based on which a carefully designed objective function is proposed to enhance the structural information contained in the embedding generator. Extensive experiments demonstrate the superiority of SPINE over the state-of-art baselines on both transductive and inductive tasks. In future work, we are interested in introducing structural identity to other network-based tasks such as social recommendation.

Acknowledgements

This research was supported by the National Natural Science Foundation of China (No. 61673364, No. 91746301) and the Fundamental Research Funds for the Central Universities (WK2150110008).