Paper ID: 887
Title: A Simple and Strongly-Local Flow-Based Method for Cut Improvement

Review #1
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): The authors present a new algorithm to efficiently find an algorithm around a node. Interestingly the running time of the algorithm depends only on the size of the output cluster and not on the size of the entire graph.  The algorithm presented here is strictly weaker than the algorithm presented in SODA 2014 by Orecchia and Zhu but it is more natural and easy to use.

Clarity - Justification: The paper is well written and it explain clearly the problem and the main results.

Significance - Justification: The problem of finding good clusters locally is a fundamental problem in graph analysis. Unfortunately the results presented here are weaker than previous work so I am not sure that the paper would interest to a broad audience.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): I think that the topic of the paper is interesting but I'm not convinced that the presented algorithm outperforms the algorithm by Orecchia and Zhu neither theoretically nor experimentally.  For example, one important corollary of Orecchia and Zhu work is that if a well connected cluster C is loosely connected to the rest of the graph then there exists a local algorithm that efficiently finds a cluster C' such that the conductance of C' and the conductance of C are just a multiplicative factor apart. Is this true also when we use this new result?  Furthermore the proofs have some small(probably fixable) issues: - appendix ln. 49  "-f(R)vol(\hat(R))" -> "vol(R\cap \hat{S})" - appendix ln. 85 \hat{\phi} is not defined - appendix step  from ln. 93 to ln. 95 is not clear to me - appendix ln.102, \frac{vol(\hat(R))}{vol(V)}(1-f(R)) < 1 so how can you get \gamma?  Additional minor comments: - ln. 110 "Good" -> "(Good" - ln. 310 \hat{R} is not defined here - ln. 672 should it be \epsilon^2  Overall, I think that the paper is interesting but I am not too excited about it.

=====

Review #2
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): This work considers the problem of designing local algorithms for cut improvement: given a cut S in an undirected graph, one wants to find a nearby cut with good conductance, and do so in time that is related to the properties of S, but does not depend on the size of the whole graph. The cut improvement problem is a useful subroutine in graph partitioning, and algorithms like MQI have been used to improve cuts produced by other heuristics. Anderson and Lang proposed a new algorithm that worked for a relaxed definition of "nearby", but unlike MQI, it is not local. Orechhia and Zhu proposed a local version of this algorithm. This work got the running time to be small by modifying specific max flow algorithms: using Dinic's to a certain depth, the authors got an approximate solution in linear time, and using a modification to Goldberg-Rao, they gave an exact algorithm.  The current paper shows a simplification of the Orechhia-Zhu algorithm. The resulting algorithm has the advantage of being able to use any max flow algorithm as a subroutine. On the negative side, while the algorithm is still local, the run time is no longer linear in the size of the seed set. The authors empirically evaluate their algorithm on MRI scans.  

Clarity - Justification: The paper is well-written.

Significance - Justification: I think the technical claim of "removing dependence on specific algorithms" is a bit overstated. Orecchia and Zhu were interested in proving a fast theoretical bound on the run time, and for that purpose, using a max flow algorithm as a black box is not useful. The value of this work is to bring that theoretical advance closer to practice, and give a variant of the OZ algorithm that is simpler and more implementable. I think this is a non-trivial contribution for an important problem.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): -

=====

Review #3
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): A local algorithm for finding cuts works as follows: it get as input a seed set S and tries to find a low conductance cut "near S" (either containing or contained in S). The running time should only depend on the size of S. There is a rich history of such local algorithms, and personalized PageRank and other local spectral methods are extremely successful in this regard.  The methods give nice approximate guarantees (via local Cheeger inequalities), but do not give exact optimal solutions. In contrast to these methods, flow-based algorithms can give an optimal solutions, when the seed set is not too large and contains the optimum set. Such algorithms can be superior to spectral methods when the seed set is not tightly connected internally.  Orecchia and Zhu give the first local, flow-based algorithm, but it depends on changing the internals of complicated flow algorithm (Dinitz's blocking flows). This paper gives a local, flow-based algorithm using *any* flow procedure. Thus, one can use an off-the-shelf solver. The optimality properties hold, but the run-time guarantees are significantly weaker than Orecchia-Zhu.   Nonetheless, the authors demonstrate the algorithm in practice on a large graph. 

Clarity - Justification: Since I am somewhat familiar with this subject and topic, I could follow the overall ideas without much difficulty.  The technical portions are (maybe because of lack of space) somewhat terse, and we see long expressions (eqns (2), (4), (5)) without any help in the text to parse them. Of course, they are easy to derive, but some description would help.  For a non-expert to understand the significance, I suggest that the summary I wrote (or some version thereof) be written prominently in the introduction. 

Significance - Justification: Using max-flow algorithm, instead of spectral methods, is an excellent direction for work. This paper shows that such approaches are viable in practice. The experiments clearly show that this beats the local spectral methods (Personalized PageRank) in finding a low conductance cut. A few more experiments would be nice to see, to make their case even stronger.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): I do find the \ell_1 regularization connection nice, but it is not novel considering Gleich-Mahoney's earlier discovery. Of course the authors know. I say this only as a suggestion to de-emphasize this part in the abstract and introduction, so that readers don't think this is an important part of this paper.   The paper is a clear accept and will provide a new set of techniques for cut analysis.

=====