## 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 language | English (US) |
---|---|

Title of host publication | Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015 |

Editors | Vitor 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 |

Publisher | Springer |

Pages | 752-767 |

Number of pages | 16 |

ISBN (Print) | 9783319235240, 9783319235240, 9783319235240, 9783319235240 |

DOIs | |

State | Published - 2015 |

Event | European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015 - Porto, Portugal Duration: Sep 7 2015 → Sep 11 2015 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9285 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015 |
---|---|

Country/Territory | Portugal |

City | Porto |

Period | 9/7/15 → 9/11/15 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)