Representativeness-aware Aspect Analysis for Brand Monitoring in Social Media

1 Introduction

Nowadays, more and more people express their opinions on social media sites like Facebook and Twitter. The fastresponding and broad diffusion nature of those social media sites bring about an increasing demand for companies to monitor the reputation of their brands and the reception by general public. Recent studies by [Glance et al., 2005; Haruechaiyasak et al., 2013] have verified that brand monitoring over social media streams can help companies maintain harmonious relationships with customers and protect their reputations.

Studies related to brand monitoring have been carried out at the document, sentence and aspect levels. Aspect-level analysis is often desired as it provides more fine-grained information about a brand. Figure 1 shows an illustrative example of users' tweets about StarHub, a telecommunication company. Looking into the tweets, we can see that the first user prefers "more data" over "unlimited sms"; here we denote such noun or noun phrases as aspect candidates. In addition, the relatively large number of retweets and likes reveals that the post has been well recognized by other users. This provides an important evidence for StarHub to identify customer needs and improve their services. While it seems to be easy for human to distinguish such users' preference from texts, it is non-trivial for machines to automatically figure it out. One of the key challenges lies in identifying the representative aspects which not only cover detailed information but also represent customers' intent [Liao et al., 2016]. In this case, data usage is more appropriate than sms and other less indicative aspects. If a company can automatically identify the representative aspects from the fast-evolving social media data, the company can perform fine-grained aspect-level analysis and react to customers' response timely [Zhang et al., 2016a].

∗The corresponding author is Xiangnan He.

Previous studies on aspect identification have treated it as a traditional text analysis task, which either developed some language rules to extract featured terms as aspects [Hu and Liu, 2004; Liu et al., 2015] or grouped terms into aspects with statistical topic models [Paul and Girju, 2010; Ren et al., 2016]. These methods, however, usually work on well-structured data such as the customer reviews and do not consider the varying impacts of posts. Intuitively, posts that are more influential (e.g., voted by many users) should raise more concerns about the respective aspects that they refer to. In addition to identifying salient aspects, it is beneficial to also select posts that are most representative of the data collection, which can assist companies in making decisions. This is related to another line of previous research, i.e. extractive summarization; which aims to select important sentences from documents. However, existing efforts have mainly focused on documents instead of short posts in social media.

Targeting at brand monitoring, we highlight two requirements other than simply extracting a set of representative aspects and posts. First, companies may change their focus of monitoring dynamically. For example, after launching a new product, the company would like to know customers' response to it. Thus, the algorithm should have the flexibility to be easily guided towards specific aspects. Second, to provide brand monitoring service online, there is often a need to sift through a huge amount of data and respond quickly [He et al., 2016]. Thus, the algorithm needs to be efficient. In this paper, we tackle the above challenges by developing a new method to automatically select representative aspects and posts from social media. We first define a new notion of representativeness of aspect, which can help companies re-adjust their focus of brand monitoring dynamically. Next, we formulate the task as a submodular optimization problem, and design an efficient greedy algorithm named FastPAS (short for Fast Posts and Aspects Selection), which can compute a near-optimal solution with theoretical guarantees. Extensive experiments on two Twitter datasets show that our method outperforms existing information extraction methods. In addition, our results suggest that monitoring the competitors' brands might also benefit one's own brand monitoring in social media.

2 RelatedWork

Existing studies on aspect identification (or aspect extraction) can be categorized into two types. The first type of work treats an aspect as a term, usually a noun or noun phrase that describes the specific properties of products. For example, early approaches [Hu and Liu, 2004; Popescu and Etzioni, 2005] extract aspects by considering the term frequency and leveraging dependency relation rules; other approaches [Kobayashi et al., 2007; Jakob and Gurevych, 2010] model it as a sequence labeling task, applying hidden markov model and conditional random field for aspect identification. The second type of work treats an aspect as a group of terms [Moghaddam and Ester, 2012], for example, [Paul and Girju, 2010] utilize statistical topic models to identify aspects as term distributions. In this work, we opt for a middle way. We extract noun or noun phrases in posts as aspect candidates and incorporate the relation between aspect candidates into the definition of representiveness. By doing this, our method manages to provide easily explainable services to end users (a merit of the first type) [He et al., 2015] as well as offer higher granularity aspects (a merit of the second type).

