Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better

Code for fast combinatorial methods to solve cluster deletion (DegMFP and RatMFP) and combinatorial solver for STC-LP.

Repo for the ICML 2024 paper:

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better

arXiv ICML 2024

Code Organization

Experiments

The experiments can be found in the Experiments folder. run-cd-functions.jl contains the code to run a single instance of the cluster deletion problem with a given method. The experiments are separated between CD-experiments and merge-experiments, with

The CD-experiments folder contains the experiments for the cluster deletion problem.

• run_many_main.jl runs all the experiments from the paper
• cd-table-print-results.jl prints the results from the experiments in a table format and plots the figures
• mpf-tests.jl can be used to run the MFP methods faster

Methods

You can find the implementations for the deterministic MFP methods (DegMFP and RatMFP) in src/run_cd_functions.jl.

The implementation for the combinatorial solver for STC-LP can be found in src/cd_lp_minst_relaxations.jl.

Data

This repo contains some small toy graphs in the folder data/smallgraphs.

Most of the standardized graphs used in the experiments can be downloaded from google drive. These graphs are in the format needed to run the experiments.

Instead, the graphs used in the paper can be downloaded from suitesparse.com and standardized using the data/standardize-snap-graphs.jl script.

Acknowledgements

Our implementation is based on nveldt's repo FastCC-via-STC.

Reference

If you find our work helpful, please cite our paper:

@misc{balmaseda2024combinatorial,
  title={Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better}, 
  author={Vicente Balmaseda and Ying Xu and Yixin Cao and Nate Veldt},
  year={2024},
  eprint={2404.16131},
  archivePrefix={arXiv},
  primaryClass={cs.DS}
}