A Graph Kernel Based on the Jensen-Shannon Representation Alignment

1 Introduction

There have been many successful attempts to classify or cluster graphs using graph kernels [G¨artner et al., 2003; Jebara et al., 2004; Barra and Biasotti, 2013; Harchaoui and Bach, 2007]. The main advantage of using graph kernels is that they characterize graph features in a high dimensional space and thus better preserve graph structures. A graph kernel is usually defined in terms of a similarity measure between graphs. Most of the recently developed graph kernels are instances of the family of R-convolution kernels proposed by Haussler [Haussler, 1999], which provide a generic way of defining graph kernels by comparing all pairs of isomorphic substructures under decomposition, and a new decomposition will result in a new graph kernel. Generally speaking, the R-convolution kernels can be categorized into the following classes, namely graph kernels based on comparing all pairs of a) walks (e.g., the random walk kernel [Jebara et al., 2004]), b) paths (e.g., the shortest path kernel [Borgwardt and Kriegel, 2005]), c) cycles (e.g., the backtracless kernel from the cycles identified by the Ihara zeta function [Aziz et al., 2013]), and d) subgraph or subtree structures (e.g., the subgraph or subtree kernel [Costa and Grave, 2010; Shervashidze et al., 2011]).

∗This work is supported by the National Natural Science Foundation of China (61402389 and 61272398). Edwin R. Hancock is supported by a Royal Society Wolfson Research Merit Award.

†Primary Author: bailu69@hotmail.com; lu@cs.york.ac.uk

‡Corresponding Author: zhihong@xmu.edu.cn.

One drawback arising in the R-convolution kernels is that they neglect the relative locations of substructures. This occurs when an R-convolution kernel adds an unit value to the kernel function by roughly identifying a pair of isomorphic substructures. As a result, the R-convolution kernels cannot establish reliable structural correspondences between the substructures. This drawback limits the precise kernel-based similarity measure for graphs.

To overcome the shortcomings of existing R-convolution kernels, we propose a novel matching kernel by aligning JS representations of vertices, which are computed based on the JSD measure [Bai et al., 2012; Bai and Hancock, 2013] between DB representations [Bai and Hancock, 2014] of graphs. The main advantages of using DB representations and the JSD measure are twofold. First, in the literature [Crutchfield and Shalizi, 1999; Escolano et al., 2012; Bai and Hancock, 2014], DB representations of graphs are powerful tools for characterizing graphs in terms of complexity measures and reflect rich depth characteristics of graphs. Second, in the litearturethe [Bai et al., 2012; Bai, 2014], the JSD measure of graphs can not only reflect the information theoretic (dis)similarities between entropies of graphs but can also be efficiently computed for a pair of large graphs. As a result, the DB representation and the JSD measure provide us an elegant way of defining new effective graph kernels.

To compute the new matching kernel, for each graph under comparison, we commence by computing the h-layer DB representation of each vertex, that has been previously introduced in [Bai et al., 2014a]. Moreover, we determine a m-sphere (i.e., a vertex set) for each vertex by selecting the vertices that have the shortest path length m to the vertex.

We compute a new m-layer JS representation for each vertex by measuring the JSD between the h-layer DB representations of the vertex and the vertices from its m-sphere. The m-layer JS representation rooted at a vertex not only encapsulates a high-dimensional entropy-based depth information for the vertex, but also reflects the co-relation between the vertex and its m-sphere vertices (i.e., the JS representation reflects richer characteristics than the original DB representation). Based on the new JS representations for two graphs we develop a new vertex matching strategy by aligning the JS representations. Finally, we compute the new kernel, namely the JS matching kernel, for graphs by counting the number of matched vertex pairs. We theoretically show the relationship between our kernel and the classical all subgraph kernel and explain the reason for the effectiveness of our kernel. Our JS matching kernel can be seen as an aligned subgraph kernel that counts the number of aligned isomorphic subgraph (i.e., the local information graph [Dehmer and Mowshowitz, 2011]) pairs which are correspond by the corresponding aligned JS representations. Our kernel thus overcomes the mentioned shortcoming of neglecting the structural correspondence information between substructures that arises in R-convolution kernels. Furthermore, compared to the DB matching kernel that is computed by aligning the h-layer DB representations [Bai, 2014; Bai et al., 2014a], our kernel not only reflects richer characteristics but also identifies more pairs of isomorphic subgraphs that encapsulate the structural correspondence information. We empirically demonstrate the effectiveness of our new kernel on graphs from computer vision datasets.

