J Math Imaging Vis DOI 10.1007/s10851-016-0686-0

Graph Characterization by Counting Sink Star Subgraphs Maedeh S. Tahaei1 · Seyed Naser Hashemi1

Received: 28 March 2016 / Accepted: 20 September 2016 © Springer Science+Business Media New York 2016

Abstract In this paper, we study the polynomial coefficients of the reduced Bartholdi zeta function for characterizing simple unweighted graphs and demonstrate how to use these coefficients for clustering graphs. The polynomial coefficients of the reduced Bartholdi zeta function are invariant to vertex order permutations and also carry information about counting the sink star subgraphs in a symmetric digraph of G. We also investigate the advantages of the reduced Bartholdi coefficients over other spectral methods such as the Ihara zeta function and Laplacian spectra. Experimental results indicate that the proposed method is more effective than the other spectral approaches, and compared to the Ihara zeta function, it has less sensitivity to structural noises such as omitting an edge. Keywords Reduced Bartholdi zeta function · Graph characterization · Graphs similarity · Polynomial coefficients · Sink star subgraph

1 Introduction Graphs are widely used in pattern recognition and can be used as a representative of the structured data in computer vision since it is an adequate tool for modeling relational information. They exhibit the spatial and conceptual links between parts of objects, and unlike the vectors, the graphs are not limited to a constraint length. Graph as a representa-

B

Seyed Naser Hashemi [email protected] Maedeh S. Tahaei [email protected]

1

Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

tive model for structural data has a large flexibility to encode the relations among the features of objects in a conformed form to the object’s complexity with various arrangements of edges/vertices. Due to these properties, graphs are used in many applications such as network analysis [16], worldwide web [41], machine learning [42] , classifying images [2,26], character recognition [23,35,64] and data mining [31,56]. Regardless of preferences for the graph-based representation, there are some problems that make its use difficult. First, graphs as hybrid mathematical models for the objects in solving some problems are computationally intractable. Despite the fact that the comparison of the two vectors can be performed in linear time, there are no efficient computational algorithms for finding graphs similarity associated with the classification of objects. Due to the lack of intrinsic labeling of the vertices in graphs, some problems such as subgraph isomorphism are known to be NP-complete. The second problem of the graph-based representation is their high sensitivity to noise which yields changes to the edges/vertices which are difficult to track, even for graphs of the same class. However, to overcome these problems and exploit the advantages of statistical learning methods in clustering and classification, graph embedding is employed as a bridge between the structural representation and feature vector representations [4,15,22,52]. Graph embedding is an approach for extracting a feature vector that has the capability to describe a perfect understanding of a graph in a permutation invariant manner [49] and represents all the information as a point in an arbitrary vector space such that the likeness and difference of the graphs are conserved. In recent years, several ways for embedding graphs have been proposed. The first approach is based on implicit embedding space for the graphs. These methods try

123

J Math Imaging Vis

to apply kernel methods in graph domains and implicitly embed the graphs into vector space [52,65]. Kondor et al. [36] introduced the graphlet kernels by using a set of graph invariants, called the graphlet spectrum. Also, these methods do not acquire a specific point for each graph, since they compute the dot product of pairs of graphs in vector space. The drawback of these methods is that a single operation on an embedded graph is not possible. The second method is based on the explicit embedding in vector space by considering the similarity/dissimilarity between graphs and predefined prototypes dependent on a similarity/dissimilarity measure such as graph edit distance [24,45,51,53]. However, the computation of the graph edit distance in consideration of correspondence matching between graphs is very expensive. Even though inexact computation was addressed, finding appropriate prototypes in a uniformed way is difficult since uniformity over a graph domain is an obscure concept [51]. The third family of graph embedding accomplishes this purpose by finding the quality of occurring particular substructures in graph [38,58] as deterministic complexity measures. For instance, one could utilize the number of matched substructures such as subgraphs, walks, paths, cycles and trees [14,47] and consider them as the similarity of the graphs. Another approach is the probabilistic complexity measures. These approaches measure the entropy of a probability distribution held by a graph. For example, Anand et al. [1] and Passerini and Severini [46] have applied the von Neumann entropy to the domain of graphs. Recently, a new complexity measure for a graph has been widely used to compute the thermodynamic depth complexity by its depthbased representations. [5,7,20]. One of the bottlenecks of these methods is that they are computationally expensive. The fourth approach of graph embedding is based on spectral graph theory. In [40], Luo et al. extracted a feature vector of a graph from Laplacian spectrum by eigenvalue decomposition of adjacency and Laplacian matrices. In addition, they developed their method by exploiting elementary symmetric polynomials (ESPs) computed from the spectral matrix of Laplacian of a graph [25,66]. Another spectralbased approach is the one proposed in [48,54]. In [54], the Laplace–Beltrami operator for the graph Laplacian applied to embed a graph in a Riemannian manifold where the geodesic distance between two points on the manifold can be determined. In [10], Bai and Hancock showed how to extract permutation invariant graph feature vectors by sampling the Rosenberg zeta function [67] which is related to the Mellin moments of the heat kernel trace. Nevertheless, these proposed spectral approaches are unsuccessful to distinguish cospectral graphs. However, in [57,60], the ability of Ihara zeta function [32,33] to distinguish the cospectral graphs has been demonstrated. The zeta function of a graph can be explicated as the Riemann zeta

123

function from number theory in which the prime numbers are considered as the prime cycles [12]. For this reason, Ren et al. [49] apply the polynomial coefficients of the Ihara zeta function of a given graph to characterize graphs. In this paper, the authors have explored the use of the Ihara zeta function for estimating cycle structure and topology of a graph since the number of closed walks in the graph with no backtracking or tails can be obtained from the Ihara coefficients. Note that all types of zeta functions are defined on md2 graphs in which every vertex has degree at least two. There is a substantial research literature on studying the properties of the Ihara zeta function [28,30,37], in distinguishing co-spectral graphs [59], and on developing the various types of the zeta functions of graphs [17,61]. Since this method computes the spectrum of an oriented line digraph as the Perron–Frobenius operator of a graph, the drawback of failure in identifying the cospectrality of the Laplacian or adjacency matrices is not seen in this method [18]. Also specialization of the Ihara zeta function is then performed for weighted graphs [49] and hypergraphs [50]. Subsequently, Furqan et al. [3] proposed an efficient method for computing the Ihara coefficients and decreased the running time of previously known algorithms. In [11], the Bartholdi zeta function for a graph was first defined which generalized the Ihara zeta function by counting the bump of a path in the prime cycle of a graph. Also, further generalization of the Bartholdi zeta function for different types of graphs has been studied in the recent decade in some combinatorial literatures. However, the Bartholdi zeta function has not been used so far as a tool of characterizing graphs in machine learning. Recently, we have proposed an explicit description of the relation between the Bartholdi zeta function and the structure of a graph [63]. Despite the fact that the Bartholdi zeta functions can be computed in polynomial time O(2|E|)3 [34], it is not easy to compute with some numeric procedures, since it is expressible as a two-variable determinant. The symbolic computations involve unusual mathematics which may bring about some difficulties with numerical processing. For computing the Bartholdi zeta function, we can employ a general symbolic computational tool where its results are accurate, and for small-size matrices, the computational time is acceptable, but for larger matrices used in machine learning the computational time becomes extremely large. Given that the Ihara coefficients determine the frequencies of the prime cycle in the graph, in this paper we introduce a novel approach for extracting a feature vector from a given graph by exploiting the count of the cyclic bump. According to our previous work which resulted in a new reduced Bartholdi zeta function of a simple graph [63], we present two algorithms for computing the coefficients of the reduced Bartholdi zeta function based on two basic theorems of [63] and without any symbolic computations. We demonstrate

