Network Embedding under Partial Monitoring for Evolving Networks

1 Introduction

Many things are organized in the form of networks, and we can get a wealth of information from the structure of networks. Due to this fact, network embedding, which can be regarded as a kind of representation learning specific to networks, is attracting more and more attention from researchers in many fields. The target of network embedding is to embed the nodes of the networks into a continuous low-dimensional latent space, i.e., to learn the real-valued low-dimensional vector representations for the nodes based on the structure of the networks, and the learned vector representations of the nodes can be regarded as their features used for many downstream tasks, such as link prediction.

Various network embedding models have been developed, and the key idea of most of them is extracting one or more kinds of information, or more specifically the proximities among the nodes, from the network structure to learn the vector representations of the nodes so that the learned representations can preserve the extracted information. For example, DeepWalk [Perozzi et al., 2014] and Node2vec [Grover and Leskovec, 2016] employ random walk to transform the network structure into sequences of nodes, and borrows the idea of Word2vec [Mikolov et al., 2013] to learn the node representations. So the proximities among the nodes in the same sliding window can be preserved by the same way as Word2vec. LINE [Tang et al., 2015] defines two kinds of proximities specifically (1st and 2nd order proximities) and adopts asynchronous stochastic gradient to learn node representations for these two kinds of proximities separately. Different network embedding models focus on different kinds of proximities and use different methods to learn distributed representations for the nodes. To some extent, one proximity results in one network embedding algorithm. Almost all these classical network embedding algorithms can only be employed on static networks. However, the real world networks are usually not static. They usually have two characteristics. First, they are usually dynamic and evolve all the time. In addition to this obvious characteristic, we find in practice that some networks change without notifying us, so we need to query the nodes to learn about the latest changes of the network structure. For example, in a web network, we have to crawl the web pages to discover their outgoing links and their changes [Bahmani et al., 2012]. In addition, many large network platforms adopt log systems to record the behavior of the nodes. If we want to know whether two nodes established a relationship, we have to check the behavior logs of these two nodes. Unfortunately, as pointed by [Anagnostopoulos et al., 2012], due to the great cost of the query, it is often impractical to query all the nodes at every moment. In other words, we can only probe part of the nodes to update the image of the network structure.

To perform network embedding on evolving networks, [Zhu et al., 2016] proposes BCGD, which adopts Adjacency Proximity, a kind of proximity we will introduce in Section 3.3, to learn the vector representations of the nodes. However, there are two shortages for BCGD. First, it can only employ Adjacency Proximity, but not other kinds of proximities. More importantly, it is built on a graph sequence < Gt0 , Gt1 , · · · >, in which each G represents a structure of the network at a time stamp, and it assumes that we can get the true network structure all the time. However, this assumption cannot hold for all the dynamic networks because of the second characteristic of real world networks we introduced above. So in this paper, we try to solve this problem, which is ignored by most network embedding algorithms but very important in practice. We propose CPNE (Credit Probing Network Embedding) to learn the vector representations of the nodes on evolving networks in a partial monitoring mode, that means we can only probe part of the nodes in a budget to get the information we need to perform network embedding, which is more in line with the real situation.

First, we employ a framework based on matrix factorization to incorporate network embedding models. On this basis, we propose our algorithm to perform network embedding under partial monitoring on evolving networks. We give this algorithm an error bound by careful theoretical analysis. At last, we evaluate our model on some real world datasets from two aspects. First we test the ability of our model to approach the potential optimal embedding values. Then we test the performance of our model on a practical problem, namely link prediction. All the experiments show great advantages of our algorithm over the baseline models.

2 RelatedWorks

There are two lines of research mostly related to our work, i.e., network embedding and dynamic network computation.

Network embedding. Different network embedding models focus on different proximities. [Cao et al., 2015] learns node representations by employing the k-step transition probabilities among the nodes. [Qiu et al., 2017] tries to find the closed forms for the proximities used in some network embedding models. [Tang and Liu, 2009; Zheng et al., 2016; Tu et al., 2016; Wang et al., 2017] utilize the proximity among the nodes belonging to the same community to learn node embedding. [Song et al., 2009] employs three kinds of proximities to learn the nodes' representations separately, i.e., Katz measure, Rooted Pagerank and Escape probability. However, all these models ignore the two characteristics of real world networks, i.e., dynamics and partial observerbility.

