An efficient heuristic approach for learning a set of composite graph classification rules

Abstract

We propose in this paper an efficient heuristic method to learn a set of classification rules from a set of graph objects. Graph classification has various real-life applications, however, this is a very challenging problem due to the intrinsic complex structure of graphs. The proposed rule constructing method is based on two lines of research. The first line of research is on Boosting [11] in which a weak-hypothesis is regarded as a rule and is assigned with a real-valued confidence. In our research, a rule is comprised by a set of subgraphs that maximize an objective function in each round of boosting. The second line of research is on utilizing the poset order of the Formal Concept Lattice of subgraphs to accelerate the process of generating rule candidates. The learned rule set is compact, comprehensible and obtains high classification accuracy on tested datasets.

Keywords

Graph classification formal concept analysis confidence-rated boosting approximation method

1. Introduction

We consider in this paper the problem of predicting the label $y\in\mathcal{Y}$ of an input graph $g\in\mathcal{G}$ as $y=f(g)$ with a modeling function $f$ learned from $n$ observations

$\displaystyle\{(g_{1},y_{1}),(g_{2},y_{2}),\dots,(g_{n},y_{n})\},g_{i}\in% \mathcal{G},y_{i}\in\mathcal{Y}$ (1)

where $\mathcal{G}$ is a set of all connected, node-and-edge-labeled, undirected graphs, and $\mathcal{Y}$ is a label space, given as $\mathcal{Y}=\{1,\dots,k\}$ .

This problem, often called graph classification, has attracted a lot of attention over the last twenty years. Applications of graph classification range from drug discovery (e.g., predicting whether or not a chemical compound has the desired biological activity, or is toxic or non-toxic), image analysis (e.g., image segmentation and object recognition), to biological network analysis, and social network (e.g., classifying users based on their feeds on Facebook, Twitter, etc.) [16, 1, 30].

The main challenge in classifying graphs is how to make sense out of graph structures. Existing methods, whether explicitly or not, use substructures such as walks, paths, subtrees, and subgraphs to represent graphs for the learning purpose [2, 13, 28]. Graph kernel methods, for example, represent a graph as a very high dimensional (and often sparse) vector of indicators of substructures, and then compute the dot product between two feature vectors by a recursive algorithm [13]. In general, it is impossible to generate all possible substructures beforehand, and therefore, methods that require to take all substructures into account are not always beneficial. Additionally, in the domain of graph classification, the prediction accuracy is not the unique goal. It is often required in various practical applications that the prediction rules are comprehensible to human. In the case of graph kernel methods for which features are not explicitly computed, the prediction rules are certainly not easy to interpret.

Boosting [11], a very successful classification algorithm that produces a linear combination of weak classifiers (a.k.a. base learners), has been extended for graph classification with improved accuracy and comprehensibility. Kudo et al. [21] proposed the first boosting algorithm for graph based on AdaBoost in which subgraph-based decision stumps were used as weak learners. In order to avoid the exhaustive enumeration of all subgraphs which is usually impractical, the authors proposed an efficient search-space pruning strategy based on the upper bound of the gain. It was shown experimentally that the proposed graph boosting algorithm leads to good accuracy and efficiency in classifying graph objects. However, this AdaBoost-based algorithm can still take many iterations to converge. Saigo et al. [29] proposed a mathematical programming boosting method that can build the prediction rule with fewer iterations compared with the AdaBoost-based method [21]. In the proposed algorithm called gBoost, single subgraphs were also used as weak learners.

Boosting-based algorithms for graph classification typically require a long training phase. In the algorithms of Kudo et al. [21] and Saigo et al. [29] the search spaces are usually very large despite the fact that they used branch-and-bound techniques and only decision stumps that are connected subgraphs were searched for. To further reduce the size of the search space, the minimum support constraint or the maximum subgraph size constraint have been used. These constraints, however, may results in losing of some optimal subgraphs. Another issue that makes boosting-based algorithms for graph classification hard is that we have to call the subgraph mining procedure for every boosting iteration because weights of examples must be recalculated.

In the above mentioned work, the feature space of subgraphs is completely constructed by subgraph mining [35], and weak learners are chosen as individual connected subgraphs. In some problems, choosing a subgraph as a weak learner can be a good solution and leads to good classification performance. However, it is not always the case that an individual connected subgraph is the optimal choice. In many complex graph classification problems, a weak learner of a subgraph can be extremely weak due to its limited discriminative ability in separating two or more classes. Boosting these poor decision stumps thus often leads to very long training phase because little training error decreases at each boosting step. Therefore, it should be a better idea to construct weak learners based on a group of subgraphs in cases no individual subgraph having enough discrimination power and a group of subgraphs may jointly providing higher discrimination power.

Figure 1.

An example of five graphs in two classes: positive (+) and negative (-). Below are three frequent subgraph patterns $P_{1}$ , $P_{2}$ , and $P_{3}$ .

For example, let us consider the graph set given in Fig. 1 where the first two graphs are positive and the remaining three graphs are negative. Three frequent subgraph patterns $P_{1}$ , $P_{2}$ , and $P_{3}$ all occur in two positive graphs and two negative graphs. These three patterns are not so discriminative. However, the subgraph group formed by $P_{1}$ , $P_{2}$ , and $P_{3}$ only occurs in positive graphs and never occur in negative graphs and therefore is very discriminative. In reality, there are many examples that support this idea. In chemistry, a group of substructures may jointly decide the property of a chemical compound. In image classification, several parts of an image may jointly determine the type of the image.

