gRegress: Extracting Features from Graph Transactions for Regression

1 Motivation

Regression models are the trusted workhorse for predictive modeling in a variety of application domains. The problem of mining subgraph features from a database of labelled graphs (referred to as graph transactions) for building regression models is critical when an attribute-valued representation is insufficient to capture the domain of study. An example of such a scenario would be the case where we are trying to build a regression model for the toxicity of chemical compounds which is a real value collected from in-vivo experiments. The chemical compounds are represented as graph transactions and the real value of interest associated with each transaction is the toxicity. Is such a scenario, how do we extract relevant features for building a regression model? Currently the state of the art in this regard is the large body of work on the problem of frequent subgraph mining (relevant literature on this topic is reviewed later in the paper). A typical frequent subgraph mining algorithm will mine the complete set of subgraphs with a user-defined frequency threshold and these subgraphs can be used as features to build a regression model. Such an approach involving feature extraction using a frequent subgraph mining algorithm has been studied in the context of the graph classification problem and has been applied to the task of classifying chemical compounds

Diane J. Cook Washington State University cook@eecs.wsu.edu

[Deshpande et al., 2005] and proteins [Huan et al., 2004] with promising results. However, this approach is plagued with a number of problems which we now illustrate by describing a small case study. The objective of this case study is to motivate our approach and set the stage for the rest of the paper.

The case study involves building regression models for predicting the melting point of a set of chemical compounds (details on the data set can be found later in the paper) based solely on subgraph features extracted by the frequent subgraph mining system gSpan using support vector regression. We ran gSpan [Yan and Han, 2002] on the dataset at thresholds ranging from 20% to 5% in 1% decrements with a maximum size of 10. Regression models were built using the feature vectors based on the presence/absence of subgraph features using SVR (Support Vector Regression) [Smola and Sch¨olkopf, 2004], [Cristianini and Shawe-Taylor, 2000] (the particular implementation used was SVMlite [Joachims, 1999]) and were evaluated using the Q2 (details on the Q2 metric are found later in the paper) score on a 5-fold cross validation. The Q2 score for the model, the number of subgraphs discovered and the runtimes of gSpan for each threshold setting are illustrated in Figure 1 (a), (b) and (c). We can observe the following. First,the predictive accuracy of the regression model improves as the threshold frequency reduces. This is an expected result [Deshpande et al., 2005] and has been observed earlier. It can be explained by the fact that additional relevant subgraph features are available on which the model can be based. Second, the number of frequent subgraphs and the runtime also increases as the threshold decreases (as expected and observed earlier [Deshpande et al., 2005]) which in the worst case is expected to grow exponentially with the size of graph transactions and the number of graph transactions.

These observations raise the question on how many of the newly considered subgraph features actually contribute to increased predictive accuracy of the regression model. To answer this question we analyzed the frequent subgraphs generated at the threshold of 10%. Figure 1 (i) shows the absolute pairwise correlations between subgraph features for those subgraphs whose absolute correlation with the output is at least 0.20. Pairwise correlation lower than 0.20 is denoted in black while pairwise correlation greater than 0.20 is denoted in white. The subgraphs in black are the ones that contribute most to the predictive accuracy of the regression model based on these thresholds on correlation with the output and the pairwise correlations. While these thresholds are somewhat arbitrary, they do give a certain measure of the redundancy of the subgraphs generated. Typically, feature selection for building regression models considers the trade off between how much a feature correlates with the output and how much the feature correlates with the features already selected. Our claim is that mining features based on their frequency produces useful features but also produces additional redundant features at an added cost. Of course, redundant features could be eliminated by a simple post processing step but this is computationally expensive as the redundant subgraphs are still generated in the first place. We should prefer to mine for a set of subgraphs such that each member of this set has high correlation with the output value and that the members of this set have low correlation with each other. Mining a complete set of subgraphs based on two thresholds, correlation with the output and correlation with other features, is an intuitive approach for building regression models and, as this work will show, is also computationally efficient. This brings us to key contributions of this work:

