Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Online Dense Subgraph Discovery via Blurred-Graph Feedback
Authors: Yuko Kuroki, Atsushi Miyauchi, Junya Honda, Masashi Sugiyama
ICML 2020 | Venue PDF | 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). |