Learning Balanced and Unbalanced Graphs via Low-Rank Coding.

Graphs have been widely applied in modeling the relationships and structures in real-world applications. Graph construction is the most critical part in these models, while how to construct an effective graph is still an open problem. In this paper, we propose a novel approach to graph construction based on two observations. First, by virtue of recent advances in low-rank subspace recovery, the similarity between every two samples evaluated in the low-rank code space is more robust than that in the sample space. Second, a sparse and balanced graph can greatly increase the performance of learning tasks, such as label propagation in graph based semi-supervised learning. The $k$<alternatives><inline-graphic xlink:type="simple" xlink:href="li-ieq1-2365793.gif"/></alternatives> -NN sparsification can provide fast solutions to constructing unbalanced sparse graphs, and $b$<alternatives> <inline-graphic xlink:type="simple" xlink:href="li-ieq2-2365793.gif"/></alternatives>-matching constraint is a necessary route for generating balanced graphs. These observations motivate us to jointly learn the low-rank codes and balanced (or unbalanced) graph simultaneously. In particular, two non-convex models are built by incorporating $k$<alternatives><inline-graphic xlink:type="simple" xlink:href="li-ieq3-2365793.gif"/></alternatives> -NN constraint and $b$<alternatives> <inline-graphic xlink:type="simple" xlink:href="li-ieq4-2365793.gif"/></alternatives>-matching constraint into the low-rank representation model, respectively. We design a majorization-minimization augmented Lagrange multiplier (MM-ALM) algorithm to solve the proposed models. Extensive experimental results on four image databases demonstrate the superiority of our graphs over several state-of-the-art graphs in data clustering, transductive and inductive semi-supervised learning. [ABSTRACT FROM PUBLISHER]