Inspired by concerns about recommendation algorithms fueling radicalization on digital media platforms, we model media items and recommendations as a directed graph and study the problem of reducing the exposure to harmful content via edge rewiring under budget constraints. 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. Our work also highlights open questions related to the more general problem of optimizing functions of graphs via edit operations under budget constraints.
Joint work with Stefan Neumann and Aristides Gionis (KTH Stockholm).