An Application of Boosting toGraph Classification

Taku Kudo,

Yuji Matsumoto

Eisaku Maeda

NTT Communication Science Laboratories.
2-4 Hikaridai, Seika-cho, Soraku, Kyoto, Japan{taku,maeda}@cslab.kecl.ntt.co.jp

Nara Institute of Science and Technology.
8916-5 Takayama-cho, Ikoma, Nara, Japanmatsu@is.naist.jp

Abstract
This paper presents an application of Boosting for classifying labeledgraphs, general structures for modeling a number of real-world data, suchas chemical compounds, natural language texts, and bio sequences. The
proposal consists of i) decision stumps that use subgraph as features,and ii) a Boosting algorithm in which subgraph-based decision stumps
are used as weak learners. We also discuss the relation between our algorithm and SVMs with convolution kernels. Two experiments using
natural language data and chemical compounds show that our method
achieves comparable or even better performance than SVMs with convolution kernels as well as improves the testing efficiency.

1

Introduction

Most machine learning (ML) algorithms assume that given instances are represented innumerical vectors. However, much real-world data is not represented as numerical vectors,
but as more complicated structures, such as sequences, trees, or graphs. Examples include
biological sequences (e.g., DNA and RNA), chemical compounds, natural language texts,
and semi-structured data (e.g., XML and HTML documents).
Kernel methods, such as support vector machines (SVMs) [11], provide an elegant solution
to handling such structured data. In this approach, instances are implicitly mapped into ahigh-dimensional space, where information about their similarities (inner-products) is onlyused for constructing a hyperplane for classification. Recently, a number of kernels havebeen proposed for such structured data, such as sequences [7], trees [2, 5], and graphs [6].
Most are based on the idea that a feature vector is implicitly composed of the counts ofsubstructures (e.g., subsequences, subtrees, subpaths, or subgraphs).
Although kernel methods show remarkable performance, their implicit definitions of feature space make it difficult to know what kind of features (substructures) are relevant or
which features are used in classifications. To use ML algorithms for data mining or as
knowledge discovery tools, they must output a list of relevant features (substructures). This
information may be useful not only for a detailed analysis of individual data but for the human decision-making process.
In this paper, we present a new machine learning algorithm for classifying labeled graphsthat has the following characteristics: 1) It performs learning and classification using theFigure 1: Labeled connected graphs and subgraph relation
structural information of a given graph. 2) It uses a set of all subgraphs (bag-of-subgraphs)
as a feature set without any constraints, which is essentially the same idea as a convolution
kernel [4]. 3) Even though the size of the candidate feature set becomes quite large, it
automatically selects a compact and relevant feature set based on Boosting.

2

Classifier for Graphs

We first assume that an instance is represented in a labeled graph. The focused problem
can be formalized as a general problem called the graph classification problem. The graphclassification problem is to induce a mapping f (x) : X → {±1}, from given training
examples T = {hxi , yi i}L
i=1 , where xi ∈ X is a labeled graph and yi ∈ {±1} is a classlabel associated with the training data. We here focus on the problem of binary classification. The important characteristic is that input example xi is represented not as a numericalfeature vector but as a labeled graph.
2.1

Preliminaries

In this paper we focus on undirected, labeled, and connected graphs, since we can easily
extend our algorithm to directed or unlabeled graphs with minor modifications. Let us introduce a labeled connected graph (or simply a labeled graph), its definitions and notations.
Definition 1 Labeled Connected Graph
A labeled graph is represented in a 4-tuple G = (V, E, L, l), where V is a set of vertices,E ⊆ V × V is a set of edges, L is a set of labels, and l : V ∪ E → L is a mapping thatassigns labels to the vertices and the edges. A labeled connected graph is a labeled graphsuch that there is a path between any pair of verticies.
Definition 2 Subgraph
Let G0 = (V 0 , E 0 , L0 , l0 ) and G = (V, E, L, l) be labeled connected graphs. G0 matches G,
or G0 is a subgraph of G (G0 ⊆ G) if the following conditions are satisfied: (1) V 0 ⊆ V ,(2) E 0 ⊆ E, (3) L0 ⊆ L, and (4) l0 = l. If G0 is a subgraph of G, then G is a supergraphof G0 .
Figure 1 shows an example of a labeled graph and its subgraph and non-subgraph.
2.2

Decision Stumps

Decision stumps are simple classifiers in which the final decision is made by a single hypothesis or feature. Boostexter [10] uses word-based decision stumps for text classification.
To classify graphs, we define the subgraph-based decision stumps as follows.
Definition 3 Decision Stumps for Graphs
Let t and x be labeled graphs and y be a class label (y ∈ {±1}). A decision stumpclassifier for graphs is given by

