# Inferring equilibrium transition rates from nonequilibrium protocols

Benjamin Kuznets-Speck  Biophysics Graduate Group, University of California,
Berkeley, CA, 94720, USA  David T. Limmer<EMAIL_ADDRESS>Chemistry
Department, University of California, Berkeley, CA, 94720, USA  Chemical
Sciences Division, Lawrence Berkeley National Laboratory, Berkeley, CA, 94720,
USA  Material Sciences Division, Lawrence Berkeley National Laboratory,
Berkeley, CA, 94720, USA  Kavli Energy NanoSciences Institute, University of
California, Berkeley, CA, 94720, USA

###### Abstract

We develop a theory for inferring equilibrium transition rates from
trajectories driven by a time dependent force using results from stochastic
thermodynamics. Applying the Kawasaki relation to approximate the
nonequilibrium distribution function in terms of the equilibrium distribution
function and the excess dissipation, we formulate a nonequilibrium transition
state theory to estimate the rate enhancement over the equilibrium rate due to
the nonequilibrium protocol. We demonstrate the utility of our theory in
examples of pulling of harmonically trapped particles in 1 and 2 dimensions,
as well as a semi-flexible polymer with a reactive linker in 3 dimensions. In
all cases we find that we are able to infer the transition rates more
effectively than phenomenological approaches based on Bell’s law. We expect
our thermodynamic approach will find use in both molecular simulation and
force spectroscopy experiments.

††preprint: APS/123-QED

Extracting thermodynamic information from molecular systems through
irreversible and dissipative processes was made possible with the revelation
of Jarzynski’s equality. Jarzynski (1997); Crooks (1999); Hummer and Szabo
(2001, 2005) However, inference of kinetic information, such as the intrinsic
rate of molecular transitions, has remained more elusive.Hughes and Dougan
(2016) Although useful ways of extracting transition rates from single
molecule force data exist, for example, they often rely on fitting to
phenomenological expressionsBell (1978) or specifying a simple model of the
underlying conformational landscape. Hummer and Szabo (2003); Dudko, Hummer,
and Szabo (2008) Such theories also typically hinge on the limiting assumption
that the driving forces are adiabatic, so that the molecule is assumed to be
in instantaneous equilibrium with the experimental forces imposed on it. Here,
we report that a molecule’s bare equilibrium transition rate can be inferred
from the statistics of the excess heat released during a nonequilibrium
protocol. This result derives from expressions from stochastic
thermodynamicsSeifert (2012) and an extension of transition state theory into
nonequilibrium regimes.

One of the most common methods for extracting rate information from
nonequilibrium experiments and simulations employs the so-called Bell’s
law.Bell (1978) Bell’s phenomenological rate law postulates that the speed of
a molecular transition is accelerated with an applied external force by a
factor that varies exponentially

$k_{\lambda}\approx k_{0}e^{\beta\lambda x^{\dagger}},\,$ (1)

where $k_{\lambda}$ is the rate in the presence of the external force
$\lambda$, $k_{0}$ is the equilibrium rate, $x^{\dagger}$ is the distance
along the forcing direction between the reactant state and a putative
transition state, and $\beta$ is the inverse temperature times Boltzmann’s
constant. Evans and Richie showed that such a form emerges from Kramer’s
theory of transition rates when considering the special case of pulling a
simple harmonic molecule through a transition state adiabatically.Evans and
Ritchie (1997) Dudko, Hummer and Szabo Dudko, Hummer, and Szabo (2006)
developed additional expressions for the rate amplification based on different
potentials and the assumption of adiabaticity, and more recently, introduced a
model-free method of estimating the force-dependent transition rate with
statistics from the rupture force distribution.Dudko, Hummer, and Szabo (2008)
Using a nonequilibrium response relation for reaction rates,Kuznets-Speck and
Limmer (2021) we provide a general perspective on the origin of Bell’s law,
from which we can develop systematic corrections. We explore the subsequent
generalizations in a number of molecular systems with increasing complexity,
and study the utility of model-independent rate estimates that depend only on
the statistics of the dissipation, a quantity that is measurable
experimentally.

To start, we demonstrate how Bell’s law can be understood as a consequence of
two distinct approximations, a transition state theory approximation and a
near equilibrium approximation. Within transition state theory, the rate of a
transition between two metastable states is

$k_{\lambda}=\nu p_{\lambda}(x^{\dagger})$ (2)

where $\nu$ is the probability flux through $x^{\dagger}$ and
$p_{\lambda}(x^{\dagger})$ the probability to reach a transition state, or
dividing surface in phase space between metastable states.Peters (2017) This
expression is an approximation to the rate because $\nu$ in principle depends
on $x^{\dagger}$, and errors associated with this approximation can be
minimized with a judicious choice of dividing surface.Chandler (1978) In
equilibrium, the probability to reach a transition state is given by a
Boltzmann distribution, $p_{0}(x^{\dagger})\propto\exp[-\beta
F(x^{\dagger})]$, where $F(x^{\dagger})$ is the free energy to reach
$x^{\dagger}$, resulting in the expected Arrhenius temperature dependence.

While transition state theory in still applicable to system away from
equilibrium,Bouchet and Reygner (2016); Banik, Chaudhuri, and Ray (2000);
Kuznets-Speck and Limmer (2021) the likelihood of reaching the transition
state is not generally known, rendering it difficult to employ. For a system
initially in equilibrium and acted upon by an external force, the
nonequilibrium distribution is encoded in the Kawaski relation,Yamada and
Kawasaki (1967); Morriss and Evans (1985); Crooks (2000); Lesnicki  _et al._
(2021)

$p_{0}(\mathbf{x})=p_{\lambda}(\mathbf{x})\left\langle e^{-\beta
Q}\right\rangle_{\lambda,\mathbf{x}}$ (3)

where $p_{0}(\mathbf{x})$ is the initial equilibrium probability of
configuration $\mathbf{x}$, $p_{\lambda}(\mathbf{x})$ is the nonequilibrium
probability distribution, and the brackets
$\left\langle\dots\right\rangle_{\lambda,\mathbf{x}}$ denote an average under
the driving force $\lambda$ conditioned on ending at $\mathbf{x}$. The excess
heat dissipated to the environment, $Q$, due to the driving force is given by

$Q(t)=\int_{0}^{t}dt^{\prime}\dot{\mathbf{x}}(t^{\prime})\cdot\bm{\lambda}(\mathbf{x},t^{\prime}),$
(4)

which for a single molecule pulling experiment could be inferred from the
force-extension curve.

If the barrier to transitioning is large, we expect that the dominant change
in the rate under an additional force is due to modulation of
$p(x^{\dagger})$, leaving the location and flux through the transition state
unchanged. Under these assumptions, we employ the Kawaski relationship
together with transition state theory to relate the rates in the presence and
absence of $\lambda$,

$\frac{k_{\lambda}}{k_{0}}\approx\langle e^{-\beta
Q}\rangle_{\lambda,x^{\dagger}}^{-1}\,,$ (5)

to the statistics of the dissipation. In this limit, the Kawasaki response
relation connects the transition rate amplification and the distribution of
excess heat dissipated to the bath. A similar rate enhancement relation has
been derived from path ensemble techniques.Kuznets-Speck and Limmer (2021)
Under an assumption of small applied force, the equilibrium rate can be
estimated with a cumulant expansion for small values of the $\beta Q$ as

$\ln k_{0}\approx\ln k_{\lambda}-\beta\langle
Q\rangle+\frac{\beta^{2}}{2}\langle\delta Q^{2}\rangle,$ (6)

which is our first main result. For simplicity of notation we drop the
explicit condition on the averages in the heat. It implies that measuring the
rate of a rare event, as determined by a mean first passage time to
$x^{\dagger}$, and accompanying heat statistics in a driven system, we can
infer the rate of a rare event in thermal equilibrium. This result can be
considered as a nonlinear response theory for the rate,Sivak and Crooks (2012)
in which frenetic contributions are neglected.Gao and Limmer (2019) It is
similar to higher order corrections to Bell’s law valid for constant applied
forces,Abkenar, Gray, and Zaccone (2017); Konda  _et al._ (2011) generalized
to nonequilibrium protocols.

Near-equilibrium, $\beta\langle Q\rangle\ll 1$, and for slow driving forces,
$\dot{\lambda}\approx 0$, the heat dissipated up the transition state
$x^{\dagger}$ is well approximated by $\langle
Q\rangle_{\lambda,x^{\dagger}}\approx\lambda x^{\dagger}$, where we have
included only terms first order in $\lambda$ and integrated Eq. 4 by parts.
Such an approximation is good when the transition remains activated, so the
dynamics along the transition path relax much faster than the transition
waiting time. Substituting this approximation for the average heat into Eq. 6
and truncating at first order, we find Bell’s law. This is our second main
result.

Figure 1: Pulling on a harmonic molecule. (a) A cartoon of the time dependent
potential, initial barrier height $\beta\Delta U^{\dagger}$, and absorbing
boundary condition, $x^{\dagger}$. (b) The heat dissipated gives Bell’s law in
the small loading rate, long rupture time limit. Dashed curves are Bell’s law
and the solid curves the full dissipation for three potential stiffnesses. (c)
Estimates of the equilibrium escape rate for increasing barrier heights and a
range of pulling velocities.

Understanding the general thermodynamic origin of Bell’s phenomenological law
allows us to systematically improve upon it. In order to test such
corrections, we have considered a hierarchy of models with increasing
complexity. In each, we apply a simple force ramp, with constant velocity $v$
so that $\lambda\propto v$, and we measure the rate under this driving
protocol, $k_{v}$, as a mean first passage time to an absorbing boundary
condition. The first model we consider is a simple overdamped particle trapped
in a harmonic potential in one dimension, labeled $x$. The equation of motion
is

$\dot{x}=\mu F(x)+\mu\lambda+\sqrt{2D}\eta$ (7)

