Guillaume Cabanac
email: cabanac@irit.fr

Mohand Boughanem
email: boughanem@irit.fr

Karen Pinel-Sauvagnat

Users Are Known by the Company They Keep: Topic Models for Viewpoint Discovery in Social Networks

Keywords: Viewpoint Discovery, Topic Modeling, Social Networks

Social media platforms such as weblogs and social networking sites provide Internet users with an unprecedented means to express their opinions and debate on a wide range of issues. Concurrently with their growing importance in public communication, social media platforms may foster echo chambers and lter bubbles: homophily and content personalization lead users to be increasingly exposed to conforming opinions.

ere is therefore a need for unbiased systems able to identify and provide access to varied viewpoints. To address this task, we propose in this paper a novel unsupervised topic model, the Social Network Viewpoint Discovery Model (SNVDM). Given a speci c issue (e.g., U.S. policy) as well as the text and social interactions from the users discussing this issue on a social networking site, SNVDM jointly identi es the issue's topics, the users' viewpoints, and the discourse pertaining to the di erent topics and viewpoints. In order to overcome the potential sparsity of the social network (i.e., some users interact with only a few other users), we propose an extension to SNVDM based on the Generalized Pólya Urn sampling scheme (SNVDM-GPU) to leverage "acquaintances of acquaintances" relationships. We benchmark the di erent proposed models against three baselines, namely TAM, SN-LDA, and VODUM, on a viewpoint clustering task using two real-world datasets. We thereby provide evidence that our model SNVDM and its extension SNVDM-GPU signi cantly outperform state-of-the-art baselines, and we show that utilizing social interactions greatly improves viewpoint clustering performance.

INTRODUCTION

e advent of social media platforms such as weblogs and social networking sites provided Internet users with an unprecedented means to express their opinions and debate on a wide range of issues, including society and policy. As a consequence, social media is increasingly impacting political life for lay users and policy makers alike, as a 2014 report by the Pew Research Center suggests [START_REF] Smith | Cell Phones, Social Media and Campaign[END_REF]. Between 2010 and 2014, the share of American voters following political gures on social media has more than doubled. Additionally, other works noted the in uence of social media on key political factors such as democratic participation [START_REF] Zhang | e Revolution Will be Networked: e In uence of Social Networking Sites on Political A itudes and Behavior[END_REF] and campaigning [START_REF] Jungherr | Twi er Use in Election Campaigns: A Systematic Literature Review[END_REF].

Concurrently with the growing importance of social media in public and political communication, a phenomenon known as the echo chambers [START_REF] Sunstein | Republic.com 2.0[END_REF] or lter bubble [START_REF] Pariser | e Filter Bubble: What the Internet Is Hiding from You[END_REF] e ect was recently brought to light by scholars.

is e ect postulates that homophily (i.e., higher chance of bonding between like-minded people) and content personalization lead to an increased exposure to conforming opinions, along with the hiding of contrasting positions. is phenomenon has been for example analyzed in the context of online news consumption [START_REF] Flaxman | Filter Bubbles, Echo Chambers, and Online News Consumption[END_REF] and exposure to ideologically diverse content on Facebook [START_REF] Bakshy | Exposure to Ideologically Diverse News and Opinion on Facebook[END_REF] and Twi er [START_REF] Dunn | Associations Between Exposure to and Expression of Negative Opinions About Human Papillomavirus Vaccines on Social Media: An Observational Study[END_REF][START_REF] Garimella | Reducing Controversy by Connecting Opposing Views[END_REF]. While it has been observed that Internet users are not necessarily interested in purely antagonistic content, the study of news consumption pa erns suggests that balanced sources, which re ect varied viewpoints, are nonetheless appreciated [START_REF] Garre | Partisan Paths to Exposure Diversity: Di erences in Pro-and Countera itudinal News Consumption[END_REF].

erefore, considering the instrumental role played by social media in politics nowadays, there is a need for unbiased systems that enable users to access di erent opinions and thus "burst" the lter bubble.

An initial and necessary step in the design of such unbiased systems is an algorithmic approach able to identify users' viewpoints on a speci c issue (e.g., U.S. policy) and the topics pertaining to this issue. In order to address this task in a realistic context -i.e., where annotation data is scarce, we propose in the present paper a novel unsupervised topic model, the Social Network Viewpoint Discovery Model (SNVDM). Given a speci c issue as well as the text and social interactions from the users discussing this issue on a social networking site, SNVDM jointly identi es the issue's topics, the users' viewpoints, and the discourse pertaining to the di erent topics and viewpoints. In addition to utilizing text data as in traditional topic modeling approaches, SNVDM exploits the homophily phenomenon and thus relies on the users' social interactions to infer their viewpoints. Indeed, users who connect together are more likely to have the same viewpoint, as prior work showed [START_REF] Michael | Political Polarization on Twi er[END_REF][START_REF] Garimella | antifying Controversy in Social Media[END_REF].

While a user's social interactions provide rich insight on her opinions, social networks contain sparse components: some users interact with only a few other users.

ey are however weakly connected to other users: the online acquaintances of their online acquaintances (therea er, for the sake of simplicity, "the acquaintances of their acquaintances"). Accounting for the virtual links between a user and the acquaintances of her acquaintances, we propose an extension to SNVDM, namely SNVDM-GPU, which is based on the Generalized Pólya Urn (GPU) scheme [START_REF] Hosam | Pólya Urn Models[END_REF]. e GPU scheme has been applied in prior work to embed word similarity in topic models [START_REF] Chen | Mining Topics in Documents: Standing on the Shoulders of Big Data[END_REF][START_REF] Li | Topic Modeling for Short Texts with Auxiliary Word Embeddings[END_REF][START_REF] Mimno | Optimizing Semantic Coherence in Topic Models[END_REF][START_REF] Wang | Mining Aspect-Speci c Opinion using a Holistic Lifelong Topic Model[END_REF]. To the best of our knowledge, our paper introduces the rst application of GPU to social networking interactions.

e contributions of the present article are the following:

• We propose a topic model, the Social Network Viewpoint Discovery Model (SNVDM), that leverages text and social networking interactions to estimate users' viewpoints and discussed topics in social media data; • Accounting for social network sparsity and weaker connections between users, we extend SNVDM into the SNVDM-GPU model, which leverages the Generalized Pólya Urn (GPU) scheme; • e two proposed models and variations thereof are evaluated against state-of-the-art baselines, namely TAM [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF], SN-LDA [START_REF] Sachan | Spatial Compactness meets Topical Consistency: Jointly modeling Links and Content for Community Detection[END_REF], and VODUM [START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF], using two real-world datasets harvested from Twi er in [START_REF] Brigadir | Analyzing Discourse Communities with Distributional Semantic Models[END_REF] to assess the validity of the discovered viewpoints;

• Additionally, we publicly release the code of our models and baselines to foster reproducibility and facilitate future viewpoint discovery research.

Section 2 reviews the prior work related to viewpoint discovery. en, in Section 3, we de ne our model SNVDM as well as its extension SNVDM-GPU and we detail their inference procedure. Section 4 describes the experiments conducted to validate these models and how they compete with state-of-the-art baselines. Finally, Section 5 concludes the article and provides future research directions to our work.

RELATED WORK

is section introduces the prior work related to viewpoint discovery in social media. We rst review political polarization in social media. en, we describe unsupervised topic models proposed in literature to address viewpoint discovery in formal text and social media. We nally provide a comparison of our models against prior approaches.

Political Polarization in Social Media

