aainstitutetext: Department of Physics, Brown University, Providence, RI
02912, USA

# Angular momentum of the asymptotic electromagnetic field in the classical
scattering of charged particles

Rishabh Bhardwaj a Luke Lippstreu<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We compute the angular momentum of the electromagnetic field on a late time
Cauchy surface with an arbitrary constant normal vector relevant for the
classical scattering of charged particles. We find a time independent
contribution to the angular momentum. This demonstrates that every charged
particle scattering event is accompanied by a net shift in the angular
momentum of the electromagnetic field. We speculate that this shift is related
to a subleading electromagnetic memory effect. We argue that this asymptotic
angular momentum should be included in the description of the asymptotic
states in quantum theories containing infrared divergences. We demonstrate
that the Lorentz covariance of the asymptotic electromagnetic angular momentum
can only be exhibited upon making reference to the Cauchy slice’s normal
vector.

##  1 Introduction

Quantum theories containing massless particles in spacetime dimensions four or
less exhibit infrared (IR) divergences due to the asymptotic states failing to
converge appropriately towards free particle states. It has been known since
the late 1960’s that the asymptotic states instead approach what are often
referred to as dressed Faddeev-Kulish (FK) states dollard ; Chung:1965zza ;
Kibble:1968sfb ; Kulish:1970ut . The exact details of these states remain
poorly understood as evidenced by the lack of explicit IR finite amplitudes
calculated using these states. Progress on theoretical questions of great
importance have often been thwarted due to the lack of an unambiguous
framework for the calculation of infrared finite amplitudes111Note that the
treatment of IR divergences by summing over physically indistinguishable
processes is formulated on the level of cross-sections not amplitudes., see
e.g. Caron-Huot:2022jli ; Caron-Huot:2022ugt  where the authors obtained
causality and unitarity constraints on Wilson EFT coefficients for gravity up
to the ambiguity of infrared logarithms. In order to study questions of
causality and unitarity in four dimensions it would be desirable to further
clarify the properties of the asymptotic states so that a less ambiguous and
more efficient approach to the calculation of IR finite amplitudes can be
developed. As a step in this direction, in this paper we provide an answer to
the following question:

What are the correct quantum numbers to assign to the asymptotic states in
theories containing infrared divergences?

We do so by calculating the classical angular momentum of the electromagnetic
(EM) field on a late time Cauchy slice in the presence of a charged particle
scattering event. We find, see (9-10) for the main result, that the EM angular
momentum asymptotes to a non-zero, time independent value. Although the
computation is classical, the result suggests the following answer to the
above posed question: charged particle momentum eigenstates
$\ket{\set{p_{i}^{\mu},\sigma_{i},e_{i}}}$ should be appended by states which
account for this asymptotic angular momentum in the EM field. Indeed, this
conclusion is in line with the recent work DiVecchia:2022owy  where it was
shown that the FK states carry a non-zero angular momentum. We hope that this
insight may lead to future work which alleviates both the infinite ambiguity
in the choice of dressings for the FK states, as well as the presence of an
infrared cut-off in the FK states which obscures Poincaré covariance. Our work
may also be of interest to communities studying the infrared triangle of
asymptotic symmetries, soft theorems and memory effects. Both Low’s subleading
soft photon theorem Low:1954kd ; Low:1958sn ; Burnett:1967km ; Gell-
Mann:1954wra ; Lysov:2014csa , as well as the one-loop corrections to the soft
photon theorem Sahoo:2018lxl , involve terms which couple the soft photon to
the angular momentum of the charged particles. As our results indicate that
angular momentum conservation requires there to be a net shift in the low
energy modes of the angular momentum tensor of the EM field accompanying any
charged particle scattering event, it would be of interest to investigate
whether this shift is related to loop corrections to the electromagnetic
memory effect Bieri:2013hqa ; Pasterski:2015zua ; AtulBhatkar:2020hqz  or the
memory effect associated to Low’s subleading soft theorem Hirai:2018ijc ;
Campiglia:2016hvg ; Himwich ; Campiglia:2019wxe ; Donnay:2022sdg .
Our work is a follow-up on Gralla:2021eoi  where the authors calculated the
late time angular momentum of the EM field in the presence of charged
particles. The calculation presented in Gralla:2021eoi  was done in the center
of momentum (COM) frame on an equal time Cauchy slice. In this paper we
present the covariant form of their results by working in an arbitrary frame
using a Cauchy slice with a constant normal vector. By doing the computation
on an arbitrary Cauchy slice, our results highlight the interesting feature
that the EM angular momentum depends on the details of the Cauchy surface. Our
results are in agreement with those in Gralla:2021eoi  when evaluated in the
COM frame on an equal time Cauchy slice.
Our work was motivated by Zwanziger’s description of dyons Zwanziger:1972sx ,
see also the recent follow-ups Csaki1 ; Csaki2 ; Lippstreu:2021avq . It is
well known that in the presence of dyons the electromagnetic field contains a
time independent angular momentum at asymptotic times. Zwanziger used this
fact to modify the Poincaré transformation properties of dyons from that of
free particles’, and in doing so was able to calculate the scattering
amplitudes of dyons whilst circumventing many of the ambiguities that
otherwise plague their calculation. In a form made precise below our main
result (9-10), the angular momentum in the EM field due to charged particles
is essentially boost-like in nature, whereas the angular momentum of dyons is
essentially rotational in nature. It would be of interest to repeat
Zwanziger’s analysis for the boost-like angular momentum found herein.
The outline of the paper is as follows: in section 2 we describe our setup of
classical charged particle scattering. In section 3 we present our main
result, the angular momentum of the asymptotic electromagnetic field, and
discuss some of its qualitative features. In section 4 we compute the
mechanical angular momentum of the charged particles to demonstrate that our
results are consistent with total angular momentum conservation. Appendices
our dedicated to the evaluation of some of the relevant integrals.
Conventions: We work in $(+---)$ signature throughout. Our anti-symmetrization
bracket $a^{[\mu}b^{\nu]}=a^{\mu}b^{\nu}-a^{\nu}b^{\mu}$ does not contain a
factor of $\frac{1}{2}$.

##  2 Setup

Consider an outgoing asymptotic state made up of particles carrying charges
$e_{i}$, each in a wave packet concentrated around a momentum $p_{i}^{\mu}$ .
At sufficiently late times we expect that such states are accurately modelled
by classical currents

$J^{\mu}_{i}=e_{i}u^{\mu}_{i}\int_{0}^{\infty}\mathrm{d}\tau\,\,\delta^{4}\Big{(}x^{\mu}-u^{\mu}_{i}\tau-
b_{i}^{\mu}+\mathcal{O}(\log\tau)\Big{)},\qquad
u^{\mu}_{i}=\frac{p^{\mu}_{i}}{m_{i}},$ (1)

where $u_{i}^{\mu}$ is the four velocity $u_{i}^{2}=1$ of particle $i$,
$b_{i}^{\mu}$ is it’s impact parameter, and the bounds of integration are
appropriate for an out state. The trajectories receive order $\ln t$
corrections to linear motion due their late interaction with other particles
which we account for later. Using the retarded Green’s function222Here we
deviate from the quantum theory by not using the Feynman propagator. the
electromagnetic field produced by particle $i$ reads

