User graph topic model

2.1. Topic modelling for short texts

Several approaches have been proposed for topic modeling to handle short and noisy data. In one approach, short texts have been extended by appending additional words from external knowledge bases Word-Net, Wikipedia or World Wide Web. Additional words are also added from the document corpus itself using co-occurrence word relationships. Co-frequency Expansion (CoFE) [37] framework added the words in the corpus which co-occur frequently with the document words, assuming that co-occurring words have high probability of falling in the same topic. A distributed representation based expansion (DREx) framework [15] is designed which is based on the concept of word embedding to model word similarities.

Another approach of tackling the short text problem is to aggregate the related short documents into longer documents. The relation among the short documents is based on some heuristics. For example, hashtags [16], users [11] and conversations [17] have been used for tweet aggregation. Hong et al. [11] applies the standard LDA on the aggregated document of all the tweets authored by a single user. Mehrotra [16] et al proposes tweet pooling based on burst-score, timestamp and hashtag, which combines tweets on the basis of tweet bursts (i.e. high number of tweets in unit time), time period (e.g. hour) and tweet hashtags respectively. Hashtag based tweet pooling scheme perform better than standard LDA but burst-score and timestamp based pooling does not improve the results. Alvarez-Melis [17] proposes conversa-tion based pooling which combines those tweets which are part of the same twitter conversation. Author claims that conversation based pooling scheme performs better than hashtag based pooling scheme. Other works have also used other tweet contextual information like URL, mentions for tweet pooling. The drawback of these pooling schemes is that the contextual information like hashtags, replies, URLs are not always available in all the tweets. These pooling schemes can be used only when the contextual information is available for aggregation. Self-Aggregation based Topic Model (SATM) [38] uses clustering methods along with topic modelling to provide a general framework for document aggregation.

Another approach for tackling short text is to design special topic modelling algorithm that are suited for sparse and noisy nature of short texts. Bi-term topic Model (BTM) [19] considers all bigrams instead of words in the entire corpus to reduce the sparsity problem. Twitter-LDA [20] models solves the data sparsity problem by assuming that short text contains exactly one topic. This assumption provides better result and is reasonable for the short text. GPU-DMM topic model [39] enriches short text by using auxiliary word embedding from large text collections. It uses Generalized Polya Urn Model to promote semantically related words during the sampling process. Word network Topic Model (WNTM) [21] works upon the pseudo documents created for each word using word graph. The group of words found in the generative process are treated as latent topics in the corpus.

2.2. Supervised topic models

Supervised topic models uses contextual information available with semi structured text documents for guiding the generative models. Blei proposes Supervised LDA (sLDA) [22] for labelled documents to accommodate a variety of response types that limits the topics to a pre-defined set with their distributions provided a priori. Labelled-LDA [40] uses one to one correspondence between topics and document tags to learn word-tag relations. Labelled-LDA restricts a documents topics to the labels assigned to it. Ramage et al [41] uses labelled-LDA to pick hyper-parameters corresponding to the tweet labels restricting tweet topics to its labels.

Several works have been proposed to use tag information associated with the documents to supervise the topic modelling. Hashtag Graph Topic Model (HGTM) [23], Tag-topic model [24], TagLDA [25], Behaviour-LDA [27], tag-Weighted Dirichlet Allocation (TWDA) [26], hashtag-LDA [28], Tag-Latent Dirichlet Allocation [29] models uses the tags associated with the documents to restrict the topics guided by tags. Y Wang [23] proposes HGTM to utilize hashtag relationship from a hashtag graph to model semi structured tweets. HGTM directly models the influence of those words which does not appear in the document itself through the use of hashtag relationships. Tsai presents Tag-topic model [24] for blog mining, which is based on the Author-Topic model and Latent Dirichlet Allocation. The tag-topic model determines the most likely tags and words for a given topic in a collection of blog posts. TagLDA [25] extend Latent Dirichlet Allocation model by replacing the unigram word distribution with a factored representation conditioned on both the topic and the tag structure of the document. TWDA [26] provides a framework that leverages both the tags and words in each document to infer the topic components for the documents. This allows not only to learn the document-topic and topic-word distributions, but also to infer the tag-topic distributions for text mining. Behavior-LDA [27] uses tweet behavior (reply, retweet, post etc.) as document tags and uses it to guide topic learning. Hashtag-LDA [28] studies the influence of tweet hashtags on the topic distribution by jointly modeling the words and hashtags in tweets. Tag-Latent Dirichlet Allocation (TLDA) [29] presents a topic modeling approach that extends Latent Dirichlet Allocation by incorporating the observed hashtags in the generative process. In TLDA, a hashtag is mapped into the form of a mixture of shared topics. This representation further enables the analysis of the relationships between the hashtags. Author Topic Model (ATM) [30] is another supervised topic model which uses author information for influencing topic modelling that models both document content and author interests. In fact, Tag-Topic model is a variant of ATM, in which tags of the blog documents instead of au-thors are used for supervision.