where the mobility $\mu$ and diffusivity $D$ satisfy an Einstein relation
$\beta D=\mu$, $F$ is a conservative force, and $\eta$ is a Gaussian random
variable with $\langle\eta\rangle=0$ and
$\langle\eta(t)\eta(t^{\prime})\rangle=\delta(t-t^{\prime})$. The conservative
force is $F=-a\kappa x$, and the particle is pulled with a linear ramp at
loading rate $v$, such that $\lambda=a\kappa vt$ as depicted in Fig. 1a. We
fix $\kappa=x^{\dagger}=\beta=\mu=1$ and vary $v=\\{0,..,0.5\\}$ and
$a=\\{8,10,12\\}$. Simulations are run from an initial condition at the origin
and stopped upon crossing $x^{\dagger}$ at $t=t_{\mathrm{rup}}$, where
$k_{v}=1/\langle t_{\mathrm{rup}}\rangle$. Time is measured in units of
$\tau=\kappa/\mu$. Associated with the location of the absorbing boundary
condition is an increased potential energy, equal to $\Delta
U^{\dagger}=a\kappa x^{{\dagger}2}/2$. We use a time step $t=10^{-2}\tau$ and
average over $10^{4}$ trajectories.

In Fig. 1b) we verify that the relationship between the heat and the argument
of the exponential in Bell’s law. Under a constant velocity force to lowest
order in $v$, $Q\approx\kappa vt_{\mathrm{rup}}$, which is plotted against the
full expression for $Q$. As expected, for small $v$, in which $\beta\langle
Q\rangle\ll 1$, both estimates agree. Note that $\langle Q\rangle$ does not
very linearly with $v$ because $t_{\mathrm{rup}}$ depends implicitly on
loading rate. Figure 1c) illustrates the convergence of the equilibrium rate
employing different estimators obtained from Eq. 6, for a range of pulling
velocities and barrier heights. The Bell’s law like rate estimate, correcting
the rate with just the mean heat, approaches the true equilibrium rate $\ln
k_{0}$ from below. Within the validity of transition state theory, this
behavior can be understood as a consequence of Jensen’s inequality, applied to
Eq. 5. Including additional dissipation statistics as in the full expression
in Eq. 6 yields a faster convergence to the equilibrium rate for all barrier
heights considered. Significant deviations from Eq. 6 occur when the
dissipation is comparable to the size of the energy barrier, in which case the
barrier is degraded enough for the event to no longer be rare.

Figure 2: Protocol dependence. (a) The potential energy surface in the
molecular $x$ and observed $q$ coordinates with absorbing boundary placed at
$x^{\dagger}=1.5$. (b) Nonequilibrium rate estimates labeled as in Fig. 1c.
(c) Modulation of the nonequilibrium rate with pulling velocity and angle
relative to the $q$ axis where the reference rate is taken as pulling along
the $q$ direction. (d) Modulation of the dissipated heat with pulling velocity
and angle relative to the $q$ axis labeled as in (c) and reference
analogously.

We now consider a simple model often adopted in force spectroscopy studies to
understand the role of flexible linkers. Specifically, we consider overdamped
motion in 2 spatial dimensions,

$\dot{\mathbf{r}}=-\bm{\mu}\nabla
U(\mathbf{r})+\bm{\mu}\lambda+\sqrt{2\mathbf{D}}\bm{\eta}$ (8)

where $\mathbf{r}=\\{q,x\\}$, and $q$ is envisioned as a measured extension
that is coupled to the true molecular extension, $x$, through a potential

$U(\mathbf{r})=\Delta
Ux^{2}(x-2)^{2}+\kappa_{l}(x-q)^{2}/2+\kappa_{m}\mathbf{r}^{2}/2$ (9)

where $\Delta U$ denotes the height of the barrier in the molecular
coordinate, while $\kappa_{l}$ and $\kappa_{m}$ are stiffnesses associated
with the linker and trap, respectively.Hinczewski  _et al._ (2013); Cossio,
Hummer, and Szabo (2015); Berezhkovskii  _et al._ (2014); Manuel, Lambert, and
Woodside (2015); Neupane and Woodside (2016) In this simplest multi-
dimensional model of a single molecule pulling experiment, the molecule
undergoes diffusion in the 2-d landscape as shown in Fig. 2a. We perform
force-ramp simulations with an added force
$\mathbf{\lambda}=a\kappa_{m}\mathbf{e}_{\Theta}vt$, parameterized by a
pulling vector $\mathbf{e}_{\theta}=\\{\cos(\Theta),\sin(\Theta)\\}$
determined by the angle $\Theta$ relative to the $q$ axis. We fix
$\kappa_{m}=\kappa_{l}=\beta=\mu_{q}=1$, $x^{\dagger}=1.5$,
$\kappa_{l}=\kappa_{m}=5$, $\beta\Delta U=5$ and vary $v=\\{0,..,0.5\\}$ and
$\Theta$. As before we estimate averages from 104 trajectories with an
absorbing boundary condition at $x^{\dagger}$.

We first consider the inference of the equilibrium rate in the difficult case
of pulling along $\Theta=0$ and where the $x$ direction is slow,
$\mu_{q}/\mu_{x}=20$. Under these conditions, shown in Fig. 2b, we observe
that similar to the harmonic oscillator, the dissipative second-cumulant
estimate of Eq. 6 converges faster to the exact equilibrium rate $\ln k_{0}$,
than either the bare driven rate or the generalized Bell’s law estimate, $\ln
k_{0}\approx\ln k_{v}-\beta\langle Q\rangle$. As before, the estimate from the
mean dissipation converges from below, however in this case the inclusion of
the second cumulant results in convergence from above. This is a consequence
of the nonlinear system considered in this example, where the non-Gaussian
heat statistics manifest an enhanced variance.

In order to understand the protocol dependence of our rate inference, we
consider $\mu_{q}/\mu_{x}=1$ and vary $\Theta$ and $v$ in Figs. 2c and 2d. As
expected, pulling along the molecular coordinate $x$,
$\Theta=90^{\mathrm{o}}$, results in a faster process relative to
$\Theta=0^{\mathrm{o}}$, and one which dissipates less heat as quantified by
$\Delta\langle Q\rangle_{\Theta}=\langle Q\rangle_{\Theta}-\langle
Q\rangle_{0}$. The rate within the driven dynamics is maximized near
$\Theta=60^{\mathrm{o}}$, which is in reasonable agreement with the optimal
transition state predicted by multidimensional transition state
theory.Berezhkovskii and Szabo (2005) For small $v$, near equilibrium, the
dissipated heat approaches zero independent of $\Theta$ as expected for a
quasi-reversible process. These results suggest that pulling along any
direction may be sufficient to estimate $\ln k_{0}$, but geometries that
minimize the heat until rupture may lead to faster convergence of Eq. 6.

Figure 3:  (a) A semi-flexible polymer with reactive ends, highlighted in red,
mechanically unfolded to a large end to end distance during a force ramp
experiment. (b) The free energy of the untethered polymer as a function of the
end to end distance. The black dashed line denotes the absorbing boundary
condition. (c) Nonequilibrium rate estimates, labeled as in Fig 1c, as a
function of heat.

As an example of a non-linear many-particle system, we consider stretching a
semi-flexible polymer with reactive endsWu  _et al._ (2018) that attract each
other with a strong, short-ranged potential. The configuration of the polymer
consists of 3$N$ dimensions,
$\mathbf{r}=\\{\mathbf{r}_{1},\dots,\mathbf{r}_{N}\\}$, and evolves with
underdamped Langevin dynamics

$m\mathbf{\ddot{r}}_{i}=-\mu^{-1}\mathbf{\dot{r}}_{i}-\bm{\nabla}_{i}U(\mathbf{r})+\bm{\lambda}+\mu^{-1}\sqrt{2D}\bm{\eta_{i}}.$
(10)

where $m$ is the mass of a monomer. The monomers interact through a potential
that consists of
$U(\mathbf{r})=U_{\mathrm{b}}(\mathbf{r})+U_{\mathrm{a}}(\mathbf{r})+U_{\mathrm{nb}}(\mathbf{r})$
where $U_{\mathrm{b}}(\mathbf{r})$ is a harmonic bond potential between
adjacent monomers

$U_{\mathrm{b}}(\mathbf{r})=\frac{\kappa_{\mathrm{b}}}{2}\sum_{i=1}^{N-1}\left(\mathbf{r}_{i+1}-\mathbf{r}_{i}\right)^{2}$
(11)

with stiffness $\kappa_{\mathrm{b}}$ and $U_{\mathrm{a}}(\mathbf{r})$ is a
harmonic angular potential that penalizes bending

$U_{\mathrm{a}}(\mathbf{r})=\frac{\kappa_{\mathrm{a}}}{2}\sum_{i=2}^{N-1}\left(\frac{\mathbf{r}_{i+1,i}\cdot\mathbf{r}_{i,i-1}}{{r}_{i+1,i}{r}_{i,i-1}}-1\right)^{2}$
(12)

where $\mathbf{r}_{i,i-1}=\mathbf{r}_{i}-\mathbf{r}_{i-1}$ is the vector
between two adjacent monomers, ${r}_{i,i-1}$ denotes its magnitude, and the
potential has a stiffness $\kappa_{\mathrm{a}}$. The nonbonding potential
$U_{\mathrm{nb}}(\mathbf{r})$ has a short ranged form,

$U_{\mathrm{nb}}(\mathbf{r})=\frac{1}{2}\sum_{i\neq
j=1}^{N}\epsilon_{ij}\left[5\left(\frac{\sigma}{r_{i,j}}\right)^{12}-6\left(\frac{\sigma}{r_{i,j}}\right)^{10}\right]$
(13)

