Multi-label collective classification via Markov chain based learning method

Qingyao Wu, Kwok Po NG, Yunming Ye, Xutao Li, Ruichao Shi, Yan Li*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

14 Citations (Scopus)


In this paper, we study the problem of multi-label collective classification (MLCC) where instances are related and associated with multiple class labels. Such correlation of class labels among interrelated instances exists in a wide variety of data, e.g., a web page can belong to multiple categories since its semantics can be recognized in different ways, and the linked web pages are more likely to have the same classes than the unlinked pages. We propose an effective and novel Markov chain based learning method for MLCC problems. Our idea is to model the problem as a Markov chain with restart on transition probability graphs, and to propagate the ranking score of labeled instances to unlabeled instances based on the affinity among instances. The affinity among instances is set up by explicitly using the attribute features derived from the content of instances as well as the correlation features constructed from the links of instances. Intuitively, an instance which contains linked neighbors that are highly similar to the other instances with a high rank of a particular class label, has a high chance of this class label. Extensive experiments have been conducted on two DBLP datasets to demonstrate the effectiveness of the proposed algorithm. The performance of the proposed algorithm is shown to be better than those of the binary relevance multi-label algorithm, collective classification algorithms (wvRN, ICA and Gibbs), and the ICML algorithm for the tested MLCC problems.

Original languageEnglish
Pages (from-to)1-14
Number of pages14
JournalKnowledge-Based Systems
Publication statusPublished - Jun 2014

Scopus Subject Areas

  • Management Information Systems
  • Software
  • Information Systems and Management
  • Artificial Intelligence

User-Defined Keywords

  • Collective classification
  • Machine learning
  • Markov chain with restart
  • Multi-label collective classification
  • Multi-label learning


Dive into the research topics of 'Multi-label collective classification via Markov chain based learning method'. Together they form a unique fingerprint.

Cite this