Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis

DOI10.1007/S10208-022-09570-YzbMath1522.90091arXiv1907.08880WikidataQ114228257 ScholiaQ114228257MaRDI QIDQ6072326

Yihong Wu, Jiaming Xu, Zhou Fan, Cheng Mao

Publication date: 13 October 2023

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.08880

zbMATH Keywords

quadratic programmingconvex relaxationsquadratic assignment problemrandom matrix theoryspectral methodsgraph matching

Mathematics Subject Classification ID

Convex programming (90C25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

Statistical limits for testing correlation of random hypergraphs ⋮ A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The eigenvector moment flow and local quantum unique ergodicity
• Hanson-Wright inequality and sub-Gaussian concentration
• Improved random graph isomorphism
• Rate of convergence to the semi-circular law
• Rate of convergence in probability to the Marchenko-Pastur law
• Fifty years of graph matching, network alignment and network comparison
• Eigenvectors distribution and quantum unique ergodicity for deformed Wigner matrices
• The graph matching problem
• Superconcentration and Related Topics
• On convex relaxation of graph isomorphism
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• Emergence of Scaling in Random Networks
• Convex Relaxations for Permutation Problems
• Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
• An Introduction to Random Matrices
• An eigendecomposition approach to weighted graph matching problems
• Distinguishing Vertices of Random Graphs
• Continuity of the map $S \to \left| S \right|$ for linear operators
• High-Dimensional Probability
• Spectral alignment of correlated Gaussian matrices
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Seeded graph matching via large neighborhood statistics
• Seeded graph matching for correlated Erd\H{o}s-R\'enyi graphs
• Concentration and Moment Inequalities for Polynomials of Independent Random Variables
• Exact matching of random graphs with constant correlation
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality

This page was built for publication: Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis