Weighted Theta Functions and Embeddings with Applications to Max-Cut, Clustering and Summarization
We introduce a unifying generalization of the Lovász theta function, and the associated geometric embedding, for graphs with weights on both nodes and edges. We show how it can be computed exactly by semidefinite programming, and how to approximate it using SVM computations. We show how the theta function can be interpreted as a measure of diversity in graphs and use this idea, and the graph embedding in algorithms for Max-Cut, correlation clustering and document summarization, all of which are well represented as problems on weighted graphs.
The paper starts by situating the problem and motivating their approach - essentially, enabling embeddings for weighted graphs by extending the original implicit embedding performed in Lovasz "Shannon capacity of a graph" paper, which operated on binary graphs. The paper then presents the connection between kernel machines and the Lovasz number in the unweighted case, and extends previous work for vertex-weighted, edge-weighted, and LS-labelled graphs. Section 3 provides practical details for computation, and section 4 motivates the use of their approach for the clustering problem - setting the number of clusters by using their \vartheta^1 bound, and initialising the clusters by starting by vertices with large alpha_i values. Finally, they show results on max-cut, clustering, overlapping clustering, and summarization tasks. The paper ties together very different work to propose a coherent approach to graph embedding. The contributions are clearly laid out, and the references to previous work is well established and used.       Overall, the paper is well-written and the notation is clean.and the derivation of their technique is clearly explained.  This is significant work that can have impact in several domains of machine learning, as shown in the experiments section.  There are a few issues that deserve slightly better explanations:  a) To recover the embedding from the computed kernel matrix, the authors propose to use a truncated SVD. This is fine, but the efficiency of the embedding really hinges on the choice of the truncation order. How much better than a full-rank orthonormal representation (basically order n) can we do and still have good performance? Surely, this depends on the structure of the input adjacency or affinity matrix - something that could be generated from a stochastic block model, for example, would presumably call for a different choice of truncation order than a lattice graph? The authors choose \sqrt(n) for the truncation order, but it would be useful to have some intuition as to the impact on the quality of the embedding generated (the paper focuses a lot on how to obtain K and alpha).  b) In section 4, the authors suggest using vertices with the largest alphas as initial centroids. In the SVM analogy, these would be support vectors (i.e. non-zero alphas), which would put them on the decision boundary. However, in the SVM setting these points are typically outliers or extreme values and don't represent the bulk of the data. I understand that the authors want 'diversity' here, but the explanation in lines 263-265 seems to be at odds with the stated goal of finding good centroids in section 4.1 - do we want representative points (center of mass) or influential points (extremes, on the boundary in the discriminative setting) ?             c) In the experiments on maxcut (table 2), the authors have selected 6 graphs from the Helmberg and Rendl set of 24 weighted graphs. These are toroidal graphs, which have a known upper bound on the cut size. Because the comparison to the best known algorithm (Scatter search or VNSPR) if empirical anyways, is there a particular reason to select these? How would the method perform on random graphs (e.g. G6...G10) or planar graphs (e.g. G18...G21) ?