- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
Consider several characteristics of a graph; each characteristic is a real number (for instance, the clustering coefficient or mean path length). Fix target value for each characteristic. We aim to construct a graph with a fixed number of vertices N, such that its characteristics values are close to the targets. We start from some graph constructed by warm-start technique (we could start with random graph instead). Our only allowed way to change the graph is double-edge swap: remove edges (a, b),(c, d), add edges (a, d),(c, b).
The question is what sequence of swaps to do, to get from our starting graph to a graph with characteristics close to the targets. We assume that evaluation of graph characteristics is costly. A typical solution is to firstly do some training (which involve computing graphs' characteristics) to get a policy of choosing swaps. The policy itself must not involve recomputing graph characteristics of each after-swap candidate (such policies are called residual-free). So once we spend lots of compute on policy, we can use it at low computational cost – that is, given new target vector we can try to achieve the target by starting from warm-start graph and sequentially choosing swaps according to policy.
The main result of the paper: no residual-free policy beats random significantly. Second result: no learned method approaches greedy method (which just choose best swap based on true characteristics).
Critical strengths
If I understood the main results correctly, it seems interesting. Unfortunately, the exposition is very hard to follow, so I am not even sure that I understood the main results correctly.
Critical weaknesses
The paper is very hard to read. Here is some suggestions on how to improve readability (I wrote it only for several lines, after that I gave up – similar comments apply throughout the paper):
- Line 155 - define m_k
- Line 157 - “the loose tail is at issue” - not clear what it means.
- Line 159 - define N (it is defined only in the legend of Figure 1b). What is <k>? Why is it 6 (not 5 as k before was used as index for components of the target vector).
- Protocol is supposedly described in lines 159-161. It is not clear what protocol consists of - I get we start from warm-start graph of size N, but what is episode, how many candidates are generated, what is meant by greedy here, etc.
- Lines 179-181 - more specific definitions of beam and MH/SA
Thank you for the line-by-line comments. We used them as a checklist when rewriting §3, which now defines the task and the protocol before any result. Your reading of the two main results is correct, with two refinements at the end.
Your first result holds under the benchmark protocol (Protocol A): no tested swap policy that skips measuring its candidates beats random significantly. The revision calls such policies "candidate-oracle-free" in place of "residual-free". In a new matched protocol (Protocol B, §4.2), imitation learners whose demonstrations continue toward the tightest band do beat random: DAgger by 18.7 and BC by 10.3 percentage points (pp) in twelve-band mean satisfaction, the share of targets satisfied averaged over the twelve bands. Their training uses more teacher calls (the expert's candidate calls) and a different training distribution than the paper's common settings (§5.1).
Your second result also holds: each tested learned method stays below greedy. In Protocol B, greedy ranked by W and the value learner (a learned scorer that measures its candidates) share start graphs and measure K = 6 candidates each. Greedy leads by 29.3 pp in the twelve-band mean [25.1, 33.7]. It ranks the immediate W, while the learner predicts the best W that a depth-3 beam reaches. A learner given the exact per-candidate metric changes that greedy measures still trails by 11.9 pp (§4.2, §5.1).