Subspace clustering meets dense subgraph mining: A synthesis of two paradigms

Stephan Günnemann, Ines Färber, Brigitte Boden, Thomas Seidl

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

101 Scopus citations

Abstract

Today's applications deal with multiple types of information: graph data to represent the relations between objects and attribute data to characterize single objects. Analyzing both data sources simultaneously can increase the quality of mining methods. Recently, combined clustering approaches were introduced, which detect densely connected node sets within one large graph that also show high similarity according to all of their attribute values. However, for attribute data it is known that this full-space clustering often leads to poor clustering results. Thus, subspace clustering was introduced to identify locally relevant subsets of attributes for each cluster. In this work, we propose a method for finding homogeneous groups by joining the paradigms of subspace clustering and dense subgraph mining, i.e. we determine sets of nodes that show high similarity in subsets of their dimensions and that are as well densely connected within the given graph. Our twofold clusters are optimized according to their density, size, and number of relevant dimensions. Our developed redundancy model confines the clustering to a manageable size of only the most interesting clusters. We introduce the algorithm GAMER for the efficient calculation of our clustering. In thorough experiments on synthetic and real world data we show that GAMER achieves low runtimes and high clustering qualities.

Original languageEnglish
Title of host publicationProceedings - 10th IEEE International Conference on Data Mining, ICDM 2010
Pages845-850
Number of pages6
DOIs
StatePublished - 2010
Externally publishedYes
Event10th IEEE International Conference on Data Mining, ICDM 2010 - Sydney, NSW, Australia
Duration: 14 Dec 201017 Dec 2010

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Conference

Conference10th IEEE International Conference on Data Mining, ICDM 2010
Country/TerritoryAustralia
CitySydney, NSW
Period14/12/1017/12/10

Fingerprint

Dive into the research topics of 'Subspace clustering meets dense subgraph mining: A synthesis of two paradigms'. Together they form a unique fingerprint.

Cite this