The proposed work is similar to the Author Topic Model in the respect that it also models the author influence on document generation. The advantage of the proposed model is that it can model those document collections in which there is only one author for each document. Performance of ATM is same as standard LDA in this situation. The proposed model is also similar to the Labelled-LDA in the respect that it modifies dirichlet hyper-parameters to model the author influence on topic distribution. Labelled-LDA uses a set of binary switches to select dirichlet hyper-parameters for selecting the topics related to the tags of the documents. Whereas the proposed model obtains dirichlet hyper-parameter values from the relationships among all the users. The proposed work is related to Word Network topic Model (WNTM) and Hashtag Graph topic Model (HGTM) in the respect that the proposed model also uses a graph of users as WNTM uses word graph and HGTM uses hashtag graph.

3.1. Latent Dirichlet Allocation (LDA) and Author Topic Model (ATM)

Latent Drichlet allocation has been widely applied for topic modelling of text documents. In LDA, each document in the corpus is supposed to be a mixture of multiple topics. Each word of the document is sup-posed to come from a different topic. Each document has a multinomial distribution over a fixed number of topics and each topic has a multinomial distribution over a fixed vocabulary words. To generate a word in a document, the generative process of LDA first generates a topic according to the probability distribution of the document over topics and then generates a word according to the probability distribution of the selected topic over vocabulary words.

Author Topic Model (ATM) extents LDA by considering the authorship information of the documents. ATM is used for the documents when there are multiple authors for a single document. In ATM, each author of the document, instead of the document itself, has a multinomial distribution over topics and each topic has a multinomial distribution over words. In ATM, document is modeled as distribution over topics that is a mixture over distributions over authors. Clearly, ATM is same as LDA when each document has exactly one author.

3.2. Proposed user graph topic model

ATM does not improve the performance substantially on documents which has exactly one authors. There are documents like tweets which has exactly one author. Due to the social nature of twitter a tweet by one author is also affected by other authors. ATM fails to model the influence of other users on the tweet generation. UGTM assumes that the words of a document may also be generated by the topic distribution of other users who are not the author of the document. User Graph Topic Model (UGTM) is a probabilistic topic model that describes a generative process to model the collaborative influence of authors on documents. The block diagram of UGTM is shown in Fig. 1.

OPEN IN VIEWER

Fig. 1

Block Diagram of UGTM.

Let the corpus has N documents. Each document has N _d words w_d1, w_d2, …, w _{dN d} . The author of the document d is u _d .

Traditional LDA assumes a fixed number of hidden topics K in the whole corpus. To generate words in a document, it first generates a latent topic and then generates word from that topic. UGTM uses two la-tent variables for the generation of a word. It first generates a latent user variable using the author’s multinomial distribution over all users. Each user has multinomial distribution over topics. UGTM then generates a latent topic variable from the generated user’s topic distribution and then generates word from the generated topic’s word distribution.

UGTM supervises user latent variable generation. Supervision information is taken from user graph which specifies the relationships among users. A user graph is an undirected weighted graph in which nodes are users and edges are obtained from some relationship among users. One relationship between user u _i and u _j is the usage of common hashtags by them in the entire corpus, which shows a kind of semantic relationship between user u _i and u _j . The weight of the edge (u _i , u _j ) is the number of common hashtags between u _i and u _j . Several of such relationship can be defined using tweet contextual information e.g. URLs, replies, mentions etc. User graph is represented as two dimensional matrix G_U×U where U is the number of users in the corpus. Let G _u be the row of the matrix G for user u.

