Reducing Exposure to Harmful Content via Graph Rewiring
Open Access
- 4 August 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 323-334
Abstract
Most media content consumed today is provided by digital platforms that aggregate input from diverse sources, where access to information is mediated by recommendation algorithms. One principal challenge in this context is dealing with content that is considered harmful. Striking a balance between competing stakeholder interests, rather than block harmful content altogether, one approach is to minimize the exposure to such content that is induced specifically by algorithmic recommendations. Hence, modeling media items and recommendations as a directed graph, we study the problem of reducing the exposure to harmful content via edge rewiring. We formalize this problem using absorbing random walks, and prove that it is NP-hard and NP-hard to approximate to within an additive error, while under realistic assumptions, the greedy method yields a (1-1/e)-approximation. Thus, we introduce Gamine, a fast greedy algorithm that can reduce the exposure to harmful content with or without quality constraints on recommendations. By performing just 100 rewirings on YouTube graphs with several hundred thousand edges, Gamine reduces the initial exposure by 50%, while ensuring that its recommendations are at most 5% less relevant than the original recommendations. Through extensive experiments on synthetic data and real-world data from video recommendation and news feed applications, we confirm the effectiveness, robustness, and efficiency of Gamine in practice.Keywords
All Related Versions
Funding Information
- EC H2020 RIA project SoBigData++ (871042)
- Academy of Finland project MLDB (325117)
- ERC Advanced Grant REBOUND (834862)
This publication has 42 references indexed in Scilit:
- Optimizing network robustness by edge rewiring: a general frameworkData Mining and Knowledge Discovery, 2016
- Absorbing Random-Walk Centrality: Theory and Algorithms2015
- Selecting Shortcuts for a Smaller World2015
- Opinion maximization in social networks2013
- Vertex cover might be hard to approximate to withinJournal of Computer and System Sciences, 2008
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002
- An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set functionDiscrete Applied Mathematics, 2001
- Cubic graphsACM Computing Surveys, 1995
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given MatrixThe Annals of Mathematical Statistics, 1950