1. Introduction

1Sentiment Analysis (SA) (Pang and Lee, 2008) faces the problem of deciding whether a text expresses a sentiment, e.g. positivity or negativity. Social Media are observed to measure the sentiment expressed in the Web about products, companies or politicians. The interest in the analysis of tweets led to the definition of highly participated challenges, e.g. (Rosenthal et al., 2014) or (Basile et al., 2014). Machine Learning (ML) approaches are often adopted to classify the sentiment (Pang et al., 2002; Castellucci et al., 2014; Kiritchenko et al., 2014), where specific representations and hand-coded resources (Stone et al., 1966; Wilson et al., 2005; Esuli and Sebastiani, 2006) are used to train some classifier. As tweets are very short, the amount of available information for ML approaches is in general not sufficient for a robust decision. A valid strategy (Vanzo et al., 2014b; Vanzo et al., 2014a) exploits Contextual information, e.g. the reply-to chain, to support a robust sentiment recognition in online discussions.

2In this paper, we foster the idea that Twitter messages belong to a network where complex interactions between messages are available. As suggested in (Speriosu et al., 2011), tweets can be represented in graph structures, along with words, hashtags or users. A Label Propagation algorithm (Zhu and Ghahramani, 2002; Talukdar and Crammer, 2009) can be adopted to propagate (possibly noisy) sentiment labels within the graph. In (Speriosu et al., 2011), it has been shown that such approach can support SA by determining how messages, words, hashtags and users influence each other. The definition of the graph is fundamental for the resulting inference, e.g. when mixing messages about different topics, sentiment detection can be difficult. We take inspiration from the contexts defined in (Vanzo et al., 2014b). In (Speriosu et al., 2011) no explicit relation between messages is considered. We, instead, build a graph where messages in the same context are linked each other and to the words appearing in them. Moreover, we inject prior polarity of words as available in a polarity lexicon (Castellucci et al., 2015). Experiments are carried out over a subset of the Evalita 2014 Sentipolc (Basile et al., 2014) dataset, showing improvements in the polarity classification with respect to not using networked information.

3In the remaining, Section 2 presents our graphbased approach. In Section 3 we evaluate the proposed method with respect to a dataset in Italian and we derive the conclusions in Section 4.

2. Sentiment Analysis through Label Propagation over Contextual Graphs

4Twitter messages are not created in isolation, but they live in conversations (Vanzo et al., 2014b; Vanzo et al., 2014a). Graph based methods (Zhu and Ghahramani, 2002; Talukdar and Crammer, 2009) provide a natural way to represent tweets in a graph structure in order to exploit relationships between messages to support the SA task.

2.1 Label Propagation Algorithms

5In a classification task, given a graph representing a set of objects whose classes are known (labeled seeds) and a set of unlabeled objects, Label Propagation (LP) algorithms spread the label distribution by exploiting the underlying graph. Labels

6are spread over a graph 𝔾 = 〈V, E, W〉, where V is a set of n nodes, E is a set of edges and W is an n × n matrix of weights, i.e. w_ij is the weight of the edge between nodes i and j.

7The Modified Adsorption (MAD) algorithm (Talukdar and Crammer, 2009) is a particular LP algorithm where the spreading of label distributions provides the labeling of all the nodes in the graph, possibly re-labeling also the seeded ones in order to improve robustness against outliers. MAD is defined starting from the Adsorption algorithm (Baluja et al., 2008), where the labeling of all the nodes in a graph is modeled as a controlled random walk. Three actions drive this random walk: inject a seeded node with its seed label; continue the walk from the current node to a neighbor; abandon the walk. These actions are modeled in the MAD algorithm through a minimization problem whose objective function is:

8    (1)

9where S, L and R are matrices whose role is to model respectively the relationships between a node and its prior labels, the relationships between two similar nodes and the regularization imposed to the labeling of nodes¹. The objective function aims at imposing the following constraints to the labeling process with these three terms: the algorithm should assign to a labeled vertex l a distribution w.r.t. the target classes that is close to the a-priori distribution (); moreover, if two nodes are close according to the graph, then their labeling should be similar. Finally, the third term is a regularization factor. More details about MAD are reported in (Talukdar and Crammer, 2009).