Dynamic network computation. Most networks are dynamic and we often have to develop new algorithms to deal with the problems on the evolving networks. [Tong et al., 2008] studies the author-conference bipartite graphs and tracks the properties of the nodes as the graphs evolve. [Han and Tang, 2017] analyzes the users' probability of joining the groups in a dynamic network. [Zhou et al., 2018] proposes a dynamic network embedding algorithm by modeling triadic closure process. However, these models assume we can obtain all the changes of the network at every moment, which is not realistic for many real world network. [Anagnostopoulos et al., 2012] introduces and formalize the problem of dynamic network computation, and summarizes the essential properties of many large networks in which the links are evolving all the time and we can only track these changes by explicitly probing the networks. In response to this situation, [Bahmani et al., 2012] proposes a convenient algorithm to compute pagerank on evolving networks. However, it chooses only one node to probe at each moment, while our algorithm supports choosing a batch of nodes to probe at each moment.

3 Network Embedding Framework

To study network embedding on evolving networks, we need to first use a unified framework to cover most existing network embedding algorithms.

3.1 Formulation

We use G = (V,A) to denote the structure of a network. V = (v1, v2, · · · , vN) is the set of the nodes in the network, and |V | = N. A is the adjacency matrix, which is an N ×N matrix. A can be real-valued if G is a weighted network.

Definition 1. Proximity Matrix. For each kind of node proximity in a network, there is a corresponding proximity matrix. We use M to denote the proximity matrix, which is an N ×N matrix and Mi,j represents the value of the corresponding proximity from node vi to vj.

Please note that M may not be Hermitian matrix, because the values of the proximities are often asymmetrical in directed networks.

Definition 2. Node Vector. Node vectors are the nodes' distributed representations. The dimension of the vectors is denoted by p. Thus all the node vectors form an N × p matrix, denoted by X, whose i-th row is the node vector of vi.

Given graph G, network embedding can be formulated as learning a mapping functions, i.e., f : V ⇒ Rp . Thus, the i-th row of X is actually f(vi).

3.2 Matrix Factorization

First, we incorporate network embedding models with a unified framework based on matrix factorization. Given one or more kinds of proximities, the learned node vectors should reflect the proximities adopted. We can use dot product to measure the result of network embedding. Thus we can achieve this goal by minimizing the objective function ONE = minX,Y ‖M -XY T ‖F , in which ‖ · ‖F represents Frobenius norm of the corresponding matrix. Since M is not necessarily a Hermitian matrix, following the usual practice [Mikolov et al., 2013; Tang et al., 2015], we introduce a matrix Y . Similar to X, Y is also an N×p matrix, in which each line is a vector corresponding to a node. However, Y is composed of vectors of nodes when they act as contexts [Mikolov et al., 2013; Tang et al., 2015].

There are many ways to optimize this objective function, such as stochastic gradient descent often used in recommendation system to factorize a rank matrix which is usually sparse [Koren et al., 2009]. Here we adopt another popular tool, i.e., singular value decomposition (SVD), to do it, like [Levy and Goldberg, 2014]. We compute SVD for M, and have M = U0Σ0W T 0 , in which Σ0 = diag(σ1, σ2, · · · , σN) is a diagonal matrix composed of all its singular values, and U0 and W0 are matrices containing all its left and right singular vectors. In practice, we only need to compute its topp singular values Σ = diag(σ1, σ2, · · · , σp) and the corresponding singular vectors U and W to compute X and Y , which can speed up the computation a lot. Then we set X = UΣ 1 2 , Y = Σ 12W T . According to the property of SVD, we have M ≈ XY T .

3.3 ProximityMatrix

For most existing network embedding models, each model adopts a specific proximity among the nodes to learn the node vectors. In this sense, one kind of node proximity results in one network embedding model. Computing the proximity matrix M is the first step to learn the node embedding X. Any kind of proximity can be used for network embedding. Here we introduce the computation method of the proximity matrix M for some kinds of proximities. Some proximities have been used by the existing network embedding models, while the others can be exploited to build new network embedding models.

