Manifold-based Similarity Adaptation for Label Propagation
Label propagation is one of the state-of-the-art methods for semi-supervised learning, which estimates labels by propagating label information through a graph. Label propagation assumes that data points (nodes) connected in a graph should have similar labels. Consequently, the label estimation heavily depends on edge weights in a graph which represent similarity of each node pair. We propose a method for a graph to capture the manifold structure of input features using edge weights parameterized by a similarity function. In this approach, edge weights represent both similarity and local reconstruction weight simultaneously, both being reasonable for label propagation. For further justification, we provide analytical considerations including an interpretation as a cross-validation of a propagation model in the feature space, and an error analysis based on a low dimensional manifold model. Experimental results demonstrated the effectiveness of our approach both in synthetic and real datasets.
The manuscript a new method “adaptive edge weighting” 
      (AEW) that weights to the edges of a neighborhood graph for use with label 
      propagation. The neighborhood graph is constructed using k-NN in the 
      feature space, and then the edge weights are optimized based on their 
      ability to reconstruct the feature vector associated with each node. The 
      objective function is the same as LLE but the weights are derived from 
      Gaussian kernels and the only parameters are the bandwidths of the kernels 
      in each dimension, thereby forcing the weights to be positive and greatly 
      reducing the number of free parameters. They call this procedure “feature 
      propagation”. The manuscript contains a theorem that connects the 
      reconstruction error in feature propagation (and the maximum neighbor 
      distance) with the expected performance in the label propagation task. 
      When tested on simulated data or eight classification / multiclass 
      benchmarks and paired with one flavor of label propagation (Harmonic 
      Gaussian Fields), AEW performs better than a version that does not 
      optimize bandwidths or a previous, similar method (LNP) that uses the 
      unrestricted LLE objective function to set the edge weights. The 
      manuscript also points out that the method is less sensitive to increases 
      in k when constructing the neighborhood graph because of the Gaussian 
      kernel derived edge weights. Clarity: The manuscript is 
      well-organized and easy to follow. The experimental section is clear 
      although one very minor issue is that I am not sure that I could perfectly 
      reproduce their results, as the exact optimization procedure they use for 
      the bandwidths is not described (steepest descent? CG?) and the synthetic 
      data set is not provided. Quality: This is a well-constructed, 
      good quality paper – it provides a new methodology, some insight into why 
      this method is appropriate through the aforementioned theorem, as well as 
      sufficient experimental evaluation. I have some questions about the 
      validation. LNP appears to use a different neighborhood graph than AEW, 
      how much of the performance improvement of AEW is due to the different 
      graphs? Also, AEW doesn’t generate a normalized Laplacian (does LNP?), but 
      normalized version of the AEW Laplacian was used in the validations, 
      presumably to improve performance. This issue is only discussed briefly; I 
      think some more discussion is warranted. Originality: The 
      contribution seems original although is a slight, but crafty, modification 
      of a previous technique (LNP) for setting the edge weights. 
      Significance: The LNP paper has >200 Google scholar citations 
      and the described method performs better, is relatively easy to implement, 
      and has no tuning parameters. Given a relevant learning problem, this 
      would be the first method that I would try. So, it does have some 
      significance. On the other hand, this does seem like an incremental 
      improvement on well-studied problem although the theorem does provide a 
      basis on which to develop other “feature propagation” based weighting 
      schemes. One other issue that could be addressed in the introduction to 
      increase the significance of the work, is why one would want to convert 
      feature vectors into a graph rather than working directly in the feature 
      space. Minor issues: Line 119: Are the limits of the argmax 
      correct here? “argmaxj≤j Fij “