Online Dense Subgraph Discovery via Blurred-Graph Feedback
Authors: Yuko Kuroki, Atsushi Miyauchi, Junya Honda, Masashi Sugiyama
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we examine the performance of our proposed algorithms DS-Lin and DS-SR. First, we conduct experiments for DS-Lin and show that DS-Lin can find a nearly-optimal solution without sampling any single edges. Second, we perform experiments for DS-SR and demonstrate that DS-SR is applicable to large-sized graphs and significantly reduces the number of samples for single edges, compared to that of the state-of-the-art algorithm. Throughout our experiments, to solve the LPs in Charikar s algorithm (Charikar, 2000), we used a state-of-the-art mathematical programming solver, Gurobi Optimizer 7.5.1, with default parameter settings. All experiments were conducted on a Linux machine with 2.6 GHz CPU and 130 GB RAM. The code was written in Python. |
| Researcher Affiliation | Academia | 1The University of Tokyo, Japan 2RIKEN AIP, Japan. |
| Pseudocode | Yes | Algorithm 2 DS-Lin. Algorithm 3 DS-SR. Algorithm 1 Unconstrained 0 1 quadratic programming. |
| Open Source Code | No | The paper states 'The code was written in Python.' but does not provide a specific link or explicit statement about making the source code publicly available for the described methodology. |
| Open Datasets | Yes | Table 1 lists real-world graphs on which our experiments were conducted. Most of those can be found on Mark Newman s website1 or in SNAP datasets2. For each graph, we construct the edge weight w using the following simple rule, which is inspired by the knockout densest subgraph model introduced by Miyauchi & Takeda (2018). 1http://www-personal.umich.edu/ mejn/netdata/ 2http://snap.stanford.edu/ |
| Dataset Splits | No | The paper describes 'exploration period' in the bandit setting and mentions 'sampling oracle' but does not specify explicit train/validation/test dataset splits with percentages, sample counts, or references to predefined splits. |
| Hardware Specification | Yes | All experiments were conducted on a Linux machine with 2.6 GHz CPU and 130 GB RAM. |
| Software Dependencies | Yes | we used a state-of-the-art mathematical programming solver, Gurobi Optimizer 7.5.1, with default parameter settings. |
| Experiment Setup | Yes | We set the minimum size of queryable subsets k = 10, 20, 30 for Karate, Lesmis, and Polbooks, and k = 10, 40, 70 for Adjnoun, Jazz, and Email. [...] We set λ = 100 and R = 1. [...] we terminate the while-loop of our algorithm once the number of iterations exceeds 10,000 except for the initialization steps. To be consistent, we also set T = m + 10000 in Naive. [...] For DS-SR, in order to make Tt positive, we run the experiments with a budget T = 10 log10 Pn+1 i=1 i for all instances. For R-Oracle, we set γ = 0.9 and ε = 0.9 as in Miyauchi & Takeda (2018). |