Classification of large graphs by a local tree decomposition

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

Classification of large graphs by a local tree decomposition

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

^*Corresponding author for this work

Stowers Institute for Medical Research
Technische Universität Darmstadt

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

26 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Proceedings of the 2005 International Conference on Data Mining, DMIN'05
Pages	200-207
Number of pages	8
Publication status	Published - 2005
Externally published	Yes
Event	2005 International Conference on Data Mining, DMIN'05 - Las Vegas, NV, United States Duration: 20 Jun 2005 → 23 Jun 2005

Publication series

Name	Proceedings of the 2005 International Conference on Data Mining, DMIN'05

Conference

Conference	2005 International Conference on Data Mining, DMIN'05
Country/Territory	United States
City	Las Vegas, NV
Period	20/06/05 → 23/06/05

Cite this

@inproceedings{c12d28247a5f4ae7954dcbc3a4bdc4e7,

title = "Classification of large graphs by a local tree decomposition",

abstract = "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.",

author = "Frank Emmert-Streib and Matthias Dehmert and J{\"u}rgen Kilian",

year = "2005",

language = "English",

isbn = "9781932415797",

series = "Proceedings of the 2005 International Conference on Data Mining, DMIN'05",

pages = "200--207",

booktitle = "Proceedings of the 2005 International Conference on Data Mining, DMIN'05",

note = "2005 International Conference on Data Mining, DMIN'05 ; Conference date: 20-06-2005 Through 23-06-2005",

}

Classification of large graphs by a local tree decomposition. / Emmert-Streib, Frank; Dehmert, Matthias; Kilian, Jürgen.
Proceedings of the 2005 International Conference on Data Mining, DMIN'05. 2005. p. 200-207 (Proceedings of the 2005 International Conference on Data Mining, DMIN'05).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Classification of large graphs by a local tree decomposition

AU - Emmert-Streib, Frank

AU - Dehmert, Matthias

AU - Kilian, Jürgen

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/49749142261

M3 - Conference contribution

AN - SCOPUS:49749142261

SN - 9781932415797

T3 - Proceedings of the 2005 International Conference on Data Mining, DMIN'05

SP - 200

EP - 207

BT - Proceedings of the 2005 International Conference on Data Mining, DMIN'05

T2 - 2005 International Conference on Data Mining, DMIN'05

Y2 - 20 June 2005 through 23 June 2005

ER -

Classification of large graphs by a local tree decomposition

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this