Graphs as a data structure can widely be used for representing complex data like road networks or blood vessels. Graphs are being used in different fields including mathematics, pattern recognition, machine vision and geography. By representing data as graphs the task of finding similarities between two datasets can be converted to a problem called graph matching.
Graphs generally represented by two main elements: points that are called nodes and links which connect nodes that are called edges. Graph matching is the process of finding structural similarities between two graphs (Riesen and Bunke, 2009). Graph matching problem is a NP-hard problem, so the main focus of researches in graph matching is on optimizing the current algorithms to find more efficient algorithms in case of speed and accuracy (Caetano et al., 2009).
2.3.1 Graph matching techniques
Several different algorithms have been introduced to give approximate solutions for graph matching problem, and each of them has their own application, in continuation Some of these approaches are briefly explained.
9
Feature extraction and embedding is one approach used for graph matching. Cheong and his colleagues (Cheong et al., 2009) in Measuring the Similarity of Geometric Graphs use it to find similarities between geometric graphs in 2D space. They used this method for some shape matching problems like recognition of symmetries in molecules. In their technique they defined a heuristic distance function called landmark distance. Landmarks which are sets of nodes collected from each graph are used in landmark distance. Then, the Earth Mover’s distance is used to find similarities between two geometric graphs. Selection of landmarks for each graph is the main step of their technique. After all, their approach is not efficient and it cannot be used for matching graphs with different number of nodes (Armiti and Gertz, 2014;
Cheong et al., 2009).
Graph spectra is another approach which is commonly used in pattern recognition for graph matching. Umeyama (1988) illustrates an estimated solution for undirected and directed weighted graph matching problem using node to node adjacency matrix and the Hungarian algorithm. Cho (Cho et al., 2010) introduced an interpretation of random walk view graph matching algorithm. They did that by Introducing an association graph which includes nodes as candidate correspondences and edges as pairwise compatibilities between candidate correspondences. They utilized the Pagerank algorithm and Sinkhorn normalization. Their algorithm is not efficient and it’s memory consuming since the size of the adjacency matrix grows at a quartic rate with respect to the graph size (Armiti and Gertz, 2014; Umeyama, 1988; Cho et al., 2010).
Another approach which is used commonly in graph matching is Continuous optimization. Graph matching is inherently a discrete optimization problem, but using this technique it can be cast into continuous, nonlinear optimization problem.
After that an optimization algorithm should be found to solve this problem. One method which is based on this technique utilizes relaxation labeling. The main concept is that each node of one of the graphs can be labeled from a discrete set of labels, and that label defines correspondence of this node with a node of the other graph. There is a vector of the probabilities for each candidate label for each node which are computed based on node attributes, node connectivity and other available information. Armiti and Gertz (2013) introduced a probabilistic technique for graph matching which works by selecting the top-k similar pairs of nodes from both graphs
10
as seeds for the match, and after that, iteratively, they expanded the match using a probabilistic voting scheme. There is a limitation for this technique which is that the match between two nodes is estimated by only the similarity of their direct neighbors, and non-neighboring nodes are not taken into account (Armiti and Gertz, 2014; Conte et al., 2004).
Graph edit distance (GED) is another approach used for inexact graph matching. The inexact graph matching is based on finding a distortion or variation between two graphs, where an exact match may not be found. The main idea of GED is to search for the sequence of edit operations that transforms one graph to be the same as another graph with the minimum cost. Graph edit distance can be computed for both attributed and unattributed graphs, and directed and undirected graphs. On the other side GED is not so complicated to implement (Armiti and Gertz, 2013; Armiti and Gertz, 2014; Gao et al., 2010). GED will be explained in details in next section.
2.3.2 Graph Edit Distance
Graph edit distance (GED) is one of the most flexible and error tolerant techniques for graph matching. The main idea is to compute the total cost of the edit operations that are needed to transform one graph to be identical to another. GED has been extended from the string edit distance which is used to determine the similarity between two strings, and is calculated based on the minimum number of insertions, deletions, and substitutions required to transform one string into the other (Riesen, 2015; Ristad et al., 1998). In this research we represent graph as g = (V, E) where V is the set of nodes or vertices and E is the set of edges.
Let us assume two graphs g1 = (V1, E1) and g2 = (V2, E2), the idea is to transform g1
to g2 with a set of standard edit operations including insertions, deletions, and substitutions of both nodes and edges. Assuming ε refers to the empty node, let us denote the substitution of two nodes u ∈ V1 and v ∈ V2 by (u → v), the deletion of node u ∈ V1 by (u → ε), and the insertion of node v ∈ V2 by (ε → v). We use the same notations for edge edit operations (Riesen, 2015).
We can define an edit path λ(g1, g2) as a set of n edit operations {e1, . . . , en } that transforms g1 into g2. We can call a subset of λ a partial edit path. Since the edge edit operations are implied by node edit operations we can assume that edit path λ(g1, g2) contains only node edit operations (Riesen, 2015).
11
For example, let us define two undirected and labeled graphs g1 and g2 as shown in Figure 2.2:
g1 g2
Figure 2.2. Graphs g1 and g2.
The edit path between them can be defined as:
λ = {(u5 → ε), (u4 → ε), (u1 → v1), (u2 → v2), (u3 → v3)}.
(u5 → ε) (u4 → ε) (u1 → v1) (u2 → v2) (u3 → v3) Figure 2.3. The sequence of edit operations between g1 and g2.
Let us assume γ(g1, g2) denotes all complete edit paths between g1 and g2 , c denotes
Cost function c defines the strength c(ei) of edit operation ei. Since there are infinite edit paths between two graphs, we need some conditions on cost function to limit the size of γ(g1, g2) to include a finite number of edit paths. These conditions are (Riesen, 2015):
12 - Non-negativity :
c(e) ≥ 0, for all node and edge edit operations e.
- Triangle inequality:
c(u → w) ≤ c(u → v) + c(v → w), c(u → ε) ≤ c(u → v) + c(v → ε), c(ε → v) ≤ c(ε → u) + c(u → v) - Symmetry:
c(e) = c(e−1), (e−1 denotes the inverse edit operation to e)
Considering two graphs g1 with n nodes and g2 with m nodes the number of possible edit paths between g1 and g2 is O(mn). Defining a proper cost function is essential in graph matching algorithm which are based on edit distance technique (Riesen, 2015).
The graph edit distance is often computed by using a tree search algorithm which searches for all possible mappings of the edges and nodes between two graphs. Often A*-based search algorithm which is utilizing some heuristics are used in this technique (Riesen and Bunke, 2009; Riesen, 2015).
As mentioned in section 1.1, this research is based on collecting annotated images of blood vessels in human eye, and we represent these annotations by graphs, so graph edit distance will be used for evaluating the quality of annotations. Next chapter will describe the method used in this research.
13
3 FRAMEWORK
This chapter is focused on the method of the research and data collection part of the thesis and contains 4 sections. As mentioned before, in this research annotated blood vessels in eye are represented as graphs, and a graph edit distance is used to compare and evaluate the annotated images. In previous chapter we’ve reviewed the background of graph edit distance. The GED method used in this research is explained in section 3.1. Section 3.2 is focused on the original database of the images and selected sub database for this research. The selected participants which in context of crowdsourcing are called crowd are explained in 3.3. The technical information about the web application which is developed exclusively for this research is described in section 3.4.