1. For a given subgraph feature, we prove an upper bound on the correlation with the output that can be achieved by any supergraph for this subgraph feature.
2. For a given subgraph feature, we prove a lower bound on the correlation that can be achieved by any supergraph for this subgraph feature with any other subgraph feature.
3. Using these two bounds we design a new algorithm called gRegress, which extracts the complete set of subgraphs such that a) each subgraph in this set has correlation with the real value above a user-specified threshold and b) each subgraph has correlation with any other subgraph in the set below a user-specified threshold.
4. We conduct an experimental validation on a number of real-world datasets showing that in terms of runtime, gRegress substantially outperforms gSpan, often by an order of magnitude while the regression models produced by both approaches have comparable accuracy.

2 ProblemFormulation

Our graphs are defined as G = (VG,EG,LG,LG), where VG is the set of vertices, EG ⊆ VG × VG is a set of edges, LG is the set of labels and L is the labelling function LG : VG ∪ EG → LG. The notions of subgraph (denoted by G ⊆ G′ ), supergraph, graph isomorphism (denoted G = G′ ) and subgraph isomorphism in the case of labelled graphs are intuitively similar to the notions of simple graphs with the additional condition that the labels on the vertexes and edges should match. Our examples consist of pairs,

where xi is a labelled graph and yi ∈ R and is assumed to be centered, that is, ∑i yi = 0. We define the set S to contain every distinct subgraph of every graph in E. For any subgraph feature g ⊆ x we define,

We define the the indicator function I(x) = y.The absolute correlation of a subgraph feature gi with the output is given by,

The absolute correlation of a a subgraph feature gi with another subgraph feature gj is given by,

We can now define the problem as follows.

Given:

1. A set of examples E,
2. A threshold on the correlation with the output α ∈ R, 0 ≤ α ≤ 1
3. A threshold on the correlation between subgraph features β ∈ R, 0 ≤ β ≤ 1

Find: A maximal set H = {g1, g2, ..., gk} such that,

1. For each gi ∈ H,

1. For any gi, gj ∈ H,

We now discuss why it makes intuitive sense to mine for the set H. First, note that the formulation is in terms of absolute correlations. This is simply because we are interested in mining subgraph features with high correlations either positive or negative. Negative correlation, implying that the absence of a subgraph correlates with the output is equivalent to positive correlation as the regression model will simply learn negative weights for such a feature. Next, note that the set H is the maximal or the largest possible set of subgraphs such that a) each subgraph in this set has correlation with the real value above a user-specified threshold α and b) each subgraph has correlation with any other subgraph in the set below a user-specified threshold β. Feature selection for building regression models considers the trade off between how much a feature correlates with the output and how much the feature correlates with the features already selected. The problem definition intuitively captures this trade off.

3 Proposed Algorithm: gRegress

Given the formulation of the problem in the previous section a naive solution would be an algorithm that searches the complete space of subgraph features (of the graph transactions) checking for each subgraph feature conditions (1) and (2) retaining only those subgraph features that satisfy all of them.

Of course, one of the many canonical labeling schemes introduced in frequent subgraph mining systems could be incorporated to prevent the generation of duplicate subgraph features (relevant literature on this topic is reviewed later in the paper).

The critical problem here is determining pruning conditions corresponding to the frequency antimonotone pruning condition used by all frequent subgraph mining systems. The frequency antimonotone pruning condition is a simple observation that if a subgraph feature has frequency below the user specified threshold, no supergraph of this subgraph can be frequent given this threshold. This simple observation allows for massive pruning of the search space in the case of frequent subgraph mining.

Thus the key problem is to answer the following two questions.

1. Given a subgraph feature, what is the highest possible correlation any supergraph of this subgraph feature can achieve with the output?
2. Given a subgraph feature what is the lowest possible correlation any supergraph of this subgraph feature can achieve with some other subgraph feature?

It must be noted that once we have a quantitative measure for questions (1) and (2) it becomes very easy to adapt any frequent subgraph mining system to solve the problem at hand. Quantitative measures for (1) and (2) in a sense correspond to the frequency antimonotone condition in the case of frequent subgraph mining.

For a graph g we define

