Generalized Relational Topic Models with Data Augmentation

1 Introduction

As the availability and scope of network data increase, statistical analysis of such data has attracted a considerable amount of attention. Network data is typically represented as a graph in which the vertices represent entities and edges represent links between entities. Analyzing network data (e.g., link prediction [Liben-Nowell and Kleinberg, 2003; Backstrom and Leskovec, 2011]) could provide useful predictive models for suggesting friends to social network users or citations to scientific articles.

Recent research has focused on latent variable models for link structures, including both parametric [Hoff et al., 2002; Hoff, 2007; Airoldi et al., 2008] and nonparametric Bayesian methods [Miller et al., 2009; Zhu, 2012]. Though modeling network structures well, these models do not account for observed attributes of the entities, such as the text contents of papers in a citation network or the contents of web pages in a hyperlinked network. One work that accounts for both text contents and network structures is relational topic models (RTMs) [Chang and Blei, 2009], an extension of latent Dirichlet allocation (LDA) [Blei et al., 2003] to predict link structures among documents as well as discover their latent topic representations.

Though powerful, existing RTMs have some assumptions that could limit their applicability. First, RTMs define a symmetric link prediction model with a diagonal weight matrix that allows the-same-topic interactions only, and the symmetric nature could make RTMs unsuitable for asymmetric networks. Second, being standard Bayesian models, RTMs do not explicitly deal with the common imbalance issue in real networks which normally have only a few observed links while most entity pairs do not have links. Finally, RTMs and other variants [Liu et al., 2009] apply variational methods to estimate model parameters with normally very strict meanfield assumptions [Jordan et al., 1999].

This paper presents three extensions to improve relational topic models: 1) we relax the symmetric assumption and define generalized relational topic models (gRTMs) with a full weight matrix that allows all pairwise topic interactions and is suitable for asymmetric networks; 2) we perform regularized Bayesian inference [Zhu et al., 2011; 2013a] that introduces a regularization parameter to deal with the imbalance problem in common real networks; and 3) we present a collapsed Gibbs sampling algorithm for gRTMs by exploring the classical ideas of data augmentation [Dempster et al., 1977; Tanner and Wong, 1987; Dyk and Meng, 2001]. Technically, we introduce a set of Polya-Gamma random variables [Polson et al., 2012], one per training link, to derive an exact mixture representation of the logistic link likelihood. Then, we can derive the local conditional distributions for collapsed Gibbs sampling analytically. This "augment-and-collapse" algorithm is simple and efficient. More importantly, it does not make restricting assumptions on the desired posterior distribution. Experiments show that these extensions are important and can significantly improve the performance.

The rest paper is structured as follows. Section 2 presents the generalized RTMs. Section 3 presents the "augment-andcollapse" Gibbs sampling algorithm. Section 4 presents experimental results and Section 5 concludes.

1 2 3 4 5 6 7 8 9 10

2 Generalized Relational Topic Models

We consider document networks with binary link structures. Let D = {(wi,wj, yij)}(i,j)∈I be a labeled training set, where the response variable Y takes values from the output space Y = {0, 1} and wi = {win}Ni n=1 denote the words within document i. A relational topic model (RTM) consists of two parts - an LDA model [Blei et al., 2003] for describing the words W = {wi}Di=1 and a classifier for considering link structures y = {yij}(i,j)∈I. Let K be the number of topics and each topic Φk is a multinomial distribution over a V -word vocabulary. For Bayesian RTMs, the topics are samples drawn from a prior, e.g., Φk ∼ Dir(β), a Dirichlet distribution. The generating process can be described as

1. For each document i
2. (a) draw a topic mixing proportion θi ∼ Dir(α)
3. draw a topic assignment zin ∼Mult(θi)
4. (b) for each word n = 1, 2, . . . ,Ni:
5. draw the observed word win ∼Mult(Φzin )
6. For each pair of documents i, j:
7. (a) draw a link indicator yij ∼ p(.|zi, zj, η), where zi = {zin}Ni n=1 .

Mult(·) denotes a multinomial distribution; and Φzin denotes the topic selected by the non-zero entry of zin, a K-binary vector with only one entry equaling to 1.

