In this work we design graph neural network architectures that can be used to
obtain optimal approximation algorithms for a large class of combinatorial
optimization problems using powerful algorithmic tools from semidefinite
programming (SDP). Concretely, we prove that polynomial-sized message passing
algorithms can represent the most powerful polynomial time algorithms for Max
Constraint Satisfaction Problems assuming the Unique Games Conjecture. We
leverage this result to construct efficient graph neural network architectures,
OptGNN, that obtain high-quality approximate solutions on landmark
combinatorial optimization problems such as Max Cut and maximum independent
set. Our approach achieves strong empirical results across a wide range of
real-world and synthetic datasets against both neural baselines and classical
algorithms. Finally, we take advantage of OptGNN's ability to capture convex
relaxations to design an algorithm for producing dual certificates of
optimality (bounds on the optimal solution) from the learned embeddings of
OptGNN.

我们设计了图神经网络架构，利用半定规划的强大算法工具，来获得一类组合优化问题的最优逼近算法。通过研究，我们证明了多项式大小的消息传递算法可以表示 Max Constraint Satisfaction Problems 的最强多项式时间算法（基于 Unique Games Conjecture）。我们利用这一结果构建了高效的图神经网络架构 OptGNN，在最大割和最大独立集等经典组合优化问题上获得了高质量的近似解。我们的方法在各种真实和合成数据集上取得了强有力的实证结果，超过了神经基准和传统算法。最后，我们利用 OptGNN 捕捉凸松弛的能力，设计了一个从 OptGNN 学习的嵌入中产生对优解的对偶证明的算法。

图神经网络是否最优逼近算法？

Are Graph Neural Networks Optimal Approximation Algorithms?

The low-rank matrix approximation problem with respect to the component-wise
$\ell_1$-norm ($\ell_1$-LRA), which is closely related to robust principal
component analysis (PCA), has become a very popular tool in data mining and
machine learning. Robust PCA aims at recovering a low-rank matrix that was
perturbed with sparse noise, with applications for example in
foreground-background video separation. Although $\ell_1$-LRA is strongly
believed to be NP-hard, there is, to the best of our knowledge, no formal proof
of this fact. In this paper, we prove that $\ell_1$-LRA is NP-hard, already in
the rank-one case, using a reduction from MAX CUT. Our derivations draw
interesting connections between $\ell_1$-LRA and several other well-known
problems, namely, robust PCA, $\ell_0$-LRA, binary matrix factorization, a
particular densest bipartite subgraph problem, the computation of the cut norm
of $\{-1,+1\}$ matrices, and the discrete basis problem, which we all prove to
be NP-hard.

本篇论文证明了基于分量的 l1 - 范数的低秩矩阵逼近问题是 NP-hard 的， 并与其它著名问题进行了有趣的联系。

论鲁棒主成分分析和 L1 范数低秩矩阵逼近的复杂度

On the Complexity of Robust PCA and $\ell_1$-norm Low-Rank Matrix  Approximation

We investigate the notion of stability proposed by Bilu and Linial. We obtain
an exact polynomial-time algorithm for $\gamma$-stable Max Cut instances with
$\gamma \geq c\sqrt{\log n}\log\log n$ for some absolute constant $c > 0$. Our
algorithm is robust: it never returns an incorrect answer; if the instance is
$\gamma$-stable, it finds the maximum cut, otherwise, it either finds the
maximum cut or certifies that the instance is not $\gamma$-stable. We prove
that there is no robust polynomial-time algorithm for $\gamma$-stable instances
of Max Cut when $\gamma < \alpha_{SC}(n/2)$, where $\alpha_{SC}$ is the best
approximation factor for Sparsest Cut with non-uniform demands.
Our algorithm is based on semidefinite programming. We show that the standard
SDP relaxation for Max Cut (with $\ell_2^2$ triangle inequalities) is integral
if $\gamma \geq D_{\ell_2^2\to \ell_1}(n)$, where $D_{\ell_2^2\to \ell_1}(n)$
is the least distortion with which every $n$ point metric space of negative
type embeds into $\ell_1$. On the negative side, we show that the SDP
relaxation is not integral when $\gamma < D_{\ell_2^2\to \ell_1}(n/2)$.
Moreover, there is no tractable convex relaxation for $\gamma$-stable instances
of Max Cut when $\gamma < \alpha_{SC}(n/2)$. That suggests that solving
$\gamma$-stable instances with $\gamma =o(\sqrt{\log n})$ might be difficult or
impossible.
Our results significantly improve previously known results. The best
previously known algorithm for $\gamma$-stable instances of Max Cut required
that $\gamma \geq c\sqrt{n}$ (for some $c > 0$) [Bilu, Daniely, Linial, and
Saks]. No hardness results were known for the problem. Additionally, we present
an algorithm for 4-stable instances of Minimum Multiway Cut. We also study a
relaxed notion of weak stability.

研究 Bilu 和 Linial 提出的稳定性概念，提出了一个基于半定编程的精确多项式算法解决具有 γ 稳定性的 Max Cut 问题，对于 γ <α_SC (n/2) 的情况，不存在可解决的凸松弛方法，此外还研究了最小多路径切问题的 4 - 稳定性。

Bilu-Linial 稳定的最大割和最小多路割实例

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

We describe a new approximation algorithm for Max Cut. Our algorithm runs in
$\tilde O(n^2)$ time, where $n$ is the number of vertices, and achieves an
approximation ratio of $.531$. On instances in which an optimal solution cuts a
$1-\epsilon$ fraction of edges, our algorithm finds a solution that cuts a
$1-4\sqrt{\epsilon} + 8\epsilon-o(1)$ fraction of edges.
Our main result is a variant of spectral partitioning, which can be
implemented in nearly linear time. Given a graph in which the Max Cut optimum
is a $1-\epsilon$ fraction of edges, our spectral partitioning algorithm finds
a set $S$ of vertices and a bipartition $L,R=S-L$ of $S$ such that at least a
$1-O(\sqrt \epsilon)$ fraction of the edges incident on $S$ have one endpoint
in $L$ and one endpoint in $R$. (This can be seen as an analog of Cheeger's
inequality for the smallest eigenvalue of the adjacency matrix of a graph.)
Iterating this procedure yields the approximation results stated above.
A different, more complicated, variant of spectral partitioning leads to an
$\tilde O(n^3)$ time algorithm that cuts $1/2 + e^{-\Omega(1/\eps)}$ fraction
of edges in graphs in which the optimum is $1/2 + \epsilon$.

本研究提出了一种基于谱分割的近似算法，可以在多项式时间内解决 max cut 问题，并取得了高质量的结果。