This repository contains code to accompany the paper "Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs", published in NeurIPS 2021. It provides an implementation of the proposed algorithm PruneMerge and several other algorithms for hierarchical clustering. Below you can find instructions for running the code.
The algorithm was implemented in Python 3.8. To install the requirements of this project, run the command:
pip install -r requirements.txt
No training is required since the algorithm is unsupervised.
To evaluate the performance of the algorithm, run the command:
python eval.py {experiment_type}
where {experiment_type} is the type of experiment to be run. This must be one of the following options: ['complete_graph', 'SBM_standard', 'SBM_planted_clique', 'HSBM', 'real_datasets']
The results will be displayed in a newly created output file "Results_{datetime}.txt", where {datetime} is the current date and time. For every experiment and every hierarchical tree construction, the exact and approximated Dasgupta's cost is printed.