Source-linked AI summary
Negative Link Prediction in Social Media
Jiliang Tang, Shiyu Chang, Charu Aggarwal, Huan Liu
TL;DR
Negative links can be useful, but many social media sites do not let users specify them, leaving them unavailable as direct inputs. NeLP predicts negative links from positive links and content-centric interactions, and the authors report patterns linking negative interactions and nearby users to negative links.
Problem
Negative links have analytical value, but many social media sites do not let users specify them, motivating prediction from commonly available data.
Source: §1 · p. 1Method
Results
Enemies are usually within 2 or 3 positive-network hops, most signed triads satisfy balance and status theory, and pairs with negative interactions are more likely to have negative links.
Source: §3.4 · p. 4Takeaways & Limitations
The reported patterns support studying negative-link prediction using positive links and content-centric interactions when negative links are not supplied to the framework.
Source: §3 · p. 3, §7 · p. 9The framework uses positive links and content-centric interactions; whether user-generated content is useful for negative-link prediction remains for future investigation.
Source: §7 · pp. 9–10
Abstract
from arXiv · showhide
Signed network analysis has attracted increasing attention in recent years. This is in part because research on signed network analysis suggests that negative links have added value in the analytical process. A major impediment in their effective use is that most social media sites do not enable users to specify them explicitly. In other words, a gap exists between the importance of negative links and their availability in real data sets. Therefore, it is natural to explore whether one can predict negative links automatically from the commonly available social network data. In this paper, we investigate the novel problem of negative link prediction with only positive links and content-centric interactions in social media. We make a number of important observations about negative links, and propose a principled framework NeLP, which can exploit positive links and content-centric interactions to predict negative links. Our experimental results on real-world social networks demonstrate that the proposed NeLP framework can accurately predict negative links with positive links and content-centric interactions. Our detailed experiments also illustrate the relative importance of various factors to the effectiveness of the proposed framework.
1. INTRODUCTION
Although much social-network research has focused on positive links, negative links also have analytical value. NeLP uses positive links and content-centric interactions to predict negative links, which many platforms do not let users specify.
1. INTRODUCTION
- Negative links can improve positive-link prediction and recommender systems, and trust and distrust relations can help users find high-quality, reliable reviews.The passage also notes that negative links are interesting in their own right.Source: §1 · p. 1
- Because many social media sites do not let users specify negative links, the paper asks whether they can be predicted from available social-network data.The motivating assumption is that structural and content-centric data may contain implicit information about negative linkages.Source: §1 · p. 1
- NeLP provides a principled framework for predicting negative links from positive links and content-centric user interactions.The framework combines theories of these sources with mathematical models.Source: §1 · p. 2
- The authors evaluate NeLP on real-world social media datasets to examine its effectiveness and mechanisms.Source: §1 · p. 2
2. PROBLEM STATEMENT
The problem is to predict the negative network from the positive network and content-centric user interactions. Unlike sign prediction, it identifies pairs that may have negative links without assuming negative-link examples are available.
2. PROBLEM STATEMENT
- A records which users created which content, while O records positive, negative, or neutral/no opinions on content.The paper represents these user-content and user-post opinion relations as matrices.Source: §2 · p. 2
- Given the positive network Gp and content-centric interactions A and O, the task is to predict the negative network Gn.Source: §2 · p. 2
- The task does not assume negative-link examples are available, unlike formulations that predict links from existing positive and negative links.Source: §2 · p. 2
- Unlike sign prediction, which assigns signs to existing links, this task identifies node pairs where negative links may exist.Source: §2 · p. 2
3. DATA ANALYSIS
Using Epinions and Slashdot data, the analysis examines negative links’ positions in positive networks, signed-triad theories, and content-centric interactions. It finds that enemies are often nearby, most triads satisfy balance and status theory, and negative interactions are associated with negative links, providing groundwork for NeLP.
3. DATA ANALYSIS
- The analysis uses Epinions trust/distrust and helpfulness ratings, and Slashdot friend/foe links and comment sentiment; users with neither positive nor negative links were filtered out.Epinions ratings above 3 are treated as positive and those below 3 as negative; Slashdot comment polarity is computed using the MPQA Subjectivity Lexicon.Source: §3 · pp. 2–3
3.1 Where Are our “Enemies”?
- Epinions and Slashdot data show that 82.64% and 87.86% of enemy-pairs, respectively, are within 3 hops in the positive networks.The analysis also reports that more than 80% of negative links in both datasets have shortest paths under 4.Source: Figure 2 · p. 3, §3.1 · p. 3
3.2 Social Theories in Signed Networks
- 92.31% and 93.01% of triads in Epinions and Slashdot are balanced, respectively, while 94.73% and 93.38% satisfy status theory.For balance theory, the study ignores link directions because the theory is designed for undirected networks.Source: §3.2 · p. 3
3.3 Negative Links and Content-centric Interactions
- Negative-interaction pairs are more likely to have negative links than sampled pairs without such interactions; the reported t-test p-values are 5.72e-89 for Epinions and 1.93e-109 for Slashdot.The ratio of pairs with both negative links and at least K negative interactions tends to increase with K.Source: §3.3 · p. 4, Figure 3 · p. 4
3.4 Discussion
- The discussion concludes that enemies are often only a few positive-network hops away, most triads satisfy balance and status theory, and negative interactions are associated with negative links.These observations provide groundwork for the proposed negative-link prediction framework.Source: §3.4 · p. 4
4. THE PROPOSED FRAMEWORK - NeLP
NeLP frames negative-link prediction as classification using constructed samples and features from positive links and content-centric interactions. It combines reliability-weighted negative samples with a balance-theory regularizer.
4.1 Label Construction
- Negative-sample candidates are pairs with negative interactions; status-theory refinement removes pairs in violating triads and adds pairs making all involving triads satisfy theory, with interaction-count-based weights or constant r for added pairs.Missing links are treated as positive samples; En:Eo imbalance ratios are 1:4131 in Epinions and 1:2534 in Slashdot.Source: §4.1 · pp. 4–5
4.2 Feature Extraction
- NeLP extracts 45 features per user pair: 16 user, 7 pair, and 22 signed features from positive links and content-centric interactions.The signed features include negative-link measures and 16 weighted triads; user and pair features include interaction counts, degrees, and shortest-path length.Source: §4.2 · p. 5
4.3 The NeLP Optimization Framework
- The classifier uses a soft-margin support vector machine to tolerate noisy training labels, especially the indirectly derived negative samples.The formulation weights positive and negative errors differently and scales each negative sample’s error by its reliability weight.Source: §4.3 · pp. 5–6
- Balance-theory regularization encourages paired samples to share link types when their users are positively linked, using selected pairs at shortest-path distance two.It also includes additional samples beyond the labeled sets, serving a role similar to unlabeled samples in semi-supervised learning.Source: §4.3 · p. 6
5. EXPERIMENTS
The experiments evaluate NeLP against baselines and across sites, then examine its components and balance-theory regularization. NeLP improves on baselines, generalizes across sites, and performs best with its components and a suitably weighted regularizer.
5.1 Evaluation Metrics
- F1-measure and precision evaluate negative-link prediction, since accuracy can mislead on highly imbalanced link-prediction data.Precision is also reported because some scenarios prioritize finding likely negative links over avoiding false negatives.Source: §5.1 · p. 7
5.2 Performance of Negative Link prediction
- NeLP significantly improves performance over baseline methods and generalizes well across Epinions and Slashdot.The comparison is reported in Table 3; the cross-site evaluation shows little performance decrease regardless of which dataset is used for training.Source: Table 3 · p. 7, §5.2 · pp. 7–8
- sPath beats random guessing, negative-interaction candidates improve results, and status-theory refinement further improves F1 by 2.37% on Epinions and 1.45% on Slashdot.The refinement removes candidates inconsistent with status theory and adds candidates that close open triads; NeLP performs best among the compared methods.Source: §5.2 · p. 7
5.3 Component Analysis of NeLP
- Removing any one of NeLP’s three components degrades performance, and removing all three degrades it further, suggesting complementary information.Setting cj = 1 reduces precision by 8.70% on Epinions and 11.08% on Slashdot; equal weighting of positive and negative samples also degrades performance, as does removing balance regularization.Source: §5.3 · p. 8
5.4 Impact of Balance Theory Regularization
- Increasing Cb from 0 to 0.001 raises precision by 4.02% on Epinions and 4.41% on Slashdot, but performance eventually drops as regularization grows.Performance is relatively stable from 0.001 to 0.1 on Epinions, while it decreases dramatically after values such as 0.05 on Slashdot.Source: §5.4 · pp. 8–9
6. RELATED WORK
Related work covers positive-link prediction, prediction of positive and negative links in signed networks, and sign prediction. These approaches draw on network topology, supervised learning, social theories, and transfer across networks.
6.1 Positive Link Prediction
- Positive-link prediction includes unsupervised methods using network topology or low-rank factorization, and supervised methods that train classifiers on pair features and link labels.Reported supervised approaches use features such as human mobility to improve prediction performance.Source: §6.1 · p. 9
6.2 Positive and Negative Link Prediction
- Signed-link prediction work includes trust and distrust propagation, balance-theory features, longer-cycle features, and matrix factorization.Source: §6.2 · p. 9
6.3 Sign Prediction
- Sign prediction research uses decision-making behavior and social theories, incorporates status theory across source and target networks, and transfers sign information to new networks.Source: §6.3 · p. 9
7. CONCLUSION
The paper proposes NeLP to predict negative links from positive links and content-centric interactions, reporting effectiveness and generalization on two real-world social-media datasets. It identifies noisy constructed labels as a concern and points to testing other noise-tolerant algorithms.
7. CONCLUSION
- NeLP uses positive links and content-centric interactions to predict negative links, with experiments on two real-world social-media datasets demonstrating effectiveness and generalization.The framework follows analysis of balance and status theories and uses those insights in its prediction approach.Source: §7 · p. 9
- Constructed labels may be noisy; the paper uses a noise-tolerant SVM and proposes testing other noise-tolerant algorithms.Source: §7 · p. 10