Cakewalk Sampling
Authors: Uri Patish, Shimon Ullman2400-2407
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | As a first use case, we empirically study the efficiency in which sampling methods can recover locally maximal cliques in undirected graphs. Not only do we show how our adaptive sampler outperforms related methods, we also show how it can even approach the performance of established clique algorithms. As a second use case, we consider how greedy algorithms can be combined with our adaptive sampler, and we demonstrate how this leads to superior performance in k-medoid clustering. |
| Researcher Affiliation | Academia | Uri Patish, Shimon Ullman Weizmann Institute of Science, Rehovot, Israel |
| Pseudocode | Yes | Algorithm 1 Cakewalk |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-source code availability for the described methodology. |
| Open Datasets | Yes | As a benchmark for the clique problem, we used 80 undirected graphs that were published as part of the second DIMACS challenge (Johnson and Trick 1996). Using a publicly available collection (White 2017), we gathered 38 datasets that had between 500 and 1000 data points. |
| Dataset Splits | No | The paper mentions using datasets for experiments but does not specify train/validation/test splits, percentages, or absolute counts for reproducibility. It implies a sampling process rather relevant to the optimization problem rather than explicit data splits for training/validation. |
| Hardware Specification | No | The paper does not specify any hardware details such as CPU, GPU models, or memory used for running the experiments. |
| Software Dependencies | No | The paper mentions the use of optimizers like Adam and Ada Grad, but does not provide specific version numbers for any software dependencies, libraries, or programming languages used in the implementation. |
| Experiment Setup | Yes | We have executed a method for 100 |V | samples (hence runtime is fixed per graph), and recorded the following items at the execution s end. We tested each method on all 80 graphs, letting it maximize the softclique-size function using various values of κ. Since a-priori we do not know which κ will lead some method towards an inclusion maximal clique, we have executed each method with each of the values 0.0, 0.1, . . . , 1.0 as κ. For estimating ˆμ, ˆσ and ˆF, we have used the last 100 objective values. |