We propose a method to build a set of graph classification rules where each rule antecedent is formed by a conjunction of subgraph conditions. In other words, the IF part of each rule is satisfied by the co-occurrence of subgraph patterns instead of a single subgraph pattern. We apply the confidence-rated boosting method to find optimal rule at each round of boosting and to reduce weights of graph examples covered by the rules generated so far. The key challenge in finding combined subgraphs is the exponentially-large search space, $2^{\Omega}$ , where $\Omega$ is the set of all subgraphs. We deal with the problem by introducing an appropriate representation of the search space based on Formal Concept Analysis [12] and using an heuristic search method to search for combined subgraphs on the Concept Lattice. The heuristic search method utilizes the partial order among concepts on the lattice.

1.1 Related work

A number of algorithms have been proposed for the graph classification problem [15, 18, 8, 21, 25, 34, 31, 29, 17, 19, 10]. One of the pioneering algorithms for graph classification is SubdueCL [15]. The algorithm searches for subgraphs present in positive examples and absent in the negative examples using a greedy, heuristic search strategy. There is an important line of research for the graph classification problem involving the development subgraph kernels [18, 14, 27, 23]. Kernel-based methods take all subgraphs into account to represent a graph as a very high dimensional vector of indicators of subsgraphs. However, using all subgraphs is not always efficient and effective. Therefore, many approaches restrict the set of subgraph features to frequently occurring, frequent closed, or class-correlated subgraphs [8, 3]. Another important line of research for the graph classification problem is based on the boosting approach [21, 29, 10]. Kudo et al. proposed to combine AdaBoost and the optimal pattern search algorithm. Saigo et al. proposed to learn from graph data using mathematical programming based on LP-Boost [7]. Fei et al. introduced an algorithm that considers the structure relationships of base learners in the functional space. A common point of these algorithms is that they use individual subgraphs as base learner. There are algorithms using different strategies for searching for optimal subgraphs [34, 31, 17].

There are also graph classification algorithms proposed under the semi-supervised setting [20, 19, 37]. In [20], subgraph features are selected from both labeled and unlabeled data using a feature evaluation criterion. The method proposed in [37] deals with the situation where only positive and unlabeled graphs are available. In [19] a process of active sample selection together with feature selection is performed.

In parallel, there are methods that represent graphs in a pairwise manner using similarity or distance measures [4, 33, 26]. Bunke and Shearer [4] proposed to use the maximum common subgraph of two graphs to compute the similarity between them. Wallis et al. [33] proposed to use the union of the two graphs and consider also the sizes of the graphs for computing the distance. Nguyen and Yamamoto [26] proposed a similarity measure based on the concept lattice, taking into account the lattice structure explicitly. The measures can be used in supervised, semi-supervised, unsupervised learnings and in matching graphs.

The rest of the paper is organized as following. In Section 2, we introduce a method for finding optimal rule based on the confidence-rated boosting method. In Section 3, we describe the Formal Concept Lattice for graphs and an heuristic method for rule growing based on the lattice. In Section 4, we describe our experiments on some real-world graph datasets to verify the effectiveness of the proposed method. We summarize the paper and provide directions for future work in Section 5.

2. Finding optimal graph classification rules

We build an ensemble of weighted rules using boosting. Each rule in the rule set is associated with a real number confidence rating. We generate only rules that predict membership in the positive class. That means, only rules with positive confidence rating are generated. For predicting membership in the negative class, we use a single default rule which is a rule with a negative confidence rating. This approach is similar to SLIPPER [5] and many other rule learners, resulting in a more comprehensible rule set.

The boosting technique can be considered as generalization of set covering. After a rule is found, covered examples are given lower weights instead of being removed from the training set. By this, a new rule will focus on examples which are hardest to classify by rules found so far. In propositional rule learning, one of the first approaches to do so was SLIPPER. Our proposed method relates to SLIPPER in that both are based on confidence-rated boosting, which is generalization of AdaBoost. The main difference between our method and SLIPPER is in the rule growing details. In SLIPPER conditions to be added to a rule are readily available in the training data, but for graph data rule conditions must be mined for. We propose to use the partial ordering in the lattice structure of graphs when growing rules. This method drastically reduces the complexity of calculations.

Algorithm 1
A generalized version of AdaBoost with real valued predictions

Given: ( $x_{1}$ , $y_{1}$ ), $\dots$ ,( $x_{n}$ , $y_{n}$ ); $x_{i}\in\mathcal{X}$ (a domain), $y_{i}\in\{+1,-1\}$ Initialize $D_{1}(i)=1/n$ For $t=1\dots T$ :
1:
Train weak learner using distribution $D_{t}$ ;
2:
Get weak hypothesis $h_{t}$ : $\mathcal{X}\rightarrow\mathbb{R}$ ;
3:
Choose $\alpha_{t}\in\mathbb{R}$ ;
4:
Update: $D_{t+1}(i)$ = $D_{t}(i)$ $exp(-\alpha_{t}y_{i}h_{t}(x_{i}))/Z_{t}$ ; Output final hypothesis: $H(x)$ = $sign(\sum_{1}^{T}\alpha_{t}h_{t}(x))$