2 VertexMatching using JS Representations

In this section, we define a JS representation for a vertex and a vertex matching method by aligning the representations.

2.1 The JSDMeasure for Graphs

In this work, we require the JSD measure for graphs. In mutual information, the JSD is a dissimilarity measure for probability distributions in terms of the entropy difference associated with the distributions [Martins et al., 2009]. In [Bai and Hancock, 2013; Bai et al., 2012], Bai et al. have extended the JSD measure to graphs for the purpose of computing the JSD based information theoretic graph kernels. In their work, the JSD between a pair of graphs is computed by measuring the entropy difference between the entropies of the graphs and those of a composite graph (e.g., the disjoint union graph [Bai et al., 2012]) formed by the graphs. In this subsection, we generalize their work in [Bai et al., 2012] and give the concept of measuring the JSD for a set of graphs. Let G = {Gn|n = 1, 2, . . . ,N} denote a set of N graphs, and Gn(Vn,En) is a sample graph in G with vertex set Vn and edge set En. The JSD measure D for the set of graphs G is

where HS(Gn) is the Shannon entropy for Gn associated with steady state random walks [Bai and Hancock, 2013] and

where PGn (v) = Dn(v, v)/ ∑u∈V Dn(u, u) is the probability of the steady state random walk visiting the vertex v ∈ Vn, and D is the diagonal degree matrix of Gn. Moreover, in Eq.(1) GDU is the disjoint union graph formed by all the graphs in G, and HS(GDU) is the Shannon entropy of the union graph. Based on the definition in [K¨oner, 1971], the entropy of the disjoint union graph is defined as

where |Vn| is the number of vertices of Gn. Eq.(1) and Eq.(3) indicate that the JSD measure for a pair of graphs can be directly computed from their vertex numbers and entropy values. Thus, the JSD measure can be efficiently computed.

2.2 The JS Representation through the JSD

In this subsection, we compute a m-layer JS representation around a vertex for a graph. To commence, we first review the concept of the h-layer DB representation around a vertex. This has been previously introduced by Bai et al. [Bai et al., 2014a], by generalizing the DB complexity trace around the centroid vertex [Bai and Hancock, 2014]. For an undirected graph G(V,E) and a vertex v ∈ V , let a vertex set N K v be defined as N K v = {u ∈ V | SG(v, u) ≤ K}, where SG is the shortest path matrix of G and SG(v, u) is the shortest path length between v and u. For G, the K-layer expansion subgraph GK v (V K v ; E K v ) around v is

For the graph G, the h-layer DB representation around v is

where (K ≤ h), GK v is the K-layer expansion subgraph around v, and HS(GK v ) is the Shannon entropy of GK v and is defined in Eq.(2). Note that, if Lmax is the greatest length of the shortest paths from v to the remaining vertices and K ≥ Lmax, the K-layer expansion subgraph is G itself.

Clearly, the h-layer DB representation DBhG(v) reflects an entropy-based information content flow through the family of K-layer expansion subgraphs rooted at v, and thus can be seen as a vectorial representation of v.

The m-layer JS representation: For the graph G(V, E) and the vertex v ∈ V , we define the m-sphere (i.e., a vertex set) around v as ˆN m v = {u ∈ V | SG(v, u) = m} (note that, ˆN m v is different from N K v , even if m = K), based on the definition in [Dehmer and Mowshowitz, 2011]. The JSD for the h-layer DB representations of v and the vertices in ˆN K v is

where GKˆN m v is a graph set and consists of the K-layer expansion subgraphs around v and the vertices in ˆN m v . Them-layer JS representation around the vertex v is

