Classification of large graphs by a local tree decomposition

Frank Emmert-Streib, Matthias Dehmert, Jürgen Kilian

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

25 Citations (Scopus)


We present a binary graph classifier (BGC) which allows to classify large, unweighted, undirected graphs. This classifier is based on a local decomposition of the graph for each node in generalized trees. The obtained trees, forming the tree set of the graph, are then pairwise compared by a generalized tree-similarity-algorithm (GTSA) and the resulting similarity scores determine a characteristic similarity distribution of the graph. Classification in this context is defined as mutual consistency for all pure and mixed tree sets and their resulting similarity distributions in a graph class. We demonstrate the application of this method to an artificially generated data set and for data from microarray experiments of cervical cancer.

Original languageEnglish
Title of host publicationProceedings of the 2005 International Conference on Data Mining, DMIN'05
Number of pages8
Publication statusPublished - 2005
Externally publishedYes
Publication typeA4 Article in conference proceedings
Event2005 International Conference on Data Mining, DMIN'05 - Las Vegas, NV, United States
Duration: 20 Jun 200523 Jun 2005


Conference2005 International Conference on Data Mining, DMIN'05
Country/TerritoryUnited States
CityLas Vegas, NV

ASJC Scopus subject areas

  • Computer Science Applications
  • Software


Dive into the research topics of 'Classification of large graphs by a local tree decomposition'. Together they form a unique fingerprint.

Cite this