betaFeedback

WorksComputer Science

Constant-Factor Local Approximation for Bipartite Densest Subgraph

Abstract

Given a vertex vv in a large bipartite graph GG, can one quickly find a small densely connected region near vv? 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 GG 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 SS and TT, its density is d(S,T):=e(S,T)/∣S∣∣T∣d(S,T):=e(S,T)/\sqrt{|S||T|}, where e(S,T)e(S,T) is the number of edges between SS and TT. 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∪˙TS\mathbin{\dot\cup}T with at most kk vertices per side, our algorithm, starting from any vertex in S∪˙TS\mathbin{\dot\cup}T, uses Oε(k4+ε)O_ε(k^{4+ε}) neighbor queries to find a subgraph X∪˙YX\mathbin{\dot\cup}Y of density Ωε(d(S,T))Ω_ε(d(S,T)) on Oε(k2+ε)O_ε(k^{2+ε}) vertices, for every fixed ε>0ε>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 kk 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-ℓp\ell_p norm bounds.

Introduction

Identifying dense bipartite subgraphs is a fundamental primitive across machine learning, network science, and web data mining. Bipartite graphs model interactions between two kinds of entities: accounts and products in e-commerce, users and multimedia content on social platforms, authors and venues in bibliometrics, or queries and destination URLs in web search [12]. In fraud detection and cybersecurity, researchers search for dense bipartite subgraphs to detect botnets, astroturfing campaigns, and lockstep review manipulation, where malicious actors coordinate attacks against targeted subsets of resources [7, 20, 16, 35]. In web mining, dense subgraphs correspond to link-spam farms [15] and authoritative topic hubs [22]. In computational biology, dense subgraphs are used to identify regulatory motifs in genomic DNA [14], analyze drug–target interaction graphs, and uncover multi-functional complexes in gene annotation networks [34].

To quantify how tightly two sets of vertices are connected, we use the bipartite density objective [21, 2]. Throughout, G=(V,E)G=(V,E) is a finite simple undirected bipartite graph with a fixed bipartition V=L∪˙RV=L\mathbin{\dot\cup}R and maximum degree Δ\Delta. For nonempty vertex sets S⊆LS\subseteq L and T⊆RT\subseteq R with e(S,T)e(S,T) edges between them, their density is

d(S,T):=e(S,T)∣S∣∣T∣=e(S,T)∣S∣⋅e(S,T)∣T∣,d(S,T):=\frac{e(S,T)}{\sqrt{|S||T|}}=\sqrt{\frac{e(S,T)}{|S|}\cdot\frac{e(S,T)}{|T|}},

the geometric mean of the average degree from SS into TT and the average degree from TT into SS.

The maximum of d(S,T)d(S,T) over all nonempty sets S,TS,T on opposite sides can be computed in polynomial time by linear programming [9]. However, on modern web-scale networks—frequently spanning hundreds of millions of vertices and billions of edges [33]—such global algorithms are computationally prohibitive, as their running time and memory footprint scale with the size of the entire graph. We therefore study the local formulation [2]: given a starting vertex vv and a target size parameter kk, find a dense bipartite subgraph in the vicinity of vv using a number of queries and running time that depend solely on kk, completely independent of the graph size ∣V∣|V| and maximum degree Δ\Delta.

Classical local clustering algorithms for low-conductance sets [36, 3, 1] seek sets with few boundary edges relative to their total degree. In contrast, d(S,T)d(S,T) is independent of edges leaving S∪TS\cup T. Dense bipartite subgraphs in interaction graphs often have many edges to the rest of the graph—for example, when fraudulent accounts add large numbers of legitimate interactions as “camouflage” [16]. With these camouflage edges, the cut conductance of S∪TS\cup T can approach 1. Standard random-walk and diffusion methods can then quickly leave the target, so we need local algorithms designed specifically for the bipartite density objective (see Figure 1).

A complete bipartite subgraph with leaves

Figure 1. A complete bipartite subgraph (S,T)(S,T) with kk vertices in SS (blue) and kk in TT (orange), each with D≥1D \ge1 leaves (gray) outside S∪TS \cup T. Here d(S,T)=kd(S,T)=k for every DD. Each vertex of S∪TS \cup T has DD of its k+Dk+D edges leaving S∪TS \cup T, so the conductance of S∪TS \cup T is at least D/(k+D)D/(k+D), which tends to one as D/k→∞D/k \to\infty. Every star in this graph has density at most k+D\sqrt{k}+D, which is o(k)o(k) for D=o(k2)D=o(k^2).