Note that, the dimension of J m G (v) is equal to that of DBhG(v), i.e., J m G (v) is a h dimensional vector. This can be observed from Eq.(5), Eq.(6) and Eq.(7). ✷ Discussions: Compared to the h-layer DB representation DBhG(v), the m-layer JS representation J (m;h) G (v) not only reflects the information content (i.e., the entropy) flow rooted at the vertex v relying on DBhG(v), but also encapsulates the entropy-based dissimilarity information (or the relationship) between the h-layer DB representation of v and that of the vertices in ˆN m v in terms of the JSD measure D(m;h) G (v). In other word, for each vertex the m-layer JS representation reflects richer characteristics than its original h-layer DB representation. This can be observed from Eq.(7). Moreover, based on the definition proposed by Dehmer and Mowshowitz in [Dehmer and Mowshowitz, 2011], the shortest paths departing from v to the vertices in ˆN m v can be used to form a local information graph LG(v,m) rooted at v. Since LG(v,m) is encompassed or determined by the m-sphere ˆN m v around v, the vertex v and its m-sphere play a crucial role of generating LG(v,m). As a result, the m-layer JS representation J (m;h) G (v) can also be seen as a vectorial signature for the local information graph LG(v,m). Details of local information graphs can be found in [Dehmer and Mowshowitz, 2011].

2.3 VertexMatching from the JS Represenations

We propose a new vertex matching method, namely the JS matching method, for a pair of graphs by aligning their JS representations of vertices. Our matching method is similar to that previously introduced by Scott et al. in [Scott and Longuett-Higgins, 1991] for point set matching, that computes an affinity matrix in terms of the distances between points. For a pair of graphs Gp(Vp,Ep) and Gq(Vq,Eq), we use the m-layer JS representations J (m;h) Gp (vi) and J (m;h) Gq (uj), that are computed from the corresponding hlayer DB representations, as the point coordinates for the vertices vi ∈ Vp and uj ∈ Vq, respectively. For Gp and Gq, we compute the Euclidean distance between J (m;h) Gp (vi) and J (m;h) Gq (uj) as the element R(m;h) (i, j) of their affinitymatrix R(m;h) , and R(m;h) (i, j) is defined as

where R(m;h) is a |Vp| × |Vq| matrix, and the parameters m and h indicate that the affinity matrix is computed from the m-layer JS representation over the h-layer DB representation. R(m;h) (i, j) represents the distance or dissimilarity between the vertex vi in Gp and the vertex uj in Gq. Furthermore, for the affinity matrix R(m;h) , the rows index the vertices of Gp, and the columns index the vertices of Gq.

If R(m;h) (i, j) is the smallest element simultaneously in row i and in column j, moreover | ˆN m vi | = | ˆN m uj | ̸= 0 (i.e., the vertex number of the m-sphere around vi ∈ Vp is equal to that around uj ∈ Vq, and these vertex numbers also cannot be 0), there should be a one-to-one correspondence between the vertex vi of Gp and the vertex uj of Gq, i.e., vi and uj are matched. We record the state of correspondence using the correspondence matrix C (m;h) ∈ {0, 1}|Vp|×|Vq| that satisfies

Eq.(9) indicates that if C (m;h) (i, j) = 1, the vertices vi and vj are matched. Moreover, the condition | ˆN m vi | = | ˆN m uj | ̸= 0 for Eq.(9) guarantees that both of the m-spheres | ˆN m vi | and | ˆN m uj | are not empty vertex sets.