We have the following upper bound on the correlation any supergraph of a subgraph feature can achieve with the output. For some subgraph features gi and gj if gj ⊆ gi, then,

Proof. It is easy to see that for any subgraph feature say gi if hgi (x) = -1 then for no subgraph feature gi ⊆ gj , hgj (x) = 1. That is, all those x such that hgi (x) = -1, for any gj ⊆ gj hgj (x) = -1. Furthermore, only for those x where hgi (x) = 1 can hgj (x) = -1 for some gi ⊆ gj. The highest possible ρgj ,I can occur in the case where for all x such that I(x) ≤ 0 hgj (x) = -1. The result follows.

For a graph g we define

We have the following lower bound on the correlation any supergraph of a subgraph feature can achieve with some other subgraph feature.

For some subgraph features gi, gj and gk, if gj ⊆ gi, then,

Proof. As before, is easy to see that for any subgraph feature say gi if hgi (x) = -1 then for no subgraph feature gi ⊆ gk, hgk (x) = 1. That is, all those x such that hgi (x) = -1, for any gi ⊆ gk hgk (x) = -1. Furthermore, only for those x where hgi (x) = 1 can hgk (x) = -1 for some gi ⊆ gk. The lowest possible ρgj,gk can occur in the case where for all x such that hgi (x) > 0 hgk (x) = -1. The result follows.

Using these bounds it is now possible to adapt any subgraph enumeration scheme to the task defined earlier. In particular, we adopt the DFS search and DFS canonical labelling used by gSpan. The key steps of our algorithm, which we refer to as gRegress, are summarized in Algorithm 3.1 and Procedure 3.2.

Algorithm 3.1 gRegress(E,α,β,S)

• 2: P ← DFS codes of 1-vertex subgraphs in E

1: H ← ∅ 3: for all gi such that gi ∈ P do: 4: Extend(E, α, β, S, H, gi) 5: return H

Procedure 3.2 Extend(E, α, β, S, H, gi)

• 1: if g not minimumDFS code :

4:

return

• 5: for all gj such that gj ∈ H:

• 7: return

• 9: P ←DFS codes of rightmost extensions of gi 10: for all gk such that gk ∈ P :

4 Experimental Evaluation

Our experimental evaluation of the proposed gRegress algorithm seeks to answer the following questions.

1. How do the subgraph features extracted by gRegress compare with frequent subgraph mining algorithms with respect to predictive accuracy of the regression model developed based on these features?
2. How does the gRegress algorithm compare with frequent subgraph mining algorithms in terms of runtime when applied to the task of feature extraction for building regression models?

1. How does the runtime gRegress algorithm vary for various choices of α and β parameters?

4.1 Selecting Data Sets and Choice of Representation

In order to answer these questions we collected a number of data sets. All the data sets are publicly available and are from the domain of computational chemistry. They consist of chemical compounds with a specific property of interest associated with each compound. They include the Karthikeyan data set [Karthikeyan et al., 2005], the Bergstrom data set [Bergstrom et al., 2003], the Huuskonen data set [Huuskonen, 2000], the Delaney data set, [Delaney, 2004] the ERBD data set (Estrogen Receptor Binding Dataset) [Tong et al., 2002] and the ARBD data set (Androgen Receptor Binding Data) [Blair et al., 2000], [Branham et al., 2002]. In every case we use a simple graph representation for the chemical compounds with element symbols as vertex labels and bond types as edge labels. The value for which the regression model to be built was centered to have a mean of zero. No information other than the subgraph features are used to build the regression models for any experiments reported in the paper.

4.2 Selecting a Frequent SubgraphMining System

Among the various frequent subgraph mining systems to compare gRegress with, we chose gSpan. While it is unclear whether gSpan is the best frequent subgraph mining [Worlein et al., 2005], [Nijssen and Kok, ] (relevant literature on this topic is reviewed later in the paper) it can definitely be considered to be among the state of the art as far as the frequent subgraph mining problem is concerned. In order to ensure that our results generalize to frequent subgraph mining algorithms in general, we compare the number of subgraphs considered by both gRegress and gSpan. This is simply a count of all minimal DFS codes considered by each of the systems. The difference between the number of minimal DFS codes considered by gSpan and gRegress gives us a measure of how gRegress compares with any other frequent subgraph mining system. This is because different frequent subgraph mining systems may use other forms of canonical labelling and search mechanisms will prevent the generation of duplicate subgraph features better than gSpan and gRegress but every subgraph feature (the minimal code in the case of gSpan and gRegress) will have to be considered at least once. If gRegress considers significantly fewer subgraphs, the speedup in terms of runtime would most likely apply to other frequent subgraph mining systems also.

