See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/4309921

Shape Indexing through Laplacian Spectra

Conference Paper · October 2007

DOI: 10.1109/ICIAPW.2007.42 · Source: IEEE Xplore

CITATIONS READS
3 41

3 authors, including:

M. Fatih Demirci Remco C. Veltkamp

TOBB University of Economics and Technology Utrecht University
85 PUBLICATIONS 1,481 CITATIONS 342 PUBLICATIONS 10,701 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Remco C. Veltkamp on 23 May 2014.

The user has requested enhancement of the downloaded file.

 Shape Indexing through Laplacian Spectra

M. Fatih Demirci Reinier H. van Leuken Remco C. Veltkamp

[email protected] [email protected] [email protected]
Department of Information and Computing Sciences, Universiteit Utrecht

Abstract trieval on the web are only a few examples which are likely
to contain large collections.
With ever growing databases containing multimedia For recognition purposes, it is very common to repre-
data, indexing has become a necessity to avoid a linear sent object views by graphs whose nodes correspond to im-
search. We propose a novel technique for indexing multime- age features and whose edges indicate relations between
dia databases, whose entries can be represented as graph these features. Both nodes and edges may be labeled by
structures. In our method, the topological structure of a attributes. These graph representations express many sig-
graph as well as that of its subgraphs are represented as nificant object properties such as geometric or hierarchical
vectors in which the components correspond to the sorted structures. Such representations, however, have drawbacks:
laplacian eigenvalues of the graph or subgraphs. We draw matching two graphs is a difficult problem.
from recently-developed techniques in the field of spectral Graph matching problems are often formulated as largest
integral variation to overcome the problem of computing isomorphic subgraph problems, for which a rich body of re-
the laplacian spectrum for every subgraph individually. By search exists in the literature. This problem has been stud-
doing a nearest neighbor search around the query spectra, ied for both theoretical and practical interests. While it is an
similar but not necessarily isomorphic graphs are retrieved. open question whether the detection of graph isomorphism
The novelties of the proposed method come from the pow- can be solved in polynomial time, the problem of subgraph
erful representation of the graph topology and successfully isomorphism is known to be NP-complete [7].
adopting the concept of spectral integral variation in an in-
When working with graph structures, indexing is formu-
dexing algorithm. Our experiments, consisting of recog-
lated as the problem of efficiently selecting a small set of
nition trials in the domain of 2-D and 3-D object recog-
database graphs, which share a subgraph with the query.
nition, including a comparison with a competing indexing
One important indexing method is a decision tree approach.
method, demonstrate both the robustness and efficacy of the
Here, the goal is to hierarchically partition the database so
approach.
that the query is first matched to the root. Depending on the
result of this match, the query is then matched to either the
right or the left child of the root. This process is repeated
1 Introduction recursively until a match is found at an internal node (or
leaf), or it exits with a failure indicating no database graphs
Shape matching is one of the fundamental problems in are isomorphic to the query. Messmer and Bunke [13] use
computer vision. In a typical matching problem the objec- this approach to organize the set of all permutations of the
tive is to compute an overall similarity value between an adjacency matrix of database graphs in a decision tree. At
unknown shape (query) and a model, and to find the corre- run time, the (sub)graph isomorphisms from the query to
spondences between their feature sets. The similarity value the database graphs are found by a decision tree traversal.
between two shapes can be used for shape recognition by A significant drawback of this method is its space require-
using stored exemplars for different shape classes as mod- ment. All permutations of the adjacency matrix have to be
els. A linear search of a database, i.e., computing the sim- encoded in decision trees, whose sizes grow exponentially
ilarity between the query and each database entry and se- with the size of the database graph. A set of pruning tech-
lecting the closest one, is inefficient for large database sys- niques is discussed to cut down the space complexity.
tems. Therefore, an effective and efficient indexing mecha- Although indexing methods with (sub)graph isomor-
nism is essential to select a small collection of candidates to phism detection algorithms are effective, due to noise, oc-
which the actual matching process is applied. Criminology, clusion, or segmentation errors, no (sub)graph isomorphism
medicine, trademark retrieval, and content-based image re- may exist between the query and the database. Furthermore,
only a certain degree of similarity between two graphs are simple. Two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 )
may be present. The indexing problem, therefore, is re- are isomorphic, if there is a bijection f : V1 → V2 such
formulated as efficiently retrieving database graphs whose that for any vertex pair u and v ∈ V1 , (u, v) ∈ E1 iff
(sub)structure is similar to the query. Although consider- (f (u), f (v)) ∈ E2 .
able research has been devoted to the problem of inexact The adjacency matrix A of a graph G = (V, E) is
(or error-tolerant) graph matching, rather less attention has a |V | × |V | matrix whose element with row index u and
been paid to this type of indexing based on graph structures. column index v is 1 if there exists an edge between u and
A framework related to the approach reported in this pa- v, and 0 otherwise. Let D(G) be the diagonal P matrix of
per is that of Shokoufandeh et al. [17]. This framework is vertex degrees with elements of D(u, u) = v∈V A(u, v).
designed especially for tree structures in which the sum of The matrix L(G) = D(G) − A(G) is called the laplacian
the largest eigenvalues of the adjacency matrix for each sub- matrix of G. 1 The laplacian matrix is a positive semidefi-
tree of the root form the component of its δ−dimensional nite and symmetric matrix with at least one zero eigenvalue.
vector, where δ is the root degree. To account for occlu- The multiplicity of zero as an eigenvalue of L(G) is equal
sion and local deformation, these vectors are also computed to the number of connected components in the graph. This
for the root of each subtree. At indexing time, each non- implies that the second smallest eigenvalue known as alge-
leaf node of the query is represented as such a vector, and braic connectivity is positive if and only if G is connected.
a nearest neigbor search is performed for each vector. Al- There exist many important theorems about laplacian ma-
though effective, by summing up the largest eigenvalues one trices and in many problems in physics and chemistry they
loses uniqueness, resulting in less representative graphs in play a central role. The reader is referred to [15, 16, 12, 14]
the vector space. In addition, it is not clear how this ap- for surveys on this topic.
proach can be extended to general graph structures. The spectrum of a graph’s laplacian matrix is obtained
In this paper, we propose a novel approach to the graph- from its eigendecomposition. Specifically, the eigende-
based indexing problem. Instead of using the adjacency composition of a laplacian matrix is L(G) = P ΛP T ,
matrix for graph characterization as done by some earlier where Λ = diag (λ1 , λ2 , . . . , λ|V | ) is the diagonal ma-
work, we characterize our graphs based on the laplacian trix with the eigenvalues in increasing order and P =
spectrum, which is more natural, more important, and more (p1 |p2 | . . . |p|V | ) is the matrix with the ordered eigenvec-
informative about the input graphs [14]. Given a graph, the tors as columns. The laplacian spectrum is the set of eigen-
sorted eigenvalues of its laplacian matrix become the com- values {λ1 , λ2 , . . . , λ|V | }. The spectrum is permutation-
ponents of its signature, which is linear in the number of invariant, i.e., two isomorphic graphs have the same set of
vertices. To perform indexing locally as well and thus to en- sorted eigenvalues. However, the converse is not true, as
code the topology of subgraphs in the framework, we adopt two graphs that have the same spectra are not necessarily
a technique analogous to that used in the decision tree ap- isomorphic.
proach [13]. Having established the signatures, the index- Two graphs are called cospectral (or, isospectral) if
ing now amounts to a nearest neighbor search around the they have the same eigenvalues. Previously, Godsil and
query signatures in a model database. We draw on an im- McKay [8] and more recently Haemers and Spence [10]
portant theorem from spectral graph theory to show that our have shown that the laplacian matrix has more represen-
graph characterization can be used to retrieve similar graphs tational power than the adjacency matrix, in terms of re-
or subgraphs from large database systems through a nearest sulting in less number of cospectral graphs. According to
neighbor search. the results given in [10], of more than a billion graphs with
11 vertices characterized by the adjacency matrix, approxi-
2 Definitions and Preliminaries mately 21% is cospectral, while this fraction is only 9% for
the laplacian matrix. As specific graph classes, trees were
also investigated for cospectrality by Zhu and Winson [22].
Before describing our framework, some definitions are
The authors report that out of more than two million trees
in order. A graph G is a pair (V, E), where V is a finite set
with 21 vertices, 21.3% of them do not have a unique adja-
of vertices and E is a set of connections (edges) between
cency spectrum. With the laplacian spectrum, this ratio de-
the vertices. The size of a graph is defined as the number
creases to 0.05%. Overall, these studies show that the lapla-
of vertices. An edge e = (u, v) connects two vertices such
cian spectrum is more representative and more informative
that u, v ∈ V . A graph G = (V, E) is called edge-weighted
than the adjacency spectrum. Our motivation for construct-
if each edge e ∈ E has a weight w(e) ∈ R. Unweighted
ing the graph characterizations using the laplacian spectrum
graphs are a special case of weighted graphs, where each
comes from these studies.
of the edges has weight 1. A graph is simple if it does not
contain loops or multiple edges and thus its edge set con- 1 The laplacian matrix is also called Kirchhoff matrix or the matrix of

