Semi-supervised clustering of graph objects: A subgraph mining approach

Xin Huang*, Hong Cheng, Jiong Yang, Jeffery Xu Yu, Hongliang Fei, Jun Huan

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

4 Citations (Scopus)


Semi-supervised clustering has recently received a lot of attention in the literature, which aims to improve the clustering performance with limited supervision. Most existing semi-supervised clustering studies assume that the data is represented in a vector space, e.g., text and relational data. When the data objects have complex structures, e.g., proteins and chemical compounds, those semi-supervised clustering methods are not directly applicable to clustering such graph objects. In this paper, we study the problem of semi-supervised clustering of data objects which are represented as graphs. The supervision information is in the form of pairwise constraints of must-links and cannot-links. As there is no predefined feature set for the graph objects, we propose to use discriminative subgraph patterns as the features. We design an objective function which incorporates the constraints to guide the subgraph feature mining and selection process. We derive an upper bound of the objective function based on which, a branch-and-bound algorithm is proposed to speedup subgraph mining. We also introduce a redundancy measure into the feature selection process in order to reduce the redundancy in the feature set. When the graph objects are represented in the vector space of the discriminative subgraph features, we use semi-supervised kernel K-means to cluster all graph objects. Experimental results on real-world protein datasets demonstrate that the constraint information can effectively guide the feature selection and clustering process and achieve satisfactory clustering performance.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications
Subtitle of host publication17th International Conference, DASFAA 2012, Busan, South Korea, April 15-18, 2012, Proceedings, Part I
EditorsSang-goo Lee, Zhiyong Peng, Xiaofang Zhou, Yang-Sae Moon, Rainer Unland, Jaesoo Yoo
Number of pages16
ISBN (Electronic)9783642290381
Publication statusPublished - Apr 2012
Event17th International Conference on Database Systems for Advanced Applications, DASFAA 2012 - Busan, Korea, Republic of
Duration: 15 Apr 201218 Apr 2012

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameInformation Systems and Applications, incl. Internet/Web, and HCI (LNISA)
NameDASFAA: International Conference on Database Systems for Advanced Applications


Conference17th International Conference on Database Systems for Advanced Applications, DASFAA 2012
Country/TerritoryKorea, Republic of
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • frequent subgraph mining
  • Semi-supervised clustering


Dive into the research topics of 'Semi-supervised clustering of graph objects: A subgraph mining approach'. Together they form a unique fingerprint.

Cite this