$\lim_{t\rightarrow\infty}F^{\mu\nu}_{i}=\frac{e_{i}}{4\pi}\frac{x^{{[}\mu}{u_{i}}^{\nu{]}}}{\Big{(}(u_{i}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}}\theta(x^{2})+\mathcal{O}(t^{-3}\log(t)),\qquad
x^{{[}\mu}{u_{i}}^{\nu{]}}\coloneqq x^{\mu}u^{\nu}_{i}-x^{\nu}u^{\mu}_{i}.$
(2)

The Heaviside $\theta(x^{2})$ is due to our use of the retarded propagator.
Note that the field strength (2) vanishes as $t^{-2}$ at late times as
expected from dimensional considerations. The impact parameter $b_{i}^{\mu}$
is an order $\mathcal{O}(t^{-3})$ correction to (2) and consequently does not
affect the EM angular momentum at late times. Similarly the $\log t$
corrections to the particle trajectories provide an order
$\mathcal{O}(t^{-3}\log(t))$ correction to (2) and hence do not affect the
late time angular momentum of the EM field, but does affect the mechanical
angular momentum. The symmetrized energy-momentum and angular momentum
densities of the EM field respectively are

$\displaystyle
T^{\alpha\beta}_{\text{E.M.}}=\Big{(}g^{\alpha\mu}F_{\mu\lambda}F^{\lambda\beta}+\frac{1}{4}g^{\alpha\beta}F_{\mu\lambda}F^{\mu\lambda}\Big{)}$
(3) $\displaystyle
M^{\alpha\beta\gamma}_{\text{E.M.}}=T_{\text{E.M.}}^{\alpha[\beta}x^{\gamma]}.$
(4)

For the fields (2) these scale at late times respectively as $t^{-4}$ and
$t^{-3}$. We will integrate these densities on a spacelike Cauchy hypersurface
$\Sigma_{n}$ specified by the conditions

$n\cdot x=c,\qquad n^{2}=1,\qquad n^{0}>0,\qquad c\gg 1$ (5)

where $n^{\mu}$ is the spacetime independent normal vector to the Cauchy
surface, and $c$ is a spacetime independent scalar which we take to be large.
For example, choosing $n^{\mu}=(1,\vec{0})$ would correspond to an equal time
Cauchy slice, and $c$ would then then be the time of the Cauchy slice. When
one computes the flux of a conserved quantity through a Cauchy slice, the
result is independent of the hypersurface, hence one can usually work with the
most convenient choice of hypersurface without loss of generality . However
one of the results of this paper will be to show that the Lorentz covariance
of the late time angular momentum of the EM field can only be exhibited if one
works on the arbitrary linear Cauchy slice (5). The EM energy-momentum and
angular momentum on such a hypersurface respectively read

$\displaystyle
P^{\beta}_{\text{E.M.}}=\int_{\Sigma_{n}}\mathrm{d}^{3}\sigma\sqrt{|g_{\sigma\sigma}|}\,\,n_{\alpha}T^{\alpha\beta}$
(6) $\displaystyle
J^{\beta\gamma}_{\text{E.M.}}=\int_{\Sigma_{n}}\mathrm{d}^{3}\sigma\sqrt{|g_{\sigma\sigma}|}\,\,n_{\alpha}M^{\alpha\beta\gamma}$
(7)

where $\sigma_{i}$ denote co-ordinates adapted to the Cauchy surface and
$\sqrt{|g_{\sigma\sigma}|}$ is the induced measure. Due to the $\theta(x^{2})$
in (2) we expect the integrals to occur over a volume of order $t^{3}$. We
therefore expect the electromagnetic momentum to vanish as
$P^{\alpha}_{\text{E.M.}}\sim t^{-1}$ at late times. The angular momentum
contains an extra power of $x^{\mu}$, we therefore expect it will contain a
finite contribution $J^{\beta\gamma}_{\text{E.M.}}\sim t^{0}$. For our Cauchy
surface (5) all power counting arguments carry over where one instead power
counts in terms of the large parameter $c$.
Each field (2) exhibits the familiar $\frac{1}{r^{2}}$ UV divergence as
$x^{\mu}$ approaches the location of the source particle. Consequently the
order $e_{i}^{2}$ terms in the angular momentum tensor (7) will diverge
logarithmically whereas the order $e_{i}e_{j}$ terms for $i\neq j$ are finite.
Such UV divergences are attributable to self-energy corrections which are
treated by mass renormalization. As we are not attempting to calculate self-
energy corrections we will drop these self-energy contributions to the angular
momentum tensor. A further justification for this is that the conservation
laws of angular momentum will hold independently for the order $e_{i}^{2}$ and
$e_{i}e_{j}$ terms.

##  3 Electromagnetic angular momentum in the asymptotic states

Using the field strengths (2) in the expression for the angular momentum (7),
and dropping the self energy terms, one finds that the outgoing angular
momentum is

$\displaystyle\lim_{c\rightarrow\infty}J_{\text{E.M.}}^{\beta\gamma}\Big{(}\set{u^{\mu}_{i}},n^{\mu},c\Big{)}=\sum_{\begin{subarray}{c}i<j\\\
i,j\,\in\,\text{out}\end{subarray}}\frac{e_{i}e_{j}}{16\pi^{2}}\int_{\Sigma_{n}}\mathrm{d}^{3}\sigma\sqrt{|g_{\sigma\sigma}|}\theta(x^{2})$
$\displaystyle\frac{{u_{i}}^{[\beta}x^{\gamma]}\Big{(}(n\cdot x)(u_{j}\cdot
x)-x^{2}(n\cdot u_{j})\Big{)}+(i\leftrightarrow
j)+n^{[\beta}x^{\gamma]}\Big{(}x^{2}(u_{i}\cdot u_{j})-(u_{i}\cdot
x)(u_{j}\cdot x)\Big{)}}{\Big{(}(u_{i}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}\Big{(}(u_{j}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}}.$ (8)

In appendix A we evaluate (8) and find our main result,

$\boxed{\lim_{c\rightarrow\infty}J_{\text{E.M.}}^{\beta\gamma}\Big{(}\set{u^{\mu}_{i}},n^{\mu}\Big{)}=\sum_{\begin{subarray}{c}i<j\\\
i,j\,\in\,\text{out}\end{subarray}}\frac{e_{i}e_{j}}{4\pi}\frac{u^{[\beta}_{i}u^{\gamma]}_{j}}{\Big{(}(u_{i}\cdot
u_{j})^{2}-1\Big{)}^{\frac{3}{2}}}\log\bigg{(}\frac{n\cdot u_{i}}{n\cdot
u_{j}}\bigg{)}.}$ (9)

In appendix B we discuss the angular momentum on a early time Cauchy surface
$c\ll-1$ and find the same result as above but with an additional minus sign
and we sum only over incoming charged particles

$\boxed{\lim_{c\rightarrow-\infty}J_{\text{E.M.}}^{\beta\gamma}\Big{(}\set{u^{\mu}_{i}},n^{\mu}\Big{)}=-\sum_{\begin{subarray}{c}i<j\\\
i,j\,\in\,\text{in}\end{subarray}}\frac{e_{i}e_{j}}{4\pi}\frac{u^{[\beta}_{i}u^{\gamma]}_{j}}{\Big{(}(u_{i}\cdot
u_{j})^{2}-1\Big{)}^{\frac{3}{2}}}\log\bigg{(}\frac{n\cdot u_{i}}{n\cdot
u_{j}}\bigg{)}.}$ (10)

The result (9-10) exhibits many interesting features. First notice that it is
independent of $c$ which is our proxy for time. Hence there is a time-
independent contribution to the EM angular momentum at asymptotic times, even
when there are only charged particles in the asymptotic states. This
observation suggests that the asymptotic states
$\ket{\set{p_{i}^{\mu},\sigma_{i},e_{i}}}$ used to describe the quantum
scattering of charged particles should be further appended by states which
account for the asymptotic angular momentum of the EM field. This is in line
with the results of DiVecchia:2022owy  where it was demonstrated that the
Faddeev-Kulish states carry a non-zero angular momentum. As the angular
momentum tensor is promoted to the operator generating Lorentz transformations
in the quantum theory, the observation that the angular momentum of the EM
field approaches a non-zero value at asymptotic times suggests that the
Lorentz transformation properties of the asymptotic states deviate from those
of the free theory. For this reason it may be of interest to study the Lorentz
transformation properties of the FK states. A striking feature of (9) is it’s
explicit dependence on the Cauchy surface via it’s dependence on the normal
vector $n^{\mu}$. Indeed, $J^{\beta\gamma}$ is only a tensor if one also
transforms the Cauchy surface appropriately

$J_{\text{E.M.}}^{\beta\gamma}\Big{(}\set{\Lambda^{\mu}_{\,\,\,\nu}u^{\nu}_{i}},\Lambda^{\mu}_{\,\,\,\nu}n^{\nu}\Big{)}=\Lambda^{\beta}_{\,\,\,\beta^{\prime}}\Lambda^{\gamma}_{\,\,\,\gamma^{\prime}}J_{\text{E.M.}}^{\beta^{\prime}\gamma^{\prime}}\Big{(}\set{u^{\mu}_{i}},n^{\mu}\Big{)}.$
(11)

The dependence on $n^{\mu}$ is due to the fact that the mechanical and
electromagnetic angular momentum densities are not independently conserved at
asymptotic times,

$\partial_{\alpha}M^{\alpha\beta\gamma}_{\text{E.M.}}=-\partial_{\alpha}M^{\alpha\beta\gamma}_{\text{mech.}}=-x^{[\gamma}F^{\beta]\lambda}J_{\lambda},$
(12)

as this torque scales logarithmically with the proper time of the source
$\ln\tau$, indicating that even at asymptotic times there is a continual
exchange of angular momentum between the particles and the EM field.
Consequently it is only the sum of these two quantities which are conserved

$\partial_{\alpha}\Big{(}M^{\alpha\beta\gamma}_{\text{E.M.}}+M^{\alpha\beta\gamma}_{\text{mech.}}\Big{)}=0$
(13)

and therefore independent of the chosen Cauchy surface, which we verify in the
next section. The relative sign between the in and out angular momenta has
interesting implications. For large impact parameters where the particles
remain undeflected and consequently have the same in-momenta as out-momenta,
there still occurs a shift in the angular momentum of the electromagnetic
field. This phenomenon was discovered in Gralla:2021eoi  where they they
christened the effect as an “electromagnetic scoot”. The same authors found
that gravitational systems also exhibit a “gravitational scoot” Gralla:2021qaf
. It would be interesting to study whether these shifts are tied to any known
memory effects. It is interesting to note that the angular momentum is
independent of the possible length scales occurring in the problem. We hope to
find a conformal symmetry argument for why (9-10), must be the result. We note
that the angular momentum should be associated to the center-of-mass of the
electromagnetic field. We are referring to the fact that for each pair of
particles it is possible to go to a frame where their contribution to
$J_{\text{E.M.}}^{ij}$’s rotational components vanish, namely the rest frame
of one of the particles, whereas it is impossible to go to a frame where all
three boost components $J^{0i}_{\text{E.M.}}$ vanish for a given pair of
particles. This should be contrasted with the angular momentum present in the
electromagnetic field in the presence of dyons (see (1.1) of Zwanziger:1972sx
) which is proportional to
$J^{\alpha\beta}_{\text{E.M.}}=\epsilon^{\alpha\beta}{}_{\gamma\delta}u_{i}^{\gamma}u_{j}^{\delta}$
and for visa-versa reasons is intrinsically associated to the rotational
angular momentum of the electromagnetic field, and not it’s center of mass.

##  4 Mechanical angular momentum

At asymptotic times the trajectories of charged particles deviate from linear
motion by an order $\log(\tau)$ correction due to their electromagnetic
interactions with the other charged particles,

$\displaystyle\lim_{\tau_{i}\rightarrow\pm\infty}x_{i}^{\mu}=u^{\mu}_{i}\tau_{i}+b^{\mu}_{i}\mp\log|m\tau_{i}|\sum_{\begin{subarray}{c}j\\\
j\neq i\end{subarray}}\frac{e_{i}e_{j}}{4\pi}\frac{(u_{i}\cdot
u_{j})u_{i}^{\mu}-u^{\mu}_{j}}{m_{i}\Big{(}(u_{i}\cdot
u_{j})^{2}-1\Big{)}^{\frac{3}{2}}}+\mathcal{O}\big{(}\tau^{-1}_{i}\log\tau_{i}\big{)}$
(14)
$\displaystyle\lim_{\tau_{i}\rightarrow\pm\infty}p_{i}^{\mu}=m_{i}u^{\mu}_{i}\mp\frac{1}{|\tau_{i}|}\sum_{\begin{subarray}{c}j\\\
j\neq i\end{subarray}}\frac{e_{i}e_{j}}{4\pi}\frac{(u_{i}\cdot
u_{j})u_{i}^{\mu}-u^{\mu}_{j}}{\Big{(}(u_{i}\cdot
u_{j})^{2}-1\Big{)}^{\frac{3}{2}}}+\mathcal{O}\big{(}\tau^{-2}_{i}\log\tau_{i}\big{)}$
(15)

see e.g. Sahoo:2018lxl ; Zwanziger:1973if  for a derivation of this result.
Here $m$ is an arbitrary constant which we choose to be the same for all
particles, and will drop out of the final result. $b^{\mu}_{i}$ is an impact
parameter. To compute the mechanical angular momentum of particle $i$,

$J^{\beta\gamma}_{i,\text{mech.}}=p_{i}^{[\beta}x^{\gamma]}_{i}$ (16)

we need to solve for the $\tau_{i}$ at which the particle intersects the
Cauchy surface $\Sigma_{n}$. Plugging in (14) into the defining equation for
the hypersurface (5) and only retaining leading order terms in $c$ we find
that the particle intersects the hypersurface at proper time

$\displaystyle n\cdot x_{i}=c\implies\tau_{i}=\frac{c}{n\cdot
u_{i}}+\mathcal{O}\big{(}c^{0}\big{)}.$ (17)

Plugging in this value for $\tau_{i}$ when using (14-15) in (16), and then
summing over all charged particles, we find that the total mechanical angular
momentum is

$\lim_{c\rightarrow\pm\infty}J^{\beta\gamma}_{\text{mech.}}\Big{(}\set{u_{i}},n\Big{)}=\sum_{i}p^{[\beta}_{i}b^{\gamma]}_{i}\mp\sum_{i<j}\frac{e_{i}e_{j}}{4\pi}\frac{u_{i}^{[\beta}u_{j}^{\gamma]}}{\Big{(}(u_{i}\cdot
u_{j})^{2}-1\Big{)}^{\frac{3}{2}}}\log\Big{(}\frac{n\cdot u_{i}}{n\cdot
u_{j}}\Big{)}$ (18)

where the sum is only over in particles if $c<0$ and only over out particles
if $c>0$. The first term is the familiar orbital angular momentum of a
particle with momentum $p_{i}^{\mu}$ at impact parameter $b_{i}^{\mu}$. Note
that the second term in (18) precisely cancels the electromagnetic angular
momentum (9). Indeed it must in order for the total angular momentum of the
system to be conserved/independent of the Cauchy surface.

## Acknowledgements

We thank Shounak De, Yangrui Hu, Lecheng Ren, Marcus Spradlin, Akshay
Yelleshpur Srikant and Anastasia Volovich for helpful discussions. LL
acknowledges support from the US Department of Energy contract DE–SC0010010
Task F.

##  Appendix A Evaluating the angular momentum integral

In this appendix we evaluate the integral (8)

$\displaystyle
I^{\beta\gamma}\Big{(}u^{\mu}_{1},u^{\mu}_{2},n^{\mu},c\Big{)}=\int_{\Sigma_{n}}\mathrm{d}^{3}\sigma\sqrt{|g_{\sigma\sigma}|}\theta(x^{2})$
$\displaystyle\frac{{u_{1}}^{[\beta}x^{\gamma]}\Big{(}(n\cdot x)(u_{2}\cdot
x)-x^{2}(n\cdot u_{2})\Big{)}+(1\leftrightarrow
2)+n^{[\beta}x^{\gamma]}\Big{(}x^{2}(u_{1}\cdot u_{2})-(u_{1}\cdot
x)(u_{2}\cdot x)\Big{)}}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}\Big{(}(u_{2}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}}.$ (19)

where for ease of demonstration we have selected the contributions from
particles $i,j=1,2$ and factored out $\frac{e_{1}e_{2}}{16\pi^{2}}$. First we
analyze the possible tensor structures for $I^{\beta\gamma}$ which is an anti-
symmetric second rank tensor, and thus has potentially six independent
components, which are formed from the vectors $n^{\mu},u_{1}^{\mu}$ and
$u_{2}^{\mu}$. We will first show that the conformal properties of the
integral restricts the possible tensor structures down to two. The $x^{\mu}$
in (19) is understood to be evaluated in co-ordinates adapted to the
hypersurface

$\displaystyle x^{\mu}=cn^{\mu}+\sum_{i=1}^{3}\sigma_{i}\epsilon_{i}^{\mu}(n)$
(20) $\displaystyle\epsilon_{i}\cdot
n=0,\qquad\epsilon_{i}\cdot\epsilon_{j}=-\delta_{ij},\qquad\sqrt{|g_{\sigma\sigma}|}=1.$
(21)

The $\theta(x^{2})=\theta(c^{2}-|\vec{\sigma}|^{2})$ then restricts the
integration range of the $\sigma$’s to the solid ball of radius $c$. Changing
to integration co-ordinates $\sigma_{i}^{\prime}=\frac{\sigma_{i}}{c}$ we see
that the six powers of $c$ in the denominator of (19) precisely cancel the six
powers of $c$ in the numerator of (19). This proves that (19) is independent
of $c$, and consequently via the defining equation of the hypersurface $n\cdot
x=c$ that (19) can only depend on ratio’s of $n^{\mu}$. Secondly, let us for a
moment generalize the definition of (19) by making the replacement in the
denominators

$\Big{(}(u_{i}\cdot
x)^{2}-x^{2}\Big{)}^{-\frac{3}{2}}\rightarrow\Big{(}(u_{i}\cdot
x)^{2}-u_{i}^{2}x^{2}\Big{)}^{-\frac{3}{2}}$ (22)

for $i=1,2$ and we no longer restrict $u_{i}^{2}=1$, we only require that
$u_{i}^{\mu}$ remain timelike. We leave the numerators untouched. This defines
a new integral $\tilde{I}^{\beta\gamma}$ from which we can readily obtain our
desired integral

$I^{\beta\gamma}\Big{(}u^{\mu}_{1},u^{\mu}_{2},n^{\mu}\Big{)}=\tilde{I}^{\beta\gamma}\Big{(}u^{\mu}_{1},u^{\mu}_{2},n^{\mu}\Big{)}\and{u_{1}^{2}=u_{2}^{2}=1}.$
(23)

From this equation we can trivially obtain the tensor structure of $I$ from
that of $\tilde{I}$. Now note that $\tilde{I}$ is homogeneously of degree $-2$
in each of the four velocities

$\displaystyle\tilde{I}(\alpha
u_{1}^{\mu},u_{2}^{\mu},n^{\mu})=\alpha^{-2}\tilde{I}(u_{1}^{\mu},u_{2}^{\mu},n^{\mu}),\qquad\tilde{I}(u_{1}^{\mu},\alpha
u_{2}^{\mu},n^{\mu})=\alpha^{-2}\tilde{I}(u_{1}^{\mu},u_{2}^{\mu},n^{\mu})$
(24)

for $\alpha>0$ a positive real number. Only two tensor structures are
compatible with all of the constraints we have listed so far,

$I^{\beta\gamma}(u_{1}^{\mu},u_{2}^{\mu},n^{\mu})=f_{1}u^{[\beta}_{1}u_{2}^{\gamma]}+f_{2}\epsilon^{\beta\gamma}{}_{\delta\lambda}u^{\delta}_{1}u^{\lambda}_{2}$
(25)

where $f_{i}\big{(}u_{1}\cdot u_{2},n\cdot u_{1},n\cdot u_{2}\big{)}$ are
Lorentz invariant functions. Note that (19) is symmetric under
$(1\leftrightarrow 2)$ and consequently we have that the $f_{i}$’s must be
anti-symmetric under $(1\leftrightarrow 2)$. We can project onto the
individual tensor components in (25) by contracting with the appropriate
tensors,

$\displaystyle
f_{1}=\frac{u^{\beta}_{1}u^{\gamma}_{2}I_{\beta\gamma}}{1-(u_{1}\cdot
u_{2})^{2}},\qquad
f_{2}=-\frac{1}{2}\frac{u_{1}^{\delta}u_{2}^{\lambda}\epsilon_{\delta\lambda\beta\gamma}I^{\beta\gamma}}{1-(u_{1}\cdot
u_{2})^{2}}.$ (26)

Explicit evaluation of the integral reveals that $f_{2}=0$. We now evaluate
$f_{1}$. Contracting $u^{\beta}_{1}u^{\gamma}_{2}$ onto $I_{\beta\gamma}$ in
(19) and performing some algebra to manipulate the numerator into a convenient
form we find

$\displaystyle f_{1}$ $\displaystyle=\frac{1}{1-(u_{1}\cdot
u_{2})^{2}}\int_{\Sigma_{n}}\mathrm{d}^{3}\sigma\sqrt{|g_{\sigma\sigma}|}\theta(x^{2})\frac{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}\Big{(}(n\cdot u_{2})(u_{2}\cdot x)-(n\cdot
x)\Big{)}-(1\leftrightarrow 2)}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}\Big{(}(u_{2}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}}$ (27) $\displaystyle=\frac{1}{1-(u_{1}\cdot
u_{2})^{2}}\int_{\Sigma_{n}}\mathrm{d}^{3}\sigma\sqrt{|g_{\sigma\sigma}|}\theta(x^{2})\frac{{u^{2}}_{\mu}n_{\nu}x^{[\mu}{u_{2}}^{\nu]}}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{1}{2}}\Big{(}(u_{2}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}}-(1\leftrightarrow 2).$ (28)