sists of distinct pairs. All graphs considered in this paper admittance in the literature.
3 Encoding The Graph Structure g1
s1 s1
G = (V, E) .
Given a query and a large database, our objective in an
.
.
.
.
indexing mechanism is to efficiently retrieve a small set
.
gl
.

of candidates, which share topological similarity with the sl

.
.
.
query or one of its subgraphs. We assume that the database .
.
.
.
.
sl
graphs are known in advance and the query graph is given
.
. . .
gO(2|V | )
at run time only. In our framework, we encode the topol-
sO(2|V | ) .
sO(2|V | )

ogy of a graph through the laplacian spectrum. Specifically,

sorted eigenvalues of the laplacian matrix are assigned to (a) (b) (c) (d)

the graph as its signature. To compute the similarity be- Figure 1: Retrieving similar graphs. For graphs given in Part (a), its sub-
graphs are constructed in Part (b). A signature is computed for each sub-
tween two graphs, we compute the Euclidean distance be- graph in Part (c). Given a signature, retrieving its similar graphs from a
tween their signatures, which is inversely proportional to large database is formulated as a nearest neighbor search as shown in Part
the structural similarity of the graphs. For a given query, re- (d).
trieving similar graphs can be reduced to a nearest neighbor
based on both local and global similarities. To account for
search among a set of points. Note that it is important to
local as well as global information in our framework, we
construct the signatures using the sorted eigenvalues, as the
will adopt the following method analogous to that used in
kth smallest eigenvalue reflects specific information about
the decision tree approach [13].
the graph, e.g., the relation between the second smallest
For a given database graph, rather than storing its signa-
laplacian eigenvalue λ2 and the diameter, mean distance,
ture in the system only, we compute the signatures of each
minimum degree, and algebraic connectivity of the graph.
subgraph of G in our algorithm. In this process, we grad-
Unfortunately, the above formulation cannot support oc-
ually increase the size of the subgraphs. Since the sorted
clusion or segmentation errors: two graphs may share sim-
eigenvalues are invariant under consistent re-orderings of
ilar structures up to only some level. Although adding or
the graph’s vertices, it is sufficient to compute the spectrum
removing graph structure changes the laplacian spectrum,
of permutation-similar matrices once. This property avoids
the spectrum of the subgraphs that survive such alteration
the need for a high-load compilation process described for
will not be affected. Therefore, our indexing mechanism
adjacency matrices in the decision tree approach.
cannot depend on the signature of the whole graph only. In-
Associated with each signature in the system is a pointer
stead, we will combine the signatures of the subgraphs with
to the corresponding graph or subgraph in the database.
our indexing mechanism.
At runtime, we first generate the signature of each sub-
Let G = (V, E) be a graph and let G0 be a graph obtained
graph of the query. Given a query signature sq , we then
from G by adding a new edge e0 such that e0 ∈ / E. Then
retrieve its nearest neighbors of the same size from the
the following theorem, known as the interlacing theorem,
database through a nearest neighbor search (see Figure 1).
relates the laplacian spectrum of both graphs 2 .
Each neighbor of sq retrieved from the database gets a vote
Theorem 1 The eigenvalues of G and G0 interlace: whose value is inversely proportional to the distance from
sq . Thus, as a result, each signature of the query generates a
0 = λ1 (G) = λ1 (G0 ) ≤ λ2 (G) ≤ λ2 (G0 ) ≤ set of votes. Moreover, we weigh the votes according to the
. . . ≤ λn (G) ≤ λn (G0 ) size of the subgraphs corresponding to the signatures, i.e.,
Pn the bigger the size, the more weight the vote receives.
In addition, it is known that i=1 (λi (G0 )−λi (G)) = 2 [1]. After performing a nearest neighbor search around the
Therefore, at least one inequality is strict. Overall this the- query signatures, we compute the weights of the votes be-
orem implies the following. Assume that we are given a tween the query and the database graphs having at least one
pair of isomorphic graphs g1 and g2 . If we construct G1 signature as the nearest neighbor of the query. We then sort
and G2 out of g1 and g2 by adding different edges to each the database graphs based on these weights. In this process,
of them, one at a time, the laplacian spectra of G1 and G2 we only add the sufficiently high-support database graphs
become proportionally less similar. As a result, the similar- to the indexing hypothesis. Since a small number of struc-
ity between the signatures of G1 and G2 may not reflect the turally different graphs may also share the same laplacian
similarity between the signatures of their subgraphs g1 and spectrum, each graph in the hypothesis should still be veri-
g2 . Constructing the indexing mechanism based on graph fied by some matching algorithm. Despite the fact that such
signatures is, therefore, too weak. An ideal indexing frame- graphs may exist in the indexing hypothesis, the number of
work should, in fact, select candidate database elements them is very small. In addition, based on Theorem 1, not
2 This theorem is obtained by Courant-Weyl([3], Theorem 2.1). The only do isomorphic graphs share the same signature, non-
reader may also refer to [9]. isomorphic but similar graphs or subgraphs have close sig-
natures in the vector space. The database, therefore, can be
pruned without losing structurally similar graphs.

