Send to

Choose Destination
Genome Inform. 2008;20:102-11.

Semi-supervised graph partitioning with decision trees.

Author information

Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto, Japan.


In this paper we investigate a new framework for graph partitioning using decision trees to search for sub-graphs within a graph adjacency matrix. Graph partitioning by a decision tree seeks to optimize a specified graph partitioning index such as ratio cut by recursively applying decision rules found within nodes of the graph. Key advantages of tree models for graph partitioning are they provide a predictive framework for evaluating the quality of the solution, determining the number of sub-graphs and assessing overall variable importance. We evaluate the performance of tree based graph partitioning on a benchmark dataset for multiclass classification of tumor diagnosis based on gene expression. Three graph cut indices will be compared, ratio cut, normalized cut and network modularity and assessed in terms of their classification accuracy, power to estimate the optimal number of sub-graphs and ability to extract known important variables within the dataset.

[Indexed for MEDLINE]

Supplemental Content

Loading ...
Support Center