We consider the Steiner tree problem on graphs where we are given a set of
nodes and the goal is to find a tree sub-graph of minimum weight that contains
all nodes in the given set, potentially including additional nodes. This is a
classical NP-hard combinatorial optimisation problem. In recent years, a
machine learning framework called learning-to-prune has been successfully used
for solving a diverse range of combinatorial optimisation problems. In this
paper, we use this learning framework on the Steiner tree problem and show that
even on this problem, the learning-to-prune framework results in computing
near-optimal solutions at a fraction of the time required by commercial ILP
solvers. Our results underscore the potential of the learning-to-prune
framework in solving various combinatorial optimisation problems.

本文使用基于机器学习的学习剪枝框架来解决史泰纳树问题，结果显示该框架可在商业整数线性规划求解器所需时间的一小部分时间内计算出近乎最优的解决方案，进一步证明了学习剪枝框架在解决各种组合优化问题方面的潜力。

在图中学习剪枝斯坦纳树问题的实例

Learning to Prune Instances of Steiner Tree Problem in Graphs

Binarized Neural Networks (BNNs) have recently attracted significant interest
due to their computational efficiency. Concurrently, it has been shown that
neural networks may be overly sensitive to "attacks" - tiny adversarial changes
in the input - which may be detrimental to their use in safety-critical
domains. Designing attack algorithms that effectively fool trained models is a
key step towards learning robust neural networks. The discrete,
non-differentiable nature of BNNs, which distinguishes them from their
full-precision counterparts, poses a challenge to gradient-based attacks. In
this work, we study the problem of attacking a BNN through the lens of
combinatorial and integer optimization. We propose a Mixed Integer Linear
Programming (MILP) formulation of the problem. While exact and flexible, the
MILP quickly becomes intractable as the network and perturbation space grow. To
address this issue, we propose IProp, a decomposition-based algorithm that
solves a sequence of much smaller MILP problems. Experimentally, we evaluate
both proposed methods against the standard gradient-based attack (FGSM) on
MNIST and Fashion-MNIST, and show that IProp performs favorably compared to
FGSM, while scaling beyond the limits of the MILP.

本文研究了使用组合和整数优化来攻击二值化神经网络的问题，提出一种混合整数线性规划（MILP）的解决方案。实验表明，与标准梯度攻击（FGSM）相比，所提出的 IProp 算法表现良好，同时超越了 MILP 的限制。

二进制神经网络的组合攻击

Combinatorial Attacks on Binarized Neural Networks

Submodular functions are a fundamental object of study in combinatorial
optimization, economics, machine learning, etc. and exhibit a rich
combinatorial structure. Many subclasses of submodular functions have also been
well studied and these subclasses widely vary in their complexity. Our
motivation is to understand the relative complexity of these classes of
functions. Towards this, we consider the question of how well can one class of
submodular functions be approximated by another (simpler) class of submodular
functions. Such approximations naturally allow algorithms designed for the
simpler class to be applied to the bigger class of functions. We prove both
upper and lower bounds on such approximations.
Our main results are:
1. General submodular functions can be approximated by cut functions of
directed graphs to a factor of $n^2/4$, which is tight.
2. General symmetric submodular functions$^{1}$ can be approximated by cut
functions of undirected graphs to a factor of $n-1$, which is tight up to a
constant.
3. Budgeted additive functions can be approximated by coverage functions to a
factor of $e/(e-1)$, which is tight.
Here $n$ is the size of the ground set on which the submodular function is
defined.
We also observe that prior works imply that monotone submodular functions can
be approximated by coverage functions with a factor between $O(\sqrt{n} \log
n)$ and $\Omega(n^{1/3} /\log^2 n) $.

本文研究了 submodular functions 可以被其他简单类别的 submodular functions 逼近的程度和方法，并证明了一些上下界。