4 More Efficient Indexing through Spectral

Integral Variation
Figure 2: Left: a view of a bat. Right: the shock graph constructed from
The local indexing procedure described above requires the medial axis and superimposed on the left image.

individual computation of the laplacian spectrum for each components, only the positive eigenvalues of Ĝ are used as
subgraph. Although for database graphs known a priori the signature. Next, when we add an edge to Ĝ, we check
this process is performed offline, in applications where new whether spectral integral variation occurs and if so, we gen-
database entries are being inserted frequently, this step plays erate the eigenvalues using the theorems referred above. We
an important role in the efficiency of the whole system. In then repeat this process and consider all subgraphs until the
this section, we draw on recent-developed techniques from whole graph is constructed. At run time, we also apply the
the domain of spectral integral variation to avoid the indi- same procedure to construct the signatures for query graphs.
vidual computation of the laplacian spectrum for each sub- In the experiments, we have generated the signatures for
graph. Specifically, we will study the effect on the laplacian (sub)graphs with at least k = 4 edges.
spectrum when an edge is added into graph G = (V, E). Although the above formulation enables us to identify
Let G + e be a graph obtained by adding an edge e = (u, v) the changed laplacian eigenvalues when they are increased
into G such that {u, v} ∈ V and e ∈ / E. Our interest in by integer quantities only, our empirical results show that it
this topic is motivated by its ability to identify the changed speeds up the signature generation step for a database with
eigenvalues of graph G, and therefore to generate the lapla- 1440 graphs known a priori by 6.47%.
cian spectrum of graph G + e without computing it. Before
we focus on this topic, let us first reconsider Theorem 1,
which shows that when an edge is added into the graph, 5 Experiments
none of its laplacian eigenvalues can decrease, while the
trace of the laplacian matrix increases by 2. This impor- To examine the fitness of the new indexing framework,
tant observation implies that given the laplacian spectrum we have performed a number of experiments using an ex-
of G, one can estimate the ranges of eigenvalues for G + e. tensive set of recognition trials in the domain of 2-D and
The concept of spectral integral variation, on the other hand, 3-D object recognition, including a comparison with a com-
provides more information. peting indexing method. We first perform our experiments
It is shown in [20] that if an edge is added to a graph using silhouettes. For a given shape, its silhouette is rep-
and the laplacian spectrum changes by integer quantities, resented by an undirected shock graph [19]. The graph is
there can only be two possibilities: either one eigenvalue constructed from the discrete skeleton using the method de-
increases by 2 (and n − 1 eigenvalues remain fixed) or two scribed in [5]. An illustration of this type of graph is given
eigenvalues increase by 1 (and n − 2 eigenvalues remain in Figure 2, where the left portion shows an input image
fixed). These two cases are called spectral integral variation taken from the database, while the right portion presents
in one place and spectral integral variation in two places. the constructed shock graph superimposed on top of the im-
In our framework, we will detect the changed eigen- age. We used the MPEG-7 dataset CE-Shape-1 part B for
value(s) in the cases where spectral integral variation oc- this representation type. The MPEG-7 database consists of
curs. For this purpose, we draw on two theorems that ap- 70 classes and 20 shapes per class.
pear in [20] and [11]. We refer to these papers or to the We also conduct our experiments in the domain of 3D
full version of this paper [6] for the specific use of these object recognition using Reeb graphs. These graph repre-
theorems. sentations allow for topological properties to be represented
After detecting changed laplacian eigenvalues when in a coarse sense. See [2] for details on the construction of
spectral integral variation occurs, we perform the follow- Reeb graphs. The right of Figure 3 shows a Reeb graph
ing process for each given database graph offline. Suppose constructed for the image shown in the left. The second
that the minimum number of edges in a subgraph for which database used in the experiments consists of Reeb graphs
we compute the signature is k. Given a database graph constructed for the McGill 3D Shape Benchmark [21]. The
G = (V, E), we first create its subgraph Ĝ with |V | vertices database consists of 420 objects classified in 19 classes.
and k edges and compute its laplacian eigenvalues. Since We first represent each object in each database as a
the second smallest laplacian eigenvalue is positive if and graph. The average size of a graph in each database is 35.
only if the graph is connected and the multiplicity of zero Given a graph, we compute the signatures for each of its
as a laplacian eigenvalue reflects the number of connected subgraphs and populate the resulting signatures in the vec-
 C RITERIA HW(%) AP WP PC(%) PI(%)
