Spectral Simplification of Graphs
Abstract
Although inexact graph-matching is a problem of potentially exponential complexity, the problem may be simplified by decomposing the graphs to be matched into smaller subgraphs. If this is done, then the process may cast into a hierarchical framework and hence rendered suitable for parallel computation. In this paper we describe a spectral method which can be used to partition graphs into non-overlapping subgraphs. In particular, we demonstrate how the Fiedler-vector of the Laplacian matrix can be used to decompose graphs into non-overlapping neighbourhoods that can be used for the purposes of both matching and clustering.
Cite
Text
Qiu and Hancock. "Spectral Simplification of Graphs." European Conference on Computer Vision, 2004. doi:10.1007/978-3-540-24673-2_10Markdown
[Qiu and Hancock. "Spectral Simplification of Graphs." European Conference on Computer Vision, 2004.](https://mlanthology.org/eccv/2004/qiu2004eccv-spectral/) doi:10.1007/978-3-540-24673-2_10BibTeX
@inproceedings{qiu2004eccv-spectral,
title = {{Spectral Simplification of Graphs}},
author = {Qiu, Huaijun and Hancock, Edwin R.},
booktitle = {European Conference on Computer Vision},
year = {2004},
pages = {114-126},
doi = {10.1007/978-3-540-24673-2_10},
url = {https://mlanthology.org/eccv/2004/qiu2004eccv-spectral/}
}