10In our approach, the MAD algorithm is applied to a graph where each node is labeled with a distribution over some polarity classes². We assume that a subset of the messages have been annotated, and they are used to train a classifier f that ignore the graph structure. The function f is then used to label the remaining messages so that the MAD algorithm is used to determine the final polarities based on the graph structure.

2.2 Contextual Graph: a definition

11In order to generalize the contextual models proposed in (Vanzo et al., 2014b), we build a Contextual Graph G of messages as following. Given a message t_j we consider its context C(t_j) as the list of l preceding messages t_j−1, t_j−2, ... , t_j−l. The context can be defined as the reply-to chain of messages (conversation context) or the temporally preceding messages sharing at least one hashtag (hashtag context). The contextual graph G is then built by considering pairs of messages (t_o,t_n) in a context, i.e. t_o,t_n ∈ C(t_j). These are linked with an edge whose weight w_to,tn is computed through a function that depends from the distance between t_o and t_n. In particular, we choose w_to,tn = e^−λ|o−n|, where λ controls="true" the influence of messages at different distances. These weighted edges are meant to capture the interaction between close messages in the context. We augment the set of vertices V with nodes representing the words appearing in messages. In particular, given r₁,r₂,...,r_k as the words composing t_o, we add k nodes to V , each representing a word r_i. Each word node is connected to its message and the weight w_to,ri is computed through the σ(t_o,r_i) function³. Word nodes are intended to make the graph connected: without them the graph would be composed by many disconnected sub-graphs, i.e. one per context. Moreover, the more words two messages share, the more they are conveying a similar message. Finally, we define the set of seed nodes as a subset of V that are associated to prior labels. As discussed in the next section, these can be either messages or words: the former are seeded through noisy labels computed from a classification function f; the latter are seeded through label distributions derived from a polarity lexicon.

3. Experimental Evaluation

12In order to evaluate the Contextual Graph and the MAD algorithm, we adopted a subset of the Evalita 2014 Sentipolc dataset (Basile et al., 2014). It consists of short messages annotated with the subjectivity, polarity and irony classes. We selected those messages annotated with polarity and that were not expressing any ironic content to focus our investigations on less ambiguous messages. Thus, the datasets used for our evaluations consist of a training set Tr of 2,449 messages and a testing set Ts of 1,129 messages.

13As in (Vanzo et al., 2014b), we downloaded the conversation and hashtag contexts that were available at the time of downloading⁴. In Table 1 the number of messages involved in the different contexts are shown. In the experiments, messages are classified with respect to the positive, negative and neutral polarity classes. The message distribution with respect to these classes is shown in Table 2.

3.1 Graph Construction

14In the Contextual Graph, vertices represent messages and auxiliary information, such as words. In the LP algorithm each vertex can become a seed, i.e. a distribution w.r.t. the polarity classes can be assigned to it. We first investigate a configuration in which only messages are seeded. Experiments are carried out on three types of Contextual Graphs. In the first experiment a graph is built by considering contexts where messages are in a reply-to relationship, namely conversation graph. A second experiment considers instead the hashtag contexts, where messages share at least one hashtag. A third experiment considers both conversation and hashtag contexts in the same graph representation. In these configurations, vertices representing words are added to the graph but they are not “seeded” (i.e. they are considered as unlabeled nodes). In the fourth experiment, the last graph is enriched by electing as seeds also words whose sentiment polarity is known a-priori, e.g. derived by a polarity lexicon. In the following, we describe how to associate polarity distributions both to messages and words.

