The Product Cut
We introduce a theoretical and algorithmic framework for multi-way graph partitioning that relies on a multiplicative cut-based objective. We refer to this objective as the Product Cut. We provide a detailed investigation of the mathematical properties of this objective and an effective algorithm for its optimization. The proposed model has strong mathematical underpinnings, and the corresponding algorithm achieves state-of-the-art performance on benchmark data sets.
1. Quick Summary   The authors propose a new objective function for  clustering networks that they call product cut. It is defined based on a personalized pagerank matrix (although it seems like some larger class should be possible and this choice is incidental). The key idea is that we are going to take a complicated product of properties of each partition rather than a simple sum of graph-based metrics of the partition as in  many standard methods. One of the complexities involves using the personalized PageRank matrix in order to define the objective.   This objective is shown to satisfy a simple analytical property that preserves the partitions in some  region around a sample problem with two clear clusters with a third cluster as the perturbation.   Next, in a small surprise, the problem is shown to be solvable by a relaxed convex _maximization_ problem (so this doesn't give any computational efficiency, but  does mean it enables more practical algorithms.) The relaxed problem has integer solutions at any extrema. This motivates a heuristic LP procedure to optimize the function.  There are a set of experimental results that show the standard results on a few test problems in terms of "purity". It'd be nice to see a few more evaluations (NMI or F1) that as well.  Small issues & questions  1. One issue with this paper relates to the convergence of the optimization strategy for convex maximization. The results in the paper do not justify convergence  to a local optima, nor to they justify convergence of the cluster at all; if f(x_{k+1}) >= f(x_k)) then we cannot conclude finding a local maxima (even with an upper-bound) nor does this give convergence of the x_k sequence.  Were you using additional properties in your statement of this conclusion?   2. In your simple example, wouldn't clustering of A, B, C also be appropriate? It seems like you show that if you introduce a good conductance cluster (C), you break the NCut objective for bi-partition.  But this isn't surprising as you are asking for a  bisection of a graph, not the trisection that NCut would more naturally produce.  Can you clarify what your method would do if you asked for a tripartition in this case?   Suggestions   There should be a broader class of matrices than the  personalized PageRank matrices that would support your procedure. (For instance, at least the heat-kernel would seem to work as well...)  Some parameter study about alpha would be nice.   Since this is really a paper about a new objective function it'd be nice to see more motivation for it.   Presentation notes * Given that the objective function is first defined with the most important term missing, it's hard to appreciate it's properties.  * Typo on figure 1a. 
This paper has some issues that would need to be addressed related to the use of the final optimization procedure. If this could be corrected, the  rest of the paper makes a small contribution, but in the context of a new objective function. Adding new objective functions to the literature is a lot like adding new standards. It's unclear if they will be useful; but this one seems to have a few nice properties that would merit acceptance.