Campus Event Calendar

Event Entry

What and Who

Reducing Exposure to Harmful Content via Graph Rewiring

Corinna Coupette
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 4 April 2023
30 Minutes
Virtual talk
Virtual talk


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).


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 03/30/2023 11:45
Roohani Sharma, 03/03/2023 21:33 -- Created document.