where $\sigma$ sets the characteristic size of a monomer and $\epsilon_{ij}$
the interaction strength between monomer $i$ and $j$. In order to model a
reactive linker, we set the two monomers on each end to interact more strongly
than the monomers in the interior of the polymer, and the cross interactions
are neglected. We hold the 1st monomer fixed at the origin, so the end to end
vector is $\mathbf{R_{EE}}=\mathbf{r_{N}}$, and pull the two ends apart with
$\bm{\lambda}=-\kappa(\mathbf{R_{EE}}-vt\mathbf{\hat{x}})$. Characteristic
snapshots are shown in Fig. 3a). We adopt a unit system with
$\beta=m=\sigma=1$, so that $\tau=1/\sqrt{\beta m\sigma^{2}}$. We set $\mu=5$,
$\kappa_{\mathrm{b}}=110$, $\kappa_{\mathrm{a}}=4.5$, $\kappa=5.5$, end
monomer interactions $\epsilon_{1,N}=4.5$, and interior monomer interactions
$\epsilon_{3,N-3}=1.7$, $N=50$. We employ a time step of 10${}^{-2}\tau$ and
estimate averages from 500 trajectories.

Under these conditions, the semi-flexible polymer permits two types of
conformations– a folded state for small $\mathbf{R_{EE}}$ where the linker
monomers are bound, and an unfolded state for large $\mathbf{R_{EE}}$ where
the linker monomers do not interact strongly. To differentiate between these
two regions, we first computed the work to pull $\mathbf{R_{EE}}$ reversibly,
denoted by $\beta\Delta F(\mathbf{R_{EE}})$. This is shown in Fig. 3b), and
evaluated using the Jarzynski equalityJarzynski (1997) within a steered
molecular dynamics framework.Park and Schulten (2004) For the free energy
calculation we employed the same constant $v$ protocols, including all of the
simulation data shown in Fig. 3c). The free energy exhibits a deep minima for
small end to end distances and a second shallow basin for large end to end
distances. Under a small additional load,
$-\kappa_{\mathrm{EE}}\mathbf{R_{EE}}$, the two basins are separated by a
barrier in the free energy. Using this biased free energy we set an absorbing
boundary condition for our pulling calculation to
$\mathbf{R_{EE}}^{\dagger}=2.5\sigma$.

We pulled the polymer at loading rates over the interval
$v=\\{0.001-0.2\\}\sigma/\tau$ and measured the dissipative heat and first
passage time to $\mathbf{R_{EE}}^{\dagger}$. Shown in Fig. 3c), we find that
convergence to the true equilibrium rate is fastest using Eq. 6, and as in the
2d model the estimate converges from above. As in both previous models, the
incorporation of the variance of the heat provides an accurate estimate of the
equilibrium over a range of heats that is comparable to a significant fraction
of the native barrier, in this case as long as $\beta\langle Q\rangle<3$. The
first order estimate converges to the true equilibrium rate slowly from below.
Over the range of pulling velocities considered, if either the Bell’s law
estimate or the bare rate were fit and linearly extrapolated to $v=0$, both
would provide an estimate of the equilibrium rate that is about an order of
magnitude too high.

Taken together, our results demonstrate an underlying stochastic thermodynamic
basis for Bell’s law under nonequilibrium driving and a useful means for going
beyond it to infer equilibrium transition rates. Within the context of single
molecule force ramp experiments, we have demonstrated a robust way to infer
unfolding rates using the first two cumulants of the heat distribution,
conditioned on ending at an absorbing transition state. In the future, this
perturbative response method may be used to study the rare kinetics of more
detailed protein models, protein unfolding in optical tweezing and atomic
force microscopy experiments, and other molecular transitions that can be sped
up by applied force.Bustamante  _et al._ (2021); Petrosyan, Narayan, and
Woodside (2021); Wang and Dudko (2021); Zhang and Dudko (2015) The
nonequilibrium thermodynamic framework developed here works not only with
constant velocity force ramps, but could be used with more complex protocols.
Indeed, protocols can be optimized to allow for rate inferences,Das, Kuznets-
Speck, and Limmer (2022) or could be used as a theoretical framework for
understanding other approximate methods that use driven dynamics to infer
rates with applied force.Voter (1997); Peña Ccoa and Hocky (2022); Khan,
Dickson, and Peters (2020); Tiwary and Parrinello (2013)

Acknowledgements The authors would like to thank Glen Hocky and Carlos
Bustamante for helpful discussions during the preparation of this manuscript.
This work has been supported by NSF Grant CHE-1954580

## References

## References

  * Jarzynski (1997) C. Jarzynski, “Nonequilibrium equality for free energy differences,” Physical Review Letters 78, 2690 (1997).
  * Crooks (1999) G. E. Crooks, “Entropy production fluctuation theorem and the nonequilibrium work relation for free energy differences,” Physical Review E 60, 2721 (1999).
  * Hummer and Szabo (2001) G. Hummer and A. Szabo, “Free energy reconstruction from nonequilibrium single-molecule pulling experiments,” Proceedings of the National Academy of Sciences 98, 3658–3661 (2001).
  * Hummer and Szabo (2005) G. Hummer and A. Szabo, “Free energy surfaces from single-molecule force spectroscopy,” Accounts of chemical research 38, 504–513 (2005).
  * Hughes and Dougan (2016) M. L. Hughes and L. Dougan, “The physics of pulling polyproteins: a review of single molecule force spectroscopy using the afm to study protein unfolding,” Reports on Progress in Physics 79, 076601 (2016).
  * Bell (1978) G. I. Bell, “Models for the specific adhesion of cells to cells: a theoretical framework for adhesion mediated by reversible bonds between cell surface molecules.” Science 200, 618–627 (1978).
  * Hummer and Szabo (2003) G. Hummer and A. Szabo, “Kinetics from nonequilibrium single-molecule pulling experiments,” Biophysical journal 85, 5–15 (2003).
  * Dudko, Hummer, and Szabo (2008) O. K. Dudko, G. Hummer, and A. Szabo, “Theory, analysis, and interpretation of single-molecule force spectroscopy experiments,” Proceedings of the National Academy of Sciences 105, 15755–15760 (2008).
  * Seifert (2012) U. Seifert, “Stochastic thermodynamics, fluctuation theorems and molecular machines,” Reports on progress in physics 75, 126001 (2012).
  * Evans and Ritchie (1997) E. Evans and K. Ritchie, “Dynamic strength of molecular adhesion bonds,” Biophysical journal 72, 1541–1555 (1997).
  * Dudko, Hummer, and Szabo (2006) O. K. Dudko, G. Hummer, and A. Szabo, “Intrinsic rates and activation free energies from single-molecule pulling experiments,” Physical review letters 96, 108101 (2006).
  * Kuznets-Speck and Limmer (2021) B. Kuznets-Speck and D. T. Limmer, “Dissipation bounds the amplification of transition rates far from equilibrium,” Proceedings of the National Academy of Sciences 118, e2020863118 (2021).
  * Peters (2017) B. Peters,  _Reaction rate theory and rare events_ (Elsevier, 2017).
  * Chandler (1978) D. Chandler, “Statistical mechanics of isomerization dynamics in liquids and the transition state approximation,” The Journal of Chemical Physics 68, 2959–2970 (1978).
  * Bouchet and Reygner (2016) F. Bouchet and J. Reygner, “Generalisation of the eyring–kramers transition rate formula to irreversible diffusion processes,” in  _Annales Henri Poincaré_ , Vol. 17 (Springer, 2016) pp. 3499–3532.
  * Banik, Chaudhuri, and Ray (2000) S. K. Banik, J. R. Chaudhuri, and D. S. Ray, “The generalized kramers theory for nonequilibrium open one-dimensional systems,” The Journal of Chemical Physics 112, 8330–8337 (2000).
  * Yamada and Kawasaki (1967) T. Yamada and K. Kawasaki, “Nonlinear effects in the shear viscosity of critical mixtures,” Progress of Theoretical Physics 38, 1031–1051 (1967).
  * Morriss and Evans (1985) G. P. Morriss and D. J. Evans, “Isothermal response theory,” Molecular Physics 54, 629–636 (1985).
  * Crooks (2000) G. E. Crooks, “Path-ensemble averages in systems driven far from equilibrium,” Physical review E 61, 2361 (2000).
  * Lesnicki  _et al._ (2021) D. Lesnicki, C. Y. Gao, D. T. Limmer, and B. Rotenberg, “On the molecular correlations that result in field-dependent conductivities in electrolyte solutions,” The Journal of chemical physics 155, 014507 (2021).
  * Sivak and Crooks (2012) D. A. Sivak and G. E. Crooks, “Near-equilibrium measurements of nonequilibrium free energy,” Physical Review Letters 108, 150601 (2012).
  * Gao and Limmer (2019) C. Y. Gao and D. T. Limmer, “Nonlinear transport coefficients from large deviation functions,” The Journal of chemical physics 151, 014101 (2019).
  * Abkenar, Gray, and Zaccone (2017) M. Abkenar, T. H. Gray, and A. Zaccone, “Dissociation rates from single-molecule pulling experiments under large thermal fluctuations or large applied force,” Physical Review E 95, 042413 (2017).
  * Konda  _et al._ (2011) S. S. M. Konda, J. N. Brantley, C. W. Bielawski, and D. E. Makarov, “Chemical reactions modulated by mechanical stress: extended bell theory,” The Journal of chemical physics 135, 164103 (2011).
  * Hinczewski  _et al._ (2013) M. Hinczewski, J. C. M. Gebhardt, M. Rief, and D. Thirumalai, “From mechanical folding trajectories to intrinsic energy landscapes of biopolymers,” Proceedings of the National Academy of Sciences 110, 4500–4505 (2013).
  * Cossio, Hummer, and Szabo (2015) P. Cossio, G. Hummer, and A. Szabo, “On artifacts in single-molecule force spectroscopy,” Proceedings of the National Academy of Sciences 112, 14248–14253 (2015).
  * Berezhkovskii  _et al._ (2014) A. M. Berezhkovskii, A. Szabo, N. Greives, and H.-X. Zhou, “Multidimensional reaction rate theory with anisotropic diffusion,” The Journal of chemical physics 141, 11B616_1 (2014).
  * Manuel, Lambert, and Woodside (2015) A. P. Manuel, J. Lambert, and M. T. Woodside, “Reconstructing folding energy landscapes from splitting probability analysis of single-molecule trajectories,” Proceedings of the National Academy of Sciences 112, 7183–7188 (2015).
  * Neupane and Woodside (2016) K. Neupane and M. T. Woodside, “Quantifying instrumental artifacts in folding kinetics measured by single-molecule force spectroscopy,” Biophysical journal 111, 283–286 (2016).
  * Berezhkovskii and Szabo (2005) A. Berezhkovskii and A. Szabo, “One-dimensional reaction coordinates for diffusive activated rate processes in many dimensions,” The Journal of chemical physics 122, 014503 (2005).
  * Wu  _et al._ (2018) J. Wu, Y. Huang, H. Yin, and T. Chen, “The role of solvent quality and chain stiffness on the end-to-end contact kinetics of semiflexible polymers,” The Journal of Chemical Physics 149, 234903 (2018).
  * Park and Schulten (2004) S. Park and K. Schulten, “Calculating potentials of mean force from steered molecular dynamics simulations,” The Journal of chemical physics 120, 5946–5961 (2004).
  * Bustamante  _et al._ (2021) C. J. Bustamante, Y. R. Chemla, S. Liu, and M. D. Wang, “Optical tweezers in single-molecule biophysics,” Nature Reviews Methods Primers 1, 1–29 (2021).
  * Petrosyan, Narayan, and Woodside (2021) R. Petrosyan, A. Narayan, and M. T. Woodside, “Single-molecule force spectroscopy of protein folding,” Journal of Molecular Biology 433, 167207 (2021).
  * Wang and Dudko (2021) B. Wang and O. K. Dudko, “A theory of synaptic transmission,” Elife 10, e73585 (2021).
  * Zhang and Dudko (2015) Y. Zhang and O. K. Dudko, “Statistical mechanics of viral entry,” Physical review letters 114, 018104 (2015).
  * Das, Kuznets-Speck, and Limmer (2022) A. Das, B. Kuznets-Speck, and D. T. Limmer, “Direct evaluation of rare events in active matter from variational path sampling,” Physical Review Letters 128, 028005 (2022).
  * Voter (1997) A. F. Voter, “Hyperdynamics: Accelerated molecular dynamics of infrequent events,” Physical Review Letters 78, 3908 (1997).
  * Peña Ccoa and Hocky (2022) W. J. Peña Ccoa and G. M. Hocky, “Assessing models of force-dependent unbinding rates via infrequent metadynamics,” The Journal of Chemical Physics 156, 125102 (2022).
  * Khan, Dickson, and Peters (2020) S. A. Khan, B. M. Dickson, and B. Peters, “How fluxional reactants limit the accuracy/efficiency of infrequent metadynamics,” The Journal of Chemical Physics 153, 054125 (2020).
  * Tiwary and Parrinello (2013) P. Tiwary and M. Parrinello, “From metadynamics to dynamics,” Physical review letters 111, 230602 (2013).