Note that, similar to the DB matching previously introduced by Bai et al. [Bai et al., 2014a], for a pair of graphs a vertex from a graph may have more than one matched vertices from the other graph. In our work, we propose to assign a vertex at most one matched vertex. One way to achieve this is to update the matrix C (m;h) by adopting the Hungarian algorithm [Munkres, 1957] that can solve the assignment problem, following the strategy proposed in [Bai et al., 2014a]. Here, the matrix C (m;h) ∈ {0, 1}|Vp|×|Vq| can be seen as the incidence matrix of a bipartite graph Gpq (Vp, Vq , Epq ), where Vp and Vq are the two sets of partition parts and Epq is the edge set. By performing the Hungarian algorithm on the matrix C (m;h) , we can assign each vertex from the partition part Vp or Vq at most one matched vertex from the other partition part Vq or Vp. Unfortunately, the Hungarian algorithm usually requires extra expansive computation and thus may lead to computational inefficiency for the JS matching. To address the inefficiency, an alternative way or strategy is to randomly assign each vertex an unique matched vertex through the correspondence matrix C (m;h) . In other words, for the correspondence matrix C (m;h) , from the first row and the first column, we will set each evaluating element of C (m;h) as 0 if there has been an existing element that is 1 either in the same row or the same column. Based on our evaluations, this strategy will not influence the effectiveness of our resulting kernel in Section 3, and the kernel using the strategy will be more efficient than that using the Hungarian algorithm.

3 AGraph Kernel from the JSMatching

In this section, we propose a new graph kernel from the JS vertex matching by aligning the JS representations of vertices.

3.1 The Jensen-ShannonMatching Kernel

Definition (The Jensen-Shannon matching kernel): Consider a pair of graphs as Gp(Vp,Ep) and Gq(Vq,Eq). Based on the definition of JS matching introduced in Section 2.3, we commence by computing the correspondence matrix C (m;h) . The JS matching kernel k(M;h) JSM , which aligns the m-layer JS

representations, for the graphs is

where M is the greatest value of the parameter m (i.e., m varies from 1 to M). Eq.(10) indicates that k(M;h) JSM (Gp,Gq) counts the number of matched vertex pairs between Gp and Gq over the M correspondence matrices C (m;h) . ✷

Lemma. The matching kernel k(M;h) JSM is positive definite (pd). Proof. Intuitively, the proposed JS matching kernel is pd because it counts pairs of matched vertices (i.e., the smallest subgraphs) over the M correspondence matrices C (m;h) . More formally, let the base counting kernel km be a function counting pairs of matched vertices between the graphs Gp and Gq from the correspondence matrix C (m;h) , and

where

where δ is the Dirac kernel, that is, it is 1 if the arguments are equal and 0 otherwise (i.e., it is 1 if a pair of vertices are matched and 0 otherwise). From the base counting kernel km, the JS matching kernel k(M;h) JSM can be re-written as

Eq.(11) indicates that the base counting kernel km is the sum of pd Dirac kernels and is thus pd. As a result, the kernel k(M;h) JSM summing the positive definite kernel km is pd. ■

3.2 Relation to the All Subgraph Kernel

The JS matching kernel can be re-defined in another manner that elucidates its advantage and effectiveness, compared to the all subgraph (AS) kernel. To commence, we review the definition of the AS kernel introduced in [Borgwardts, 2007]. Let Gp(Vp,Ep) and Gq(Vq,Eq) be a pair of graphs for the kernel computation. The AS kernel is defined as

where

Below, we re-define the JS matching kernel in a manner that is similar to the AS kernel. Based on the definition in Section 2.2, the m-layer JS representations around a vertex v ∈ Vp of Gp(Vp,Ep) and a vertex u ∈ Vq of Gq(Vq,Eq) are J (m;h) Gp (v) = Dm Gp (v) + DBhGp (v) and J (m;h) Gq (u) = Dm Gq (u) +DBhGq (u), respectively. According to the discussions in Section 2.2, each m-layer JS representation around a vertex can be seen as a vectorial signature of a local information graph, which is determined by the vertex and the msphere around the vertex. Based on the JS matching defined in Section 2.3, if the vertices v and u are matched, the two m-layer JS representations around the two vertices are close together in a corresponding principle space. Thus, the corresponding local information graphs LGp (v, m) around v ∈ Vp and LGq (u,m) around u ∈ Vq can be seen as approximate isomorphism, i.e., LGp (v,m) ≃ LGq (u,m). As a result, the JS matching kernel k(M;h) JSM can be re-written as

