Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.10471 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914183788888064 |
|---|---|
| author | Chen, Jingbang Li, Weinuo Zhou, Yingli Zhou, Hangrui Mang, Qiuyang Wang, Can Fang, Yixiang Ma, Chenhao |
| author_facet | Chen, Jingbang Li, Weinuo Zhou, Yingli Zhou, Hangrui Mang, Qiuyang Wang, Can Fang, Yixiang Ma, Chenhao |
| contents | Counting $(p,q)$-bicliques in bipartite graphs is crucial for a variety of applications, from recommendation systems to cohesive subgraph analysis. Yet, it remains computationally challenging due to the combinatorial explosion to exactly count the $(p,q)$-bicliques. In many scenarios, e.g., graph kernel methods, however, exact counts are not strictly required. To design a scalable and high-quality approximate solution, we novelly resort to $(p,q)$-broom, a special spanning tree of the $(p,q)$-biclique, which can be counted via graph coloring and efficient dynamic programming. Based on the intermediate results of the dynamic programming, we propose an efficient sampling algorithm to derive the approximate $(p,q)$-biclique count from the $(p,q)$-broom counts. Theoretically, our method offers unbiased estimates with provable error guarantees. Empirically, our solution outperforms existing approximation techniques in both accuracy (up to 8$\times$ error reduction) and runtime (up to 50$\times$ speedup) on nine real-world bipartite networks, providing a scalable solution for large-scale $(p,q)$-biclique counting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10471 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scalable Approximate Biclique Counting over Large Bipartite Graphs Chen, Jingbang Li, Weinuo Zhou, Yingli Zhou, Hangrui Mang, Qiuyang Wang, Can Fang, Yixiang Ma, Chenhao Social and Information Networks Counting $(p,q)$-bicliques in bipartite graphs is crucial for a variety of applications, from recommendation systems to cohesive subgraph analysis. Yet, it remains computationally challenging due to the combinatorial explosion to exactly count the $(p,q)$-bicliques. In many scenarios, e.g., graph kernel methods, however, exact counts are not strictly required. To design a scalable and high-quality approximate solution, we novelly resort to $(p,q)$-broom, a special spanning tree of the $(p,q)$-biclique, which can be counted via graph coloring and efficient dynamic programming. Based on the intermediate results of the dynamic programming, we propose an efficient sampling algorithm to derive the approximate $(p,q)$-biclique count from the $(p,q)$-broom counts. Theoretically, our method offers unbiased estimates with provable error guarantees. Empirically, our solution outperforms existing approximation techniques in both accuracy (up to 8$\times$ error reduction) and runtime (up to 50$\times$ speedup) on nine real-world bipartite networks, providing a scalable solution for large-scale $(p,q)$-biclique counting. |
| title | Scalable Approximate Biclique Counting over Large Bipartite Graphs |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2505.10471 |