UGTM uses dirichilet-multinomial distribution pair to model user, topic and word generation. Dirichilet distribution is the conjugate prior of the multinomial distribution. The effect of using dirichlet distribution as prior for multinomial distribution is the addition of dirichilet prior count to the multinomial counts in the posterior distribution. For this reason dirichlet prior counts are also called pseudo-counts, which provides a smoothing effect on multinomial parameters and exhibits the polya-urn’s rich get richer behavior [42].

3.2.2. Generative process of tweets in UGTM

Let the author of the document d be u _d . For each word position w _{d i} in document d, user u _{d i} and topic z _{d i} latent variables are generated. First, user u _{d i} of the word w _{d i} is generated. User u _{d i} is generated by drawing from the u _d ’s multinomial distribution ψ _{u d} over all users with dirichlet hyper-parameter γ _{u d} . Each user has a multinomial distribution over topics with dirichlet hyper-parameter α. Topic z _{d i} is drawn from user u _{d i} ’s topic distribution. Each topic has a multinomial distribution over terms with dirichlet hyper-parameter β. Finally, Word w _{d i} is drawn from topic z _{d i} ’s term distribution. By assigning a user latent variable, each user has a contribution to the topic distribution of the document. The plate notation of graphical model of UGTM is depicted in Fig. 1.

OPEN IN VIEWER

Fig. 2

Plate Notation of graphical Model of UGTM.

The generative process for UGTM is described as follows: Φ ∼Dirichlet(β)

θ ∼ Dirichlet(α)

ψ _{u d} ∼ Dir(γ _{u d} )

u| u _d ∼Multinomial(ψ _{u d} )

z ∼Multinomial(θ _u )

w ∼ Multinomial(Φ _z )

Dirichlet hyper-parameters α, β are predefined. Dirichlet hyper-parameter γ is derived from the user graph G (Section 3.2.1). Let γ _u be the dirichlet prior for user u. Number of topics K and number of users U are fixed.

For each of the user u = 1: U, draw ψ _u ∼Dir(γ _u )

For each of the user u = 1: U, draw θ _u ∼Dir(α)

For each of the topic z = 1: K, draw Φ _z ∼Dir(β)

For each document d = 1: N, draw document length N _d

Let u _d be the author of document d and dirichlet hyper-parameter for user u _{d i} be γ _{u d i} .

For each word w _di i = 1: N _d of document d:

Draw u _{d i} for w _di , u _{d i} ∼Multinomial(ψ _{u d} | γ _{u d} )

Draw z _di for u _di , z _di ∼Multinomial(θ _{u d i} )

Draw w _di for z _di , w _di ∼Multinomial(Φ _{z d i} )

UGTM is a probabilistic model that describes the generation of documents as defined in Fig. 2. The author u _d and words w _d of the document are observed. The Dirichlet hyper-parameters γ _u for each user u is derived from the user graph G. For each word in each document, a user and topic latent variables are sampled according to latent multinomial distribution parameters ψ and θ respectively. Now the task is to infer all the hidden variables based on the observed variables. Assuming all words of all the documents are drawn independently, the probability of generating the whole corpus is given by: p ( w | ψ , θ , Φ , u , z , G ) = ∏ d = 1 N p ( w d | ψ , θ , Φ , u d , G )(1)

Here, N is the number of documents in the corpus. Since all the words of a document are drawn independently, the probability of generating document d is given by:

p ( w d | ψ , θ , Φ , u d , G ) = ∏ i = 1 N d p ( w d i | ψ , θ , Φ , u d , G ) Based on the generative process of UGTM, this can be written as: = ∏ i = 1 N d ∑ u = 1 U ∑ k = 1 K p ( w d i , u d i = u , z d i = k | ψ , θ , Φ , u d , G )

= ∏ i = 1 N d ∑ u = 1 U ∑ k = 1 K p ( w d i | z d i = k , Φ ) . p ( z d i = k | u d i = u , θ ) . p ( u d i = u | ψ )

