Quantifying Political Polarity Based on Bipartite Opinion Networks
(2014)

Political inclinations of individuals (liberal vs. conservative) largely shape their opinions on several issues such as abortion, gun control, nuclear power, etc. These opinions are openly exerted in online forums, news sites, the parliament, and so on. In this paper, we address the problem of quantifying political polarity of individuals and of political issues for classification and ranking. We use signed bipartite networks to represent the opinions of individuals on issues, and formulate the problem as a node classification task. We propose a linear algorithm that exploits network effects to learn both the polarity labels as well as the rankings of people and issues in a completely unsupervised manner. Through extensive experiments we demonstrate that our proposed method provides an effective, fast, and easy-to-implement solution, while outperforming three existing baseline algorithms adapted to signed networks, on real political forum and US Congress datasets. Experiments on a wide variety of synthetic graphs with varying polarity and degree distributions of the nodes further demonstrate the robustness of our approach. Introduction Many individuals use online media to exert their opinions on a variety of topics. Hotly debated topics include liberal vs. conservative policies such as tax cuts and gun control, social issues such as abortion and same-sex marriage, environmental issues such as climate change and nuclear power plants, etc. These openly debated issues in blogs, forums, and news websites shape the nature of public opinion and affect the direction of politics, media, and public policy. In this paper, we address the problem of quantifying political polarity in opinion datasets. Given a set of individuals from two opposing camps (liberal vs. conservative) debating a set of issues or exerting opinions on a set of subjects (e.g. human subjects, political issues, congressional bills), we aim to address two problems: (1) classify which person lies in which camp, and which subjects are favored by each camp; and (2) rank the people and the subjects by the magnitude or extent of their polarity. Here while the classification enables us to determine the two camps, ranking helps us understand the extremity to which a person/subject is polarized; e.g. same-sex marriage may be highly polarized among the Copyright c © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. two camps (liberals being strictly in favor, and conservatives strictly being against), while gun control may not belong to a camp fully favoring or opposing it (i.e., is less polarized). Ranking also helps differentiate moderate vs. extreme individuals, as well as unifying vs. polarizing subjects; such as (unifying) bills voted in the same way, e.g. all ‘yea’ by the majority of congressmen vs. (polarizing) bills that are voted quite oppositely by the two camps. A large body of prior research focuses on sentiment analysis on politically oriented text (Cohen and Ruths 2013; Conover et al. 2011b; 2011a; Pak and Paroubek 2010; Tumasjan et al. 2010). The main goal of these works is to classify political text. In this work, on the other hand, we deal with network data to classify its nodes. Moreover, these methods mostly rely on supervised techniques whereas we focus on un/semi-supervised classification. Other prior research on polarization have exploited link mining and graph clustering to study the social structure on social media networks (Adamic and Glance 2005; Livne et al. 2011; Conover et al. 2011b; Guerra et al. 2013) where the edges depict the ‘mention’ or ‘hyperlink’ relations and not opinions. Moreover, these works do not perform ranking. Different from previous works, our key approach is to exploit network effects to both classify and rank individuals and political subjects by their polarity. The opinion datasets can be effectively represented as signed bipartite networks, where one set of nodes represent individuals, the other set represent subjects, and signed edges between the individuals and subjects depict the +/− opinions. As such, we cast the problem as a node classification task on such networks. Our main contributions can be summarized as follows: • We cast the political polarity classification and ranking problem as a node classification task on edge-signed bipartite opinion networks. • We propose an algorithm, called signed polarity propagation (SPP), that computes probabilities (i.e., polarity scores) of nodes of belonging to one of two classes (e.g., liberal vs. conservative), and use these scores for classification and ranking. Our method is easy-to-implement and fast—running time grows linearly with network size. • We show the effectiveness of our algorithm, in terms of both prediction and ranking, on synthetic and real datasets with ground truth from the US Congress and Political Forum. Further, we modify three existing algorithms to handle signed networks, and compare them to SPP. Our experiments reveal the advantages and robustness of our method on diverse settings with various polarity and degree distributions. Related Work Scoring and ranking the nodes of a graph based on the network structure has been studied extensively, with wellknown algorithms like PageRank (Brin and Page 1998), and HITS (Kleinberg 1998). These, however, are applied on graphs where the edges are unsigned and therefore cannot be directly used to compute polarity scores. Computing polarity scores can be cast as a network classification problem, where the task is to assign probabilities (i.e., scores) to nodes of belonging to one of two classes, which is the main approach we take in our work. There exist a large body of work on network-based classification (Getoor et al. 2007; Neville and Jensen 2003; Macskassy and Provost 2003). Semi-supervised algorithms based on network propagation have also been used in classifying political orientation (Lin and Cohen 2008; Zhou, Resnick, and Mei 2011). However, all the existing methods work with unsigned graphs in which the edges do not represent opinions but simply relational connections such as HTML hyperlinks between blog articles or ‘mention’ relations in Twitter. Signed networks have only recently attracted attention (Leskovec, Huttenlocher, and Kleinberg 2010b). Most existing studies focused on tackling the edge sign prediction problem (Yang et al. 2012; Chiang et al. 2011; Leskovec, Huttenlocher, and Kleinberg 2010a; Symeonidis, Tiakas, and Manolopoulos 2010). Other works include the study of trust/distrust propagation (Guha et al. 2004; DuBois, Golbeck, and Srinivasan 2011; Huang et al. 2012), and product/merchant quality estimation from reviews (McGlohon, Glance, and Reiter 2010). These works do not address the problem of classifying and ranking nodes in signed graphs. With respect to studies on political orientation through social media, (Adamic and Glance 2005; Adar et al. 2004) use link mining and graph clustering to analyze political communities in the blogosphere. While these and most clustering algorithms are designed to work with unsigned graphs, there also exist approaches for clustering signed graphs (Traag and Bruggeman 2009; Lo et al. 2013; Zhang et al. 2013). Clustering, however, falls short in scoring the nodes and hence quantifying polarity for ranking. Related, (Livne et al. 2011) utilize graph and text mining techniques to analyze differences between political parties and their online media usage in conveying a cohesive message. Most recently, (Cohen and Ruths 2013) use supervised classification techniques to classify three groups of Twitter users with varying political activity (figures, active, and modest) by their political orientation. Other works that exploit supervised classification using text features include (Conover et al. 2011a; Golbeck and Hansen 2011; Pennacchiotti and Popescu 2011). Similar to (Adamic and Glance 2005), there exist related works that study the social structure for measuring polarity. These works rely on the existence of (unsigned) social links between the users of social media and study the communities induced by polarized debate; an immediate consequence of the homophily principle, which states that people with similar beliefs and opinions tend to establish social ties. (Livne et al. 2011) and (Conover et al. 2011b) both use modularity (Newman 2006) as a measure of segregation between political groups in Twitter. (Guerra et al. 2013) compare modularity of polarized and non-polarized networks and propose two new measures of polarity based on community boundaries. Again, these works do not study the opinion networks with signed edges. As our main task is quantifying polarity, work on sentiment analysis is also related. There exist a long list of works on sentiment and polarity prediction in political text (Tumasjan et al. 2010; Awadallah, Ramanath, and Weikum 2010; Conover et al. 2011b; He et al. 2012), as well as in tweets, blogs, and news articles (Pak and Paroubek 2010; Godbole, Srinivasaiah, and Skiena 2007; Thomas, Pang, and Lee 2006; Balasubramanyan et al. 2012). These differ from our work as they use text-based sentiment analysis, while we focus on the network effects in signed graphs. Proposed Method Problem Overview We consider the problem of polarity prediction and ranking in opinion datasets (e.g. forums, blogs, the congress). Opinion datasets mainly consist of a set of people (e.g. users in a forum, representatives in The House) and a set of subjects (e.g. political issues, political people, congressional bills). Each person often maintains a positive or negative opinion toward a particular subject (e.g. a representative votes ‘yes’ for a bill, a person ‘likes’ a political individual). This opinion is often an exposition of the person’s latent political leaning—liberal or conservative. For example, we could think of a person with strong negative opinion toward gay&lesbian rights to be more conservati