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.