y t⊆x
def
hht,yi (x) =−y otherwise.

The parameter for classification is a tuple ht, yi, hereafter referred to as a rule of decision
stumps. The decision stumps are trained to find a rule ht̂, ŷi that minimizes the error rate
for the given training data T = {hxi , yi i}L
i=1 :ht̂, ŷi =

L

L

i=1

i=1

1 X
1X
I(yi 6= hht,yi (xi )) = argmin(1 − yi hht,yi (xi )),L
2Lt∈F ,y∈{±1}t∈F ,y∈{±1}argmin(1)SLwhere F is a set of candidate graphs or a feature set (i.e., F = i=1 {t|t ⊆ xi }) and I(·)
is the indicator function. The gain function for a rule ht, yi is defined asdefgain(ht, yi) =LXyi hht,yi (xi ).

(2)

i=1

Using the gain, the search problem (1) becomes equivalent to the problem: h t̂, ŷi =argmaxt∈F ,y∈{±1} gain(ht, yi). In this paper, we use gain instead of error rate for clarity.
2.3

Applying Boosting

The decision stump classifiers are too inaccurate to be applied to real applications, since thefinal decision relies on the existence of a single graph. However, accuracies can be boosted
by the Boosting algorithm [3, 10]. Boosting repeatedly calls a given weak learner andfinally produces a hypothesis f , which is a linear combination of K hypotheses producedPKby the weak learners, i,e.: f (x) = sgn( k=1 αk hhtk ,yk i (x)). A weak learner is built(k)(k)
at each iteration k with different distributions or weights d(k) = (di , . . . , dL ) on the
PL (k)(k)training data, where i=1 di = 1, di ≥ 0. The weights are calculated to concentrate
more on hard examples than easy examples. To use decision stumps as the weak learner of
Boosting, we redefine the gain function (2) as:defgain(ht, yi) =LX

yi di hht,yi (xi ).

(3)

i=1

In this paper, we use the AdaBoost algorithm, the original and the best known algorithm
among many variants of Boosting. However, it is trivial to fit our decision stumps to otherboosting algorithms, such as Arc-GV [1] and Boosting with soft margins [8].

3Efficient Computation

In this section, we introduce an efficient and practical algorithm to find the optimal ruleht̂, ŷi from given training data. This problem is formally defined as follows.
Problem 1 Find Optimal Rule
Let T = {hx1 , y1 , d1 i, . . . , hxL , yL , dL i} be training data where xi is a labeled graph,PLyi ∈ {±1} is a class label associated with xi and di ( i=1 di = 1, di ≥ 0) is a normalized weight assigned to xi . Given T , find the optimal rule ht̂, ŷi that maximizes the gain,SLi.e., ht̂, ŷi = argmaxt∈F ,y∈{±1} di yi hht,yi , where F = i=1 {t|t ⊆ xi }.
The most naive and exhaustive method in which we first enumerate all subgraphs F andthen calculate the gains for all subgraphs is usually impractical, since the number of subgraphs is exponential to its size. We thus adopt an alternative strategy to avoid such exhaustive enumerations. The method to find the optimal rule is modeled as a variant ofbranch-and-bound algorithm and will be summarized as the following strategies: 1) DefineFigure 2: Example of DFS Code Tree for a grapha canonical search space in which a whole set of subgraphs can be enumerated. 2) Find
the optimal rule by traversing this search space. 3) Prune the search space by proposing acriteria for the upper bound of the gain. We will describe these steps more precisely in thenext subsections.
3.1

Efficient Enumeration of Graphs

Yan et al. proposed an efficient depth-first search algorithm to enumerate all subgraphsfrom a given graph [12]. The key idea of their algorithm is a DFS (depth first search)code, a lexicographic order to the sequence of edges. The search tree given by the DFS
code is called a DFS Code Tree. Leaving the details to [12], the order of the DFS code
is defined by the lexicographic order of labels as well as the topology of graphs. Figure 2
illustrates an example of a DFS Code Tree. Each node in this tree is represented in a 5-tuple[i, j, vi , eij , vj ], where eij , vi and vj are the labels of i−j edge, i-th vertex, and j-th vertex
respectively. By performing a pre-order search of the DFS Code Tree, we can obtain all thesubgraphs of a graph in order of their DFS code. However, one cannot avoid isomorphic
enumerations even giving pre-order traverse, since one graph can have several DFS codes
in a DFS Code Tree. So, canonical DFS code (minimum DFS code) is defined as its firstcode in the pre-order search of the DFS Code Tree. Yan et al. show that two graphs G
and G0 are isomorphic if and only if minimum DFS codes for the two graphs min(G)and min(G0 ) are the same. We can thus ignore non-minimum DFS codes in subgraphenumerations. In other words, in depth-first traverse, we can prune a node with DFS codec, if c is not minimum. The isomorphic graph represented in minimum code has alreadybeen enumerated in the depth-first traverse. For example, in Figure 2, if G1 is identical toG0 , G0 has been discovered before the node for G1 is reached. This property allows us to
avoid an explicit isomorphic test of the two graphs.
3.2

