Spectral Norm Regularization of Orthonormal Representations for Graph Transduction

Recent literature [1] suggests that embedding a graph on an unit sphere leads to better generalization for graph transduction. However, the choice of optimal embedding and an efficient algorithm to compute the same remains open. In this paper, we show that orthonormal representations, a class of unit-sphere graph em-beddings are P AC learnable. Existing P AC-based analysis do not apply as the VC dimension of the function class is infinite. We propose an alternative P AC-based bound, which do not depend on the VC dimension of the underlying function class, but is related to the famous Lov asz ϑ function. The main contribution of the paper is SPORE, a SPectral regularized ORthonormal Embedding for graph transduction, derived from the P AC bound. SPORE is posed as a non-smooth convex function over an elliptope.