Analyzing the Harmonic Structure in Graph-Based Learning
We find that various well-known graph-based models exhibit a common important harmonic structure in its target function -the value of a vertex is approximately the weighted average of the values of its adjacent neighbors. Understanding of such structure and analysis of the loss defined over such structure help reveal important properties of the target function over a graph. In this paper, we show that the variation of the target function across a cut can be upper and lower bounded by the ratio of its harmonic loss and the cut cost. We use this to develop an analytical tool and analyze five popular graph-based models: absorbing random walks, partially absorbing random walks, hitting times, pseudo-inverse of the graph Laplacian, and eigenvectors of the Laplacian matrices. Our analysis sheds new insights into several open questions related to these models, and provides theoretical justifications and guidelines for their practical use. Simulations on synthetic and real datasets confirm the potential of the proposed theory and tool.
- A desirable property (*) for algorithms on graphs is 
      to get a solution which is almost constant in each cluster, but 
      drastically change between clusters. This paper tries to establish a 
      relation between ``near harmonic'' function on graphs and their drop in 
      dense/sparse areas. The authors then study different algorithms and their 
      ``harmonic loss'', as a step to show that property (*) holds for their 
      results. - This paper contains several mini steps toward getting tools 
      to check if the property (*) holds for a machine algorithm. However the 
      results are not still strong enough, and can not be considered as a proof. 
      - The paper is easy to read and follow, but there are some space for 
      improvements. Some of the results can significantly simplified (See 
      detailed comments). Supplementary material is supposed to contain proofs 
      and specific details, and not complete new sections (Section 4.2 and 4.3) 
      - Originality and significance: The paper introduce new tools to 
      intuitively justify the property (*) for graph algorithms. The machinery 
      looks attractive for me, but i do not see them as a tool for finding 
      rigorous proofs. Main comments: - The so called left/right/- 
      continuity of functions on graphs as it is defined, have nothing to do 
      with mathematical concept of continuity. It does not guaranty any bound on 
      function's jump. If you remove all results about continuity, would the 
      message of the paper is change? My suggestion is to choose another 
      keyword, which does not imply properties stronger than the actual meaning 
      to the reader. - lines 192-199: All the statements are imprecise and 
      hand wavy. One can build functions f which is almost harmonic everywhere, 
      but does not drop at all on a cut with a very small w(). Consider this 
      graph and function values defined on vertices, where 000 shows a big 
      complete graph with f zero on it (or super tiny random values if you 
      like): 1--0.8--0.6--0.4--0.2--0--000--0--0--000 f is almost 
      harmonic everywhere(except two vertices), however it does not drop at all 
      on the edges between two 000 clusters, where conductance is relatively 
      small. For other statements in this paragraph, also one can build 
      counterexamples. - In Corollary 3.1, we can explicitly characterize 
      L_f(S_i), which is the inverse of the resistance distance between vertex 1 
      and n - line 247: it is claimed that f continuously changes on graphs. 
      However the definition 2.5 of continuous f is much weaker than 
      "continuously changing on graphs" - lines 264-310: We have f_1(i) + 
      f_2(i) = 1. So we do not need to consider f_1 and f_2 as one of them 
      already contain all the information. Also Lemma 3.3 boils down to deciding 
      the class by comparing f'_1(i) with 1/n. - I suggest the Authors to 
      give a recipe for analyzing semi-supervised algorithms. This would 
      increase the readability of their paper. A recipe is something like: 
      1- try to write the solution function f as a sum of a harmonic term 
      and non-harmonic term. In my own words, find the net incoming flow into 
      each node. It is clear that we may not be able to write the solution for 
      all methods in this form. 2- Use theorems 2.7 and 2.8 to check if they 
      provide good bounds on the drop - There are many qualitative 
      statements, which Authors should avoid having them. This makes their work 
      look very hand-wavy and imprecise. tiny comments: - In 
      definition 2.5, it is good to mention that S_i depends on f. - line 
      170: r.h of inequality, k \in \bar{S_i} Pro: - Bound on the 
      change of function f depending on Harmonic Loss and conductance - 
      Presenting the solution of different graph algorithms in the harmonic form 
      Co: - Upper/lower bounds on the change of function f only 
      indicate the property (*) and does not give a rigorous proof - The 
      normalizing step can presented much simpler. In fact i do not count it as 
      a contribution of the paper. - The supplementary material is misused 
      by Authors.