Previous work has defined the link likelihood as

where ¯zi = 1 Ni ∑Ni n=1 zin is the average topic assignments of document i; σ is the sigmoid function; and ◦ denotes elementwise product. In [Chang and Blei, 2009], other choices of σ such as the exponential function and the cumulative distribution function of the normal distribution were also used. Here, we focus on the commonly used logistic likelihood model [Miller et al., 2009; Liu et al., 2009].

2.1 The Full RTMModel

Since η⊤(¯zi ◦ ¯zj) = ¯z⊤i diag(η)¯zj , the standard RTM learns a diagonal weight matrix which only captures the-same-topic interactions (i.e., there is a non-zero contribution to the link likelihood only when documents i and j have the same topic). One example of the fitted diagonal matrix on the Cora citation network [Chang and Blei, 2009] is shown in Table 1, where each row corresponds to a topic and we show the representative words for the topic at the right hand side. Due to the positiveness restriction of the latent features ¯zi and the competition between the diagonal entries, some of ηk will have

learning, bound, PAC, hypothesis, algorithm numerical, solutions, extensions, approach, remark mixtures, experts, EM, Bayesian, probabilistic features, selection, case-based, networks, model planning, learning, acting, reinforcement, dynamic genetic, algorithm, evolving, evolutionary, learning plateau, feature, performance, sparse, networks modulo, schedule, parallelism, control, processor neural, cortical, networks, learning, feedforward markov, models, monte, carlo, Gibbs, sampler

10

1 2 3 4 5 6 7 8 9 10

positive values while some are negative. The negative interactions (corresponding to rare topics) may conflict our intuitions of understanding a citation network, where we would expect that papers with the same topics tend to have citation links. Furthermore, by using a diagonal weight matrix, the model is symmetric, i.e., the probability of a link from document i to j is the same as the probability of a link from j to i. The symmetry property does not hold for many networks, e.g., citation networks. To make RTMs more expressive and applicable to asymmetric networks, the first simple extension is to define the link likelihood as

using a full K × K weight matrix U. Using the algorithm to be presented, an example of the learned U matrix on the Cora citation network is shown in Table 2. We can see that by allowing all pairwise topic interactions, all the diagonal entries are positive, while most off-diagonal entries are negative. This is consistent with our intuition that papers with the same topics tend to have citation links, while papers with different topics are less likely to have citation links; and there are some papers with generic topics (e.g., topic 4) that have positive link interactions with almost all others.

2.2 Regularized Bayesian Inference

Let Z = {zi}Di=1 and Θ = {θi}Di=1 denote all the topic assignments and mixing proportions respectively. To fit RTMs, maximum likelihood estimation (MLE) was used with an EM algorithm [Chang and Blei, 2009]. We consider Bayesian inference to get the posterior p(Θ,Z,Φ,U|D) ∝ p0(Θ,Z,Φ,U)p(D|Z,Φ,U), where p0(Θ,Z,Φ,U) = p0(U)(∏i p(θi|α) ∏n p(zin|θi))∏k p(Φk|β) is the prior distribution defined by the model and p(D|Z,Φ,U) = p(W|Z,Φ)p(y|Z,U) is the likelihood. One common issue is that real networks are highly imbalanced-the number of positive links is much smaller than the number of negative links. For example, less than 0.1% document pairs in the Cora network have positive links.

To deal with this imbalance issue, we propose to do regularized Bayesian inference [Zhu et al., 2011; 2013a] which offers an extra freedom to handle the imbalance issue in a cost-sensitive manner. Specifically, we define a Gibbs classifier for binary links as follows. If the weight matrix U and topic assignments Z are given, we build a classifier using the likelihood (2) and the latent prediction rule is

where I(·) is an indicator function that equals to 1 if predicate holds otherwise 0. Since both U and Z are hidden variables,

genetic, evolving, algorithm, coding, programming logic, grammars, FOIL, EBG, knowledge, clauses reinforcement, learning, planning, act, exploration mixtures, EM, bayesian, networks, learning, genetic images, visual, scenes, mixtures, networks, learning decision-tree, rules, induction, learning, features wake-sleep, learning, networks, cortical, inhibition monte, carlo, hastings, markov, chain, sampler case-based, reasoning, CBR, event-based, cases markov, learning, bayesian, networks, distributions

