Timezone: »
Poster
Learning on graphs using Orthonormal Representation is Statistically Consistent
Rakesh Shivanna · Chiranjib Bhattacharyya
Existing research \cite{reg} 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. \emph{Orthonormal representation} of graphs, a class of embeddings over the unit sphere, was introduced by Lov\'asz \cite{lovasz_shannon}. 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 $ \Omega\left(\frac{\vartheta(G)}{n}\right)^{\frac{1}{4}}$ where $\vartheta(G)$ is the famous Lov\'asz~$\vartheta$ 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 \cite{lap_mv1} 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.
Author Information
Rakesh Shivanna (Google Inc.)
Chiranjib Bhattacharyya (Indian Institute of Science)
More from the Same Authors

2015 Poster: Weighted Theta Functions and Embeddings with Applications to MaxCut, Clustering and Summarization »
Fredrik D Johansson · Ankani Chattoraj · Chiranjib Bhattacharyya · Devdatt Dubhashi 
2015 Poster: Spectral Norm Regularization of Orthonormal Representations for Graph Transduction »
Rakesh Shivanna · Bibaswan K Chatterjee · Raman Sankaran · Chiranjib Bhattacharyya · Francis Bach 
2014 Poster: A provable SVDbased algorithm for learning topics in dominant admixture corpus »
Trapit Bansal · Chiranjib Bhattacharyya · Ravindran Kannan 
2012 Poster: The Lovasz $\theta$ function, SVMs and finding large dense subgraphs »
Vinay Jethava · Anders Martinsson · Chiranjib Bhattacharyya · Devdatt Dubhashi 
2010 Poster: Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions »
Achintya Kundu · Vikram Mukunda Rao Tankasali · Chiranjib Bhattacharyya · Aharon BenTal 
2009 Poster: On the Algorithmics and Applications of a Mixednorm based Kernel Learning Formulation »
Saketha Nath Jagarlapudi · dinesh govindaraj · Raman S · Chiranjib Bhattacharyya · Aharon BenTal · K. R. Ramakrishnan 
2007 Poster: Kernels on Attributed Pointsets with Applications »
Mehul Parsana · Sourangshu Bhattacharya · Chiranjib Bhattacharyya · K. R. Ramakrishnan 
2007 Poster: A Randomized Algorithm for Large Scale Support Vector Learning »
Krishnan S Kumar · Chiranjib Bhattacharyya · Ramesh Hariharan