# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 5 Graph Matching
(2018) and represents the relationship of a given vertex to its neighborhood in terms of simulated heat diffusion. For each vertex, the signature records the amount of heat \(s_{u}(t)\) left at the vertex at a number of times assuming a unit amount of heat is put on the vertex initially. The HKS for each vertex is expressed as \(h(t,\lambda_{k})=e^{-t\lambda_{k}}\) and is intrinsic, meaning that, if two graphs are isomorphic, then the signatures of corresponding vertices are the same, i.e., equivalent vertices dissipate heat similarly. The signatures are also stable under small perturbations ([PERSON], 2018). Hence, the similarity between two vertices can be evaluated by comparing their HKS. However, for each vertex, the heat diffusion should be influenced by the size of the region. As in a real environment, a smaller room should diffuse heat to neighboring rooms faster than a larger room. Without taking the size of a region into account, every vertex will diffuse heat in the same way and important information given by the segmentation will be lost during the matching. Thus, each vertex is associated with a weight corresponding to the standardized size attribute of the corresponding region, as illustrated in Figure 5. We use the standardized size of regions to reduce scaling errors between the sketch and metric maps. However, the graph Laplacian used by [PERSON] and [PERSON] (2018) for the LFS is expressed with weights on the edges instead of the vertices. Indeed, the generalized graph Laplacian is defined as the difference between the diagonal matrix of the vertex degree and \(\mathcal{A}\) is the graph adjacency matrix:  
\[\mathcal{A}= \begin{cases}w(i,j)&\text{if }(i,j)\in\mathcal{E}\\ 0&\text{otherwise}\end{cases}  \tag{6}\]  
with \(\mathcal{E}\) the set of edges in the graph \(\mathcal{G}\) and \(w\) the weights on the edges, i.e., \(w:\mathcal{E}\mapsto\mathbb{R}^{+}\). \[\mathcal{L}= \begin{cases}\sum_{z\sim v}a_{z}&\text{if }u=v\\ -\sqrt{\alpha_{v}a_{u}}&\text{if }u\sim v\\ 0&\text{otherwise}\end{cases}  \tag{7}\]where vertex \(v\) has weight \(\alpha_{v}\) and \(u\sim v\) means that the vertex \(u\) and \(v\) are adjacent. To express the graph Laplacian, and by extension the LFS, with weights on the vertices instead, we use the formulation proposed by [PERSON] and [PERSON] [32]. To be able to use the graph Laplacian defined in Equation (7) to find the eigenvectors and values of the graph, which are necessary for the LFS, one needs to prove that \(\mathcal{L}\) is symmetric and positive semi-definite. Since this aspect of \(\mathcal{L}\) was not shown by [PERSON] and [PERSON] [32], we show that \(\mathcal{L}\) is indeed symmetric and positive semi-definite. We can define the incidence matrix \(\mathcal{B}\) as in the work of [PERSON] and [PERSON] [32]:  
\[\mathcal{B}= \begin{cases}\sqrt{\alpha_{v}}&\text{if }e=\{u,v\},u=v_{i},v=v_{j}, \text{and }i\leq j\\ -\sqrt{\alpha_{v}}&\text{if }e=\{u,v\},u=v_{i},v=v_{j},\text{and }i>j\\ 0&\text{otherwise}\end{cases}  \tag{8}\]  
Thus, we have \(\mathcal{L}=\mathcal{B}^{T}\mathcal{B}\). If we consider the eigen decomposition of \(\mathcal{L}\) with unit-norm eigenvector \(\phi_{i}\) and corresponding eigenvalue \(\lambda_{n}\), we have:  
\[\lambda_{n} =\phi_{i}^{T}\mathcal{L}\phi_{i} \tag{9}\] \[=\phi_{i}^{T}\mathcal{B}^{T}\mathcal{B}\phi_{i}\] \[=(B\phi_{i})^{T}(\mathcal{B}\phi_{i})\]  
Since \(\lambda_{n}\) can be written as the inner product of the vector \(\mathcal{B}\phi_{i}\) with itself, this shows that \(\lambda_{n}\geq 0\) and so the eigenvalues of \(\mathcal{L}\) are all non-negative and \(\mathcal{L}\) is positive-semidefinite, allowing us to use the eigenvectors and eigenvalues of \(\mathcal{L}\). The LFS in Equation (3) represents the structural relationship of a vertex compared to its neighbors. Instead, we want the LFS to represent the structural relationship of the vertex compared to the set of anchors found in Sections 4.2 and 4.3. Thus, we use the heat kernel value of anchor vertices at a given vertex, as presented by [PERSON] et al. [33].