Parallel Peeling of Bipartite Networks for Hierarchical Dense Subgraph Discovery
Open Access
- 20 June 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 10 (2) , 1-35
Abstract
Wing and Tip decomposition are motif-based analytics for bipartite graphs that construct a hierarchy of butterfly (2,2-biclique) dense edge and vertex induced subgraphs, respectively. They have applications in several domains, including e-commerce, recommendation systems, document analysis, and others. Existing decomposition algorithms use a bottom-up approach that constructs the hierarchy in an increasing order of the subgraph density. They iteratively select the edges or vertices with minimum butterfly count peel , i.e., remove them along with their butterflies. The amount of butterflies in real-world bipartite graphs makes bottom-up peeling computationally demanding. Furthermore, the strict order of peeling entities results in a large number of sequentially dependent iterations. Consequently, parallel algorithms based on bottom up peeling incur heavy synchronization and poor scalability. In this article, we propose a novel Parallel Bipartite Network peelinG (PBNG) framework that adopts a two-phased peeling approach to relax the order of peeling, and in turn, dramatically reduce synchronization. The first phase divides the decomposition hierarchy into few partitions and requires little synchronization. The second phase concurrently processes all partitions to generate individual levels of the hierarchy and requires no global synchronization. The two-phased peeling further enables batching optimizations that dramatically improve the computational efficiency of PBNG. We empirically evaluate PBNG using several real-world bipartite graphs and demonstrate radical improvements over the existing approaches. On a shared-memory 36 core server, PBNG achieves up to 19.7× self-relative parallel speedup. Compared to the state-of-the-art parallel framework P ar B utterfly , PBNG reduces synchronization by up to 15,260× and execution time by up to 295×. Furthermore, it achieves up to 38.5× speedup over state-of-the-art algorithms specifically tuned for wing decomposition. Our source code is made available at https://github.com/kartiklakhotia/RECEIPT .Keywords
All Related Versions
Funding Information
- Defense Advanced Research Projects Agency (FA8750-17-C-0086)
- National Science Foundation (CNS-2009057 and OAC-1911229)
This publication has 61 references indexed in Scilit:
- Engineering Parallel Algorithms for Community Detection in Massive NetworksIEEE Transactions on Parallel and Distributed Systems, 2015
- Dense subgraph maintenance under streaming edge weight updates for real-time story identificationThe VLDB Journal, 2013
- Truss decomposition in massive networksProceedings of the VLDB Endowment, 2012
- On triangulation-based dense neighborhood graph discoveryProceedings of the VLDB Endowment, 2010
- A Survey of Algorithms for Dense Subgraph Discovery2010
- Analyzing Consumer-Product Graphs: Empirical Findings and Applications in Recommender SystemsManagement Science, 2007
- MotifCut: regulatory motifs finding with maximum density subgraphsBioinformatics, 2006
- Vertex similarity in networksPhysical Review E, 2006
- The structure of scientific collaboration networksProceedings of the National Academy of Sciences of the United States of America, 2001
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969