Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
Authors: Vicente Balmaseda, Ying Xu, Yixin Cao, Nate Veldt
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We accompany our theoretical results with practical implementations and numerical experiments. |
| Researcher Affiliation | Academia | 1Department of Computer Science and Engineering, Texas A&M University, College Station, Texas, USA 2Department of Computing, Hong Kong Polytechnic University, Hong Kong, China. |
| Pseudocode | Yes | Algorithm 1 Pivot( ˆG = (V, ˆE)) Algorithm 2 MATCHFLIPPIVOT(G = (V, E)) Algorithm 3 STC-LP-ROUND(G = (V, E)) Algorithm 4 Faster maximal edge-disjoint open wedge set Algorithm 5 [i, j, jold, finished] = TRIANGLEINCREMENT(i, j, jold, next, finished) Algorithm 6 [i, j, jold, next, finished] = OPENWEDGEINCREMENT(i, j, jold, next, finished) Algorithm 7 Combinatorial solver for STC LP |
| Open Source Code | Yes | Code for our algorithms and experiments can be found at https: //github.com/vibalcam/combinatorial-cluster-deletion. |
| Open Datasets | Yes | For the most direct comparison with previous work (Veldt, 2022), we consider the same collection of large graphs from the SNAP Repository (Leskovec & Krevl, 2014)... The graphs in Figure 4 are from the Facebook100 dataset (Traud et al., 2012). The small graphs considered in Table 1 are all available from the Suitesparse matrix collection (Davis & Hu, 2011). |
| Dataset Splits | No | The paper mentions various datasets but does not provide specific training, validation, and test splits (e.g., percentages, sample counts, or explicit references to predefined splits). It does not specify a cross-validation setup or stratified splitting. |
| Hardware Specification | No | Our experiments were run on a laptop with 16 GB of RAM. This is a general description of a computing device and memory, but it does not specify the exact GPU/CPU models, processor types, or other detailed hardware specifications. |
| Software Dependencies | No | Our algorithms are implemented in Julia. For solving minimum s-t cut problems in practice, we instead apply a fast Julia implementation of the push-relabel algorithm for maximum s-t flows. The paper mentions Julia as the programming language and Gurobi as optimization software, but it does not provide specific version numbers for Julia, Gurobi, or any other libraries/packages used. |
| Experiment Setup | No | The paper describes the algorithmic components and their theoretical properties. However, it does not explicitly provide specific hyperparameter values (e.g., learning rate, batch size, epochs), details on model initialization, or other system-level training settings. The 'Cluster merging heuristic' is mentioned, but its parameters are not detailed. |