e growing interplay between social media and politics impulsed substantial research on the polarization of online discussions. A seminal study reported on the interactions between political bloggers for the 2004 U.S. elections [START_REF] Lada | Political Blogosphere and the 2004 U.S. Election: Divided ey Blog[END_REF]: Democratic (resp. Republican) bloggers were primarily connected to Democratic (resp. Republican) bloggers. A similar trend was stressed from the analysis of political discussions on Twi er [START_REF] Michael | Political Polarization on Twi er[END_REF]. It was however noted that mentions across ideologically antagonistic users are frequent, as opposed to retweets across such users. Other works analyzed the topics and word usage of Twi er communities built on political or social polarizing issues [START_REF] Brigadir | Analyzing Discourse Communities with Distributional Semantic Models[END_REF][START_REF] Graells-Garrido | Finding Intermediary Topics Between People of Opposing Views: A Case Study[END_REF]. An interesting related body of work tackled the detection of online controversy, i.e., issues that polarize Internet users. In [START_REF] Dori-Hacohen | Automated Controversy Detection on the Web[END_REF], the authors proposed a weakly-supervised approach to identify controversial Wikipedia articles based on edits and talk pages. Controversy detection was also studied on Twi er using supervised [START_REF] Popescu | Detecting Controversial Events from Twi er[END_REF] and unsupervised methods [START_REF] Garimella | antifying Controversy in Social Media[END_REF]. e burst of interest for the study of polarization in social media led researchers to devise supervised machine learning models in order to automatically identify users' political a liation and viewpoint (e.g., Democratic or Republican) from their generated content and/or social interactions [START_REF] Al Zamal | Homophily and Latent A ribute Inference: Inferring Latent A ributes of Twi er Users from Neighbors[END_REF][START_REF] Cohen | Classifying Political Orientation on Twi er: It's Not Easy![END_REF][START_REF] Fang | Topic-centric Classi cation of Twi er User's Political Orientation[END_REF][START_REF] Pennacchio | Democrats, Republicans and Starbucks A cionados: User Classi cation in Twi er[END_REF][START_REF] Rao | Actionable and Political Text Classication using Word Embeddings and LSTM[END_REF]. e proposed approaches were based on traditional machine learning classi ers such as Naive Bayes [START_REF] Fang | Topic-centric Classi cation of Twi er User's Political Orientation[END_REF][START_REF] Hardisty | Modeling Perspective using Adaptor Grammars[END_REF], Support Vector Machine [START_REF] Al Zamal | Homophily and Latent A ribute Inference: Inferring Latent A ributes of Twi er Users from Neighbors[END_REF][START_REF] Cohen | Classifying Political Orientation on Twi er: It's Not Easy![END_REF][START_REF] Magdy | #ISISisNotIslam or #DeportAllMuslims? Predicting Unspoken Views[END_REF], Decision Trees [START_REF] Pennacchio | Democrats, Republicans and Starbucks A cionados: User Classi cation in Twi er[END_REF], or Neural Networks [START_REF] Iyyer | Political Ideology Detection Using Recursive Neural Networks[END_REF][START_REF] Rao | Actionable and Political Text Classication using Word Embeddings and LSTM[END_REF]. While these classi ers usually reach high accuracy, they need to be fed labeled examples, which may be di cult to gather.

Unsupervised Viewpoint Discovery

A common method to overcome the lack of annotation data in text mining tasks is to explore unsupervised topic modeling approaches, e.g., based on Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent Dirichlet Allocation[END_REF]. Researchers therefore proposed Bayesian and topic models to discover viewpoints in formal documents such as essays [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF][START_REF] Michael | Summarizing Contrastive Viewpoints in Opinionated Text[END_REF][START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF] and legislation bills [START_REF] Viet-An | Tea Party in the House: A Hierarchical Ideal Point Topic Model and Its Application to Republican Legislators in the 112th Congress[END_REF], or in social media data such as forum posts [START_REF] Qiu | A Latent Variable Model for Viewpoint Discovery from readed Forum Posts[END_REF][START_REF] Qiu | Modeling Interaction Features for Debate Side Clustering[END_REF] and tweets [START_REF] Barberá | Birds of the Same Feather Tweet Together: Bayesian Ideal Point Estimation Using Twi er Data[END_REF][START_REF] Joshi | Political Issue Extraction Model: A Novel Hierarchical Topic Model at Uses Tweets By Political And Non-Political Authors[END_REF][START_REF] Ren | Time-aware Multi-Viewpoint Summarization of Multilingual Social Text Streams[END_REF].

Application to Formal

Text. In [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF], the authors de ned the Topic-Aspect Model (TAM) that jointly models topics and so-called aspects, which can be interpreted as viewpoints in the context of viewpoint discovery. A constrastive viewpoint summarization framework based on TAM was then described in [START_REF] Michael | Summarizing Contrastive Viewpoints in Opinionated Text[END_REF], aiming to nd phrases that best re ect the di erent viewpoints pertaining to a set of topics. Another topic model, the Viewpoint and Opinion Discovery Uni cation Model (VODUM), was proposed to identify viewpoints by leveraging parts of speech [START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF]. e proposed scheme helped discriminate between topic words and opinion words. e authors of [START_REF] Viet-An | Tea Party in the House: A Hierarchical Ideal Point Topic Model and Its Application to Republican Legislators in the 112th Congress[END_REF] studied a slightly di erent yet related problem: the prediction and analysis of legislators' ideal point given their votes on bills. Ideal point is a measure used in political science to assign policy makers on a one-dimension ideological spectrum ranging from liberal to conservative.

e topic model devised in [START_REF] Viet-An | Tea Party in the House: A Hierarchical Ideal Point Topic Model and Its Application to Republican Legislators in the 112th Congress[END_REF] integrates regression techniques to estimate real-valued ideal points and is able to extract ideological discourse vocabulary.

Models

for Social Media Data. Topic modeling for viewpoint discovery has been applied as well to social media and particularly to forums, which naturally enable Internet users to debate. A more comprehensive literature review on the subject is provided in [START_REF] Qiu | Mining User Viewpoints in Online Discussions[END_REF]. e topic models described in [START_REF] Qiu | A Latent Variable Model for Viewpoint Discovery from readed Forum Posts[END_REF][START_REF] Qiu | Modeling User Arguments, Interactions, and A ributes for Stance Prediction in Online Debate Forums[END_REF][START_REF] Qiu | Modeling Interaction Features for Debate Side Clustering[END_REF] utilize the threaded nature of forum posts. e authors assume that the viewpoint conveyed in a post depends on the post's positive or negative polarity and the viewpoint of the parent post -thereby denoting agreement or disagreement between users. However, the proposed approach could not be applied to social networking sites such as Twi er, where threaded interactions are scarce.

Viewpoint discovery was also studied on Twi er. e authors of [START_REF] Ren | Time-aware Multi-Viewpoint Summarization of Multilingual Social Text Streams[END_REF] designed a time-aware topic model to summarize contrastive opinions expressed in multilingual social text streams. However, contrast was based only on sentiment (positive, negative, or neutral) rather than on viewpoint -which goes beyond mere sentiment polarity and encompasses partisanship, e.g., pro-Palestine and pro-Israel, or Democratic and Republican. Conversely, the work described in [START_REF] Joshi | Political Issue Extraction Model: A Novel Hierarchical Topic Model at Uses Tweets By Political And Non-Political Authors[END_REF] focused on detecting positions and political issues on Twi er. It proposed a topic model that uses politically a liated users to estimate non-a liated users' position; yet it did not leverage interactions between users. On the other hand, a Bayesian ideal point model for Twi er users was devised in [START_REF] Barberá | Birds of the Same Feather Tweet Together: Bayesian Ideal Point Estimation Using Twi er Data[END_REF] but it was only based on follow interactions and it did not utilize text data.