More formally, the local algorithm receives a starting vertex vv, an integer k≥1k\geq1, and adjacency-list access to GG, as in Andersen [2]. We count neighbor queries: we read a specified entry of an adjacency list, or receive ⊥\perp past its end. The guarantee is measured against unknown cohesive sets S⊆LS\subseteq L, T⊆RT\subseteq R (Definition 1.1) with at most kk vertices on each side. We require the algorithm to succeed from every starting vertex in S∪TS\cup T, using a number of queries independent of ∣V∣|V|. An approximation ratio α≥1\alpha\geq1 means returning nonempty sets X⊆LX\subseteq L, Y⊆RY\subseteq R with d(X,Y)≥d(S,T)/αd(X,Y)\geq d(S,T)/\alpha. For a single vertex, we write e(u,T):=e({u},T)e(u,T):=e(\{u\},T) and e(S,w):=e(S,{w})e(S,w):=e(S,\{w\}).

We ask for approximation, not recovery: the union of the returned sets need not contain the starting vertex or intersect S∪TS\cup T (after adding vv to the returned set on its side, the density is at least d(X,Y)/2d(X,Y)/\sqrt{2}; see Lemma B.3). A star with at least d(S,T)2d(S,T)^2 leaves has density at least d(S,T)d(S,T) and is therefore an acceptable output.

Andersen’s algorithm can be implemented using O(Δk2)O(\Delta k^2) neighbor queries and returns sets X,YX,Y with O(Δk2)O(\Delta k^2) vertices each (this follows from Andersen’s analysis Andersen [2]; see also Appendix § 9.§ 2). Its approximation ratio is bounded by O(1+log⁡2(Δ/d(S,T)))O(1+\log_2(\Delta/d(S,T))) Andersen [2]. This bound is constant only when d(S,T)=Ω(Δ)d(S,T)=\Omega(\Delta). For the complete bipartite subgraph of Figure 1 with DD camouflage edges per vertex, the lower bound on the returned density is Ω(k/(1+log⁡2((k+D)/k)))\Omega(k/(1+\log_2((k+D)/k))), which decreases as DD grows even though d(S,T)=kd(S,T)=k. The density is invariant under the addition of edges outside the subgraph induced by S∪TS \cup T, and the guarantee is not. Whether this dependence on the maximum degree is necessary for local approximation was open.

Our results

Our main result is a constant-factor local approximation algorithm for the bipartite densest subgraph problem. We cannot guarantee success from every vertex of S∪TS \cup T for arbitrary target sets S,TS,T, since a vertex in S∪TS \cup T may have few or no edges into the opposite target set. We therefore require every target vertex to have at least half the average degree of its side within the target subgraph.

Definition 1.1 (Cohesive sets). Nonempty sets S⊆LS \subseteq L, T⊆RT \subseteq R with e(S,T)>0e(S,T)>0 are cohesive if e(u,T)≥e(S,T)2∣S∣e(u,T) \ge\frac{e(S,T)}{2|S|} for all u∈Su \in S, and e(S,w)≥e(S,T)2∣T∣e(S,w) \ge\frac{e(S,T)}{2|T|} for all $w \in T.

We use the term cohesiveness to formalize the minimum-degree structure already implicit in Andersen’s proof of his main theorem Andersen [2]. For any sets S⊆LS \subseteq L, T⊆RT \subseteq R with e(S,T)>0e(S,T)>0, there are cohesive subsets S∗⊆SS^* \subseteq S, T∗⊆TT^* \subseteq T of at least the same density, d(S∗,T∗)≥d(S,T)d(S^*,T^*) \ge d(S,T) (Lemma A.1). For arbitrary S,TS,T, our setting is exactly that of Andersen, whose algorithm succeeds from every vertex of subsets that are selected by a minimum-degree argument and contain at least half of the edges (see the discussion in Corollary A.2).

Theorem 1.2 (Main result). For every ϵ>0\epsilon> 0, all cohesive sets S⊆LS \subseteq L, T⊆RT \subseteq R with ∣S∣,∣T∣≤k|S|, |T| \le k, and every starting vertex v∈S∪˙Tv \in S \mathbin{\dot\cup} T, the deterministic algorithm LocalDense2+ϵ(G,v,k)_{2+\epsilon}(G, v, k) (Algorithm 2) returns nonempty sets X⊆LX \subseteq L, Y⊆RY \subseteq R with the following guarantees:

