Dynamic Spectral Clustering with Provable Approximation Guarantee
Authors: Steinar Laenen, He Sun
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental studies on both synthetic and real-world datasets further confirm the practicality of our designed algorithm. |
| Researcher Affiliation | Academia | 1School of Informatics, University of Edinburgh, United Kingdom. Correspondence to: Steinar Laenen <steinar.laenen@ed.ac.uk>, He Sun <h.sun@ed.ac.uk>. |
| Pseudocode | Yes | Algorithm 1 Spectral Clustering(G, k); Algorithm 2 Sample Edge(e, G, τ); Algorithm 3 Static SZSparsifier(G, τ); Algorithm 4 Update Sparsifier(Gt, Ht, sp t , e, τ); Algorithm 5 Contract Graph(Ht, P); Algorithm 6 Query Spec Clustering(GT , HT , e GT , γ, ℓ); Algorithm 7 Update Contracted Graph(Gt, e Gt, e) |
| Open Source Code | Yes | Our code can be downloaded from https://github.com/steinarlaenen/Dynamic-Spectral-Clustering-With-Provable-Approximation-Guarantee. |
| Open Datasets | Yes | We study graphs generated from the stochastic block model (SBM), and introduce two dynamic extensions to generate new clusters and merge existing clusters. We further evaluate our algorithm on the MNIST dataset (Lecun et al., 1998), which consists of 10 classes of handwritten digits and has 70, 000 images, and the letter subset of the EMNIST dataset (Cohen et al., 2017) |
| Dataset Splits | No | No specific training, validation, or test dataset splits (e.g., percentages, sample counts, or citations to predefined splits) were explicitly mentioned for reproducibility. |
| Hardware Specification | Yes | Algorithms were implemented in Python 3.12.1 and experiments were performed using a Lenovo Think Pad T15G, with an Intel(R) Xeon(R) W-10855M CPU@2.80GHz processor and 126 GB RAM. |
| Software Dependencies | No | The paper only mentions 'Python 3.12.1' without listing other specific versioned libraries or solvers used, which is insufficient for reproducible software dependencies according to the guidelines. |
| Experiment Setup | Yes | We set p = 0.1, q = 0.01, r1 = 0.95, and s = 0.00001, and plot the results in the left plots of Figure 2. We set p = 0.1, q = 0.001, r2 = 0.95, and s = 0.00001, and plot the results in the right plots of Figure 2. We construct a k-nearest neighbour graph for each dataset, and set k = 100 (resp. k = 200) for MNIST (resp. EMNIST). |