Discovery of viewpoints and related discourse

Uni ed approach TAM [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF][START_REF] Michael | Summarizing Contrastive Viewpoints in Opinionated Text[END_REF]; VODUM [START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF]; [START_REF] Viet-An | Tea Party in the House: A Hierarchical Ideal Point Topic Model and Its Application to Republican Legislators in the 112th Congress[END_REF] ✗ ✗ ✓ ✓ [START_REF] Qiu | A Latent Variable Model for Viewpoint Discovery from readed Forum Posts[END_REF]; [START_REF] Qiu | Modeling Interaction Features for Debate Side Clustering[END_REF]; [START_REF] Qiu | Modeling User Arguments, Interactions, and A ributes for Stance Prediction in Online Debate Forums[END_REF]; [START_REF] Joshi | Political Issue Extraction Model: A Novel Hierarchical Topic Model at Uses Tweets By Political And Non-Political Authors[END_REF]

✓ ✗ ✓ ✓ [44] ✓ ✗ ✗ ✓ [5]; SN-LDA [45] ✓ ✓ ✗ ✓ [49] ✓ ✓ ✗ ✗ SNVDM(-GPU) [this paper] ✓ ✓ ✓ ✓
Although addressing a di erent task, the topic model described in [START_REF] Sachan | Spatial Compactness meets Topical Consistency: Jointly modeling Links and Content for Community Detection[END_REF], namely the Social Network Latent Dirichlet Allocation (SN-LDA), combined both text and social networking interactions to detect communities on Twi er. e di erence between traditional community detection and viewpoint discovery is that the former usually focuses on topical communities (e.g., communities discussing football or programming) while the la er studies the di erent viewpoints expressed on a common set of topics (e.g., the Democratic and Republican positions on abortion). Nonetheless, the homophily phenomenon is featured in both cases; the method used in [START_REF] Sachan | Spatial Compactness meets Topical Consistency: Jointly modeling Links and Content for Community Detection[END_REF] is therefore relevant to our viewpoint discovery goal. Community detection techniques were otherwise applied in conjunction with LDA to analyze advocating and conspiring discussions about vaccines and their underlying topics on Twi er [START_REF] Surian | Characterizing Twi er Discussions About HPV Vaccines Using Topic Modeling and Community Detection[END_REF]. However, the proposed approach did not unify the modeling of text and social interactions. Moreover, the community detection techniques used are non-parametric and thus lead to the discovery of many small communities which may be di cult to interpret and do not necessarily re ect di erent viewpoints.

We summarize in Table 1 the characteristics of our models SNVDM and SNVDM-GPU compared against related work from Section 2.2. Our topic models SNVDM and SNVDM-GPU use social networking interactions and text in a uni ed fashion to discover viewpoints, topics and related word usage in social media data.

ese characteristics are further detailed in Section 3.

METHOD

In this section, we describe the topic models proposed to discover viewpoints and topics in social networking data. We rst establish preliminary de nitions and notations. Secondly, we de ne our topic model, the Social Network Viewpoint Discovery Model (SNVDM), and give its inference procedure. irdly, we provide background on the Pólya Urn sampling scheme and we detail our extension to SNVDM, namely SNVDM-GPU, based on Generalized Pólya Urn.

Preliminaries

As the focus of this work is the modeling of viewpoints and topics in social networks, we provide de nitions for related terms and phrases. Following the de nitions of [START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF], a topic is "one of the subjects discussed in a document collection" and a viewpoint is "the standpoint of one or several authors on a set of topics. " We use the phrase "social network" to denote the directed graph of online social interactions (the edges) between users (the nodes) on a social media platform (e.g., Twi er). We therea er simply use social interactions or interactions to denote online social interactions. Given the directed nature of a social network, a user may take part in two w udn , z udn , l udn , x udn e n-th word token and its topic, level, and route assignments, resp., for document d from user u.

s udi e sender of incoming interaction i on document d from u. distinct types of interactions: incoming interactions and outgoing interactions. A user u takes part in an incoming interaction with another user u ′ if u ′ initiated the interaction (e.g., u ′ retweeted or replied to u's tweet). We then call u and u ′ the recipient and the sender of this interaction, respectively. Conversely, a user u takes part in an outgoing interaction with another user u ′ if u initiated the interaction (e.g., u retweeted or replied to u ′ 's tweet). Similarly, we call u and u ′ the sender and the recipient of this interaction, respectively. e notations for the variables used throughout our paper are provided in Table 2. Additionally, we use boldface symbols to represent a multiset or a vector (e.g.

, v = { ud } D u d=1 U u=1
). Count variables, i.e., variables expressing the number of speci c assignments, are de ned by n and subscripts (e.g., n uz is the number of word tokens from user u assigned to topic z). A subscript " • " means that the counting is marginalized over the corresponding variable (e.g., n • = U u=1 n u ). A superscript -( ) on a count variable implies that the count variable excludes from the counting (e.g., n -(udn) uz is the number of word tokens from user u assigned to topic z, excluding word n from document d of user u). ). e original variable names for TAM and SN-LDA were slightly modi ed from [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF] and [START_REF] Sachan | Spatial Compactness meets Topical Consistency: Jointly modeling Links and Content for Community Detection[END_REF], respectively, to facilitate their comparison against SNVDM.

Social Network Viewpoint Discovery Model

(SNVDM), we introduce its key characteristics. In traditional topic models such as LDA [START_REF] Blei | Latent Dirichlet Allocation[END_REF], words are assumed to be drawn from topic-speci c word distributions. However, in SNVDM, we aim to model viewpoints in addition to topics. A naive approach to account for this would be to simply draw all words from viewpoint/topicspeci c distributions. However, all words need not depend on both a viewpoint and a topic. A word can for example be a background word (e.g., say): it does not re ect any viewpoint or topic; it can otherwise be a topic word (e.g., energy), and depend only on a topic -and not on any viewpoint. To implement this observation, we follow the idea proposed in TAM [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF]. e authors introduced Bernoulli latent variables, namely levels and routes, to account for the possible dependency of word tokens on topic and viewpoint, respectively.

is yields four types of words: background words (level = 0, route = 0), viewpoint words (level = 0, route = 1), topic words (level = 1, route = 0), and viewpoint-topic words (level = 1, route = 1). ese di erent types of words are very useful to analyze the viewpoint-speci c and neutral word usage on a given topic.

Although word usage partially helps identify the expressed viewpoint in a document, this may not be enough as viewpoints can be expressed in a subtle way [START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF]. It is even more problematic in social media texts (e.g., tweets), which are o en short, noisy, and contain numerous abbreviations. However, social media platforms enable social interactions between users. e underlying social network then provides precious insights on users' viewpoint according to the homophily principle: like-minded users tend to connect together.

is idea has been already used in prior topic models designed for community detection, e.g. in SN-LDA [START_REF] Sachan | Spatial Compactness meets Topical Consistency: Jointly modeling Links and Content for Community Detection[END_REF]. However, SN-LDA only utilized interactions and latent topics to identify communitiesword usage did not directly depend on communities. Moreover, in SN-LDA, a given user is only aware of her outgoing interactions, i.e., the interactions she initiated: her incoming interactions are ignored. is may ma er for a user that only or mostly receives incoming interactions (e.g., a user that is o en retweeted but scarcely retweets). Under the modeling of SN-LDA, this user's community will be di cult to identify as she has very few outgoing interactions.