J Math Imaging Vis

that these coefficients are able to count the sink star subgraphs (special complete bipartite structures) in a simple graph and can be used as a new representation for graphs. The reduced Bartholdi zeta function focuses on the variable related to the number of bumps on paths in a simple graph. In fact, we tend to concentrate on an exclusive variable of the Bartholdi zeta function. We ignore the other variable which is common with the Ihara zeta function [63]. Moreover, the other advantage of omitting this formal variable lies in the fact that the determinant expression of the reduced Bartholdi zeta function can be computed faster than the Bartholdi zeta function. In this paper, we consider a simple graph as an unweighted, undirected graph containing no graph loops or multiple edges. The rest of the paper is organized as follows. In the next section, we establish the definitions of the Ihara, Bartholdi and reduced Bartholdi zeta functions and present some definitions and preliminaries which are necessary for the remainder of the paper. In Sect. 3, the relation between the structure of the graph and the coefficients of the reduced Bartholdi zeta function is presented and we demonstrate the algorithms for calculating all the coefficients of the reduced Bartholdi zeta function. Finally, Sect. 4 provides an experimental result of the proposed method on random graphs and some graphs extracted from the real-world data. Experimental results are compared with dominant spectral approaches.

Definition 2.3 Consider a simple undirected and finite graph G = (V (G), E(G)) having n vertices and m edges, where V (G) and E(G) denote the vertex and the edge set of G, respectively. Associated with G, one may correspond a symmetric digraph, denoted by D(G) with V (D(G)) = V (G) and E(G) = A(D(G)) = {(u, v), (v, u)|uv ∈ E(G)}. Therefore, a one-to-one correspondence between the set of symmetric digraphs and the set of simple undirected and finite graphs can be identified. In the symmetric digraph D(G), we say that a backtrack path P = (a1 , . . . , ak ) has a bump at t (ai ) if ai+1 = ai−1 for some 1 ≤ i ≤ k − 1. The cyclic bump count, cbc(C), is defined as the number of bumps in the cycle C = (a1 , a1 , . . . , ak ) and is given by     cbc(C) =  i = 1, . . . , k|ai+1 = ai−1  .

Definition 2.4 The oriented line graph of G, denoted by L(D(G)), is a digraph whose vertex set is constructed by substituting each arc of D(G) for a vertex. For each pair of these vertices such as (ai , a j ), there is an edge between them, if and only if the origin of one arc meets the terminus of another. So, if T is adjacency matrix of the oriented line graph L(D(G)), then  Ti j =

2 Basic Concepts and Definitions In this section, we state some definitions which are useful in the sequel of the paper. Definition 2.1 A directed graph or digraph D is an ordered pair (V (D), A(D)) consisting of a non-empty set V (D) of vertices and a set A(D) ⊆ V (D) × V (D) of arcs. For any arc a = (u, v), an orientation from u = o(a) as its origin to v = t (a) as its terminus is assumed. The inverse of the arc a = (u, v) obtained by switching the origin and terminus of a is denoted by a −1 = (v, u). Definition 2.2 A path P of length k in D is a finite nonempty sequence (v0 , a1 , v1 , . . . , ak , vk ), which terms are alternately vertices and arcs, such that ai = (vi−1 , vi ), for 1 ≤ i ≤ k. For abbreviation, we write P = (a1 , . . . , ak ). A path P has a backtracking, if ai+1 = ai−1 , for some 1 ≤ i ≤ k −1. Moreover, if v0 = vk , then P is called a cycle. Also, a cycle with no backtracking is called a backtrack-less cycle. Let B r be the cycle obtained by going r times around a cycle B, which is called r -multiple of cycle B. A cycle is called prime or primitive, if it has no backtracking and is not multiple of other cycles.

(1)

1 if t (ai ) = o(a j ) and a j = ai −1 , 0 otherwise,

(2)

