Multi-Modal Bayesian Embeddings for Learning Social Knowledge Graphs

1 Introduction

With the rapid development of online social networks, understanding user behaviors and network dynamics becomes an important yet challenging issue for social network mining. Quite a few research works have been conducted towards dealing with this problem. For instance, Want et al. [2014] developed an approach to infer topic-based diffusion networks by considering different cascaded processes. Han and Tang [2015] proposed a probabilistic framework to model social links, communities, user attributes, roles and behaviors in a unified manner. Sudhof et al. [2014] developed a theory of conditional dependencies between human emotional states and implemented the theory using conditional random fields (CRFs). However, all the aforementioned works do not consider linking social contents to a universal knowledge bases, and thus the mining results can only be applied to a specific social network. Tang et al. [2013] proposed the SOCINST model to extract entity information by incorporating both social context and domain knowledge. However, users are not directly linked to knowledge bases, which limits deeper user understanding.

To bridge the gap between social networks and knowledge bases, we formalize a novel problem of learning social knowledge graphs. More specifically, given a social network, a knowledge base, and text posted by users on social networks, we aim to link each social network user to a given number of knowledge concepts. For example, in an academic social network, the problem can be defined as linking each researcher to a number of knowledge concepts in Wikipedia to reflect the research interests. Learning social knowledge graphs has potential applications in user modeling, recommendation, and knowledge-based search [Sigurbj¨ornsson and Van Zwol, 2008; Kasneci et al., 2008; Tang et al., 2008].

Multi-modal topic models, such as author-topic models [Rosen-Zvi et al., 2004] and Corr-LDA [Blei and Jordan, 2003], can be extended to model the two modalities-i.e., social network users and knowledge concepts-in our problem. However, topic models are usually trained on text, and it is difficult to leverage information in knowledge bases and the structure of social networks. Recent advances in embeddings [Mikolov et al., 2013; Bordes et al., 2013; Perozzi et al., 2014] proposed to learn embeddings for words, knowledge concepts, and nodes in networks, which captures continuous semantics from unlabeled data. However, these embedding techniques do not model multi-modal correlation and thus cannot be directly applied to multi-modal settings.

We propose GenVector, a multi-modal Bayesian embedding model, to learn social knowledge graphs. GenVector uses latent discrete topic variables to generate continuous word embeddings and network-based user embeddings. The model combines the advantages of topic models and word embeddings, and is able to model multi-modal data and continuous semantics. We present an effective learning algorithm to iteratively update the latent topics and the embeddings.

We collect three datasets for evaluation. Experiments show that GenVector clearly outperforms state-of-the-art methods. We also deploy GenVector into an online academic search system to connect a network of 38,049,189 researchers with a knowledge base with 35,415,011 concepts. We carefully design an online A/B test to compare the proposed model with the original algorithm of the system. Results show that GenVector significantly decreases the error rate by 67%. Our main contributions are as follows:

• ÷ We formalize the problem of learning social knowledge

• graphs with the goal of connecting large-scale social networks with open knowledge bases.
• ÷ We propose GenVector, a novel multi-modal Bayesian embedding model to model multi-modal embeddings with a shared latent topic space.
• ÷ We show that GenVector outperforms state-of-the-art methods in the task of learning social knowledge graphs on three datasets and significantly decreases the error rate in an online A/B test on a real system.

2 ProblemFormulation

The input of our problem includes a social network, a knowledge base, and text posted by users of the social network. The social network is denoted as G r = (V r ↪ E r ), where V r is a set of users and E r is a set of edges between the users, either directed or undirected. The knowledge base is denoted as G k = (V k ↪ C), where V k is a set of knowledge concepts and C denotes text associated with or facts between the concepts. One example of the knowledge base is Wikipedia, where concepts are entities proposed by users and text information of a concept corresponds to the article associated with the entity. In general, our problem setting is applicable to any specific C as long as we can learn knowledge concept embeddings from C. Social text posted by users is denoted as D▷ Given a user u 2 V r , du 2 D denotes a document of all text posted by u. Each user u has only one document du.

The output of the problem is a social knowledge graph G = (V r ↪ V k ↪P). More specifically, given a user u 2 V r , Pu is a ranked list of top-k knowledge concepts in V k , where the order indicates the relatedness to user u. For example, in an academic social network, the algorithm outputs the top-k research interests of each researcher u as a ranked list Pu.

