The Total Variation on Hypergraphs -Learning on Hypergraphs Revisited
Hypergraphs allow one to encode higher-order relationships in data and are thus a very flexible modeling tool. Current learning methods are either based on approximations of the hypergraphs via graphs or on tensor methods which are only applicable under special conditions. In this paper, we present a new learning framework on hypergraphs which fully uses the hypergraph structure. The key element is a family of regularization functionals based on the total variation on hypergraphs.
The paper defines a notion of total variation on 
      hypergraphs, proves its convexity and relation to cuts, discusses 
      applications to learning and normalized cuts (for clustering), computes 
      proximity operators as part of optimization algorithms, and presents 
      numerical experiments comparing with a popular method of Zhou from 2006. 
      Overall, the paper tours several sub-disciplines. There are a lot of ideas 
      and a few theorems (though of course they cannot say much about a global 
      solution in the case of the normalized cut problem, but no one can). The 
      paper stays focused despite the amount of material and it is well written, 
      with only occasional grammar issues. Section 5 falls most into my 
      area of expertise, and I am satisfied with it. I am less familiar with 
      existing work on spectral clustering and existing approaches for 
      hypergraphs. This paper is basically claiming to be the first major 
      advance in 7 years (since Zhou [11]), and I am inclined to believe this, 
      but not completely certain. If it is true, then this paper should 
      definitely be accepted and will likely become well-known. But of course I 
      am a bit skeptical that the authors have not found any more recent work 
      than [11], given the amount of attention to the subject (or is it because 
      everyone is working on tensors and ignoring hypergraphs?) Other 
      comments: - Comparisons were always with [11], which uses the same 
      hypergraph framework, and then reduces it with the CE technique to a graph 
      problem. But these problems (SSL, clustering) can be attacked from quite 
      different perspectives. A comparison with an "outside" approach would make 
      this paper stronger, even a simple algorithm (such as k-means for 
      clustering... or explain why it is not applicable). Your clustering 
      approach which recursively splits clusters is clearly not optimal (though 
      I do not doubt that it is a standard technique). - Line 121: "the 
      optimal cut". Shouldn't this be "an optimal cut", since it is symmetric so 
      and the mirror-image cut would work as well? - The section around 
      Thm 4.1 seemed vague to me and could have benefited from more explanation. 
      For example, it's not clear to me how to apply the second equation from 
      the theorem. - I'm not sure what the authors mean by "tight 
      relaxation" (section 4, and mentioned in the intro). Is it the "the 
      tightest"? (in that case, define what is your class of "relaxations", 
      since it's not the class of convex functions in this case). Or do you mean 
      "tighter" than the linear eigenproblem relaxation? (in this case, how do 
      you justify this? For graphs, it is justified by empirical evidence, so 
      for hypergraphs, you should derive the linear relaxation and test it). 
      - Section 5. The method in [24] has since been extended a lot; 
      see, for example, Condat 2011 
      (http://www.optimization-online.org/DB_HTML/2011/12/3284.html). In 
      particular (and I think this was already in [24]), it can exploit smooth 
      functions. Usually, it is better (in terms of convergence rates) to take 
      derivatives of smooth functions when possible, as opposed to calculating 
      their proximity operators; so for the first G term in Table 1, why not 
      treat it as the smooth term? For line 276, "the main idea" (also, note 
      that this phrase is repeated three times on this page) is not really 
      described that well, since this is not unique to the method of [24]. 
      Rather [24] allows one to separate many terms. - I am quite 
      familiar with TV on a grid (for 2D). In this case, people prefer using the 
      isotropic TV, but this does not have a closed-form proximity operator nor 
      an efficient algorithm to compute it. Alternatively, the most common form 
      of anisotropic TV is much simpler to work with. It appears that your TV 
      definition generalizes this anisotropic TV. It's not clear, but it would 
      be very interesting to explore, if it is possible to define an isotropic 
      TV on a hypergraph. - Prop 5.1. This is O( n log n) due to the 
      sort. Is it not possible to avoid the sort and just find the largest and 
      smallest entries of the input? This would bring it down to O(n). I realize 
      you may have to worry about cases when the answer will have several values 
      at the max/min, but it still may be possible to deal with this. - 
      Experiments. Overall, well done. For making the hypergraph edges using 
      data points that have the same value of a feature, is it not beneficial to 
      make edges (but with much lower weight) when data points have *similar* 
      values? - The table on page 8: what are the entries? Some kind of 
      error? This was not explained - Line 415: "Our method... minimizes 
      the normalized cut on the hypergraph." Unless I have misunderstood, this 
      is not true. You apply a convex method to a nonconvex problem, so in the 
      best case (and this you would need to show) you reach a stationary point 
      or local minima. So at least say that your method "attempts" to 
      minimize... Grammar: - Line 276 and 301, "proximum" and 
      "proxima" are not commonly used; just use "proximity operator". - 
      Line 416-7 is awkward. - The authors use the construction "allow 
      to" a lot, as well as variants "suggest/recommend to use", "favor to split 
      off", "propose to solve", (e.g., line 17, 69, 107, 192, 201, 385). Since 
      the English is otherwise nearly perfect, it's worth correcting this. In 
      these cases, the infinite should be a gerund, e.g. "suggest to use" should 
      be "suggest using". Rarely, both forms are correct (e.g. "I like to play 
      tennis" and "I like playing tennis" are both fine). In the case of 
      "Hypergraphs allow to encode", it should be "Hypergraphs allow one to 
      encode". - "However" is not used correctly a few times. E.g. line 
      199, it should be "Hence" not "However", and line 408 it should be 
      "Thus".