As we address the problem by jointly selecting representative posts and aspects, it is also related to the extractive summarization task [He et al., 2012]. One of the standard methods is MaximumMarginal Relevance (MMR) [Carbonell and Goldstein, 1998]. A major problem of MMR is that the decision made is only based on the current iteration, which can be suboptimal. In contrast, our method has a more solid constant-factor approximation guarantee. Along this line, [Long et al., 2009] defines the best summary as the one that has the minimum information distance to the entire document set, and [Lin and Bilmes, 2010] uses non-monotone submodular set functions to perform extractive summarization.

It is worth noting that the existing aspect analysis and summarization works have mainly focused on documents. To perform aspect analysis on the social media data [Liao et al., 2014], it is crucial to account for the varying impact of posts (which is evidenced by the explicit surrogate like the number of likes and retweets). Moreover, our method is specifically tailored for the downstream application of brand monitoring, being more flexible and efficient than existing methods.

3 ProblemDefinition

We first introduce the notion of representativeness, highlighting the key diminishing return property of our design. Then we formulate the task as a submodular optimization problem that selects representative posts and aspects simultaneously.

3.1 Definition of Representativeness

Given a set of posts P = {p1, · · · , pN}, we first extract aspect candidates (which are nouns or noun phrases). We slightly abuse the use of "aspect" and "aspect candidate" in case of no ambiguity. Let the set of aspect candidates be A = {a1, · · · , aM}, then we present each post pj as a tuple < Aj, τj >, where Aj denotes the set of aspect candidates the post contains; and τj denotes the impact of pj. Denoting the number of retweets and likes for pj as rj and lj, we set

where α and β adjust the importance of retweets and likes, respectively. We found that η = 0.75 returns a modest improvement over the linear version with η = 1.

Now, we define a post's representativeness score for an aspect candidate. An intuitive way is to weight the aspect using the traditional term weighting schemes, such as TF-IDF. However, we argue that the exact termmatching scheme is insufficient for our aspect candidates. For example, if a salient aspect "data usage" occurs in a post (while "data plan" does not), we cannot say the post is not representative for "data plan". With this in mind, we define each post pj's representiveness Ri(pj) for an aspect candidate ai, i.e.,

where fsim(·, ·) ∈ [0, 1] denotes the similarity score between two aspects, which is calculated from fuzzy matching [Chaudhuri et al., 2003]: we first use character-level edit distances to find the match of tokens, which captures spelling errors or abbreviations. Then we apply WordNet similarity weighted token-level edit distance of aspect candidates to calculate fuzzy similarity score. The representativeness score regarding the aspect ai is estimated by the average similarity to aspects in pj. In addition, the post's impact τj is also incorporated, so that influential posts are more likely to be representative for its aspects. The denominator |Aj| punishes long posts containing many aspects.

Next, we define the representativeness score of a posts set X for an aspect ai, to pave the way for the task of post selection. Intuitively, when the aspect ai does not occur in the post set X, adding a new post that covers ai will gain the most; further adding posts that contain ai should be rewarded less and less. This diminishing return property is known as submodularity in discrete optimization, which is a discrete analog of convexity [Lov´asz, 1983]. It motivates us to design the function as follows,

This design helps to select posts with fewer redundant aspects. We theoretically prove the submodularity property of Ri(X) next, which is crucial to our efficient algorithm for posts and aspects selection.

Proof. Equation 3 defines a non-decreasing function such that for any post set X ⊆ Y, we will have Ri(X) ≤ Ri(Y)1 . It states that if we add a new post to a small set X, the reward is no smaller than adding the post to the larger set Y, as formulated in the following theorem.

Theorem 1. For post sets X ⊆ Y and post p /∈ Y, it holds that,

Proof. We first consider the reward of adding post p to the set Y,

Since Ri(pj) ∈ [0, 1], we have (1 -Ri(pj)) ∈ [0, 1]. Considering the fact that X ⊆ Y, we can get,