10

we infer a posterior distribution q(U, Z) that has the minimal expected log-logistic loss

which is a good surrogate loss for the expected link prediction error, ∑ij Eq[I(ˆ yij|U,zi,zj ̸= yij)], of a Gibbs classifier that randomly draws a model U from the posterior distribution and makes predictions [McAllester, 2003; Germain et al., 2009]. In fact, this choice is supported by the observations that logistic loss has been widely used as a convex surrogate loss for the misclassification error [Rosasco et al., 2004] in the task of binary classification.

With the above Gibbs classifier, we define gRTM as solving the regularized Bayesian inference problem

where L(q) = KL(q||p0(U, Θ, Z, Φ)) -Eq [log p(W|Z, Φ)] is an information theoretical objective; c is a positive regularization parameter controlling the influence from link structures; and P is the space of normalized distributions. To better understand the above formulation, we define the pseudolikelihood for links as

where ωij = ¯z⊤i U¯zj is the discriminant function value. The pseudo-likelihood is un-normalized if c ̸= 1. Then, problem (5) can be written as

where ψ(y|Z,U) = ∏ij ψ(yij|zi, zj,U). It can be shown that the optimum solution of problem (5) or the equivalent (7) is the posterior distribution with link information

where φ(y,W) is the normalization constant to make q as a normalized distribution.

Therefore, by solving problem (5) or (7) we are in fact doing Bayesian inference with a generalized pseudo-likelihood, which is a powered version of the likelihood (2). The flexibility of using regularization parameters can play a significant role in dealing with imbalanced network data as we shall see. For example, we can use a larger c value for the sparse positive links, while using a smaller c for the dense negative links. This simple strategy has been shown effective in learning classifiers [Akbani et al., 2004] and link prediction models [Zhu, 2012] with highly imbalanced data. Finally, an ad hoc generative story can be described as in RTMs, where c can be understood as the pseudo-count of a link.

3 Augment and Collapse Sampling

For the generalized gRTMs or standard RTMs, posterior inference is intractable. Previous solutions use variational techniques with mean-field assumptions. For example, a variational EM algorithm was developed in [Chang and Blei,

2009] with the factorization assumption that q(U, Θ, Z, Φ) = q(U)(∏i q(θi) ∏n q(zin)) ∏k q(Φk) which can be too restricted in practice. In this section, we present a simple and efficient Gibbs sampling algorithm without making any restricting assumptions on q. Our "augment-and-collapse" sampling algorithm relies on a data augmentation reformulation of the Bayesian inference problem (7).

3.1 Formulation with Data Augmentation

For the pseudo-likelihood ψ(y|Z, η), it is not easy to derive a sampling algorithm directly. Instead, we develop our algorithms by introducing auxiliary variables, which lead to a scale mixture of Gaussian components and analytic conditional distributions for Bayesian inference without an accept/reject ratio. Our algorithm represents an extension of Polson's approach [Polson et al., 2012] to deal with nontrivial Bayesian latent variable models for relational data analysis. Let us first introduce the Polya-Gamma variables.

Definition 1 [Polson et al., 2012] A random variable X has a Polya-Gamma distribution, denoted by X∼PG(a, b), if

where (a, b) are positive parameters and each gi ∼ G(a, 1) is an independent Gamma random variable.

Then, using the ideas of data augmentation [Polson et al., 2012], we have the following results

Lemma 2 The pseudo-likelihood can be expressed as

Lemma 2 indicates that the posterior distribution of gRTMs, i.e., q(U,Θ,Z,Φ), can be expressed as the marginal of a higher dimensional distribution that includes the augmented variables λ. The complete posterior distribution is

3.2 Inference with Collapsed Gibbs Sampling