Adjacency Proximity (AP) means that if there is a link (this link can be weighted) between two nodes, then these two nodes have some similarity. Obviously, the proximity matrix is just the adjacency matrix A, i.e., M (AP) = A.

Jaccard's Coefficient Proximity (JC) can be used to measure the similarity between two finite sets [Jaccard, 1912]. Here the proximity matrix for Jaccard's Coefficient Proximity can be computed as M (JC) i,j = |nbr(vi)∩nbr(vj)| |nbr(vi)∪nbr(vj)| , where nbr(·) denotes the neighbors of the corresponding node.

Katz Proximity (KP) is defined by [Katz, 1953] based on a straightforward intuition that if there are more paths between two nodes and the paths are shorter, the two nodes are more similar. The Katz Proximity between vi and vj can be defined as M (KP ) i,j = ∑∞l=1 αl ·|paths(l) i,j |, where paths(l) i,j is the set of all l-hop paths from vi to vj . Thus the Katz Proximity matrix can be computed as M (KP ) = ∑∞l=1 αlAl = (I-αA)-1-I, where α < 1 is an attenuation factor, I is the identity matrix, and (·)-1 represents the reverse of the corresponding matrix. In addition to the proximities listed above, there are many other proximities, such as Preferential Attachment Proximity [Barabˆasi et al., 2002], Adamic-Adar Proximity [Adamic and Adar, 2003], SimRank Proximity [Jeh and Widom, 2002], High Order Proximity [Benson et al., 2016]. Due to the space limit, we do not list all of them here.

4 Credit Probing Network Embedding

When a network evolves, its proximity matrix M changes accordingly, thus we need to keep updating the node vectors to reflect the latest M. However, in many real world networks, we can only probe part of the nodes to update the proximity matrix and the node vectors. In this section, on the basis of the unified network embedding framework, we propose our algorithm for network embedding under partial monitoring on evolving networks. Here we take Adjacency Proximity for an example, so M = A, and it can be generalized to other proximities just by replacing M with corresponding proximity matrix.

4.1 Algorithm

Specifically, we can describe our problem as follows. Let < 0, 1, ..., T > be a sequence of time stamps. First we select a starting time stamp, for example, t0, and until this moment we can get the complete information of the network structure, thus we can get relatively accurate proximity matrix Mt0 and the results Xt0 and Yt0 . However, at the following time stamps, we can only probe part of the nodes, leading to that we cannot get a global view over the change of the network structure, and consequently we cannot get accurate proximity matrix Mti and accurate embedding results Xti and Yti . The challenge is how to choose the appropriate nodes, whose number cannot exceed a budget denoted by K, to probe to make the results as accurate as possible. This problem can be formulated as follows.

Problem 1. In a network, given a time stamps sequence < 0, 1, ..., T >, the starting time stamp (for example, t0), the proximity and the dimension of the embedding, we need to figure out a strategy, denoted by π, to choose at most K < N nodes to probe at each following time stamp, so that it minimizes the discrepancy between the approximate embedding result, denoted by ˆ ft(V ), and the potential optimal embedding result, denoted by f ∗ t (V ), as described by the following objective function.

It is a sequential decision problem. Obviously, the best strategy is to capture as much "change" as possible with limited "probing budget". If we probe a node which has no change, it is a "waste". Furthermore, probing a node having a big change is better than probing a node having a small change. In a network, some nodes are more likely to change than others, so how do we decide which nodes to choose in the next step?

We propose an algorithm to solve this problem based on a kind of reinforcement learning problem, namely Multi-armed Bandit (MAB) [Auer et al., 2002; Garivier and Capp´e, 2011; Chen et al., 2013] problem. We try to choose the "productive" nodes according to their historical "rewards". We denote the reward of each node vi at each time stamp tj as rvi,tj , which is the change it bring to the proximity matrix M from the last time stamp, formulated as rvi,tj = ‖∆M‖F . We assume that the reward of each node vi has a distribution with an expectation µvi . We should choose the nodes from which we have obtained good rewards, which can be regarded as exploitation. Besides, we should also give a chance to the nodes that we have never probed or rarely probed because they have not fully showed themselves, which can be regarded as exploration. To choose the nodes, we must make a trade-off between exploitation and exploration. To this end, we maintain a "credit" for each node.