Clearly, we can see that Ri(X) is submodular.

3.2 ProblemFormulation

In real-world application of brand monitoring, companies usually hope to extract only a small set of posts that contain influential and representative aspects for further analysis. Motivated by this scenario, we consider the representativeness of a posts set X for the whole posts collection P, which is defined as,

where wi ∈ W denoting the non-negative weight of the aspect ai, which can be pre-defined by the end user, otherwise uniformly set as 1. It serves as a hyper-parameter that can be flexibly tuned to adjust the aspect focus for selecting representative posts. For example, a telecommunication company is more interested with the aspect "data plan" than "camera resolution", and a news company may have more focus on trending topics. To put more focus on a certain aspect, one just need to set the corresponding wi to a relatively large number. Moreover, by further introducing an exponential decay on the weight for aspect terms captured in the posts selection procedure, we further avoids redundancy. We will detail this later in Section 4.2. Note that submodularity is closed under nonnegative linear combinations. Therefore, R(X) also holds the diminishing return property.

1 When X is an empty set, we force Ri(X) to be zero to ensure the non-decreasing property.

In order to find the k posts which are most representative for the whole posts collection, we formulate the problem as follows. Given the posts collection P and a budget k, our task is to find k posts that maximizes the representativeness for the whole collection. Mathematically, the optimization problem is formalized as,

4 Optimization Algorithms

After formulating our problem in Equation 5, we now aim to find an efficient algorithm to solve it. In this section, we first present a greedy optimization solution for the problem; we then leverage its monotone property to speed it up, making it suitable to run on large-scale datasets.

4.1 Greedy Optimization Solution (PAS)

It is known that submodular functions can be minimized in polynomial time; however, maximizing a submodular function is an NP-complete problem [Feige et al., 2011]. It is computationally expensive to get the exact optimal solution. Fortunately, the classic result of [Nemhauser et al., 1978] shows that by applying a simple greedy algorithm to solve Equation 5, we can obtain a (1 - 1e ) lower bound approximation of the optimal solution. Next, we describe our greedy strategy for solving Equation 5.

We start from X = φ, which is an empty set. We then iteratively add a post p′ ∈ P \ X that gives the greatest marginal gain until the budget is reached. This greedy step is formalized as,

We term this straightforward greedy algorithm as PAS, short for Post and Aspect Selection algorithm. According to the theory developed by [Nemhauser et al., 1978] on discrete optimization:

Lemma 1. If R is a submodular, non-decreasing set function and R(φ) = 0, then a greedy algorithm finds a set X ′ which is no worse than constant fraction (1 - 1/e) away from the optimal X ∗ whereX ∗ = argmax

It is clear that our R(X) satisfies all the conditions of Lemma 1, meaning that the error rate of PAS algorithm is bounded by 1/e. Although the algorithm works well in practice, it is rather inefficient. To show this, we now analyze its time complexity using big-O notations.

Algorithm 1: FastPAS

Input: Posts P , Budget k, Initial weights W Output: Selected posts X 1 X ← ∅; U ←P; 2 for p ∈ U do ∆p ←R({p}); flagp ← true ; 3 while k > 0 and U ̸= ∅ do // Select one post 4 while true do // Get the top post 5 p ← arg maxp∈U ∆p; 6 if flagp then 7 add p to X and delete p from U; 8 update wi with decay if ai ∈ Ap; 9 break; 10 else 11 ∆p ← R(X ∪ {p}) - R(X); f lagp ← true; 12 end 13 end 14 for p ∈ U do f lagp ← false ; 15 end

Time Complexity Analysis. Let the number of total aspect candidates be M, and the number of averaged aspect candidates per post be m. Suppose we have selected posts X and want to select the next post. Then the time cost for evaluating the marginal gain for one post p (i.e., ∆X (p)) is O(mM|X |). Nevertheless, the key bottleneck of PAS is in the evaluation of Equation 6, which requires a traversal of all the unselected posts to find the best post in terms of ∆X(p). As such, for selecting k posts from the post collection P, we roughly need to evaluate ∆X(p) for about k|P| times, which is unsuitable for large-scale data with over millions of posts.

