Source-linked AI summary
Exploiting Social Network Structure for Person-to-Person Sentiment Analysis
Robert West, Hristo S. Paskov, Jure Leskovec, Christopher Potts
TL;DR
Person-to-person evaluations matter socially, but separate text and signed-network analyses miss how linguistic and relational signals interact. The paper combines both signals in a graphical model, relaxes its NP-hard objective to an efficiently solvable hinge-loss Markov random field, and outperforms text-only and network-only models in two contrasting datasets.
Problem
Existing sentiment and signed-network models often analyze their respective signals separately, leaving their interaction insufficiently understood despite the importance of person-to-person evaluations.
Method
A graphical model predicts A’s opinion of B by synthesizing network context with sentiment analysis of evaluative texts, using a hinge-loss Markov random field relaxation for efficient inference.
Results
The combined model outperforms text-only and network-only versions across the Wikipedia Requests for Adminship and Convote datasets.
Takeaways & Limitations
Across sparse-network/strong-text and dense-network/noisier-text settings, the method adapts how it combines the two signals and excels where either component alone cannot.
Takeaways & Limitations
The formulation is for undirected graphs, although the authors state that extension to directed graphs is straightforward.
Abstract
from arXiv · showhide
Person-to-person evaluations are prevalent in all kinds of discourse and important for establishing reputations, building social bonds, and shaping public opinion. Such evaluations can be analyzed separately using signed social networks and textual sentiment analysis, but this misses the rich interactions between language and social context. To capture such interactions, we develop a model that predicts individual A's opinion of individual B by synthesizing information from the signed social network in which A and B are embedded with sentiment analysis of the evaluative texts relating A to B. We prove that this problem is NP-hard but can be relaxed to an efficiently solvable hinge-loss Markov random field, and we show that this implementation outperforms text-only and network-only versions in two very different datasets involving community-level decision-making: the Wikipedia Requests for Adminship corpus and the Convote U.S. Congressional speech corpus.
1 Introduction
Person-to-person evaluations shape reputations, social bonds, and public opinion, motivating computational analysis. The paper combines signed-network structure with textual sentiment to predict one person’s opinion of another, outperforming separate text-only and network-only models across two contrasting datasets.
- Person-to-person evaluations occur widely and influence reputations, social bonds, and public opinion, especially in political discourse.
- Existing signed-network and sentiment-analysis approaches provide complementary predictive signals but generally neglect their interaction.Networks can be informative when text is sparse, while text can help when network labels are sparse.
- The paper develops a graphical model that predicts A’s opinion of B by synthesizing social-network context with sentiment from evaluative texts.
- The underlying problem is NP-hard, but the implementation uses an efficiently solvable hinge-loss Markov random field relaxation.
- The combined model outperforms text-only and network-only versions on Wikipedia Requests for Adminship and Convote congressional speech data.The datasets differ in size, textual style and quality, and network structure and observability.
2 Background and related work
Prior work studies sentiment, signed-network structure, and contextual social signals largely through separate or broad homophily-based models. This paper focuses on person-to-person signed evaluations and models the interaction between linguistic evidence and relational structure.
- Sentiment analysis commonly models emotional valence and arousal, with product, company, and service reviews as a dominant application.
- Related work incorporates political affiliation, bias, stance, topical context, and social information, but these are not the paper’s primary focus.
- Signed social networks encode person-to-person sentiment through positive and negative edges, enabling sociological analysis of pairwise and group-level relationship patterns.
- Social theories: Balance theory predicts an edge sign from the other two signs in an undirected triangle, using friend-enemy relationship intuitions.
- Social theories: Status theory predicts directed edge signs from relative social status, with positive edges toward higher-status nodes and negative edges toward lower-status nodes.
- Signed-network modeling: Prior studies find that network structure alone can support accurate edge-sign prediction and have also applied hinge-loss Markov random fields to sign prediction.
- Research gap: The paper addresses the missing understanding of how sentiment expression and signed-network structure interact, beyond approximate contextual or demographic features.
- Novelty: Unlike homophily-based models of person-to-item evaluations, this work predicts signed person-to-person evaluations and considers the full set of triangle configurations.
3 Model
The model jointly infers person-to-person edge signs from textual sentiment predictions and signed-network structure, balancing edge agreement with socially plausible triangle configurations. Because the resulting TRIANGLE BALANCE problem is NP-hard, the paper relaxes it to an efficiently solvable HL-MRF with continuous edge signs.
- Model motivation: The model synthesizes textual features on an edge with surrounding signed-network structure to predict person-to-person edge signs.It is designed to use sentiment signals even when network information is important, and network structure when textual signals are sparse or unclear.
- Model representation: The signed graph represents people as vertices, relationships as edges, and positive or negative relationship polarities as binary edge signs.The formulation is presented for undirected graphs, with directed relationships described as a straightforward extension.
- Optimization objective: TRIANGLE BALANCE minimizes edge costs for disagreement with sentiment probabilities and triangle costs for undesirable configurations under balance or status theory.Observed edge signs are fixed, while unobserved signs are inferred from the network, textual predictions, and triangle configurations.
- Computational complexity: TRIANGLE BALANCE is NP-hard.The paper sketches a proof of this computational-hardness result before introducing a tractable relaxation.
- HL-MRF relaxation: The relaxation replaces binary edge signs with continuous values in [0,1], interpreted as degrees of positive polarity, while preserving the original objective on binary assignments.Edge and triangle costs are interpolated with hinge-loss terms; convex surrogates are used for triangle costs.
- HL-MRF relaxation: The relaxed objective is an HL-MRF whose convex hinge-loss formulation permits efficient exact inference, implemented with Probabilistic Soft Logic and ADMM.The model uses a weighted sum of hinge losses of linear functions of the variables.
4 Wikipedia experiments
Wikipedia Requests for Adminship provides a signed voting network with rich evaluative comments, enabling comparison of sentiment-only, network-only, and combined prediction models. The combined model remains robust when evidence or textual features are sparse and improves on component approaches, including in leave-one-out prediction.
- Dataset: The corpus contains 11K editors, 160K signed votes, 76% positive edges, and nearly 1M triangles, with comments typically accompanying votes.Votes support, oppose, or remain neutral; neutral votes are discarded, and comments have a median/mean length of 19/34 tokens.
- Experimental setup: The evaluation compares an independent text sentiment model, a combined model using sentiment and triangle costs, and a network-only triangle model.The sentiment model uses L2-regularized logistic regression over frequent-word term frequencies, while the combined and network models exploit network context.
- Evidence ratio: AUC/ROC rises from 0.56 to 0.82 for the network-only model as evidence increases from 12.5% to 75%, while sentiment alone remains at 0.88.The text model’s strong performance reflects highly indicative, sometimes formulaic language in the comments.
- Evidence ratio: At 75% evidence, combining sentiment and network information reaches 0.89 AUC/ROC and 0.68 AUC/negPR, versus 0.88 and 0.60 for sentiment alone.The AUC/negPR improvement is reported as 13%, while the combined model is not harmed by low evidence and can default toward sentiment-only behavior.
- Feature robustness: When sentiment features are removed, the combined model remains stronger than both alternatives and learns to disregard sentiment predictions as they approach random performance.When sentiment falls to the network-only level of 0.81 ROC/AUC, the combined model remains at 0.86.
- Leave-one-out setting: In leave-one-out prediction, adding sentiment to the network model achieves 0.93 AUC/ROC and 0.75 AUC/negPR, exceeding both LOO alone and the combined model.LOO alone reaches 0.88 and 0.63, while the combined model reaches 0.89 and 0.68.
5 U.S. Congress experiments
The Convote experiments evaluate joint sentiment-network prediction on a dense person–person voting graph, finding that the combined model performs best, especially when little network evidence is available.
- 5.1 Dataset description: Convote contains 3,857 speech segments from 53 U.S. House debates, with speakers, parties, bills, and votes annotated.
- 5.1 Dataset description: The authors construct a dense undirected person–person graph by linking Congresspeople who voted on the same bill and labeling edges by vote agreement.
- 5.2 Experimental setup: Random edge sampling partitions the network into five folds, each containing 20% of the edges while retaining all nodes.
- 5.2 Experimental setup: The Convote sentiment model converts distributed SVM scores into probabilities using Platt scaling, then estimates agreement probabilities between speakers.
- 5.3 Results: The combined model consistently achieves the best results, with its largest gains in realistic settings where little network evidence is available.
- 5.3 Results: Network-only prediction eventually catches up because the derived graph predominantly contains even-negative-edge triangles, constraining the solution space.
- 5.3 Results: At 15% evidence, network-only prediction has very high precision until roughly 0.20 recall, while the combined model preserves higher precision afterward.
6 Discussion
The paper concludes that jointly modeling textual and network information succeeds across two contrasting datasets because the model adapts to which signal is more trustworthy. It also presents this adaptivity as useful for applications where signal reliability is unknown in advance.
- 6 Discussion: The model jointly predicts person-to-person evaluation polarity by synthesizing textual and social-network information across two datasets.
- 6 Discussion: In Wikipedia, sentiment is strong but the network is sparse, whereas Convote has a strong voting network but indirect, noisy speech-based sentiment.
- 6 Discussion: The method excels in both settings because it learns how best to combine the two signals from the data.
- 6 Discussion: The authors envision extracting a coherent network subgraph, annotating edge evaluativity, training the combined model with a sentiment model, and predicting new edge labels.
A Proof sketch of Theorem 1
The proof sketch establishes NP-hardness by reducing TWO-LEVEL SPIN GLASS to TRIANGLE BALANCE. The reduction maps vertices to edges and original edges to triangles through an added central vertex.
- A Proof sketch of Theorem 1: The full proof is available online, while the paper provides only a proof sketch because of space constraints.
- A Proof sketch of Theorem 1: The proof reduces TWO-LEVEL SPIN GLASS, a known NP-hard problem, to TRIANGLE BALANCE.
- A Proof sketch of Theorem 1: TWO-LEVEL SPIN GLASS assigns signs to vertices to minimize an energy over edge costs, whereas TRIANGLE BALANCE assigns signs to edges using edge and triangle costs.
- A Proof sketch of Theorem 1: The reduction creates a new vertex connected to every original vertex, producing one triangle for each original edge and one corresponding edge for each original vertex.