The generalized boosting algorithm is given in Algorithm 1 where $Z_{t}=\Sigma_{i}D_{t}(i)\exp(-\alpha_{t}y_{i}h_{t}(x_{i}))$ is a normalization constant that ensures the distribution $D_{t+1}$ sums to 1. We can rewrite $Z$ by omitting the dependency on $t$ as

$\displaystyle Z=\sum_{x_{i}\notin R}D(i)+\sum_{x_{i}\in R}D(i)exp(-y_{i}C_{R})$ (2)

where $C_{R}=\alpha h(x)$ is the confidence value of the rule $R$ . To minimize training error, on each round of boosting, we pick a rule $R$ that minimize Eq. (2). We let the rules generated by the weak learner to “abstain” (vote with confidence zero) on examples not covered by the rule, and vote with an appropriate non-zero confidence on covered examples. By solving the equation $\frac{d(Z)}{d(C_{R})}=0$ we get

$\displaystyle C_{R}=\frac{1}{2}\ln{\frac{W^{+}_{R}}{W^{-}_{R}}}$ (3)

where $W^{+}_{R}=\sum_{x_{i}\in R:y_{i}=+1}D(i)$ , and $W^{-}_{R}=\sum_{x_{i}\in R:x_{i}=-1}D(i)$ . Plugging the value of $C_{R}$ into Eq. (2), we obtain $Z=1-(\sqrt{W^{+}_{R}}-\sqrt{W^{-}_{R}})^{2}$ which is minimized if and only if we pick a rule $R$ that maximize $\left|\sqrt{W^{+}_{R}}-\sqrt{W^{-}_{R}}\right|$ . If we consider rules that correlate to only positive class then the best rule is the one that maximizes

$\displaystyle\tilde{Z}=\sqrt{W^{+}_{R}}-\sqrt{W^{-}_{R}}$ (4)

Equation (4) implies that an optimal classification rule based on the confidence-rated boosting method has a natural trade-off between accuracy (the proportion of the positive examples satisfied by a rule to the total number of examples that the rule satisfies) and coverage (the fraction of examples that satisfy the rule). This has practical use in building classification rule sets because we do not need to check rules having too small coverage (too small support set), thus this can help to save a lot of time. Particularly, in the graph mining domain, finding subgraphs of small supports often requires a lot of calculation time.

Equation (4) shows us how to pick the optimal classification rule in a set of rule candidates. However, it does not tell us how to construct the rule candidate set. In the next section, we introduce a method for dealing with this problem, that is, using an iceberg concept lattice of subgraphs to find optimal graph classification rules. Our method is an heuristic one that takes into account the partial order of sets of subgraphs on the lattice. Even though in this paper we discuss and implement only a method for two-class problem, the method can extends easily to multiple classes.
3. The formal concept lattice of graphs

Let $L$ be a finite set and $\leqslant$ a partial ordering on $L$ . A strict partial ordering $<$ is defined from $\leqslant$ as $x<y$ if $x\leqslant y$ and $x\neq y$ . The structure $(L,\leqslant)$ is called a poset. We say that $(L,\leqslant)$ is a lattice if, for every $x,y\in L$ , there is a unique greatest lower bound (denoted $x\wedge y$ ) and a unique least upper bound (denoted $x\vee y$ ). Operations $\wedge$ and $\vee$ are called the meet and join operations, respectively. For finite lattices, there always exist the greatest element (denoted $\top$ ) and the least element (denoted $\bot$ ). A detailed review of the lattice theory can be found in [6, 24].

The term Formal Concept Analysis (FCA) was introduced by Ganter and Wille in 1984 [12], and builds on applied lattice and order theory. FCA is a principled way of constructing a concept hierarchy from a collection of objects and their attributes. In [26], the authors proposed to apply FCA theory to graph data. We give a brief summary of the Formal Concept Lattice for graph data here, following what given in [26].

A formal concept is a pair $(O,A)$ where $O$ (a set of objects) and $A$ (a set of attributes) are connected by two set-theoretic operators $\alpha$ and $\omega$ . The operator $\alpha$ induces the set of attributes from a set of objects, and the operator $\omega$ returns the set of objects from a set of attributes, respectively.

For graph data, each graph instance (for example, a chemical compound) is regarded as an object and all subgraphs of this graph are treated as attributes. Let $\mathcal{G}$ be a set of graph objects and let $\mathcal{S}$ be the set of all subgraphs induced from $\mathcal{G}$ , the operators $\alpha$ and $\omega$ are defined as

$\alpha(G)=\{s\in\mathcal{S}$ $\mid$ $s$ is a maximal common subgraph of all objects in $G\}$ ,

$\omega(S)=\{g\in\mathcal{G}$ $\mid$ s is a subgraph of g (denoted $s\preceq g$ ), for all subgraph attribute $s\in S\}$ .

Let $S$ and $S^{\prime}$ be two sets of subgraphs, we say that $S$ is subsumed by $S^{\prime}$ (denoted $S\vDash S^{\prime}$ ), if and only if for any $s\in S$ , there exists $s^{\prime}\in S^{\prime}$ such that $s\preceq s^{\prime}$ . The partial ordering between two formal concepts of graph can be defined using the subset and the subsumption relationships

$(G,S)\leqslant(G^{\prime},S^{\prime})\Longleftrightarrow O\subseteq G^{\prime}$ (equivalent to $S^{\prime}\vDash S$ ).