4.2 FastPAS

The raw PAS algorithm treats each iteration as independent of each other, which makes it slow in selecting the post of largest marginal gain. Given the monotone property of our submodular objectives, we can achieve a significant speed-up by leveraging the dependency of two iterations to avoid unnecessary evaluation of posts' marginal gain. The idea is to re-use the marginal gain of previous iterations to assist in the post selection of the current iteration, rather than evaluating it for all unselected posts in each iteration [Wang et al., 2017a]. Moreover, aspects captured in selected posts should be suppressed in future selection procedure. Therefore, assuming ai has appeared in the selected posts set t times, its new weight will degrade to be wie-t . Note that the monotone property of objectives still hold after degrading weights for some aspect terms. We give an example to illustrate how FastPAS works.

Assuming in the first iteration (the selected post set X0 is empty), we evaluated the marginal gain for all posts and obtained ∆X0 (p2) > ∆X0 (p3) > ∆X0 (p1) > ∆X0 (p4). Clearly, p2 would be selected in the first iteration, and the goal of the second iteration becomes selecting the post p ∈ {p3, p1, p4} that leads to the largest gain ∆X1 (p) where X1 = {p2}. Instead of evaluating ∆X1 (p) for all the three remaining posts with updated W, we would first check the value of p3. If ∆X1 (p3) is larger than ∆X0 (p1), we would know that p3 must be the one that has the largest gain, since the submodularity guarantees that ∆X0 (p1) > ∆X1 (p1) (see Theorem 1). Thus the iteration can be stopped earlier without evaluating the marginal gain for p1 and p4.

The above example illustrates the key ingredient of our FastPAS for acceleration, which is detailed in Algorithm 1. The variable X stores the selected posts and U stores the remaining posts. For each post p, we store a marginal gain score ∆p, which can be the latest score of the current status (labeled by flagp being true) or an old score of previous iterations (labeled by flagp being false). In each iteration, to select the post of largest marginal gain of the current status, we first check the post with the largest ∆p (line 5): if ∆p is the latest score (i.e., flagp is true), we get the expected post and can perform early termination (line 7); otherwise, we need to update ∆p to the latest score of the current status (line 9), and continue the process (line 5-10) until the expected post is found. Moreover, we use priority queue as the data structure for the variable ∆, which is rather fast in selecting the maximum element (i.e., line 5).

Our FastPAS algorithm is guaranteed to return the same results as PAS, while being much faster than PAS owing to the early termination pruning. Analytically, adding a new post to X will not decrease ∆X(p) too much. As such, the top few posts of one iteration are very likely to be the top elements for the next iteration. Thus, FastPAS only needs to evaluate the marginal gain for these top few elements, rather than all the elements. In the later section, we empirically show that the acceleration is over 1, 000 times on average for our Twitter datasets consisting of 12, 000 tweets.

5 Experiments

As our proposed method aims to efficiently extract representative aspects and posts for brand monitoring, we list the research questions to guide the remainder of this section.

• RQ1 Does our method extract salient aspects of the corpus? Whether monitoring competing brands is useful or not?
• RQ2 How does our method perform as compared to other state-of-the-art methods?
• RQ3 How is the efficiency of our accelerated FastPAS as compared to the raw PAS method?

5.1 Data and Experimental Settings

As there are no public benchmarks available for the brand monitoring task, we constructed the dataset by ourselves as in Table 1 . We issued queries "Singtel" and "StarHub" (which are the largest two telecommunication companies in Singapore) to Twitter search, and collected the tweets that were posted between September 2015 and March 2016. We carry out experiments on the two datasets separately. For aspect candidate extraction, we applied the Stanford parser to extract noun and noun phrases, followed by a modest filtering on the aspect candidates with threshold 10 (i.e., appear in less than 10 posts) to combat the possible noises.

To quantitatively evaluate the extracted aspects, we adopt the metric Normalized Discounted Cumulative Gain

