Learning on graphs using Orthonormal Representation is Statistically Consistent
Existing research [4] suggests that embedding graphs on a unit sphere can be beneficial in learning labels on the vertices of a graph. However the choice of optimal embedding remains an open issue. Orthonormal representation of graphs, a class of embeddings over the unit sphere, was introduced by Lovász [2]. In this paper, we show that there exists orthonormal representations which are statistically consistent over a large class of graphs, including power law and random graphs. This result is achieved by extending the notion of consistency designed in the inductive setting to graph transduction. As part of the analysis, we explicitly derive relationships between the Rademacher complexity measure and structural properties of graphs, such as the chromatic number. We further show the fraction of vertices of a graph G, on n nodes, that need to be labelled for the learning algorithm to be consistent, also known as labelled sample complexity, is Ω where ϑ(G) is the famous Lovász ϑ function of the graph. This, for the first time, relates labelled sample complexity to graph connectivity properties, such as the density of graphs. In the multiview setting, whenever individual views are expressed by a graph, it is a well known heuristic that a convex combination of Laplacians [7] tend to improve accuracy. The analysis presented here easily extends to Multiple graph transduction, and helps develop a sound statistical understanding of the heuristic, previously unavailable.
The paper presents statistical analyses of graph transduction algorithms, based on orthonormal embedding of graphs introduced by [17]. The main results provided in the paper are: 1) providing a deterministic upper bound on transductive Rademecher complexity in terms of a graph-structural measure (Chromatic number/Lovasz-theta function) for a class of graphs.2) using that relation to establish graph-dependent generalization bounds for transduction algorithms -  the high level proof technique for this part follows [10], but several modification for the current setting are done. 3) establishing consistency of a particular LS labeling algorithm, using the above results for several families of graphs. A multiple graph extension is also provided, although it is straight-forward given the previous results. The results provided are interesting - particularly the deterministic connection between Rademacher complexity and the structural properties of the graph. The subsequent results are naturally based on this connection. I wonder if there could be tighter upper bounds based on concentration results for \lambda_1(K), that hold with high probability which involves some interpretable parameter of the graph ? The paper is not well-written which makes following the proofs and interpreting the results time-consuming. Presentation could be improved significantly. I would suggest to move some proofs (or all) in the main paper to the supplementary section and improve the presentation in the main paper (by interpreting  the results). Furthermore, there are several places where the style could be made formal (e.g., 163-164; 212-217). Also in algorithm 1, should it be \hat y = U^T h* ? There are several typographical errors that need to be corrected (e.g., supplementary pdf - line 216 - dictribution -> distribution). Also minor changes like providing the original definition of v(G) and then presenting the alternate identity from [14] (lines 124-125) needs to  be done.