Constant-Factor Local Approximation for Bipartite Densest Subgraph

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\dot{\cup }T$ with at most $k$ vertices per side, our algorithm, starting from any vertex in $S\dot{\cup }T$, uses $O_{ϵ}(k^{4+ϵ})$ neighbour queries to find a subgraph $X\dot{\cup }Y$ of density ${\Omega }_{ϵ}(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 this upper bound 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 Lovasz–Simonovits curve to the bipartite density problem, based on weak-${\ell }_p$ norm bounds.