(i) Locality and complexity: The output (X,Y)(X,Y) has Oϵ(k2+ϵ)O_\epsilon(k^{2+\epsilon}) vertices, and the algorithm makes Oϵ(k2+ϵmin⁡{Δlog⁡22(2k),k2})O_\epsilon(k^{2+\epsilon}\min\{\Delta\log_2^2(2k), k^2\}) neighbor queries and runs in time O~ϵ(k2+ϵmin⁡{Δ,k2})\widetilde{O}_\epsilon(k^{2+\epsilon}\min\{\Delta, k^2\}).

(ii) Constant-factor approximation: d(X,Y)≥316eϵ1+ϵd(S,T)d(X,Y) \ge\frac{\sqrt{3}}{16\sqrt{e}}\frac{\epsilon}{1+\epsilon}d(S,T), independent of edges outside the subgraph induced by S∪˙TS \mathbin{\dot\cup} T.

We complement our positive results by proving limitations on the output size:

Theorem 1.3 (Limitations on the output size, informal). No possibly randomized algorithm with neighbor-query access that, for all cohesive sets S⊆LS \subseteq L, T⊆RT \subseteq R with kk vertices on each side, returns nonempty sets X⊆LX \subseteq L, Y⊆RY \subseteq R with d(X,Y)=Ω(d(S,T))d(X,Y)=\Omega(d(S,T)) with probability at least 2/32/3 from at least one vertex in S∪˙TS \mathbin{\dot\cup} T can guarantee an output bound of o(k2)o(k^2) vertices on each side if either:

(i) Unconditional: Its number of queries depends only on kk; or

(ii) Computational: Assuming the Strongish Planted Clique Hypothesis (SPCH), its running time is at most f(k)∣V∣cf(k)|V|^c for a constant cc and a computable function ff of kk alone.

Up to the factor kϵk^\epsilon, our output size is therefore the best possible in both settings. We discuss the main result in § 2 and the limitations in § 3.

Our technique

From power iteration to prefix sweeps. Our starting point is Andersen’s pruned power iteration [2]. We maintain a nonnegative vector xx indexed by vertices and multiply it by the adjacency matrix, setting y(w):=∑ux(u)y(w) := \sum_u x(u), where the sum is over the neighbors of ww. For now, we set aside rescaling and pruning. The mass of xx on a set QQ is ∑u∈Qx(u)\sum_{u\in Q}x(u). Suppose every vertex of SS has at least aa neighbors in TT and every vertex of TT at least bb in SS. After one multiplication, the mass of yy on TT is at least aa times the mass of xx on SS, and after two, the mass on SS is at least abab times its original value. These bounds hold even with edges leaving the target, since all coordinates are nonnegative. By cohesiveness, there exist powers of two a,b∈[1,k]a,b\in[1,k], with ab>d(S,T)/4\sqrt{ab}>d(S,T)/4 (see § 2.2; we remove this choice later). We cannot locate a dense pair from the growth of target mass alone: the target is unknown, and mass outside it may grow faster. Andersen extracts a dense pair from growth of the Euclidean norm. Instead we sort consecutive vectors and consider their initial segments, or prefixes. We seek a Lovász–Simonovits-type win–win [36, 3]: either we find a dense prefix pair in a sweep, or we obtain upper bounds on prefix sums that eventually become incompatible with the mass that remains on the target. Here set size means number of vertices, rather than volume.

