The Rectilinear Steiner Minimum Tree (RSMT) problem is a fundamental problem
in VLSI placement and routing and is known to be NP-hard. Traditional RSMT
algorithms spend a significant amount of time on finding Steiner points to
reduce the total wire length or use heuristics to approximate producing
sub-optimal results. We show that Graph Neural Networks (GNNs) can be used to
predict optimal Steiner points in RSMTs with high accuracy and can be
parallelized on GPUs. In this paper, we propose GAT-Steiner, a graph attention
network model that correctly predicts 99.846% of the nets in the ISPD19
benchmark with an average increase in wire length of only 0.480% on suboptimal
wire length nets. On randomly generated benchmarks, GAT-Steiner correctly
predicts 99.942% with an average increase in wire length of only 0.420% on
suboptimal wire length nets.

研究论文提出了 GAT-Steiner，一种基于图注意力网络模型，能够高准确率地预测 ISPD19 基准测试中 99.846% 的网段，并在次优网长中仅产生 0.480% 的平均增加。在随机生成的基准测试中，GAT-Steiner 在 99.942% 的网段中高准确率地预测，并且在次优网长中仅产生 0.420% 的平均增加。

GAT-Steiner: 使用 GNN 进行直角斯坦纳最小树预测

GAT-Steiner: Rectilinear Steiner Minimal Tree Prediction Using GNNs

Recent years have witnessed rapid advances in the use of neural networks to
solve combinatorial optimization problems. Nevertheless, designing the "right"
neural model that can effectively handle a given optimization problem can be
challenging, and often there is no theoretical understanding or justification
of the resulting neural model. In this paper, we focus on the rectilinear
Steiner minimum tree (RSMT) problem, which is of critical importance in IC
layout design and as a result has attracted numerous heuristic approaches in
the VLSI literature. Our contributions are two-fold. On the methodology front,
we propose NN-Steiner, which is a novel mixed neural-algorithmic framework for
computing RSMTs that leverages the celebrated PTAS algorithmic framework of
Arora to solve this problem (and other geometric optimization problems). Our
NN-Steiner replaces key algorithmic components within Arora's PTAS by suitable
neural components. In particular, NN-Steiner only needs four neural network
(NN) components that are called repeatedly within an algorithmic framework.
Crucially, each of the four NN components is only of bounded size independent
of input size, and thus easy to train. Furthermore, as the NN component is
learning a generic algorithmic step, once learned, the resulting mixed
neural-algorithmic framework generalizes to much larger instances not seen in
training. Our NN-Steiner, to our best knowledge, is the first neural
architecture of bounded size that has capacity to approximately solve RSMT (and
variants). On the empirical front, we show how NN-Steiner can be implemented
and demonstrate the effectiveness of our resulting approach, especially in
terms of generalization, by comparing with state-of-the-art methods (both
neural or non-neural based).

近年来，神经网络在解决组合优化问题方面取得了快速发展。在本文中，我们提出了 NN-Steiner，这是一种新颖的混合神经 - 算法框架，用于计算矩形斯坦纳最小生成树（RSMT），并展示了其在处理复杂示例方面的泛化性和与现有方法的比较效果。