Upper bound of gain

DFS Code Tree defines a canonical search space in which one can enumerate all subgraphsfrom a given set of graphs. We consider an upper bound of the gain that allows pruning ofsubspace in this canonical search space. The following lemma gives a convenient methodof computing a tight upper bound on gain(ht0 , yi) for any supergraph t0 of t.
Lemma 1 Upper bound of the gain: µ(t)For any t0 ⊇ t and y ∈ {±1}, the gain of ht0 , yi is bounded by µ(t) (i.e., gain(ht0 yi) ≤ µ(t)),
where µ(t) is given by
µ(t)

def

=



max 2

X

di −

{i|yi =+1,t⊆xi }LX

yi · di , 2

X

di +

{i|yi =−1,t⊆xi }

i=1

L
X
i=1

Proof 1gain(ht0 , yi) =

L
X
i=1

di yi hht0 ,yi (xi ) =

L
X
i=1



yi · di .

di yi · y · (2I(t0 ⊆ xi ) − 1),where I(·) is the indicator function. If we focus on the case y = +1, thengain(ht0 , +1i)

=

2

X

yi di −

Xdi −{i|t0 ⊆xi }

≤

2

L
X

yi · di ≤ 2{i|yi =+1,t⊆xi }≤LX

yi · dii=1

yi · di ,i=1

since |{i|yi = +1, t0 ⊆ xi }| ≤ |{i|yi = +1, t ⊆ xi }|gain(ht0 , −1i)

di −{i|yi =+1,t0 ⊆xi }

i=1

L
X

X

2

X

for any t0 ⊇ t. Similarly,
di +{i|yi =−1,t⊆xi }LX

yi · di .

i=1

Thus, for any t0 ⊇ t and y ∈ {±1}, gain(ht0 , yi) ≤ µ(t). 2

We can efficiently prune the DFS Code Tree using the upper bound of gain u(t). During
pre-order traverse in a DFS Code Tree, we always maintain the temporally suboptimal gain
τ among all the gains calculated previously. If µ(t) < τ , the gain of any supergraph t 0 ⊇ t
is no greater than τ , and therefore we can safely prune the search space spanned from thesubgraph t. If µ(t) ≥ τ , then we cannot prune this space since a supergraph t0 ⊇ t might
exist such that gain(t0 ) ≥ τ .
3.3

Efficient Computation in BoostingAt each Boosting iteration, the suboptimal value τ is reset to 0. However, if we can calculate a tighter upper bound in advance, the search space can be pruned more effectively. For
this purpose, a cache is used to maintain all rules found in the previous iterations. Suboptimal value τ is calculated by selecting one rule from the cache that maximizes the gain of
the current distribution. This idea is based on our observation that a rule in the cache tends
to be reused as the number of Boosting iterations increases. Furthermore, we also maintainthe search space built by a DFS Code Tree as long as memory allows. This cache reduces
duplicated constructions of a DFS Code Tree at each Boosting iteration.

4

Connection to Convolution Kernel

Recent studies [1, 9, 8] have shown that both Boosting and SVMs [11] work according tosimilar strategies: constructing an optimal hypothesis that maximizes the smallest margin
between positive and negative examples. The difference between the two algorithms is themetric of margin; the margin of Boosting is measured in l1 -norm, while that of SVMs is
measured in l2 -norm. We describe how maximum margin properties are translated in the
two algorithms.
AdaBoost and Arc-GV asymptotically solve the following linear program, [1, 9, 8],
maxw∈IRJ ,ρ∈IR+ρ;s.t. yiJX

wj hj (xi ) ≥ ρ, ||w||1 = 1

(4)

j=1

where J is the number of hypotheses. Note that in the case of decision stumps for graphs,
J = |{±1} × F| = 2|F|.
SVMs, on the other hand, solve the following quadratic optimization problem [11]: 1
maxw∈IRJ ,ρ∈IR+1

ρ; s.t. yi · (w · Φ(xi )) ≥ ρ, ||w||2 = 1.

For simplicity, we omit the bias term (b) and the extension of Soft Margin.