Here, U is the number of users and K is the number of topics. = ∏ i = 1 N d ∑ u = 1 U ∑ k = 1 K Φ kw d i θ uk ψ u d u(2)

The exact inference of the above probability distribution s intractable. An approximate inference method called Gibbs Sampling is used for the solution. Gibbs Sampling [43] is a special case of Markov Cain Monte Carlo (MCMC) [44] simulation and provides simple algorithm for approximate inference in complex models. A collapsed Gibbs sampler is used which integrates out some of the parameters for model inference. In this application, model parameters Φ, θ and ψ are integrated out.

Adopting the process as described in [45], the full conditionals for the hidden variables z _di and u _di are derived after integrating out other parameters, the sample posterior distributions for z _di and u _di can be written as:

p ( u d i = u | U - i , Z - i ) ∝ n u d , - i u + γ u d u ∑ u = 1 U ( n u d , - i u + γ u d u ) × n u , - i k + α ∑ k = 1 K ( n u , - i k + α )(3)

p ( z d i = k | Z - i , W - i ) ∝ n u , - i k + α ∑ k = 1 K ( n u , - i k + α ) × n k , - i t + β ∑ t = 1 T ( n k , - i t + β )(4)

After sufficient number of sampling iteration, the Gibbs sampling chain converges. The parameters Φ, θ and ψ can be obtained using following equations:

ψ u u ′ = n u ′ u + χ u u ′ ∑ u = 1 U ( n u ′ u + χ u u ′ )(5)

θ uk = n u k + α ∑ k = 1 K ( n u k + α )(6)

Φ kt = n k t + β ∑ t = 1 T ( n k t + β )(7)

The Gibbs sampling algorithm is described in Algorithm 1.

Once the parameters has been inferred, a new documents topic distribution can also be inferred using the estimated parameters. For a new document with its author and words known, its topics can be inferred using the same sampling algorithm using the parameters learned by algorithm 1. The algorithm to infer the topics of a new document is shown in Algorithm 2:

4.1. Datasets

The dataset is collected using Twitter Streaming API [46] during April, 2018. Twenty disjoint trending topics are selected to fetch tweets from twitter. For each of the trending topic, certain number of tweets are fetched. Total number of tweets in the dataset is around 193K after discarding retweets. The trending topic of each tweet is assigned as class label of that tweet. The dataset is randomly divided into 80% training set and 20% test set. Topic label distribution in both training and test set is preserved.

OPEN IN VIEWER

Fig. 3

Purity and NMI Score.

Firstly, the data collected from Twitter are processed to remove the quirks of the social nature of Twitter. A raw tweet may have any sort of slangs, punctuations and hyphenation. After tokenizing, all stop-words, expressions, mentions and URLs are removed in the Tweet text. HTML characters are escaped and slangs are modified using a slang dictionary. Only those tweets are retained which has more than 3 tokens after preprocessing.

4.3. Evaluation criterion

The proposed model is evaluated on two tasks. First task is tweet clustering. The performance of proposed model is evaluated on how well it clusters the tweets. Since the true labels of the tweets are available, Purity and Normalized Mutual Information (NMI) [47] are used for clustering evaluation. Clustering quality is good if value of Purity and NMI are large. H-Score [19] measure is also used which is the ratio of intra-cluster distance to the inter-cluster distance. Lesser the H-score values, better the performance.

For Purity and NMI, Each topic is considered as a cluster. To assign a tweet to a cluster, cosine similarity is calculated between vector space model representation of the tweet and topic words distribution. Each tweet is assigned to exactly one cluster with maximum similarity.

For H-score calculation, each tweet’s word-topic count vector is found and normalized to make it a vector. For H-score calculation, we select 20 popular hashtags and each hashtag’s tweet-set is considred as a topic. Note that, one tweet may be in more than one topic if it has more than one selected hashtags. Second task is evaluation of topic quality, which is measured using Pointwise Mutual Information (PMI) score [48], which agrees with human-judged topic coherence. PMI score uses point wise mutual information using an external knowledge-base. In our experiment, English Wikipedia of size 3.1 M articles is used for calculating PMI score. Top twenty words of each topic are considered for the evaluation of PMI-score.

