Revisiting Multi-Label Propagation: the Case of Small Data

This paper focuses on multi-label learning from small number of labelled data. We demonstrate that the straightforward binary-relevance extension of the interpolated label propagation algorithm, the harmonic function, is a competitive learning method with respect to many widely-used evaluation measures. This is achieved mainly by a new transition matrix that better captures the underlying manifold structure. Furthermore, we show that when there exists label dependence, we can use the outputs of a competitive learning method as part of the input to the harmonic function to provide improved results over those of the original model. Finally, since we are using multiple metrics to thoroughly evaluate the performance of the algorithm, we propose to use the game-theory based method of Kalai and Smorodinsky to output a single compromise solution. This method can be applied to any learning model irrespective of the number of evaluation measures used.