15Message seeding. A classification function f that feeds the label distributions for messages is derived by a supervised learning process. In particular, we consider the training set Tr described above, and we acquire a Support Vector Machine multi-classifier in a One-Vs-All schema for the positive, negative and neutral polarity classes as in (Castellucci et al., 2014). Two types of features are adopted: the first is a boolean Bagof-Words (BOW) feature set. The second is a Wordspace (WS) feature set derived from vector representations of the words in a message, obtained through a neural word embedding (Mikolov et al., 2013). We acquired the embedding from a corpus of 10 million tweets downloaded during the first months of 2015. A skip-gram model is acquired through the word2vec⁵ tool and deriving⁶ 250-dimensional vectors for about 99,410 words. The WS feature set for a message t_j is obtained by considering the linear combination of word vectors that appear in t_j. The SVM classifier realizes the function f that assign the initial label distribution, reflecting the classifier confidence in assigning a polarity to each message, i.e. belonging to both train and test datasets, as well as belonging to contexts.

16Words seeding. Seeds words are also considered when building the Contextual Graph. In particular, we adopt the Distributional Polarity Lexicon (DPL) (Castellucci et al., 2015) that associates each word to the prior information about the positivity, negativity and neutrality. The lexicon is built as follows: a classifier d is acquired from a dataset of generic messages gathered by Twitter considering the occurrence of noisy labels, i.e. emoticons expressing positivity, negativity or neutrality. In a nutshell, given the properties of the vector space WS, we project sentences and words in the same space, in order to transfer the polarity from sentences to words via the classifier d and obtaining the polarity scores of the DPL. The positivity and negativity scores of a word in DPL are used as seed distribution in the MAD algorithm.

3.2 Experimental Results

17A first measure is given by the SVM classifier that is used to assign a polarity distribution to seeds belonging to the test dataset. We measure the mean between the F1 scores of the positive and negative classes (F1-Pn), and the mean between the F1 scores of all the three classes (F1-Pnn). Different feature representations are exploited in the SVM evaluation, as pointed out in Table 3.

18Table 3: SVM results (w/o contexts).

19When adopting also the WS features, the performance increases in both the performance measures, with respect to the setting where only BOW features are considered.

20In Tables 4 and 5 the MAD algorithm results⁷ are reported w.r.t. the Conversation and Hashtag contexts, as well to different context sizes, e.g. at size 3 we consider a maximum of 2 messages preceding a target one. The MAD algorithm is able to consistently increase the F1-Pn performance measure, while it is equally performing in the F1-Pnn. When adopting the Hashtag context, performances are higher w.r.t. the Conversation context setting. This is probably due to the fact the only 15% of the messages belong to a reply-to chain, while about 40% of the message belong to a Hashtag context. Moreover, Hashtag contexts refer to more coherent sets of messages. It makes the LP algorithm better exploit the graph by assigning similar labeling to nodes in the Hashtag context.

21In Table 6 we applied the MAD algorithm over a graph built considering both contexts: in this scenario, we tuned and adopted two distinct λ values, i.e. λ_c and λ_h, respectively when weighting messages in conversation and hashtag contexts. Again, the contribution of the contextual information is measured through an increment of both the performance measures. Moreover, the contribution of the two contexts allows to further push the performances up, confirming the need of additional information when dealing with such short messages.

22Finally, we injected seed distributions over words through the Distributional Polarity Lexicon (DPL). The lexicon allows injecting a-priori seed on the words in the Contextual Graph, resulting in higher performances w.r.t. the case without DPL.

4. Conclusion

23In this paper, the Contextual Graph is defined as a structure where messages can influence each other by considering both intra-context and extracontext links: the former are links between messages, while the latter serves to link messages in different contexts through shared words. The application of a Label Propagation algorithm confirms the positive impact of contextual information in the Sentiment Analysis task over Social Media. We successfully injected prior polarity information of words in the graph, obtaining further improvements. This is our first investigation in graph approaches for SA: we only adopted the MAD algorithm, while other algorithms have been defined, since (Zhu and Ghahramani, 2002) and they will be investigated in future works. Moreover, other contextual information could be adopted. Finally, other datasets should be considered, proving the effectiveness of the proposed method that does not strictly depend on the language of messages.