The set of all formal concepts of graphs endowed with the $\leqslant$ order forms a formal concept lattice. In this paper we construct the lattice by using the method proposed in [26]. The main idea of the method is to make use of the set of all closed subgraphs returned by a closed subgraph mining algorithm. Figure 2 illustrates an example of the formal concept lattice induced from the set of five graph objects given in Fig. 1. Each concept in the lattice is represented by a rounded rectangle of which the set of subgraphs inside the rectangle is the intent of the concept and the list of integer numbers below the rectangle is the extent of the concept. The extent of a concept is in fact the support set (of graph objects) of the intent’s subgraphs. As we can see, each subgraph in the intent of a concept is a closed subgraph in the sense that every proper supergraph of the subgraph has smaller support set than the support set of the subgraph. Moreover, both the extent and the intent of a concept are closed sets.

As pointed out in [26], the problem of constructing a complete lattice is NP-Complete. In almost every case, it is possible to construct an upper part of the lattice only (called an iceberg lattice) using frequent closed subgraphs. A subgraph is frequent if its support is not less than a given threshold $m i n s u p p$ where support of a subgraph in a graph dataset is the number of graph objects in the set that contain it. In our example, if we restrict $minsupp=3$ then we obtain an iceberg lattice that is shown in the dashed rectangle of Fig. 2.

Figure 2.

The formal concept lattice of the dataset in Fig. 1. a The entire concept lattice. b An iceberg part of (a) with minsupp $=$ 3 (indicated by a dashed rectangle).

The lattice structure, once built, could facilitate pattern understanding, knowledge discovery, and interactive exploration of complex graph data. In [26] the authors proposed to learn a similarity measure between two graph objects based on the iceberg lattice. In this paper we propose to learn a set of classification rule for graphs using the lattice. Although both methods are based on the iceberg lattice for the learning purpose, there is difference in how the lattice is used. In [26] the iceberg lattice is built once and unchanged during the learning process, in the method proposed in this paper the lattice can be extended accordingly at each round of rule learning. In this sense our method is somewhat similar to the method of [29] where the search space is stored in memory and progressively extended.

4. Rule growing based on the lattice of graphs

In machine learning, a classification rule takes the following form:

$\text{If}\ P_{1}\wedge P_{2}\ldots\wedge P_{n}\ \text{Then}\ y_{j}$

where each $P_{i}$ (1 $\leqslant$ $i$ $\leqslant$ $n$ ) is a descriptor of objects and $y_{j}$ is a class label. In transactional data a descriptor is pair of attribute-value. An object is classified as $y_{j}$ if the object satisfies all the descriptors. In the graph learning domain a descriptor is usually represented as a subgraph and an object is said to satisfy a descriptor if it contains the descriptor as a subgraph. In this paper we generalize this idea by considering a descriptor as a set of subgraphs and a graph object satisfies the descriptor if it contains all the subgraphs in the set.

We propose to search for graph classification rules on an iceberg lattice of subgraphs. Due to the closed property of formal concepts (each intent of a concept is a closed set and each subgraph in the intent is also a closed subgraph), for any subset $S\subseteq 2^{\mathcal{S}}$ we can always find a formal concept $C$ such that $S$ is a subset of $C$ ’s intent and the support set of $S$ is identical to $C$ ’s extent. This means that the lattice contains complete information for finding rules. If we want to search for a rule that classifies positive graphs only, such a rule that corresponds to a formal concept $C$ is given by:

$\text{If}\ \wedge\ \text{Intent}(C)\ \text{Then}\ y=+1.$

As mentioned previously, Eq. (4) implies that we do not need to scan the complete formal concept lattice when searching for rules because optimal rules must have large enough support sets, and thus it is appropriate to use an iceberg lattice for this task. The main problem here is that we do not know beforehand how deep an iceberg lattice should be in order for it to contain all the optimal classification rules. This is equivalent to that we do not know how to set the value of the parameter minsupp for the tasks of subgraph mining and lattice construction. Our heuristic method bases on the following assumption. Suppose that the used iceberg lattice is deep enough. There is a high possibility that optimal rules (corresponding to concepts having maximal $\tilde{Z}$ values) are in the iceberg lattice, or if they are not, they locate not far from the bottom line of the iceberg lattice. We expand the iceberg lattice selectively so that it can cover these optimal concepts by merging concepts having high $\tilde{Z}$ values and are near enough on the lattice.

In the “standard theory” of FCA, the following theorem means that the intersection of extents of nodes in a lattice is always an extent of a node in the lattice. The intersection of intents of nodes in a lattice is always an intent of a node in the lattice.

.

(Ganter and Wille) Every extent is the intersection of attribute extents and every intent is the intersection of object intents.

Theorem 1 suggests that we can extend a lattice using the intersection of extents or intents of nodes in the lattice. However, in the “expanded version" of FCA for graph data this theorem no longer holds as shown in [26]. Specifically, the intersection of intents of nodes in a lattice of graph data is not always an intent of a node in the lattice.

.

(Nguyen and Yamamoto) The join of two formal concepts by the Join operator $\vee$ is again a formal concept. Similarly, the meet of two formal concepts by the Meet operator $\wedge$ is again a formal concept.

