Beyond Transitivity: Robust Trust Inference via Collaborative Agreement
A robust trust inference algorithm in weighted signed social networks based on collaborative filtering and agreement as a similarity metric
The paper introduces a robust unsupervised trust inference algorithm for Weighted Signed Social Networks (WSNs) based on Memory-based Collaborative Filtering. By utilizing "Agreement" as a novel local similarity metric between trustors and trustees, it achieves state-of-the-art performance in predicting both trust and distrust across various real-world datasets including Bitcoin exchanges and Wikipedia RfA.
TL;DR
Trust is the currency of social interaction, but predicting it in digital Weighted Signed Networks (WSNs)—where relations can be both positive (trust) and negative (distrust)—is notoriously difficult. This paper proposes a new unsupervised algorithm that treats trustors as "users" and trustees as "items" in a Collaborative Filtering (CF) framework. By replacing simple transitivity with a robust "Agreement" metric, handles distrust more intuitively and maintains high performance even when 90% of the network data is missing.
Background: The Problem with Negative Ties
In traditional social network analysis, we often assume transitivity: "If Alice trusts Bob, and Bob trusts Carol, Alice likely trusts Carol." However, the introduction of distrust breaks this logic. If Alice distrusts Bob, and Bob distrusts Carol, Carol might be an even bigger threat than Bob.
Existing models like PageRank or HITS often fail here because they rely on global connectivity. When a network is sparse—meaning we only see a fraction of the total interactions—these global algorithms lose their context and accuracy.
Methodology: "Quality over Quantity" Agreement
The researchers pivot away from global rankings toward a local, memory-based Collaborative Filtering approach. The core intuition is two-fold:
- Trustor Agreement: If two users agree on their assessment of a group of people, they will likely agree on a new person.
- Trustee Similarity: If two people are viewed similarly by those who know them, they will likely receive similar ratings from a new user.
1. The Agreement Metric
Instead of using Jaccard Similarity (which only counts common neighbors), the authors define an Agreement Decay Factor (). It calculates the exponential difference between weights:
As the difference in trust values increases, the "Agreement" score drops toward zero. This ensures that a single shared, highly-agreed-upon trustee is more valuable for prediction than ten shared trustees where the trustors have conflicting opinions.
2. Solving Sparsity with Bootstrapping
To prevent the algorithm from failing when users share zero common trustees, a bootstrapping factor () is introduced. It allows the model to "estimate" a baseline level of agreement based on the total number of trustees, ensuring the system can still provide a recommendation even in the "cold-start" regions of a social graph.
Experimental Results: Robustness to the Extreme
The authors tested their approach on datasets including Bitcoin-Alpha, Bitcoin-OTC, and Wikipedia RfA.
SOTA Comparison
In the "Leave-one-out" task (predicting a single removed link), the Agreement-based CF outperformed established baselines like Fairness-Goodness (FxG) and Bias and Deserve (BAD) across all metrics (MAE, RMSE, and PCC).
Resilience to "Hidden" Networks
The most impressive feat of this algorithm is its robustness. In tests where up to 90% of the edges were removed (randomly hidden), the Agreement algorithm showed a very slow degradation in accuracy.
In the figure above, while other metrics (like the blue/green lines for BAD/FxG) show sharp declines in Correlation (PCC) as edges are removed, the Agreement algorithm (red line) maintains a high correlation, proving its local logic is independent of the global graph's completeness.
Critical Insight & Conclusion
Why does this work? Global algorithms are like trying to map an entire country to find your way home; if a few bridges are out, the map fails. This Collaborative Filtering approach is like asking your immediate neighbors for directions. As long as your neighborhood is somewhat intact, the advice remains accurate.
Limitations & Future Work
The algorithm currently ignores the "trust" the target trustor has in the "recommending trustors"—a common feature in trust propagation models. Integrating Propagation + Agreement could lead to even higher accuracy. Additionally, the parameters and are currently static; making these adaptive to specific network types (e.g., trading vs. voting) remains a key area for exploration.
Final Takeaway: For modern decentralized social platforms where data is sparse and distrust is a reality, local "Agreement" is a far more reliable metric for trust than global popularity.