S HOCK , L APL . 37.3% 7.4 12 99% 90%
R EEB , L APL . 29.6% 4.3 9 97% 87%
S HOCK , A DJ . 18.0% 19.1 23 97% 82%
R EEB , A DJ . 17.3% 10.2 22 94% 78%

Table 1: Results for indexing systems constructed using eigenvalues for

Figure 3: The Reeb graph constructed for the object on the left is shown Laplacian and Adjacency matrices. HW: Percentage of highest-weighted
on the right. graph belonging to the same class as the query, AP: Average position of
the closest matching graph from the query class, WP: Worst position of the
tor space. In our experimental setup, we applied the follow- closest matching graph from the query class, PC: Percentage of database
ing leave-one-out procedure to the datasets for evaluation. that can be pruned to determine the right query class, PI: Percentage of
We initially remove the first graph from the database and database that can be pruned to retrieve all instances of the query.
use it as a query for the remaining database graphs. The
and Reeb graph datasets, respectively. In other words, the
graph is then put back in the database, and the procedure is
recall in each dataset is 100% if the scope is set to the first
repeated with the second graph from the database, etc., until
10% and 13% of the sorted candidate models for shock and
all database graphs have been used as a query.
Reeb graphs respectively.
There exist several performance measures to assess the
Additionally, we compare our indexing framework to the
quality of a retrieval system or indexing mechanism. Pre-
one presented in [17]. This indexing algorithm was used
cision and recall are two well-known examples. In some
in [21] on a subset of the McGill dataset with the object
applications high precision is necessary, meaning that the
parts represented by directed acyclic graphs (DAG) through
relevant items that are returned must be at the top of the
medial surfaces [18]. The subset of the McGill dataset used
ranking. In some other applications, however, high recall
in this experiment includes a total of 320 exemplars taken
is preferred, meaning that false negatives are to be avoided
from several object classes (hands, humans, teddy bears,
(the returned result must contain all or the most relevant
glasses, pliers, tables, chairs, cups, airplanes, birds, dol-
objects). A good indexing system should, in fact, perform
phins, dinosaurs, four-legged animals, and fish). To be con-
well according to both of these two measures. We con-
sistent with the test in [21], we also merge the categories
ducted two sets of experiments to cover both scenarios. In
“four-legged” and “dinosaurs” into a broader class, “four-
the first experiment, the class of the query should be deter-
limbs”. The results reported in [21] indicate that on average
mined quickly (best match must appear high in the ranking).
70% of the models from the same class as the query are
In the second experiment, all the objects belonging to the
in the top 80 (25 % of 320). Moreover, for 9 out of these
query class should be returned in a small candidate set.
13 object classes, all instances of the query are in the top
The results for these experiments are presented in Ta-
80. Our results, on the other hand, show that 100% of the
ble 1. For comparison purposes, the same experiments
query classes are always in the top 48 (15 % of 320). The
were conducted with the adjacency spectrum representa-
improvement clearly demonstrates the better efficacy ob-
tion. For each query, the database graphs are ranked in
tained by the proposed indexing framework. We believe that
decreasing order of the vote weights. In in 37.3% of the
the improvement is due to 1) more powerful representation
cases, the highest-weight database graph belongs to the cor-
obtained by laplacian matrices, 2) more effective signature
rect shape class for shock graphs and this ratio is 29.6% for
construction by our algorithm, i.e., low loss of uniqueness
Reeb graphs. Moreover, the average position of the closest
in the signature, and, 3) better encoding of local topology.
matching graph among the highest-weight candidates is 7.4
and 4.3 for shock and Reeb graphs, respectively. In addi-
tion, the worst position of the closest matching graph is 12 6 Conclusions and Future Work
for shock graphs, while this number is 9 for Reeb graphs.
These results present that to determine the correct class of In this paper, we have proposed a novel, graph-based
the query, more than 99% and 97% of shock and Reeb graph indexing method using the eigenvalue characterization of
datasets can be pruned by our indexing mechanism. laplacian matrices. The sorted eigenvalues of the lapla-
In the second experiment, the system’s performance is cian matrix of a graph G = (V, E) become the compo-
evaluated by computing the total number of retrieved im- nents of an O(|V |)-dimensional vector. A nearest neighbor
ages that is necessary to retrieve the entire query class (max- search around this vector returns graphs that are similar to
imum minimal scope). Our results show that the first 134 of G. This implies that no graph isomorphism is required; our
the candidate return set always contains all the graphs be- method retrieves those graphs that are similar in terms of
longing to the query class for shock graphs; this number their topologies. To account for partial similarities, we cre-
is 54 for Reeb graphs. This indicates that for this task our ate signatures for subgraphs of G. We draw from recently-
framework prunes more than 90% and 87% of the shock developed techniques in the field of spectral integral varia-
tions to overcome the problem of computing the laplacian References
spectrum for every subgraph individually.
[1] W. N. Anderson and T. D. Morley. Eigenvalues of the lapla-
By using the laplacian spectrum as a signature, we cap- cian of a graph. Linear and Multilinear Algebra, 18:141–
ture the graph topology to a large extent. The signature of a 145, 1985.
[2] S. Biasotti. Reeb graph representation of surfaces with
graph is invariant under the reorderings of its vertices. This
boundary. In SMI’04, pages 371–374, Washington, DC,
allows us to compare the signatures of a large number of
USA, 2004.
graphs without solving the computationally expensive cor- [3] D. Cvetković, M. Doob, and H. Sachs. Spectra of Graphs:
respondence problem between their vertices. Although de- Theory and Application. VEB Deutscher Verlag der Wis-
termining graphs that can uniquely be defined by their graph senschaften, Berlin, 2nd edition, 1982.
spectra is a difficult problem [4], we showed in this paper [4] E. R. V. Dam and W. H. Haemers. Spectral characterizations
that representing graphs by their laplacian spectra is more of some distance-regular graphs. Journal of Algebraic Com-
binatorics, 15(2):189–202, 2002.
discriminating than by adjacency spectra. [5] M. F. Demirci, A. Shokoufandeh, Y. Keselman, L. Bretzner,
and S. Dickinson. Object recognition as many-to-many fea-
We plan to extend our work in a number of ways. We ture matching. IJCV, 69(2):203–222, 2006.
will first incorporate geometric information in the indexing [6] M. F. Demirci, R. van Leuken, and R. Veltkamp. Indexing
system and combine it with the topological similarity during through laplacian spectra, 2007. Computer Vision and Im-
age Understanding, Special Issue on Similarity Matching in
the process of fast candidate selection. We believe that this
Computer Vision and Multimedia (to appear).
important addition will make the whole system more effec- [7] M. R. Garey and D. S. Johnson. Computers and Intractabil-
tive. Rather than evaluating our results using the classifica- ity: A Guide to the Theory of NP-Completeness. W. H. Free-
tion performed on the original dataset, we will use different man & Co., New York, NY, USA, 1979.
sets of existing matching algorithms and measure the fitness [8] C. Godsil and B. McKay. Constructing cospectral graphs. In
of the framework. In addition, we plan to conduct a more Aequationes Mathematicae, pages 257– 268, 1982.
[9] R. Grone, R. Merris, and V. S. Sunder. The laplacian spec-
comprehensive comparison of our approach to more lead-
trum of a graph. SIAM Journal on Matrix Analysis and Ap-
ing indexing algorithms, including a test regarding the time plications, 11:218–238, 1990.
efficiency of each system. Since our framework computes [10] W. H. Haemers and E. Spence. Enumeration of cospectral
a proper topological similarity between graph pairs, one of graphs. Eur. J. Comb., 25(2):199–211, 2004.
our future goals is also to design a matching approach based [11] S. Kirkland. A characterization of spectral integral variation
on a similar idea. We will not only compute the similar- in two places for laplacian matrices. Linear and Multilinear
Algebra, 52(2):79–98, 2004.
ity value between graphs, but also find the node correspon- [12] R. Merris. Laplacian matrices of graphs: a survey. In Linear
dences using both topology and geometry. Although our ex- Algebra Applications, volume 199, pages 381–389, 1994.
periments present promising retrieval results for databases [13] B. Messmer and H. Bunke. A decision tree approach to graph
of sizes 1400 and 420, we will also evaluate our framework and subgraph isomorphism detection. Pattern Recognition,
on large datasets (more than around 10000 images). 32(12):1979–1998, 1999.
[14] B. Mohar. The laplacian spectrum of graphs. In Sixth In-
ternational Conference on the Theory and Applications of
Our proposed indexing framework has been designed to Graphs, pages 871–898, 1988.
account for both occlusion and local deformation. In one of [15] B. Mohar. Laplace eigenvalues of graphs: a survey. Discrete
our future works, we will perform a set of occlusion exper- Math., 109(1-3):171–183, 1992.
iments and report the performance of the system. Finally, [16] B. Mohar. Some applications of laplace eigenvalues of
graphs, 1997.
we will also study in detail how the concept of spectral in- [17] A. Shokoufandeh, D. Macrini, S. Dickinson, K. Siddiqi, and
tegral variation changes the time efficiency of our indexing S. Zucker. Indexing hierarchical structures using graph spec-
system. To measure this, we will compute the time it takes tra. PAMI, 27(7), 2005.
to construct the signature for each database graph with and [18] K. Siddiqi, S. Bouix, A. Tannenbaum, and S. W. Zucker. The
without spectral integral variation. Improving the time ef- hamilton-jacobi skeletons. IJCV, 48(3):215–231, 2002.
[19] K. Siddiqi, A. Shokoufandeh, S. Dickinson, and S. Zucker.
ficiency of the signature construction process for database
Shock graphs and shape matching. IJCV, 30:1–24, 1999.
graphs known a priori is especially important for applica- [20] W. So. Rank one perturbation and its application to the lapla-
tions where new database entries are being inserted fre- cian spectrum of a graph. Linear and Multilinear Algebra,
quently. 46:193–198, 1999.
[21] J. Zhang, K. Siddiqi, D. Macrini, A. Shokoufandeh, and S. J.
Dickinson. Retrieving articulated 3-d models using medial
Acknowledgments This research was supported by surfaces and their graph spectra. In EMMCVPR, 2005.
the FP6 IST projects 511572-2 PROFI and 506766 [22] P. Zhu and R. C. Wilson. A study of graph spectra for com-
AIM@SHAPE. We thank Simone Marini, IMATI-CNR paring graphs. In British Machine Vision Conference, 2005.
Italy, for providing the Reeb graphs.

View publication stats