In the second equality we have cancelled repeated powers of the same function
in the numerator and denominator as well as manipulated the numerators into a
form that reveals that the integrand contains terms proportional to the field
strengths of the particles (2). Defining the scaled field strengths,

$G^{\mu\nu}_{i}=\frac{x^{[\mu}{u_{i}}^{\nu]}}{\Big{(}(u_{i}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}}$ (29)

which due to Maxwell’s equations $\partial_{\mu}F^{\mu\nu}=J^{\nu}$ satisfies,

$\partial_{\nu}G^{\mu\nu}_{i}=-4\pi
u^{\nu}_{2}\int_{0}^{\infty}\mathrm{d}\tau\,\,\delta^{4}(x^{\alpha}-u_{2}^{\alpha}\tau).$
(30)

We then have that

$\displaystyle f_{1}=\frac{1}{1-(u_{1}\cdot
u_{2})^{2}}\int_{\Sigma_{n}}\mathrm{d}^{3}\sigma\sqrt{|g_{\sigma\sigma}|}\theta(x^{2})\frac{{u^{2}}_{\mu}n_{\nu}G^{\mu\nu}_{2}}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{1}{2}}}-(1\leftrightarrow 2).$ (31)

The divergence property (30) motivates us to use Stokes theorem and interpret
$\Sigma_{n}$ as part of a boundary enclosing a $4$-volume. To this end we need
to add extra boundary terms. We would like the added boundary terms to
evaluate to zero. To this end let us note $f_{1}$ vanishes on the surface
which has a normal vector