# Paragraph2Graph: A GNN-based framework for layout paragraph analysis

Shu Wei
Datagrand Tech Inc.
<EMAIL_ADDRESS>
Nuo Xu
Datagrand Tech Inc.
<EMAIL_ADDRESS>
Deng Huang
Datagrand Tech Inc.
<EMAIL_ADDRESS>
Xiang Gao
Datagrand Tech Inc.
<EMAIL_ADDRESS>

###### Abstract

Document layout analysis has a wide range of requirements across various
domains, languages, and business scenarios. However, most current state-of-
the-art algorithms are language-dependent, with architectures that rely on
transformer encoders or language-specific text encoders, such as BERT, for
feature extraction. These approaches are limited in their ability to handle
very long documents due to input sequence length constraints and are closely
tied to language-specific tokenizers. Additionally, training a cross-language
text encoder can be challenging due to the lack of labeled multilingual
document datasets that consider privacy. Furthermore, some layout tasks
require a clean separation between different layout components without
overlap, which can be difficult for image segmentation-based algorithms to
achieve. In this paper, we present Paragraph2Graph, a language-independent
graph neural network (GNN)-based model that achieves competitive results on
common document layout datasets while being adaptable to business scenarios
with strict separation. With only 19.95 million parameters, our model is
suitable for industrial applications, particularly in multi-language
scenarios. We are releasing all of our code and pretrained models at this
repo.

_K_ eywords GNN $\cdot$ Language-independent $\cdot$ Document Layout $\cdot$
Layout Paragraph $\cdot$ Generalization

Figure 1: The overall Paragraph2Graph architecture. The whole pipeline
consists of five parts: node definition, edge definition, GNN, graph sampling
and task-specific layers;dotted lines represent invalid edge connections

##  1 Introduction

Document layout analysis is an important task for very-rich document
understanding. Given the availability to the text bounding boxes, text info
and document image, most current works either integrate all modalities
together with BERT-like encoders [1][2][3][4] or simply using visual
information [5] [6] to model the task as an object detection problem. While
effective, industrial applications need to consider very-long multilingual
paragraphs, which a BERT-like encoder fails to hold due to the limitation of
input sequence length and lack of multilingual document dataset. Moreover,
some scenarios expecting a clear separation between layout components make
image segmentation-based algorithms hard to adapt due to vague boundaries.
Although post-processing can handle the problems, hand-craft rules make the
pipeline complicated and hard to be maintained. In contrast, graph neural
networks (GNNs) can offer a promising alternative approach that does not rely
on language models.

With this work, we propose Paragraph2Graph, a language-independent GNN model
to address these limitations. Fig.1 shows the overall architecture. We first
encode image features with a pre-trained CNN backbone. Since each OCR box can
be regarded as a spatially-separated node of a graph, we therefore incorporate
the 2d OCR text coordinates, denoted as layout modality, and image features
together as node features. Then, we build our neural network with DGCNN [7] to
dynamically refresh the graph based on updated node features and layout
modality. As for edge features, besides simply concatenating two node
features, relationship proposals [8] is also used for better capturing the
relative spatial relationship. To improve the computation efficiency and
balance between positive and negative training pairs, we also propose a graph
sampling method based on layout modality. A sparse graph can benefit forward
and backward computations compared to fully-connected graphs. Finally, two
linear probes are trained to conduct node classification and edge
classification respectively.

Our method does not require the use of a tokenizer or language model to
extract text features as part of node embedding, making it language-
independent and efficient in terms of parameters. In contrast to Transformer
Encoder series or previous GNN works [9][10][11][12][13], we have shown that
Paragraph2Graph can easily generalize to multilingual documents without any
modifications. We also conducted experiments showing that a model trained on
Chinese documents performs similarly or even better on an English evaluation
dataset than a model trained on English documents. This demonstrates the
language-independence of our approach and indicates that the diversity of
document layouts is the primary factor affecting performance. Additionally,
our GNN models exhibit better generalization than object detection frameworks
such as Faster-RCNN and Mask-RCNN.

Our contributions can be summarized as follows:

  * •

We propose a language-independent GNN framework which we call the
Paragraph2Graph. The framework consists of node definition, edge definition,
graph sampling, GNN and task-specific layers. Each part of it can be easily
edited.

  * •

We offer an empirical selection for each part of the Paragraph2Graph that
achieves competitive results on several document layout analysis tasks.

  * •

We conduct extensive experiments and give our ablation analysis to justify the
effective design.

  * •

The language-independent design allows us to make use of all public datasets
to train a model regardless of language.

Figure 2: Three common practices for document layout analysis.

##  2 Related Work

Fig.2 shows three common practices for document layout analysis.

###  2.1 Layout Tasks use Transformer Encoder

A very-rich document has different modalities available across text info, text
position and image. To mimic how humans read, LayoutLM [1], LayoutLMv2 [2],
BROS [4] first integrate text features of each token with layout modality and
corresponding image features. Afterward, LayoutLMv3 [3] extends the visual
backbone to visual transformers. These frameworks define the document layout
analysis as a relation extraction and follow the same design by constructing a
fully-connected graph to calculate the relation score between all nodes. Then,
each relationship in the graph is inferred based on evaluating whether the
score is over a threshold or not. All tokens inferred to be relational are
grouped as one region. However, these methods are highly language-dependent
because of their language-specific tokenizers. Due to the lack of labeled
multilingual document datasets without privacy consideration, it is a
challenging alternative plan to train a cross-language tokenizer. Besides,
with the limitation of input sequence length, Transformer Encoder-series
methods cannot deal with very-long documents, such as dense tables in
financial reports. The high computational cost introduced by self-attention
and fully-connection graphs reduce the availability to the industry as well.

###  2.2 Layout Tasks use Object Detection

Document layout analysis is about detecting the layout location of
unstructured digital documents by returning bounding boxes and categories such
as figures, tables, headers, footers, paragraphs, etc. Such a task is
initially defined as an object detection problem on which many algorithms
[5][6] [14] related to object detection or segmentation have been successfully
applied. However, for all the object detection or segmentation models, the
predicted bounding boxes may overlap with each other due to the vague boundary
between instances as shown in Fig.3. The slight offset of the prediction boxes
has little effect on the training loss, which in turn contributes limited to
the model optimization to reach a high IoU. It’s hard to assign a label to a
text box that is either located at the edge of a predicted region or is shared
by multiple predicted regions, which makes the $AP^{IoU\geq 0.9}$ less
satisfying. It has to be mentioned that recent works [3][15][16] replacing CNN
backbone with vision transformer to achieve state-of-art results on public
datasets, but the uncompetitiveness of computation cost can’t be ignored.

(a) ground truth layout regions

(b)  predicted regions by an object detection method

Figure 3: (a) ground truth layout region (b) tricky cases that an object
detection method fails to handle with: region 1: shows one text box can locate
across two layout regions;region 2: the text box exactly located at the box
boundary;region 3: The text box is not located in any regions. green, red,
yellow, blue rectangle means detected regions for the Title, Text, Table, and
Page Foot.

###  2.3 Layout Task use GNN

