2020/10/16 by Kartik Lakhotia, Lakhotia, Kartik, Rajgopal Kannan +5
Computer Science · #Caching and Content Delivery #Graph Theory and Algorithms #Cloud Computing and Resource Management
paper · pdf · doi:10.48550/arxiv.2010.08695
Tip decomposition is a crucial kernel for mining dense subgraphs in bipartite\nnetworks, with applications in spam detection, analysis of affiliation networks\netc. It creates a hierarchy of vertex-induced subgraphs with varying densities\ndetermined by the participation of vertices in butterflies (2,2-bicliques). To\nbuild the hierarchy, existing algorithms iteratively follow a\ndelete-update(peeling) process: deleting vertices with the minimum number of\nbutterflies and correspondingly updating the butterfly count of their 2-hop\nneighbors. The need to explore 2-hop neighborhood renders tip-decomposition\ncomputationally very expensive. Furthermore, the inherent sequentiality in\npeeling only minimum butterfly vertices makes derived parallel algorithms prone\nto heavy synchronization.\n In this paper, we propose a novel parallel tip-decomposition algorithm --\nREfine CoarsE-grained Independent Tasks (RECEIPT) that relaxes the peeling\norder restrictions by partitioning the vertices into multiple independent\nsubsets that can be concurrently peeled. This enables RECEIPT to simultaneously\nachieve a high degree of parallelism and dramatic reduction in\nsynchronizations. Further, RECEIPT employs a hybrid peeling strategy along with\nother optimizations that drastically reduce the amount of wedge exploration and\nexecution time.\n We perform detailed experimental evaluation of RECEIPT on a shared-memory\nmulticore server. It can process some of the largest publicly available\nbipartite datasets orders of magnitude faster than the state-of-the-art\nalgorithms -- achieving up to 1100x and 64x reduction in the number of thread\nsynchronizations and traversed wedges, respectively. Using 36 threads, RECEIPT\ncan provide up to 17.1x self-relative speedup. Our implementation of RECEIPT is\navailable at https://github.com/kartiklakhotia/RECEIPT.\n