${n^{\prime}}^{\mu}=\frac{1}{\sqrt{2}}\frac{u_{1}^{\mu}+u_{2}^{\mu}}{\sqrt{(u_{1}\cdot
u_{2})^{2}+1}}$ (32)

which is easily deduced from the fact that $f_{1}(u_{1}\cdot n,u_{2}\cdot
n,n)$ is anti-symmetric under $1\leftrightarrow 2$. We therefore add the
boundary $\Sigma_{n^{\prime}}$ below333We add the surface
$\Sigma_{n^{\prime}}$ below $\Sigma_{n}$ so that the normal vector $n^{\mu}$
does not flip sign when using Stokes theorem $\Sigma_{n}$, i.e.
$c^{\prime}<c$, and join the two boundaries at radial infinity, which we are
free to do without affecting the integral $f_{1}$ as the integrand (31) falls
off sufficiently fast $\frac{1}{R^{3}}$ at radial infinity. We call the
$4-$volume bounded by this closed surface $V_{\Sigma}$. Using Stokes theorem
we have that

$\displaystyle f_{1}$ $\displaystyle=\frac{1}{1-(u_{1}\cdot
u_{2})^{2}}\int_{V_{\Sigma}}\mathrm{d}^{4}x\partial_{\nu}\Bigg{(}\theta(x^{2})\frac{{u^{2}}_{\mu}G^{\mu\nu}_{2}}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{1}{2}}}\Bigg{)}-(1\leftrightarrow 2)$ (33)
$\displaystyle=\frac{1}{1-(u_{1}\cdot
u_{2})^{2}}\int_{V_{\Sigma}}\mathrm{d}^{4}x\Bigg{(}\theta(x^{2})\frac{{u^{2}}_{\mu}\partial_{\nu}G^{\mu\nu}_{2}}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{1}{2}}}\Bigg{)}-(1\leftrightarrow 2)$ (34)
$\displaystyle=\frac{4\pi}{(u_{1}\cdot
u_{2})^{2}-1}\int_{V_{\Sigma}}\mathrm{d}^{4}x\int_{0}^{\infty}\mathrm{d}\tau_{2}\Bigg{(}\theta(x^{2})\frac{\delta^{4}(x^{\alpha}-u_{2}^{\alpha}\tau_{2})}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{1}{2}}}\Bigg{)}-(1\leftrightarrow 2)$ (35)
$\displaystyle=\frac{4\pi}{\Big{(}(u_{1}\cdot
u_{2})^{2}-1\Big{)}^{\frac{3}{2}}}\int^{u^{\alpha}_{2}\tau_{2}\cap\Sigma_{n}}_{u^{\alpha}_{2}\tau_{2}\cap\Sigma_{n^{\prime}}}\frac{\mathrm{d}\tau}{|\tau|}-(1\leftrightarrow
2)$ (36)

In going to the second equality we used that the terms where the derivative
does not act on $G^{\mu\nu}_{2}$ are symmetric under $(1\leftrightarrow 2)$
and hence vanish when we antisymmetrize. In the third equality we have used
the divergence property (30). At the fourth equality the bounds on the
$\tau_{2}$ integral indicate that we integrate $\tau$ from the proper time at
which particle $2$ intersects the lower boundary, until the proper time that
it intersects the upper boundary. To find the upper and lower intersection
times one simply uses the defining equations for the boundaries, e.g. $(n\cdot
x)=c$, to find

$\displaystyle\tau^{\text{lower}}_{2}=\frac{c^{\prime}}{n^{\prime}\cdot
u_{2}},\qquad\tau^{\text{upper}}_{2}=\frac{c}{n\cdot u_{2}}.$ (37)

Note that ${n^{\prime}}\cdot u_{2}$ is symmetric in $(1\leftrightarrow 2)$.
Altogether then we have that444The sign function arises from the relation
$\int_{A}^{B}\frac{\mathrm{d}}{|x|}=\text{sign}(B)\ln|\frac{B}{A}|$ where the
interval $[A,B]$ does not contain $0$ so that no poles are encountered along
the integration contour.

$f_{1}=\text{sign}(c)\frac{4\pi}{\Big{(}(u_{1}\cdot
u_{2})^{2}-1\Big{)}^{\frac{3}{2}}}\log\Big{(}\frac{n\cdot u_{1}}{n\cdot
u_{2}}\Big{)}$ (38)

Then using the relation between $f_{1}$ and our integral $I^{\beta\gamma}$
(25) we have that

$I^{\beta\gamma}\Big{(}u_{1}^{\mu},u_{2}^{\mu},n^{\mu}\Big{)}=4\pi\text{sign}(c)\,\,\frac{u^{[\beta}_{1}u^{\gamma]}_{2}}{\Big{(}(u_{1}\cdot
u_{2})^{2}-1\Big{)}^{\frac{3}{2}}}\log\Big{(}\frac{n\cdot u_{1}}{n\cdot
u_{2}}\Big{)}.$ (39)

