Empirical comparison of graph classification and regression algorithms

2009 2009

Other formats: Order a copy

Abstract (summary)

Several domains are inherently structural; relevant data cannot be represented as a single table without significant loss of information. The development of predictive models in such domains becomes a challenge as traditional machine learning algorithms which deal with attribute-valued data cannot be used. One approach to develop predictive models in such domains is to represent the relevant data as labeled graphs and treat subgraphs of these graphs as features on which to base the predictive model.

The general area of this research is the development of predictive models for such domains. Specifically, we target domains which are readily modeled as sets of separate graphs (rather than a single graph) and on the tasks of binary classification and regression on such graphs. An example would be learning a binary classification model that distinguishes between aliphatic and aromatic compounds or a regression model for predicting the melting points of chemical compounds.

The contributions of this work include a comprehensive comparison of current approaches to graph classification and regression to identify their strengths and weaknesses, the development of novel pruning mechanisms in the search for subgraph features for the graph regression problem, the development of a new algorithm for graph regression called gRegress and the application of current approaches in graph classification and regression to various problems in computational chemistry.

Our empirical results indicate that our pruning mechanisms can bring about a significant improvement in the search for relevant subgraph features based on their correlation with each other and the target, sometimes by an order of magnitude. Our empirical results also indicate that gRegress addresses a key weakness in the current work on graph regression, namely, the need for a combination of linear models.

Indexing (details)

Artificial intelligence;
Computer science
0800: Artificial intelligence
0984: Computer science
Identifier / keyword
Applied sciences; Graph classification; Regression algorithms
Empirical comparison of graph classification and regression algorithms
Ketkar, Nikhil S.
Number of pages
Publication year
Degree date
School code
DAI-B 70/11, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Holder, Lawrence B.
Washington State University
University location
United States -- Washington
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.