Edge-based Operators for Graph Characterization

This thesis addresses problems in computer vision and pattern recognition using graphs. The particular focus is on graph matching and characterization using edge-based operators. The thesis commences with a brief introduction in Chapter 1, followed by a review of the relevant literature in Chapter 2. The remainder of the thesis is organized as follows.

Chapter 3 discusses the structure of the Ihara coefficients and presents efficient methods to compute these coefficients. One of our contributions in this chapter is to propose a O(k|V|^3) worst-case running time algorithm to compute the set of first k Ihara coefficients.Chapter 4 proposes efficient methods for characterizing labelled as well as unlabelled graphs. One of our contributions in this chapter is to propose a graph kernel based on backtrackless walks for labelled graphs, whose worst-case running time is the same as that of the kernel defined using random walks.

The next part of the thesis discusses the edge-based Laplacian and its applications. Chapter 5 introduces the concept of a metric graph and the eigensystem of the edge-based Laplacian. Our novel contribution in this chapter is to fully explore the eigenfunctions of the edge-based Laplacian and develop a method for explicitly calculating the edge-interior eigenfunctions. In Chapter 6, we define a wave equation on a graph and give a complete solution. The solution is used to define a signature to classify weighted as well as unweighted graphs. Chapter 7 presents another application of the edge-based Laplacian, where the edge-based heat diffusion process is used to define a signature for points on the surface of a three-dimensional shape. It is called the edge-based heat kernel signature (EHKS) and it can be used for shape segmentation, correspondence matching and shape classification. Finally, in Chapter 8 we provide concluding remarks and discuss directions for future research.