In this paper, we introduce a modi cation of the lazy associative classi cation which addresses the graph classi cation problem. To deal with intersections of large graphs, graph intersections are approximated with all common subgraphs up to a xed size similarly to what is done with graphlet kernels. We illustrate the algorithm with a toy example and describe our experiments with a predictive toxicology dataset.
Classi cation methods for data given by graphs usually reduce initial graphs
to numeric representation and then use standard classi cation approaches, like
SVM [
The rest of the paper is organized as follows. In Section 2, we give main de nitions on labeled graphs, pattern structures, and lazy associative classi cation. In Section 3, we consider an example. In Section 4, we discuss the results of computational experiments on PTC dataset. In Section 5, we give the conclusion and discuss directions of further research.
In this section, we give the de nitions of the main concepts used in the paper. 2.1
First, we recall some standard de nitions related to labeled graphs, see
e.g. [
Undirected graph is a pair G = (V; E). Set V is referred to as a set of nodes of a graph. Set E = ffv; ug j v; u 2 V g [ E0, a set of unordered elements of V , is called a set of edges, and E0 V | is a set of loops. If E0 = ;, then G is called a graph without loops.
Graph H = (VH ; EH ) is called a subgraph of graph G = (VG; EG), if all nodes and edges of H are at the same time nodes and edges of G correspondingly, i.e. VH VG and EH EG.
Graph H = (VH ; EH ) is called an induced subgraph of graph G = (VG; EG), if H is a subgraph of G, and edges of H are comprised of all edges of G with both nodes belonging to H.
Given sets of nodes V , node labels LV , edges E, and edge labels LE , a labeled graph is de ned by a quadruple G = ((V; lv); (E; le)) such that { lv V LV is the relation that associates nodes with labels, i.e., lv is a set of pairs (vi; li) such that node vi has label li, { le V V LE is the relation that associates edges with labels, i.e., le is a set of triples (vi; vj ; lij ) such that edge (vi; vj ) has label lij .
Example 1. A molecule structure can be represented by a labeled graph.
NH12 C3
CH23
C4 OH5
Cl6
Here V = f1; 2; 3; 4; 5; 6g, E = f(1; 3); (2; 3); (3; 4); (4; 5); (4; 6)g, lv = f(1; N H2); (2; CH3); (3; C); (4; C); (5; OH); (6; Cl)g, le = f(1; 3; 1); (2; 3; 1); (3; 4; 2); (4; 5; 1); (4; 6; 1)g, and edge type 1 corresponds to a single bond (ex. HN2|C) while edge type 2 { to a double bond (ex. C = C).
A labeled graph G1 = ((V1; lv1); (E1; le1)) dominates a labeled graph G2 = ((V2; lv2); (E2; le2)) with given order (e.g. natural, lexicographic) on vertex and edge labels, or G2 G1 (or G2 is a subgraph of G1), if there exists an injection ' : V2 ! V1 such that it: { respects edges: (v; w) 2 E2 ) ('(v); '(w)) 2 E1, { ts under labels: lv2(v) lv1('(v)); (v; w) 2 E2 ) le2(v; w) le1('(v); '(w)).
Two labeled graphs G1 and G2 are called isomorphic (G1 ' G2) if G1 and G2 G1.
G2
C4 Cl5
NH62
C4 CH53
OH6
An injective function f : V ! V 0 is called a subgraph isomorphism from G to G0, if there exists a subgraph of G0: S G0, such that f is a graph isomorphism from G to S, or G ' S.
CH13 C3 OH2
C4
NH62
G2 :
NH12 C3 Cl2
C4 CH53
OH6 G1 is subgraph-isomorphic to G2.
Given labeled graphs G1 and G2, a set G1 u G2 = fG j G G1; G2; 8G G1; G2 G 6 Gg is called a set of maximal common subgraphs of graphs G1 and G2. We also refer to G1 u G2 as to intersection of graphs G1 and G2, and to u { as to similarity operator de ned on graphs. 8> NH2 > > > Example 4. <> > > >>>: OH
C C
Cl
CH3 >>>>>=9 ><>>>8> CH3 > u > >>>>; >>>>: NH2
C C
OH 9> 8> NH2 >>> >>> => = <> OH >>>>>; >>>>>: OH
C CH3 C ;
C C 9 > > > > > = > > OH >>>;
For sets of graphs G = fG1; : : : ; Gkg and H = fH1; : : : ; Hng the similarity operator is de ned in the following way:
G u H = MAX fGi u Hi j Gi 2 G; Hj 2 Hg
Given sets of labeled graphs G1 and G2, we say that a set of graphs G1 is subsumed by a set of graphs G2, or G1 v G2, if G1 u G2 = G1. 2.2
De nition 1. A labeled graph g is called a k-graphlet of a labeled graph G if
g is a connected induced subgraph of graph G with k nodes [
De nition 2. A set of labeled graphs Gk is called a k-graphlet representation of a labeled graph G if any g 2 G is a unique (up to subgraph isomorphism) kgraphlet of graph G, i.e 8g 2 Gk graph g is a k-graphlet of G, 8g1; g2 2 G one does not have g1 g2. De nition 3. k-graphlet distribution of a labeled graph G is the set f(gi; ni)g, where gi is a k-graphlet of G and ni is the number of k-graphlets in G isomorphic to gi.
CH3 H
OH H OH G1 = fC C = C; C C H; C = C H; C C Cg, G2 = fC C = C; C C H; C = C H; C C O; C = C O; C O Hg { are 3-graphlet representations of graphs G1 and G2 correspondingly (with benzene rings comprised of carbon molecules C). 3-graphlet distributions of graphs G1 and G2 are given in Table 1.
Graphlets were introduced in biomedicine and are used to compare real
cellular networks with their models. It is easy to demonstrate that two networks are
di erent by simply showing a short list of properties in which they di er. It is
much harder to show that two networks are similar, as it requires demonstrating
their similarity in all of their exponentially many properties [
Graphlet distribution serves as a measure of network local structure
agreement and was shown to express more structural information than other metrics
such as centrality, local clustering coe cient, degree distribution etc. In [
De nition 4. Let G be a set (of objects), let (D; u) be a meet-semi-lattice (of
all possible object descriptions) and let : G ! D be a mapping between objects
and descriptions. Set (G) := f (g)jg 2 Gg generates a complete subsemilattice
(D ; u) of (D; u), if every subset X of (G) has in mum uX in (D; u).
Pattern structure is a triple (G; D; ), where D = (D; u), provided that the
set (G) := f (g) j g 2 Gg generates a complete subsemilattice (D ; u) [
subsumption relation v: given c; d 2 D one has c v d , c u d = c. Operation u is also called a similarity operation. A pattern structure (G; D; ) gives rise to the following derivation operators ( ) :
A = l (g) g2A
for A 2 G; d = fg 2 G j d v (g)g for d 2 (D; u):
pattern concepts of (G; D; ).
G; d 2 D; A = d, and A = d are called Example 6. Let f1; 2; 3g be a set of objects, fG1; G2; G3g { be a set of their descriptions (i.e., graph representations):
G1 :
C
C CH3
NH2
NH2
OH
NH2
OH C
C
D is the set of all sets of labeled graphs, u is a graph intersection operator, D = (D; u). A set of objects (graphs) f1; 2; 3g, their \descriptions" (i.e. graphs themselves) D = fG1; G2; G3g ( (i) = Gi; i = 1; : : : ; 3), and similarity operator u comprises a pattern structure (f1; 2; 3g; D; ). f1; 2; 3g = fN H2 C = Cg, because fN H2 C = Cg is the only graph, subgraph-isomorphic to all three graphs 1; 2, and 3. Likewise,
C = Cg = f1; 2; 3g, because graphs 1; 2, and 3 subsume graph fN H2 fN H2 C = Cg. f1; 2g = fCH3 C = C N H2g, because fCH3 C = C N H2g is a graph, subgraph-isomorphic to 1, and 2, but not to graph 3. Likewise, fCH3 C = C N H2g = f1; 2g, because only graphs 1, and 2 subsume graph fCH3 C = C N H2g, but graph 3 does not.
Here is the set of all pattern concepts for this pattern structure: f f1; 2; 3g ;
NH2 C f2; 3g ;
NH2 C!
OH! C
Cl
C ; f1; 2g ;
CH3 C
! C
NH2 ; f1; 3g ;
NH2 C
C
NH2 ! ; ; (1; fG1g) ; (2; fG2g) ; (3; fG3g) ; (;; fG1; G2; G3g) g:
For some pattern structures (e.g., for the pattern structures on sets of graphs
with labeled nodes) even computing subsumption of patterns may be NP-hard.
Hence, for practical situations one needs approximation tools, which would
replace the patterns with simpler ones, even if that results in some loss of
information. To this end, we use a contractive monotone and idempotent mapping
: D ! D that replaces each pattern d 2 D by (d) such that the pattern
structure (G; D; ) is replaced by (G; D; ). Under some natural algebraic
requirements that hold for all natural projections in particular pattern
structures we studied in applications, see [
Consider a binary classi cation problem with a set of positive examples G+, negative examples G , test examples Gtest, and a pattern structure (G+ [ G ; D; ) de ned on the training set.
De nition 6. A pattern h 2 D is a positive premise i [
= ; and h \ G+ 6= ;
A positive premise is a subset of the least general generalization of descriptions
of positive examples, which is not contained in (does not cover) any negative
example. A negative premise is de ned similarly. Various classi cation schemes
using premises are possible, as an example consider the following simplest scheme
from [
lem is an association rule in a form h ! f+; g, where h is a positive or negative premise, respectively.
The de nition means that for a binary graph classi cation problem, for
instance, we can mine classi cation association rules in a form fgig ! f+; g,
i.e. if a test graph subsumes a subgraph gi, that is common only to positive
(negative) training examples, it is therefore classi ed as positive (negative). We
elaborate this idea in the next subsection. As there might be lots of such CARs,
we might come up with a single classi cation rule taking into account these
CARs. For instance, we can count all positive and negative CARs for each test
object and classify it with a majority voting procedure. Of course, the idea is
easily generalized to multi-label classi cation problem. The described classi cation
schemes are explored in [
Another advantage of the lazy classi cation framework is its obvious parallelization. Suppose there are K processors. If we consider classi cation of an unlabeled object we can divide the training set into K separate subsets. Then, for each subset we perform intersections between the labeled objects with the unlabeled one to be classi ed. After all unfalsi ed intersections are found we can go on to the classi cation phase which involves voting based on those intersections.
In this subsection, we combine the ideas of pattern structures and their projections, graphlets, and lazy associative classi cation, and introduce our algorithm. First, we recall the de nition of k-projection producing all graphs with less than or equal to k nodes.
De nition 8. Given a graph pattern structure (G; D; ), we call k(G) = fHi = ((Vi; lvi); (Ei; lei)) j Hi G; Hi is connected; jVij kg a k-projection, de ned for graph descriptions G.
Obviously, this operator is a projection, i.e. contractive, monotone, and idempotent function.
De nition 9. Given a graph pattern structure (G; D; ), k-graphlet derivation operator k = S1 l k l takes an object g described by graph G and produces all l-graphlets of G for l = 1; : : : k.
Example 7. For object 1 with \graph description" G1 from example 5 3(1) is the set of all 1-,2-, and 3-graphlets of graph 1: 3(1) = fC; H; C C; C = C; C H; C C = C; C C H; C = C H; C C Cg. To clarify, here (1) = fG1g; 3(1) = 3( (1)) = 3(G1) = fHi = ((Vi; lvi); (Ei; lei)) j Hi G1; jVij 3g.
De nition 10. Given k-graphlet representations G1k and G2k of labeled graphs G1 and G2, the intersection G1 uk G2k is called k-graphlet intersection of G1 k and G2. The uk operator is further called k-graphlet similarity operator. Example 8. For graphs 1 and 2 with \graph descriptions" G1 and G2 from example 5 G1 u3 G2 = fC; H; C C; C = C; C H; C C = C; C C H; C = C Hg is the set of all common 1-, 2-, and 3-graphlets of graphs 1 and 2.
Here are the main steps of our algorithm: 1. All k-graphlet intersections of test examples and positive training examples are computed: h+ = Gtr uk G+; 2. Each intersection h+ is tested on subsumption by negative training examples.
If some of them subsumes h+, then this intersection is falsi ed. Otherwise, h+ gives a vote for positive classi cation of the test example Gtr; 3. The same procedure is done for each intersection of Gtr with negative examples; 4. Test example Gtr is classi ed according to the weighted majority rule where each unfalsi ed intersection is given a weight equal to its cardinality (the cardinality of the corresponding set of graphs).
We illustrate the principle of our method with a toy example. Let us consider the following training and test sets comprised of molecular descriptions of toxic (G1 { G4) and non-toxic (G5 { G7) chemical compounds. The task is to build a discriminative classi er able to determine whether the objects from the test set (G8 G11) are toxic or not. The main steps of the algorithm, described in the previous section, are brie y illustrated with Tables 2 and 3. First, we build 3-graphlet intersections of test and training examples (we use only graphlets with 3 nodes for the purpose of illustration). Then, a \+" or \|" sign with cardinality of intersection is put in Table 3 if this intersection is not subsumed by any example of the opposite class. Otherwise, the counter-example subsuming this intersection is given.
Positive examples:
A C B A C B A C B A C E G1 : G5 : G8 :
D D Negative examples:
A C D
D D Test examples:
A C B
G2 : G6 :
G9 : C C C
A A
B B
C C C C C
D D
E D
G3 : G7 : G10 :
B
A D A
C C C C C
G4 : E E
D D
B
E C
A G11 :
C C
B
D E B E D E A D 3-graphlet intersections of training and test examples are given in Table 2. For instance, graphs G1 and G8 have 4 common 3-graphlets: A{C{B, A{C=C, B{ C=C, and C=C{D. In this simple case, we do not di erentiate between a single and a double bond (e.g., ACC here stands for A{C=C without ambiguity).
Further, Table 3 summarizes the procedure. For instance, a '+4' sign for graphs G1 and G8 means that all common 3-graphlets of G1 and G8 (i.e., A{C{ B, A{C=C, B{C=C, and C=C{D) are not subgraph-isomorphic to any of the negative examples G5 { G7 altogether at the same time. Thus, this intersection \gives a vote" of weight 4 (the cardinality of the mentioned set of graphlets) for positive classi cation of G8. On the contrary, all common 3-graphlets of G4 and G8 (A{C=C, B{C=C, and C=C{E) are altogether subgraph-isomorphic to negative example G6, therefore, the intersection of G4 and G8 doesn't \give a vote" for positive classi cation of G8.
Thus, molecules G8 and G11 are classi ed as toxic, G9, G10 are classi ed as non-toxic. 4
The proposed algorithm was tested with the 2001 Predictive Toxicology
Challenge dataset in comparison with SVM with graphlet kernel and
k-NearestNeighbor with graphlet-based Hamming distance. SVM classi ers are considered
to be good benchmarks for graph classi cation problem [
The training set is comprised of 417 molecular graphs of chemical compounds with indication of whether a compound is toxic or not for a particular sex and species group out of four possible groups: fmice, ratsg fmale, femaleg. Thus, 4 separate sets were built for male rats (MR, 274 examples, 117 are toxic for male rats, 157 are non-toxic), male mice (MM, 266 examples, 94 are positive, 172 are negative), female rats (FR, 281 examples, 86 are positive, 195 are negative) and female mice (FM, 279 examples, 108 are positive, 171 are negative).
We run 5-fold cross-validation for each group (MR, MM, FR, FM) and compared average classi cation metrics for each fold. The results for male rats are presented in Table 4 (we got similar results for other groups).
The parameters for SVM and kNN classi ers were tuned through the process of GridSearch cross-validation2. The 'K nodes' parameter determines the maximum number of nodes in graphlet representation of graphs, i.e. when it is equal to 4, all graph are approximated with their 4-graphlet representation, or all unique (in the sense of isomorphism) graphlets with up to 4 nodes.
As we can observe, graphlet-based lazy associative classi cation is reasonable with at least 3-graphlet descriptions. In case of 2-graphlet descriptions the 2 http://scikit-learn.org/stable/modules/grid\_search.html algorithm often refuses to classify test objects, because 2-graphlet intersections of positive and test objects are falsi ed by negative objects and vice versa. But 3-graphlet descriptions are optimal for this method as the model is probably over tted in case of 4- and 5-graphlet descriptions. 5
In this paper, we have proposed an approach to graph classi cation based on the combination of graphlets, pattern structures and lazy classi cation. The key principle of lazy classi cation is that one does not have to produce the whole set of classi cation rules whatever they are. Instead, one generates those rules that allow one to classify the current test object. The framework favors the complex structure of objects as soon as the algorithm does not require a training phase.
We have carried out a number of experiments in molecule classi cation within the proposed lazy classi cation framework. We compared classi cation performance of our method and SVM with graphlet kernel and KNN with graphletbased distance. The reason for such a choice is that SVM classi ers are considered to be good benchmarks for graph classi cation problem, while kNN is a famous lazy classi cation method.
In our experiments graphlet-based lazy classi cation - following the same learning curve as the other methods - shows better classi cation performance compared to the classical methods in case of molecule toxicology prediction problem. Further, we plan to investigate the over tting problem for our algorithm, in particular, the dependency of classi cation metrics on the number of considered nodes in graphlets. Other types of descriptions and a parallel version of our algorithm are also promising directions of study.