Definition 3. Node Credit. If a node vi has been probed for Tvi times by time stamp tj, its credit Cvi,tj is defined as

in which ˆµvi,tj is the empirical mean of the rewards of vi at time stamp tj, and can be achieved by calculating the arithmetic mean of the historical rewards. λ is used to make a trade-off between exploitation and exploration.

The credit of a node can be determined by three factors, including the historical reward, the current time stamp and

Algorithm 1: Credit Probing Network Embedding

Input: A network G, dimension p, proximity kind, time stamp < 0, 1, ..., T >, parameter λ, probing budget K.

Output: approximate node representation matrix ˆXti at each time stamp

1 Initialize ˆµvi , Tvi , Cvi for each node.

2 foreach time stamp tj do

3 probe the nodes with the highest credit.

4 update the approximate network structure ˆGtj .

5 compute the approximate proximity matrix ˆMtj .

6 compute ˆXti .

7

8

9

10

foreach node vi do

update Tvi

update Cvi,tj according to Eq.2.

end

11 end

the times that it has been probed so far. From this definition we can see that a higher historical reward and a smaller number of probe times can lead to a higher credit, which is in line with our purpose of balancing exploitation and exploration. We describe our algorithm to perform network embedding under partial monitoring on evolving networks in Algorithm 1, called Credit Probing Network Embedding (CPNE). At each time stamp, we select the nodes with the highest credits to probe. Then we update the structure of the network and the proximity matrix with the feedback of the probing. Next, we compute the node representations based on the image of the network structure and the proximity matrix. Finally, we update the credits for all the nodes based on Eq.2. To start this algorithm, we should first initialize the credits. There are several methods to implement the initial phase in step 1 in the algorithm. For example, we can initialize them with the information before partial monitoring.

4.2 Theoretical Analysis

In this section, we do some theoretical analysis for our algorithm and provide an error bound to the result of our algorithm. First, we should design a correct metric to measure the objective function in Eq.1. It is not trivial, because when we measure the difference between two sets of embedding values, denoted by X and X′ , it makes no sense to measure the difference between their entries' concrete values with metrics such as ‖X -X′ ‖F . Instead, we should treat the embedding matrix as a whole, and solve this problem with the geometric meaning of the matrix. We can regard matrix X, i.e., the vector representations of the nodes, as a subspace of RN or a linear transformation, which is a stretching of the length and a rotation of the direction of a vector. Since X is achieved by U and S, of which U is a unitary matrix and S is a vector composed of the singular values, the magnitude of the stretching is determined by S and the angle of the rotation is determined by U. Let X∗ represent the potential optimal network embedding result, and ˆX represent the network embedding result obtained by our model. So we can compare the difference between X∗ and ˆX by their corresponding unitary matrices U ∗ and ˆU, and the vectors S∗ and ˆ S. For the vectors S∗ and ˆ S, we can measure their difference by L2-norm of their difference vector, called Magnitude Gap, which is defined as follows.

Definition 4. Magnitude Gap.

For the unitary matrices U ∗ and ˆU, we can measure their difference by their canonical angles [Afriat, 1957; Stewart, 1990]. Please note that X is the embedding result matrix achieved with Y in pairs, which is the vectors of the nodes acting as contexts. In other words, X is the node vectors specific to Y which is obtained by W, so when we compare the difference between U ∗ and ˆU we have to compare the difference between W ∗ and ˆW together, which are also unitary matrices associated with U ∗ and ˆU respectively. Let θ1, θ2, ..., θp be the canonical angles of U ∗ and ˆU, and φ1, φ2, ..., φp be the canonical angles of W ∗ and ˆW. To compare them, we construct two diagonal matrices Θ = diag(θ1, θ2, ..., θp) and Φ = diag(φ1, φ2, ..., φp). We use Angle Gap to measure the difference between (U ∗ ,W ∗ ) and ( ˆU, ˆW), which is defined as follows.