The Join operator $\vee$ and the Meet operator $\wedge$ for graph data are defined in [26]. In this paper we will use the Meet operator $\wedge$ for expanding the iceberg lattice and finding optimal rules. However, we do not apply the Meet operator to all nodes in the lattice but to only nodes that are promising to reach high $\tilde{Z}$ values. This approximation approach is fast yet efficient. We first give some notions.

If $C_{1}$ and $C_{2}$ are two formal concepts and $C_{1}\leqslant C_{2}$ then $C_{2}$ is called an ancestor of $C_{1}$ on the lattice. Let $C_{1}$ and $C_{2}$ be two formal concepts, the least upper bound $C_{1}\vee C_{2}$ is called the closest ancestor of $C_{1}$ and $C_{2}$ .

The distance between two formal concepts $C_{1}$ and $C_{2}$ is defined as the minimum number of steps to go from $C_{1}$ to $C_{2}$ through their closest ancestor $C_{1}\vee C_{2}$ .

Let $d\geqslant 1$ be a non negative integer given by the user. A neighbor of a concept $C$ is a concept on the lattice having the distance to $C$ that does not exceed $d$ .

Our method works as follows. Given an iceberg concept lattice. At each round of the boosting algorithm, we find $k$ concepts on the lattice having largest $\tilde{Z}$ values so that no pair of concepts among $k$ concepts are neighbors of each other. For each concept $C$ in the $k$ concepts found, we create a cluster of concepts including $C$ itself and all neighbors of $C$ on the lattice. We then used these clusters to generate new concepts by applying the Meet operator on pairs of concepts in each cluster. A concept is not paired with its ancestor since the result will be the concept itself. A new generated concept can be paired with other concept to generate next new concepts. The new concept generation phase terminates if no new concepts with higher $\tilde{Z}$ found or when the stopping criterion is met. The concept with highest $\tilde{Z}$ value is then selected as the optimal rule for the round.

4.1 Stopping criterion

In the graph learning field, a good stopping criterion should: i) limit the maximum amount of time spent per each iteration; ii) stop if the error is no longer decreasing or decreasing too slowly; iii) stop if the support (the number of supporting graphs) of the rule is less than a given threshold $\theta$ . Although our approximation method can efficiently explore the search space, we still use the stopping condition based on the minimum support because it is simple yet effective and can better guarantee over-fitting avoidance. In our experiments, $\theta=$ 2% of dataset size is always used. It is shown experimentally that for the datasets used in this paper, setting $\theta<$ 2% does not improve the classification performance of the algorithms while requiring more computation and may even lead to over-fitting.

Putting all the above discussion together, Algorithm 2 gives our method for graph classification rule finding.

Algorithm 2
Finding rules based on the iceberg lattice

Given: $G$ a set of graphs, minsupp the minimum support, $L$ the iceberg lattice induced from $G$ using minsupp, $D$ weight distribution on $G$ , $k$ and $d$ two positive integers.
1:
Find $k$ concepts on $L$ having largest $\tilde{Z}$ values on the distribution $D$ such that no two concepts are neighbors regarding the distance threshold $d$ ;
2:
For each concept $C$ of $k$ concepts found, build a cluster Cluster(C);
3:
Extend each cluster by generating new concepts by applying Eq. (5) to every pair of concepts in the cluster, repeat this action until the stop condition is met;
4:
Output the rule $R$ corresponding to the concept having the largest $\tilde{Z}$ value;

The Meet ( $\wedge$ ) operator applied for a pair of $C_{1}(O_{1},A_{1})$ and $C_{2}(O_{2},A_{2})$ to generate a new concept is defined according to [26] as

$\displaystyle(O_{1},A_{1})\wedge(O_{2},A_{2})=(O_{1}\cap O_{2},\alpha\circ% \omega(A_{1}\cup A_{2})).$ (5)

The Meet ( $\wedge$ ) operator does two things: to compute the extent using the set intersection operator and to find the intent using the composite operator $\alpha\circ\omega$ . The operator $\alpha\circ\omega$ involves the finding of maximal common subgraphs in the set of graph objects $O_{1}\cap O_{2}$ with $minsupp=|O_{1}\cap O_{2}|$ (as can be seen in Fig. 2). This is usually an expensive operator. However, as shown in the algorithm in Algorithm 2, this operator fires just once for each boosting round when the optimal concept has already been found (in the Step 4) in order to find the intent of the concept that is also the left-hand side of the corresponding classification rule. In the Step 3 of the algorithm, the composite operator $\alpha\circ\omega$ is not used because to compute $\tilde{Z}$ value only the extent is enough.

We call this rule learning algorithm for graph classification as LGC (for Lattice-based Graph Classification Rule Learning). Next, we discuss a relaxed version of the algorithm with reduced learning time.
4.2 A relaxed version of the algorithm

To avoid the computation of exact classification rules that can be expensive, we propose to find and use approximate rules corresponding to approximate intents of the optimal concepts instead. These approximate intents are found by using the following approximate Meet operator (denoted $\tilde{\wedge}$ )

$\displaystyle(O_{1},A_{1})\;\tilde{\wedge}\;(O_{2},A_{2})=(O_{1}\cap O_{2},A_{% 1}\cup A_{2}).$ (6)

