Spectral Graph Correspondences
Judith Hermanns · 2022
Graph correspondence problems occur whenever we aim at establishing correspondences between nodes or parts of two or more graphs. In this thesis, we focus on two correspondence problems: graph alignment and subgraph localization. In graph alignment, nodes of a graph $G$ are aligned to their counterparts in $G'$. In subgraph localization, the problem is to localize a query graph $Q$ in a larger graph $G$. Due to their closeness to graph isomorphism problems, both tasks are deemed computationally challenging. In this thesis we consider these problems on undirected, unattributed graphs. Given that in these cases only the structure of the graph is available, we investigate how these problems can be tackled by spectral graph theory. Spectral graph theory deals with the question which properties of the graph can be inferred from the spectrum of the graph. The spectrum of the graph are the eigenvalues of the graph laplacian. The laplacian is a graph descriptor comprising all structural information of a graph. In a first contribution, we develop the spectral graph alignment method GRASP by framing the problem of aligning nodes as a problem of mapping node-specific functions across graphs. We establish the notion of unrestricted graph alignment as graph alignment which only uses the graph structure as an input. We evaluate our approach against other unrestricted graph alignment methods and find that it outperforms other scalable methods. In a second contribution, we structure the previously unstructured field of unrestricted graph alignment algorithms by developing an evaluation framework together with benchmark datasets and we evaluate algorithms previously not compared against each other on real and synthetic data. In a third contribution, we tackle the problem of subgraph localization by aligning the spectra of the query graph $Q$ and the larger graph $G$. As subgraph localization with only structural information on large graphs has not been convincingly tackled yet, we evaluate our method against a state-of-the-art graph alignment algorithm and show that the former is superior in localization quality.