An Eigendecomposition Approach to Weighted Graph Matching Problems

By S. Umeyama. 1988

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning shape correspondence with anisotropic convolutional neural networks (2016, background): “Several approaches formulate the correspondence problem as quadratic assignment and employ different relaxations thereof [Ume88,LH05,RBA ∗ 12,CK15,KKBL15].”
Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition (2001, methodology): “For instance, Umeyama has an eigendecomposition method that matches graphs of the same size [13].”
A Path Following Algorithm for the Graph Matching Problem (2008, unknown): “This approach was pioneered by Umeyama [13], while further diﬀerent methods based on spectral representations were proposed in [3–5,14,15].”
Thirty Years Of Graph Matching In Pattern Recognition (2004, unknown): “…[32], Pardalos98 [117], Shinano98 [143], Cordella00 [28], Cordella01 [29], Koch01 [81], Larrosa02[86] Special Kind of Graphs Inexact Matching Umeyama88[157], Carcassoni01[21], Kosinov01[83], Xu01[173], Shokoufandeh01[144] Tsai79[154], Ghahraman80[59], Shapiro81[136], Sanfeliu83[132],…”
Finding Matches in a Haystack: A Max-Pooling Strategy for Graph Matching in the Presence of Outliers (2014, background): “Since graph matching is mathematically expressed as a quadratic assignment problem [8], which is NP-hard, most research has long focused on developing accurate and efficient approximate algorithms [14, 27].”
Shape Matching and Object Recognition Using Shape Contexts (2002, background): “The work of Sclaro and Pentland [50] is representative of the eigenvector- or modalmatching based approaches; see also [52, 51, 57].”
Link prediction by de-anonymization: How We Won the Kaggle Social Network Challenge (2011, background): “Weighted graph matching has been studied in [29], [4].”
Matching with shape contexts (2000, background): “Earlier examples of approaches in this vein can be found in [23, 22, 27].”
Decoding brain states from fMRI connectivity graphs (2011, methodology): “Full graph matching algorithms (e.g., Umeyama, 1988) are commonly used to obtain distances between graphs, which is a basic operation of pattern recognition.”
A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks (2017, methodology): “Existing tractable algorithms for the QAP include spectral alignment methods [29] and methods based on semidefinite programming relaxations [32; 13].”
Graph Invariant Kernels (2015, unknown): “For this reason, starting from the seminal work of Umeyama (1988), spectral methods have been popular in pattern recognition as graph matching tool.”
Robust 3D Shape Correspondence in the Spectral Domain (2006, methodology): “Through formal arguments and numerous experiments, we demonstrate that our approach outperforms previous methods which operate on spectral embeddings [7, 8, 31, 33], as well as schemes that find correspondence in the spatial domain via non-rigid iterative closest points [6] or the use of local shape”
View-based 3-D object recognition using shock graphs (2002, methodology): “For instance, in [57], Umeyama matches same-size, weighted graphs by an eigendecomposition method that finds the permutation matrix that minimizes the difference of the graphs’ arcs’ weights.”
Image Matching from Handcrafted to Deep Features: A Survey (2020, methodology): “With Koopmans–Beckmann’s QAP formulation, the spectral methods (Umeyama 1988; Scott and Longuet-Higgins 1991; Shapiro and Brady 1992; Caelli and Kosinov 2004) relax X to be orthogonal, i.e.”
A review of multimodal image matching: Methods and applications (2021, methodology): “In detail, spectral relaxation methds commonly convert this task as an eigenvector solving problem, hich can be solved by a discretization strategy [241,242], replicator quation from evolutionary game theory [243], nonnegative matrix facorization approach [244], a probabilistic interpretation strate”
Word Translation Without Parallel Data (2017, background): “As a simple baseline, we tried to match the first two moments of the projected source and target embeddings, which amounts to solving W ? ∈ argminW ‖(WX) (WX) − Y Y ‖F and solving the sign ambiguity (Umeyama, 1988).”