erefore, in our model SNVDM, we propose to use both incoming and outgoing interactions. More precisely, in SNVDM, incoming interactions are used at document level to denote the retrospective in uence of interacting users (e.g., retweeting users) on the viewpoint expressed in a document. Note that, in this paper, we adopt a static view of the collection, we therefore assume in SNVDM's generative process that incoming interactions on a document occur immediately a er the document is wri en. In other words, we do not account for the temporality of incoming interactions.

We now give a more formal de nition of our proposed model SNVDM by providing its graphical model (Figure 1c) compared against that of TAM (Figure 1a) and that of SN-LDA (Figure 1b). We describe as well SNVDM's generative story: (1) Draw general and topic-speci c route distributions ψ 0 and ψ 1z ∼ Beta(γ 0 , γ 1 )

for z = 1, ..., T ; (2) Draw background, viewpoint, topic, and viewpoint-topic word distributions ϕ 00 , ϕ 01 , ϕ 10z , and ϕ 11 z ∼ Dirichlet W (β ) for = 1, ..., V and z = 1, ..., T ;

(3) Draw viewpoint-speci c interacting user distributions ξ ∼ Dirichlet U (µ 1 U ) for = 1, ..., V ; (4) For each user u = 1, ..., U :

(a) Draw viewpoint distribution In the next section, we detail the posterior inference procedure for SNVDM based on collapsed Gibbs sampling.