Definition 5. Angle Gap.

where PU ∗ is the orthogonal projection operator of U ∗ , which can be achieved by PU ∗ = U ∗U ∗† = U ∗ (U ∗T U ∗ )-1U ∗T , in which (·)-1 is the inverse of the corresponding matrix and (·)† is Moore-Penrose pseudoinverse. In the same way, we can get PˆU , PV ∗ and Pˆ V with ˆU, V ∗ and ˆ V respectively.

Obviously, for both of the two metrics Magnitude Gap and Angle Gap, the smaller their values, the better the algorithm. To be clear, we add subscript tj to the notation to denote the value at time stamp tj. For example, MGtj represents Magnitude Gap at tj . We define the cumulative losses of MG and AG as LMG = ∑Ttj=1 MGtj and LAG = ∑Ttj=1 MGtj respectively. Then we theoretically analyze the upper bound for each loss. Let D = (vi1 , vi2 , · · · , vip ) be a node set, and D∗ be the optimal node set which have the highest combinatorial reward expectation among all possible node sets. Please note that the combinatorial reward of a set is not necessarily the sum of the individual rewards of the nodes in the set. We define ∆min vi = µD∗ - max{µD|D ̸= D∗ , vi ∈ D}, and ∆max vi = µD∗ -min{µD|D ̸= D∗ , vi ∈ D}, in which µD is the combinatorial reward expectation. Furthermore, we define ∆max = max∆max vi . If we normalize the rewards to [0, 1] and obtain X∗ by selecting D∗ , we can get the upper bounds for LMG and LAG. Specifically, for LMG, we have the following theorem.

Theorem 1.

To prove Theorem 1, we need to use an important theory of matrix perturbation, namely Mirsky theorem. Due to the space limit, we do not repeat it here. One can refer to [Mirsky, 1960] for details.

Proof. Let ∆M = M ∗ - ˆM be the difference matrix between the optimal proximity matrix and the proximity matrix obtained by CPNE. Then we can prove the following inequality by the combinatorial multi-armed bandit theory [Chen et al., 2013].

Then we have

The last inequality is derived from Mirsky theorem. We can get Theorem 1 by combining Formula 5 and Formula 6.

For LAG, we have the following theorem.

Theorem 2.

δ

in which the meaning of δ is explained in the following proof.

To prove Theorem 2, we need to use another important theory of matrix perturbation, namely Wedin theorem. One can refer to [Wedin, 1972] for details.

Proof. Based on our model we have

and

in which Σ∗0 is the diagonal matrix composed of the rest (N-p) singular values of M ∗ , and U ∗ 0 andW ∗ 0 are the corresponding left singular vectors and right singular vectors. The notations in the second equation have similar meanings. We can find a δ > 0 such that min |σ( ˆ Σtj ) - σ(Σ∗0,tj )| ≥ δ and

minσ( ˆ Σtj ) ≥ δ. Then applying Wedin theorem, we have

Then we can get Theorem 2 by combining Formula 5 and Formula 7.

Usually, if we have a larger K, we will have a smaller ∆max and a larger ∆min vi , so we can get a lower error bound.

5 Experiments

In this section we evaluate the performance of our model on several real world datasets from two aspects. First, we evaluate our model's ability to approach the potential optimal values, which is to minimize Magnitude Gap and Angle Gap. Then we evaluate the performance of our model for one of the most important real world problems, namely link prediction. We use the following two datasets to conduct our experiments.

AS. The graph of router comprising Internet is organized into subgraphs called autonomous systems (AS). An AS exchanges traffic flows with its peers, and we can construct a communication network from the Border Gateway Protocol logs. AS dataset contains 9 networks, 1 per week between March 31 2001 and May 26 2001 [Leskovec et al., 2005]. AS dataset contains 10,900 nodes and 19,318 temporal edges.

