Seeded graph matching
Open accessThe DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
Given two graphs, the graph matching problem is to align the two vertex sets so as to minimize the number of adjacency disagreements between the two graphs. The seeded graph matching problem is the graph matching problem when we are first given a partial alignment that we are tasked with completing. In this article, we modify the state-of-the-art approximate graph matching algorithm “FAQ” of Vogelstein et al. (2015) to make it a fast approximate seeded graph matching algorithm, adapt its applicability to include graphs with differently sized vertex sets, and extend the algorithm so as to provide, for each individual vertex, a nomination list of likely matches. We demonstrate the effectiveness of our algorithm via simulation and real data experiments; indeed, knowledge of even a few seeds can be extremely effective when our seeded graph matching algorithm is used to recover a naturally existing alignment that is only partially observed.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
An algorithm for quadratic programming
Frank, M., & Wolfe, P. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030109 · Cited by 3,030 · cited 5×
“We first briefly review the Frank-Wolfe Method before proceeding to apply it.”
MethodInfluentialMatrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248
Structural Properties of the Caenorhabditis elegans Neuronal Network
Varshney, L. R., Chen, B. L., Paniagua, E., Hall, D. H., & Chklovskii, D. B. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1001066 · Cited by 867 · cited 2×
“elegans is a roundworm that has been extensively studied (see for example [43, 44, 45, 46]).”
Background
Cited by
The connectome of an insect brain
Winding, M., Pedigo, B. D., Barnes, C. L., Patsolic, H. G., Park, Y., Kazimiers, T., Fushiki, A., Andrade, I. V., Khandelwal, A., Valdes-Aleman, J., et al. (2023) · Science · doi:10.1126/science.add9330 · Cited by 435
“We employed a family of techniques based on the Fast Approximate Quadratic (FAQ) graph matching algorithm (30, 31) to predict bilateral neuron pairs on the basis of connectivity.”
MethodSelf-citationMarin, E. C., Morris, B. J., Stürner, T., Champion, A. S., Krzeminski, D., Badalamente, G., Gkantia, M., Dunne, C. R., Eichler, K., Takemura, S.-Y., et al. (2024) · doi:10.7554/elife.97766.1 · Cited by 44
Marin, E. C., Morris, B. J., Stürner, T., Champion, A. S., Krzeminski, D., Badalamente, G., Gkantia, M., Dunne, C. R., Eichler, K., Takemura, S.-Y., et al. (2023) · doi:10.1101/2023.06.05.543407 · Cited by 33
Marin, E. C., Morris, B. J., Stürner, T., Champion, A. S., Krzeminski, D., Badalamente, G., Gkantia, M., Dunne, C. R., Eichler, K., Takemura, S.-Y., et al. (2024) · eLife · doi:10.7554/elife.97766 · Cited by 13
Do Vision and Language Encoders Represent the World Similarly?
Maniparambil, M., Akshulakov, R., Dahou Djilali, Y. A., Seddik, M. E. A., Narayan, S., Mangalam, K., & O'Connor, N. E. (2024) · 2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr52733.2024.01359 · Cited by 7
Metadata
- Authors
- Fishkind, D. E., Adali, S., Patsolic, H. G., Meng, L., Singh, D., Lyzinski, V., & Priebe, C. E.
- Venue
- Pattern Recognition
- Publisher
- Elsevier BV
- Published
- 2019-03
- Volume
- 87
- Pages
- 203-215
- ISSN
- 0031-3203 (ISSN-L)
- OpenAlex
- W1586001150
- Cited by
- 74
- References
- 4
- FWCI
- 4.11
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.