# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 5 Graph Matching
### Planar Graph Matching Using the Laplacian Family Signature  
We extend the planar graph matching method presented in our previous work [3] to use the LFS. Our solution to the graph matching problem is a neighbor expanding matching strategy. To initialize the matching process, the matching algorithm starts by finding a set of pairs of vertices, also called seeds, between a graph \(G\) and a corresponding graph \(G^{\prime}\). How to find the seeds is described below. From each seed, the algorithm finds the correspondences between the vertices of their neighborhoods by considering all permutations of ordered neighbors and keeping the one that yields the minimum normalized Levenshtein edit distance [34]. The Levenshtein edit distance is the minimum number of single edits between two sequences required to change one sequence into the other. Given two vertices' neighborhoods, we consider as possible changes: removing a vertex and all of its edges, adding a vertex and an edge, or replacing a vertex. Each removal, replacement, or vertex creation is one edit. Thus, removing a vertex and all its edges has a cost of \(1+n\) with \(n\) the number of edges associated with the vertex. On the other hand, adding a vertex and an edge has a cost of 2 and replacing a vertex a cost of 1. Then, to find all correspondences between vertices of the graphs, the neighborhood matching process is repeated for newly obtained vertex-to-vertex correspondences until no correspondence is left to expand.Once all seeds have been expanded, the final solution to the matching problem is the one with the lowest cost when adding both the cost of all correspondences and the cost of removing, in both graphs, all vertices without a correspondence, and their associated edges. See Algorithm 1 for the pseudocode of the matching algorithm and Figure 6 for an illustration of the calculation of the Levenshtein edit distance between two neighbors. ```
Data: seeds Result:matching
1 to_explore = {};
2 whileseeds is not empty do
3 add first element ofseeds toto_explore;
4 remove first element ofseeds;
5 hypothesis = {};
6 whileto_explore is not empty do
7 pair = first element ofto_explore;
8 remove first element ofto_explore;
9 addpair tohypothesis;
10 min_permutation = the permutation of the neighborhoods of the two vertices inpair that minimizes the normalized Levenshtein edit distance;
11 foreverycorrespondence inmin_permutationdo
12 ifbothvertices incorrespondence are not already inhypothesisthen
13 addcorrespondence toto_explore;
14 ifcorrespondence is inseedsthen
15 removecorrespondence fromseeds;
16 edit_distance = get edit distance fromhypothesis;
17 addhypothesis and edit_distance tohypothesis_all;
18 matching=hypothesis in hypotheses_all with the smallest edit_distance;
19 returnmatching;
```  
**Algorithm 1**Graph-Edit-Distance matching algorithm. To decide when to remove or replace a vertex, the Levenshtein edit distance needs a comparison measure between vertices. We define the comparison measure between two vertices as the mean absolute difference between their heat kernel anchor distances \(s_{u}^{an}(t)\) over \(n_{l}\) times samples, starting from 0 and with a sampling time of \(n\):  
\[c(v,v^{\prime})=\frac{\sum_{i=0}^{n_{l}}|s_{u}^{an}(i*n)-s_{v^{\prime}}^{an}(i* n)|}{n_{l}} \tag{11}\]  
where \(u\) is a vertex of the graph \(G\) and \(u^{\prime}\) a vertex of \(G^{\prime}\). Since \(s_{u}^{an}(t)\) is bounded between 0 and 1, Equation (11) is also bounded between 0 and 1. The vertices are replaced or removed only if they are sufficiently different from each other up to a certain threshold \(m\), i.e., \(c(v,v^{\prime})\leq m\). Stability to the threshold \(m\) is evaluated in Section 6.4. Similarly, we find the seeds by calculating \(c(v,v^{\prime})\) for every possible correspondence between the vertices of \(G\) and \(G^{\prime}\). If \(c(v,v^{\prime})\leq m\), we create a new seed for the matching algorithm.