where

Here, the condition | ˆN m vi | = | ˆN m uj | ̸= 0 of Eq.(17) guarantees that the m-spheres ˆN m v and ˆN m u exist, i.e., the local information graphs LGp (v,m) and LGq (u,m) that are determined by the m-spheres exist. This is because an empty m-sphere cannot form a local information, more details can be found in [Dehmer and Mowshowitz, 2011].

Discussions: Through Eq.(14) and Eq.(17), we observe that both the kernels kAS and k(M;h) JSM need to identify any pair of isomorphic subgraphs. For kAS and k(M;h) JSM , each pair of isomorphic subgraphs pair will add an unit value to the kernel function, i.e., both the AS kernel and our JS matching kernel count the number of isomorphic subgraph pairs. However, we also observe that there are two significant differences between the AS kernel and the JS matching kernel. First, for the JS matching kernel, only the subgraphs (i.e., the local information graphs) around a pair of matched vertices that are determined by the vertices and the m-spheres around the vertices are evaluated with respect to be isomorphic. By contrast, for the AS kernel, any pair of subgraphs are evaluated for identifying the isomorphism. As a result, the JS matching kernel overcomes the NP-hard problem of measuring all possible pairs of subgraphs that arises in the AS kernel. Second, for the JS matching kernel, any pair of isomorphic local information graphs are identified by a pair of matched vertices and the m-spheres around the vertices. Thus, there is a locational correspondence between the isomorphic local information graphs (i.e., the corresponding subgraphs) with respect to the global graphs. By contrast, a pair of subgraphs having no location correspondence may also be seen as isomorphism by the AS kernel. The above observations indicate that our JS matching kernel is essentially an aligned subgraph kernel that counts the number of aligned isomorphic local information graph pairs, which are corresponded by the corresponding JS representations. Our kernel thus overcomes the shortcoming of neglecting the relative locations between substructures arising in the R-convolution kernels.

3.3 Discussions and RelatedWork

Clearly, the JS matching kernel is related to the DB representation defined in [Bai and Hancock, 2014]. However, there are two significant differences. First, the DB representation is computed by measuring the entropies of subgraphs rooted at the centroid vertex. The centroid vertex is identified by evaluating the minimum shortest path length variance to the remaining vertices. By contrast, in our work, we first compute the h-layer DB representation rooted at each vertex, and then compute the resulting m-layer JS representation. For a vertex, its m-layer JS representation is computed by summing its DB representation and the JSD measure between its DB representation and that of the vertices from its m-sphere. Second, in [Bai and Hancock, 2014] the DB representation from the centroid vertex is a vectorial signature of a graph, i.e., it can be seen as an embedding vector for the graph. Embedding a graph into a vector tends to approximate the structural correlations in a low dimensional space, and thus leads to information loss. By contrast, the JS matching kernel aligning the m-layer JS representation represents graphs in a high dimensional space and thus better preserves graph structures.

On the other hand, the DB matching kernel developed in [Bai et al., 2014a] is also related to the DB representation in [Bai and Hancock, 2014]. Moreover, similar to our JS matching kernel, the DB matching kernel can also better preserve graph structures by kernelizing the DB representation. However, unlike the JS matching kernel, this kernel is computed by aligning the h-layer DB representation rather than aligning the m-layer JS representation. According to the statement in Section 2.2, the m-layer JS representation for a vertex reflects richer characteristics than its original h-layer DB representation. As a result, the JS matching kernel can capture more information for graphs than the DB matching kernel. Moreover, Bai [Bai, 2014] also demonstrates the relationship between the DB matching kernel and the AS kernel. The DB matching kernel can also be re-defined as a manner that is similar to the AS kernel, i.e., the DB matching kernel can be seen as a subgraph kernel that counts the number of approximately isomorphic h-layer (i.e., K = h) expansion subgraph pairs. Each pair of isomorphic h-layer expansion subgraphs are identified by a pair of matched vertices from the DB matching. Thus, similar to our JS matching kernel, the DB matching kernel can also reflect the locational correspondence information between each pair of identified isomorphic subgraphs. Unfortunately, the identified isomorphic subgraph pair number of the DB matching kernel is less than that of the JS matching kernel. For a pair of graphs each having x vertices, the DB matching kernel can only identify x pairs of isomorphic subgraphs at most. By contrast, the JS matching kernel can identify Mx pairs of isomorphic subgraphs at most. This again demonstrates that our JS matching kernel captures more information than the DB matching kernel.