The approximate Meet operator does not require to find maximal common subgraphs of graphs in the set $O_{1}\cap O_{2}$ . It simply uses a union operator to group two sets of subgraphs already found. Note that every maximal common subgraph in the set returned by $\alpha\circ\omega(A_{1}\cup A_{2})$ is also a minimal common supergraph of some subgraphs in the set $A_{1}\cup A_{2}$ . For this reason, an approximate classification rule induced by the approximate Meet operator often contain smaller subgraphs and tends to cover a larger set of graph objects compared to the exact classification rule. This may reduce the power of the rule in separating two classes, but in return, the computation time is much less. Figure 3 gives an example of the idea. The bottom left rectangle (in solid line) and the bottom right rectangle (in dashed line) show the concepts resulted from the Meet operator and the approximate Meet operator on two concepts on the top of the figure, respectively. The corresponding left-hand sides of the classification rules are ${A}-{C}-{B}\wedge{A}-{E}$ and ${A}-{C}\wedge{B}-{C}\wedge{A}-{E}\wedge{B}$ , respectively. In this example, both the classification rules cover the same set of graph objects $\{1,5\}$ . In other cases, an approximate classification rule may cover more graph objects as can be easily observed from Fig. 2.

Figure 3.

An example of the Meet operator and the approximate Meet operator.

We call this relaxed version of the LGC algorithm as aLGC (for approximate Lattice-based Graph Classification Rule Learning). As we can see, the performance of both LGC and aLGC is dependent on the size of the lattice they are based on. If the lattice is big enough (in other words, deep enough), there is little difference between the two algorithms in predictive power. However, if the size of the lattice decreases, there is a bigger loss in predictive power of the aLGC algorithm compared with that of the LGC algorithm. We examine the two algorithms with respect to different lattice sizes in the experimental algorithm.

5. Experiments

In this section, we evaluate the performance of the proposed algorithms LGC and aLGC by comparing them with some state-of-the-art algorithms for graph classification. LGC and aLGC are compared to gBoost [29], an efficient method for graph classification and regression based on boosting. gBoost adopts a mathematical programming-based learning method and uses single connected subgraphs as decision stumps. LGC and aLGC are also compared to CORK [31], another efficient method for graph classification which is not based on boosting. In CORK, features are also single connected subgraphs which are found by using a submodular selection criterion in a greedy forward manner.

Table 1
Several statistics of the used datasets

Dataset	Size	MV	AV	ME	AE
AIDS	5,621	222	28	234	30
DD	1,178	5,748	284	14,267	715
NCI1	4,117	111	29	119	32
NCI33	3,298	111	30	119	33
NCI330	4,608	120	25	132	27
NCI41	3,108	111	30	119	33
PTC (MR)	344	109	25	108	26

Size: number of graphs in the dataset, MV: maximum number of vertices, AV: average number of vertices, ME: maximum number of edges, AE: average number of edges.

For the experiments, we use the datasets shown in Table 1. This includes one antiviral screen (AIDS) dataset, four anti-cancer screen datasets (NCI), and one Dobson and Doig (DD) molecular dataset. The AIDS dataset [32] originally contains 43,850 chemical compounds divided into three groups: 423 active (CA) compounds, 1,081 moderately active (CM) compounds and 42,346 inactive (CI) with respect to the HIV virus. This dataset can be found at the website https://dtp.cancer.gov/dtpstandard/AIDSData/index.jsp. We combine the active (CA) and moderately active (CM) compounds to form the active class and randomly select 4,117 inactive compounds from the CI group to form the inactive class in order to get the more balanced dataset.

NCIs [32] are anti-cancer screen datasets collected from the PubChem website http://pubchem.ncbi.nlm.nih.gov. Each of the anti-cancer screens forms a classification problem, where the class labels are either active or inactive in a screen for anti-cancer activity. In each NCI dataset, the active class is vary rare compared to the inactive class. As with the AIDS dataset, we have transformed NCI datasets into more balanced datasets by re-sampling.

DD is a data set of 1,178 protein structures [9]. Each protein is represented by a graph, in which the nodes are amino acids and two nodes are connected by an edge if they are less than 6 Angstroms apart. The edge labels are omitted. The DD dataset is divided into two classes: 691 enzymes and 487 non-enzymes. Among all the datasets, DD is the most densely connected one with an average size of 284 vertices and 715 edges.