There are two modalities in this problem, social network users and knowledge concepts. Previous problem settings usually consider only one of the two modalities. For example, social tag prediction [Heymann et al., 2008] aims to assign tags to social network users without linking tags to knowledge bases. On the contrary, entity recognition in social context [Tang et al., 2013] extracts entities from social text without directly linking entities to users. In this sense, the problem of learning social knowledge graphs is technically challenging because we need to leverage information of both users and concepts.

3 Model Framework

We propose GenVector, a multi-modal Bayesian embedding model for learning social knowledge graphs. To jointly model multiple modalities, GenVector learns a shared latent topic space to generate network-based user embeddings and text-based concept embeddings in two different embedding spaces.

GenVector takes pretrained knowledge concept embeddings and user embeddings as input, where the pretrained embeddings encode information from the knowledge base G k and the social network G r . In other words, embeddings are given as observed variables in our model. We use the Skipgram model [Mikolov et al., 2013] to learn knowledge concept embeddings, and use DeepWalk [Perozzi et al., 2014] to learn network-based user embeddings.

3.1 Generative Process

GenVector is a generative model, and the generative process is illustrated in Figure 1, where we plot the graphical representation with D documents and T topics. Each document du contains a user u with all text posted by u.

The generative process is as follows:

1. For each topic t, and for each dimension
2. (a) Draw θrt ↪ λrt fromNormalGamma(⌧ r )
3. (b) Draw θkt ↪ λkt fromNormalGamma(⌧ k )
4. For each user u
5. (a) Draw a multinomial distribution ✓ from Dir(↵)
6. (b) For each knowledge concept w in du
7. Draw a topic z fromMulti(✓)
8. For each dimension of the embedding of w, draw f k fromN(θkz ↪ λkz )
9. (c) Draw a topic y uniformly from all z's in du
10. (d) For each dimension of the embedding of user u, draw f r fromN(θry ↪ λry )

where notations with superscript k denotes parameters defined for knowledge concepts and notations with r for network users; ⌧ is the hyperparameter of the normal Gamma distribution; θ and λ are the mean and precision of the Gaussian distribution; ↵ is the hyperparameter of the Dirichlet distribution; ✓u is the multinomial topic distribution of document du (or user u); zum is the topic of the m-th knowledge concept in document du; yu is the topic of user u; N(·) denotes the Gaussian distribution. Similarly, f k um are knowledge concept embeddings, while f r u are network-based user embeddings. We drop the subscripts or superscripts when there is no ambiguity.

Note that although it is possible to draw the embeddings from a multivariate Gaussian distribution, we draw each dimension from a univariate Gaussian distribution separately instead, because it is more computationally efficient and also practically performs well. Although developed independently, our model extends Gaussian LDA [Das et al., 2015] to

Algorithm 1: Model Inference

Input: Training data D, hyperparameters ⌧↪ ↵, initial embeddings f r ↪ f k , burn-in iterations tb, max iterations tm, latent topic iterations tl, parameter update period tp Output: latent topics z↪ y, model parameters λ↪ θ↪ ✓, updated embeddings f r ↪ f k // Initialization 1 random initialize z↪ y // Sampling 2 for t 1 to tm do 3 for t0 1 to tl do 4 foreach latent topic z do 5 Draw z according to Eq. (2) 6 foreach latent topic y do 7 Draw y according to Eq. (1) 8 if tp iterations since last read-out and t > tb then 9 Read out parameters according to Eq. (3) 10 Average all read-outs 11 if t > tb then 12 Update the embeddings according to Eq. (5) 13 return z↪ y↪ λk ↪ λr ↪ θk ↪ θr ↪ ✓↪ f r ↪ f k

model multiple modalities. Similar multi-modal techniques were also used in Corr-LDA [Blei and Jordan, 2003]. However, different from Corr-LDA, we generate continuous embeddings in two spaces and use normal Gamma distribution as the prior.

3.2 Inference

We employ collapsed Gibbs sampling [Griffiths, 2002] to do inference. The basic idea of collapsed Gibbs sampling is to integrate out the model parameters and then perform Gibbs sampling. Due to space limitations, we directly give the conditional probabilities of the latent variables.