(NDCG), a widely used measure in information retrieval community [He et al., 2017]. It assigns higher importance to results at top ranks, scoring successively lower ranks with marginal fractional utility [Feng et al., 2017]. For the relevance level, we invite five student volunteers to label each aspect with one of the three pre-defined levels: Unrepresentative (score 1), Ordinary (score 2) and Representative (score 3). Specifically, we ask the volunteers to rate the top-10 aspects produced by each method and report the averaged performance of NDCG@10 (the Fleiss' kappa value between them is 0.67). Since it is impractical to ask the volunteers to read through all tweets to judge the notion of representativeness, we apply a simplified process to reduce their workloads: we first provide them Annual Financial Report and Wikipedia page of the two companies, and then show them 5% of randomly sampled tweets.

5.2 Salient Aspects (RQ1)

Our method is designed to select both influential and representative posts and aspects. In Table 2, we show the top 5 posts selected by FastPAS for Singtel and highlight aspects.

Table 2: Top five posts selected for the Singtel dataset.

1. Mobile data price war erupts, M1 halves prices following Singtel's lead.
2. is it just me or is singtel wifi damn suay?
3. Customer's details leaked on Singtel app after software glitch.
4. singtel's wifi forces you to use your mobile data.
5. @Singtel launches new data-free music service with @Spotify, @KKBOX, @MeRadioSG.

As we can see, the selected posts show the important aspects for a telecommunication company and the detected aspects are rather diverse. The only redundant information comes from "singtel wifi", which occurs twice in the top five posts (both the 2nd and 4th post). Even so, we think this level of redundancy is generally acceptable since the 4th post also contains another important aspect "mobile data" in addition to "singtel wifi". Moreover, if we increase the budget size to 10, the algorithm can additionally discover aspects such as "singtel's m-wallet", "cloud service", "net profit" and so on.

Table 3: Top five posts selected for the StarHub dataset.

1. Starhub needs to understand that unlimited sms is useless, more data please.
2. Singtel having unlimited data during cny, starhub why you so stingy
3. starhub's 3g sucks hello im not in cave.
4. Starhub's customer service staffs are using Super Junior mousepads hahaha cool
5. Info: "We Broke Up" to be Shown in Singapore's StarHub Cable Channel?855

We also show the top five posts for StarHub (Table 3), which is one of the main competitors of Singtel. We observe that the selected posts cover different aspects of StarHub, including data usage, sms, customer service etc. In contrast to the Singtel corpus, the top posts show that users complain a lot about data usage, which is evidenced by the negative sentiment of posts. Looking into the data, we find that most of the complaints are caused by one event - during the Chinese New Year, StarHub did not provide free data promotion but Singtel did. Interestingly, when we scrutinize the posts of Singtel, we only see very few users praise Singtel's data promotion. The reason might be that users are more likely to post complaints on social media when they have unsatisfactory experience. Thus, to obtain a more comprehensive sense of customers' view and to get better sense of whether a commercial strategy works or not via social media, it might be useful to monitor competing brands at the same time.

To verify that our definition of representativeness (i.e., Equation 4) exhibits the submodular property, we show the marginal gain (short for MG) of each iteration (selecting one post) in Figure 2. First and foremost, we can see that MG decreases with more posts selected. For Singtel, the largest MG is obtained when selecting the first post, and the value drops dramatically in the subsequent selections; similar trend can be observed for StarHub. Since MG can be seen as the "gradient" of representativeness, the curve of MG indicates that the representativeness increases gradually with a decaying speed. This trend justifies the diminishing return property of our design.

5.3 Performance of Aspect Extraction (RQ2)

We now study the performance of aspect extraction by comparing with the following baselines:

AspectFreq Aspects are ranked by their frequency judged by number of occurrence. This baseline benchmarks performance by extracting the popular aspects of a corpus.

PostImpact This method first selects posts by their impact, and then identifies top aspects from the selected posts.

ASUM[Jo and Oh, 2011] It is a probabilistic topic model to jointly extract aspects and sentiments. We manually annotate the most representative word to indicate the aspect.

THUS[Long et al., 2009] This method selects sentences (posts) that have least information distance to the corpus.

BMSF[Lin and Bilmes, 2010] This method summarizes the corpus by maximizing a non-monotone submodular function under a budget constraint.

Table 4 shows the performance in terms of NDCG@10 for aspect extraction. As can be seen, our method achieves the best performance on both datasets, outperforming other methods by a large margin. This verifies the rationality of our design, such that the extracted aspects are highly representative of the corpus.

Among the baselines, ASUM is sophisticatedly designed for aspect extraction; however it does not take the impact of a post into consideration, and thus can be suboptimal in identifying representative aspects from social media posts. Similarly, both THUS and BMSF exhibit the same issue due to the overlook of social impacts - although they successfully extract aspects "3g" and "internet" as top aspects, they fail to identify the influential aspects like "free-data" that attract a large number of likes and retweets. PostImpact considers the impact information; however, its weak performance indicates that purely relying on the impact is insufficient. For example, the post promoting "2GB DATA Plan" attracts many retweets and likes in the Singtel dataset while this aspect lacks representativeness of the overall corpus.

Redundancy Analysis

In this evaluation, we invite the volunteers to label each of the top 10 aspects as redundant or not, and report the averaged redundancy ratio in Figure 3. It can be seen that our FastPAS method achieves the lowest redundancy ratio on both datasets - on average, only one of the top ten aspects is labeled as redundant by volunteers. We attribute the low redundancy to our two designs - the fuzzy matching scheme in measuring aspect similarity and the submodular property in selecting posts. Specifically, by using the fuzzy matching technique, our method manages to consider the similarity among aspects in the character-level, which helps to avoid redundancy like "singtel wi-fi" and "singtel's wifi". Moreover, by endowing the representativeness function with submodularity, our method can avoid selecting posts that contain similar aspects by suppressing the marginal gain. For those baselines, the relatively high redundancy ratio of AspectFreq and PostImpact (over 40%) indicates that neither the popularity of aspect nor the impact of post is sufficient to extract non-redundant aspects. ASUM achieves a lower redundancy ratio, despite that ASUM is not explicitly designed to reduce redundancy. This is because the clustering nature of topic models helps to discover aspects (topics) that are distinct from each other by modeling the co-occurrence statistics. However, it requires human efforts to manually label a topic with an aspect term. The summarization methods THUS and BMSF also achieve a relatively low redundancy, which is as expected since both methods are designed to reduce redundancy to a certain extent (THUS defines a conditional information distance for selecting posts, and BMSF uses a submodular function that is similar to MMR). The superior performance of our FastPAS over THUS and BMSF further justifies FastPAS's efficacy in extracting representative and non-redudant aspects.

5.4 Speed Up (RQ3)

To show the speedup of our FastPAS method over the vanilla PAS, we compare the actual running time of the two algorithms. We implement the algorithms in Java and run them on the same machine ( Intel i7 CPU of 3.60GHZ and 32GB RAM) in a single-thread for a fair comparison on efficiency.

Figure 4 shows the time consumption of each iteration (that selects one post) of the two methods on both datasets. The y-axis is in log-scale to better highlight the difference. As we can see from the figure, FastPAS significantly reduces the running time starting from the 2nd iteration. - on average, PAS requires over 10, 000 milliseconds to select one post, while FastPAS only takes less than 100 milliseconds. With more posts selected, both methods show an increasing trend of running time, which justifies our time complexity analysis.

6 Conclusion and FutureWork

We addressed the problem of extracting representative aspects and posts from social media streams. We presented a new method - FastPAS - to meet specific requirements for brand monitoring. Extensive experiments showed that our method can extract representative aspects and posts efficiently, and meanwhile could control the redundancy well. In future, we will consider how to apply extracted aspects to downstream applications, such as using them to improve personalized summarization [Ren et al., 2013] and the explainability of recommendation [Wang et al., 2017b]. We will further improve the efficiency of our method to make it more suitable for practical use, for example by developing hashing techniques [Zhang et al., 2016b]. Lastly, as social media is now being overwhelmed by multi-media content, such as image tweets and micro-videos [Chen et al., 2017], it is interesting to unify such multi-modal data to perform more comprehensive aspect analysis.

Acknowledgments

NExT is supported by the National Research Foundation, Prime Minister's office, Singapore under its IRC@SG Funding Initiative.