π u ∼ Dirichlet V (η 1 V ); (b) Draw topic distribution θ u ∼ Dirichlet T (α 1 T ); (c) Draw level distribution σ u ∼ Beta(δ 0 , δ 1 ); (5

Posterior Inference.

As for other probabilistic topic models, the exact posterior inference for SNVDM is intractable. We thus rely on collapsed Gibbs sampling [START_REF] Jun | e Collapsed Gibbs Sampler in Bayesian Computations with Applications to a Gene Regulation Problem[END_REF] to estimate the model distributions. In SNVDM, the latent variables of interest for a collapsed Gibbs sampler are topics z, levels l, routes x, document viewpoints v and outgoing interaction viewpoints v ′ ; the observed variables are words w, incoming interaction senders s, and outgoing interaction recipients r. e collapsed Gibbs sampler for SNVDM then successively samples the aforementioned latent variables from their conditional posterior probability, which we provide in the remainder of this section. Mathematical derivations are omi ed due to space limitations; for a detailed description of Gibbs sampling derivations for topic models, the interested reader can refer to [START_REF] Heinrich | Parameter Estimation for Text Analysis[END_REF].

Sampling topics, levels, and routes. Similarly to TAM [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF], assignments z udn , l udn and x udn can be jointly sampled from the following joint conditional posterior probability:

p(z udn = z, l udn = l, x udn = x | ud = , rest) ∝ n -(udn) uz + α 1 T n -(udn) u• + α • n -(udn) ul + δ l n -(udn) u• + δ 0 + δ 1 • p(x udn = x |rest) • p(w udn = w |rest) (1)
where p(

x udn = x |rest) =            n -(ud n) 0x +γ x n -(ud n) 0• +γ 0 +γ 1 if l = 0, n -(ud n) 1zx +γ x n -(ud n) 1z• +γ 0 +γ 1 if l = 1; and p(w udn = w |rest) =                            n -(ud n) 00w +β n -(ud n) 00• +βW if l = 0, x = 0, n -(ud n) 01 w +β n -(ud n) 01 • +βW if l = 0, x = 1, n -(ud n) 10zw +β n -(ud n) 10z• +βW if l = 1, x = 0, n -(ud n) 11 zw +β n -(ud n) 11 z• +βW if l = 1, x = 1.
Sampling document viewpoints. e conditional posterior probability for the viewpoint ud assigned to user u and her document d is given by:

p( ud = |rest) ∝ W w =1 n (ud ) 01 w -1 a=0 (n -(ud ) 01 w + a + β) n (ud ) 01 • -1 b=0 (n -(ud) 01 • + b + βW ) • T z=1 W w =1 n (ud ) 11 zw -1 a=0 (n -(ud ) 11 zw + a + β) n (ud ) 11 z• -1 b=0 (n -(ud ) 11 z• + b + βW ) • n -(ud ) u + η 1 V n -(ud ) u• + η • U u ′ =1 n (ud ) u ′ -1 a=0 (n -(ud ) u ′ + a + µ 1 U ) n (ud ) • -1 b=0 (n -(ud ) • + b + µ) . ( 2
)
Sampling outgoing interaction viewpoints. For each outgoing interaction o of user u, viewpoint ′ uo is sampled as follows:

p( ′ uo = |r uo = u ′ , rest) ∝ n -(uo) u +η 1 V n -(uo) u• +η • n -(uo) u ′ +µ 1 U n -(uo) • +µ . (3)
Sampling hyperparameters. Prior work showed that sampling hyperparameters -as opposed to se ing them to xed valuesimpacts the model's performance [START_REF] Hanna | Rethinking LDA: Why Priors Ma er[END_REF]. erefore, we apply a full Bayesian treatment to our model by sampling the hyperparameters α, γ , δ , η, and µ from Gamma(1, 1) hyperpriors, following the auxiliary variable sampling technique as in [START_REF] Newman | Distributed Algorithms for Topic Models[END_REF]. We only x β = 0.01 as its sampling is more costly -since it depends on the usually large vocabulary size.

Discussion.

Although SNVDM utilizes direct outgoing and incoming interactions between a user and her acquaintances, it does not leverage farther users in the network such as acquaintances of acquaintances, who can nevertheless bring precious insights on the user's viewpoint. For example, consider a user u who exclusively interacts with a second user u ′ , who in turn interacts with a large number of users. Using only u's sparse direct interactions will not provide much information about her, whereas knowing that there exists a weaker link between u and u ′ 's acquaintances can help describe u more accurately. We augment our model in the next section to implement this idea.

Generalized P ólya Urn Extension

We propose to extend SNVDM in order to account for virtual links between users and their "acquaintances of acquaintances". We rst introduce the simple Pólya urn scheme, then describe the extension of SNVDM based on generalized Pólya urn.

Simple Pólya Urn.

Collapsed Gibbs sampling for Dirichletmultinomial topic models such as LDA or SNVDM can be interpreted as an urn metaphor called the simple Pólya urn (SPU) scheme. SPU assumes that colored balls are successively drawn from an urn; if a ball of color c is drawn, then this ball is put back into the urn and one additional ball of color c is added. is over-replacement scheme enforces a property known as "the rich get richer": the more balls of color c are drawn, the more likely balls of color c will be drawn in the future.

We illustrate the SPU metaphor assuming outgoing interactions are balls, the recipient user of the interaction is their color, and each urn is associated with a viewpoint. Initially, we assume that each urn contains µ 1 U balls of each color. Now suppose that the interaction o for user u is the last ball we want to sample from urni.e., we have already drawn and observed all other interactions/balls. en the probability of obtaining color u ′ for ball (uo) is given by:

p(r uo = u ′ | ′ uo = , rest) = n -(uo) u ′ +µ 1 U n -(uo) • +µ (4)
where n

-(uo)
u ′ can be interpreted as the number of balls of color u ′ added in urn , and n -(uo)

• as the total number of balls added in urn , both counts excluding ball (uo) and the µ initial balls. Note that the rightmost term in Eq. ( 3) is the same as the one in Eq. ( 4) obtained using the SPU assumption, illustrating the equivalency between Dirichlet-multinomial and SPU models.

Generalized Pólya

Urn. e generalized Pólya urn (GPU) scheme [START_REF] Hosam | Pólya Urn Models[END_REF] extends SPU by altering the replacement rule: a er a ball of color c is drawn, the ball is put back into the urn and a certain number of balls of colors related to c are added along. In prior topic models using GPU, balls are tokens and colors are word types [START_REF] Chen | Mining Topics in Documents: Standing on the Shoulders of Big Data[END_REF][START_REF] Li | Topic Modeling for Short Texts with Auxiliary Word Embeddings[END_REF][START_REF] Mimno | Optimizing Semantic Coherence in Topic Models[END_REF][START_REF] Wang | Mining Aspect-Speci c Opinion using a Holistic Lifelong Topic Model[END_REF]; the "relatedness" of colors is therefore based on word similarity such as PMI [START_REF] Chen | Mining Topics in Documents: Standing on the Shoulders of Big Data[END_REF][START_REF] Wang | Mining Aspect-Speci c Opinion using a Holistic Lifelong Topic Model[END_REF] or computed from word embeddings [START_REF] Li | Topic Modeling for Short Texts with Auxiliary Word Embeddings[END_REF].

In our model, however, we utilize GPU to account for weaker links between users in a social network. As illustrated in 3.3.1, we consider interactions as balls and users as colors. Leveraging the network structure, we assume that the users most related to a user u are the users who interact the most with u. Formally, we de ne the number of incoming interactions on u where u ′ is the sender as i uu ′ = D u d =1 I ud i=1 I(s udi = u ′ ), and the number of outgoing interactions from u where u ′ is the recipient as o uu ′ = O u o=1 I(r uo = u ′ ). I denotes the indicator function: I(true) = 1 and I(false) = 0. e set of the τ most interacting acquaintances of u (if such number of acquaintances exists for u) is then R uτ with

|R uτ | = min τ , U u ′ =1 I(i uu ′ + o uu ′ > 0)
, and such that, for all u ′ ∈ R uτ , i uu ′ + o uu ′ > 0 (i.e., u ′ is an acquaintance of u) and, for all u ′′ R uτ , i uu ′ + o uu ′ ≥ i uu ′′ + o uu ′′ (i.e., u ′ interacts more with u than u ′′ does). We now de ne a U × U real-valued matrix A known as schema or addition matrix [START_REF] Hosam | Pólya Urn Models[END_REF] which, given a withdrawn ball of color u, expresses the number of balls A uu ′ for each color u ′ = 1, ..., U that is added along to the urn:

A uu ′ =          1 if u = u ′ , λ if u u ′ and u ′ ∈ R uτ , 0 otherwise; ( 5
)
where λ is a real-valued parameter in [0, 1] denoting the number of balls added for colors related to u (i.e., in R uτ ). Contrarily to the SPU scheme, balls sampled according to GPU are non-exchangeable, implying that the sampling order for a sequence of balls will impact the probability of the observed colors. Following [START_REF] Mimno | Optimizing Semantic Coherence in Topic Models[END_REF], we approximate the exact conditional posterior probability used in Gibbs sampling by assuming that the ball or sequence of balls of interest is sampled as if we already sampled and observed all other balls in the urn. We thus ignore the current sampling's implications on the drawing of subsequent balls.

e application of the GPU scheme to SNVDM under this approximation leads to a slight modi cation of the collapsed Gibbs sampler described in Section 3.2.2. In the sampling of document viewpoint ud , the rightmost term in Eq. ( 2) under the GPU assumption can be shown to become:

I ud i=1 U u ′′ =1 A u ′′ s ud i n -(ud ) u ′′ + i-1 j=1 A s ud j s ud i + µ 1 U U u ′′ =1 A u ′′ • n -(ud) u ′′ + i-1 j=1 A s ud j • + µ . (6)
Similarly, the rightmost term in Eq. ( 3) for the sampling of outgoing interaction viewpoint ′ uo is changed into:

U u ′′ =1 A u ′′ u ′ n -(uo) u ′′ + µ 1 U U u ′′ =1 A u ′′ • n -(uo) u ′′ + µ . ( 7
)

EXPERIMENTS

In this section, we detail the experiments conducted on our models SNVDM and SNVDM-GPU, and their comparison against state-ofthe-art baselines. We aim to validate the following hypotheses:

• (H1) e viewpoint clustering performance of the proposed models (a) outperforms that of state-of-the-art baselines; it is improved by (b) exploiting both incoming and outgoing interactions, and (c) implementing the generalized Pólya urn scheme. • (H2) Generalized Pólya urn scheme increases models' robustness to social network sparsity, i.e., GPU-based models are less a ected by limited number of social interactions.

• (H3) e proposed models are comparably e cient to stateof-the-art baselines, i.e., their execution times have the same order of magnitude. • (H4) e viewpoints and topics discovered by our models are coherent. In the remainder of this section, we rst introduce the experimental setup. Secondly, we detail the viewpoint clustering performance of our models and baselines. irdly, we discuss the e ciency of the evaluated models. Finally, we illustrate the discovered viewpoints and topics by providing their most representative words.

Experimental Setup

4.1.1 Baselines and Evaluated Models. In order to test hypotheses (H1)-(H4), we compare prior topic models able to discover viewpoints against variations of our proposed models:

• TAM [START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF] was initially designed to discover topics and aspects -which represent viewpoints in our context. It was integrated into a viewpoint summarization framework in [START_REF] Michael | Summarizing Contrastive Viewpoints in Opinionated Text[END_REF]. It does not account for interactions between users. • SN-LDA [START_REF] Sachan | Spatial Compactness meets Topical Consistency: Jointly modeling Links and Content for Community Detection[END_REF] aims to jointly discover topics and communities -which we interpret as viewpoints -in a social network where users are associated with text data. e only interactions used are outgoing interactions.

• VODUM [START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF] models viewpoints and topics. It leverages part of speech to be er discriminate opinion words (i.e., viewpoint/topic-speci c words) from topic words. It does not use interactions between users. • SNVDM-WII is a degenerate variation of our model SNVDM (described in Section 3.2) without incoming interactions. e only interactions used are outgoing interactions.

• SNVDM is the model we propose, as described in Section 3.2. It leverages incoming and outgoing interactions. • SNVDM-GPU (τ = 10) and SNVDM-GPU (τ = ∞) extend SNVDM by integrating the generalized Pólya urn scheme into the inference procedure, as described in Section 3.3. e value of τ de nes the maximum number of most interacting acquaintances used as related users. In SNVDM-GPU (τ = 10), only the 10 most interacting acquaintances of a given user are used as her related users, whereas for SNVDM-GPU (τ = ∞) all acquaintances are used as related users. We release the Java code for our models and baselines at h ps: //github.com/ honet/SNVDM. 4.1.2 Datasets. ere exists only few annotated datasets to evaluate models for viewpoint discovery in social networks. In 2016, the International Workshop on Semantic Evaluation (SemEval) introduced a benchmark for stance detection on Twi er [START_REF] Saif | SemEval-2016 Task 6: Detecting Stance in Tweets[END_REF]. However, the task proposed by SemEval was focused on tweet-level stance detection, whereas in this work we are interested in discovering user-level viewpoints. e methods and data relevant to these two problems di er as only the la er enables the exploitation of social interactions. erefore, we chose to validate our approaches on two Twi er datasets1 introduced in [START_REF] Brigadir | Analyzing Discourse Communities with Distributional Semantic Models[END_REF], which we refer the reader to for additional details. e rst dataset, therea er denoted as Indyref, [START_REF] Brigadir | Analyzing Discourse Communities with Distributional Semantic Models[END_REF] either from self-description in user pro les or from o cial and uno cial lists. Similarly to prior work on political polarization [START_REF] Michael | Political Polarization on Twi er[END_REF][START_REF] Magdy | #ISISisNotIslam or #DeportAllMuslims? Predicting Unspoken Views[END_REF], the Twi er social interactions that we considered to de ne the users' social network are retweets and replies.

An issue we had to address with the datasets was the fact that they contained a large amount of tweets that did not concern the studied political subject (e.g., tweets about leisure or daily life). To remove these irrelevant tweets, we discarded all the tweets with no interactions from the users in the dataset, i.e., tweets with neither reply nor retweet from the dataset users. Although this process removed some relevant tweets, we observed that it provided us with considerably more focused datasets. Moreover, we only kept unique tweets in the datasets (removing the retweeted duplicates) and assigned them to their original authors. A er the denoising step, users le with no tweets were discarded (32 for Indyref and 232 for Midterms). Note that this process is widely applicable to any dataset with social interactions and it does not require supervision. However, the number of interactions per tweet ratio is a ected; therefore we further investigate in Section 4.2.2 the impact of the network sparsity on the models' and baselines' performance.

We then performed the following preprocessing steps on the datasets using Lingpipe2 and TweetNLP3 . We applied the part-ofspeech tagger provided by TweetNLP to the tweets, as it is required by the baseline VODUM to discriminate opinion words from topic words. Following [START_REF] Cabanac | VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery[END_REF], nouns were used as topic words and verbs, adverbs, adjectives, and prepositions (and additionally hashtags) were used as opinion words in VODUM. Tokens not matching these parts of speech were discarded from the datasets used by all modelsthe rationale is that, for a fair comparison, we wanted to test all models on exactly the same text data. We then removed stopwords, user mentions, URLs and word tokens that appeared only once. Following [START_REF] Scho | Comparing Apples to Apple: e E ects of Stemmers on Topic Models[END_REF], we did not perform stemming. Users with no tweets (or with only token-less tweets) were discarded. e statistics of the preprocessed datasets are detailed in Table 3. Reported interactions include both incoming and outgoing interactions.

Parameter Se ing.

For both datasets Indyref and Midterms, we set the number of viewpoints (for VODUM and all SNVDMbased models), aspects (for TAM), and communities (for SN-LDA) to 2. For all baselines and models, hyperparameters were initialized to 1 and sampled as described in Section 3.2.2, except for word distributions parameters (β in SNVDM-based models) which are set to 0.01. e parameter λ used in GPU models was xed to 0.5. We observed (not shown due to space limitations) that this yielded be er performance than se ing λ = 1 (i.e., a uniform treatment of direct acquaintances and acquaintances of acquaintances). e Gibbs sampling inference for all baselines and models is performed on 5 Markov chains of 1,000 iterations each, with 500 iterations for burn-in. A er burn-in, one sample was collected every 50 iterations, and models' distributions were eventually estimated based on the 10 collected samples.

Viewpoint Clustering

In this section, we describe the results obtained by baselines and proposed models on the clustering of users' viewpoints, evaluated in terms of Purity and Normalized Mutual Information (NMI) [START_REF] Christopher | Introduction to Information Retrieval[END_REF]. Purity measures the proportion of users who are assigned to the correct groundtruth class. NMI is an information theoretic clustering metric based on Mutual Information and Entropy. We also tested the BCubed F measure [START_REF] Amigó | A Comparison of Extrinsic Clustering Evaluation Metrics based on Formal Constraints[END_REF] but we found almost perfect Spearman's rank correlations between Purity and BCubed F (ρ = 0.998) and between NMI and BCubed F (ρ = 0.999) -computed from the 280 measurements obtained in Section 4.2.1. erefore, for the sake of brevity, we only report the clustering quality results in terms of Purity and NMI in the experiments.

e clusters are built as follows: In SNVDM-based models, each user u is assigned to the viewpoint (cluster) that maximizes the user-speci c viewpoint distribution π u . TAM's aspect and SN-LDA's community assignments for users are similary obtained. In VODUM, a viewpoint is naturally a ributed to each user, as viewpoints are de ned at user level.

Clustering

Performance. e viewpoint clustering results in terms of Purity and NMI for di erent number of topics T ∈ {5, 10, 15, 20} on both the Indyref and Midterms datasets are reported in Figure 2. Note that the error bars denote the 95% condence interval about the mean, which are computed from the 5 repeated executions (i.e., the 5 Markov chains). Con rming (H1a), we observe that for both datasets and for both metrics, our proposed models SNVDM, SNVDM-GPU (τ = 10) and SNVDM-GPU (τ = ∞) outperform all baselines with superior mean Purity and mean NMI on both Indyref and Midterms. e fact that their 95% con dence intervals do not intersect with those of baselines also con rm the statistical signi cance of this observation at signicance level α = 0.05. We also notice that our models are mostly insensitive to the number of topics.

Comparing our models SNVDM, SNVDM-GPU (τ = 10) and SNVDM-GPU (τ = ∞) against SN-LDA and the degenerate variation SNVDM-WII, which both do not exploit incoming interactions, support (H1b). Indeed, all models that use incoming interactions in addition to outgoing interactions signi cantly outperform those using only outgoing interactions. We nevertheless note that the baseline SN-LDA still achieved a strong clustering performance on both datasets, especially on Indyref. is could be explained by the fact that Indyref features a larger number of interactions per user, upon which SN-LDA heavily relies. It also underlines the key importance of social interactions to viewpoint discovery. Other baselines TAM and VODUM both performed markedly worse than SN-LDA. ey obtained similar performance on Midterms and TAM got be er results on Indyref. e underperformance of VODUM may be due to its reliance on parts of speech, which are possibly less discriminative in identifying viewpoint-speci c words in noisy, short texts like tweets than they are in long and formal documents. Both VODUM and TAM seem to be moderately sensitive to the number of topics, VODUM obtaining be er performance for lower number of topics on both datasets.

Hypothesis (H1c) is also validated by the observation that GPUbased models SNVDM-GPU (τ = 10) and SNVDM-GPU (τ = ∞) attained slightly higher clustering performance than that of SNVDM. However, note that SNVDM-GPU (τ = 10) only signi cantly outperforms SNVDM at signi cance level α = 0.05 on the Midterms dataset: on Indyref their 95% con dence intervals intersect both for Purity and NMI and the di erence is therefore not signi cant. We suspect the large number of interactions in the Indyref dataset to be responsible for the similar clustering results of SN-LDA, SNVDM, SNVDM-GPU (τ = 10) and SNVDM-GPU (τ = ∞). We therefore investigate in the next section to what extent these models are robust to data with less interactions, i.e., sparser social networks.

Robustness to Network Sparsity.

In order study the robustness of models to sparse interactions, we arti cially included di erent percentages of the interactions (100%, 50%, 25%, and 10%) that are available in the Indyref dataset.

e interactions to be removed -either incoming or outgoing ones -were randomly chosen. en, for the obtained datasets derived from Indyref (identical for all evaluated models), we analyzed the viewpoint clustering performance of SN-LDA, SNVDM, SNVDM-GPU (τ = 10) and SNVDM-GPU (τ = ∞). Given that the number of topics only has a e ect on the performance, as observed in Section 4.2.1, we set T = 10 in this experiment. e results are shown in Table 4. Here as well, we provide the 95% con dence interval about the mean. We observe a similar trend for all models: the clustering performance is substantially degraded for low percentage of interactions, especially 10%. is stresses again that interactions are key to the identi cation of viewpoints in a social network.

Overall, in this studied case, GPU-based models are only marginally more robust to sparsity than other models, with signi cant improvements only over SN-LDA for 100%, 50%, and 25%; this observation thus merely provides weak support to hypothesis (H2). However, interestingly, SNVDM-GPU (τ = 10) seems to be more robust to interaction sparsity than SNVDM-GPU (τ = ∞): from 50% and below, SNVDM-GPU (τ = 10) performed slightly be er. is may be explained by the fact that SNVDM-GPU (τ = 10) is more selective than SNVDM-GPU (τ = ∞) on interacting users: the former uses only the 10 most interacting acquaintances, while the la er leverages all available acquaintances.

E ciency

We discuss in this section the e ciency in terms of execution time for the baselines and the proposed models. e machine used to perform the experiments is a laptop with eight i7-4700MQ CPUs at 2.40 GHz (although our implementation is not parallelized) and 8GB

We report in Table 5 the time (in seconds) taken by one Gibbs sampling iteration on Indyref (with T = 10) and Midterms (with T = 15). While we observe that the SN-LDA and TAM implementations are faster, the execution times for SNVDM and SNVDM-GPU (τ = 10) are on the same order of magnitude: at most about 2 and 3 times slower, respectively. e execution times on Midterms are very similar for all models, which is explained by the lower number of interactions. With more interactions, the di erence is greater on Indyref. Indeed, SNVDM-based and especially GPU-based models are highly dependent on interactions. is is con rmed by the very slow execution time of SNVDM-GPU (τ = ∞) on Indyref. On the contrary, we see that SNVDM-GPU (τ = 10) ran in reasonable time due to the more restrictive selection of related users; this model is therefore a good tradeo between e ectiveness and e ciency.

Discovered Viewpoints and Topics

In topic modeling literature, the traditional method to study the discovered topics' quality is to analyze the coherence of the top words (i.e., most probable words) for the topic-speci c distributions over words. Based on these top words, topic coherence metrics have been proposed (e.g., in [START_REF] Mimno | Optimizing Semantic Coherence in Topic Models[END_REF]) to quantitatively compare the topics' quality across di erent models. However, the models and baselines we wish to compare here have di erent distributions over words. For example, SN-LDA only has topic-speci c distributions over words, while SNVDM-based models distinguish between four types of words, as described in Section 3.2.1: background words (drawn from ϕ 00 ), viewpoint words (drawn from ϕ 01 ), topic words (drawn from ϕ 10 ), and viewpoint-topic words (drawn from ϕ 11 ). Consequently, topic coherence metrics cannot be applied to compare the topics' quality of our models and baselines. For that reason, we choose to provide in this section a qualitative analysis of the topics and viewpoints discovered by our models.

It is particularly interesting to study for a same topic the topic words as well as the viewpoint words for the di erent viewpoints: this enables the comparison between neutral word usage against subjective word usage. erefore, we selected one topic discovered by our most e ective model SNVDM-GPU (τ = ∞) in each dataset, Indyref (with T = 10) and Midterms (with T = 15), and display its top 10 topic words as well as its top 10 viewpoint-topic words speci c to "Yes"/"No" supporters in Table 6 and Democrats/Republicans in Table 7, respectively. Note that the topics were manually labeled.

Table 6 shows the top words for a central topic in the Indyref dataset: the question of the Sco ish independence. As expected, discovered topic words focus only on neutral aspects such as the referendum (#indyref, vote, campaign). On the contrary, pro-Yes and pro-No viewpoints are clearly re ected in viewpoint-topic words. "Yes" supporters use speci c hashtags such as #voteyes and #yes. On the other hand, "No" supporters use #be ertogether, which was the mo o of the pro-No side. Moreover, "No" supporters seem to raise the issue of the currency in case of separation. In Table 7, we reported the top words about energy and resources discovered in the Midterms dataset. is topic showcases a striking di erence in Democratic and Republican discourse. Democrats talk about environmental issues, with hashtags such as #actonclimate and (a) Purity results on Indyref. (b) NMI results on Indyref. (c) Purity results on Midterms. τ = 10) 0.704 ± 0.097 0.149 ± 0.121 0.938 ± 0.008 0.666 ± 0.031 0.951 ± 0.007 0.720 ± 0.031 0.958 ± 0.004 0.749 ± 0.019 SNVDM-GPU (τ = ∞) 0.687 ± 0.125 0.139 ± 0.117 0.900 ± 0.041 0.546 ± 0.107 0.958 ± 0.003 0.752 ± 0.014 0.964 ± 0.002 0.776 ± 0.010 #climatechange, while republicans focus on the economic impact such as jobs and bills. Overall, we observe that the discovered topics and viewpoints are reasonably coherent, which con rms (H4).

CONCLUSION AND FUTURE WORK

In this paper, we introduced a novel topic model for viewpoint discovery in social networks, namely SNVDM, and its extension based on the generalized Pólya urn (GPU) scheme. We showed throughout extensive experiments on two di erent Twi er datasets that our proposed models signi cantly outperform state-of-the-art models in a viewpoint clustering task. e experiments thereby underlined that leveraging both incoming and outgoing interactions as well as exploiting the GPU scheme lead to signi cant improvement in terms of Purity and Normalized Mutual Information. is conrms previous ndings which highlighted the key importance of social interactions to discovering viewpoints [START_REF] Magdy | #ISISisNotIslam or #DeportAllMuslims? Predicting Unspoken Views[END_REF]. Additionally, the GPU scheme was found to slightly improve the robustness to social network sparsity. Moreover, proposed models SNVDM and SNVDM-GPU (τ = 10) were shown to be comparably e cient to baselines, thus constituting good tradeo s between e ciency and e ectiveness. e discovered topics and viewpoints were also observed to be reasonably coherent.

Although our approach is widely applicable to study viewpoints in social networks, one of its limitations is that it is most e ective for users that are strongly engaged (i.e., users who post and interact a lot). To study less active users' viewpoints, post-level (e.g., tweetlevel) techniques may complement our approach.

In future work, we plan to extend our proposed models and account for the temporal evolution of viewpoints, in order to illustrate the trends of topics and underlying views concurring with current events. Another interesting research direction would be to leverage users' geolocation (e.g., as in [START_REF] Hong | Discovering Geographical Topics In e Twi er Stream[END_REF]) and explore region-level viewpoints. Eventually, we aim to devise an unbiased viewpoint summarization framework for social media to provide balanced viewpoints and thus mitigate the " lter bubble" e ect.

ud e viewpoint assignment

  for document d from user u. ruo , ′ uo e recipient and the viewpoint assignment, resp., for outgoing interaction o of user u. ϕ00, ϕ01, ϕ10, ϕ11, β 1 × W matrix of background word distributions, V × W matrix of viewpoint word distributions, T × W matrix of topic word distributions, V × T × W matrix of viewpoint-topic word distributions, and their concentration parameter, resp.ψ0, ψ1, γ0, γ11 × 2 matrix of general route distribution, T × 2 matrix of topicspeci c route distributions, and their shape parameters, resp.ξ , µ V × U matrix of viewpoint-speci c interacting user distributions, and their concentration parameter, resp.σ , δ0, δ1 V × U matrix of user-speci c level distributions, and their shape parameters, resp.θ , α U × T matrix of user-speci c topic distributions and their concentration parameter, resp.π , η U × V matrix of user-speci c viewpoint distributions and their concentration parameter, resp. n00w , n01 w , n10zw , n11 zw Number of background instances of word w, number of viewpoint instances of word w assigned to , number of topic instances of word w assigned to z, number of viewpoint/topic instances of word w assigned to and z, resp. n0x , n1zx Number of words assigned to level 0 and route x and number of words assigned to level 1, topic z, and route x, resp. n u Number of interactions with interacting user u assigned to viewpoint . n ul Number of words from user u assigned to level l. nuz Number of words from user u assigned to topic z. nu Number of documents and outgoing interactions from user u assigned to viewpoint .

3. 2 . 1 Nu

 21 Model Definition. Before providing a more formal description of our proposed Social Network Viewpoint Discovery Model1+T

Figure 1 :

 1 Figure1: Graphical models for TAM (a), SN-LDA (b), and our proposed model SNVDM (c). e original variable names for TAM and SN-LDA were slightly modi ed from[START_REF] Paul | A Two-Dimensional Topic-Aspect Model for Discovering Multi-Faceted Topics[END_REF] and[START_REF] Sachan | Spatial Compactness meets Topical Consistency: Jointly modeling Links and Content for Community Detection[END_REF], respectively, to facilitate their comparison against SNVDM.

  ) For each document d = 1, ..., D u from u = 1, ..., U : (a) Draw a document viewpoint ud ∼ Discrete(π u ); (b) For each token n = 1, ..., N ud : (i) Draw a topic z ud n ∼ Discrete(θ u ); (ii) Draw a level l ud n ∼ Discrete(σ u ); (iii) If l ud n = 0, draw a general route x ud n ∼ Discrete(ψ 0 ); Else if l ud n = 1, draw a topic-speci c route x ud n ∼ Discrete(ψ 1z ud n ); (iv) If l ud n = 0 and x ud n = 0, draw a background word w ud n ∼ Discrete(ϕ 00 ); Else if l ud n = 0 and x ud n = 1, draw a viewpoint word w ud n ∼ Discrete(ϕ 01 ud ); Else if l ud n = 1 and x ud n = 0, draw a topic word w ud n ∼ Discrete(ϕ 10z ud n ); Else if l ud n = 1 and x ud n = 1, draw a viewpoint-topic word w ud n ∼ Discrete(ϕ 11 ud z ud n ); (c) For each incoming interaction i = 1, ..., I ud , draw sender s ud i ∼ Discrete(ξ ud ); (6) For each outgoing interaction o = 1, ..., O u from u = 1, ..., U : (a) Draw an outgoing interaction viewpoint ′ uo ∼ Discrete(π u ); (b) Draw a recipient r uo ∼ Discrete(ξ ′ uo ).

  (τ = 10) SNVDM-GPU (τ = ∞) (d) NMI results on Midterms.

Figure 2 :

 2 Figure2: Viewpoint clustering results on Indyref (2a, 2b) and Midterms (2c, 2d) datasets in terms of Purity (2a, 2c) and NMI (2b, 2d) for di erent number of topics(5, 10, 15, and 20). Higher is better. Error bars denote 95% con dence intervals around the mean computed from 5 executions.

Table 5 :

 5 Execution time (in seconds) of one Gibbs sampling iteration for models TAM, SN-LDA, VODUM, SNVDM-WII, SNVDM, SNVDM-GPU (τ = 10) and SNVDM-GPU (τ = ∞) on Indyref (with T = 10) and Midterms (with T = 15).

Table 1 :

 1 Comparison of our models SNVDM and SNVDM-GPU against related work approaches.

		Application	Use of social
	Reference	to social	networking
		media	interactions

Table 2 :

 2 De nition of the notations used in the paper.Number of users, number of documents from u, number of outgoing interactions for u, number of tokens for u and d, number of incoming interactions for u and d, resp.

	Symbol	De nition
	U , Du , Ou ,
	N ud , I ud

T , V , W Number of topics, number of viewpoints, and number of words in the vocabulary, resp.

Table 3 :

 3 Statistics of the datasets used in the experiments. Yes and No, respectively expressing support and opposition to Sco ish independence. e second dataset, therea er denoted as Midterms, is constituted of the tweets wri en by the policy makers who were active during the 2014 U.S. Midterm Election. Note that, in order to extend the Midterms dataset, we used users' full Twi er timelines (until 21/11/2014) instead of restricting to the tweets posted during the Midterm Election timespan. Only Democratic and Republican users appear in the dataset. For both datasets, users' groundtruth viewpoints were originally obtained in

	Dataset	#Users	#Tweets #Tokens Vocabulary #Interactions
		Yes/Dem. No/Rep.
	Indyref	589	575 270,075 2,043,204	38,942	696,654
	Midterms	767	778 113,545	975,199	25,312	241,741
	contains tweets about the 2014 Sco ish Independence Referendum
	posted between 11/08/2014 and 20/10/2014. e two represented
	viewpoints are

Table 4 :

 4 Viewpoint clustering results in terms of Purity and NMI on Indyref for di erent percentages of social interactions (100%, 50%, 25%, and 10%). Higher is better, best scores are in boldface. Errors denote 95% con dence intervals around the mean computed from 5 executions. ± 0.113 0.087 ± 0.089 0.795 ± 0.056 0.283 ± 0.083 0.863 ± 0.026 0.433 ± 0.045 0.917 ± 0.002 0.588 ± 0.008 SNVDM 0.621 ± 0.148 0.082 ± 0.136 0.912 ± 0.043 0.580 ± 0.135 0.946 ± 0.017 0.702 ± 0.066 0.957 ± 0.002 0.748 ± 0.011 SNVDM-GPU (

	Model	10% interactions used	25% interactions used	50% interactions used	100% interactions used
		Purity	NMI	Purity	NMI	Purity	NMI	Purity	NMI
	SN-LDA	0.644

Table 6 :

 6 e top 10 topic words (1st column) and viewpoint-topic words for "Yes" supporters (2nd column) and "No" supporters (3rd column) about Sco ish independence discovered by SNVDM-GPU (τ = ∞) on Indyref.

				Topic: Sco ish independence
					Viewpoint: Yes Viewpoint: No
		Indyref Midterms	#indyref	#voteyes	#indyref
	TAM SN-LDA VODUM SNVDM-WII SNVDM SNVDM-GPU (τ = 10) SNVDM-GPU (τ = ∞)	1.45 1.18 2.78 2.08 2.49 3.47 14.67	0.87 0.64 1.85 1.08 1.15 1.34 2.56	scotland independence scotland yes vote independence campaign westminster sco ish vote uk independent people country future #yes	uk salmond #be ertogether #scotdecides separation currency thanks today
				independent	#scotland	say

Table 7 :

 7 e top 10 topic words (1st column) and viewpoint-topic words for Democrats (2nd column) and Republicans (3rd column) about Energy and ressources discovered by SNVDM-GPU (τ = ∞) on Midterms.

	energy	#actonclimate	#4jobs
	house	climate	#obamacare
	new	#p2	#jobs
	gas	change	gop
	natural	#climatechange	obama
	#energy	clean	bills
	#	oil	jobs
	#kxl	energy	house
	support	#gop	act
	economic seec	watch

Topic: Energy and resources

Viewpoint: Dem. Viewpoint: Rep.

ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or a liate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only. CIKM'17, November 6-10, 2017, Singapore. © 2017 ACM. ISBN 978-1-4503-4918-5/17/11. . . $15.00 DOI: h ps://doi.org/10.1145/3132847.3132897

h p://dx.doi.org/10.6084/m9. gshare.1430449

h p://alias-i.com/lingpipe/

h p://www.cs.cmu.edu/ ∼ ark/TweetNLP/

ACKNOWLEDGMENTS

We would like to thank Éric Gaussier and Igor Brigadir for their valuable comments and helpful suggestions. is work was partially supported by the French National Research Agency under project LisTIC (ANR-16-CE26-0014-01).