Local algorithm finds dense bipartite graph areas near a vertex
Constant-Factor Local Approximation for Bipartite Densest Subgraph
Data Structures and Algorithms
Summary
Finding small groups of tightly connected points near a given point in a large two-part network can help detect fraud or recommend items. The authors developed a new method that very quickly finds such groups without being slowed down by highly connected points. Their method guarantees to find groups nearly as dense as the best known, using only a limited number of checks around the starting point. They also explain why this method’s performance is close to the best possible. The key idea was adapting a previously known curve technique to work in this two-part network setting.
What this means in practice
- •For fraud detection teams: Quickly identify small dense groups of interactions near suspicious points in large bipartite networks, improving local detection accuracy.
- •For recommendation system engineers: Find tightly connected user-item subgroups efficiently around a user to improve personalized recommendations without scanning the entire network.
Authors
Michael Kapralov, Jakub Łącki, Silvio Lattanzi, Guy Weissenberg
Abstract
Given a vertex $v$ in a large bipartite graph $G$, can one quickly find a small densely connected region near $v$? This is the algorithmic core of many fraud detection, community detection, and recommender systems. One would like a local algorithm, i.e., an algorithm that probes $G$ in only a small number of locations to find such a region. Our main contribution is the first constant-factor local approximation, independent of the maximum degree of the graph, for the classical notion of bipartite density: if the sides of a bipartite subgraph are $S$ and $T$, its density is $d(S,T):=e(S,T)/\sqrt{|S||T|}$, where $e(S,T)$ is the number of edges between $S$ and $T$. We consider cohesive dense subgraphs, since every dense subgraph contains a cohesive core of at least the same density. For such a cohesive dense subgraph $S\mathbin{\dot\cup}T$ with at most $k$ vertices per side, our algorithm, starting from any vertex in $S\mathbin{\dot\cup}T$, uses $O_ε(k^{4+ε})$ neighbor queries to find a subgraph $X\mathbin{\dot\cup}Y$ of density $Ω_ε(d(S,T))$ on $O_ε(k^{2+ε})$ vertices, for every fixed $ε>0$. Our result improves upon the result of Andersen (2010), whose approximation guarantee depends logarithmically on the maximum degree. We complement our positive result with information-theoretic and computational limitations showing that the quadratic dependence on $k$ in the output size is essentially unavoidable for constant-factor approximation. Our main technical innovation is an adaptation of the Lovász-Simonovits curve to the bipartite density problem, based on weak-$\ell_p$ norm bounds.