(5)

The function Φ(x) maps the original input example x into a J-dimensional feature vector(i.e., Φ(x) ∈ IRJ ). The l2 -norm margin gives the separating hyperplane expressed by dotproducts in feature space. The feature space in SVMs is thus expressed implicitly by usinga Marcer kernel function, which is a generalized dot-product between two objects, (i.e.,K(x1 , x2 ) = Φ(x1 ) · Φ(x2 )).
The best known kernel for modeling structured data is a convolution kernel [4] (e.g., stringkernel [7] and tree kernel [2, 5]), which argues that a feature vector is implicitly composedof the counts of substructures. 2 The implicit mapping defined by the convolution kernel
is given as: Φ(x) = (#(t1 ⊆ x), . . . , #(t|F | ⊆ x)), where tj ∈ F and #(u) is the
cardinality of u. Noticing that a decision stump can be expressed as hht,yi (x) = y · (2I(t ⊆x) − 1), we see that the constraints or feature space of Boosting with substructure-based
decision stumps are essentially the same as those of SVMs with the convolution kernel 3 .
The critical difference is the definition of margin: Boosting uses l1 -norm, and SVMs use
l2 -norm. The difference between them can be explained by sparseness.
It is well known that the solution or separating hyperplane of SVMs is expressed in a linear
PL
combination of training examples using coefficients λ, (i.e., w =i=1 λi Φ(xi )) [11].
Maximizing l2 -norm margin gives a sparse solution in the example space, (i.e., most of λi
becomes 0). Examples having non-zero coefficients are called support vectors that form thefinal solution. Boosting, in contrast, performs the computation explicitly in feature space.
The concept behind Boosting is that only a few hypotheses are needed to express the final
solution. l1 -norm margin realizes such a property [8]. Boosting thus finds a sparse solution
in the feature space. The accuracies of these two methods depend on the given training
data. However, we argue that Boosting has the following practical advantages. First, sparse
hypotheses allow the construction of an efficient classification algorithm. The complexityof SVMs with tree kernel is O(l|n1 ||n2 |), where n1 and n2 are trees, and l is the number of
support vectors, which is too heavy to be applied to real applications. Boosting, in contrast,
performs faster since the complexity depends only on a small number of decision stumps.
Second, sparse hypotheses are useful in practice as they provide “transparent” models withwhich we can analyze how the model performs or what kind of features are useful. It isdifficult to give such analysis with kernel methods since they define feature space implicitly.

5

Experiments and Discussion

To evaluate our algorithm, we employed two experiments using two real-world data.
(1) Cellphone review classification (REV)The goal of this task is to classify reviews for cellphones as positive or negative. 5,741 sentences were collected from an Web-BBS discussion about cellphones in which users weredirected to submit positive reviews separately from negative reviews. Each sentence is represented in a word-based dependency tree using a Japanese dependency parser CaboCha 4 .
(2) Toxicology prediction of chemical compounds (PTC)
The task is to classify chemical compounds by carcinogenicity. We used the PTC data
set5 consisting of 417 compounds with 4 types of test animals: male mouse (MM), female
2
Strictly speaking, graph kernel [6] is not a convolution kernel because it is not based on the countof subgraphs, but on random walks in a graph.
3
The difference between decision stumps and the convolution kernels is that the former uses abinary feature denoting the existence (or absence) of each substructure, whereas the latter uses the
cardinality of each substructure. However, it makes little difference since a given graph is often sparseand the cardinality of substructures will be approximated by their existence.
4
http://chasen.naist.jp/˜ taku/software/cabocha/
5
http://www.predictive-toxicology.org/ptc/

Table 1: Classification F-scores of the REV and PTC tasks
REV
Boosting
SVMs

BOL-based Decision Stumps
Subgraph-based Decision Stumps
BOL Kernel
Tree/Graph Kernel

76.6
79.0
77.2
79.4

MM

PTC
FM
MR

47.0
48.9
40.9
42.3

52.9
52.5
39.9
34.1

42.7
55.1
43.9
53.2

FR

26.9
48.5
21.8
25.9

mouse (FM), male rat (MR) and female rat (FR). Each compound is assigned one of thefollowing labels: {EE,IS,E,CE,SE,P,NE,N}. We here assume that CE,SE, and P are “positive” and that NE and NN are “negative”, which is exactly the same setting as [6]. We thus
have four binary classifiers (MM/FM/MR/FR) in this data set.
We compared the performance of our Boosting algorithm and support vector machines withtree kernel [2, 5] (for REV) and graph kernel [6] (for PTC) according to their F-score in
5-fold cross validation.
Table 1 summarizes the best results of REV and PCT task, varying the hyperparametersof Boosting and SVMs (e.g., maximum iteration of Boosting, soft margin parameter ofSVMs, and termination probability of random walks in graph kernel [6]). We also show
the results with bag-of-label (BOL) features as a baseline. In most tasks and categories,
ML algorithms with structural features outperform the baseline systems (BOL). These results support our first intuition that structural features are important for the classification of
structured data, such as natural language texts and chemical compounds.
Comparing our Boosting algorithm with SVMs using tree kernel, no significant difference
can be found the REV data set. However, in the PTC task, our method outperforms SVMs
using graph kernel on the categories MM, FM, and FR at a statistically significant level.
Furthermore, the number of active features (subgraphs) used in Boosting is much smaller
than those of SVMs. With our methods, about 1800 and 50 features (subgraphs) are usedin the REV and PTC tasks respectively, while the potential number of features is quite
large. Even giving all subgraphs as feature candidates, Boosting selects a small and highly
relevant subset of features.
Figure 3 show an example of extracted support features (subgraphs) in the REV and PTC
task respectively. In the REV task, features reflecting the domain knowledge (cellphonereviews) are extracted: 1) “want to use ”→ positive, 2) “hard to use”→ negative, 3)“recharging time is short” → positive, 4) “recharging time is long” → negative. Thesefeatures are interesting because we cannot determine the correct label (positive/negative)
only using such bag-of-label features as “charging,” “short,” or “long.” In the PTC task,
similar structures show different behavior. For instance, Trihalomethanes (TTHMs), wellknown carcinogenic substances (e.g., chloroform, bromodichloromethane, and chlorodibromomethane), contain the common substructure H-C-Cl (Fig. 3(a)). However, TTHMs
do not contain the similar but different structure H-C(C)-Cl (Fig. 3(b)). Such structural
information is useful for analyzing how the system classifies the input data in a category
and what kind of features are used in the classification. We cannot examine such analysis
in kernel methods, since they define their feature space implicitly.
The reason why graph kernel shows poor performance on the PTC data set is that it cannot
identify subtle difference between two graphs because it is based on a random walks in agraph. For example, kernel dot-product between the similar but different structures 3(c)and 3(d) becomes quite large, although they show different behavior. To classify chemicalcompounds by their functions, the system must be capable of capturing subtle differencesamong given graphs.
The testing speed of our Boosting algorithm is also much faster than SVMs with tree/graphFigure 3: Support features and their weights
kernels. In the REV task, the speed of Boosting and SVMs are 0.135 sec./1,149 instancesand 57.91 sec./1,149 instances respectively6 . Our method is significantly faster than SVMs
with tree/graph kernels without a discernible loss of accuracy.

