3-in-1 Correlated Embedding via Adaptive Exploration of the Structure and Semantic Subspaces

1 Introduction

Network embedding, which learns the representation of every node in the network, challenges the end-to-end strategy for its crown in network analysis [Hamilton et al., 2017; Cai et al., 2017]. Tremendous efforts have been made to improve the performance of embedding in two directions. One is the preservation of structure and properties of the network [Wang et al., 2017b; Ou et al., 2016; Yang et al., 2018], while the other is the integration of side information [Yang et al., 2015; Tu et al., 2017; 2016]. Recently, researchers started to jointly explore the two directions to further improve the embedding performance. To exploit the advantages of both the topological and non-topological information, which are actually complementing each other, combinational network embedding learns the node representation by exploring both of them and draws great attentions [Wang et al., 2017a; Huang et al., 2017b].

†These authors contributed equally to this work and should be considered co-first authors.

∗Corresponding author.

Most of the existing methods can be categorized into two classes. Class 1 methods, which assume the topological and non-topological information being aligned, usually force the entire embedding to represent the two kinds of information simultaneously [Chang and Blei, 2009; Wang et al., 2016; Pan et al., 2016; Liao et al., 2017]. However, the alignment assumption doesn't usually hold in reality. Taking Twitter as an example, social relationships often indicate user groups and users may post messages of diverse topics, i.e., the network structure and content semantic are not aligned at all.

Class 2 methods, which usually assume one kind of information to be more important than the other, tend to require the embeddings to perfectly represent one kind of information and then constrain the embeddings with the other kind of information [Yang et al., 2015; Wang et al., 2017a]. [Huang et al., 2017b] regularizes the network embedding by employing the content embeddings. [Huang et al., 2017a] constrains the embedding of the node attribute with the network topology information. From the literature review we can conclude that some methods in Class 2 are scheduled to prefer the topological information, while others are set to prefer the nontopological information. However, these predetermined preferences of the topological or non-topological information are not rigorous.

In fact, topological and non-topological information is correlated and they should be considered with no predetermined preferences during the embedding process. The ignorance of the correlation tends to degrade the integration of these information and the quality of embedding. The biased treatments of the two kind of information will reduce the versatility of the embedding methods.

In this paper, to alleviate these issues, we improve the embedding performance by considering the correlation in the topological and non-topological information. Three new assumptions about the embedding space and its properties have been proposed, as shown in Figure 1. With the assumptions, nodes, communities (mesoscopic properties of the topological information) and topics (mesoscopic properties of the non-topological information) are seamlessly transformed into one embedding space and a new generative model is developed to portray the generation process of the network and content. This model, which is constructed with respect to the Bayesian framework, can adaptively weight the impacts of the two types of information. i.e., it can automatically lean to the information which is more discriminative. Specifically, if the community structure of the network is more distinguishable than the topic semantics of node content, the model will assign more weight to the topological information, and vice versa. Then the embeddings can be achieved by maximizing the posterior distribution with the variational inference and reparameterization trick.

The main contributions are summarized as follows:

1. We propose three new assumptions to explicitly describe the correlations between the topological and nontopological information.
2. We propose a novel generative model to portray the generation process of the network and content from the latent embeddings of nodes, communities and topics, and adaptively weight their impacts.
3. We propose an efficient variation inference algorithm by adopting the reparameterization trick to maximize the posterior distribution and obtain the embeddings.

2 Correlated EmbeddingModel

A network with node content can be represented as an attributed graph G = (O,E,W). O = {oi|i = 1, ...,D}

is a set of D vertices, where oi is associated with a bag of Ni words {wi,n|n = 1, ...,Ni}. Each word wi,n is drawn from the vocabulary of L words. E is a set of edges, each of which connects two vertices in O. The adjacency matrix Y = [yij ] ∈ RD×D is adopted to represent the network topology, where yij = 1 if an edge exists between the vertices oi and oj, and vice versa. Besides, we assume that the number of communities in the network, K, and the number of topics in the content, T , are known.

