Robust classification of information networks by consistent graph learning

Shi Zhi, Jiawei Han, Quanquan Gu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Graph regularization-based methods have achieved great success for network classification by making the label-link consistency assumption, i.e., if two nodes are linked together, they are likely to belong to the same class. However, in a real-world network, there exist links that connect nodes of different classes. These inconsistent links raise a big challenge for graph regularization and deteriorate the classification performance significantly. To address this problem, we propose a novel algorithm, namely Consistent Graph Learning, which is robust to the inconsistent links of a network. In particular, given a network and a small number of labeled nodes, we aim at learning a consistent network with more consistent and fewer inconsistent links than the original network. Since the link information of a network is naturally represented by a set of relation matrices, the learning of a consistent network is reduced to learning consistent relation matrices under some constraints. More specifically, we achieve it by joint graph regularization on the nuclear norm minimization of consistent relation matrices together with ℓ1-norm minimization on the difference matrices between the original relation matrices and the learned consistent ones subject to certain constraints. Experiments on both homogeneous and heterogeneous network datasets show that the proposed method outperforms the state-of-the-art methods.

Original languageEnglish (US)
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015
EditorsVitor Santos Costa, Carlos Soares, Annalisa Appice, Annalisa Appice, Pedro Pereira Rodrigues, Vitor Santos Costa, Carlos Soares, João Gama, Alípio Jorge, Pedro Pereira Rodrigues, João Gama, Vitor Santos Costa, Alípio Jorge, Annalisa Appice, Pedro Pereira Rodrigues, João Gama, Annalisa Appice, Carlos Soares, Alípio Jorge, João Gama, Pedro Pereira Rodrigues, Vitor Santos Costa, Carlos Soares, Alípio Jorge
PublisherSpringer-Verlag Berlin Heidelberg
Pages752-767
Number of pages16
ISBN (Print)9783319235240, 9783319235240, 9783319235240, 9783319235240
DOIs
StatePublished - 2015
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015 - Porto, Portugal
Duration: Sep 7 2015Sep 11 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9285
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015
CountryPortugal
CityPorto
Period9/7/159/11/15

Keywords

  • Consistent graph learning
  • Consistent link
  • Consistent network
  • Information network
  • Robust classification

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Robust classification of information networks by consistent graph learning'. Together they form a unique fingerprint.

Cite this