4.3 Selecting a Regression Algorithm

Among the various approaches to regression we chose SVR (Support Vector Regression) [Smola and Sch¨olkopf, 2004], [Cristianini and Shawe-Taylor, 2000] which can be considered among the state of the art as far as the regression problem is concerned. In particular, we use the SVMLite [Joachims, 1999] package. While it is possible that in certain situations other regression algorithms might outperform SVR, we find it unlikely to get opposite results while comparing the quality of the regression models based on the subgraph features produced by gSpan and gRegress with any regression algorithm. But in future work we will consider other regression methods.

4.4 The Q2 score

We use the Q2 score to evaluate the predictive accuracy of the regression models. While other measures of regression quality exist, we chose Q2 due to its use in evaluating other graph regression methods [Saigo et al., 2008]. The Q2 score for a regression function f is defined as follows.

Note that the Q2 score is a real number between 0 and 1 and its interpretation is similar to the Pearson correlation coefficient. The closer it is to 1, the better the regression function fits the testing data.

4.5 Experiments

In order to answer question (1) and (2) we conducted experiments on gSpan and gRegress on the six data sets described above. The subgraph features produced by each algorithm were used to build a regression model using SVR. The predictive accuracy of the models was evaluated based on the Q2 score using a 5-fold cross validation. Additionally the runtimes and the number of subgraphs considered by each algorithm were also recorded. The maximum subgraph size for each system was set to ten. The parameters of each system (threshold frequency in the case of gSpan and the α and β parameters in the case of gRegress) were systematically varied. While comparing results on the various runs of the algorithms, we select the significantly highest Q2 scores achieved by each system and then compare the lowest possible runtimes and the subgraphs considered for this Q2 score. The intuition behind this to compare the lowest computational cost for the best possible predictive accuracy. The results of these experiments are reported in Figure 1 (d), (e) and (f) .

In order to answer question (3) we ran gRegress on the Karthikeyan data set (we chose this data set as this was the largest data set in terms of transactions) with α and β parameters systematically varied in small increments of 0.05. Figure 1 (g) and (h) illustrate these results with contour plots.

4.6 Observations

We can observe the following from the experimental results.

1. The predictive accuracy of the regression models based on the features generated by gSpan and gRegress is comparable.
2. gRegress substantially outperforms gSpan in terms of runtime and the number of subgraphs explored.
3. The runtime and the number of subgraphs explored by gRegress increases for small values of α and large values of β.

5 RelatedWork

The field of graph mining or the discovery of interesting patterns from structured data represented as graphs has been extensively researched and good surveys can be found in [Washio and Motoda, 2003] and [Cook and Holder, 2006].

The problem of developing regression models from graph transactions is relatively new as compared to the related problem of graph classification. Recently, [Saigo et al., 2008] extended their boosting based approach for graph classification to perform graph regression. In this work the authors also propose an approach based on partial least square regression. Work related to the task of developing regression models from graph transactions also includes [Ke et al., 2007] in which the authors investigate the search for subgraphs with high correlation from a database of graph transactions.

6 Conclusions and FutureWork

The findings of this work are as follows. Firstly, mining features from graph transactions for building regression models based on their frequency produces useful features but also produces additional redundant features at an added cost. Secondly, features can be mined based on two thresholds, correlation with the output and correlation with other features, at a significantly lower cost without sacrificing the predictive accuracy of the regression model.

The work raises the following questions which we plan to investigate as a part of our future work. First, how can the relation between the α and β parameters and the predictive accuracy of the regression model be characterized? Second, how to systematically select the α and β parameters to get the best regression model?