Abstract
Brand monitoring on social media is often hindered by the sheer volume of data and the varying impact of individual posts. Traditional frequency-based methods fail to capture the true public sentiment and often produce redundant results. This paper introduces FastPAS, a representativeness-aware algorithm that leverages social impact metrics (likes and retweets) and submodular optimization. FastPAS identifies diverse, high-impact aspects of brand conversation while achieving a 1,000x speedup over standard greedy selection methods.
Introduction
In the era of social media, companies must navigate a "needle in a haystack" problem to understand customer feedback. Identifying specific features or "aspects" (e.g., "data plans," "customer service") is critical for reputation management. However, social media data presents two primary challenges:
- Varying Impact: A post from an influential user with high engagement is more representative than multiple ignored posts. Standard NLP tools often treat all posts as equal, missing this nuance.
- Noise and Redundancy: Informal language, typos, and repetitive complaints make simple frequency-based extraction ineffective, often resulting in redundant or low-quality aspect lists.
To address these, we define representativeness as a metric that balances data coverage with the social "weight" of source posts.
Methodology
The core of our approach is formalizing aspect selection as a submodular optimization problem.
Representativeness Scoring
Each post is assigned a score based on its social impact (a weighted sum of retweets and likes) and its relevance to specific aspects. To handle the informal nature of social media, we employ fuzzy matching. By combining character-level edit distance with WordNet similarity, the system can group variations like "wifi" and "wi-fi" into a single aspect.
Submodular Optimization and FastPAS
We utilize a submodular function to select posts, which naturally accounts for diminishing returns. Once a post covering a specific aspect is selected, the marginal value of adding another post on the same topic decreases, encouraging diversity.
To solve this efficiently, we developed FastPAS. This algorithm uses "lazy evaluations" based on the property that marginal gains only decrease as more items are selected. This allows the algorithm to skip thousands of irrelevant evaluations. Furthermore, we apply an exponential decay to weights for aspects already captured to further minimize redundancy.
Experimental Setup
We evaluated FastPAS using two custom Twitter datasets:
- Singtel: 12,457 tweets related to the Singaporean telecommunications provider.
- StarHub: 12,726 tweets related to its primary competitor. The datasets include metadata for engagement (likes and retweets) spanning from September 2015 to March 2016.
Key Results and Discussion
Efficiency and Scalability
The "Fast" in FastPAS refers to its significant computational efficiency. By leveraging lazy evaluations, the algorithm achieves an average 1,000x speedup compared to the standard greedy selection method (PAS). This performance makes real-time monitoring of large-scale social media streams feasible.
Accuracy and Redundancy
FastPAS consistently outperformed state-of-the-art baselines, including ASUM and BMSF, in aspect extraction quality (measured by NDCG@10). Crucially, it demonstrated the lowest redundancy ratio among all tested methods. In human evaluations, typically only one out of the top ten aspects selected by FastPAS was considered redundant.
Competitive Intelligence
Our analysis revealed that monitoring competitors is as vital as monitoring one's own brand. For instance, FastPAS identified a surge in complaints from StarHub users regarding data limits during a period when Singtel offered a "free data" promotion. This demonstrates the algorithm's ability to extract actionable intelligence from competitive dynamics.
Conclusion and Future Work
FastPAS provides a robust framework for representativeness-aware brand monitoring. While highly effective, future work will address the reliance on manual labeling for evaluation and expand the model to include multi-media content, such as images and video. Integrating these representative aspects into personalized recommendation engines remains a key objective for future development.
Summary updated