Although we can do Gibbs sampling to infer the complete posterior q(U, λ,Θ,Z,Φ) and thus q(U,Θ,Z,Φ) by ignoring λ, the mixing rate would be slow due to the large sample space. An effective way to reduce the sample space and improve mixing rates is to integrate out the intermediate Dirichlet variables (Θ,Φ) and build a Markov chain whose equilibrium distribution is the collapsed distribution q(U, λ,Z). Such a collapsed Gibbs sampling procedure has been successfully used in LDA [Griffiths and Steyvers, 2004]. For gRTMs, the collapsed posterior distribution is

where δ(x) = ∏dim(x) i=1 Γ(xi) Γ(∑dim(x) i=1 xi) , C tk is the number of times the term t being assigned to topic k over the whole corpus and Ck = {Ctk }Vt=1 ; C k i is the number of times that terms being associated with topic k within the i-th document and Ci = {C k i }Kk=1 . Then, the conditional distributions used in collapsed Gibbs sampling are as follows.

For U: Let ¯zij = vec(¯zi¯z⊤j ) and η = vec(U), where vec(A) is a vector concatenating the row vectors of A. Then we have ωij = η⊤¯zij. For the common isotropic Gaussian prior p0(U) = ∏kk′ N(Ukk′ ; 0, ν 2 ), we have

where the posterior mean is µ = Σ(∑ij κij¯zij) and the covariance is Σ = ( 1 ν 2 I + ∑ij λij¯zij¯z⊤ij )-1 . We can easily draw a sample from this K2 -dimensional Gaussian distribution. The inverse can be robustly done using Cholesky decomposition. Since K is normally not large, the inversion is relatively efficient, especially when the number of documents is large.

For Z: The conditional distribution of Z is

where ψ(yij|λ,Z) = exp(κijωij - λijω2 ij 2 ). By canceling common factors, we can derive the local conditional of one variable zin given others Z¬ as:

where C · ·,¬n indicates that term n is excluded from the corresponding document or topic; and N + i = {j : (i, j) ∈ I} and N - i = {j : (j, i) ∈ I} denote the neighbors of document i in the training network. We can see that the first term is from the LDA model for observed word counts and the second term is from the link structures y.

For λ: Finally, the conditional distribution of the augmented variables λ is a Polya-Gamma distribution

The result is achieved by using the construction definition of the general PG(a, b) class through an exponential tilting of the PG(a, 0) density [Polson et al., 2012]. To draw samples from the Polya-Gamma distribution, a naive implementation of the sampling using the infinite sum-of-Gamma representation is not efficient and it also involves a potentially inaccurate step of truncating the infinite sum. Here we adopt the efficient method proposed in [Polson et al., 2012], which draws the samples through drawing samples from the closely related exponentially tilted Jacobi distribution.

With the above conditional distributions, we can construct a Markov chain which iteratively draws samples of η (i.e, U) using Eq. (8), Z using Eq. (9) and λ using Eq. (10), with an initial condition. In our experiments, we initially set λ = 1 and randomly draw Z from a uniform distribution. In training, we run the Markov chain for M iterations (i.e., the so called burn-in stage). Then, we draw a sample ˆU as the final classifier to make predictions on testing data. As we shall see in practice, the Markov chain converges to stable prediction performance with a few burn-in iterations.

3.3 Prediction

Since gRTMs account for both text contents and network structures, we can make predictions for each of them conditioned on the other [Chang and Blei, 2009]. For link prediction, given a test document w, we infer its topic assignments z in order to apply the classifier (3). This can be done with a collapsed Gibbs sampler, where the conditional distribution is p(zkn = 1|z¬n) ∝ ˆ φkwn (Ck¬n +αk); C k¬n is the times that the terms in this document w assigned to topic k with the n-th term excluded; and ˆΦ is a MAP estimate of the topics, with ˆ φkt ∝ C tk +βt. For word prediction, we infer the distribution p(wn|y,D, ˆΦ, ˆU) = ∑k ˆ φkwn p(zkn = 1|y,D, ˆU). This can be done by drawing a few samples of zn.

4 Experiments

