ParHAC: Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth Skip to main content Explore our many areas of focus Explore all research areas Applied AI & sciences Earth AI Health AI Science AI Sustainability & crisis resilience Foundational ML & algorithms Algorithms & theory Information retrieval Machine intelligence Machine perception Natural language processing People, systems & quantum AI Human-computer interaction and visualization Networking Quantum AI Responsible AI Anti abuse Software engineering Software systems Learn More Publications Projects Building a collaborative ecosystem Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products. Open source Discover open-source code and collaborate with the community. Shaping the future together See all programs Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming. Locations Find your place in our global offices and research labs. Translating discovery into real-world impact People Our researchers drive advancements in computer science through both fundamental and applied research. Teams Collaborative groups tackling the world's most challenging AI problems. Research Explore our many areas of focus Explore all research areas Applied AI & sciences Earth AI Health AI Science AI Sustainability & crisis resilience Foundational ML & algorithms Algorithms & theory Information retrieval Machine intelligence Machine perception Natural language processing People, systems & quantum AI Human-computer interaction and visualization Networking Quantum AI Responsible AI Anti abuse Software engineering Software systems Learn More Publications Projects Resources Building a collaborative ecosystem Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products. Open source Discover open-source code and collaborate with the community. Conferences & events Careers Shaping the future together See all programs Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming. Locations Find your place in our global offices and research labs. Blog About Translating discovery into real-world impact People Our researchers drive advancements in computer science through both fundamental and applied research. Teams Collaborative groups tackling the world's most challenging AI problems. Google Research Google AI Learn about all our AI Google DeepMind Explore the frontier of AI Google Labs Try our AI experiments Research Resources Conferences & events Careers Blog About Search Home Publications ParHAC: Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth David Eisenstat Jessica Shi Jakub Łącki Laxman Dhulipala Vahab Mirrokni NeurIPS'22 (2022) Download Google Scholar Copy Bibtex Abstract Obtaining scalable algorithms for hierarchical agglomerative clustering (HAC) is of significant interest due to the massive size of real-world datasets. At the same time, efficiently parallelizing HAC is difficult due to the seemingly sequential nature of the algorithm. In this paper, we address this issue and present ParHAC, the first efficient parallel HAC algorithm with sublinear depth for the widely-used average-linkage function. In particular, we provide a (1+ϵ)-approximation algorithm for this problem on m edge graphs using O(m polylog m) work and poly-logarithmic depth. Moreover, we show that obtaining similar bounds for exact average-linkage HAC is not possible under standard complexity-theoretic assumptions. We complement our theoretical results with a comprehensive study of the ParHAC algorithm in terms of its scalability, performance, and quality, and compare with several state-of-the-art sequential and parallel baselines. On a broad set of large publicly-available real-world datasets, we find that ParHAC obtains a 50.1x speedup on average over the best sequential baseline, while achieving quality similar to the exact HAC algorithm. We also show that ParHAC can cluster one of the largest publicly available graph datasets with 124 billion edges in a little over three hours using a commodity multicore machine. Research Areas Algorithms and theory Meet the teams driving innovation Our teams advance the state of the art through research, systems engineering, and collaboration across Google. See our teams Follow us Explore our other initiatives Google AI Discover how Google AI is committed to enriching knowledge and solving complex challenges Products Build Research Responsibility Societal Impact About Google Cloud High-performance infrastructure for cloud computing, data analytics & machine learning Overview Solutions Products Pricing Resources Google DeepMind Our mission is to build AI responsibly to benefit humanity Models Research Science About Google Labs Explore the future of AI responsibly with Google Labs About Experiments Stay connected About Google Google Products Privacy Terms Cookies management controls ×