Finally, like the JS graph kernel [Bai and Hancock, 2013], our kernel is also related to the JSD. However, the JS graph kernel only reflects the global similarity of graphs in terms of the JSD measure between a pair of global graphs, and lacks the interior topological information of graphs. By contrast, our JS matching kernel can reflect rich vertex correspondence information from the JS representations computed by measuring the JSD between corresponding DB representations.

4 Experimental Results

We demonstrate the performance of our new kernel on three standard graph datasets from computer vision databases. The reason of using computer vision datasets is that many computer vision applications usually require the correspondence information between pairwise feature points that are abstracted from images or 3D shapes, for the objective of similarity measure. For an instance, one has two graphs abstracted from two digital images both containing the same object, based on different viewpoints. Here, each vertex represents a feature point. Identifying the correspondence information between pairwise vertices or substructures from the identical region is our concern, and can provide us an elegant way of reflecting precise similarity between the images or shapes. As a result, the new matching kernel can easily indicate its main advantage of identifying the correspondence information, on computer vision datasets. The advantage is unavailable for most existing graph kernels from R-convolution.

BAR31, BSPHERE31 and GEOD31: The SHREC 3D Shape database consists of 15 classes and 20 individuals per class, that is 300 shapes [Biasotti et al., 2003]. This is a usual benchmark in 3D shape recognition. From the SHREC 3D Shape database, we establish three graph datasets named BAR31, BSPHERE31 and GEOD31 datasets through three mapping functions. These functions are a) ERG barycenter: distance from the center of mass/barycenter, b) ERG bsphere: distance from the center of the sphere that circumscribes the object, and c) ERG integral geodesic: the average of the geodesic distances to the all other points. The number of maximum, minimum and average vertices for the three datasets are a) 220, 41 and 95.42 (for BAR31), b) 227, 43 and 99.83 (for BSPHERE31), and c) 380, 29 and 57.42 (for GEOD31), respectively.

4.1 Experiments on Graph Datasets

Experimental Setup: First, we evaluate the performance of our JS matching kernel (JSMK) on graph classification problems. We also compare our kernel with several alternative state-of-the-art graph kernels. These graph kernels include 1) the DB matching kernel (DBMK) [Bai, 2014; Bai et al., 2014a], 2) the Weisfeiler-Lehman subtree kernel (WLSK) [Shervashidze et al., 2011], 3) the shortest path graph kernel (SPGK) [Borgwardt and Kriegel, 2005], 4) the graphlet count graph kernel [Shervashidze et al., 2009] with graphlet of size 4 (GCGK) [Shervashidze et al., 2009], 5) the un-aligned quantum Jensen-Shannon kernel (UQJS) [Bai et al., 2015], 6) the Jensen-Shannon graph kernel (JSGK) [Bai and Hancock, 2013], and 7) the Jensen-Tsallis q-difference kernel (JTQK) [Bai et al., 2014b] associated with q = 2. For our JS matching kernel k(M;h) JSM , we set the h as 10 and the greatest value of m as 40 (i.e., M = 40). For the WLSK kernel and the JTQK kernel, we set the highest dimension (i.e., the highest height of subtrees) of the Weisfeiler-Lehman isomorphism (for the WLSK kernel) and the tree-index method (for the JTQK kernel) as 10. For the DBMK kernel, we set the highest layer of the required DB representation as 10. For each kernel, we compute the kernel matrix on each graph dataset. We perform 10-fold cross-validation using the CSupport Vector Machine (C-SVM) Classification to compute the classification accuracies, using LIBSVM [Chang and Lin, 2011]. We use nine samples for training and one for testing. All the C-SVMs were performed along with their parameters optimized on each dataset. We repeat the experiment 10 times. We report the average classification accuracies and standard errors for each kernel in Table.1.