Wechat. This dataset is collected from a large social network platform, namely Wechat 1 . We randomly select a user with the mean degree of all the WeChat users, and extract its one-hop and two-hop neighbors to construct a subnetwork, containing 15,320 nodes. All the information about the users is erased, and only the topological structure is kept for scientific research. If two users establish a friend relationship between each other, there will be a temporal edge record in the data. We collect the temporal edges from 2015-12-31 23:59:59 to 2017-05-31 23:59:59, and set the snapshot of the WeChat network at the beginning as the initial graph. We set the time interval as one month, then we get 18 time stamps. This network contains 226,988 temporal edges.

To save the space, we only show the result of the first experiment on AS, and that of the second experiment on Wechat.

5.1 Approaching the Potential Optimal Values

This experiment is to evaluate the performance for approaching the potential optimal values of network embedding. The metrics for this experiment are cumulative losses of MG and AG. We use Adjacency Proximity to conduct the experiments. We compute S∗ , U ∗ and W ∗ with the true network structure. We take the first two time stamps for initialization. We use the following four baseline models for the first experiment.

Random. We uniformly select nodes from a network to probe at each time stamp.

Round robin. We cycle through the nodes and probing them in this order.

Degree centrality. At each time stamp, we choose the nodes with the highest values of degree centrality in the latest image of the network structure to probe.

Closeness centrality. This method is similar to Degree Centrality except that it takes the nodes' closeness centrality as the score to choose the nodes.

1 http://www.wechat.com

Comparison of the Models

We compute all the metric values of our model and the baseline models at each time stamp on AS. We set K = 128, λ = 1 and p = 10 for all the models. Then we plot the values of each metric in one sub-figure in Fig.1, in which the X axes represent the time stamps while the Y axes represent the metric values. Then we can see that our model shows significant superiority over all the baseline models in both metrics. From Fig.1 we can also find that for the four baseline models, the performances of Closeness Centrality is somehow slightly better than the other three baseline models. This may be because the nodes with higher closeness centrality usually change more than other nodes in this network, and deserve more attention when the network evolves.

Parameter Sensitivity

In this section, we take a look at the sensitivity of the hyperparameters K. K is the budget of the number of the nodes that we can probe at each time stamp. Usually, the larger the K, the smaller the metric values may be, and the more accurate the learned node vectors. We set K = 16, 32, 64, 128, 256 sequentially, and run CPNE on AS. We plot the results in Fig.2, in which the X axes represent the time stamps while the Y axes represent the metric values. From Fig.1 and Fig.2 we can see that even if we only choose 16 nodes to probe at each time stamp with our algorithm, we can still achieve a better performance than most other algorithms when they choose 128 nodes to probe at each time stamp.

5.2 Link Prediction

In addition to the experiments of testing our model's performance to approach the potential optimal embedding values, we also test the performance of our model for a real world application, i.e., link prediction.

We take BCGD [Zhu et al., 2016] as our baseline. However, BCGD is based on the assumption that all the changes of the network can be perceived. To make a valid comparison, we set the four node probing strategies mentioned above for BCGD separately. Thus we get four baseline methods. We use the node vectors learned by our model and the baseline models at each time stamp (except the last time stamp) to predict the new links in the next time interval. We take the new links emerging in the next time interval as positive instances, and randomly sample the equal number of node pairs that never be linked during the next time interval as the negative instances. We use the dot product of the vectors of two nodes to measure their probability of being linked. We adopt AUC (Area Under the receiver operating characteristic Curve) as our metric. To be fair, we set p = 20 for all the models. For λ of our model, we set it to be 1. For λ, ζ, and δ of BCGD, we set them in accordance with the paper presenting it.

Experimental Results

We conduct the experiment for K = 500 and 1000, and plot the experimental results in Fig.3(a) and Fig.3(b) respectively, in which the X axes represent the time stamps while the Y axes represent the AUC values. We can see that our model outperforms all the baseline models significantly. Specifically, CPNE gets improvements of 36.10% and 39.12% over the best baseline for K = 500 and 1000 respectively at the last time stamp for link prediction.

6 Conclusion

In this paper, we study the problem of network embedding under partial monitoring for evolving networks. There are still many challenges in network embedding on dynamic networks. For the future work, we will try other reinforcement learning algorithms to solve such problems. In addition, how to employ deep learning models to learning embedding values in such a setting is also interesting and meaningful.