Graph Neural Networks (GNNs) have their special advantages in modeling spatial
layout patterns of documents. Each text box of a document can be regarded as a
spatially-separated node in a graph;text boxes grouped in the same layout
region can be seen as being connected by edges. Since the document layout
analysis can be implemented as node and edge classification from a sampled
graph, there exist no vague text boxes hard to be assigned to a certain group.
We conclude a general pipeline covering all existing GNN-based layout analysis
algorithms——node definition, graph sampling, edge definition, GNNs and task-
oriented processing. Existing works only explore part of the pipeline.

For node definition, [9] uses char embedding with BiLSTM to integrate text
into node;[17] adds regional image feature from FPN output;[10] encodes box
coordinate $xywh$ into node embedding. Afterward, Post-OCR [18] adds
$cos\alpha,sin\alpha,xcos\alpha,xsin\alpha,ycos\alpha,ysin\alpha$ and the
width of the first word, where $\alpha$ is the angle of text box;ROPE[11]
explores the importance of the reading orders of given word-level node
representations in a graph;Doc2Graph [13] uses a pre-trained U-Net to get text
image feature;Doc-GCN [12] proposes a large collection for node definition,
which includes text embedding from BERT model, image feature from pre-trained
Faster-RCNN model, the number of tokens, the ratio of token number and box
area, and syntactic feature.

For edge definition, [9] uses horizontal and vertical distance and the ratio
of height between the two text boxes;ROPE[11] constructs with spatial
embeddings from horizontal and vertical normalized relative distances between
centers, top left corners, and bottom right corners and relative height and
width aspect ratios;Doc2Graph[13] uses the output of the last GNN layer,
softmax of the output logits and polar coordinates for node embedding.

For the GNN module, based on the vanilla GNNs, many works have studied
sophisticated designs to improve GNNs performances. Graph Convolutional
Networks [19] is a type of Graph Neural Network which applies convolution over
graph structures. This design is widely used in [12][20]. GAT[21] leverages
the self-attention mechanism into GNNs to decouple node update coefficients
from the structure of the graph. It has been used in [17][10][18].

For graph sampling, given that a document usually has a large number of text
boxes that can be regarded as nodes, it is essential to construct a graph with
both high connectivity and sparsity compared to a fully-connected graph to
allow necessary gradient propagation. [22] first proposes $\beta$-skeleton
graph;GraphSage [23] uniformly samples a set of nodes from the neighborhoods
and only aggregates feature information from sampled neighbors. [18][11][20]
all follow $\beta$-skeleton to build their graph, but the miss to cover
tabular structures where text box density is relatively high. K-Nearest
Neighbor is another good substitution, [10] set $K=10$ and [24] set $K=3$, but
it is still too tricky to tune satisfying parameters for different business
scenarios.

###  2.4 Other Tasks use GNN: table recognition, text line grouping

All aforementioned algorithms can be generalized to table recognition tasks by
simply modifying the task-oriented layers to represent whether two adjacent
cells are in the same row or col. For the table recognition task, [25] uses
KNN to construct a graph and represent text features by encoding character
embedding with GRU;[26] constructs a fully-connection graph and set weighted
loss to balance between positive and negative samples.[27] [28] [29] [30]
share the identical GNN structure. Text line grouping task is more easily
adaptable to GNN with minor changes. [24] predicts edge classified probability
to judge if the pivot and its neighbors are in the same line;[31] introduces
the residual connection mechanism for GNNs. In general, a powerful GNN model
can be used in many downstream document analysis tasks.

##  3 Method

We follow our conclusion to establish a unified pipeline covering all main
steps to build a GNN-based model for layout analysis: they include node
definition, graph sampling, edge definition, GNNs, and task-oriented
processing.

##### Node definition

Given a document image $D\in\mathbb{R}^{H\times W\times 3}$ with $N$ text
boxes generated by any commercial or open source Optical Character Recognition
(OCR) engine. we denote all text boxes as:
$\texttt{position\\_info}=\\{x_{min}^{n},y_{min}^{n},x_{max}^{n},y_{max}^{n}\mid
n\in[0,N-1]\\}$. The input image D is first resized into
$D^{\prime}\in\mathbb{R}^{400\times 400\times 3}$. $D^{\prime}$ is sent to a
pre-trained ResNet visual backbone to get a series of output features from
different scales. These features are integrated with $D^{\prime}$ into
$F\in\mathbb{R}^{400\times 400\times d}$ with an FPN structure. For $N$ text
boxes, we pick out their corresponding image features with ROIAlign and embed
them as $I^{N\times k}$, aka image embedding. $d$, $k$ is the intermediate
dimensions. Given the normalized bounding box, the layout information is
represented as
$\texttt{layout}_{n}=(x_{min}^{n},y_{min}^{n},x_{max}^{n},y_{max}^{n},x_{ctr}^{n},y_{ctr}^{n},w_{n},h_{n})$.
The layout information composes of bounding box coordinates, center point
coordinates, bounding box width and height to construct a token-level 2D
positional embedding, denoted as layout embedding. We then fuse layout
embedding and image embedding:

