Improved Graph Laplacian via Geometric Consistency
In all manifold learning algorithms and tasks setting the kernel bandwidth used construct the graph Laplacian is critical. We address this problem by choosing a quality criterion for the Laplacian, that measures its ability to preserve the geometry of the data. For this, we exploit the connection between manifold geometry, represented by the Riemannian metric, and the Laplace-Beltrami operator. Experiments show that this principled approach is effective and robust.
This paper proposes a method for improving the graph Laplacian by choosing the bandwidth parameter in the heat kernel for the neighborhood graph.  The method uses geometric consistency in the sense that the Riemannian metric estimated with the graph Laplacian should be close to another estimate of the Riemannian metric based on the estimation of the tangent space.  Some experiments with synthetic and real data demonstrate promising results of the proposed method. 
The proposed method for choosing bandwidth seems novel and interesting.  It is based on the very natural geometric idea for capturing the Riemannian geometry of the manifold.  There are, however, some concerns also as described below. 
- From the experimental results in Table 1, it is not very clear whether the proposed method outperforms the other methods.  In comparison with Rec, the advantage of GC are often minor, and GC^{-1} sometimes gives worse results.  More careful comparison including statistical significance is necessary.  
- The authors say that d=1 is a good choice in the method.  The arguments to support this claim is not convincing, however.  It is not clear whether Proposition 3.1 tells that d=1 is sufficient.  More detailed explanations and discussions would be preferable. 
- The paper is easy to read, but not necessarily well written.  There are many typos in the paper.  To list a few, 
-- l.36: methods are duplicated. 
-- eq.(2): it should be minus in the exponential. 
-- l. 179: on is duplicated. 
-- Caption of Figure 1: have are.