while T is a 2M × 2M non-symmetric matrix. In addition, the line graph of G called L(G) is constructed by replacing each edge of G with a vertex, where vertices of L(G) are adjacent, if and only if their corresponding edges in G are adjacent to each other with a vertex. Definition 2.5 Let G be a simple undirected graph with the edge set E(G) = {e1 , . . . , em }. Arbitrarily orient its edges and label all 2m arcs of its symmetric digraph D(G) −1 }. as E(G) = {a1 , . . . , am , am+1 = a1−1 , . . . , a2m = am −1 −1 Furthermore, let ai  = ai and ai = ai  for all i, 1  i  m. Hence, the labels of the arcs are changed to E(G) = {a1 , . . . , am , a1 , . . . , am  }. Suppose S[α; α  ] = Sq×q as the q × q submatrix of T with rows indexed by a subset α = {i 1 , . . . , i q } ⊆ {1, . . . , m, 1 , . . . , m  } (for q  2) and columns indexed by corresponding inverse subset α  = {i 1 , . . . , i q } such that i 1 < · · · < i q , for all i, 1  i  m. The determinant of the submatrix S[α; α  ] of T is called the semi-principal minor of T. If the above labeling applied in D(G), then T = (ci j ) as the adjacency matrix of the oriented line graph L(D(G)) can be shown as follows:

123

J Math Imaging Vis

⎛

T2m×2m

0 c12 · · · ⎜ c21 0 · · · ⎜ ⎜ .. .. ⎜ . . ⎜ ⎜ cm1 cm2 · · · ⎜ =⎜ ⎜ 0 c1 2 · · · ⎜ ⎜ c2 1 0 · · · ⎜ ⎜ . .. ⎝ .. . cm  1 am  2

c1m 0 c12 c2m c21 0 .. .. . . 0 cm1 cm2

⎞ · · · c1m  · · · a2m  ⎟ ⎟ . ⎟ .. . .. ⎟ ⎟ ··· 0 ⎟ ⎟ ⎟ (3) · · · c1 m  ⎟ ⎟ · · · c2 m  ⎟ ⎟ . ⎟ .. . .. ⎠

c1 m 0 c1 2 c2 m c2 1 0 .. .. . . · · · 0 cm  1 cm  2 · · · 0

Definition 2.6 A sink star subgraph in the digraph D(G) is said to be a directed star subgraph containing a sink node v ∈ V such that deg− (v)  2, and q leaves with q  deg− (v). A set of all possible sink star subgraphs with q leaves in the digraph D(G) is denoted by Sq . In Fig. 1, one sink star subgraph selected from the digraph D(G) with 4 leaves is shown in red. Definition 2.7 A partition of an integer n is a non-increasing sequence of positive integers lgreater than 1, denoted by c1 , c2 , . . . , cl , such that n = i=1,ci >1 ci . Each ci , 1  i  l, is called a part of the partition. From now on, let p(n) be the number of unique partitions of the integer n, and ρni denote the ith unique partition of integer n, for 1  i  p(n). As an example, the partitions 3  n  6 are shown: 3 4 5 6

(4)

[C]

where [C] is the class of equivalence prime backtrack-less cycles and the l(C), by definition, is the length of cycle C. Also, Hashimoto [28] generalized the determinant expression for the Ihara zeta function of an irregular graph by using the adjacency matrix of the oriented line graph, T, which can be written as follows,

123

−1 (t) = c0 + c1 t + · · · + c2M−1 t 2M−1 + c2M t 2M . ZG

(6)

The basic formula (4) of Ihara zeta function considers the number of backtrack-less cycles C with the length of l(C) in the graph and in [49], some of its coefficients are used as a feature vector in order to characterize graphs. 2.2 Bartholdi Zeta Function and Backtrack-Less Cycles and Backtrack Cycles The Bartholdi zeta function of graph G is defined to be a function of two independent variables u, t which extended the definition of a prime cycles by allowing them to have bumps as described in [11]. ζG (u, t) =

−1

 1 − u cbc(C) t l(C) ,

(7)

[C]

Bi j =

The Ihara zeta function of a simple undirected graph G is a function of complex variable t, given by [33]

Fig. 1 The sink star subgraph with 4 leaves

where T is defined in Definition 2.4. The reciprocal of the Ihara zeta function for a graph can be defined as a sequence of coefficients such as



2.1 Ihara Zeta Function and Backtrack-Less Cycles

−1

 1 − t l(C) ,

(5)

where [C] runs over all equivalence classes of primitive cycles C of G (see [1]). For any ai , a j ∈ D(G), two 2|E| × 2|E| matrices B, J are defined as follows:

: (3) : (2, 2), (4) : (2, 3), (5) : (2, 2, 2), (2, 4), (3, 3), (6)

Z G (t) =

Z G (t)−1 = det(I2m − tT),

1 if t (ai ) = o(a j ) Ji j = 0 otherwise,



1 if a j = ai−1 0 otherwise.

(8)

Also, Bartholdi [11] gave a determinant expression of the Bartholdi zeta function of graph G, based on the above definitions of B, J, which can be written as ζG (u, t)−1 = det(I 2m − (B − (1 − u)J)t).

(9)

The Bartholdi zeta function contains two variables u, t, where the variable t is common with the rational form of Ihara zeta function and the variable u which is referred to the backtrack bump counts of a cycle in a graph. However, if in the Bartholdi zeta function the variable u is set as zero u = 0, it becomes the Ihara zeta function. On the other hand, by some mathematical operations the variable t can be omitted from the Bartholdi zeta function as described in the following subsection, and so it is reduced to a new zeta function which is called the reduced Bartholdi zeta function [63].

J Math Imaging Vis

2.3 The Reduced Bartholdi Zeta Function and Backtrack Cycles

⎡ 1 1⎢ 0 ⎢ 2⎢ 0 ⎢ 4⎢ ⎢ 1 ⎢ 1 5⎢ ⎣ 0 6

In order to present our result in the next section, we briefly describe the way of constructing the reduced Bartholdi zeta function. The details can be found in our previous work [63]. Using the definition of the adjacency matrix of the oriented line graph and using the fact that T = B − J, Eq. (9) can be changed to the following form

(A) ζ (u, t)−1 = det (I 2m − (T + uJ) t) .

(10)

1 , we get the reciproBy substituting t for x1 , and factoring x 2m 1 −1 cal form of the ζ (u, x ) as χ (u, v) = det(vI 2m −(T +uJ)), where v is replaced by x1 . If we set the variable v = 0, then the following polynomial, called the reduced Bartholdi zeta function, is obtained:

χ (u, v = 0) = (−1)2m det (T + uJ) = d0 u 2m + d1 u 2m−1 + d2 u 2m−2 + · · · + d2m . (11) The coefficients of the reduced Bartholdi zeta function enumerate the backtracks of the graph. They are quite different from the Ihara zeta function which is confined to the enumeration of backtrack-less cycles [33]. In the next section, we briefly show the relation between the coefficients of the reduced Bartholdi zeta function and the structure of the graph G.

3 Relation Between the Coefficients of the Reduced Bartholdi Zeta Function and the Structure of Simple Graphs The coefficients of the reduced Bartholdi zeta function in Eq. (11) can be used as descriptors of graph structure for characterizing simple graphs. In this work, we present two algorithms for computing all the coefficients of the reduced Bartholdi zeta function and interpret them from the structural point of view. Before presenting the algorithms we have developed in this paper, let us briefly review the values of the first coefficients of the reduced Bartholdi zeta function for a simple graph G which is an unweighted, undirected graph containing no loops or multiple edges. The first coefficient of the reduced Bartholdi zeta function, d0 , is equal to (−1)m , the second coefficient d1 is always zero, and the third coefficient d2 is determined by (−1)m+1 × the number of edges of line graph of G, L(G). For more information and the proofs of the results mentioned here, we refer to our previous work [63], which expresses the relation between all the coefficients

2 4 ⎤ 0 1 0 0 ⎥ ⎥ 0 0 1 1 ⎥ ⎥ 0 0 0 0 ⎥ ⎥ ⎥ 0 0 0 1 ⎥ ⎦ 1 0 1 0

(B)

Fig. 2 The sink star subgraph of an arbitrary digraph D(G) and its associated SPM

of the reduced Bartholdi zeta function and the structure of graphs. Furthermore, we need to clarify the relation between our definitions, so the following lemma states the relation between the structure of semi-principal minor and sink star subgraphs. Lemma 3.1 [63] For any n × n semi-principal minor S, extracted from matrix T of graph G, the indices of its rows can be interpreted as a set of unconnected sink star subgraphs in a digraph D(G). Moreover, the sum of all indegrees of their sink nodes is equal to n. According to the proof of this lemma in [63], for every semi-principal minor S, the indices of any rows which is participant in a sink star subgraph have to be disjoint from other sink star subgraphs of S. This fact that each index contributes exactly to one sink star subgraph shows that the sum of all indegrees of their sink nodes will be equal to the number of indices of rows in S which is n. As a result, we can see that every semi-principal minor completely corresponds to a set of unconnected sink star subgraphs in a digraph D(G) as shown in Fig. 2. In Fig. 2b, some indices of T involved in constructing a semi-principal minor are presented. The next lemma indicates that integer partitions, as defined in Definition 2.7, are involved in the construction of these unconnected sink star subgraphs from a semi- principal minor. Lemma 3.2 [63] Let ρni be the ith partition of integer n. By Definition 2.6, corresponding to each ci a sink star graph Sci with ci leaves , 1  i  l, can be associated. Furthermore, the collection of Sc1 , . . . , Sci , . . . , Scl in which c1 + · · · + ci + · · · + cl = n constructs a set of unconnected sink star subgraphs to which a semi-principal minor of size n can be assigned. Now we state two main theorems proved in [63], which are used for building the structure of a graph, relying on the concepts mentioned earlier of sink star subgraphs, integer partition and the semi-principal minors.

123

J Math Imaging Vis

Theorem 3.3 [63] Let T and J be two 2m × 2m square matrices associated with L(D(G)) and define M = T + uJ. Then, the reduced Bartholdi zeta function of G is given by det(M) = d0 u 2m + d1 u 2m−1 + d2 u 2m−2 + · · · + d2m . Let dn be the coefficient of the variable u 2m−n , 0  n  2m. Then, the value of (−1)m dn is obtained by the sum of those semi-principal minors of T which have n rows and n columns. The theorem states that by considering the permutations contributing to dn for the coefficient of u 2m−n , one must take into account all those summands which have exactly 2m − i variables of u from matrix T+uJ. In the following algorithm, the way of extracting of semi- principal minors is presented. The summation of the corresponding determinant of SPMs with n rows and n columns is return as the (−1)m dn .

Algorithm 2: calculating the coefficient dn of reduced Bartholdi function based on partitions (RBP)

1 2 3 4 5 6 7

8

Algorithm 1: calculating the coefficient dn of reduced Bartholdi function based on SPM (RBS)

1 2 3 4 5 6 7 8 9 10 11 12

Input: 2m × 2m matrix T as the adjacency matrix of the oriented line graph of the graph G Output: dn ← the nth coefficient of reduced Bartholdi polynomial sum ← 0; C ← Find all possible combinations from {1, 2, . . . , 2m} with n elements; for k ← 1 to si ze(C) do D ← zeros matrix of size n × n; for i ← 1 to n do for j ← 1 to n do D(i, j) ← T (C(k, i), C(k, j) + sign(m − C(k, j)) × m); end end sum ← det (D) + sum; end return sum;

Definition 3.4 [63] Suppose ρni , for all n, 1  i  p(n). We choose one matrix of similar semi-principal minors as a prototype matrix for ρni , called Pni , which exhibits a set of isomorphic subgraphs. Next, we present the other theorem which is used for finding the coefficients of the reduced Bartholdi zeta function based on the partition number. Theorem 3.5 [63] Let Uni be the set of sink star subgraphs corresponding to ρni in D(G). Then, the nth coefficient, dn , of the term u 2m−n in the reduced Bartholdi zeta function of the graph G is given by dn = (−1)m

p(n)  i=1

123

|Uni | × det(Pni ),

(12)

9 10

Input: degree sequence of the graph, all partitions of n as ρni ; 1  i  p(n), p(n) is the number of different partitions of n, each ρni contains a list of numbers k ci = n. c1 , · · · , ck , such that i=1 Output: dn ← the nth coefficient of the reduced Bartholdi polynomial summation ← 0; for i ← 1 to p(n) do ρni ← c1 + · · · + ck ; S ← Find all possible combinations from degree sequence of the graph with k elements ; P S ← Find all permutations of each row of S and add to the end of S; for j ← 1 to si ze(P S) do summation ←   P S(1, j)  P S(2, j) j) × × · · · × P S(k, + summation; c1 c2 ck end end return summation;

where Pni is the prototype matrix of ρni and p(n) denotes the number of unique partitions of the integer n. A pseudocode for computing the coefficients based on abovementioned theorem is given in Algorithm 2. 3.1 Computational Complexity We can see that the use of the above algorithms for computing all the coefficients dn of the reduced Bartholdi zeta function is intractable, while the problem of the partitions number and finding all possible combinations from {1, 2, . . . , 2|E|} are known to be NP-complete [29]. This is because the exact computation cost for finding the coefficient dn of Algorithm 1 (RBS) is O(n 2 (2|E|)min(n,2|E|−n) ) and for Algorithm 2 (RBP) will be equal to O(| p(n)|(n/2)|V | ), which are very large costs. Also, similar to the Ihara zeta function, the coefficients of the reduced Bartholdi zeta function can be obtained by computing the determinant of T + u J in O(2|E|)3 [49], but symbolic computation time for the large matrices used in computer vision datasets becomes extremely large. Furthermore, by empirical experiments in the next section, we can see that the beginning and trailing coefficients of the reduced Bartholdi zeta function present more information than the intermediary ones. However, since our approach of graph characterization is restricted to a small number of coefficients, we can apply Algorithm 1 or 2 without having to involve symbolic computation. In our implementation in the next section, we use both mentioned algorithms for finding the coefficients with the aim of analyzing the performance of them for different datasets. The results of these algorithms are

J Math Imaging Vis

the same, but for the purpose of fast computing, for smaller n, we prefer to use RBP algorithm with exact cost O(|V |) for d2 and O(|V |2 ) for d4 . For the larger n, the cost of RBS algorithm will be O(|E|2 ) for d2m and O(|E|3 ) for d2m−1 . In addition, for the tree structured datasets, which det(T ) = 0 and may be intractable for the Ihara zeta function, our algorithms without any determinant computation can be used for computing desired coefficients and this approach should be effective and efficient for such datasets.

4 Experimental Results In this section, we examine the performance of the reduced Bartholdi zeta function on both random graphs and the graphs extracted from real-world datasets. The intention of assessing our proposed method on random graphs is to investigate the ability of recognizing different graphs by the measure of graph edit distance and with a certain level of structural similarity. The purpose of using the graphs extracted from real-world datasets is to evaluate the coefficients of the reduced Bartholdi zeta function as a valuable clustering tool in pattern vector space. 4.1 Comparison of Edit Distance and the Proposed Similarity Measure Graph edit distance is one of the basic similarity measures between graphs. It is a minimum edit operation to transform one graph to another by deleting, inserting or relabeling vertices/edges. The comparison between the graph edit distance and the reduced Bartholdi zeta function can be used to clarify the criteria of our proposed method for distinguishing the graphs of different classes. This study is possible only under certain conditions, for the reason that the computational complexity of exact graph edit distance is exponential in the number of vertices. So we evaluate the performance of the proposed method with comparison of graph edit distance by the approach introduced in [49] using random graphs. We compare the Euclidean distance between feature vectors of given random graphs and a seed graph where these features are extracted from the polynomial coefficients of the reduced Bartholdi zeta function. 4.2 Random Graphs We generate a set of random graphs from a real graph of COIL dataset with 110 vertices and 310 edges. The generation of graphs is performed by randomly deleting 30–90 edges from the seed graph, and then, 60 different classes are constructed. This deletion repeated 100 times ensuring that the md2 constrain remains satisfied, so we have 100 graphs in each class with the same edit cost. For simplicity, the edit

cost between these new graphs and the seed graph is assumed to be the number of deleted edges. In the case of fast computing of the first set of coefficients, we prefer to use Algorithm 1, and in order to find the last set, Algorithm 2 is used. We also consider the coefficients of the Ihara zeta function [49] which is one of the most effective methods in the case of spectral representations of graphs and has prominent results in contrast with other methods in this field of research. So we compare our result with this approach and take into account the two forms of the unselected Ihara coefficients as (c3 , c4 , c5 , c6 , c7 , ln(|c2M |))T and selected Ihara coefficients as (c3 , c4 , ln(|c2M |))T as stated in [49]. =  We obtain the Euclidean distance as di, j

(vi − v j )T (vi − v j ) between feature vectors of the seed graph and the feature vectors of all the other random graphs in a same class (with the fix number of deleted edges) and draw it as a function of the edit distance as it is shown in Fig. 3. Comparing the ranges of feature distance in Fig. 3a–d, we can see that the dynamic ranges of the reduced Bartholdi feature distance and normalized reduced Bartholdi feature distance in Fig. 3c, d are much less than the selected and unselected Ihara feature distance in Fig. 3a, b for a corresponding edit distance. Also Fig. 3c, d shows that our measurement for characterizing random graph is more similar to the graph edit distance. While the Ihara zeta function has a very large variation in feature distance, for deleting an edge, specially for the unselected Ihara feature distance its range is too large compared to the range of edit distance and also is not completely linear as shown in Fig. 3a, b. In contrast, Fig. 3c, d shows the linear behavior of the reduced Bartholdi feature distance as a function of graph edit distance. Thus, the Ihara zeta function has more sensitivity to structural noises such as omitting an edge. For more analysis on synthesis data and showing how accurate our data is in the experiment, we compare the relative standard deviation (RSD) under controlled conditions in the structure of graphs. RSD is a useful parameter to measure the stability of the standard deviation expressed as a percentage of the mean for the same series. The smaller RSD shown in Fig. 3e for normalized reduced Bartholdi feature distance illustrates that it is tightly clustered around the average of feature distance and can show how accurate our data is in an experiment. Albeit, the values of RSDs for all four features are less than 5.5 and it is due to this fact that the stability of them are acceptable, by considering that increasing in number of edges deletion will cause the convergence of pairs of diagrams to each other. 4.3 Real-World Datasets

Here, we use three different graph datasets on real-world data. The first dataset, namely COIL [44], can be made up of graphs obtained from the images in the Columbia object

123

J Math Imaging Vis selected Ihara coefficients

Unselected Ihara coefficients

5

500

2.1

x 10

2 1.9 1.8

400

Feature distance

Feature distance

450

350

300

1.7 1.6 1.5 1.4 1.3

250

1.2 200 30

40

50

60

70

1.1 30

80

40

50

Edit distance

60

70

80

Edit distance

(A)

(B) Normalized Reduced Bartholdi coefficients

Reduced Bartholdi coefficients 80

2 1.8

70

60

Feature distance

Feature distance

1.6

50

40

1.4 1.2 1 0.8

30 0.6 20 30

40

50

60

70

0.4 30

80

40

50

Edit distance

60

70

80

Edit distance

(C)

(D) 6

Reduced Bartholdi coefficients Normalized Reduced Bartholdi coefficients Selected Ihara coefficients Unselected Ihara coefficients

5.5 5 4.5

RSD%

4 3.5 3 2.5 2 1.5 1 30

40

50

60

70

80

Edit distance

(E) Fig. 3 a–d The feature vector distance extracted from the reduced Bartholdi coefficients and the Ihara coefficients versus edit distance in random graphs. a Selected Ihara coefficients. b Unselected Ihara coefficients. c Reduced Bartholdi coefficients. d Normalized reduced Bartholdi coefficients. e RSD

123

J Math Imaging Vis Fig. 4 3D images for experiments. a COIL dataset. b ALOI dataset. c ETHZ dataset. d SHREC dataset

123

J Math Imaging Vis 35

30

35

4 class 5 class 6 class 7 class 8 class

30

Sb+Sw/S

S +S /S b w w

25

w

25

20

15

15

10

5

20

10

d2

d3

d4

d5

d6

d7

d2m−1

d2m

Coefficient label

(A)

5

4 class 5 class 6 class 7 class 8 class c

3

c

4

c

c6

5

c7

ln(c

)

2m

Coefficient label

(B)

Fig. 5 Criterion function values for classes of COIL dataset. a Reduced Bartholdi coefficients. b Selected Ihara coefficients

image library (COIL) which consists of eight 3D objects shown in Fig. 4a, and each of them has 72 views under controlled rotation and lighting condition. The second dataset, namely ALOI [6], can be made up of graphs extracted from the images of three similar boxes as shown in Fig. 4b. The third dataset, namely ETHZ [19], can be made up of graphs extracted from 8 3D objects where each of them has 5 views for different rotations which are shown in Fig. 4c. For extracting graphs from images, we first determine the dominant points of images by Harris corner detector [27]. Using the corner points, Delaunay graph of an image is constructed which plane it to triangulations as presented for COIL dataset in Fig. 4a. In addition, we evaluate our method on a usual benchmark in 3D shape recognition called SHREC database with 15 classes and 20 individuals per class as shown in Fig. 4d. From this database, the datasets named BAR31, BSPHERE31 and GEOD31 are extracted by using three mapping functions [13]. The way the graphs are extracted depends on these mapping function (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. These databases belong to tree structured datasets. 4.4 Selecting the Best Combinations of Coefficients For selecting a suitable feature vector from polynomial coefficients of the reduced Bartholdi zeta function, we begin by computing the first eight coefficients from the beginning as (d0 , d1 , d2 , d3 , d4 , d5 , d6 , d7 )T and two final coefficients as (d2m−1 , d2m )T . The coefficients of the reduced Bartholdi zeta

123

function can be obtained by computing the determinant of T + u J in O(2|E|)3 [49]. In the case of small number of coefficients, for avoiding the limitations of symbolic computation and increasing the speed of computation, acquiring the coefficients from the beginning can be performed by using RBP algorithm and the two final coefficients can be achieved based on RBS algorithm. Also all the features of the vector are scaled in a natural logarithmic manner, while the logarithm transformation of feature vector moves big values of features closer to each other. It moves small values farther apart and prevents the problems of dynamic range. Then, for selecting a subset of prominent coefficients, we consider the criterion function as JC [49], to select salient individual Ihara coefficients which have larger value of JC . In this paper, the authors consider the criterion function of the coefficients of Ihara. They select three objects and use for each object 10 sample images as training data to compute the criterion function value of the COIL dataset and then investigate the result of the two forms of unselected Ihara coefficients as (c3 , c4 , c5 , c6 , c7 , ln(|c2M |))T and selected Ihara coefficients as (c3 , c4 , ln(|c2M |))T . In our experiment, we estimate the criterion function of the coefficients of Ihara and reduced Bartholdi zeta function for all the 8 classes of the COIL dataset with 72 sample images in each class. For better investigation, we gradually increase the number of classes from 4 to 8 and separately compute the criterion function of each of them. In JC = (Sb + Sw )/Sw , the between-class U D (c − ck )2 and the within-class scatter is Sb = Ui=1 Ui k,i scatter is Sw = i=1 ck,i, j ∈Ci Di (ck,i − ck )2 where U is the number of classes, Di is the number of instances in class Ci , ck is the average of the samples for coefficient ck and ck,i is the average of the samples for ck in class Ci .

J Math Imaging Vis 8

15

object 1 object 2 object 3 object 4

7.5

object 1 object 2 object 3 object 4

14.5 14 13.5

d4

13

d2

7

6.5

12.5 12 11.5

6

11 10.5

5.5

0

10

20

30

40

50

60

70

10

80

0

10

20

Number of views

30

40

50

60

70

80

Number of views

(A)

(B)

300

250

object 1 object 2 object 3 object 4

250

object 1 object 2 object 3 object 4

200

200

2m

d

150

d

2m−1

150

100 100 50

50

0

0

10

20

30

40

50

60

70

80

Number of views

(C)

0

0

10

20

30

40

50

60

70

80

Number of views

(D)

Fig. 6 Reduced Bartholdi coefficients for graphs extracted from the first four objects in the COIL dataset: a d2 , b d4 , c d2m−1 and d d2m

According to the JC value, we choose four coefficients (d2 , d4 , d2m−1 , d2m )T of the reduced Bartholdi zeta function for our experiments. Also, we compare JC value of our coefficients computed from the reduced Bartholdi zeta function with unselected coefficients of Ihara zeta function as shown in Fig. 5. It shows that the reduced Bartholdi coefficients have more steady behavior for different classes compared to Ihara zeta coefficients. This is because by changing the number of classes, the ratio of JC values of the reduced Bartholdi coefficients to each other is the same, while this ratio in the Ihara coefficients is different. The four selected coefficients (d2 , d4 , d2m−1 , d2m )T of the reduced Bartholdi zeta function determined from the first four classes of the COIL dataset as functions of view numbers are plotted in Fig. 6. Each line demonstrates one coefficient obtained from one object. The lines in each subfigure are

completely disjoint, and it shows that for the purpose of classifying different object classes, these four selected coefficients of the reduced Bartholdi zeta function are adequate. Although the selection of the coefficients is purely empirical, but note that for both the Ihara and reduced Bartholdi zeta function the beginning and trailing coefficients present more information than the intermediary ones. Furthermore, by considering Theorem 3.5 for the reduced Bartholdi zeta function, we can see that the intermediary coefficients are constructed by the combinations of smaller ones and also Theorem 3.3 shows that the larger coefficients contain spectral information. Also, the last coefficient as det(T) is associated with the degree d(vi ) of the graph G [49]. Hence, the remaining coefficients do not increase discrimination of objects of different classes and have some redundant information about the combination of other coefficients.

123

100 0 −100 −200 −300 2000

2 0 −2

10 5

1000

5

x 10

1 −1000

Second Eigenvector

0

First Eigenvector

Second Eigenvector

(A) 800

0

−100

−1

(C)

(D)

0.6

Coefficients of normalized Reduced Bartholdi Zeta Function

Object 1 Object 2 Object 3

0.4

−5

0.05

0.2 0 −0.2 −0.4

−10

−600

Object 1 Object 2 Object 3

0.1

Second Eigenvector

−400

Second Eigenvector

Second Eigenvector

Second Eigenvector

0 −200

0

First Eigenvector

−1

−0.2

600

200

−0.5

−0.15

Second Eigenvector

First Eigenvector

Coefficients of Reduced Bartholdi Zeta Function

Object 1 Object 2 Object 3

0

−0.1

−50

Second Eigenvector

First Eigenvector

5

400

0.5

−0.05

0

Coefficients of selected Ihara Zeta Function

Object 1 Object 2 Object 3

1000

0.05

100

(B)

Coefficients of unselected Ihara Zeta Function

−3

x 10

50

−0.5

−200 −400

−10

Object 1 Object 2 Object 3 Object 4

4 2 0

150

0 −5

−1

−2000

0

200

0

2

0.02 0 −0.02

400

3 0

Object 1 Object 2 Object 3 Object 4

Third Eigenvector

Object 1 Object 2 Object 3 Object 4

Third Eigenvector

Object 1 Object 2 Object 3 Object 4

Third Eigenvector

Third Eigenvector

J Math Imaging Vis

0

−0.05

−0.1

−0.6

−800 −1000 −4

−0.8

−15 −2

0

2

4

6

8

10

First Eigenvector

−200

−100

0

100

200

300

−0.15 −60

−40

−20

0

First Eigenvector

4

x 10

(E)

(F)

Coefficients of unselected Ihara Zeta Function

20

40

60

80

100

−0.8

Coefficients of selected Ihara Zeta Function

Coefficients of Reduced Bartholdi Zeta Function

−500

2 0 −2 −4

0.2

0.4

0.6

0.8

1

Coefficients of normalized Reduced Bartholdi Zeta Function 0.1

Object 1 Object 2 Object 3 Object 4 Object 5

0.2 0.1 0 −0.1 −0.2

Object 1 Object 2 Object 3 Object 4 Object 5

0.05

Second Eigenvector

0

4

0

(H)

0.3

Second Eigenvector

6

Second Eigenvector

Second Eigenvector

Object 1 Object 2 Object 3 Object 4 Object 5

8

500

−0.2

First Eigenvector

0.4

1000

−0.4

(G)

10

Object 1 Object 2 Object 3 Object 4 Object 5

1500

−0.6

First Eigenvector

0

−0.05

−0.3 −6

−1000

−0.4

−8

−0.1 −0.5

−10 −1

−0.5

0

0.5

1

1.5

First Eigenvector

−300

−200

−100

5

x 10

0

100

200

300

−60

−40

−20

0

20

80

100

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

(J)

(K)

(L)

0.4

0.6

0.8

g Reduced Bartholdi coefficients. h Normalized reduced Bartholdi coefficients. Comparison of clustering performance for four classes of graphs extracted from ETHZ dataset. i Unselected Ihara coefficients. j Selected Ihara coefficients. k Reduced Bartholdi coefficients. l Normalized reduced Bartholdi coefficients

Feature vector

Classes of COIL dataset 4

5

6

7

8

Reduced Bartholdi coefficients

0.99

0.93

0.90

0.88

0.89

Normalized reduced Bartholdi coefficients

0.99

0.92

0.90

0.88

0.89

Selected Ihara coefficients

0.99

0.93

0.87

0.87

0.88

Unselected Ihara coefficients

0.98

0.88

0.88

0.85

0.86

Truncated Laplacian spectra

0.93

0.87

0.85

0.85

0.87

4.5 Evaluating Methods on Real-World Datasets

Table 2 Rand indices for graphs from the ALOI dataset Classes of ALOI dataset 2

3

Reduced Bartholdi coefficients

0.91

0.96

Normalized reduced Bartholdi coefficients

0.93

0.97

Selected Ihara coefficients

0.88

0.95

Unselected Ihara coefficients

0.69

0.79

123

60

First Eigenvector

Fig. 7 Comparison of clustering performance for four classes of graphs extracted from COIL dataset. a Unselected Ihara coefficients. b Selected Ihara coefficients. c Reduced Bartholdi coefficients. d Normalized reduced Bartholdi coefficients. Comparison of clustering performance for four classes of graphs extracted from ALOI dataset. e Unselected Ihara coefficients. f Selected Ihara coefficients.

Feature vector

40

First Eigenvector

(I)

Table 1 Rand indices for graphs from the COIL dataset

−80

First Eigenvector

We compare our method with the finite difference approaches. We use K -means classifier to amount the classification accuracy on the real-world Datasets. We investigate the efficiency of the feature vectors for clustering graphs by applying Rand indices for evaluating performance where the Rand index is defined as R I = P/(P + Q), the fraction of the pairs where the two clusterings agree where P is the number of true clus-

J Math Imaging Vis Table 3 Rand indices for graphs from the ETHZ dataset

Table 4 Rand indices for trees from the BAR31 dataset

Table 5 Rand indices for trees from the BSPHERE31 dataset

Feature vector

Classes of ETHZ dataset 3

4

5

6

7

8

Reduced Bartholdi coefficients

91

91

87

86

84

85

Normalized reduced Bartholdi coefficients

91

95

87

86

84

84

Selected Ihara coefficients

77

87

80

83

84

84

Unselected Ihara coefficients

72

77

82

82

84

84

Feature vector

Classes of BAR31 dataset 10

11

12

13

14

15

Reduced Bartholdi coefficients

86

86

87

88

89

90

Normalized reduced Bartholdi coefficients

86

87

87

88

89

90

Selected Ihara coefficients

41

38

36

33

30

29

Unselected Ihara coefficients

39

37

34

33

31

29

Feature vector

Classes of BSPHERE31 dataset 10

Table 6 Rand indices for trees from the GEO31 dataset

11

12

13

14

15

Reduced Bartholdi coefficients

85.76

86.59

87.05

87.92

88.71

89.35

Normalized reduced Bartholdi coefficients

85.77

86.55

87.06

87.93

88.66

89.30

Selected Ihara coefficients

39.68

37.32

–

–

–

–

Feature vector

Classes of GEO31 dataset 10

11

12

13

14

15

Reduced Bartholdi coefficients

83.81

84.75

85.76

86.17

86.75

87.76

Normalized reduced Bartholdi coefficients

83.78

84.76

85.76

86.17

86.75

87.76

tering as agreements and Q is the number of false clustering as disagreements. The Rand index lies in the interval [0, 1], where 1 occurs when the clustering has been done perfectly. We refer the feature vectors constructed from: (1) unselected Ihara coefficients, (2) selected Ihara coefficients, (3) reduced Bartholdi coefficients and (4) normalized reduced Bartholdi coefficients, on ALOI dataset, the first four objects of the COIL dataset, and the first five objects of the ETHZ dataset. By using principal component analysis (PCA), the clustering result of the extracted feature vectors from different above approaches is shown in Fig. 7. Hence, the reduced Bartholdi coefficients produce clusters with better separation, compared to both selected and the unselected Ihara coefficients. Also, we evaluate our proposed methods on three COIL, ALOI and ETHZ datasets with different numbers of object classes and measure the accuracy of clustering by using K -means and computing the Rand index. The result of Rand indices obtained from different approaches is shown in Tables 1, 2 and 3. The reduced Bartholdi coefficients give the best accuracy, and the poorest results are obtained in the case of the unselected Ihara.

Furthermore, we compare the result of our proposed methods on the tree structure datasets: BAR31, BSPHERE31 and GEOD31 datasets with different numbers of object classes and measure the accuracy of clustering by using K -means and computing the Rand index. The result of Rand indices obtained from different approaches is shown in Tables 4, 5 and 6. Based on the results on BSPHERE31 and GEOD31, it is concluded that the Ihara zeta function is intractable for these datasets, since for the classes 12–15 of BSPHERE31 and for all the classes of GEOD31, all the coefficients of the Ihara zeta function became zero. However, the reduced Bartholdi coefficients give the admissible accuracy even for the tree structure datasets.

5 Conclusion and Future Work In this paper, we have utilized a modified version of the Bartholdi zeta function as the reduced Bartholdi zeta function and have obtained its coefficients for the aim of clustering graphs, while they can be used to construct the feature vec-

123

J Math Imaging Vis

tor for characterizing graphs. Hence, we first theoretically demonstrate the relation between the reduced Bartholdi zeta function and sink star subgraphs extracted from the original graph. In addition, by using two main theorems, we present two algorithms for calculating the coefficients of the reduced Bartholdi zeta function. Finally, we evaluate the performance of our proposed method on the random graphs and real-world graphs. Our experiments show that the reduced Bartholdi zeta function has less sensitivity to structural noises such as omitting an edge compared to the Ihara zeta function. Also, the reduced Bartholdi zeta function is more efficient in the tree structured and the real-world datasets. The coefficients of the Ihara zeta function are determined by the number of closed walks, i.e., triangles and squares in the graph with no backtracking or tails which are not the most basic characteristics from md2 graphs and concentrating on the longer length cycles instead of the edges and their incidences leads to lose some local information about the graph. Also, we can see that the proposed approach with backtracking feature based on probing star subgraphs is more effective and efficient than the Ihara approach for solving any graph datasets. In addition, while the Ihara zeta function coefficients are completely intractable in tree structure datasets, the reduced Bartholdi coefficients by considering the backtracks are expected to significantly outperform the Ihara coefficients. Our future research directions will focus on the some aspects. First, based on R-convolution kernel, one can find the dot product of two zeta function-based vectors and also decompose the graphs into simpler substructures and measure the pairwise similarities between the resulting substructures. Examples of the R-convolution kernels can be summarized into the following classes, which include graph kernels based on all pairs of (a) walks [8,62], (b) paths [21] (c) cycles [3] and (d) subgraph or subtree structures [9,39]. It would be profitable to extend our approach due to the kernelization strategies. Second, we plan to apply our approach for weighted graph, directed graphs and hypergraph where the Bartholdi zeta function can be extended for more general graphs [43,55]. Finally, based on the linear behavior of the reduced Bartholdi coefficients in terms of edit distance, it would be interesting to employ the reduced Bartholdi coefficients for estimating the edit distance between two or more graphs.

References 1. Anand, K., Bianconi, G., Severini, S.: Shannon and von Neumann entropy of random networks with heterogeneous expected degree. Phys. Rev. E 83(3), 036109 (2011)

123

2. Auwatanamongkol, S.: Inexact graph matching using a genetic algorithm for image recognition. Pattern Recognit. Lett. 28(12), 1428–1437 (2007) 3. Aziz, F., Wilson, R.C., Hancock, E.R.: Backtrackless walks on a graph. IEEE Trans. Neural Netw. Learn. Syst. (99), 1–1 (2013) 4. Borzeshi, E.Z., Piccardi, M., Riesen, K., Bunke, H.: Discriminative prototype selection methods for graph embedding. Pattern Recognit. 46(6), 1648–1657 (2013) 5. Bai, L., Escolano, F., Hancock, E.R.: Depth-based hypergraph complexity traces from directed line graphs. Pattern Recognit. 54, 229–240 (2016) 6. Bai, L., Hancock, E.R.: Graph kernels from the jensen-shannon divergence. J. Math. Imaging Vis. 47(1–2), 60–69 (2013) 7. Bai, L., Hancock, E.R.: Depth-based complexity traces of graphs. Pattern Recognit. 47(3), 1172–1186 (2014) 8. Bai, L., Rossi, L., Bunke, H., Hancock, E.R.: Attributed graph kernels using the jensen-tsallis q-differences. In Joint European conference on machine learning and knowledge discovery in databases, Springer, pp. 99–114 (2014) 9. Bai, L., Rossi, L., Zhang, Z., Hancock, E.: An aligned subtree kernel for weighted graphs. In Proceedings of the 32nd international conference on machine learning (ICML-15), pp. 30–39 (2015) 10. Bai, X., Hancock, E.R.: Recent results on heat kernel embedding of graphs, pp. 373–382. GbRPR, Springer (2005) 11. Bartholdi, L.: Counting paths in graphs, arXiv preprint arXiv:math/0012161 (2000) 12. Bass, H.: The Ihara-Selberg zeta function of a tree lattice. Int. J. Math. 3(06), 717–797 (1992) 13. Biasotti, S., Marini, S., Mortara, M., Patanè, G., Spagnuolo, M., Falcidieno, B.: 3D shape matching through topological structures, DGCI, pp. 194–203 (2003) 14. Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs, pp. 74–81. In IEEE international conference on data mining, IEEE (2005) 15. Bunke, H., Riesen, K.: Improving vector space embedding of graphs through feature selection algorithms. Pattern Recognit. 44(9), 1928–1940 (2011) 16. Chen, N., Zhu, J., Sun, F., Zhang, B.: Learning harmonium models with infinite latent features. Neural Netw. Learn. Syst. IEEE Trans. 25(3), 520–532 (2014) 17. Cooper, Y.: Properties determined by the ihara zeta function of a graph. Electron. J. Comb. 16(1) (2009) 18. Emms, D., Severini, S., Wilson, R.C., Hancock, E.R.: Coined quantum walks lift the cospectrality of graphs and trees. Pattern Recognit. 42(9), 1988–2002 (2009) 19. Ethz 53 objects datasets. http://www.vision.ee.ethz.ch/en/datasets/ 20. Escolano, F., Hancock, E.R., Lozano, M.A.: Heat diffusion: thermodynamic depth complexity of networks. Phys. Rev. E 85(3), 036206 (2012) 21. Feragen, A., Kasenburg, N., Petersen, J., de Bruijne, M., Borgwardt, K.: Scalable kernels for graphs with continuous attributes. In Advances in neural information processing systems, pp. 216– 224 (2013) 22. Ferrer, M., Valveny, E., Serratosa, F., Riesen, K., Bunke, H.: An approximate algorithm for median graph computation using graph embedding, pp. 1–4 (2008) 23. Fischer, A., Suen, C.Y., Frinken, V., Riesen, K., Bunke, H.: A fast matching algorithm for graph-based handwriting recognition, pp. 194–203. In Graph-based representations in pattern recognition, Springer (2013) 24. Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113–129 (2010) 25. Hancock, E.: Spectral approaches to learning in the graph domain, pp. 47–47 (2010)

J Math Imaging Vis 26. Harandi, M.T., Sanderson, C., Shirazi, S., Lovell, B.C.: Graph embedding discriminant analysis on Grassmannian manifolds for improved image set matching, pp. 2705–2712 (2011) 27. Harris, C., Stephens, M.: A combined corner and edge detector. In Alvey vision conference, vol. 15, Citeseer, p. 50 (1988) 28. Hashimoto, K.: Artin type l-functions and the density theorem for prime cycles on finite graphs. Int. J. Math. 3(06), 809–826 (1992) 29. Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM (JACM) 21(2), 277–292 (1974) 30. Horton, M.D.: Ihara zeta functions of irregular graphs (2006) 31. Horváth, T., Gärtner, T., Wrobel, S.: Cyclic pattern kernels for predictive graph mining. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp. 158–167 (2004) 32. Ihara, Y.: Discrete subgroups of pl (2, k). In Algebraic groups and discontinuous subgroups (Proc. Sympos. Pure Math., Boulder, Colo., 1965), pp. 272–278 (1965) 33. Ihara, Y.: On discrete subgroups of the two by two projective linear group over p-adic fields. J. Math. Soc. Jpn. 18(3), 219–235 (1966) 34. Kaltofen, E., Villard, G.: On the complexity of computing determinants. Comput. Complex. 13(3–4), 91–130 (2005) 35. Kannan, R.J., Prabhakar, R.: An improved handwritten Tamil character recognition system using octal graph (2008) 36. Kondor, R., Shervashidze, N., Borgwardt, K.M.: The graphlet spectrum. In Proceedings of the 26th annual international conference on machine learning, ACM, pp. 529–536 (2009) 37. Kotani, M., Sunada, T.: Zeta functions of finite graphs (2000) 38. Kramer, S., De Raedt, L.: Feature construction with version spaces for biochemical applications. In Proceedings of the 18th international conference on machine learning (ICML 2001), Morgan Kaufman, pp. 258–265 (2001) 39. Kriege, N., Mutzel, P.: Subgraph matching kernels for attributed graphs, arXiv preprint arXiv:1206.6483 (2012) 40. Luo, B., Wilson, R.C., Hancock, E.R.: Spectral embedding of graphs. Pattern Recognit. 36(10), 2213–2230 (2003) 41. Meusel, R., Vigna, S., Lehmberg, O., Bizer, C.: Graph structure in the web—revisited: a trick of the heavy tail. In: Proceedings of the companion publication of the 23rd international conference on World wide web companion, International World Wide Web Conferences Steering Committee, pp. 427–432 (2014) 42. Micheli, A.: Neural network for graphs: a contextual constructive approach. Neural Netw. IEEE Trans. 20(3), 498–511 (2009) 43. Mizuno, H., Sato, I.: Some weighted bartholdi zeta function of a digraph. Linear Algebra Appl. 445, 1–17 (2014) 44. Nayar, S., Murase, H.: Visual learning and recognition of 3D objects from appearance. Int. J. Comput. Vis. 14(1), 5–24 (1995) 45. Neuhaus, M., Bunke, H.: Automatic learning of cost functions for graph edit distance. Inf. Sci. 177(1), 239–247 (2007) 46. Passerini, F., Severini, S.: Quantifying complexity in networks: the von neumann entropy. Int. J. Agent Technol. Syst. (IJATS) 1(4), 58–67 (2009) 47. Qiangrong, J., Hualan, L., Yuan, G.: Cycle kernel based on spanning tree. In Electrical and Control Engineering (ICECE), 2010 International Conference on, IEEE, pp. 656–659 (2010) 48. Qureshi, R.J., Ramel, J.-Y., Cardot, H., Mukherji, P.: Combination of symbolic and statistical features for symbols recognition. In Signal processing, communications and networking. ICSCN’07. International conference on, IEEE 2007, pp. 477–482 (2007) 49. Ren, P., Wilson, R., Hancock, E.: Graph characterization via ihara coefficients. IEEE Trans. Neural Netw. 22(2), 233–245 (2011) 50. Ren, P., Aleksi´c, T., Wilson, R.C., Hancock, E.R.: A polynomial characterization of hypergraphs using the ihara zeta function. Pattern Recognit. 44(9), 1941–1957 (2011) 51. Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(4), 950–959 (2009)

52. Riesen, K., Bunke, H.: Classification and Clustering of Vector Space Embedded Graphs. World Scientific, London (2010) 53. Robles-Kelly, A., Hancock, E.R.: Graph edit distance from spectral seriation. IEEE Trans. Pattern Anal. Mach. Intell. 27(3), 365–378 (2005) 54. Rustamov, R.M.: Laplace-beltrami eigenfunctions for deformation invariant shape representation, pp. 225–233. In Proceedings of the fifth Eurographics symposium on Geometry processing, Eurographics Association (2007) 55. Sato, I., Mitsuhashi, H., Morita, H.: A generalized bartholdi zeta function for a general graph. Linear and Multilinear Algebra, pp. 1–18 (2015) 56. Schenker, A., Bunke, H., Last, M., Kandel, A.: Graph-Theoretic Techniques for Web Content Mining. World Scientific, London (2005) 57. Scott, G., Storm, C.: The coefficients of the ihara zeta function. Involve J. Math. 1(2), 217–233 (2008) 58. Sidere, N., Héroux, P., Ramel, J.Y.: Vector representation of graphs: application to the classification of symbols and letters. In 10th international conference on document analysis and recognition, IEEE, pp. 681–685 (2009) 59. Storm, C.: Extending the Ihara-Selberg zeta function to hypergraphs. Ph.D. thesis, Dartmouth College Hanover, New Hampshire (2007) 60. Storm, C.K.: The zeta function of a hypergraph. Electron. J. Comb. 13(1), R84 (2006) 61. Storm, C.K.: Some graph properties determined by edge zeta functions, arXiv preprint arXiv:0708.1923 (2007) 62. Sugiyama, M., Borgwardt, K.: Halting in random walk kernels. In Advances in neural information processing systems, pp. 1639– 1647 (2015) 63. Tahaei, M.S., Hashemi, S.N.: The coefficients of the reduced bartholdi zeta function. Linear Algebra Appl. 509, 1–18 (2016) 64. Jain, A.K., Taxt, T.: Feature extraction methods for character recognition-a survey. Pattern Recognit. 29(4), 641–662 (1996) 65. Ünay, D., Çataltepe, Z., Aksoy, S.: Recognizing patterns in signals, speech, images, and videos: ICPR 2010 contents, Istanbul, Turkey, August 23–26, 2010, contest reports, vol. 6388, Springer Science and Business Media (2011) 66. Wilson, R., Hancock, E., Luo, B.: Pattern vectors from algebraic graph theory. IEEE Trans. Pattern Anal. Mach. Intell. 27(7), 1112– 1124 (2005) 67. Xiao, B., Hancock, E.R., Wilson, R.C.: Graph characteristics from the heat kernel trace. Pattern Recognit. 42(11), 2589–2606 (2009)

Maedeh S. Tahaei received both B.S. degree and M.S. degree of Computer Science from Tehran Polytechnic University, Iran. She was a member of Algorithms and Computational Geometry Group (ACG) at the Department of Computer Science of Amirkabir University of Technology, Tehran, Iran. Her M.S. thesis focused on structural pattern recognition using geometrical tools. She is currently pursuing the Ph.D. degree of Computer Science in Amirkabir University of Technology. Her research interests include machine learning, structural pattern recognition, computational geometry and graph characterization.

123

J Math Imaging Vis Seyed Naser Hashemi an assistant professor in the Department of Mathematics and Computer Science at Amirkabir University of Technology, Iran, received his Ph.D. in 2001 from University of Waterloo, Canada. He is interested in theoretical computer science, such as approximation algorithms, randomness in computation, complexity, theory of computing, graph theory and combinatorics.

123