Correlated Label Propagation with Application to Multi-label Learning

by Feng Kang, Rong Jin and Rahul Sukthankar

This paper talks about multi-label propagation. Usually label propagation is commonly seen in semi-supervised learning tasks. As for multi-labeled tasks, the critical difference is that labels may have correlationships (co-occurrences).

The paper proposes a linear programming model for the task

\max_{z \in \mathbb{R}^n} \sum_{k = 1}^n \alpha_k z_k \qquad \text{s.t. } \forall t \in \{ 0, 1\}^n, z^\top t \leq \sum_{i = 1}^N K(x_i, x_q) \Omega(t^\top t(S_i)), z \succeq 0

where \Omega is a concave function. The interpretation of this objective function is: for any possible labelling of the test sample, the propagated score is bounded from above by weighted (by the similarity, depicted by K(\cdot, \cdot)) sum of score from those samples sharing labels.
The amazing thing about the objective function is that a greedy algorithm can find the optimal when \Omega is concave and the solution is only determined by the order of the undetermined coefficients \alpha_k. This optimization is related to the so-called sub-modular optimization (see here).