We present experiments on two public data sets of document networks 1 . The Cora data [McCallum et al., 2000] consists of abstracts of 2,708 computer science research papers, with links between documents that cite each other. In total, the Cora citation network has 5,429 positive links, and the dictionary consists of 1,433 words. The WebKB data [Craven et al., 1998] contains 877 webpages from the computer science departments of different universities, with links between webpages that are hyper-linked. In total, theWebKB network has 1,608 positive links and the dictionary has 1,703 words.

Since many baseline methods have been outperformed by the standard RTMs in [Chang and Blei, 2009] on the same datasets, we focus on evaluating the effects of the various extensions in the generalized relational topic models (denoted by Gibbs-gRTM) by comparing with its several special cases:

1. Var-RTM: the standard RTMs (i.e., c = 1) with a diagonal logistic likelihood and a variational EM algorithm with mean-field assumptions [Chang and Blei, 2009];
2. Gibbs-RTM: the Gibbs-gRTM model with a diagonal weight matrix for the logistic link likelihood;
3. Approx-gRTM: the Gibbs-gRTM model with fast approximation on sampling Z, by computing the link likelihood term in Eq. (8) for once and caching it for sampling all the word topics in each document.

For Var-RTM, we follow the setup [Chang and Blei, 2009] and use positive links only as training data; to deal with the one-class problem, a regularization penalty was used, which in effect injects some number of pseudo-observations (each with a fixed uniform topic distribution). For GibbsgRTM models, including Gibbs-RTM and Approx-gRTM, we instead draw some unobserved links as negative examples.

1 http://www.cs.umd.edu/projects/linqs/projects/lbc/index.html

Though subsamping normally results in imbalanced datasets, the regularization parameter c in Gibbs-gRTM can effectively address it, as we shall see. Here, we fix c at 1 for negative examples, while we tune it for positive examples.

4.1 Quantitative Results

We first report the overall results using the measures of link rank, word rank and AUC (area under ROC curve) of link prediction, following the setups in [Chang and Blei, 2009]. Link rank is defined as the average rank of the observed links from the held-out test documents to the training documents. The word rank is defined as the average rank of the words in testing documents given their links to the training documents. The test documents are completely new that are not observed during training. In the training phase all the words along with their links of the test documents are removed.

Fig. 1 and Fig. 2 show the 5-fold average results and standard deviations of various models on both datasets with respect to the variation of topic numbers. For the RTMmodels using collapsed Gibbs sampling, we randomly draw 1% of the unobserved links as negative training examples, which lead to imbalanced training sets. We can see that the generalized Gibbs-gRTM achieves significantly better results on link rank and AUC scores than all other competitors. For word rank, all the RTM models using Gibbs sampling perform better than the RTMs using variational EM methods when the number of topics is larger than 5. The outstanding performance of Gibbs-gRTM is due to many factors. For example, the superior performance of Gibbs-gRTM over the diagonal GibbsRTMdemonstrates that it is important to consider all pairwise topic interactions to fit real network data; and the superior performance of Gibbs-RTM over Var-RTM shows the benefits of using the regularization parameter c in the regularized Bayesian framework and a collapsed Gibbs sampling algorithm without restricting mean-field assumptions. To single out the influence of the proposed Gibbs sampling algorithm, we also present the results of Var-RTM and Gibbs-RTM with c = 1, both of which randomly sample 0.2% unobserved links as negative examples. We can see that by using Gibbs sampling without restricting assumptions, Gibbs-RTM (neg 0.2%) outperforms Var-RTM (neg 0.2%) that makes meanfield assumptions when the number of topics is larger than 10. We defer more careful analysis of other factors in the next section, including c and the subsampling ratio.

We also note that the cost we pay for the outstanding performance of Gibbs-gRTM is on training time, which is much longer than that of Var-RTM because Gibbs-gRTM has K2 latent features in the logistic likelihood and more training link pairs, while Var-RTM has K latent features and only uses the sparse positive links as training examples. Fortunately, we can apply a simple approximate method in sampling Z as in Approx-gRTM to significantly improve the training efficiency, while the prediction performance is not sacrificed much. In fact, Approx-gRTM is still significantly better than Var-RTM in all cases, and it has comparable link prediction performance with Gibbs-gRTM on the WebKB dataset, when K is large. Table 3 further shows the training time spent on each sub-step of the Gibbs sampling algorithm of GibbsgRTM. We can see that the step of sampling Z takes most of the time (> 70%); and the steps of sampling Z and η take more time as K increases, while the step of sampling λ takes almost a constant time when K changes.

