Skeletal Graphs from Schrödinger Magnitude and Phase

Francisco Escolano, Edwin R. Hancock, Miguel Angel Lozano

Abstract

Given an adjacency matrix, the problem of finding a simplified version of its associated graph is a challenging one. In this regard, it is desirable to retain the essential connectivity of the original graph in the new representation. To this end, we exploit the magnitude and phase information contained in the Schrödinger Operator of the Laplacian. Recent findings based on continuous-time quantum walks suggest that the long-time averages of both magnitude and phase are sensitive to long-range interactions. In this paper, we depart from this hypothesis to propose a novel representation: skeletal graphs. Using the degree of interaction (or “long-rangedness”) as a criterion we propose a structural level set (i.e. a sequence of graphs) from which it emerges the simplified graph. In addition, since the same theory can be applied to weighted graphs, we can analyze the implications of the new representation in the problems of spectral clustering, hashing and ranking from computer vision. In our experiments we will show how coherent transport phenomenon implemented by quantum walks discovers the long-range interactions without breaking the structure of the manifolds on which the graph or its connected components are embedded.
BibTeX
@inproceedings{escolano2015skeletal,
  author = {Francisco Escolano and Edwin R. Hancock and Miguel Angel Lozano},
  title = {{Skeletal Graphs from Schrödinger Magnitude and Phase}},
  booktitle = {GbRPR},
  year = {2015},
  doi = {10.1007/978-3-319-18224-7\_33},
}

Loading related content...

Figure