References

  1. [1]Zeyuan Allen-Zhu, Silvio Lattanzi, and Vahab Mirrokni. A local algorithm for finding well-connected clusters. In Proceedings of the 30th International Conference on Machine Learning (ICML 2013), volume 28 of Proceedings of Machine Learning Research, pages 396–404, 2013. URL https://proceedings.mlr.press/v28/allenzhu13.html.
  2. [2]Reid Andersen. A local algorithm for finding dense subgraphs. ACM Transactions on Algorithms, 6 (4):60:1–60:12, 2010. doi: 10.1145/1824777.1824780. URL https://doi.org/10.1145/1824777.1824780.
  3. [3]Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using PageRank vectors. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 475–486, 2006. doi: 10.1109/FOCS.2006.44. URL https://doi.org/10.1109/FOCS.2006.44.
  4. [4]Reid Andersen, Shayan Oveis Gharan, Yuval Peres, and Luca Trevisan. Almost optimal local graph clustering using evolving sets. Journal of the ACM, 63(2):15:1–15:31, 2016. doi: 10.1145/2856030. URL https://doi.org/10.1145/2856030.
  5. [5]Artur Back de Luca, Kimon Fountoulakis, and Shenghao Yang. Local graph clustering with noisy labels. In 12th International Conference on Learning Representations (ICLR 2024), 2024. URL https://openreview.net/forum?id=89A5c6enfc.arxiv.org/abs/2310.08031
  6. [6]Colin Bennett and Robert C. Sharpley. Interpolation of Operators, volume 129 of Pure and Applied Mathematics. Academic Press, 1988. ISBN 978-0-12-088730-9.
  7. [7]Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. CopyCatch: Stopping group attacks by spotting lockstep behavior in social networks. In Proceedings of the 22nd International Conference on World Wide Web (WWW 2013), pages 119–130, 2013. doi: 10.1145/2488388.2488400. URL https://doi.org/10.1145/2488388.2488400.
  8. [8]Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica, 26(5):495–519, 2006. doi: 10.1007/s00493-006-0029-7. URL https://doi.org/10.1007/s00493-006-0029-7.
  9. [9]Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In APPROX 2000, volume 1913 of Lecture Notes in Computer Science, pages 84–95, Springer, 2000. doi: 10.1007/3-540-44436-X_10. URL https://doi.org/10.1007/3-540-44436-X_10.
  10. [10]Fan Chung. A local graph partitioning algorithm using heat kernel PageRank. Internet Mathematics, 6(3):315–330, 2009. doi: 10.1080/15427951.2009.10390643. URL https://doi.org/10.1080/15427951.2009.10390643.
  11. [11]Yizhou Dai, Miao Qiao, and Lijun Chang. Anchored densest subgraph. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD 2022), pages 1200–1213, 2022. doi: 10.1145/3514221.3517890. URL https://doi.org/10.1145/3514221.3517890.
  12. [12]Inderjit S Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2001), pages 269–274, 2001. doi: 10.1145/502512.502550. URL https://doi.org/10.1145/502512.502550.
  13. [13]Kimon Fountoulakis, Di Wang, and Shenghao Yang. p-norm flow diffusion for local graph clustering. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), volume 119 of Proceedings of Machine Learning Research, pages 3222–3232, 2020. URL https://proceedings.mlr.press/v119/fountoulakis20a.html.arxiv.org/abs/2005.09810
  14. [14]Eugene Fratkin, Brian T Naughton, Douglas L Brutlag, and Serafim Batzoglou. MotifCut: regulatory motifs finding with maximum density subgraphs. Bioinformatics, 22(14):e150–e157, 2006. doi: 10.1093/bioinformatics/btl243. URL https://doi.org/10.1093/bioinformatics/btl243.
  15. [15]David Gibson, Ravi Kumar, and Andrew Tomkins. Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB 2005), pages 721–732, 2005. URL https://www.vldb.org/conf/2005/papers/p721-gibson.pdf.
  16. [16]Bryan Hooi, Kijung Shin, Hyun Ah Song, Alex Beutel, Neil Shah, and Christos Faloutsos. Graph-based fraud detection in the face of camouflage. ACM Transactions on Knowledge Discovery from Data, 11(4):44:1–44:26, 2017. doi: 10.1145/3056563. URL https://doi.org/10.1145/3056563.
  17. [17]Yufan Huang, David F. Gleich, and Nate Veldt. Densest subhypergraph: Negative supermodular functions and strongly localized methods. In Proceedings of the ACM Web Conference 2024 (WWW 2024), pages 881–892, 2024. doi: 10.1145/3589334.3645624. URL https://doi.org/10.1145/3589334.3645624.
  18. [19]Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. doi: 10.1006/jcss.2001.1774. URL https://doi.org/10.1006/jcss.2001.1774.
  19. [20]Meng Jiang, Peng Cui, Alex Beutel, Christos Faloutsos, and Shiqiang Yang. Catching synchronized behaviors in large networks: A graph mining approach. ACM Transactions on Knowledge Discovery from Data, 10(4):35:1–35:27, 2016. doi: 10.1145/2746403. URL https://doi.org/10.1145/2746403.
  20. [21]Ravi Kannan and V. Vinay. Analyzing the structure of large graphs. Manuscript, July 13, 1999. URL https://www.cs.yale.edu/homes/kannan/Papers/webgraph.pdf.
  21. [22]Jon M Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604–632, 1999. doi: 10.1145/324133.324140. URL https://doi.org/10.1145/324133.324140.
  22. [23]Angsheng Li and Pan Peng. Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ratio measure. In Algorithms and Computation (ISAAC 2013), volume 8283 of Lecture Notes in Computer Science, pages 655–665. Springer, 2013. doi: 10.1007/978-3-642-45030-3_61. URL https://doi.org/10.1007/978-3-642-45030-3_61.
  23. [24]Meng Liu and David F. Gleich. Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering. In Advances in Neural Information Processing Systems, volume 33, pages 5023–5035, 2020. URL https://proceedings.neurips.cc/paper/2020/hash/3501672ebc68a5524629080e3ef60aef-Abstract.html.arxiv.org/abs/2006.08569
  24. [25]Raymond Liu. Bipartite density: from mixing time to local algorithms for dense subgraphs. Master of mathematics thesis, University of Waterloo, 2026. URL https://hdl.handle.net/10012/24018.
  25. [26]László Lovász and Miklós Simonovits. The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. In 31st Annual Symposium on Foundations of Computer Science (FOCS 1990), pages 346–354, 1990. doi: 10.1109/FSCS.1990.89553. URL https://doi.org/10.1109/FSCS.1990.89553.
  26. [27]László Lovász and Miklós Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms, 4(4):359–412, 1993. doi: 10.1002/rsa.3240040402. URL https://doi.org/10.1002/rsa.3240040402.
  27. [28]Peter Macgregor and He Sun. Local algorithms for finding densely connected clusters. In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), volume 139 of Proceedings of Machine Learning Research, pages 7268–7278, 2021. URL https://proceedings.mlr.press/v139/macgregor21a.html.arxiv.org/abs/2106.05245
  28. [29]Pasin Manurangsi. Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In STOC 2017, pages 954–961. ACM, 2017. doi: 10.1145/3055399.3055412. URL https://doi.org/10.1145/3055399.3055412. Theorem numbers refer to arXiv:1611.05991v2.
  29. [30]Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The strongest planted clique hypothesis and its consequences. In ITCS 2021, volume 185 of Leibniz International Proceedings in Informatics, pages 10:1–10:21. Schloss Dagstuhl, 2021. doi: 10.4230/LIPIcs.ITCS.2021.10. URL https://doi.org/10.4230/LIPIcs.ITCS.2021.10.
  30. [31]Pan Peng. A local algorithm for finding dense bipartite-like subgraphs. In Computing and Combinatorics (COCOON 2012), volume 7434 of Lecture Notes in Computer Science, pages 145–156. Springer, 2012. doi: 10.1007/978-3-642-32241-9_13. URL https://doi.org/10.1007/978-3-642-32241-9_13.
  31. [32]Pan Peng, Yuyang Wang, Joy Qiping Yang, and Yichun Yang. An exponential lower bound for spectral density estimation on unweighted graphs. In Proceedings of Thirty Ninth Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 5332–5357. PMLR, 2026. URL https://proceedings.mlr.press/v336/peng26a.html.arxiv.org/abs/2606.28188
  32. [33]Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. Locally densest subgraph discovery. In Proceedings of the 21st ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2015), pages 965–974, 2015. doi: 10.1145/2783258.2783299. URL https://doi.org/10.1145/2783258.2783299.
  33. [34]Barna Saha, Allison Hoch, Samir Khuller, Louiqа Raschid, and Xiao-Ning Zhang. Dense subgraphs with restrictions and applications to gene annotation graphs. In Annual International Conference on Research in Computational Molecular Biology, volume 6044 of Lecture Notes in Computer Science, pages 456–472. Springer, 2010. doi: 10.1007/978-3-642-12683-3_30. URL https://doi.org/10.1007/978-3-642-12683-3_30.
  34. [35]Kijung Shin, Bryan Hooi, and Christos Faloutsos. Fast, accurate, and flexible algorithms for dense subtensor mining. ACM Transactions on Knowledge Discovery from Data, 12(3):28:1–28:30, 2018. doi: 10.1145/3154414. URL https://doi.org/10.1145/3154414.
  35. [36]Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on Computing, 42(1):1–26, 2013. doi: 10.1137/080744888. URL https://doi.org/10.1137/080744888.
  36. [37]Shenghao Yang and Kimon Fountoulakis. Weighted flow diffusion for local graph clustering with node attributes: An algorithm and statistical guarantees. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023), volume 202 of Proceedings of Machine Learning Research, pages 39252–39276, 2023. URL https://proceedings.mlr.press/v202/yang23d.html.arxiv.org/abs/2301.13187

Paper details

vlnc:W_394nb7aq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools, LLM-generated ideas

View statement
Looking for related papers…
Contents