A Linearly Constrained Power Iteration for Spectral Semi-Supervised Classification on Signed Graphs

Abstract

In this work we consider the problem of semi-supervised node classification and extend the method of Xu et al. [1] to a multiclass setting. [1] proposed a linearly constrained variant of the power iteration for classification with two classes where the semi-supervised knowledge was incorporated in the linear constraints. For the multiclass setting we extend this work to a linearly constrained orthogonal iteration. In order to optimize all clusters at the same time, we deviate from the orthogonal iteration by replacing the QR-decomposition for orthonormalization by a projection operation. Our method is parameter-free in the sense that it only relies on a positive definite matrix representation of the graph which admits both conventional graphs and signed graphs. In our experiments we show that the joint optimization using a projection operation outperforms the sequential optimization with orthogonality constraints.