Experimental Results: In terms of the classification accuracies, our JSMK kernel can easily outperform all the alternative graph kernels on any dataset. The classification accuracies of our JSMK kernel are obviously higher than those of all the alternative kernels. The reasons for the effectiveness are threefold. First, compared to the WLSK, SPGK, GCGK and JTQK kernels that require decomposing graphs into substructures, our JSMK kernel can establish the substructure location correspondence which is not considered in these kernels. Second, compared to the JSGK and QJSK kernels that rely on the similarity measure between global graphs in terms of the classical or quantum JSD, our JSMK kernel can identify the correspondence information between both the vertices and the substructures, and can thus reflect richer interior topological characteristics of graphs. By contrast, the JSGK and QJSK kernels can only reflect the global similarity information between graphs. Third, compared to the DBMK kernel that can also reflect the correspondence information between substructures, our JSMK kernel can identify more pairs of aligned isomorphic substructures. Moreover, as we have stated in Section 3.3, the m-layer JS representation can reflect richer characteristics than the h-layer DB representation. As a result, the JSMK kernel using the JS representation can capture more information for graphs than the DBMK kernel using the DB representation.

Comparisons with Increasing h and M: We explore the performance of our JSMK kernel on graph datasets with increasing h (i.e., h = 1, 2, . . . , 10 when M = 40) and M (i.e., M = 5, 10, 15 . . . , 50 when h = 10). We report the results in Fig.1. In each subfigure, the x-axis gives the varying of h or M, and the y-axis gives the classification accuracies of our JSMK kernel. The lines of different colours represent the results on different datasets. The classification accuracies tend to become greater with increasing h or M. The reasons are twofold. First, for the parameter h, the greater the h, the higher dimensional DB complexity information of our kernel can be captured. Second, for the parameter M, the greater the M, the more pairs of aligned isomorphic local information graphs can be identified by our kernel.

4.2 Computational Evaluations

We explore the computational efficiency (i.e, the CPU runtime) of our JSMK kernel on randomly generated graphs with respect four parameters: the graph size n, the layer h of the DB representations of graphs, the greatest value of the JS representation layer M, and the graph dataset size N. We vary x = {100, 200, . . . , 2000}, h = {1, 2, . . . , 10}, M = {1, 2, . . . , 10}, and N = {5, 10, . . . , 500}, separately. a) For the parameter x, we generate 20 pairs of graphs with increasing number of vertices. We report the runtime for computing the kernel values between pairwise graphs (h = 10 and M = 10). b) For the parameter h, we generate a pair of graphs each of which has 200 vertices. We report the runtime for computing the kernel values of the pair of graphs as a function of h (M = 10). c) For the parameter M, we use the pair of graphs from step b. We report the runtime for computing the kernel values of the pair of graphs as a function of M (h = 10). d) For the parameter N, we generate 500 graph datasets with an increasing number of test graphs. In each dataset, one graph has 200 vertices. We report the runtime for computing the kernel matrices for each graph dataset (h = 10 and M = 10). Note that, since M = 10, the runtime is for computing the 10 kernel matrices for each dataset. The CPU runtime is reported in Fig.2, as operated in Matlab R2011b on a 2.5GHz Intel 2-Core processor (i.e., i53210m). Fig.2 indicates that the runtime scales cubicly with n, linearly with h and M, and quadratically with N. These verify that our kernel can be computed in a polynomial time.

5 Conclusions

We have developed a JS matching kernel by aligning the JS representations that are computed over the corresponding DB representations in terms of the JSD measure. Our new kernel can incorporate explicit local substructure correspondence into the process of kernelization, the new kernel thus addresses the drawback of neglecting the relative locations between substructures that arises in the R-convolution kernels. Experiments demonstrate that our kernel can easily outperforms start-of-the-art graph kernels.