where the subscript -u means ruling out dimension u of a vector; ntu is the number of knowledge concepts assigned to topic t in document du; Er and Ek are the dimensions of user embeddings and knowledge concept embeddings; l is the smoothing parameter of Laplace smoothing [Manning et al., 2008].

The function G0 (·) is given as follows

with

where ⌧ = ¶↵0↪ β0↪ 0↪ θ0♦ are the hyperparameters of the normal Gamma distribution; n is the number of i's with yi = t; x is a vector of concatenating the e-th dimension of fi's with yi = t; n0 = n - 1 if yu = t, otherwise n0 = n; ¯x is the mean of all dimensions of x.

By taking the expectation of the posterior probabilities, we update the model parameters by

In Gaussian LDA [Das et al., 2015], the word embeddings were kept fixed during inference. Unlike their approach, in our model, we update the embeddings during inference to adapt to different specific problems. Let W be the number of knowledge concepts. We write the log likelihood of the data given the model parameters as

We employ gradient ascent to maximize the log likelihood by updating the embeddings f r and f k . The gradients are computed as

The inference procedure is summarized in Algorithm 1. Following [Heinrich, 2005], we set a burn-in period for tb iterations, during which we do not update embeddings or read out parameters. Similar to [Bezdek and Hathaway, 2003], we employ alternating optimization for inference. More specifically, we first fix the embeddings to sample the topics and infer the model parameters (Cf. Line 3 - 10, Algorithm 1). After a number of iterations, we fix the topics and parameters, and use gradient ascent to update the embeddings (Cf. Line 11 - 12, Algorithm 1). We repeat the procedure for a given number of iterations.

3.3 Prediction

Given a user u and a knowledge concept w, let guw denote whether yu is drawn from zw. Conditioned on u and the model parameters, we compute the joint probability of guw = 1 and generating the embedding f kw ,

For each user u, we rank the interacted knowledge concepts w according to Eq. (6) to obtain Pu. In this way, we construct a social knowledge graph via learning the multi-modal Bayesian embedding model. Note that although it is possible to rank the knowledge concepts by deriving p(f kw ♣f r u ), our preliminary experiments show that using Eq. (6) gives better results.

4 Experiments

In this section, we perform a series of experiments to evaluate the proposed methods. We compare our models with state-ofthe-art models on three datasets, and also design an online test on our system to demonstrate the effectiveness of our method.

4.1 Data and Evaluation

We deploy our algorithm and run the experiments on AMiner 1 , an online academic search system [Tang et al., 2008]. The academic social network G r is constructed by viewing each researcher as a user, and undirected edges represent co-authorships between researchers. There may be multiple edges between a pair of researchers if they collaborate multiple times. We use the publicly available English Wikipedia as the knowledge base G k . Each "category" or "page" in Wikipedia is viewed as a knowledge concept. We use the full-text Wikipedia corpus 2 as the text information C to learn the knowledge concept embeddings. Social text D is derived from publications, where document du for researcher u contains all publications authored by u. If a publication has multiple authors, the publication is repeated for each researcher in their corresponding documents. The basic statistics are shown in Table 1. We compare the following methods.

GenVector is our model proposed in Section 3. We empirically set θ0 = 0, 0 = 1E-5, β0 = 1, ↵0 = 1E3, T = 200, ↵ = 0▷25.

GenVector-E is a variation of GenVector without updating the embeddings in Line 12 of Algorithm 1. We compare GenVector-E with GenVector to evaluate the benefit of embedding update.

Sys-Base is the original algorithm adopted by our system. Sys-Base first extracts key terms using a state-of-the-art NLP rule based extraction algorithm [Mundy and Thornthwaite, 2007], and sorts the key terms by frequency.

CountKG extracts knowledge concepts from social text D by referring to the knowledge concept set V k , and ranks the concepts by appearance frequency.

Author-Topic learns an author-topic model [RosenZvi et al., 2004] and ranks the knowledge concepts by PTt=1 p(w♣t)p(t♣u), where t↪ u↪w denote topic, user and knowledge concept respectively. We set T = 200, ↵ = 0▷25.

1 https://aminer.org/

2 https://dumps.wikimedia.org/enwiki/latest/