4.2 Sensitivity Analysis

To get insights about the outstanding performance of GibbsgRTM, we present a careful analysis of various factors.

Hyper-parameters c: Fig. 3 and Fig. 4 show the prediction performance of the diagonal Gibbs-RTM and the generalized Gibbs-gRTM on the Cora dataset with different c values. For Gibbs-RTM, we can see that the link rank decreases and AUC scores increase when c becomes larger and the prediction performance is stable in a wide range (e.g., 2 ≤ √c ≤ 6). But the RTM model (i.e., c = 1) using Gibbs sampling doesn't perform well due to its ineffectiveness in dealing with highly imbalanced network data. In Fig. 4, we can observe that when 4 ≤ c ≤ 10, the link rank and AUC scores of Gibbs-gRTM achieve the local optimum, which performs much better than the performance of Gibbs-gRTM when c = 1. By comparing Fig. 3 and Fig. 4, we can see that Gibbs-gRTM generally needs a smaller c to get the best performance. This is because by allowing all pairwise topic interactions, Gibbs-gRTM is much more expressive than Gibbs-RTM; and thus easier to over-fit when c gets large. For both Gibbs-RTM and GibbsgRTM, the word rank increases slowly with the growth of c. This is because a larger c value makes the model more concentrated on fitting link structures and thus the fitness of observed words sacrifices a bit. But if we compare with the variational RTM (i.e., Var-RTM) as shown in Fig. 1, the word ranks of both Gibbs-RTM and Gibbs-gRTM are much lower for all the c values we have tested. This suggests the advantages of the collapsed Gibbs sampling algorithm. In the previous experiments, we has set c = 25 for Gibbs-RTM and c = 4 for Gibbs-gRTM.

Subsample ratio: We analyze the influence of the subsample ratio on the performance of Gibbs-gRTM on the Cora data in Fig. 5. In total, less than 0.1% links are positive on the Cora networks. We can see that by introducing the regularization parameter c, Gibbs-gRTM can effectively fit various imbalanced network data and the different subsample ratios have a weak influence on the performance of Gibbs-gRTM. Since a larger subsample ratio leads to a bigger training set, the training time increases as expected.

Burn-In: We analyze the sensitivity of Gibbs-gRTM on Cora dataset with respect to the number of burn-in iterations. Fig. 6 show the performance of Gibbs-gRTM with different numbers of burn-in iterations. We can see that the link rank and AUC scores converge fast to stable optimum points with about 300 iterations. The training time grows almost linearly with respect to the number of burn-in iterations. We have similar observations for the diagonal Gibbs-RTMmodel and Approx-gRTM with fast approximation. In all the previous experiments, we have set the burn-in steps at 400.

Finally, Gibbs-gRTM models are insensitive to the other parameters (e.g., the Dirichlet prior α) and we omit the details due to space limitation.

5 Conclusions and Discussions

We have presented a generalized relational topic model for considering all pairwise topic interactions and dealing with imbalanced network data by doing regularized Bayesian inference. We also presented a simple "augment-and-collapse" sampling algorithm without restricting assumptions on the posterior distribution. Experiments on real network data demonstrate significant improvements on prediction tasks. The time efficiency can be significantly improved with a simple approximation method.

For future work, we are interested in making the sampling algorithm scalable to large networks by using distributed architectures [Smola and Narayanamurthy, 2010] or doing online inference [Hoffman et al., 2010]. Moreover, the data augmentation idea can be applied to solve the posterior inference problem of other Bayesian logistic latent variable models, such as supervised topic models [Zhu et al., 2013b].

Acknowledgments

This work is supported by National Key Project for Basic Research of China (Grant Nos: 2013CB329403, 2012CB316301), Tsinghua Self-innovation Project (Grant Nos: 20121088071, 20111081111), and China Postdoctoral Science Foundation Grant (Grant No: 2012M520281).