Finally, to obtain the angular momentum we multiply by
$\frac{e_{1}e_{2}}{16\pi^{2}}$ and sum over all pairs of outgoing particles to
obtain our main result (9).

##  Appendix B Contributions from the in-states

###  B.1 In-states do not contribute to the out angular momentum

The field strength’s produced by incoming currents have support on the
outgoing Cauchy surface (outgoing Cauchy surface is defined as a $c>0$) which
could thus potentially affect the angular momentum on an outgoing surface.
However we will show here that these terms give zero contribution. We model an
in-current by simply changing the bounds of integration from that of an out-
current (1)

$J^{\mu}_{i}=e_{i}u^{\mu}_{i}\int_{-\infty}^{0}\mathrm{d}\tau\,\,\delta^{4}\Big{(}x^{\mu}-u^{\mu}_{i}\tau-
b_{i}^{\mu}+\mathcal{O}(\log\tau)\Big{)},\qquad
u^{\mu}_{i}=\frac{p^{\mu}_{i}}{m_{i}}.$ (40)

The field strength created by such an in-source has support everywhere except
for the forward lightcone of the origin (using the retarded Green’s function)

$\lim_{|t|\rightarrow\infty}F^{\mu\nu}_{i}=\frac{e_{i}}{4\pi}\frac{x^{{[}\mu}{u_{i}}^{\nu{]}}}{\Big{(}(u_{i}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{3}{2}}}(1-\theta(x^{0})\theta(x^{2}))+\mathcal{O}(t^{-3}\log(t)).$
(41)

On an outgoing Cauchy surface $c>0$ the contributions of in-currents to the
angular momentum on such an outgoing Cauchy surface can be obtained simply by
making the replacement $\theta(x^{2})\rightarrow\theta(-x^{2})$ in (8). We
thus seek to show that (19) is zero when making this replacement. Following
the reasoning of appendix A we see that the arguments which lead from (19) to
(36) were independent of the $\theta(x^{2})$. We are thus lead to the
conclusion that the in-currents contributions to the out-going angular
momentum is

$\displaystyle f_{1}$ $\displaystyle=\frac{4\pi}{(u_{1}\cdot
u_{2})^{2}-1}\int_{V_{\Sigma}}\mathrm{d}^{4}x\int_{-\infty}^{0}\mathrm{d}\tau_{2}\Bigg{(}\theta(-x^{2})\frac{\delta^{4}(x^{\alpha}-u_{2}^{\alpha}\tau_{2})}{\Big{(}(u_{1}\cdot
x)^{2}-x^{2}\Big{)}^{\frac{1}{2}}}\Bigg{)}-(1\leftrightarrow 2)$ (42)
$\displaystyle=0$ (43)

which is zero because $\theta(-\tau^{2})=0$ or more simply put, because the
in-current has no support within the 4-volume $V_{\Sigma}$. We therefore
conclude that the incoming currents do not contribute to the outgoing angular
momentum.

###  B.2 In-states contribution to the in angular momentum

Here we compute the angular momentum on an early time Cauchy surface $c\ll 0$
due to the incoming currents (40). The field strengths created by the in-
sources (41) have support everywhere on the $c\ll 0$ Cauchy surface.
Consequently the integral expression for the electromagnetic angular momentum
on an in-Cauchy surface due to the in-currents is the same as in (8), except
we drop the $\theta(x^{2})$, sum over only incoming particles, and
$\Sigma_{n}$ must now be taken to be the in-Cauchy surface. We therefore seek
to evaluate (19) with these replacements. The arguments that lead from (19) to
(39) can be repeated verbatim with these replacements. The only difference at
an intermediate step are the bounds of integration for the $\tau$ integral at
(35) would be $[-\infty,0]$ but this is inconsequential. We conclude that the
in particles contribution to the incoming momentum is (10).

## References

  * (1) J. D. Dollard, Asymptotic convergence and the coulomb interaction, Journal of Mathematical Physics 5 (1964), no. 6 729–738, [https://doi.org/10.1063/1.1704171].
  * (2) V. Chung, Infrared Divergence in Quantum Electrodynamics, Phys. Rev. 140 (1965) B1110–B1122.
  * (3) T. W. B. Kibble, Coherent Soft-Photon States and Infrared Divergences. I. Classical Currents, J. Math. Phys. 9 (1968), no. 2 315–324.
  * (4) P. P. Kulish and L. D. Faddeev, Asymptotic conditions and infrared divergences in quantum electrodynamics, Theor. Math. Phys. 4 (1970) 745.
  * (5) S. Caron-Huot, Y.-Z. Li, J. Parra-Martinez, and D. Simmons-Duffin, Graviton partial waves and causality in higher dimensions, arXiv:2205.01495.
  * (6) S. Caron-Huot, Y.-Z. Li, J. Parra-Martinez, and D. Simmons-Duffin, Causality constraints on corrections to Einstein gravity, arXiv:2201.06602.
  * (7) P. Di Vecchia, C. Heissenberg, and R. Russo, Angular momentum of zero-frequency gravitons, arXiv:2203.11915.
  * (8) F. E. Low, Scattering of light of very low frequency by systems of spin 1/2, Phys. Rev. 96 (1954) 1428–1432.
  * (9) F. E. Low, Bremsstrahlung of very low-energy quanta in elementary particle collisions, Phys. Rev. 110 (1958) 974–977.
  * (10) T. H. Burnett and N. M. Kroll, Extension of the low soft photon theorem, Phys. Rev. Lett. 20 (1968) 86.
  * (11) M. Gell-Mann and M. L. Goldberger, Scattering of low-energy photons by particles of spin 1/2, Phys. Rev. 96 (1954) 1433–1438.
  * (12) V. Lysov, S. Pasterski, and A. Strominger, Low’s Subleading Soft Theorem as a Symmetry of QED, Phys. Rev. Lett. 113 (2014), no. 11 111601, [arXiv:1407.3814].
  * (13) B. Sahoo and A. Sen, Classical and Quantum Results on Logarithmic Terms in the Soft Theorem in Four Dimensions, JHEP 02 (2019) 086, [arXiv:1808.03288].
  * (14) L. Bieri and D. Garfinkle, An electromagnetic analogue of gravitational wave memory, Class. Quant. Grav. 30 (2013) 195009, [arXiv:1307.5098].
  * (15) S. Pasterski, Asymptotic Symmetries and Electromagnetic Memory, JHEP 09 (2017) 154, [arXiv:1505.00716].
  * (16) S. Atul Bhatkar, New asymptotic conservation laws forelectromagnetism, JHEP 02 (2021) 082, [arXiv:2007.03627].
  * (17) H. Hirai and S. Sugishita, Conservation Laws from Asymptotic Symmetry and Subleading Charges in QED, JHEP 07 (2018) 122, [arXiv:1805.05651].
  * (18) M. Campiglia and A. Laddha, Subleading soft photons and large gauge transformations, JHEP 11 (2016) 012, [arXiv:1605.09677].
  * (19) E. Himwich and A. Strominger, Celestial current algebra from low’s subleading soft theorem, Physical Review D 100 (9, 2019).
  * (20) M. Campiglia and A. Laddha, Loop Corrected Soft Photon Theorem as a Ward Identity, JHEP 10 (2019) 287, [arXiv:1903.09133].
  * (21) L. Donnay, S. Pasterski, and A. Puhm, Goldilocks modes and the three scattering bases, JHEP 06 (2022) 124, [arXiv:2202.11127].
  * (22) S. E. Gralla and K. Lobo, Electromagnetic scoot, Phys. Rev. D 105 (2022), no. 8 084053, [arXiv:2112.01729].
  * (23) D. Zwanziger, Angular distributions and a selection rule in charge-pole reactions, Phys. Rev. D 6 (1972) 458–470.
  * (24) C. Csaki, S. Hong, Y. Shirman, O. Telem, J. Terning, and M. Waterbury, Scattering amplitudes for monopoles: pairwise little group and pairwise helicity, JHEP 08 (2021) 029, [arXiv:2009.14213].
  * (25) C. Csáki, S. Hong, Y. Shirman, O. Telem, and J. Terning, Completing Multiparticle Representations of the Poincaré Group, Phys. Rev. Lett. 127 (2021), no. 4 041601, [arXiv:2010.13794].
  * (26) L. Lippstreu, Zwanziger’s pairwise little group on the celestial sphere, JHEP 11 (2021) 051, [arXiv:2106.00084].
  * (27) S. E. Gralla and K. Lobo, Self-force effects in post-Minkowskian scattering, Class. Quant. Grav. 39 (2022), no. 9 095001, [arXiv:2110.08681].
  * (28) D. Zwanziger, Reduction formulas for charged particles and coherent states in quantum electrodynamics, Phys. Rev. D 7 (1973) 1082–1099.


# GAT-Steiner: Rectilinear Steiner Minimal Tree Prediction Using GNNs

Bugra Onal2, Eren Dogan2, Muhammad Hadir Khan, Matthew R. Guthaus
Computer Science and Engineering, University of California Santa Cruz, Santa
Cruz, CA 95064
{bonal, erdogan, mkhan33<EMAIL_ADDRESS>
###### Abstract

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.

22footnotetext: Equal contribution

##  I Introduction

To create a physical layout, placement and routing tools must connect together
pins of nets with wires during the placement, routing and optimization phases.
Net routing, however, takes a significant amount of time since there are many
such nets, so existing solutions typically make use of iterative heuristic
approaches since the problem is known to be NP-hard. Long runtimes not only
affect the time to market but also make it increasingly difficult to iterate
in the design flow in the later stages.

In order to satisfy the power, performance, and area (PPA) requirements of a
design, nets are typically connected with the shortest wire length possible.
Modern placement and routing tools leverage Steiner points to achieve a better
wire length through Steiner Minimum Trees (SMTs) or, a variant of this problem
with orthogonal routing layers, Rectilinear Steiner Minimum Trees (RSMT). RSMT
is an NP-hard problem, and finding these Steiner points accurately can be a
time-consuming process for routing tools. Optimal RSMTs can be computed using
Integer Linear Programming (ILP) [1], but require significant run-time which
limits their usage in placement and optimization steps.

There are a number of state-of-the-art RSMT heuristics such as FLUTE [2] and
SALT [3], but they give up wire-length optimality for run time. Another recent
work [4] utilizes a mixed neural network (NN) and dynamic programming (DP)
approach using the PTAS algorithm [5], but does not use Graph Neural Networks
(GNNs). Yet another deep reinforcement learning technique for non-rectilinear
SMT problems has shown some promise but also relies on iterative Steiner point
selection using GNNs [6]. In general, these algorithmic, iterative approaches
limit batch computation and, at best, require multiple calls to a GPU for
parallel computation.

We propose the first Graph Neural Network (GNN) model for the RSMT problem
using a Graph Attention Network (GAT) [7]. The idea is to directly predict
Steiner points, while significantly reducing the runtime by computing these
Steiner points in parallel rather than iteratively. In addition,
implementations of GNNs can also predict the Steiner points for multiple
Steiner trees at the same time using vector processing units offering speed-up
at the design level.

In Section II, we provide more context on the state-of-the-art techniques we
use to achieve our high-accuracy model for RSMT prediction. In Section III, we
describe our model structure, how we implemented it and how we train it. In
Section IV, we show how we tested the model, and analyze accuracy and
parallelization we gained. Finally, Section V concludes the paper.

##  II Background

GNNs are neural network (NN) techniques similar to Convolutional Neural
Networks (CNNs); however, their input is a non-uniform graph instead of a
regular matrix [8, 7, 9]. Technically, CNNs are a special, uniform graph case
of GNNs. GNN models that interpret relations between nodes of the input graph
can be trained to perform node prediction, edge prediction, and graph
classification.

GNNs can be trained for either transductive inference or inductive inference.
Transductive inference refers to applications where the model is trained to
solve a specific set of test inputs; whereas inductive learning refers to
models trained to solve for a more general problem on unknown inputs.

Similar to other NN methods, GNNs can be trained in both supervised and
unsupervised fashions using back-propagation. Supervised learning is when the
training data is labeled with known outputs so that patterns can be recognized
between the inputs and outputs. With unsupervised training, the training data
does not have labels and the model instead uses a loss heuristic, but these
are often challenging to formulate for a given problem.

A significant advantage that GNNs have over CNNs is that they can correctly
predict outcomes for isomorphic graphs. If two graphs have a one-to-one
mapping with different node ordering, they are isomorphic. In these two cases,
CNNs will often predict different results for isomorphic graphs depending on
training and node ordering, whereas GNNs predict consistently by aggregating
features from topological neighbours.

One issue with GNNs, however, is over-smoothing where node features tend to
converge to similar values for deeply layered networks [10]. This is mostly
addressed by tuning the model to have appropriate levels, but has also been
examined through adaptive mechanisms [11].

The message passing feature is the core principle behind GNNs. It is an
iterative process of updating the features of the nodes (i.e.,
$\overrightarrow{h}_{j}$ to $\overrightarrow{h}_{j+1}$) based on their
neighbors’ and their own features ($\overrightarrow{h}_{i}$ for
$i\in\mathcal{N}_{i}$) using learnable weights. Each iteration over all nodes
is a GNN layer which allows features to be updated with information from
neighbors that are one step further away. A message-passing layer can be
written in matrix form as

$H_{k+1}=\sigma(A\times H_{k}\times W_{k}).$ (1)

where $H_{k}$ is matrix of feature vectors at the $k^{th}$ layer for all node
features ($\overrightarrow{h}_{i}$); $A$ is the adjacency matrix of the graph;
$W_{k}$ is the learnable component in the $k^{th}$ layer; and $\sigma(\cdot)$
is any non-linear activation function. This message-passing method is used as
a way to discover feature embeddings for further use with downstream tasks
such as node prediction. An example of message passing on a Hanan grid graph
for a single node is shown in Fig. 1.

Figure 1: GAT message passing of nodes on a Hanan grid to update a single
node’s feature vector, $\overrightarrow{h}_{5}$. Three attention heads are
shown (green, red, blue) and three layers are stacked on top of each other.
Node features can be coordinates, node type, etc. and are aggregated with
multiple-levels.

Graph Attention Networks (GATs) [7] are a specialized variant of GNNs, where
the relations of neighbors can be learned with an attention mechanism [12].
GATs add an attention coefficient for each neighbor based on weighted feature
similarity:

$e_{ij}=\alpha(W{\overrightarrow{h}_{i}},W{\overrightarrow{h}_{j}}).$ (2)

These coefficients are made comparable at each layer and neighborhood by using
the softmax of all neighbor attention coefficients,

$\alpha_{ij}=softmax(e_{ij})$ (3)

as seen in Fig 1.

GATs can also incorporate multiple attention heads to understand how portions
of neighbor features may affect the output of that node differently [7].
Specifically, multiple weight matrices may be used and the weighted outputs
combined using concatenation, averaging, or summation. For example, in
rectilinear routing, the left and up neighbors together may affect a node
differently than the right or lower neighbors and may benefit from multiple
attention heads. Fig. 1 shows three such attention heads in red, green, and
blue entering the center node with different weights.

Dropout is a method used to prevent over-fitting the model for specific
training data [13]. During training, a dropout layer randomly selects a set of
input features with a predefined percentage and masks those out of the
updates. Similarly, attention dropout in GNNs can select a predefined
percentage of neighbors and mask those from a layer update during training.

##  III Implementation

The GAT-Steiner model is shown in Fig. 2 and is made up of a number of GAT
convolutional layers [7] configured to do node prediction. In addition, we
implemented layer and attention dropout mechanisms. We adopt a supervised
training model using optimal RSMTs generated by GeoSteiner but also use L2
regularization loss functions for kernel, bias and attention regularization of
each layer.

The output of the GAT model is the probability of each node being a Steiner
node. We apply a threshold of 0.5 to select all the Steiner points from a
single inference. Using the Steiner points along with the net pins, we route
the net using Kruskal’s MST algorithm. In this section, we discuss the model
features, training data, and loss in detail.

Figure 2: The model flow, starting with Hanan grids of nets; adjacency
matrices and feature vectors are constructed. Then, feature embeddings are
found using 2 GAT layers using multiple attention heads, with ELU and sigmoid
activation functions respectively. Steiner point probability for each node is
found and points above the threshold are selected as Steiner points. Finally,
nets are routed by finding the MST of pins and Steiner nodes.

We have used disjoint data mode, which allows multiple input nets to be
processed at the same time by creating a sparse diagonal block union of their
adjacency matrices. Disjoint mode is visualized in Fig. 2 with two nets. This
approach allows training and inference for multiple nets to run in parallel
and improves runtime significantly.

###  III-A Model Features and Labels

In order to extract the topographical features of the net, we use the Hanan
grid of the net’s pins (e.g., blue squares) as the input graph as seen in Fig.
1 and Fig. 2. Empty nodes (e.g., purple circles) in the input graph can be
chosen as the Steiner nodes (e.g., green circle). Features for every node are
made up of their $x$ and $y$ coordinates and identification of node type,
which can be a pin or an empty node.

An adjacency matrix is constructed representing each of the four orthogonal
directions that connect sinks and empty nodes in the Hanan grid.

The true output labels are binary node classifications which identify the
correct, optimal Steiner nodes.

###  III-B Labeled Training Data

GeoSteiner produces optimal results for RSMT problems but can take excessive
run-time for large instances. We use GeoSteiner to label training data for up
to degree 50 nets.

In order to make sure the model learns from as many different RSMT examples as
possible and the model scales for large degree nets, we generated a synthetic
dataset of random nets. All coordinates are chosen randomly between 0 and
1,000,000. The dimensions of each problem instance are normalized to floating
point numbers between 0 and 100. We found that, when normalized, the training
samples produce more consistent patterns that the model can learn.

Table I shows statistics for the randomly generated training data. We randomly
generate 1,000 nets for each degree between 3 and 50 which makes training
uniform across net degrees. We do not use nets of degrees larger than 50 in
training. We use standard techniques for training using the sampled random
data by selecting 80% training and 10% validation data. We collected the final
accuracy of the training phase using the remaining 10% as test data, but
perform evaluation using more extensive, separate datasets in Section IV.

TABLE I: Training Dataset Statistics # of nets ($\times 10^{3}$) | # of nets by degree ($\times 10^{3}$) |  Degree of largest net
---|---|---
3-9 | 10-19 | 20-29 | 30-39 | 40-49 | 50
48 | 7 | 10 | 10 | 10 | 10 | 1 | 50

###  III-C Training Evaluation

We use Binary Focal Loss (BFL) [14] which weighs the less occurring labels
higher to train the model better. In our case, there are $\approx$6% Steiner
nodes and $\approx$94% non-Steiner nodes. This made it so that when it was
trained with unweighted binary cross-entropy, the model would always predict
non-Steiner for all nodes. On the other hand, BFL can be computed as

$BFL(p)=-\alpha(1-p)^{\gamma}\log(p)$ (4)

where $\alpha$ is the class balancing factor for class 1 (Steiner node);
$\gamma$ is the focal factor and $p$ is the model predicted probability. We
set the $\alpha$ value to 0.8, $\gamma$ value to 2, and used summation
reduction.

We also implemented a custom confusion matrix to use as the model’s accuracy
metric. This confusion matrix ignores accurate predictions of non-Steiner
nodes (true negatives). Since our labeled data had $\approx$94% non-Steiner
nodes, taking true negatives into account would generate a misleading
accuracy. The custom confusion matrix uses the following formula

$Accuracy=\begin{cases}\qquad\>\>\>1,&\text{if }TP+FP+FN=0\\\
\frac{TP}{(TP+FP+FN)},&\text{otherwise}\end{cases}$ (5)

where $TP$ is the correct prediction of Steiner nodes (true positives), $FP$
is the incorrect prediction of Steiner nodes (false positives), and $FN$ is
the incorrect prediction of non-Steiner nodes (false negatives). Some low
degree problems do not have any Steiner nodes since the original nodes align
perfectly. We assume these cases are correct predictions if the model predicts
all non-Steiner nodes. We used this metric for all accuracy reported in this
paper.

###  III-D Hyperparameter Tuning

We tuned model hyperparameters with Keras Tuner [15] using the range of values
in Table II and the Hyperband tuner [16] with Binary Focal Loss in Equation 4
on the validation set. We found the model with the highest accuracy for the
validation data had 2 GAT convolution layers. The first used ELU activation, 2
channels and 8 attention heads. The final layer used sigmoid activation and
had a fixed number of channels and number of attention heads of 1 in order to
produce a single probability value per node.

TABLE II: Model parameters Parameter | Range Explored | Best Value(s)
---|---|---
Number of GAT layers | [2, 8] | 2
Number of channels | [2, 64] | 2$\rightarrow$1
Number of attention heads | [1, 64] | 8$\rightarrow$1
Attention dropout | [0.0, 0.25] | 0.225
Layer dropout | [0.0, 0.25] | 0.0

###  III-E Non-Steiner Refinement

It is possible that we predict a node is a Steiner node when it is, in fact,
not one. This would be obvious if, for example, the degree of the “Steiner”
node is only 2 as in Fig. 3. We use quotes around the term Steiner in this
case, because the nodes are predicted as Steiner nodes but are not technically
Steiner nodes. For such cases, we developed a refinement strategy that is
applied to all nets with mispredicted degree-2 “Steiner” nodes:

1\. Consider all predicted Steiner nodes (of all node degrees) and remove the
node with the lowest probability. Then, run the MST algorithm again. Keep
doing step 1 until we no longer have degree-2 “Steiner” nodes.

2\. If the wire length has improved, return the last solution. Otherwise,
recover the initial solution before step 1 and continue with step 3.

3\. Consider only the degree-2 “Steiner” nodes and remove the node with the
lowest probability. Then, run the MST algorithm again. Keep doing step 3 until
we no longer have degree-2 “Steiner” nodes. Return the final solution.

In the worst case, this strategy will still have the same wire length as the
initial solution. Step 3 cannot worsen the wire length since we are only
removing degree-2 “Steiner” nodes, which are unnecessary.

Our non-Steiner refinement is different than other iterative Steiner
prediction methods [6] because we only examine degree-2 nodes that are
extremely rare whereas the other methods iteratively add one node at a time
for every Steiner node, which requires multiple calls to the GNN model
inference.

Figure 3: A net with a mispredicted degree-2 “Steiner” node (which isn’t by
definition a Steiner node) that increases the total wire length by 6.34%.

##  IV Results

###  IV-A Methodology

We implemented our model using the Tensorflow [17] and Spektral [18]. We used
the ADAM optimizer with a learning rate of 0.01 and early stopping with a
patience of 5 epochs.

All serial data generation, testing, and evaluation are done on a server with
two AMD EPYC 7542 32-core 2.9 GHz processors (128 threads total) and 512GiB
DRAM. Programs were run on a single core of this machine, and we have not used
a graphics processing unit (GPU) or tensor processing unit (TPU). Parallel
training, testing, and evaluation are done with a NVIDIA GeForce RTX 4090
24GiB card.

We used our serial-execution server for the other heuristics. We downloaded
the source codes of FLUTE and SALT. FLUTE has accuracy and local refinement
options. Accuracy is set to 3 by default, and can be 18 at maximum. Local
refinement is suggested to be enabled if accuracy is larger than 4. We
compiled FLUTE with two settings. FLUTE-3 is compiled with default options.
FLUTE-18 is compiled with accuracy set to 18 and local refinement enabled. For
both settings, we set the maximum degree to 3,000. SALT is compiled with the
same FLUTE-3 settings and given an epsilon value of 10,000 so that it will
optimize wire length instead of path length. We compiled GeoSteiner 5.3 with
ILOG CPLEX Optimization Studio 12.6.3 [19], a linear programming solver
library, for the best performance.

We used additional evaluation datasets from the ISPD 2019 routing contest
benchmarks [20] as well as random nets that were not used in training. Our
random evaluation nets include sizes greater than 50 whereas we only trained
on nets up to degree 50. The random evaluation dataset has 900 random nets
each for degrees 3 to 50, and 1,000 random nets for degrees 100, 200, 300,
400, 500, 1000, 2000, 3000. As can be seen in Table III, the random evaluation
data has a larger spread over all net sizes compared to the ISPD19 dataset.
ISPD19 only has a few nets with degree greater than 100.

TABLE III: Evaluation Dataset Statistics Dataset |  # of nets ($\times 10^{3}$) | Approx. # of nets by degree ($\times 10^{3}$) |  Degree of largest net
---|---|---|---
3-9 | 10-19 | 20-29 | 30-39 | 40-49 | 50-99 |  $\geq$100
Random | 440 | 63 | 90 | 90 | 90 | 90 | 9 | 8 | 3,000
ISPD19 | 382 | 335 | 14 | 3 | 14 | 3 | 10 | 0.02 | 2,556

###  IV-B Accuracy Analysis

The accuracy metric for the results is our custom confusion matrix in Eq. 5.
We generated solutions with GAT-Steiner, FLUTE, and SALT, and analyzed these
predictions based on the optimal solutions generated by GeoSteiner. Note that
our results regard label mispredictions with the same wire length as the
correct predictions.

With our model, mispredictions are either a missing Steiner node or an extra
Steiner node, with the majority of them being the latter due to the BFL
weights in Section III-C. Fig. 3 illustrates an example of such suboptimal
wire length net. Some problems might have multiple optimal solutions, or the
predicted RSMT might predict a node as a Steiner node when it is not needed
yet it does not affect the actual wire length of the net.

GAT-Steiner achieved 99.766% accuracy on the 10% of training data reserved for
testing, but we will do more thorough analysis in the rest of this section.

Table IV shows the average accuracy of Steiner point prediction for GAT-
Steiner and the other heuristics on all nets. GAT-Steiner performs by far
superior in the random evaluation over the other algorithms, since their
heuristic approach does not perform well for large degree nets. It still
performs slightly better on the ISPD19 dataset, which has a net degree
distribution similar of that of a common design.

TABLE IV: Net Wire Length Results Random Evaluation Dataset
---
| GAT-Steiner | FLUTE-3 | FLUTE-18 | SALT
Average accuracy | 99.992% | 52.071% | 79.446% | 51.027%
Suboptimal WL nets | 0.058% | 65.157% | 29.784% | 63.884%
Average WL increase | 0.420% | 1.610% | 0.516% | 1.575%
Max WL increase | 4.114% | 11.585% | 8.042% | 11.585%
ISPD19 Dataset
| GAT-Steiner | FLUTE-3 | FLUTE-18 | SALT
Average accuracy | 99.909% | 95.592% | 98.418% | 95.923%
Suboptimal WL nets | 0.154% | 6.600% | 2.640% | 5.770%
Average WL increase | 0.480% | 1.342% | 0.470% | 0.989%
Max WL increase | 11.708% | 23.276% | 13.157% | 19.767%

###  IV-C Suboptimality Analysis

We also did an analysis of the impact of mispredictions on solution quality.
Table IV shows the rate of suboptimal wire length nets. Many papers only
present the results including correctly predicted nets which can be misleading
since many easy nets are easily predicted correctly (e.g., 3-pin nets or nets
with no Steiner points) whereas harder nets can be far from optimal. Often,
benchmarks are dominated by easy nets, which give a misleading picture of
overall capability.

Fig. 4 shows the maximum, minimum and average wire length increase of
suboptimal wire length instances from all heuristics. The average and maximum
wire length increase is also in Table IV. The box and whisker plot defines an
outlier as 1.5x the inter-quartile range (IQR) from the box. GAT-Steiner has
the smallest wire-length increase in outliers and the fewest of them. Table V
further shows that the number of outliers from GAT-Steiner is 1-2 orders of
magnitude less than the other heuristic approaches.

Since both FLUTE and SALT inherently work better on smaller instances, they
have much worse accuracy on the random dataset which is distributed over a
larger range of net sizes (Table III).

TABLE V: Number of Outliers in Fig. 4 | FLUTE-3 | FLUTE-18 | SALT | GAT-Steiner
---|---|---|---|---
Random | 9,741 | 6,098 | 9,747 | 23
ISPD19 | 1,322 | 547 | 1,121 | 70

GAT-Steiner produced degree-2 nodes predicted as “Steiner” nodes for 2.254%
and 1.471% of the nets in the random dataset and the ISPD19 dataset,
respectively. On nets with these nodes, we ran our refinement algorithm from
Section III-E. 93.478% and 85.608% of these nodes were already the optimal
solutions and therefore removing the unnecessary degree-2 nodes did not alter
the solution. This is because the extraneous degree-2 nodes are usually on the
optimal path and do not affect the actual wire length. Since this refinement
step is only run for a small percentage of nets, its runtime overhead was
negligible.

Figure 4: GAT-Steiner makes an average error of less than 1% in wire length on
suboptimal nets across all datasets and has the smallest maximum suboptimal
wire length outlier. The red line shows the average wire length increase.
Figure 5: GAT-Steiner’s accuracy remains above 99% as problem size scales up
while other heuristics’ accuracy decline.

###  IV-D Parallelization Analysis

GeoSteiner, FLUTE, and SALT are implemented in single-threaded C/C++ programs;
therefore, they can only solve problems sequentially. Our model is implemented
in Python, which is slower than C/C++, but it can solve problems in parallel
using our GNN model on a GPU. Although our model might be slower than
GeoSteiner when only a single RSMT is solved, it has significant speedups when
RSMT instances are solved in parallel.

We used the random evaluation dataset to measure speedup since we have more
uniform data across degrees. We used the largest batch size that fit into the
GPU’s memory. For nets having degree 3 to 50, 1,000 nets fit into the memory.
For larger nets, we had to scale our batch size down. The batch size affects
the speed proportionally; therefore, it can be set higher if GPU memory
allows.

Fig. 6 and Fig. 7 show the total GPU execution time of all batches using the
random evaluation dataset. GeoSteiner, FLUTE, and SALT are run sequentially.
For the results shown in Fig. 6, the average speedup of GAT-Steiner is 9.363x
over GeoSteiner. GAT-Steiner achieved an average speedup of 24.305x for the
subset of Fig. 7. For the ISPD19 dataset, GAT-Steiner was able to run
inference with only 4 batches of size 100,000 total nets each.

Figure 6: GAT-Steiner has the advantage of parallelism for larger instances
compared to the other algorithms.  Figure 7: GAT-Steiner has a parallelism
advantage for large instances even if parallelism needs to be scaled down due
to GPU memory limits.

###  IV-E Hyperparameter Analysis

Using the best model according to the Keras tuner result in Table II as a
baseline, we explored the effects of each hyperparameter in our model
separately by performing a sensitivity analysis of each with the confusion
matrix accuracy (i.e., fixing every other parameter and then examining how the
accuracy of our model is affected).

From our analysis, we observed that beyond the optimal 2-layer configuration,
the accuracy significantly drops. This is in line with our expectations, since
we expect over-smoothing to be a factor with increasing number of layers.
Luckily, however, deep networks are unnecessary for even very large nets as
shown earlier.

The number of channels and the number of attention heads do not significantly
affect the accuracy and result in changes of at most 0.2%. For both
parameters, the accuracy almost reaches our optimal model’s with 2 channels
and 2 attention heads and beyond this point the accuracy mostly stays within a
$\pm$0.05% range. This provides insight that GAT-Steiner reaches a sufficient
number of learnable parameters with a relatively small number of channels and
attention heads. This also confirms (in addition to our evaluation
experiments) that we are not over-fitting the data.

Our model did not benefit from the use of feature dropout layers. We observed
that with dropout rates of just 2.5%, our model would lose about 5% accuracy.
We believe that this might be due to our model not having many input features
(i.e., just $x$ location, $y$ location, and node type). Since every feature is
critical to determining if a node is a Steiner node, feature dropout had a
negative effect on our model’s accuracy.

On the other hand, attention dropout is a similar mechanism except that a
neighbor’s effect on a node can be dropped out completely. In particular,
attention dropout prevents a node from relying on obtaining features through a
particular path in the graph to other nodes. Instead, attention dropout
requires that a node learn about nearby nodes and which features are shared
through multiple paths simultaneously. Attention dropout does affect overall
accuracy and enables the model to learn a more robust set of weights. However,
we saw that at attention dropout rates greater than 30%, the model starts to
mispredict more often.

##  V Conclusion

In this paper, we proposed GAT-Steiner, a graph attention network model to
predict Steiner points for the Rectilinear Steiner Minimal Tree (RSMT)
problems. GAT-Steiner can be used to predict RSMTs in bulk with very high
accuracy and 1-2 orders of magnitude fewer wire-length outliers than heuristic
approaches. Our model achieved 99.992% accuracy on the randomly generated test
data and 99.909% accuracy on the ISPD 2019 benchmarks.

## References

  * [1] D. Juhl, D. M. Warme, P. Winter, and M. Zachariasen, “The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study,” Mathematical Programming Computation, vol. 10, pp. 487–532, Dec 2018.
  * [2] C. Chu and Y.-C. Wong, “FLUTE: Fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 1, pp. 70–83, 2008.
  * [3] G. Chen, P. Tu, and E. F. Y. Young, “SALT: Provably good routing topology by a novel steiner shallow-light tree algorithm,” in 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 569–576, 2017.
  * [4] A. B. Kahng, R. R. Nerem, Y. Wang, and C.-Y. Yang, “NN-Steiner: A mixed neural-algorithmic approach for the rectilinear steiner minimum tree problem,” arXiv:2312.10589, 2023.
  * [5] S. Arora, “Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems,” J. ACM, vol. 45, p. 753–782, sep 1998.
  * [6] S. Wang, “Steiner Tree: a deep reinforcement learning approach,” Master’s thesis, University of Delaware, 2021.
  * [7] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph Attention Networks,” arXiv:1710.10903, 2018.
  * [8] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” arXiv:1609.02907, 2017.
  * [9] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” arXiv:1706.02216, 2018.
  * [10] T. K. Rusch, M. M. Bronstein, and S. Mishra, “A survey on oversmoothing in graph neural networks,” arXiv:2303.10993, 2023.
  * [11] K. Xu, C. Li, Y. Tian, T. Sonobe, K. ichi Kawarabayashi, and S. Jegelka, “Representation learning on graphs with jumping knowledge networks,” arXiv:1806.03536, 2018.
  * [12] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” arXiv:1706.03762, 2023.
  * [13] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: a simple way to prevent neural networks from overfitting,” The Journal of Machine Learning Research, vol. 15, no. 1, pp. 1929–1958, 2014.
  * [14] T.-Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár, “Focal loss for dense object detection,” arXiv:1708.02002, 2018.
  * [15] T. O’Malley, E. Bursztein, J. Long, F. Chollet, H. Jin, L. Invernizzi, et al., “KerasTuner,” 2019.
  * [16] L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar, “Hyperband: A novel bandit-based approach to hyperparameter optimization,” arXiv:1603.06560, 2018.
  * [17] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng, “TensorFlow: Large-scale machine learning on heterogeneous systems,” 2015.  Software available from tensorflow.org.
  * [18] D. Grattarola and C. Alippi, “Graph Neural Networks in TensorFlow and Keras with Spektral,” arXiv:2006.12138, 2020.
  * [19] IBM, “ILOG CPLEX Optimization Studio,” 2024.  https://www.ibm.com/products/ilog-cplex-optimization-studio.
  * [20] W.-H. Liu, S. Mantik, W.-K. Chow, Y. Ding, A. Farshidi, and G. Posser, “ISPD 2019 initial detailed routing contest and benchmark with advanced routing rules,” in International Symposium on Physical Design (ISPD), p. 147–151, 2019.