Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory
Authors: Zhou Fan, Cheng Mao, Yihong Wu, Jiaming Xu
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. This section is devoted to comparing our spectral method to various existing algorithms for graph matching, using both synthetic examples and real datasets. |
| Researcher Affiliation | Academia | Zhou Fan 1 Cheng Mao 2 Yihong Wu 1 Jiaming Xu 3 1Department of Statistics and Data Science, Yale University, New Haven, Connecticut, USA 2School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, USA 3The Fuqua School of Business, Duke University, Durham, North Carolina, USA. |
| Pseudocode | Yes | Algorithm 1 GRAph Matching by Pairwise eigen Alignments (GRAMPA) 1: Input: Weighted adjacency matrices A and B on n vertices, and a bandwidth parameter η > 0. 2: Output: A permutation bπ Sn. 3: Construct the similarity matrix i,j=1 w(λi, µj) uiu i Jvjv j Rn n (3) where J Rn n denotes the all-ones matrix and w is the Cauchy kernel of bandwidth η: w(λ, µ) = 1 (λ µ)2 + η2 . (4) 4: Output the permutation estimate bπ by rounding b X to a permutation, e.g., by solving the linear assignment problem (LAP) bπ = argmax π Sn i=1 b Xi,π(i). (5) |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the methodology described. |
| Open Datasets | Yes | We use a subset of the Autonomous Systems dataset from the University of Oregon Route Views Project (University of Oregon Route Views Project), available as part of the Stanford Network Analysis Project (Leskovec & Krevl, 2014; Leskovec et al., 2005). In this section, we evaluate the performance of GRAMPA on the SHREC 16 dataset (L ahner et al., 2016)... |
| Dataset Splits | No | The paper mentions '15 for training and 10 for testing' for the SHREC 16 dataset but does not provide specific details on the dataset splits (percentages, sample counts, or methodology) for its own experiments, nor does it explicitly mention the use of a validation set for hyperparameter tuning. |
| Hardware Specification | No | The paper discusses computational efficiency and experiment runtime but does not specify any particular hardware (e.g., GPU models, CPU types, or memory) used for running its experiments. |
| Software Dependencies | No | The paper mentions general algorithms and solvers (e.g., 'Hungarian algorithm', 'QP solvers', 'ADMM procedure') but does not specify any software dependencies with version numbers (e.g., specific libraries, frameworks, or programming language versions) used for implementation or experimentation. |
| Experiment Setup | Yes | For simplicity and consistency, we fix η = 0.2 in the following synthetic experiments. Here, for simplicity, we apply both methods to the unnormalized adjacency matrices, and set η = 1 for GRAMPA. we apply our GRAMPA algorithm with η = 1 to the unweighted adjacency matrices of the mesh graphs, without using the training data. |