On Manipulating Weight Predictions in Signed Weighted Networks

Tomasz Lizurej, Tomasz Michalak, Stefan DziembowskiAAAI 2023 · DOI

Introduction

In digital ecosystems like cryptocurrency exchanges (e.g., Bitcoin OTC) and e-commerce platforms, trust is a critical commodity. These platforms often represent user interactions as Signed Weighted Networks, where edges represent ratings on a scale (e.g., -10 to +10). To help users assess risk, the Fairness-Goodness Algorithm (FGA) is frequently employed to predict the "weight" of potential connections based on existing data. However, these systems are prime targets for rating fraud, where attackers use Sybil identities to inflate their own reputation or denigrate competitors. This paper investigates the vulnerability of FGA to such manipulations.

Theoretical Foundation and Complexity

The authors first establish a rigorous theoretical foundation for FGA by defining it through a system of 11 axioms, such as Smooth Goodness and Monotonicity for Fairness. They prove that these axioms uniquely determine the FGA measure.

The study then addresses the computational complexity of manipulating the algorithm. Two primary adversarial goals are identified: decreasing the predicted trust between two nodes (DMT) and decreasing a specific node's reputation (DNR). The authors prove that finding an optimal manipulation strategy is both NP-hard and W[2]-hard, suggesting that as networks scale, finding a "perfect" attack becomes computationally infeasible.

Attack Modeling: Direct vs. Indirect

A key contribution of the paper is the distinction between two attack vectors:

  • Direct Attacks: The attacker directly rates the target node.
  • Indirect Attacks: The attacker targets the neighbors of the target node. By lowering the "fairness" of those who trust the target, the attacker aims to indirectly devalue the target's "goodness" score.
Comparison of direct and indirect attacks on a small network, showing the resulting changes in goodness (g) and fairness (f) scores.

While direct attacks are highly effective, they are often easier to detect or prevent through transaction requirements. Indirect attacks are stealthier but, as the authors demonstrate, mathematically "diluted" by the network structure.

Empirical Resilience

The study evaluates FGA's resilience using real-world datasets, including Bitcoin OTC, Bitcoin Alpha, and RFA Net. These networks are typically dense, with over 84% positive edges.

The results highlight a significant disparity in attack effectiveness. In simulations, direct attacks could shift a target's goodness score by 0.2 to 1.2. In contrast, indirect attacks were consistently weak. For instance, on the Bitcoin OTC dataset, the median change in goodness from an indirect attack was only 0.053.

Impact of direct and indirect attacks across different network densities (k) for various datasets.

The authors prove a theoretical bound for "minimum-k-neighbour networks": an indirect attack is at least $k$ times weaker than a direct one. As shown in the empirical plots, as the minimum degree $k$ increases, the impact of indirect attacks remains negligible compared to direct ones.

Conclusion

The Fairness-Goodness Algorithm proves to be a robust choice for reputation systems. Its inherent resistance to indirect manipulation, combined with the computational hardness of finding optimal attacks, makes it difficult to game in practice. Future work will focus on applying this adversarial lens to other trust functions and developing even more resilient versions of FGA that can automatically filter out the "ripples" of indirect Sybil attacks.

Summary updated

BibTeX
@inproceedings{lizurej2023manipulating,
  author = {Tomasz Lizurej and Tomasz Michalak and Stefan Dziembowski},
  title = {{On Manipulating Weight Predictions in Signed Weighted Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25652},
}
Figure