PTC dataset (can be collected from http://www.predictive-toxicology.org/ptc/) represents carcinogenicity of chemical compounds for Female Mice (FM), Male Mice (MM), Female Rats (FR) and Male Rats (MR). Compounds are classified according to their carcinogenicity assayed on rats and mice. We assume that compounds labeled as CE, SE, or P as positive, and those of NE or N as negative. We use only MR since the properties of other datasets are similar.

We use the CloseGraph algorithm [36] to generate frequent closed subgraphs at $minsupp=$ 5% of dataset size. The generated frequent closed subgraphs are used to build the iceberg lattice according to the method described in [26]. The $k$ parameter, the number of seeding concept clusters used in Algorithm 2, is chosen from $\{4,6,8,10,12\}$ . Experimental results show that $k=8$ is often the most suitable number for tested datasets and larger values of $k$ do not improve the predictive performance of the algorithm. The $d$ parameter to decide whether two concepts are neighbors is set to $2$ . That means, when searching for neighbors of a concept, we just consider its siblings. For gBoost, we set the minimum support threshold $\textit{minsupp}=$ 5% for all datasets and search the optimal value of $\nu$ within a range of four values $\{$ 0.02, 0.04, 0.06, 0.08 $\}$ , where $\nu$ is the parameter for regularization. For CORK, we follow the setting in [31]. Note that in CORK, the minsupp value is adapted to the number of remaining graphs at each iteration so that subgraphs with low frequencies can also be mined. We use 10-fold cross-validation for classification. Experiments are measured on a 3.2 GHz Intel Core 2 Duo CPU with 2GB of RAM, running Ubuntu 14.04.

Table 2

Training time comparison of LGC, aLGC, and gBoost

Dataset	gBoost (seconds)	LGC (seconds)	aLGC (seconds)
AIDS	614	226	137
DD	6,473	2,725	1,634
NCI1	822	267	174
NCI33	840	235	132
NCI330	912	279	143
NCI41	606	179	112
PTC (MR)	17	13	11

Figure 4.

Classification accuracies.

Figure 5.

Classification AUC values.

For measurement, we use accuracy (ACC) as the performance measurement in our experiments because accuracy is an effective metric to assess the algorithm performance for balanced datasets. For better comparing the algorithms we also use the area under the ROC curve (AUC) [22]. The ACC values are shown in Fig. 4 and the AUC values are shown in Fig. 5. The standard deviations for all datasets except for PTC are less than 3% for all the algorithms. For the PTC dataset, standard deviations are larger, between 6% to 8%. As can be seen in the figures, LGC, aLGC and gBoost outperform CORK, both in accuracy and in AUC, for all the tested datasets. This result shows the advantage of boosting-based approaches over the greedy feature selection approach based on submodular quality criterion adopted by CORK. aLGC and gBoost give almost similar results on four cancer datasets, however aLGC gives better results on AIDS, DD and PTC datasets. LGC outperforms both aLGC and gBoost in ACC and in AUC, although the differences are not very large except for DD and PTC datasets. The result is encouraging and shows the effectiveness of selected features of co-occurrence subgraphs of our methods.

Next, we evaluate the runtime efficiency of the algorithms by comparing their training time. Table 2 shows the runtimes of LGC, aLGC and gBoost. We do not report the training times of CORK because the current release of CORK requires very long running time on tested datasets, especially on the Dobson and Doig (DD) dataset. As can be seen in the table, both LGC and aLGC are much faster than gBoost, an efficient global inductive method, on all four datasets. Since LGC, aLGC and gBoost all use the set of subgraph patterns generated by a mining algorithm for the learning purpose, their runtime behaviors are mainly determined by the used mining algorithm. As discussed previously gBoost takes longer time since it needs to call the mining algorithm multiple times with a low value of minsupp in order to obtain a good predictive rule set. LGC also calls the mining algorithm multiple times, however, the first call of the mining algorithm to build the iceberg lattice consumes most of the running time, other calls run on a very small dataset that is the graph set of the extent of optimal concepts with high value of minsupp (100% of the set size). aLGC is fastest because it calls the mining algorithm just once.

Figure 6.

Varying minimum support thresholds – accuracy values.

Both LGC and aLGC are approximate algorithms and their performances depend on the size of the iceberg lattice, but to different extents. We test the performance of LGC and aLGC with difference values of minsupp to see how the prediction performance changes as minsupp increases. Figure 6 reports the test results on the NCI1 dataset. From the figure, we can see that accuracy values of aLGC algorithm decrease as minsupp increases from 5% to 13% in all datasets. Accuracy values of the LGC algorithm also decrease as minsupp increases but not as much as those of aLGC. However, we observe here that for both LGC and aLGC, accuracy decreases more at higher values of minsupp. This manifests the approximate nature of our proposed approach.

6. Conclusion

We have proposed in this paper a method for finding a set of classification rules for connected, node-and-edge-labeled, undirected graphs. Optimal rules are found based on the Confidence-rated Boosting method. The searching space is limited to the formal concept lattice constructed from the training graphs. The proposed approximation methods exploit the partial order among sets of subgraphs to accelerate the optimal rule finding process in each round of boosting. Experimental results show that the proposed methods achieve equal or better classification accuracy when compared to two state-of-the-art algorithms while saving considerable training time. For future work, we plan to utilize the minimal graph generators of the equivalent classes found in the lattice to construct rules which may results in rules of more generalization power.

Footnotes

Acknowledgments

This research is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant 102.05-2013.37.

References

Acosta-Mendoza

Alonso

A.G.

and Medina-Pagola

J.E.

, Frequent approximate subgraphs as features for graph-based image classification, Knowledge-Based System 27 (2012), 381–392.

Borgwardt

K.M.

and Kriegel

H.P.

, Shortest-path kernels on graphs, In DM-05, 2005, pp. 74–81.

Bringmann

Zimmermann

Raedt

L.D.

and Nijssen

, Don’t be afraid of simpler patterns, In 10th European Conference on Principles and Practice of Knowledge Discovery in Databases PKDD, 2006, pp. 55–66.

Bunke

and Shearer

, A graph distance metric based on the maximal common subgraph, Pattern Recognition Letters 19 (1998), 255–259.

Cohen

W.W.

and Singer

, A simple, fast, and effective rule learner, In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 1999, pp 335–342.

Davey

and Priestley

, Introduction to lattices and order, Cambridge University Press, 2 edition, 2002.

Demiriz

Bennett

and Shawe-Taylor

, Linear programming boosting via column generation, Machine Learning 46(1–3) (2002), 225–254.

Deshpande

Kuramochi

and Karypis

, Frequent sub-structure-based approaches for classifying chemical compounds, In ICDM-03, 2003, pp. 35–42.

Dobson

P.D.

and Doig

A.J.

, Distinguishing enzyme structures from non-enzymes without alignments, Journal of Molecular Biology 330(4) (2003), 771–783.

10.

Fei

and Huan

, Structured sparse boosting for graph classification, ACM Trans. Knowl. Discov. Data 9(1) (2014), 1–22.

11.

Freund

and Schapire

R.E.

, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences 55(1) (1997), 119–139.

12.

Ganter

and Wille

, Formal Concept Analysis, Mathematical Foundations. Springer, 1998.

13.

Gärtner

Flach

and Wrobel

, On graph kernels: hardness results and efficient alternatives, In COLT-03, 2003, pp. 129–2003.

14.

Gartner

Flach

and Wrobel

, On graph kernels: Hardness results and efficient alternatives, In Learning Theory and Kernel Machines, volume 2777, 2003, pp. 129–143.

15.

Gonzalez

J.A.

Holder

L.B.

and Cook

D.J.

, Graph-based relational concept learning, In Proceedings of the Nineteenth International Conference on Machine Learning, 2002, pp. 219–226.

16.

Ichigaku

and Hisorhi

, Graph mining: procedure, application to drug discovery and recent advances, Drug Discovery Today 18(1–2) (2013), 50–57.

17.

Jin

Young

and Wang

, Graph classification based on pattern co-occurrence, In Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM ’09, 2009, pp. 573–582.

18.

Kashima

Tsuda

and Inokuchi

, Marginalized kernels between labeled graphs, In Proceedings of the Twentieth International Conference on Machine Learning, 2003, pp. 321–328.

19.

Kong

Fan

and Yu

P.S.

, Dual active feature and sample selection for graph classification, In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11, 2011, pp. 654–662.

20.

Kong

and Yu

P.S.

, Semi-supervised feature selection for graph classification, In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, 2010, pp. 793–802.

21.

Kudo

Maeda

and Matsumoto

, An application of boosting to graph classification, In NIPS 2004, 2004, pp. 729–736.

22.

Ling

C.X.

Huang

and Zhang

, Auc: A better measure than accuracy in comparing learning algorithms, In Proceedings of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence, 2003, pp. 329–341.

23.

Mahé

Ralaivola

Stoven

and Vert

J.P.

, The pharmacophore kernel for virtual screening with support vector machines, Journal of Chemical Information and Modeling 46(5) (2006), 2003–2014.

24.

Monjardet

, The presence of lattice theory in discrete problems of mathematical social sciences why, Mathematical Social are Either Active or Inactive in a Screen for Anti-Cancer ActivitySciences 46(2) (2003), 103–144.

25.

Moonesinghe

H.D.K.

Valizadegan

Fodeh

S.J.

and Tan

, A probabilistic substructure-based approach for graph classification, In 19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2007), October 29–31, 2007, Patras, Greece, Volume 1, 2007, pp. 346–349.

