Dynamic Correlation Clustering in Sublinear Update Time
Authors: Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally we complement our theoretical analysis with experiments on real world data. and We conduct two sets of experiments. |
| Researcher Affiliation | Collaboration | 1Google Research 2Columbia University. |
| Pseudocode | Yes | Algorithm 1 AGREEMENTALGORITHM(G), Algorithm 2 Notify(u, ϵ), Algorithm 3 Dynamic Agreement (DA), Algorithm 4 Connect(u, ϵ, t), Algorithm 5 Anchor(u, ϵ, t), Algorithm 6 Clean(u, ϵ, t), Algorithm 7 Compute Connected Components( e G), Algorithm 8 PROBABILISTICAGREEMENT(u, v, ϵ), Algorithm 9 HEAVY(u, ϵ) |
| Open Source Code | Yes | Our code is written in Python 3.11.5 and is available at https://github.com/andreasr27/DCC. |
| Open Datasets | Yes | We use four graphs from SNAP (Leskovec & Krevl, 2014)... and we use Drift (Vergara et al., 2012; Rodriguez Lujan et al., 2014) from the UCI Machine Learning Repository (Dua & Graff, 2017). |
| Dataset Splits | No | The paper describes how dynamic node streams are created ('we first create a random arrival sequence for all the nodes. Subsequently in between any two additions, with probability p, we select at random a node of the current graph and delete it.'), but does not specify train/validation/test splits as the task is dynamic clustering on evolving graphs. |
| Hardware Specification | No | The paper does not provide specific hardware details such as GPU/CPU models or memory used for running experiments. |
| Software Dependencies | Yes | Our code is written in Python 3.11.5 |
| Experiment Setup | Yes | We set the deletion probability in between any two node arrivals to be 0.2. The agreement parameter is set to ϵ = 0.2... all our subroutines use a random sample of size 2 and the probability of a node joining the anchor set is set to 20/du... |