NTN is a neural tensor network [Socher et al., 2013] that takes f kw and f r u as the input vector, and outputs the probability of u matching w. We perform cross validation to set the weighting factor λ = 1E-2 and the slice size k = 4.

It is difficult in practice to directly evaluate the results of social knowledge graphs. Instead, we consider two strategies-offline evaluation on three data mining tasks and an online A/B test with live users.

4.2 Offline Evaluation

We collect three datasets for evaluation. We first learn a social knowledge graph based on the data described in Section 4.1 (we discard the long-tailed users that do not appear in our evaluation datasets). For each researcher u, we treat Pu as the research interests of the researcher. Then we use the collected datasets in the following sections to evaluate the precision of the research interests.

Homepage Matching

We crawl 62↪ 127 researcher homepages from the web. After filtering out those pages that are not informative enough (# knowledge concepts < 5), we obtain 1↪ 874 homepages. We manually identify the research interests that are explicitly specified by the researcher on the homepage, and treat those research interests as ground truth. We then evaluate different methods based on the ground truth and report the precision of the top 5 knowledge concepts. The performances are listed in Table 2. GenVector outperforms Sys-Base, Author-topic, and NTN by 5▷8%, 4▷9%, and 18▷5% respectively.

By comparing NTN with GenVector, we show that taking the learned embeddings as input without exploiting the latent topic structure cannot result in good performance, although NTN is among the most expressive models given plain vectors as input [Socher et al., 2013]. NTN does not perform well because it has no prior knowledge about the underlying structure of data, and it is thus difficult to learn a mapping from embeddings to a matching probability. GenVector performs better than Author-Topic, which indicates that incorporating knowledge concept embeddings and user embeddings can boost the performance. In this sense, GenVector successfully leverages both network structure (by learning the user embeddings) and large-scale unlabeled corpus (by learning the knowledge concept embeddings).

GenVector also significantly outperforms Sys-Base and CountKG. Sys-Base and CountKG compute the importances of the knowledge concepts by term frequency. For this reason, the extracted knowledge concepts are not necessarily semantically important. Sys-Base is better than CountKG because Sys-Base uses the key term extraction algorithm [Mundy and Thornthwaite, 2007] to filter out frequent but unimportant knowledge concepts.

The difference between GenVector-E and GenVector indicates that updating the embeddings can further improve the performance of the proposed model. This is because updating the embeddings to fit the data in specific problems, is better than using general embeddings learned from unlabeled data.

LinkedIn Profile Matching

We design another experiment to evaluate the methods based on the LinkedIn profiles of researchers. We employ the network linking algorithm COSNET [Zhang et al., 2015] to link the academic social network on our system to the LinkedIn network. More specifically, given a researcher on our system, COSNET finds the according profile on LinkedIn, if any.

We first select the connected pairs with highest probabilities given by COSNET, and then manually select the correct ones. We use the selected pairs as ground truth, e.g., A on our system and B on LinkedIn are exactly the same researcher in the physical world.

Some LinkedIn profiles of researchers have a field named "skills", which contains a list of expertise. Once a researcher accept endorsements on specific expertise from their friends, the expertise is appended to the list of "skills". After filtering out researchers with less than five "skills", we obtain a dataset of 113 researchers. We use the list of "skills" as the ground truth of research interests. We report the precision of top 5 research interests in Table 3. Since some of the "skills" are not necessarily research interests (e.g. Python), we focus on precision and do not consider recall-based evaluation metrics.

We can observe from Table 3 that GenVector gives the best performance. GenVector outperforms CountKG, AuthorTopic and NTN by 7▷7%, 5▷9%, and 20▷0% respectively (sign test over samples p < 0▷05). Updating the embeddings improves the performance by 1▷1%.

Intruder Detection

In this experiment, we employ human efforts to judge the quality of the social knowledge graph. Since annotating research interests is somewhat subjective, we label the research interests that are clearly not relevant [Liu et al., 2009], also known as intruder detection [Chang et al., 2009]. In other words, instead of identifying the research interests of a researcher, we label what are definitely NOT the research interests of a researcher, e.g., "challenging problem" and "training set".

We randomly pick 100 high cited researchers on our system. For each researcher, we run different algorithms to output a ranked list of knowledge concepts. We combine the top 5 knowledge concepts of each algorithm and perform a random shuffle. The labeler then labels clearly irrelevant research interests in the given list of knowledge concepts. We report the error rate of each method in Table 4.

According to Table 4, GenVector produces less irrelevant knowledge concepts than other methods. It is because GenVector leverages large-scale unlabeled corpus to encode the semantic information into the embeddings, and therefore is able to link researchers to major research interests.

4.3 Online Test

To further test the performance of our algorithm, we deploy GenVector on our online system with the full dataset described in Section 4.1. We leverage collective intelligence by asking the users to select what they think are the research interests of the given researcher.

Since Sys-Base is the original algorithm adopted by our system, we perform an online test by comparing GenVector with Sys-Base to evaluate the performance gain. For each researcher, we first compute the top 10 research interests provided by the two algorithms. Then we randomly select 3 research interests from each algorithm, and merge the selected research interests in a random order. When a user visits the profile page of a researcher, a questionnaire is displayed on top of the profile. A sample is shown in Figure 2. Users can vote for research interests that they think are relevant to the given researcher.

We collect 110 questionnaires in total, and use them as ground truth to evaluate the algorithms. The error rates of different algorithms are shown in Table 5. We can observe that GenVector decreases the error rate by 67%. Moreover, the error rate of GenVector is lower than or equal to that of Sys-Base for 95▷45% of the collected questionnaires (sign test over samples p ⌧ 0▷01).

4.4 Run Time and Convergence

Figure 3 plots the run time and convergence of GenVector and GenVector-E. During the burn-in period, GenVector and GenVector-E perform identically because GenVector does not update the embeddings during the period. After the burnin period, the likelihood of GenVector continues to increase while that of GenVector-E remains stable, which indicates that by updating the embeddings, GenVector can better fit the data, which leads to better performance shown in previous sections. The experiments were run on Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz with 64 threads.

4.5 Case Study

Table 6 shows the researchers and knowledge concepts within each topic, output by GenVector and Author-Topic, where each column corresponds to a topic. As can be seen from Table 6, Author-Topic identifies several irrelevant concepts (judged by human) such as "integrated circuits" in topic #1, "food intake" in topic #2, and "in vitro" in topic #3, while GenVector does not have this problem.

5 RelatedWork

Variants of topic models [Hofmann, 1999; Blei et al., 2003] represent each word as a vector of topic-specific probabilities. Although Corr-LDA [Blei and Jordan, 2003] and the author-topic model [Rosen-Zvi et al., 2004] can be used for multi-modal modeling, the topic models use discrete representation for observed variables, and are not able to exploit the continuous semantics of words and authors.

Learning embeddings [Mikolov et al., 2013; Levy and Goldberg, 2014; Perozzi et al., 2014] is effective at modeling continuous semantics with large-scale unlabeled data, e.g., knowledge bases and network structure. Neural tensor networks [Socher et al., 2013] are expressive models for mapping the embeddings to the prediction targets. However, GenVector can better model multi-modal data by basing the embeddings on a generative process from latent topics.

Recently a few research works [Das et al., 2015; Wan et al., 2012] propose hybrid models to combine the advantages of topic models and embeddings. Gaussian embedding models [Vilnis and McCallum, 2015] learn word representation via a Gaussian generative process to encode hierarchical structure of words. However, these models are proposed to address other issues in semantic modeling, and cannot be directly used for multi-modal data.

Learning social knowledge graphs is also related to keyword extraction. Different from conventional keyword extraction methods [Liu et al., 2009; Mundy and Thornthwaite, 2007; Matsuo and Ishizuka, 2004; Rao et al., 2013], our method is based on topic models and embedding learning.

6 Conclusion

In this paper, we study the problem of learning social knowledge graphs. We propose GenVector, a multi-modal Bayesian embedding model, to jointly incorporate the advantages of topic models and embeddings. GenVector models the network embeddings and knowledge concept embeddings in a shared topic space. We present an effective learning algorithm that alternates between topic sampling and embedding update. Experiments show that GenVector outperforms stateof-the-art methods, including topic models, embedding-based models and keyword extraction based methods. We deploy the algorithm on a large-scale social network and decrease the error rate by 67% in an online test.

Acknowledgements. Zhilin Yang and Jie Tang are supported by 973 (2014CB340506) and 863 (2015AA124102).