In this section, the nodes, communities and topics are designed to be represented in the same M-dimensional latent embedding space. We denote A ∈ RD×M , V ∈ RK×M and U ∈ RT×M as the embedding matrices of the nodes, communities and topics, where ai ∈ RM , vk ∈ RM and ut ∈ RM are the corresponding embedding of node i, community k and topic t, respectively.

2.1 Assumptions

To explore the correlations between the topological and nontopological information, we make three natural assumptions about the embedding space and its inner relationships.

Assumption 1: The 3-in-1 embedding space RM is spanned by the network structure subspace S ⊂ RM and the content semantic subspace C ⊂ RM . An example is shown in Figure 1, where the embedding space (red coordinate system) is spanned by the content semantic subspace (blue plane) and the network structure subspace (green plane).

Assumption 2: Subspace reflects the mesoscopic properties of the observations. As shown in previous work, mesoscopic properties, such as community structures in network embedding [Wang et al., 2017b] and topics in document embedding [He et al., 2017], should be preserved during embedding. Instead of forcing the entire embedding to represent the network structure and content semantic information simultaneously, we indirectly constrain the corresponding subspaces to be spanned by the embeddings of mesoscopic properties. In this paper, we define the network structure and content semantic subspaces as S = span(v1, v2, ..., vK) and C = span(u1, u2, ..., uT ) respectively, where vk ∈ RM and ut ∈ RM are the embeddings of the communities and topics. Let V = [v1, v2, ..., vK] ∈ RK×M and U = [u1, u2, ..., uT ] ∈ RT×M . As the example shown in Figure 1, the network structure subspace (blue plane) is spanned by the embeddings of communities v1 and v2, while the content semantic subspace (green plane) is spanned by the embeddings of topics u1 and u2.

Assumption 3: The corresponding information is generated by the node's mesoscopic properties, which are the projections of the embedding to the subspaces. The projection of embedding ai to the network structure subspace is V ′V ai ∈ RM , and the coordinate based on bases {v1, v2, ..., vK} is gi = V ai ∈ RK . gi, which is the inner product of the embedding of node and communities, can be regarded as the community weight of node i. It can be transformed into the community distribution via si = softmax(gi) where sik = softmaxk(gi) = egik / ∑j egij . Similarly, the topic weight of node i is fi = Uai ∈ RT and the topic distribution is ri = softmax(fi), where rit = softmaxt(fi) =

efit / ∑j efij . gi and fi can be regarded as the structure and content embeddings of node i respectively. According to the mixed-membership model [Blei et al., 2003; Airoldi et al., 2008], the topic and community distributions of nodes are the latent variables which respectively generate the network topology and node content. An example is shown in Figure 1 and the detailed generation process will be discussed in Section 2.2.

2.2 Generative Model

The assumptions proposed above connect the embeddings (nodes, communities and topics) and mesoscopic properties (community and topic) . Here we continue to introduce the generative process from the mesoscopic properties of each node to the topological and non-topological observations. For topological observation, the stochastic block model is adopted. The community distribution of node generates a community assignment to the initiator and receiver for each pair of nodes. The probability of this pair of nodes being connected depends on the communities to which initiator and receiver belong. For non-topological observation, the topic model is adopted. The topic distribution of node generates a topic assignment to each word position. The probability of the word appearing in current position depends on the word distribution of this topic.

The generative process is described as follows. The proposed model, which is illustrated in Figure 2, is represented by three types of variables (observed variables, latent variables and parameter variables). Note that the notations are summarized in Table 1.