26.

Nguyen

V.A.

and Yamamoto

, Learning from graph data by putting graphs on the lattice, Expert Systems with Applications 39(12) (2012), 11172–11182.

27.

Ralaivola

Swamidass

S.J.

Saigo

and Baldi

, Graph kernels for chemical informatics, Neural Networks 18(8) (2005), 1093–1110.

28.

Ramon

and Gärtner

, Expressivity versus efficiency of graph kernels, In Workshop on Mining Graphs, Trees and Sequences, 2003, pp. 65–74.

29.

Saigo

Nowozin

Kadowaki

Kudo

and Tsuda

, gBoost: A mathematical programming approach to graph classification and regression, Machine Learning 75(1) (2009), 69–89.

30.

Tang

and Liu

, Graph mining applications to social network analysis, In Managing and Mining Graph Data, volume 40 of Advances in Database Systems, 2010, pp. 487–513.

31.

Thoma

Cheng

Gretton

Han

Kriegel

Smola

Song

Yan

and Borgwardt

, Near-optimal supervised feature selection among frequent subgraphs, In SDM-09, 2009.

32.

Wale

Watson

I.A.

and Karypis

, Comparison of descriptor spaces for chemical compound retrieval and classification, Information System 14(3) (2008), 347–375.

33.

Wallis

W.D.

Shoubridge

Kraetz

and Ray

, Graph distances using graph union, Pattern Regcognition Letters 22 (2001), 701–704.

34.

Yan

Cheng

Han

and Yu

P.S.

, Mining significant graph patterns by leap search, In ICMD-08, 2008, pp. 433–444.

35.

Yan

and Han

, gSpan: graph-based substructure pattern mining, In ICDM-02, 2002, pp. 721–724.

36.

Yan

and Han

, Closegraph: Mining closed frequent graph patterns, In KDD-03, 2003, pp. 286–295.

37.

Zhao

Kong

and Yu

P.S.

, Positive and unlabeled learning for graph classification, In Proceedings of the 2011 IEEE 11th International Conference on Data Mining, ICDM ’11, 2011, pp. 962–971.

An efficient heuristic approach for learning a set of composite graph classification rules

Abstract

Keywords

1. Introduction

2. Finding optimal graph classification rules

.

.

4.1 Stopping criterion

Table 1 Several statistics of the used datasets

Footnotes

Acknowledgments

References

Table 1
Several statistics of the used datasets