Department of ECE, Northeastern University
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 project, we develop a novel approach to constructing graph, which is based on low-rank coding and b-matching constraint. By virtue of recent advances in low-rank subspace recovery theory, compact encoding using low-rank representation coefficients allows us to obtain a robust similarity metric between all pairs of samples. Meanwhile, the b-matching constraint helps in obtaining a sparse and balanced graph, which benefits label propagation in GSSL. We build a joint optimization model to learn low-rank codes and balanced graph simultaneously. After using a graph re-weighting strategy, we present a semi-supervised learning algorithm by incorporating our sparse and balanced graph with Gaussian harmonic function (GHF). Experimental results on the Extended YaleB, PIE, ORL and USPS databases demonstrate that our graph outperforms several state-of-the-art graphs, especially when the labeled samples are very scarce.
Figure 1. Our Framework.
Figure 2. Similarity metric in the original space and the low-rank code space.
Code will be available soon.
1. Sheng Li and Yun Fu. Low-Rank Coding with b-Matching Constraint for Semi-supervised Classification, International Joint Conference on Artificial Intelligence (IJCAI), pp. 1472-1478, 2013. [PDF]