1. For each topic t = 1, 2, ..., T
2. (a) Draw the topic word distribution φt ∼ Dir(β)
3. (b) Draw the topic embedding ut ∼ N(0, α-1 I)
4. For each community k = 1, 2, ...,K
5. (a) Draw the community embedding vk ∼ N(0, η-1 I)
6. For each node d = 1, 2, ...,D
7. (a) Draw node embedding ad ∼ N(0, ρ-1 I)
8. (b) Draw the node topic weight fd ∼ N(Uai, ε-1 I)
9. (c) Draw the node community weight gd ∼ N(V ai, τ -1 I)
10. (d) Derive the distribution over topics rd = softmax(fd)
11. (e) Derive the distribution over communities sd = sof tmax(gd)
12. (f) For each word n = 1, 2, ..., Nd
13. Draw the topic assignment zdn ∼Mult(rd)
14. Draw the word wdn ∼ Mult(φzdn )
15. For each pair of nodes i and j
16. (a) Draw initiator indicator xi→j ∼Mult(si)
17. (b) Draw receiver indicator xi←j ∼Mult(sj)
18. (c) Draw link yij ∼ Bernoulli(Bxi→j ,xi←j ).

The joint distribution generated by the above model is

where ∑l φtl = 1. To obtain the embeddings of nodes, communities and topics, A∗ , F ∗ , G∗ , U ∗ , V ∗ , X∗ , Z ∗ , B∗ and Φ∗ that maximizing the posterior P(A, F,G,U, V,X,Z,B, Φ|Y,W, α, η, ρ, ξ, τ, ε, β) should be computed. However, since the likelihood is intractable, the posterior can be approximated via variational inference.

Remarks: One of the most remarkable advantages of the proposed method is that it automatically weights the impacts of two kinds of information and leans to the more discriminative one. For example, assume there exists an attributed network. The community structure in that network is more distinguishable than the topic semantics in that network, i.e., the community assignment of each node is more unequivocal (the entropy of each si is low); while the topic assignment of each node is less unequivocal (the entropy of each ri is very high). Since both si = softmax(V ai) and ri = softmax(Uai) are derived from the projections of ai to the network structure subspaces S and the content semantic subspace C respectively, the correlation between ai and S is high, while the correlation between ai and C is low, i.e., the model leans to the topological information.

3 Variational Inference

In this section, we solve the proposed formulation by adopting the variational EM algorithm. By grouping all the variables into the observed variables as J = {Y,W} and the latent variables as H = {A, F,G,U, V,X,Z,Φ}, the log marginal probability can be decomposed as

Maximizing the lower bound L(q(H)) w.r.t. q(H) is equivalent to minimizing the KL divergence between q(H) and P(H|J). Therefore, the posterior P(H|J) can be approximated by q(H). Here, q(H) is restricted to mean-field family of variational distributions

where the factors have the following parametric forms,

For simplicity, the covariance matrices for q(fd) and q(gd) are both assumed to be diagonal, i.e.,

Then, the objective function can be obtained as

L(q(H)) is iteratively minimized by varying each q(.) and fixing the others. For each topic t, we update q(ut) = N (ut|µt, Σ(u) t ) by minimizing

By rearranging the items which do not contain ut, we obtain

where

Then, we can conclude that q∗ (ut) is proportional to

exp{- 12 u′t [αI + ε ∑d (Σ(a) d +γdγ ′d )]u′t + ∑d ζdtγ ′dut} Thus, q∗ (ut) satisfies our assumption that q(ut) = N (ut|µt, Σ(u) t ) where

where Σ(u) t is independent with t and all topics share the same covraiance matrix Σ(u) . Similarly, q∗ (vk) meets our assumption that q(vk) = N(vk|νk, Σ(v) k ) where

After approximate distributions for three embeddings, q(ad), q(ut) and q(vk) are obtained. Then we optimize L(q(H)) according to the latent variables φt, zdn and fd in the topic model branch. Similar to LDA, we can obtain

which satisfies the assumption q(φt) = Dir(φt|λt) where

The approximate distribution q(zdn = t) is proportional to

where Ψ(.) is the diagamma function, i.e., the first derivative of the log Gamma function. The last latent variable in the topic model branch to be approximated is fd. By isolating the terms containing fd, the objective function is

