On the Troll-Trust Model for Edge Sign Prediction in Social Networks

Géraud Le Falher, Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale

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 (positive or negative) of the edges. Many successful heuristics for this problem are based on 'troll-trust' features, which estimate the fraction of outgoing and incoming positive/negative edges at each node. This paper formalizes these heuristics as approximators to the Bayes optimal classifier for a simple probabilistic model. We introduce a Label Propagation algorithm run on a transformed version of the original social graph that approximates the maximum likelihood estimator for this model. Extensive experiments show that this algorithm is competitive in accuracy and significantly more scalable than existing methods.

Introduction

Traditional social network analysis often focuses on the presence or absence of connections. However, many modern platforms—such as Slashdot, Wikipedia, and Epinions—allow users to specify the nature of their relationships through signed edges. These signs can represent trust versus distrust, friendship versus enmity, or endorsement versus criticism.

Predicting these missing edge signs is a critical task. While simple heuristics based on a user's 'trollness' (propensity to create negative edges) or 'trustworthiness' (propensity to receive positive edges) have proven effective, they lacked a rigorous theoretical foundation. This paper bridges that gap by providing a generative model and a scalable global algorithm based on Label Propagation.

The Troll-Trust Generative Model

The authors propose a generative model where each node $i$ is characterized by two latent parameters: $p_i \in [0, 1]$, representing the node's 'trustingness' (tendency to like others), and $q_i \in [0, 1]$, representing the node's 'trustworthiness' (tendency to be liked by others). Under this model, the probability that an edge from node $i$ to node $j$ is positive is defined as the average of these two parameters: $P((i, j) = +) = \frac{p_i + q_j}{2}$. This simple formulation captures the essence of 'troll-trust' heuristics: a 'troll' has a low $p_i$, while a highly trusted user has a high $q_j$.

Graph Transformation and Label Propagation

To solve the prediction problem globally, the authors transform the original directed graph $G$ into a new undirected, weighted graph $G''$. In this transformation, the original edges of $G$ become the nodes of $G''$. This reduction allows the use of standard node-classification techniques for edge sign prediction.

The transformation process from a directed signed graph (a) to the undirected graph G'' (c) used for Label Propagation.

The Maximum Likelihood Estimator (MLE) for the generative model is then approximated using a Label Propagation (L. Prop) algorithm on $G''$. This approach spreads known edge labels across the transformed network to find a harmonic solution that minimizes a quadratic energy function, effectively capturing global network structure while remaining computationally efficient. Additionally, the authors derive an online version of the algorithm with theoretical mistake bounds for adversarial conditions.

Empirical Evaluation

The proposed model was evaluated on five diverse real-world datasets: Wikipedia (admin voting), Slashdot (friend/foe tags), Epinions (trust/distrust reviews), Wik. Edits (constructive/destructive interactions), and Citations (endorsing/criticizing citations). These datasets vary in size from approximately 4,800 nodes to over 138,000 nodes, providing a robust test for both accuracy and scalability.

Results and Discussion

The experimental results demonstrate that the Label Propagation approach is highly effective. Accuracy was measured using the Matthews Correlation Coefficient (MCC), which is more robust to the class imbalance typical of social networks (where positive edges usually outnumber negative ones).

Performance comparison (MCC and execution time) of Label Propagation (L. Prop) against state-of-the-art baselines across various datasets.

Key findings include:

  • Competitive Accuracy: L. Prop consistently ranked among the top-performing algorithms across all datasets and training set sizes, often outperforming complex models that account for structural balance (triads).
  • Superior Scalability: L. Prop is significantly faster than other global methods. On larger datasets like Epinions and Wik. Edits, it outperformed competitors like RankNodes and LowRank matrix factorization by two to three orders of magnitude in terms of computation time.
  • Theoretical Alignment: Logistic regression models trained on troll-trust features yielded weights that closely matched the predictions of the generative model, confirming the theoretical link between simple heuristics and the Bayes optimal classifier.

Conclusion

By formalizing the 'Troll-Trust' model, this work provides a solid theoretical basis for widely used heuristics in social network analysis. The proposed Label Propagation algorithm on the transformed graph $G''$ offers a powerful combination of global predictive power and extreme scalability, making it suitable for modern, large-scale social media platforms. Future work may involve incorporating additional metadata or structural features while preserving the efficiency of the current approach.

Summary updated

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 social relationships). Many successful heuristics for this problem are based on the troll-trust features, estimating at each node the fraction of outgoing and incoming positive/negative edges. We show that these heuristics can be understood, and rigorously analyzed, as approximators to the Bayes optimal classifier for a simple probabilistic model of the edge labels. We then show that the maximum likelihood estimator for this model approximately corresponds to the predictions of a Label Propagation algorithm run on a transformed version of the original social graph. Extensive experiments on a number of real-world datasets show that this algorithm is competitive against state-of-the-art classifiers in terms of both accuracy and scalability. Finally, we show that troll-trust features can also be used to derive online learning algorithms which have theoretical guarantees even when edges are adversarially labeled.
BibTeX
@inproceedings{falher2017troll,
  author = {Géraud Le Falher and Nicolò Cesa-Bianchi and Claudio Gentile and Fabio Vitale},
  title = {{On the Troll-Trust Model for Edge Sign Prediction in Social Networks}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=B89VezhzGX9},
}
Figure