Subhajit Sahu

Prof. Subhajit Sahu

orcid

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
12 August 2024
Verified
Conference Paper
Open access
Subhajit SahuSubhajit Sahu
Subhajit Sahu
KKKishore Kothapalli
Kishore Kothapalli
DBDip Sankar Banerjee
Dip Sankar Banerjee
Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions is critical in a number of applications, where the size of datasets have reached significant scales. This paper presents one of the most efficient implementations of the Leiden algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Leiden implementation, which we term as GVE-Leiden, outperforms NetworKit Leiden and cuGraph Leiden (running on NVIDIA A100 GPU) by 8.2 × and 3.0 × respectively — achieving a processing rate of 403M edges/s on a 3.8B edge graph. In addition, GVE-Leiden improves performance at a rate of 1.6 × for every doubling of threads.



1 May 2022
Verified
Conference Paper
Closed access
Subhajit SahuSubhajit Sahu
Subhajit Sahu
KKKishore Kothapalli
Kishore Kothapalli
DBDip Sankar Banerjee
Dip Sankar Banerjee
The design and implementation of parallel algorithms for dynamic graph problems is attracting significant research attention in the recent years, driven by numerous applications to social network analysis, neuroscience, and protein interaction networks. One such problem is the computation of PageRank values of vertices in a directed graph. This paper presents two new parallel algorithms for recomputing the PageRank values of vertices in a dynamic graph. Our techniques require the recomputation of the PageRank of only the vertices affected by the insertion/deletion of a batch of edges. We conduct detailed experimental studies of our algorithm on a set of 11 real-world graphs. Our results on Intel Xeon Silver 4116 CPU and NVIDIA Tesla V100 PCIe 16GB GPU indicate that our algorithms outperform static and dynamic update algorithms by $6.1\times$: and $8.6\times \mathbf{on}$ the CPU, and by 9.8×and $9.3\times\mathbf{on}$ the GPU respectively. We also compare the performance of the algorithms in batched mode to cumulative single-edge updates.

27 May 2024
Verified
Conference Paper
Closed access
Subhajit SahuSubhajit Sahu
Subhajit Sahu
KKKishore Kothapalli
Kishore Kothapalli
DBDip Sankar Banerjee
Dip Sankar Banerjee
Community detection is the problem of identifying natural divisions in networks. A relevant challenge in this problem is to find communities on rapidly evolving graphs. In this paper, we present our parallel Dynamic Frontier (DF) approach. Given a batch update of edge deletions or insertions, this approach incrementally identifies an approximate set of affected vertices in the graph with minimal overhead. We apply this approach to both Louvain, a high quality, and Label Propagation Algorithm (LPA), a fast static community detection algorithm. Our approach achieves a mean speedup of 7.3 × and 6.7 ×, when applied to Louvain and LPA respectively, compared to our parallel and optimized implementation of Δ-screening, a recently proposed state-of-the-art approach. Finally, we show how to combine Louvain and LPA with the DF approach to arrive at a hybrid algorithm. This algorithm produces high-quality communities while providing a speedup of 2.0 x on top of DF -based Louvain.