Here, µ = [µ1, ...., µT ] ∈ RM×T is the collection of the means of q(ut) = N(ut|µt,Σ(u) t ). Due to the normalization term in the softmax function, Eq[log P(zdn|fd) does not have a close-form solution. Thus, reparameterization trick and Monto Carlo sampling [Kingma and Welling, 2013] are adopted to approximate this expectation. Since we assume q(fd) = N (fd|ζd, diag(σ(f ) d )), fd can be reparameterized as

where ⊙ denotes the element-wise multiplication. Then, S samples can be obtained from ϵs ∼ N(0, I) and Eq[log P(zdn|fd) can be rewritten as

The derivations of the three terms in L(q(fd)) (Eq. (7)) w.r.t. the variational parameter ζd are

Similarly, the derivations of these terms w.r.t. σ(f) d are

∇σ(f )

d

∇σ(f )

d

∇σ(f )

d

where et is a vector whose elements are all 0 except the tth element being 1. Then the derivatives of L(q(fd)) (Eq. (7)) w.r.t. the variational parameter ζd and σ(f) d are

Thus, σ(f) d = √ε and ζd can be updated with Adagrad.

Eq [log P (fd|ad, U, ε)] = -εσ(f )

Eq[log q(fd)] = -1/σ(f)

d ,

Eq [log P (zdn|fd)] = 0, d , L(q(H)) is optimized w.r.t. the latent variables θk, xi→j, xi←j and gd in the stochastic block model branch. Similar to the derivation of q(fd), the variational parameters of q(gd) = N (gd|ψd, diag(σ(g) d )) can be updated as follows. σ(g) d = √τ, and ψd is updated with Adagrad according to

where ν = [ν1, ...., νK] ∈ RM×K is the collection of the means of q(vk) = N(vk|νk,Σ(v) k ) and gd = ψd + σ(g) d ⊙ δ, δ ∼ N(0, I).

Next, we optimize L(q(H)) w.r.t. q(xi→j) and obtain

Similarly, χhi←j = q(xi←j = h) is proportional to

Until then, we have finished the E-step in the variational EM algorithm, which computes all the approximate distributions of the latent variables. In the M-step. the hyper-parameters α, η, ρ, ξ, τ, ε, β are fixed and only the model parameter B is updated by maximizing ELBO according to the updated variational parameters. By isolating terms containing B and maximizing L(B), we obtain

By performing the E-step (variational parameters update) and M-step (model parameters update) alternatively, the posterior distribution can be effectively approximated. At last, γd, µt and νk are the embeddings of nodes, topics and communities.

Complexity Analysis

The complexity of the proposed variational algorithm is analyzed as follows. In Eq. (2), updating the means of variational topic embedding {µt}Tt=1 requires O(T(DM +M 2 )) operations. Updating the covariance of variational embedding Σ(u) , which is independent of topic t and only need to be computed once, requires O(DM 2 +M 3 ) operations. Similarly, the complexities of Eqs. (3) and (4) are O(K(DM + M 2 ) +DM 2 +M 3 ) and O(D(TM +KM +M 2 ) + (T + K)M 2 + M 3 ), respectively. In Eq (5), only a one-time traversal over all the words in every node is required, whose complexity is O(DN) where N is the average number of words in each node. The computations in Eq. (6) consists of two parts, computing Φ(.) for each pair of the topic and word and computing κtdn . Their complexities are O(TL) and O(DN) respectively, because computing κtdn only demands a single traversal over all the words. The complexities of Eqs. (8) and (9) are O(D(TM+N)) and O(DKM+R).

Due to the sparsity of network structre [Airoldi et al., 2008], Eqs. (10) and (11) can be performed with only one traversal over all the edges, and thus their time complexities are O(R). Similarly, B can be updated via O(R) operations. In general, the total complexity of the proposed algorithm is O(M 3 + (D+T +K)M 2 +D(T +K)M +DN +T L+R) in each iteration, which is linear with the network scale.

4 Evaluations

4.1 Experimental Setups

Datasets. In the experiments, eight public real networks, as shown in Table 2, are employed. Four of them, i.e., Texas, Cornell, Washington and Wisconsin, are the sub-networks of WebKB network. Each of them is the collection of webpages from an American university. Similarly, nodes in Wiki network are webpages from Wikipedia. Citeseer, Cora and Pubmed are three citation networks whose nodes and edges are scientific publications with binary-valued word attributes and citation relationships, respectively.

Baseline Methods. To demonstrate the superiority of our proposed method, nine state-of-the-art embedding methods are employed for comparisons. These methods can be classified into two categories. The methods in the first category, such as DeepWalk [Perozzi et al., 2014], node2vec [Grover and Leskovec, 2016], LINE [Tang et al., 2015], GraRep [Cao et al., 2015] and M-NMF [Cao et al., 2015], only exploit the network topology information. The methods in the second category, such as TADW [Yang et al., 2015], AANE [Huang et al., 2017a], TriDNR [Pan et al., 2016] and ASNE [Liao et al., 2017] jointly exploit both the topological and nontopological information. Each baseline method employs the default settings in original paper. For fair comparison, the embedding dimension M is set to 64 for every method.

Parameter Settings. In the experiments, the hyperparameters are set to β = 1/T, α = ρ = η = 0.1 and τ = ε = 1. For the number of communities and topics, we simply fix T = K = 40, though they are larger than the true number of groups C and T +K > M, for the following reasons: 1) We are interested in computing the embedding instead of directly detecting the communities and topics; 2) Setting T +K > M reveals the correlations between topological and non-topological information more obviously.