4.4. Results & discussion

Results for both the evaluation tasks are presented in the following sub-sections. Three kind of user relationships have been used to construct user graph. The proposed model is denoted as UGTM-H when hashtags are used to construct user graph. The model is denoted as UGTM-M and UGTM-R when user mentions and replies are used for graph construction respectively.

UGTM results are compared with ATM [30] and HGTM [23]. HGTM uses hashtag relationship among tweets to model the tpoics. Work in [23] shows that it outperforms all hashtag based topic models on tweet and hashtag clustering tasks. We have implemented HGTM-T algorithm as described in [23].

4.4.1. Tweet Clustering

The Purity, NMI and H-score results for the dataset are shown in Figs. 4 and 5. The empirical results shows that all variants of UGTM perform better than ATM on all three evaluation measures purity, NMI and H-score. Among the three UGTM variants, UGTM-H perform better than UGTM-M which performs better than UGTM-R. It shows that hashtag based co-occurrence relationship shows stronger semantic relationship among users than relationship based on user mentions and tweet replies. One reason for this is that the experimental dataset is collected using hashtag based keywords and most of the users have used the popular hashtags and are related with each other based on those hashtags. Also the number of tweets mentioning users (41.1 %) and replying other tweets (14.8 %) are much less than the number of tweets having hashtags (53.3 %). UGTM-M and UGTM-R are outperformed by HGTM. but the performance of UGTM-H is at par with HGTM. In fact, UGTM-H performs slightly better than HGTM on H-Score. Note that HGTM is trained on only those tweets which has at least one hashtag and tested on entire test set which also includes tweets that does not include any hashtags. When HGTM is tested on only those test tweets which has some hashtags, the purity, NMI and H-Score values comes out to be 0.65, 0.51 and 0.41 respectively.

OPEN IN VIEWER

Fig. 4

H-Score.

OPEN IN VIEWER

Fig. 5

PMI Score.

OPEN IN VIEWER

Table 2

Top Twenty Words for Each Algorithm

Topic	UGTM-H	UGTM-M	UGTM-R	HGTM	ATM
ipad	ipad apple iphone professional education pencil inch mini support ios air event price free unveils	ipad iphone bad application celebrate giveaway country update detox work money store ago ipads win	ipad apple pencil asifa buy system house year pretty white money mini god job daughter	ipad apple iphone pencil education professional inch ios support mini event application air unveils price	ipad apple support iphone professional pencil education inch air exposed ios price apps unveils tablet
theatreday	day theatre happy bring friends favourite tuesday celebrating celebrate year awesome public lucky love deal	happy good theatre price breaking feel guys friends start expulsion point wait hard days deal	No topic	happy theatre day celebrate today love world stage show celebrating life great amazing years favourite	happy day theatre pet amazing pets great remember yesterday late missed live fun left forward
Champions League	champions league man real liverpool city semi final madrid roma finals click uefa barcelona ahead	league champions win liverpool madrid uefa won set teams article tweet yesterday coutinho premier bayern	league champions win final liverpool semi won madrid finals real season uefa quarter messi roma	champions league liverpool win real semi madrid final uefa city barcelona man finals cognizant manchester	champions league final win media man liverpool semi finals social started silent followers goal roma
Kim Jong Un	kim jong south north home moon korean breaking leader part jae meet history korea proud	kim jong south north korean korea history leader live makes peace moment meet meeting share	kim jong north south korean korea leader moon jae live moment historic war enter bought	kim jong south moon korean north jae korea leader historic summit plane military president joint r	south president kim jong north read report moon leader medical found start meet history jae
Asaram	asaram bapu innocent case pocso misuse jail bogus swamy justice proof fake due frame conspiracy	asaram bapu innocent case pocso media jail stop bogus swamy proof girl allegation called support	asaram bapu innocent case bogus jail years proof swamy saint bapuji sant judiciary single legal	bapu asaram innocent pocso misuse bogus justice swamy due proof frame conspiracy allegation framed law	asaram bapu innocent pocso misuse jail girl due law proof frame injustice innocents framed sheer