Abstract
In the problem of edge sign prediction, we are given a directed graph (representing a social network), and our task is to predict the binary labels of the edges (i.e., the positive or negative nature of the relationship). This paper provides a rigorous theoretical foundation for "troll-trust" heuristics—simple rules of thumb used to predict whether a social media link is positive or negative. By framing these heuristics as approximations of a Bayes optimal classifier, the authors develop a Label Propagation algorithm that is not only more accurate than state-of-the-art methods but also orders of magnitude faster.
Introduction
In social network analysis, understanding the nature of connections—whether they represent trust or distrust, friendship or enmity—is critical. This is known as the edge sign prediction problem. While many networks are driven by homophily, real-world data often contains negative relationships like disapproval or trolling.
Existing solutions typically fall into two categories: simple local heuristics that lack theoretical grounding, or complex global models that are computationally expensive. This research bridges that gap by providing a theoretical justification for simple heuristics and leveraging that theory to build a scalable, high-performance algorithm.
The Troll-Trust Generative Model
The authors propose a stochastic generative model where the sign of a directed edge from user $i$ to user $j$ is determined by two latent parameters:
- $p_i$: The node's "optimism" or tendency to like others.
- $q_j$: The node's "trustworthiness" or tendency to be liked by others.
The probability of a positive edge is defined as the average of these parameters: $P(y_{i,j} = 1) = \frac{p_i + q_j}{2}$. From this model, the authors derive the Bayes Learning Classifier ($blc(tr, un)$), which uses "trollness" (outgoing negative edge fraction) and "untrustworthiness" (incoming negative edge fraction) to approximate the Bayes optimal classifier.
Label Propagation and Graph Transformation
To scale this model, the authors transform the directed graph $G$ into a new undirected graph $G''$. In this transformation, the original edges become nodes in the new graph. By applying a standard Label Propagation (L. Prop) algorithm to $G''$, they can approximate the Maximum Likelihood Estimator of the generative model efficiently.
This approach reduces the complex edge sign prediction problem to a node classification problem on a sparse transformed graph, allowing for rapid computation even on massive datasets.
Experimental Evaluation
The model was evaluated on five real-world datasets: Wikipedia (admin voting), Slashdot (friend/foe tags), Epinion (trust/distrust reviews), Wik. Edits (constructive/destructive interactions), and Citations (endorsement/criticism). Performance was measured using the Matthews Correlation Coefficient (MCC), which is robust for imbalanced datasets where positive edges predominate.
Key Findings
- Accuracy: The L. Prop. algorithm consistently outperformed or matched state-of-the-art methods, particularly in "low-data" scenarios where only 5% of edge signs were known.
- Efficiency: The computational gains were significant. On the Slashdot dataset, L. Prop. required only 0.6 seconds to train, whereas competing global methods like RankNodes or LowRank took between 2.4 and 70 seconds. In some cases, L. Prop. was over 100x faster than traditional methods.
- Theoretical Validation: The strong performance of the simple $blc(tr, un)$ classifier validated the underlying assumption that "trollness" and "trustworthiness" are the primary drivers of edge signs.
Conclusion
By grounding common heuristics in a formal generative model, this work demonstrates that simple features can be mathematically optimal. The resulting Label Propagation algorithm offers a powerful tool for large-scale social network analysis, combining theoretical rigor with extreme computational efficiency. Future work may involve incorporating triadic effects (e.g., structural balance theory) and dynamic user behavior to further refine prediction accuracy.
Summary updated