White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Edge-based Operators for Graph Characterization

Aziz, Furqan (2014) Edge-based Operators for Graph Characterization. PhD thesis, University of York.

Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (6Mb) | Preview


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.

Item Type: Thesis (PhD)
Keywords: Ihara zeta function Backtrackless walks on a graph Graph Kernels Edge-based Laplacian Diffusion processes on a graph Three-dimensional shape analysis
Academic Units: The University of York > Computer Science (York)
Identification Number/EthosID: uk.bl.ethos.605486
Depositing User: Mr Furqan Aziz
Date Deposited: 03 Jun 2014 11:04
Last Modified: 08 Sep 2016 13:30
URI: http://etheses.whiterose.ac.uk/id/eprint/6218

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)