4.2 Node Classification and Clustering

For node classification, the SVM implemented by Liblinear is adopted as the classifier. For each network, 10% of the nodes are randomly selected for training, while the rest of them is employed for testing. This process is repeated 10 times, and the average accuracy are reported in Table 3. The results indicate that the proposed method gives a 5% performance improvement (on average) compared to the state-of-the-art methods, which not only demonstrates the effectiveness and efficiency of the proposed model, but also shows the success of correlation exploration and information adaptation.

For node clustering, the k-means algorithm is applied to the learned embeddings. NMI is adopted to measure the clustering performance. This process is repeated 10 times for each network, and the average results are shown in Table 4. The proposed methods significantly outperform the existing stateof-the-art methods by preserving the mesoscopic properties in network structure and node content.

4.3 Correlation Analysis

To reveal the effectiveness of the correlations between the topological and non-topological information, the dimensions of the network structure subspace K and content subspace T vary from 32 to 64 when the dimension of embedding space is fixed as 64. The results are presented in Figure 3 and demonstrate several observations that: 1) The best results are achieved when both K and T are between 40 and 48, i.e., some (not all) dimensions of the two subspaces are aligned. 2) When K = T = 32, i.e., the two subspaces are independent, the performance is poor. 3) When either K or T is 64, i.e., one subspace contains the other one, the performance also degrades. 4) When K = T = 64, i.e., two subspaces are perfectly aligned, the performance is extremely poor. These observations satisfy the proposed assumptions of this paper.

5 Conclusions

Based on the three new assumptions about the embedding space and its properties, in this paper, nodes, communities and topics are seamlessly mapped into one embedding space, and a novel correlated embedding approach is proposed to better utilize the correlations between the topological and non-topological information and adaptively weight the impacts of them. Extensive results demonstrate the superiority of the proposed method compared to the current state-of-theart methods.

Acknowledgments

Supported by National Key R&D Program of China (No.2017YFC0820106, 2016YFC0801004), National Natural Science Foundation of China (No.61503281, U1636214, U1605252, 61332012, 61772361), Key Program of the Chinese Academy of Sciences (No. QYZDB-SSW-JSC003) and Fundamental Theory and Cutting Edge Technology Research Program of Institute of Information Engineering, CAS (No. Y7Z0381102).