Graph matching plays a central role in such fields as computer vision,
pattern recognition, and bioinformatics. Graph matching problems can be cast as
two types of quadratic assignment problems (QAPs): Koopmans-Beckmann's QAP or
Lawler's QAP. In our paper, we provide a unifying view for these two problems
by introducing new rules for array operations in Hilbert spaces. Consequently,
Lawler's QAP can be considered as the Koopmans-Beckmann's alignment between two
arrays in reproducing kernel Hilbert spaces (RKHS), making it possible to
efficiently solve the problem without computing a huge affinity matrix.
Furthermore, we develop the entropy-regularized Frank-Wolfe (EnFW) algorithm
for optimizing QAPs, which has the same convergence rate as the original FW
algorithm while dramatically reducing the computational burden for each outer
iteration. We conduct extensive experiments to evaluate our approach, and show
that our algorithm significantly outperforms the state-of-the-art in both
matching accuracy and scalability.

本文提出了在 Hilbert 空间中的一些规则，引入了新的外积算法，可以在重现核 Hilbert 空间中将 Lawler 的 QAP 视为 Koopmans-Beckmann 的对齐，有效地解决了大规模亲和力矩阵的问题。提出基于熵正则化的 Frank-Wolfe 算法 (EnFW) 对 QAP 进行优化，具有与原始 FW 算法相同的收敛速率，同时显著减少每个外层迭代的计算负担，实验表明我们提出的算法在匹配准确性和可扩展性方面显著优于现有技术。

KerGM: 基于核函数的图匹配

KerGM: Kernelized Graph Matching

In this paper, we present a majorized semismooth Newton-CG augmented
Lagrangian method, called SDPNAL$+$, for semidefinite programming (SDP) with
partial or full nonnegative constraints on the matrix variable. SDPNAL$+$ is a
much enhanced version of SDPNAL introduced by Zhao, Sun and Toh [SIAM Journal
on Optimization, 20 (2010), pp.~1737--1765] for solving generic SDPs. SDPNAL
works very efficiently for nondegenerate SDPs but may encounter numerical
difficulty for degenerate ones. Here we tackle this numerical difficulty by
employing a majorized semismooth Newton-CG augmented Lagrangian method coupled
with a convergent 3-block alternating direction method of multipliers
introduced recently by Sun, Toh and Yang [arXiv preprint arXiv:1404.5378,
(2014)]. Numerical results for various large scale SDPs with or without
nonnegative constraints show that the proposed method is not only fast but also
robust in obtaining accurate solutions. It outperforms, by a significant
margin, two other competitive publicly available first order methods based
codes: (1) an alternating direction method of multipliers based solver called
SDPAD by Wen, Goldfarb and Yin [Mathematical Programming Computation, 2 (2010),
pp.~203--230] and (2) a two-easy-block-decomposition hybrid proximal
extragradient method called 2EBD-HPE by Monteiro, Ortiz and Svaiter
[Mathematical Programming Computation, (2013), pp.~1--48]. In contrast to these
two codes, we are able to solve all the 95 difficult SDP problems arising from
the relaxations of quadratic assignment problems tested in SDPNAL to an
accuracy of $10^{-6}$ efficiently, while SDPAD and 2EBD-HPE successfully solve
30 and 16 problems, respectively.

提出了 SDPNAL+，一种用于半定规划（SDP）的 majorized semismooth Newton-CG 增广 Lagrange 方法。 它结合了收敛的 3 块交替方向乘法方法和矩阵变量上部分或全部非负约束的优化方法。 与其他两种代码相比，提出的方法不仅快速而且稳健，而且可以高效地解决所有从 SDPNAL 测试的 95 个困难 SDP 问题，同时另外两个方法分别只能成功解决 30 个和 16 个问题。

SDPNAL$+$: 半定规划带非负约束的主化半平滑牛顿 - CG 增广拉格朗日方法

SDPNAL$+$: A Majorized Semismooth Newton-CG Augmented Lagrangian Method  for Semidefinite Programming with Nonnegative Constraints

Quadratic assignment problems (QAPs) arise in a wide variety of domains,
ranging from operations research to graph theory to computer vision to
neuroscience. In the age of big data, graph valued data is becoming more
prominent, and with it, a desire to run algorithms on ever larger graphs.
Because QAP is NP-hard, exact algorithms are intractable. Approximate
algorithms necessarily employ an accuracy/efficiency trade-off. We developed a
fast approximate quadratic assignment algorithm (FAQ). FAQ finds a local optima
in (worst case) time cubic in the number of vertices, similar to other
approximate QAP algorithms. We demonstrate empirically that our algorithm is
faster and achieves a lower objective value on over 80% of the suite of QAP
benchmarks, compared with the previous state-of-the-art. Applying the
algorithms to our motivating example, matching C. elegans connectomes
(brain-graphs), we find that FAQ achieves the optimal performance in record
time, whereas none of the others even find the optimum.

本文介绍了一种快速的近似二次分配算法（FAQ），能够更高效地在大数据和图值数据上处理 QAP 问题，通过在 C.elegans 连通图匹配案例上的实证表明其优越性。