$\texttt{node\\_embedding}:=\texttt{MLP}(\texttt{Concate}(\texttt{image\\_embedding},\texttt{layout\\_embedding})$

##### GNN module

After gathering all the node features, they are passed as input to the
interaction model. We have tested two graph neural networks to use as the
interaction part which are the modified versions of [7] and [32] respectively.
These modified networks are referred to as DGCNN* and GravNet* hereafter. We
update the node features by aggregating weighted neighbor nodes with
DGCNN/GravNet.

$\texttt{node\\_embedding}=\max(\texttt{node\\_embedding},\texttt{DGCNN or
GravNet}(\texttt{node\\_embedding},\texttt{position\\_info}))$

##### Graph sampling

Text boxes classified into the same layout category can be regarded as having
an edge between them. We refer to this task as node grouping: to infer whether
there exists an edge between a node pair. To construct node pairs, we
therefore connect all potential edges between the nodes with a location-based
node search algorithm. Instead of constructing a fully-connected graph, our
method can both save computation costs and improve training efficiency. Based
on the common structure of a document, each text node can have potential edge
connections both vertically and horizontally. For each text box, we pick up
its top 1-2 location-nearest text boxes in four directions (top, bottom, left
and right). Complex cases need additional processing as shown in Fig.4-b. Our
method can effectively sample a sparse graph without missing necessary node
pairs. Comparison among KNN, $\beta$-skeleton, and our sampling methods can be
found in Appendix Fig.5.

(a) left

(b) right

Figure 4: Left: illustration of our graph sampling strategy: for each node
(shown in orange), we sample one edge horizontally (shown as red region) and
two edges vertically (shown as green region);Right: We vertically sample top-2
nearest edges instead top-1 to ensure the connectivity with this common right-
alignment paragraph structures

##### Edge definition

We concatenate the node feature of each valid node pair as $F_{pair}$.
Inspired by ROPE [11], we encode natural reading orders of words as $F_{rope}$
to help capture the better sequential presentation between nodes. A new
reading order code is first assigned to neighbors with respect to each text
box. Then, a sinusoidal encoding matrix is applied to encode the reading order
index.

We also consider that the relationship between nodes is an important feature
that has been ignored by [8]. Following the relationship proposal, suppose two
nodes have a potential relationship, we denote one node as $S$, a subject, the
other as $O$, an object, and the relationship as $R$.
$\Delta(S,O)=(t^{SO}_{x},t^{SO}_{y},t^{SO}_{w},t^{SO}_{h},t^{OS}_{x},t^{OS}_{y})$,
where

$t^{SO}_{x}=(x^{S}-x^{O})/w^{S},\quad t^{SO}_{y}=(y^{S}-y^{O})/h^{S}\\\ $ (1)
$t^{SO}_{w}=\log(w^{S}/w^{O}),\quad t^{SO}_{h}=\log(h^{S}/h^{O})\\\ $ (2)
$t^{OS}_{x}=(x^{O}-x^{S})/w^{O},\quad t^{OS}_{y}=(y^{O}-y^{S})/h^{O}$ (3)

$x^{S}$, $y^{S}$, $w^{S}$, $h^{S}$ represent the center coordinates, width,
and height of a subject box, similarly denotations apply for $x^{O}$, $y^{O}$,
$w^{O}$, $h^{O}$. The coordinates of $R$ is the minimum bounding rectangle of
$S$, $O$, which means

$(x_{min}^{R},y_{min}^{R},x_{max}^{R},y_{max}^{R})=\min(x_{min}^{O},x_{min}^{S}),\min(y_{min}^{O},y_{min}^{S}),max(x_{max}^{O},x_{max}^{S}),\max(y_{max}^{O},y_{max}^{S})$

The relationship feature $F_{rel}$ is defined as an concatenation of
$\Delta(S,O)$, $\Delta(S,R)$ and $\Delta(O,R)$. Finally, the edge feature is
formally represented as:

$F_{edge}=\texttt{Concate}(F_{pair},F_{rope},F_{rel})$

##### Task-oriented processing

For node classification, we apply a fully-connected layer to fuse features and
a linear layer $W^{h\times c}$ to classify each node. $h$ is the hidden
dimension and $c$ is the number of categories. For node grouping, we follow
the same idea as node classification: a fully-connected layer to fuse features
and a linear layer $W^{h\times 2}$ to infer whether there exists an edge
between a node pair or not. All connected nodes are regarded as layout
instance. The minimum bounding boxes of connected nodes are the final layout
bounding boxes. The category mode of connected nodes is the category of the
layout instance.

##  4 Experiments

Previous works propose various definitions on edge and nodes, but they either
get non-competitive results or introduce expensive computation costs. We
therefore study the combinations of these designs and compare them with object
detection and the Transformer Encoder model on several document layout
analysis tasks. Our experiments demonstrate the effectiveness and
competitiveness of our method.

We train our model with 1 GeForce 3090 GPUs from scratch, We use an Adam
optimizer with 0.937 momentum and 0.005 weight decay. The learning rate is set
to 0.0001.

###  4.1 Results on Public Datasets

##### FUNSD

The FUNSD [33] provides 199 annotated forms with 9, 707 entities and 31, 485
word-level annotations for four entity types: header, question, answer, and
other. It includes noisy scanned documents in English from various fields,
such as research, marketing, and advertising. This dataset is commonly used in
GNN-related papers, and we used it for our experiments for easy comparison.
FUNSD contains two level labels: word and entity. For word-level labels, we
predict the category of each word and determine whether two words belong to
the same entity. For entity-level labels, we adds two classification heads:
one for entity labeling and the other for entity linking, which predicts
whether two entities are matched.

We report our best hyperparameter configuration as shown in
Tab.LABEL:table:ablation ours-Large in the ablation experiment of section 4.3.
We train the models with a batch size of 2 for 60 epochs and a warm-up period
of 10 epochs. The training and validation set are split as provided, with 149
for training and 50 for evaluation.

To evaluate the performance of our method, we use multi-class F1-scores to for
node classification and binary edge classification F1-scores for grouping or
linking, along with corresponding precision and recall values. Our method
significantly outperformed previous works. Despite not using a language model,
our model had a significantly smaller number of parameters as shown in Tab.1.

In the entity task,our model shown in Tab.2, achieved a F1 score of 0.80575
for entity-labeling and 0.77031 for entity-linking, using 32.98 million
parameters. We achieved state-of-the-art results in entity linking,
outperforming other GNN models and the Transformer Encoder series. On the
entity labeling task, our F1 score was lower than some Transformer Encoder
modeles such as LayoutLMv2, LayoutLMv3, and BROS. This may be due to those
methods having more parameters and being pre-trained on several text-image
alignment tasks, giving them strong semantic and visual understanding
abilities. Despite being trained from scratch with only 149 samples, our model
still outperformed BERT, Roberta, and LayoutLM, and achieves significant
improvements over most previous GNN works. However, doc2graph performed
$1.6\%$ better than our model on the entity labeling task, but it still
suffers from the problems associated with language-based GNNs due to its use
of a language model. Compared to other state-of-the-art models, our GNN model
performed competitively.

| F1 | word-labeling | word-grouping | Params
---|---|---|---|---
GNN with Language model | FUNSD[33] | - | 0.41 | 340M
GNN with Language model | Named[10] | - | 0.65 | 201M
GNN with Language model | ROPE[11] | 0.5722 | 0.8933 | -
GNN | ours-Large | 0.68933 | 0.91483 | 32.98M
Table 1: Performance for word level on FUNSD. | F1 | entity-labeling | entity-linking | Params
---|---|---|---|---
GNN with Language model | FUNSD[33] | 0.57 | 0.04 | 340M
GNN with Language model | Named[10] | 0.64 | 0.39 | 201M
GNN | FUDGE[34] | 0.6652 | 0.5662 | 17M
GNN | Word-FUDGE[34] | 0.7221 | 0.6258 | 17M
GNN with Language model | Doc2Graph[13] | 0.8225 | 0.5336 | 6.2M+
Transformer Encoder | BERT-base[35] | 0.6026 | 0.2765 | 110M
Transformer Encoder | BERT-L[35] | 0.6563 | 0.2911 | 340M
Transformer Encoder | RoBERTa-base[36] | 0.6648 |  | 125M
Transformer Encoder | RoBERTa-L[36] | 0.7072 |  | 355M
Transformer Encoder | LayoutLM[1] | 0.7927 | 0.4586 | 113M
Transformer Encoder | LayoutLM-L[1] | 0.7789 | 0.4283 | 343M
Transformer Encoder | LayoutLMv2[2] | 0.8276 | 0.4291 | 200M
Transformer Encoder | LayoutLMv2-L[2] | 0.8420 | 0.7057 | 426M
Transformer Encoder | BROS[4] | 0.8305 | 0.7146 | 138M
Transformer Encoder | BROS-L[4] | 0.8452 | 0.7701 | 340M
Transformer Encoder | LayoutLMv3[3] | 0.9029 |  | 133M
Transformer Encoder | LayoutLMv3-L[3] | 0.9208 |  | 368M
GNN | ours-Large | 0.80575 | 0.77031 | 32.98M
Table 2: Performance for entity level on FUNSD. Doc2Graph params counts a
spaCy model and a pre-trained U-Net on FUNSD besides its own weights.

##### PublayNet

PublayNet[37] contains research paper images annotated with bounding boxes and
polygonal segmentation across five document layout categories: Text, Title,
List, Figure, and Table. The official splits contain 335, 703 training images,
11, 245 validation images, and 11, 405 test images. We train our model on the
training split and evaluate our model on the validation split following
standard practice. We train our models with the batch size of 4 for 5 epochs
and warm-up 1 epoch. Because of training resource limitations, we only report
our suboptimal configuration shown in Tab.LABEL:table:ablation ours-Small.

We measure the performance using the mean average precision (mAP) @
intersection over union (IOU) [0.50:0.95] of bounding boxes and report results
in Tab.3 with only two categories : Text and Title. Tab.11 shows all
categories. Our proposed GNN-based model outperforms several state-of-the-art
object detection models. Specifically, our model achieves a mAP of 0.954 and
0.913 for Text and Title detection, with a model size of 77M. Our model shows
better performance than Faster-RCNN,Cascade-RCNN and Mask-RCNN regardless of
whether they have been pretrained , which sizes ranging from 168M to 538M.
Compared to Faster-RCNN-Q and Post-OCR models with mAPs of 0.914 and 0.892
respectively, our GNN-based model achieves higher accuracy in Text category.
Fig.6 shows some cases of our algorithm on this dataset.

| mAP | Text | Title | Size
---|---|---|---|---
OD | Faster-RCNN[37] | 0.910 | 0.826 | -
OD | Mask-RCNN[37] | 0.916 | 0.84 | 168M
OD-pretrained | Faster-RCNN[UDoc][16] | 0.939 | 0.885 | -
OD-pretrained | Mask-RCNN[DiT-base][15] | 0.934 | 0.871 | 432M
OD-pretrained | Cascade-RCNN[DiT-base][15] | 0.944 | 0.889 | 538M
OD-pretrained | Cascade-RCNN[layoutlm-v3][3] | 0.945 | 0.906 | 538M
OD | Faster-RCNN-Q[18] | 0.914 |  | -
GNN | Post-OCR[18] | 0.892 |  | -
GNN | ours-Large | 0.954 | 0.913 | 77M
Table 3: Performance on Publaynet on paragraph categories.OD-pretrained means
object model use pretrained CNN.

##### Doclaynet

Doclaynet[38] is a recently released document layout dataset annotated in COCO
format. It contains 80863 manually annotated pages from diverse data sources
to represent a wide variability in layouts with 11 distinct classes: Caption,
Footnote, Formula, List-item, Page-footer, Page-header, Picture, Section-
header, Table, Text, and Title. Compared with publaynet, this dataset covers
more complex and diverse document types, including Financial Reports, Manuals,
Scientific Articles, Laws & Regulations, Patents and Government Tenders.

We use the same training parameters as in PubLayNet and evaluate the quality
of their predictions using mean average precision (mAP) with 10 overlaps that
range from 0.5 to 0.95 in steps of 0.05 (mAP@0.5-0.95). These scores are
computed by leveraging the evaluation code provided by the COCO API.
Similarly,we only compare categories belonging to the Paragraph type without
Table and Picture.The results shown in Tab.4 draw a similar conclusion as we
do in Publaynet: ours achieves better results with only 1/7 parameters with
respect to object detection models in total with a mAP of 0.771. Specifically,
our model performs exceptionally well in Page-Header, Caption, Section-Header,
Title, and Text detection with mAPs of 0.796, 0.809, 0.824, 0.643, and 0.827,
respectively. Comparatively, YOLO-v5x6 achieves best result in Footnote, Title
and Text.Tab.12 shows all categories.

mAP | Mask-RCNN-res50[38] | Mask-RCNN-resnext101[38] | Faster-RCNN-resnext101[38] | YOLO-v5x6[38] | ours-Small
---|---|---|---|---|---
Page-Header | 0.719 | 0.7 | 0.720 | 0.679 | 0.796
Caption | 0.684 | 0.715 | 0.701 | 0.777 | 0.809
Formula | 0.601 | 0.634 | 0.635 | 0.662 | 0.726
Page-Footer | 0.616 | 0.593 | 0.589 | 0.611 | 0.920
Section-Header | 0.676 | 0.693 | 0.684 | 0.746 | 0.824
Footnote | 0.709 | 0.718 | 0.737 | 0.772 | 0.625
Title | 0.767 | 0.804 | 0.799 | 0.827 | 0.643
Text | 0.846 | 0.858 | 0.854 | 0.881 | 0.827
Total-paragraph | 0.702 | 0.7143 | 0.7148 | 0.744 | 0.771
Params | - | - | 60M | 140.7M | 19.95M

Table 4: performance on Doclaynet on paragraph categories.

###  4.2 Discussion on Generalization of Language

To demonstrate the language-independence of our model, we first train our
model on datasets in English and evaluate them on a dataset in Chinese. Among
them, Publaynet is a pure English dataset, Doclaynet is mostly in English, and
DGDoc is a pure Chinese dataset containing 12, 000 images from real business
scenarios. We use the same F1 indicator as the experiment on FUNSD. As shown
in Tab.5, our models trained on Doclaynet data and models trained on Chinese-
data behave similarly on Publaynet, and even the latter one gets a higher F1
on two tasks. The model trained on Publaynet data and the model trained on
Chinese-data perform similarly on Doclaynet. This experiment proves that our
model has the language-independent ability, which allows us to focus more on
training data with diversity and complex layout structures instead of
languages. The most important advantage of this conclusion is that for non-
English application scenarios, we do not need to collect and annotate a large
number of documents, which is very time-consuming and expensive. Instead, we
can directly collect a variety of public datasets regardless of languages to
train the model.

F1 | val-doclaynet | val-publaynet | val-chineseData
---|---|---|---
node | edge | node | edge | node | edge
train-doclaynet | 0.94670 | 0.97267 | 0.95774 | 0.97171 | 0.85892 | 0.94851
train-publaynet | 0.72742 | 0.86069 | 0.98729 | 0.99302 | 0.76158 | 0.8839
train-chineseData | 0.88256 | 0.92285 | 0.96289 | 0.96847 | 0.97295 | 0.98872
Table 5: Comparison results for discussion on generalization of language.

###  4.3 Discussion on Generalization of Data Complexity

In order to compare the generalization of the model, we use two
datasets:Doclaynet is a more diverse dataset than Publaynet in layout. As
shown in Tab.6, if we trained on Publaynet and predicted on Doclaynet, both
models Mask-RCNN or our GNN-based model drop badly in mAP. But if we use the
model trained on Doclaynet to predict on Publaynet, our model only slightly
decreases, while Mask-RCNN drops significantly. It shows that as long as our
model has been trained on complex and diverse layouts, it can also migrate to
simple layouts well.

mAP | val-publaynet | val-doclaynet
---|---|---
maskrcnn-res50 | ours-Small | maskrcnn-res50 | ours-Small
train-publaynet | Section-Header | 0.87 | 0.913 | 0.32 | 0.484
Text | 0.96 | 0.954 | 0.42 | 0.338
train-doclaynet | Section-Header | 0.53 | 0.811 | 0.68 | 0.796
Text | 0.77 | 0.769 | 0.84 | 0.827
Table 6: Comparison results for discussion on generalization of data
complexity.

###  4.4 Ablation Experiments

####  4.4.1 Node-definition

When considering the node definition, we tested whether the box information is
4 values or 8, the backbone tried res-18 and res-50, GNN tried DGCNN and
GravNet, whether the GNN input and output are residual connect.The impact of
each factor was compared on four tasks for more comprehensive assessment in
Tab.7.The addition of residual connections (using res-18 or res-50) generally
leads to better performance than non-residual networks.The use of more big
backbone (res-50 vs res-18) can improve the results for all tasks.When
comparing different GNN models, DGCNN tend to perform better than
Gravnet.However the importance of box information is vague.

box-infor | backbone | GNN | GNN-res | WL | WG | EL | EG
---|---|---|---|---|---|---|---
4 | res-18 | D | - | 0.65189 | 0.86821 | 0.76458 | 0.67797
8 | res-18 | D | - | 0.63914$\downarrow$ | 0.86248$\downarrow$ | 0.77573 | 0.69695
8 | res-18 | D | + | 0.65579 | 0.86399$\downarrow$ | 0.77144 | 0.70509
8 | res-50 | D | - | 0.66774 | 0.87487 | 0.77873 | 0.71613
8 | res-18 | G | - | 0.58861$\downarrow$ | 0.84461$\downarrow$ | 0.71397$\downarrow$ | 0.60032$\downarrow$
Table 7: Ablation experiments of node definition on FUNSD: WL, WG, EL, EG
means word-labeling, word-grouping, entity-labeling, entity-linking;D and G
means DGCNN and Gravnet;box-info 4 means $x_{min},y_{min},w,h$, 8 means
$x_{min},y_{min},x_{max},y_{max},x_{center},y_{center},w,h$.

####  4.4.2 Edge-definition

As for edge definition , we tested four factors:whether to use
relationship,ROPE, polar and node class result as shown in Tab.8. Four tasks
is also WL (word-labeling), WG (word-grouping), EL (entity-labeling), and EG
(entity-linking). The results indicate that adding relation and node-class
edges improves the performance of all metrics except EG. Adding the ROPE edge
improves WL and WG but not EL and EG. Adding the polar edge does not
significantly affect the results.

relation[8] | ROPE[11] | polar[13] | node-class[13] | WL | WG | EL | EG
---|---|---|---|---|---|---|---
|  |  |  | 0.63478 | 0.86348 | 0.77873 | 0.70071
|  |  | + | 0.63914 | 0.86248$\downarrow$ | 0.77573$\downarrow$ | 0.69695$\downarrow$
+ |  |  | + | 0.63972 | 0.90039 | 0.77916 | 0.74759
+ | + | + | + | 0.63374$\downarrow$ | 0.89869$\downarrow$ | 0.77358$\downarrow$ | 0.74925
Table 8: Ablation experiments of edge definition on FUNSD: WL, WG, EL, EG
means word-labeling, word-grouping, entity-labeling, entity-linking.

####  4.4.3 Input Process & Loss

Tab.9 shows the results of various ablation experiments conducted on the FUNSD
dataset, using different input processes and loss functions. The first row
represents the baseline model, which uses a 400*400 image size and cross-
entropy (CE) loss. The effect of image padding is investigated by adding a
padding of unknown size to the input images. The results indicate that this
modification does not significantly affect the word-labeling metric but has a
negative impact on word-grouping, entity-labeling, and entity-linking.
Increasing the image size to 800*608 pixels leads to some improvement in the
word-grouping and entity-labeling metrics, but the word-labeling and entity-
linking scores remain relatively low.Adding a contrastive loss term in
addition to the cross-entropy loss leads to some improvement in all four
tasks.Overall, Padding may not be helpful, larger image sizes may not lead to
significant improvements, and the addition of a contrastive loss may be
beneficial.

image-size | image-pad | loss | WL | WG | EL | EG
---|---|---|---|---|---|---
400*400 |  | CE | 0.61066 | 0.86352 | 0.78216 | 0.72722
400*400 | + | CE | 0.63914 | 0.86248$\downarrow$ | 0.77573$\downarrow$ | 0.69695$\downarrow$
800*608 | + | CE | 0.68795 | 0.87782 | 0.81947 | 0.70487$\downarrow$
400*400 | + | CE+Con | 0.64178 | 0.87105 | 0.77658$\downarrow$ | 0.71704$\downarrow$
Table 9: Ablation experiments of input process and loss on FUNSD: WL, WG, EL,
EG means word-labeling, word-grouping, entity-labeling, entity-linking;CE and
Con means CE loss and Contrastive loss.

####  4.4.4 Final Best Model

Name | backbone | image-size | WL | WG | EL | EG
---|---|---|---|---|---|---
ours-Small | res-18 | 400*400 | 0.66579 | 0.90148 | 0.78216 | 0.75522
ours-Large | res-50 | 800*608 | 0.68933 | 0.91483 | 0.82504 | 0.77031
Table 10: Best model.

We study the combinations of a variety of designs for each component in the
GNN model and justify their effectiveness on our document layout analysis
tasks.

As seen in Tab.10, scale-up image size, relationship proposal, and larger CNN
backbone are useful to improve accuracy, while contrast loss, and Gravnet are
not. The importance of other factors is ambiguous to tell. DGCNN is a better
choice than Gravnet. Based on the detailed ablation experiment, we get the
best design combination is ours-Large. Since we enlarge the input image size,
more memory is cost. Therefore, on the large datasets DoclayNet and PublayNet,
we finally report the suboptimal configuration ours-Small instead.

##  5 Conclusion and Future Work

In this paper, we propose a language-independent GNN framework for document
layout analysis tasks. Our proposed model, Paragraph2Graph, uses a pre-trained
CNN to encode image features and incorporates 2d OCR text coordinates and
image features as node features in a graph. We use a dynamic graph
convolutional neural network (DGCNN) to update the graph based on these
features and include edge features based on relationships. To improve
efficiency, we also propose a graph sampling method based on layout modality.
Our method does not require a tokenizer or language model and can easily
generalize to multilingual documents without modifications. We show that our
method can achieve competitive results on three public datasets with fewer
parameters. There are several potential improvements and attempts we leave for
future work: (1) We have only experimented with only a few common GNNs, while
torch-geometric [39] officially offers nearly 60 related algorithms. Some of
them can be a better substitution for DGCNN. (2) The backbone of image
features can be pre-trained on document data making it better at capturing
document image features. (3) Similar to the layoutLM which has a reasonable
pre-training task to improve the merge of different modalities, our model can
be pre-trained with image reconstruction tasks as well, such as MAE. (4) Our
model doesn’t behave well on grouping tables and figures. Future research is
needed to expand its generality on these important document layout components.

## Acknowledgments

We would like to acknowledge Xinxing Pan, Weihao Li, Binbin Yang, Hailong
Zhang for their helpful suggestions.

## References

  * [1] Yiheng Xu, Minghao Li, Lei Cui, Shaohan Huang, Furu Wei, and Ming Zhou.  Layoutlm: Pre-training of text and layout for document image understanding.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1192–1200, 2020.
  * [2] Yang Xu, Yiheng Xu, Tengchao Lv, Lei Cui, Furu Wei, Guoxin Wang, Yijuan Lu, Dinei A. F. Florêncio, Cha Zhang, Wanxiang Che, Min Zhang, and Lidong Zhou.  Layoutlmv2: Multi-modal pre-training for visually-rich document understanding.  ArXiv, abs/2012.14740, 2020.
  * [3] Yupan Huang, Tengchao Lv, Lei Cui, Yutong Lu, and Furu Wei.  Layoutlmv3: Pre-training for document ai with unified text and image masking.  arXiv preprint arXiv:2204.08387, 2022.
  * [4] Teakgyu Hong, Donghyun Kim, Mingi Ji, Wonseok Hwang, Daehyun Nam, and Sungrae Park.  Bros: A layout-aware pre-trained language model for understanding documents.  ArXiv, abs/2108.04539, 2021.
  * [5] Shaoqing Ren, Kaiming He, Ross B. Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39:1137–1149, 2015.
  * [6] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [7] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon.  Dynamic graph cnn for learning on point clouds.  Acm Transactions On Graphics (tog), 38(5):1–12, 2019.
  * [8] Ji Zhang, Mohamed Elhoseiny, Scott Cohen, Walter Chang, and Ahmed Elgammal.  Relationship proposal networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5678–5686, 2017.
  * [9] Xiaojing Liu, Feiyu Gao, Qiong Zhang, and Huasha Zhao.  Graph convolution for multimodal information extraction from visually rich documents.  arXiv preprint arXiv:1903.11279, 2019.
  * [10] Manuel Carbonell, Pau Riba, Mauricio Villegas, Alicia Fornés, and Josep Lladós.  Named entity recognition and relation extraction with graph neural networks in semi structured documents.  In 2020 25th International Conference on Pattern Recognition (ICPR), pages 9622–9627, 2021.
  * [11] Chen-Yu Lee, Chun-Liang Li, Chu Wang, Renshen Wang, Yasuhisa Fujii, Siyang Qin, Ashok Popat, and Tomas Pfister.  Rope: reading order equivariant positional encoding for graph-based document information extraction.  arXiv preprint arXiv:2106.10786, 2021.
  * [12] Siwen Luo, Yihao Ding, Siqu Long, Josiah Poon, and Soyeon Caren Han.  Doc-GCN: Heterogeneous graph convolutional networks for document layout analysis.  In Proceedings of the 29th International Conference on Computational Linguistics, pages 2906–2916, Gyeongju, Republic of Korea, October 2022. International Committee on Computational Linguistics.
  * [13] Andrea Gemelli, Sanket Biswas, Enrico Civitelli, Josep Lladós, and Simone Marinai.  Doc2graph: a task agnostic document understanding framework based on graph neural networks.  arXiv preprint arXiv:2208.11168, 2022.
  * [14] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 580–587, 2014.
  * [15] Junlong Li, Yiheng Xu, Tengchao Lv, Lei Cui, Chaoxi Zhang, and Furu Wei.  Dit: Self-supervised pre-training for document image transformer.  Proceedings of the 30th ACM International Conference on Multimedia, 2022.
  * [16] Jiuxiang Gu, Jason Kuen, Vlad I. Morariu, Handong Zhao, Nikolaos Barmpalios, R. Jain, Ani Nenkova, and Tong Sun.  Unidoc: Unified pretraining framework for document understanding.  In Neural Information Processing Systems, 2021.
  * [17] Johannes Michael, Max Weidemann, Bastian Laasch, and Roger Labahn.  Icpr 2020 competition on text block segmentation on a newseye dataset.  In ICPR Workshops, 2020.
  * [18] Renshen Wang, Yasuhisa Fujii, and Ashok Popat.  Post-ocr paragraph recognition by graph convolutional networks.  2022 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pages 2533–2542, 2021.
  * [19] Thomas Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  ArXiv, abs/1609.02907, 2016.
  * [20] Shuang Liu, Renshen Wang, Michalis Raptis, and Yasuhisa Fujii.  Unified line and paragraph detection by graph convolutional networks.  In DAS, 2022.
  * [21] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [22] David G Kirkpatrick and John D Radke.  A framework for computational morphology.  In Machine Intelligence and Pattern Recognition, volume 2, pages 217–248. Elsevier, 1985.
  * [23] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  Advances in neural information processing systems, 30, 2017.
  * [24] Shi-Xue Zhang, Xiaobin Zhu, Jie-Bo Hou, Chang Liu, Chun Yang, Hongfa Wang, and Xu-Cheng Yin.  Deep relational reasoning graph network for arbitrary shape text detection.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9696–9705, 2020.
  * [25] Yiren Li, Zheng Huang, Junchi Yan, Yi Zhou, Fan Ye, and Xianhui Liu.  Gfte: Graph-based financial table extraction.  In ICPR Workshops, 2020.
  * [26] Wenyuan Xue, Qingyong Li, and Dacheng Tao.  Res2tim: Reconstruct syntactic structures from table images.  In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 749–755, 2019.
  * [27] Zewen Chi, Heyan Huang, Heng-Da Xu, Houjin Yu, Wanxuan Yin, and Xian-Ling Mao.  Complicated table structure recognition.  ArXiv, abs/1908.04729, 2019.
  * [28] Shah Rukh Qasim, Hassan Mahmood, and Faisal Shafait.  Rethinking table recognition using graph neural networks.  2019 International Conference on Document Analysis and Recognition (ICDAR), pages 142–147, 2019.
  * [29] Sachin Raja, Ajoy Mondal, and C. V. Jawahar.  Table structure recognition using top-down and bottom-up cues.  ArXiv, abs/2010.04565, 2020.
  * [30] Wenyuan Xue, Baosheng Yu, Wen Wang, Dacheng Tao, and Qingyong Li.  Tgrnet: A table graph reconstruction network for table structure recognition.  In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 1275–1284, 2021.
  * [31] Pau Riba, Anjan Dutta, Lutz Goldmann, Alicia Fornés, Oriol Ramos Terrades, and Josep Lladós.  Table detection in invoice documents by graph neural networks.  2019 International Conference on Document Analysis and Recognition (ICDAR), pages 122–127, 2019.
  * [32] Shah Rukh Qasim, Jan Kieseler, Yutaro Iiyama, and Maurizio Pierini.  Learning representations of irregular particle-detector geometry with distance-weighted graph networks.  The European Physical Journal C, 79:1–11, 2019.
  * [33] Guillaume Jaume, Hazim Kemal Ekenel, and Jean-Philippe Thiran.  Funsd: A dataset for form understanding in noisy scanned documents.  In 2019 International Conference on Document Analysis and Recognition Workshops (ICDARW), volume 2, pages 1–6. IEEE, 2019.
  * [34] Brian L. Davis, B. Morse, Brian L. Price, Chris Tensmeyer, and Curtis Wigington.  Visual fudge: Form understanding via dynamic graph editing.  In ICDAR, 2021.
  * [35] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  ArXiv, abs/1810.04805, 2019.
  * [36] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  ArXiv, abs/1907.11692, 2019.
  * [37] Xu Zhong, Jianbin Tang, and Antonio Jimeno-Yepes.  Publaynet: Largest dataset ever for document layout analysis.  2019 International Conference on Document Analysis and Recognition (ICDAR), pages 1015–1022, 2019.
  * [38] Birgit Pfitzmann, Christoph Auer, Michele Dolfi, Ahmed Samy Nassar, and Peter W. J. Staar.  Doclaynet: A large human-annotated dataset for document-layout analysis.  ArXiv, abs/2206.01062, 2022.
  * [39] PyG Team.  Pytorch geometric.  https://pytorch-geometric.readthedocs.io/en/latest/, December 2022\.

##  6 Appendix

###  6.1 Graph Sampling Comparison

(a)  $\beta$-skeleton;left: $\beta$=1.0;middle: $\beta$=0.9;right:
$\beta$=0.8. Decreasing $\beta$ can trade sparsity with connectivity, but a
dense graph will make information propagation less effective.

(b) KNN;left: $knn$=5;middle: $knn$=10;right: $knn$=20;Increasing $knn$ can
mitigate connectivity missing, but make sampled graph much denser.

(c) ours

Figure 5: graph sampling results of KNN, $\beta$-skeleton and our strategy

As shown in Fig 5, green lines represent valid pairs connected by algorithms,
red represents missing pairs that should be connected.The sampled results of
KNN and $\beta$-skeleton are very sensitive to different parameters. For (a):
when $\beta$=1, sampled graph miss many pairs, $\beta$=0.8 return enough
pairs, but more negative pairs are introduced. Our sampling strategy can reach
a balance between sparsity and connectivity.

(a) finaly layout analysis output

(b) connect all paired edges

(c) connect all unpaired edges

Figure 6: Result on Publaynet: a) rectangle color red, green, yellow, black means Text, Title, Table, and List;black line means edge between two nodes;b) edge predicted to be connected;c) edge predicted to be unconnected. mAP | Text | Title | List | Table | Figure | Total | Size
---|---|---|---|---|---|---|---
Faster-RCNN[37] | 0.910 | 0.826 | 0.883 | 0.954 | 0.937 | 0.902 | -
Mask-RCNN[37] | 0.916 | 0.84 | 0.886 | 0.96 | 0.949 | 0.91 | 168M
Faster-RCNN[UDoc][16] | 0.939 | 0.885 | 0.937 | 0.973 | 0.964 | 0.939 | -
Mask-RCNN[DiT-base][15] | 0.934 | 0.871 | 0.929 | 0.973 | 0.967 | 0.935 | 432M
Cascade-RCNN[DiT-base][15] | 0.944 | 0.889 | 0.948 | 0.976 | 0.969 | 0.945 | 538M
Cascade-RCNN[layoutlm-v3][3] | 0.945 | 0.906 | 0.955 | 0.979 | 0.970 | 0.951 | 538M
Faster-RCNN-Q[18] | 0.914 |  |  |  |  |  | -
Post-OCR[18] | 0.892 |  |  |  |  |  | -
ours-Small | 0.954 | 0.913 | 0.805 | 0.932 | 0.777 | 0.876 | 77M
Table 11: performance on Publaynet on all categories.