6

Conclusions

In this paper, we focused on an algorithm for the classification of labeled graphs. The
proposal consists of i) decision stumps that use subtrees as features, and ii) a Boostingalgorithm in which subgraph-based decision stumps are applied as the weak learners. Twoexperiments are employed to confirm the importance of subgraph features. In addition, we
experimentally show that our Boosting algorithm is accurate and efficient for classification
tasks involving discrete structural features.

References[1] Leo Breiman. Prediction games and arching algoritms. Neural Computation, 11(7):1493 –
1518, 1999.
[2] Michael Collins and Nigel Duffy. Convolution kernels for natural language. In NIPS 14, Vol.1,
pages 625–632, 2001.
[3] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learningand an application to boosting. Journal of Computer and System Sicences, 55(1):119–139,
1996.
[4] David Haussler. Convolution kernels on discrete structures. Technical report, UC Santa Cruz
(UCS-CRL-99-10), 1999.
[5] Hisashi Kashima and Teruo Koyanagi. Svm kernels for semi-structured data. In Proc. of ICML,
pages 291–298, 2002.
[6] Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeledgraphs. In Proc. of ICML, pages 321–328, 2003.
[7] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. Textclassification using string kernels. Journal of Machine Learning Research, 2, 2002.
[8] Gunnar. Rätsch, Takashi. Onoda, and Klaus-Robert Müller. Soft margins for AdaBoost. Machine Learning, 42(3):287–320, 2001.
[9] Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: a new
explanation for the effectiveness of voting methods. In Proc. of ICML, pages 322–330, 1997.
[10] Robert E. Schapire and Yoram Singer. BoosTexter: A boosting-based system for text categorization. Machine Learning, 39(2/3):135–168, 2000.
[11] Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.
[12] Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In Proc. of
ICDM, pages 721–724, 2002.
6

We tested the performances on Linux with XEON 2.4Ghz dual processors.