mAP | Mask-RCNN-res50[38] | Mask-RCNN-resnext101[38] | Faster-RCNN-resnext101[38] | YOLO-v5x6[38] | ours-Small
---|---|---|---|---|---
Page-Header | 0.719 | 0.7 | 0.720 | 0.679 | 0.796
Caption | 0.684 | 0.715 | 0.701 | 0.777 | 0.809
Formula | 0.601 | 0.634 | 0.635 | 0.662 | 0.726
Page-Footer | 0.616 | 0.593 | 0.589 | 0.611 | 0.920
Section-Header | 0.676 | 0.693 | 0.684 | 0.746 | 0.824
Footnote | 0.709 | 0.718 | 0.737 | 0.772 | 0.625
Title | 0.767 | 0.804 | 0.799 | 0.827 | 0.643
Text | 0.846 | 0.858 | 0.854 | 0.881 | 0.827
List-Item | 0.812 | 0.808 | 0.810 | 0.862 | 0.805
Picture | 0.717 | 0.727 | 0.720 | 0.771 | 0.581
Table | 0.822 | 0.829 | 0.822 | 0.863 | 0.559
Total-paragraph | 0.702 | 0.7143 | 0.7148 | 0.744 | 0.771
Total | 0.724 | 0.735 | 0.734 | 0.768 | 0.738
Params | - | - | 60M | 140.7M | 19.95M

Table 12: performance on Doclaynet on all categories.