# A Comparison of Two- and Three-dimensional Neutrino-hydrodynamics
simulations of Core-collapse Supernovae

Tomoya Takiwaki11affiliationmark:  , Kei Kotake22affiliationmark:
11affiliationmark:  , and Yudai Suwa33affiliationmark:  11affiliationmark:
Center for Computational Astrophysics, National Astronomical Observatory of
Japan, 2-21-1, Osawa, Mitaka, Tokyo, 181-8588, Japan  22affiliationmark:
Department of Applied Physics, Fukuoka University, Fukuoka 814-0180, Japan
3Yukawa Institute for Theoretical Physics, Kyoto University, Oiwake-cho,
Kitashirakawa, Sakyo-ku, Kyoto, 606-8502, Japan

###### Abstract

We present numerical results on two- (2D) and three-dimensional (3D)
hydrodynamic core-collapse simulations of an 11.2$M_{\odot}$ star. By changing
numerical resolutions and seed perturbations systematically, we study how the
postbounce dynamics is different in 2D and 3D. The calculations were performed
with an energy-dependent treatment of the neutrino transport based on the
isotropic diffusion source approximation scheme, which we have updated to
achieve a very high computational efficiency. All the computed models in this
work including nine 3D models and fifteen 2D models exhibit the revival of the
stalled bounce shock, leading to the possibility of explosion. All of them are
driven by the neutrino-heating mechanism, which is fostered by neutrino-driven
convection and the standing-accretion-shock instability (SASI). Reflecting the
stochastic nature of multi-dimensional (multi-D) neutrino-driven explosions,
the blast morphology changes from models to models. However, we find that the
final fate of the multi-D models whether an explosion is obtained or not, is
little affected by the explosion stochasticity. In agreement with some
previous studies, higher numerical resolutions lead to slower onset of the
shock revival in both 3D and 2D. Based on the self-consistent supernova models
leading to the possibility of explosions, our results systematically show that
the revived shock expands more energetically in 2D than in 3D.

###### Subject headings:

supernovae: general — neutrinos — hydrodynamics

††slugcomment: for ApJ

##  1\. Introduction

Ever since the first numerical simulation of core-collapse supernovae (CCSNe)
(Colgate & White, 1966), the neutrino-driven mechanism has been the leading
candidate of the explosion mechanism for more than four decades. In the long
history, a very important lesson we have learned from Rampp & Janka (2000);
Liebendörfer et al. (2001); Thompson et al. (2003); Sumiyoshi et al. (2005)
near the Millennium, is that the spherically-symmetric (1D) form of this
mechanism fails to explode canonical massive stars. Supported by accumulating
supernova observations of the blast morphology (e.g., Wang & Wheeler (2008),
and references therein), a number of multi-dimensional (multi-D) hydrodynamic
simulations have been reported so far, which gives us a confidence that
hydrodynamic motions associated with neutrino-driven convection (e.g., Herant
et al. (1994); Burrows et al. (1995); Janka & Müller (1996); Fryer et al.
(2002) and see collective references in Burrows et al. (2012); Murphy et al.
(2013); Couch (2013)) and the SASI (e.g., Blondin et al. (2003); Scheck et al.
(2004); Scheck et al. (2006); Ohnishi et al. (2006, 2007); Ott et al. (2008);
Murphy & Burrows (2008); Foglizzo et al. (2006, 2007, 2012); Iwakami et al.
(2008, 2009, 2013); Endeve et al. (2010, 2012); Fernández & Thompson (2009a,
b); Fernández (2010); Hanke et al. (2012)) can help the onset of neutrino-
driven explosions.

In fact, a growing number of neutrino-driven explosions have been recently
obtained in the state-of-the-art two-dimensional (2D) simulations, in which
spectral neutrino transport is solved with different levels of sophistication
(e.g., Buras et al. (2006); Marek & Janka (2009); Müller et al. (2012, 2013);
Bruenn et al. (2013); Suwa et al. (2010, 2011, 2013), Janka (2012) for a
review). This success is, however, accompanying new questions. Among
them111Note that general relativity (GR, e.g., Müller et al. (2012); Kuroda et
al. (2012); Ott et al. (2013)) and detailed weak interactions (e.g., Langanke
et al. (2008); Furusawa et al. (2013)) are considered as important as 3D
effects., three-dimensional (3D) effects on the neutrino-driven mechanism are
attracting a paramount attention (e.g., Burrows (2013); Kotake et al. (2012)
for a review). Unfortunately, however, experimental 3D models that employed a
light-bulb scheme (e.g., Murphy & Burrows (2008)), have provided divergent
results so far. The basic result of Nordhaus et al. (2010) who were the first
to point out that 3D leads to easier explosions than 2D, has been supported by
the follow-up studies (Burrows et al., 2012; Dolence et al., 2013), but not by
Hanke et al. (2012); Couch (2013). On top of the urgent task to make a
detailed comparison between these idealized models, self-consistent 3D
simulations should be done in order to have the final word on the 3D effects.

At present, 3D CCSN simulations including spectral neutrino transport are only
few (Hanke et al., 2013; Takiwaki et al., 2012). Very recently, Hanke et al.
(2013) succeeded in performing 3D simulations with detailed neutrino transport
for a 27 $M_{\sun}$ star. In addition to the first discovery regarding the
violent SASI activity in self-consistent 3D models, their results illuminate
the importance to go beyond the prevalent light-bulb scheme, only by doing so,
the non-linear couplings such as between core-contraction of the proto-neutron
star (PNS), the accretion neutrino luminosity, and the multi-D hydrodynamic
feedback of neutrino-driven convection and the SASI, can be self-consistently
determined. On the other hand, the very high computational cost allowed Hanke
et al. (2013) to focus on a single (self-consistent) 3D model, and it has not
been clarified yet whether 3D helps or harms the onset of neutrino-driven
explosions compared to 2D.

To address this question, we investigate in this paper how the explosion
dynamics will differ from 3D to 2D by systematically changing numerical
resolutions and initial seed perturbations in multi-D radiation-hydrodynamic
simulations. For the multi-group neutrino transport, the isotropic diffusion
source approximation (IDSA) scheme (Liebendörfer et al., 2009) is implemented
in a ray-by-ray manner (e.g., Takiwaki et al. (2012) for more details), which
we have updated to achieve a very high computational efficiency. As in
Takiwaki et al. (2012), we here focus on the evolution of an $11.2M_{\odot}$
star of Woosley et al. (2002). We choose this lighter progenitor because the
shock revival occurs relatively earlier after bounce (e.g., Buras et al.
(2006)) compared to more massive progenitor models as employed in Hanke et al.
(2013). The updated transport scheme together with the employed earlier-to-
explode progenitor allow us to conduct a systematic numerical study, for the
first time, in both 2D and 3D (to the best of our knowledge) in the context of
self-consistent neutrino-driven supernova models.

Figure 1.— Three dimensional plots of entropy per baryon (top panel),
$\tau_{\rm res}/\tau_{\rm heat}$ (bottom left panel) that is the ratio of the
residency to the neutrino heating timescale (see the text for details), and
the net neutrino heating rate (bottom right panel, in unit of ${\rm
erg}~{}{\rm cm}^{-3}~{}{\rm s}^{-1}$) for three snapshots (top and bottom
left: $t=230$ ms, and bottom right: $t=150$ ms measured after bounce ($t\equiv
0$) of our model 3D-H-1). The contours on the cross sections in the $x=0$
(back right), $y=0$ (back bottom), and $z=0$ (back left) planes are,
respectively, projected on the sidewalls of the graphs. For each snapshot, the
length of white line is indicated at right bottom text.

Figure 2.— Same as the top panel in Figure 1 but for models 3D-H-2 (left
panel) and 3D-H-2 (middle panel), which produces stronger explosions closely
toward the north (left panel) and south pole (middle panel), respectively.
Right panel shows the evolution of average shock radii for the high-resolution
2D (green lines) and 3D (red lines) models explored in this study (e.g., Table
1).

##  2\. Numerical Methods and Models

Here we briefly summarize several major updates of the code that we have
implemented after our previous work (Takiwaki et al., 2012) in which the
spectral neutrino transport scheme IDSA (Liebendörfer et al., 2009) was
implemented in the ZEUS-MP code (Hayes et al., 2006).

In the original IDSA scheme, a steady-state approximation ($\partial{f^{\rm
s}}/(\partial t)=0$) is assumed. Here $f^{\rm s}$ represents the streaming
part of the neutrino distribution function (e.g., Liebendörfer et al. (2009)).
Then one should deal with a Poisson-type equation to find the solution of
$f^{s}$ (e.g., Eq.(10) in Liebendörfer et al. (2009)). This is computationally
expensive, because a collective data-communication is required on the MPI
routines for all the processors (along the given radial direction in the ray-
by-ray approximation) to solve the Cauchy problem.

To get around the problem, one needs to solve the evolution of $f^{\rm s}$ as,

$\displaystyle\frac{\partial\mathcal{E}^{\rm s}}{c\partial{t}}$
$\displaystyle+$ $\displaystyle\frac{1}{r^{2}}\frac{\partial}{\partial
r}r^{2}\mathcal{F}^{\rm s}=\mathcal{S}[{j},{\chi},{\Sigma}],$ (1)
$\displaystyle\mathcal{E}^{\rm s}$ $\displaystyle\equiv$
$\displaystyle\frac{1}{2}\int d{\mu}\,{f}^{{\rm s}},$ (2)
$\displaystyle\mathcal{F}^{\rm s}$ $\displaystyle\equiv$
$\displaystyle\frac{1}{2}\int\mu d{\mu}\,{f}^{{\rm s}},$ (3)
$\displaystyle\mathcal{S}$ $\displaystyle\equiv$
$\displaystyle-\left(\hat{j}+\hat{\chi}\right)\mathcal{E}^{\rm s}+\Sigma,$ (4)

where $\mathcal{E}^{\rm s}$ and $\mathcal{F}^{\rm s}$ corresponds to the
radiation energy and flux of the streaming particle, and $\mathcal{S}$
represents the source term that is a functional of the neutrino emissivity
($j$), absorptivity ($\chi$), and the isotropic diffusion term ($\Sigma$) all
defined in the laboratory frame, respectively. From local hydrodynamic
quantities (density, $Y_{e}$, entropy), the source term of Eq.(1)
($\mathcal{S}[{j},{\chi},{\Sigma}]$) can be determined. For closure, we use a
prescribed relation between the radiation energy and flux as
($\mathcal{F}^{\rm s}/\mathcal{E}^{\rm
s}=\frac{1}{2}(1+\sqrt{1-[{R_{\nu}}/\max\left(r,R_{\nu}\right)]^{2}})$ with
$R_{\nu}$ being the radius of an energy-dependent scattering sphere (see
Eq.(11) in Liebendörfer et al. (2009)). Since the cell-centered value of the
flux, $\mathcal{F}^{\rm s}$, is obtained by the prescribed relation, the cell-
interface value is estimated by the first-order upwind scheme assuming that
the flux is out-going along the radial direction. With the numerical flux, the
transport equation of $\mathcal{E}^{\rm s}$ (Eq.(1)) now expressed in a
hyperbolic form is numerically solved. This modification does not produce any
significant changes in the numerical results (see Takiwaki et al. in
preparation for more details), however, the computational cost becomes more
than 10 times smaller than that in the previous treatment. The velocity
dependent terms ($O(v/c)$) are only included (up to the leading order) in the
trapped part of the distribution function (Eq. (15) in Liebendörfer et al.
(2009)). Concerning heavy-lepton neutrinos
($\nu_{x}=\nu_{\mu},\nu_{\tau},\bar{\nu}_{\mu},\bar{\nu}_{\tau}$), we employ a
leakage scheme to include the $\nu_{x}$ cooling via pair-, photo, plasma
processes (e.g., Rosswog & Liebendörfer (2003); Itoh et al. (1989)). We apply
the so-called ray-by-ray approach in which the neutrino transport is solved
along a given radial direction assuming that the hydrodynamic medium for the
direction is spherically symmetric. To improve the accuracy of total energy
conservation, we follow the prescription proposed by Müller et al. (2010). For
the calculations presented here, self-gravity is computed by a Newtonian
monopole approximation. We use the equation of state (EOS) by Lattimer &
Swesty (1991) with a compressibility modulus of $K=180$ MeV (LS180).

Our fiducial 3D models are computed on a spherical polar grid with a
resolution of $n_{r}\times n_{\theta}\times n_{\phi}$ = $320\times 64\times
128$, in which non-equally spacial radial zones covers from the center to an
outer boundary of 5000 km. The radial grid is chosen such that the resolution
$\Delta r$ is better than 2km in the PNS interior and typically better than
5km outside the PNS. For the spectral transport, we use 20 logarithmically
spaced energy bins ranging from 3 to 300 MeV and we take a ray-by-ray
approximation (e.g., Buras et al. (2006); Bruenn et al. (2013)), in which a
ray is cast for every angular zone. In all the multi-D runs, the innermost 5
km is computed in spherical symmetry to avoid excessive time-step limitations.
Seed perturbations for aspherical instabilities are imposed by hand at 10 ms
after bounce by introducing random perturbations of $1\%$ in velocity behind
the stalled shock.

To test the sensitivity of the supernova dynamics to numerical resolutions, we
compute 3D model-series with lower angular resolutions, namely half or quarter
of the (equidistant) mesh numbers in the azimuthal direction ($n_{r}\times
n_{\theta}\times n_{\phi}$ = $320\times 64\times 64$ and $n_{r}\times
n_{\theta}\times n_{\phi}$ = $320\times 64\times 32$). In 2D simulations we
vary the mesh numbers in the lateral direction as $n_{r}\times n_{\theta}$ =
$320\times 64$, $n_{r}\times n_{\theta}$ = $320\times 128$ and $n_{r}\times
n_{\theta}$ = $320\times 256$, respectively (see Table 1). In the table, model
3D-H-1 differs from model 3D-H-2 (and 3D-H-3 etc) only in the random seed
perturbations (with the perturbation amplitudes being the same in all cases).
Note that the lowest-resolution 3D model in this work corresponds to the best-
resolution model in Takiwaki et al. (2012). By using the fastest K computer in
Japan, it took typically 1.3 months (equivalently $\sim$ 4 million core-hour
computing-time) for each of our 3D fiducial models.

Table 1Model Summary

Model | $n_{r}\times n_{\theta}\times n_{\phi}$ | Angular | $t_{400}$ | $t_{400,{\rm av}}$ | $\sigma[t_{400}]$ | $t_{\rm end}$ | $R_{\rm max}$ | $E_{\rm diag}$ | $(l,m)_{\mathrm{max}}$ | $|c_{l,m}|_{\mathrm{max}}$
---|---|---|---|---|---|---|---|---|---|---
|  | resolution [∘] | [ms] | [ms] | [ms] | [ms] | [km] | [$10^{50}$ erg] |  |
3D-H-1 | $320\times 64\times 128$ | $2.8^{\circ}\times 2.8^{\circ}$ | 223 | 236 | 24 | 284 | 550 | 0.15 | 1,0 | 0.02
3D-H-2 | $320\times 64\times 128$ | $2.8^{\circ}\times 2.8^{\circ}$ | 216 | 369 | 850 | 0.25 | 2,0 | 0.02
3D-H-3 | $320\times 64\times 128$ | $2.8^{\circ}\times 2.8^{\circ}$ | 269 | 269 | 400 | 0.15 | 2,0 | 0.02
3D-M-1 | $320\times 64\times 64$ | $2.8^{\circ}\times 5.6^{\circ}$ | 192 | 194 | 1.2 | 269 | 600 | 0.25 | 1,0 | 0.01
3D-M-2 | $320\times 64\times 64$ | $2.8^{\circ}\times 5.6^{\circ}$ | 194 | 319 | 700 | 0.30 | 1,0 | 0.02
3D-M-3 | $320\times 64\times 64$ | $2.8^{\circ}\times 5.6^{\circ}$ | 195 | 279 | 700 | 0.27 | 1,0 | 0.01
3D-L-1 | $320\times 64\times 32$ | $2.8^{\circ}\times 11.3^{\circ}$ | 193 | 188 | 4 | 314 | 1000 | 0.60 | 2,1 | 0.009
3D-L-2 | $320\times 64\times 32$ | $2.8^{\circ}\times 11.3^{\circ}$ | 188 | 273 | 800 | 0.45 | 2,1 | 0.009
3D-L-3 | $320\times 64\times 32$ | $2.8^{\circ}\times 11.3^{\circ}$ | 183 | 273 | 700 | 0.35 | 2,1 | 0.01
2D-H-1 | $320\times 256$ | $0.7^{\circ}$ | 138 | 151 | 7 | 300 | 1100 | 0.65 | 1,0 | 0.05
2D-H-2 | $320\times 256$ | $0.7^{\circ}$ | 154 | 329 | 1200 | 0.45 | 2,0 | 0.08
2D-H-3 | $320\times 256$ | $0.7^{\circ}$ | 159 | 311 | 1200 | 0.76 | 2,0 | 0.1
2D-H-4 | $320\times 256$ | $0.7^{\circ}$ | 156 | 368 | 1500 | 0.6 | 2,0 | 0.05
2D-H-5 | $320\times 256$ | $0.7^{\circ}$ | 150 | 345 | 1200 | 0.7 | 2,0 | 0.1
2D-M-1 | $320\times 128$ | $1.4^{\circ}$ | 140 | 142 | 10 | 369 | 1700 | 0.5 | 1,0 | 0.1
2D-M-2 | $320\times 128$ | $1.4^{\circ}$ | 125 | 319 | 1800 | 0.8 | 2,0 | 0.06
2D-M-3 | $320\times 128$ | $1.4^{\circ}$ | 151 | 400 | 1700 | 0.85 | 1,0 | 0.1
2D-M-4 | $320\times 128$ | $1.4^{\circ}$ | 144 | 469 | 2300 | 1.0 | 1,0 | 0.1
2D-M-5 | $320\times 128$ | $1.4^{\circ}$ | 152 | 400 | 1800 | 1.0 | 2,0 | 0.05
2D-L-1 | $320\times 64$ | $2.8^{\circ}$ | 137 | 133 | 6 | 387 | 2100 | 1.1 | 2,0 | 0.08
2D-L-2 | $320\times 64$ | $2.8^{\circ}$ | 137 | 395 | 2200 | 1.26 | 2,0 | 0.1
2D-L-3 | $320\times 64$ | $2.8^{\circ}$ | 126 | 483 | 2800 | 1.3 | 1,0 | 0.09
2D-L-4 | $320\times 64$ | $2.8^{\circ}$ | 140 | 559 | 2400 | 1.3 | 1,0 | 0.09
2D-L-5 | $320\times 64$ | $2.8^{\circ}$ | 125 | 569 | 2500 | 1.3 | 2,0 | 0.05

††footnotetext: Note that “H”, “M”, or “L” appended to our models stands for
high, moderate, low azimuthal angular resolutions, respectively. The third
number (-$i$) of each model that runs from 1 to 3 for 3D models and from 1 to
5 for 2D models represents the difference only in the random seed
perturbations (with the perturbation amplitudes being the same in all cases).
$t_{400}$ represents the time when the average shock radius touches a radius
of 400 km, and $t_{400,{\rm av}}$ and $\sigma[t_{400}]$ denotes the model
average and the dispersion of $t_{400}$. $t_{\mathrm{end}}$ denotes the time
of the end of the simulation. $R_{\mathrm{max}}$ and $E_{\mathrm{diag}}$ are
the averaged shock radius and the diagnostic explosion energy at $t_{\rm
end}$. $(\ell,m)_{\rm max}$ denotes the set of spherical harmonics mode when
the normalized amplitude takes the maximum value ($|c_{\ell,m}|_{\rm max}$)
during the linear SASI phase.

##  3\. Result

As summarized in Table 1, all the computed models including nine 3D models and
fifteen 2D models exhibit shock revival, leading to the possibility of
explosion. Before going into detail how the explosion dynamics and
stochasticity are different in 2D and 3D, we briefly outline the hydrodynamics
features taking model 3D-H-1 as an example.

The top panel of Figure 1 shows the blast morphology of model 3D-H-1 at
$t_{\rm pb}=230$ ms (postbounce) when the revived shock is reaching an angle-
averaged radius of 400 km (e.g., red dashed line in the right panel of Figure.
2). As seen from the side wall panels, a bipolar explosion is obtained for
this model. The bottom left panel (red regions) shows that the ratio of the
residency timescale to the neutrino heating timescale (e.g., Equations (6) and
(7) in Takiwaki et al. (2012)) exceeds unity behind the shock, which presents
evidence that the shock revival is driven by the neutrino-heating mechanism.
The bottom right panel of Figure 1 depicts spacial distribution of the net
neutrino heating rate at $t_{\rm pb}=150$ ms. Small scale inhomogeneities
(colored as red or yellow) are seen, which predominantly comes from neutrino-
driven convection and anisotropies of the accretion flow, but the shape of the
gain region is very close to be spherical before the onset of an explosion.
This suggests that the bipolar geometry of the shock is produced not by the
global anisotropy of the neutrino heating in the vicinity of the neutrino
sphere, but by multi-D effects such as by neutrino-driven convection and the
SASI in the gain regions after the explosion (gradually) sets in.

Reflecting the stochastic nature of the multi-D neutrino-driven explosions,
the blast morphology changes from models to models. The left and middle panels
of Figure 2 show that a stronger explosion is obtained toward the north
direction (model 3D-H-2) and the south pole (model 3D-H-3), which is only
different from model 3D-H-1 (e.g., Table 1) in terms of the imposed initial
random perturbations. Note that due to the use of the spherical coordinates,
we cannot omit the possibility that the polar axis still gives a special
direction in our 3D simulations. But more importantly, our results show that
the final fate of the 3D and 2D models whether an explosion is obtained or
not, is little affected by the stochasticity of the explosion geometry.

In fact, the right panel of Figure 2 shows the evolution of the average shock
radius for our 1D (blue line), 2D (green lines), and 3D (red lines) models,
respectively. Before the onset of shock revival (before 100 ms after bounce),
the evolution of the shock is all similar to that of the 1D model (blue line).
After that, our results show that the shock expansion is systematically more
energetic in 2D (green lines) than in 3D (red lines). This feature is
qualitatively consistent with Takiwaki et al. (2012), and also with Hanke et
al. (2013) who recently reported 2D vs. 3D comparison based on a single 3D
model but employing more detailed neutrino transport than ours.

Due to our lack of necessary computational resources, our 3D models should be
terminated typically before $t_{\rm end}\lesssim 300$ ms postbounce (e.g., in
Table 1), but we expect them to produce explosions subsequently, seeing a
continuous shock expansion out to a radius of 500 km in 3D (and 700 km in 2D).
Given the same numerical resolution (e.g., model series 3D-L in Table 1), the
average shock radii in this study is smaller than those in Takiwaki et al.
(2012), in which the cooling by heavy-lepton neutrinos was not taken into
account. Due to the inclusion of the $\nu_{x}$ cooling, the (angle-averaged)
$\bar{\nu}_{e}$ luminosity decreases more quickly after bounce (compare Figure
3 and Figure 14 of Takiwaki et al. (2012)), which leads to the less energetic
shock expansion in this study. It should be mentioned that by comparing our
$\nu_{x}$ luminosity estimated by the leakage scheme with that obtained by the
work by Buras et al. (2006) with detailed neutrino transport, the peak
luminosity is more than 20 % smaller in our case. Such underestimation of
cooling by heavy-lepton neutrinos should lead to artificially larger maximum
shock extent ($R_{\rm max}\sim 260$ km, blue line in the right panel of Figure
2) compared to $R_{\rm max}\sim 170$ km in Buras et al. (2006). We have to
emphasize that the use of the leakage scheme together with the omission of
inelastic neutrino scattering on electrons and GR effects in the present
scheme is likely to facilitate artificially easier explosions. Regarding our
2D models, the relatively earlier shock revival ($\sim 100$ ms postbounce)
coincides with the decline of the mass accretion rate onto the central PNS.
This could be the reason that the timescale is similar to that in Müller et
al. (2012) who reported 2D (GR) models for the same progenitor model with
detailed neutrino transport.

As seen from Figure 3, the angle average neutrino luminosity ($\langle
L_{\nu}\rangle$) and the mean neutrino energy
($\langle\epsilon_{\nu}\rangle=\int E^{3}\mathcal{F}^{\rm s}dE/\int
E^{2}\mathcal{F}^{\rm s}dE$, where $E$ is neutrino energy) is barely affected
by the imposed initial perturbations (presumably at few-percent levels in
amplitudes). This again supports our finding that the explosion stochasticity
is very influential to determine the blast morphology but not the working of
the neutrino-heating mechanism.

From the bottom panel of Figure 3, it can be seen that overall trend in the
neutrino luminosities and the mean energies is similar between our 3D and 2D
model. The neutrino luminosities in the 2D model (green lines) show a short-
time variability (with periods of milliseconds to $\gtrsim 10$ ms) after
around 100 ms postbounce. Such fast variations in the postbounce luminosity
evolution have been already found in previous 2D studies (e.g., Ott et al.
(2008); Marek et al. (2009)). This is caused by the modulation of the mass
accretion rate due to convective plumes and downflows hitting onto the PNS
surface (see also Lund et al. (2012); Tamborra et al. (2013) about the
detectability of these neutrino signals). It is interesting to note that such
fast variability is less pronounced in our 3D model (red lines in the bottom
panel). This is qualitatively consistent with Lund et al. (2012) who analyzed
the neutrino signals from 2D and 3D models, in which an approximate neutrino
transport was solved (Wongwathanarat et al., 2010) as in Scheck et al. (2006).

Figure 3.— Top panel shows time evolution of neutrino luminosities and mean
energies of electron ($\nu_{e}$), anti-electron ($\bar{\nu}_{e}$), or heavy-
lepton ($\nu_{X}$) neutrinos for models 3D-H-2 (green line) and 3D-H-3 (red
line), respectively. Bottom panel is the same as the top panel but for the
comparison between 2D and 3D (for models 3D-H-1 and 2D-H-1). These quantities
are estimated at 500 km.

Figure 4 shows evolution of the average PNS radius for the 1D (blue line), 2D
(green line), and 3D models (red line), respectively, that are defined by a
fiducial density of $10^{11}~{}{\rm g}~{}{\rm cm}^{-3}$. The PNS contraction
is similar among the 1D, 2D, and 3D models. Although the PNS contraction
potentially affect the evolution of the shock (Hanke et al., 2013; Suwa et
al., 2013), in our cases that are unchanged by the difference of the dimension
and that are not main agent to explain the divergence of the shock evolution
in 1D, 2D and 3D. The PNS contraction is slightly stronger in the later
postbounce phase in 1D ($\gtrsim 150$ ms postbounce, compare blue with green
and red lines)) compared to 2D and 3D because no shock revival was obtained in
the 1D model and heavier PNS and slightly deeper gravitational potential are
obtained compared to that of the multi-D models. In the figure, three more
lines (solid, dashed, dotted gray lines) are plotted, in which we estimate the
evolution of the PNS radius based on the fitting formula (equation (1) of
Scheck et al. (2006)) by changing a final radius of PNS $R_{\rm f}$ for a
given set of an exponential timescale of $t_{\rm ib}=1$ s and an initial
radius of PNS $R_{\rm i}=$ 85 km. As can be seen, the dashed gray line
($R_{\rm f}=12$ km) can most closely reproduce our results, which is just
between the slow and fast contraction investigated in the work by Hanke et al.
(2013).

Figure 4.— Average PNS radius (defined by a fiducial density of
$10^{11}~{}{\rm g}~{}{\rm cm}^{-3}$) for the 1D (blue line), 2D (green line),
and 3D models (red line), respectively. The gray lines labeled as ”fit”
corresponds to the prescribed PNS evolution with three different values of
$R_{\rm f}=10,12,$ and 15 km (see text for more details).

Figure 5.— Top panel shows radial profiles of angle-averaged entropy at 100 ms
postbounce for the 1D, 2D-H-1, 3D-H-1 model, respectively. Bottom panel shows
spectra of the turbulent kinetic energy as a function of wavenumber ($k$)
between our 2D (green line) and 3D (red line) model, respectively.

Top panel of Figure 5 shows angle-averaged entropy profile at 100 ms
postbounce, after when the difference of the subsequent shock evolution
between our 1D, 2D, and 3D models becomes remarkable (e.g., right panel in
Figure 2). As has been studied in detail since 1990’s (e.g., Herant et al.
(1994); Burrows et al. (1995); Janka & Müller (1996)), buoyancy-driven
convection supported by turbulence (e.g., Murphy et al. (2013)) transports
heat radially outward, leading to a more extended entropy profile in the 2D
(green line in the panel) and 3D (red line) model compared to the 1D model
(blue line) (see also Hanke et al. (2012)).

Bottom panel of Figure 5 compares the turbulent energy spectra of the
anisotropic velocity (Takiwaki et al. (2012)) as a function of wavenumber
($k$) between our 2D (green line) and 3D (red line) model, respectively. The
green and red line crosses at around $k_{\rm cross}$ = 0.02/km (corresponding
to $\sim$ 50 km in spacial scale), above which the amplitude for the 3D model
(red line) dominates over that for the 2D model (green), below which the
amplitude for the 2D model does for the 3D model. This is qualitatively
consistent with the previous results using the light-bulb method (e.g., Hanke
et al. (2012); Burrows et al. (2012); Dolence et al. (2013); Couch (2013);
Fernández et al. (2013). By comparing the 2D and 3D curve with spectral slopes
labeled by the corresponding exponent (-5/3:dotted blue line, -3:dotted black
line), the power-low dependence ($\propto k^{-5/3}$) approximately holds for
$k_{\rm int}\lesssim 0.02$ /km in the 2D model (green line) presumably as a
result of the inverse energy cascade (Kraichnan, 1967). Above $k_{\rm cross}$,
the slope of the 3D model (red line) become more closer to $k^{-5/3}$ (blue
line), while the spectrum slope of the 2D model drops much steeply with the
wave number as $k^{-3}$ (gray line). These features are again in accord with
the previous studies mentioned above (e.g., Hanke et al. (2012); Burrows et
al. (2012); Dolence et al. (2013); Couch (2013); Fernández et al. (2013)).

As shown in the middle panel of Figure 2, model 3D-H-3 produces one-sided
explosion towards the south pole during the simulation time. Reflecting the
unipolarity, the average shock radius is smaller than for the other 3D models
(compare dotted line (in red) with solid and dashed red (in red) in the right
panel of Figure 2). To quantify the vigor of the shock expansion ,
$t_{\mathrm{400}}$ is a useful quantity that was defined in Hanke et al.
(2012) as the moment of time when the shock reaches an average radius of 400
km. In fact, as seen from Table 1, $t_{\mathrm{400}}$ of model 3D-H-3
($t_{\mathrm{400}}\approx 270~{}\mathrm{ms}$) is delayed about 50 ms compared
to those of models 3D-H-1 and 3D-H-2 ($t_{\mathrm{400}}\approx
220~{}\mathrm{ms}$).

The model average of $t_{400}$ (e.g., $t_{400,{\rm av}}$ in Table 1) clearly
shows that models with higher numerical resolutions lead to slower onset of
the shock revival in both our 3D and 2D models. This feature is qualitatively
consistent with the 2D self-consistent models by Marek & Janka (2009) and with
the 3D idealized models by Hanke et al. (2013); Couch (2013), respectively.

$\sigma_{400}$ in Table 1 represents the model dispersion of $t_{400}$, which
varies much more stochastically in 3D models with different numerical
resolution (from 1.2 to 24 ms) than those in 2D (from 6 to 10 ms). For model
3D-H-3, the shock revival is most delayed (e.g., Table 1) and the shock
expansion is weakest among the computed models (dotted red line in Figure 1).
Nagakura et al. (2013) proposed that shock revival is very sensitive to the
imposed seed perturbations near the stalled shock. Following the hypothesis,
we speculate that the influence of seed perturbations is seen most remarkably
in our weakest explosion model.

$E_{\rm diag}$ in Table 1 denotes the diagnostic energy defined as the total
energy (internal plus kinetic plus gravitational), integrated over all matter
where the sum of the corresponding specific energies is positive. We include
recombination energy in internal energy(Bruenn et al. (2013)). Reflecting the
earlier shock revival, the diagnostic energy is systematically bigger in 2D
than in 3D. These diagnostic energies when we terminated the simulation were
typically on the order of $\sim 10^{49}$ erg and $\sim 10^{50}$ erg for our 3D
and 2D models, respectively. It should be noted that this quantity is
estimated at the end of simulation,$t_{\rm end}$. In order to compare the
diagnostic energy with the observed kinetic explosion energy ($\sim 10^{51}$
erg), a much longer-term simulation including improved microphysics, general
relativity, and nuclear burning would be needed.

Figure 6.— Time evolution of $\chi$ parameter (left panel) and normalized
spherical harmonic mode amplitudes of the shock for our 3D high-resolution
models with respect to each $(\ell,m)$ (right panel, e.g., $|c_{\ell
m}/c_{00}|$ in equation (10) of Takiwaki et al. (2012)). The horizontal blue
line corresponds to $\chi=3$, above which neutrino-driven convection dominates
over the SASI (Foglizzo et al., 2006). In the right panel, lower modes with
larger amplitudes are selected.

Recently it is enthusiastically discussed which one between neutrino-driven
convection and the SASI plays a more crucial role in facilitating neutrino-
driven explosions (Foglizzo et al., 2006; Dolence et al., 2013; Murphy et al.,
2013; Burrows et al., 2012; Hanke et al., 2012, 2013). The left panel of
Figure 6 shows the time evolution of the Foglizzo parameter $\chi$ (Foglizzo
et al., 2006) As seen, $\chi$ continuously exceeds the critical number of $3$
(Foglizzo et al., 2006) rather shortly after bounce ($\sim 40$ ms), marking
the transition to the non-linear phase. The earlier onset of the shock revival
and the absence of clear features of the SASI in the linear phase (see
discussion below) could indicate that neutrino-driven convection dominates
over the SASI when the explosion sets in (e.g., at $t_{400}$ in Table 1).

The right panel of Figure 6 shows the evolution of normalized coefficient of
spherical harmonics of the shock surface for model 3D-H-1. No clear feature of
the linear growth of the SASI ($\lesssim 40$ ms postbounce) was obtained for
the 11.2 $M_{\odot}$ star explored in this work. In both our 3D and 2D models,
the qualitative behaviors of the harmonic modes seen in Figure 6 are less
sensitive to the employed numerical resolution and seed random perturbations
(see appendix A). The dominant channels are of low modes (e.g., $(\ell,m)_{\rm
max}$ in Table 1), the amplitudes of which (e.g., $|c_{\ell,m}|_{\rm max}$ in
the table) are systematically larger in 2D than in 3D. This is qualitatively
consistent with previous 3D simulations employing different numerical setups
(e.g., Nordhaus et al. (2010); Hanke et al. (2012); Burrows et al. (2012);
Hanke et al. (2013)).

After the linear phase comes to an end at around 100 ms postbounce, the
trajectory of the revived shock shows a wider diversity (e.g., Figure 1)
depending on the employed numerical resolution and seed perturbations.

##  4\. Summary and Discussion

Studying an 11.2 $M_{\odot}$ and changing numerical resolutions and seed
perturbations systematically in the multi-D simulations employing the updated
IDSA scheme, we studied how the postbounce dynamics is different in 2D and 3D.
All the computed models exhibit the neutrino-driven revival of the stalled
bounce shock, leading to the possibility of an explosion. Though the blast
morphology changes from models to models reflecting the stochastic nature of
multi-D neutrino-driven explosions, it was found that the final fate of these
multi-D models whether an explosion is obtained or not, is little affected by
the explosion stochasticity at least in the current investigated progenitor
model. In line with some previous studies, higher numerical resolutions lead
to slower onset of the shock revival in both 3D and 2D. Our results
systematically showed that the revived shock expands more energetically in 2D
than in 3D.

The caveats of our 3D models include the ray-by-ray approximation, the use of
the softer EOS, and the omission of detailed neutrino reactions and general
relativity (e.g., Kuroda et al. (2012); Ott et al. (2013)). Keeping our
efforts to improve them, it is important to study the dependence of
progenitors (e.g., Buras et al. (2006); Bruenn et al. (2013)) and EOS (e.g.,
Marek & Janka (2009); Suwa et al. (2013)) on the neutrino-driven mechanism in
3D computations. A number of exciting issues also remain to be investigated,
such as gravitational-wave signatures (e.g., Kotake (2013)), neutrino emission
and its detectability (e.g., Lund et al. (2012)), and the possibility of 3D
SASI flows generating pulsar kicks and spins (e.g., Wongwathanarat et al.
(2013)). Shifting from individuals to populations of 3D models, a rush of 3D
explorations with increasing sophistication is now going to shed light on
these fascinating riddles (hopefully not in the distant future) with
increasing supercomputing resources on our side.

We are thankful to K. Sato and S. Yamada for continuing encouragements.
Numerical computations were carried on in part on the K computer at the RIKEN
Advanced Institute for Computational Science (Proposal number hp120285),
XC30/XT4 at NAOJ, and on SR16000 at YITP in Kyoto University. This study was
supported in part by Grants-in-Aid for Scientific Research (Nos. 23540323,
23340069, 24244036, and 25103511) and by HPCI Strategic Program of Japanese
MEXT.

##  Appendix A Dependence on the amplitude of seed perturbations

In this Appendix we briefly report on the dependence on the amplitudes of the
initial seed perturbations. We have added a radial velocity perturbation,
$\delta v_{r}(r,\theta,\phi)$ to the profile obtained by 1D
simulation,$v_{r}^{1D}(r)$, according to the equation $\delta v_{r}=p_{\rm
amp}{\rm rand}\times v_{r}^{1D}$ where rand is pseudorandom number that takes
the value from $-1$ to $1$ and $p_{\rm amp}$ represents the absolute amplitude
of the seed perturbations that we take as $1\%$ in the models discussed in the
main section. Let us firstly note that the amplitude of seed perturbations
$a_{\ell,m}$ assumed in this study scales as $p_{\rm amp}/N^{1/2}$, where
$a_{\ell,m}$ denotes the amplitude of the $(\ell,m)$ component of the seed
perturbations at a given radius (i.e. $a_{\ell,m}=\int d\phi\int\sin\theta
d\theta\left(v_{r}^{1D}+\delta v_{r}\right)Y_{\ell,m}^{*}$, where
$Y_{\ell,m}^{*}$ is conjugate of spherical harmonic function) and
$N=n_{\theta}\times n_{\phi}$ represents the total angular mesh number where
$n_{\theta},n_{\phi}$ being the mesh number in the $\theta$ and $\phi$
direction, respectively(e.g. in our 3D model with highest resolution,
$n_{\theta}=64,n_{\phi}=128$). Therefore the seed amplitudes assumed in this
work depend on numerical resolution (i.e., $N$).

If we keep the seed amplitudes ($a_{\ell,m}$) constant for models with
different resolutions, will our results change drastically? Since we cannot
rerun 3D models due to the limited computational resources, we compute a
number of 2D models to answer to this question. First of all, let us discuss
2D models with different seed amplitudes. Top panel of Figure 7 shows the
evolution of $c_{1,0}$ (the normalized harmonic amplitudes of shock position)
for 2D models with $p_{\rm amp}=1\%$ (red lines) or $0.176\%(=1\%/\sqrt{32})$
(green lines) with five different realizations of initial random perturbation.
The reduced amplitude is determined by the ratio of total grid number of 2D-H
models and 3D-H models (i.e.
$1/\sqrt{32}=\sqrt{n_{\theta}|_{2D-H}/(n_{\theta}n_{\phi})|_{3D-H}}$). One
might have a guess that $c_{\ell,m}(t)$ could evolve as
$a_{\ell,m}\exp(t/t_{0})$ with $t_{0}$ representing the duration of the linear
growth rate of hydrodynamic instabilities including the SASI or neutrino-
driven convection. If this could be the case, the linear growth amplitude (at
before 35 ms postbounce in the top panel) should be higher about $\sqrt{32}$
times for red lines compared to green lines. But as it is shown, this is not
the case222 Note that if the initial seed perturbations would be more bigger
than those assumed in this study, they should affect the postbounce
hydrodynamics (see Couch& Ott (2013)). And after the early rising phase (about
40 ms postbounce in the panel), the saturation amplitudes are shown to be
insensitive to the initial perturbation amplitudes (for the initial strength
employed above). Remembering that neutrino-driven convection is likely to
dominate over the SASI in the non-linear regime for the 11.2 $M_{\odot}$
progenitor employed in this work, the delay of $t_{400}$ (in the non-linear
phase) for models with higher numerical resolutions cannot be also simply
ascribed to the difference of the seed amplitudes.

Bottom panels of Figure 7 show evolution of $c_{1,0}$ for different resolution
(H, M, and L) for our 2D and 3D models, respectively. For a given numerical
resolution, $t_{400}$ of the chosen models in these plots is close to a median
of $t_{400}$ for each model series. Note that in these models the initial seed
amplitudes are dependent on both resolution and dimension. As can be seen, in
both 2D and 3D, the amplitudes in the linear phase ($<40$ms postbounce) are
comparable for models with different resolutions. And in the non-linear
regime, no monotonic dependence of the non-linear evolution on the initial
seed amplitudes (between H, M, L models) can be found. These results show that
the findings in this work are less sensitive to the assumed initial seed
perturbations.

Figure 7.— Top panel shows evolution of $c_{1,0}$ for our 2D models with
$p_{\rm amp}=1\%$ (red lines) or $0.176\%(=1\%/\sqrt{32})$ (green lines) with
5 different realizations of random perturbation (see text for more details).
Bottom panels show evolution of $c_{1,0}$ for different resolution (H, M, and
L) for our 2D and 3D models.

## References

  * Bethe & Wilson (1985) Bethe, H. A., & Wilson, J. R. 1985, ApJ, 295, 14
  * Blondin et al. (2003) Blondin, J. M., Mezzacappa, A., & DeMarino, C. 2003, Astrophys. J., 584, 971
  * Bruenn et al. (2013) Bruenn, S. W., Mezzacappa, A., Hix, W. R., et al. 2013, ApJ, 767, L6
  * Buras et al. (2006) Buras, R., Janka, H.-T., Rampp, M., & Kifonidis, K. 2006, A&A, 457, 281
  * Burrows et al. (1995) Burrows, A., Hayes, J., & Fryxell, B. A. 1995, ApJ, 450, 830
  * Burrows (2013) Burrows, A. 2013, Reviews of Modern Physics, 85, 245
  * Burrows et al. (2012) Burrows, A., Dolence, J. C., & Murphy, J. W. 2012, ApJ, 759, 5
  * Burrows et al. (1995) Burrows, A., Hayes, J., & Fryxell, B. A. 1995, ApJ, 450, 830
  * Colgate & White (1966) Colgate, S. A., & White, R. H. 1966, ApJ, 143, 626
  * Couch (2013) Couch, S. M. 2013, ApJ, 775, 35
  * Couch& Ott (2013) Couch, S. M., & Ott, C. D. 2013, ApJ, 778, L7
  * Demorest et al. (2010) Demorest, P. B., Pennucci, T., Ransom, S. M., Roberts, M. S. E., & Hessels, J. W. T. 2010, Nature, 467, 1081
  * Dolence et al. (2013) Dolence, J. C., Burrows, A., Murphy, J. W., & Nordhaus, J. 2013, ApJ, 765, 110
  * Endeve et al. (2010) Endeve, E., Cardall, C. Y., Budiardja, R. D., & Mezzacappa, A. 2010, ApJ, 713, 1219
  * Endeve et al. (2012) Endeve, E., Cardall, C. Y., Budiardja, R. D., et al. 2012, ApJ, 751, 26
  * Fernández & Thompson (2009a) Fernández, R. & Thompson, C. 2009a, ApJ, 703, 1464
  * Fernández & Thompson (2009b) —. 2009b, ApJ, 697, 1827
  * Fernández (2010) Fernández, R. 2010, ApJ, 725, 1563
  * Fernández et al. (2013) Fernández, R., Mueller, B., Foglizzo, T., & Janka, H.-T. 2013, arXiv:1310.0469
  * Foglizzo et al. (2006) Foglizzo, T., Scheck, L. & Janka, H.-Th., 2006, ApJ, 652, 1436
  * Foglizzo et al. (2007) Foglizzo, T., Galletti, P., Scheck, L., & Janka, H.-T. 2007, ApJ, 654, 1006
  * Foglizzo et al. (2012) Foglizzo, T., Masset, F., Guilet, J., & Durand, G. 2012, Physical Review Letters, 108, 051103
  * Furusawa et al. (2013) Furusawa, S., Nagakura, H., Sumiyoshi, K., & Yamada, S. 2013, ApJ, 774, 78
  * Fryer et al. (2002) Fryer, C. L., Holz, D. E., & Hughes, S. A. 2002, Astrophys. J., 565, 430
  * Hanke et al. (2012) Hanke, F., Marek, A., Müller, B., & Janka, H.-T. 2012, ApJ, 755, 138
  * Hanke et al. (2013) Hanke, F., Müller, B., Wongwathanarat, A., Marek, A., & Janka, H.-T. 2013, ApJ, 770, 66
  * Hayes et al. (2006) Hayes, J. C., Norman, M. L., Fiedler, R. A., Bordner, J. O., Li, P. S., Clark, S. E., ud-Doula, A., & Mac Low, M. 2006, ApJS, 165, 188
  * Herant et al. (1994) Herant, M., Benz, W., Hix, W. R., Fryer, C. L., & Colgate, S. A. 1994, ApJ, 435, 339
  * Itoh et al. (1989) Itoh, N., Adachi, T., Nakagawa, M., Kohyama, Y., & Munakata, H. 1989, Astrophys. J., 339, 354
  * Iwakami et al. (2008) Iwakami, W., Kotake, K., Ohnishi, N., Yamada, S., & Sawada, K. 2008, Astrophys. J., 678, 1207
  * Iwakami et al. (2009) —. 2009, Astrophys. J., 700, 232
  * Iwakami et al. (2013) Iwakami, W., Nagakura, H., & Yamada, S. 2013, arXiv:1308.0829
  * Janka & Müller (1996) Janka, H., & Müller, E. 1996, A&A, 306, 167
  * Janka (2012) Janka, H.-T. 2012, Annual Review of Nuclear and Particle Science, 62, 407
  * Herant et al. (1994) Herant, M., Benz, W., Hix, W. R., Fryer, C. L., & Colgate, S. A. 1994, ApJ, 435, 339
  * Kotake (2013) Kotake, K. 2013, Comptes Rendus Physique, 14, 318
  * Kotake et al. (2012) Kotake, K., Takiwaki, T., Suwa, Y., et al. 2012, Advances in Astronomy, 2012
  * Kuroda et al. (2012) Kuroda, T., Kotake, K., & Takiwaki, T. 2012, ApJ, 755, 11
  * Kraichnan (1967) Kraichnan, R. H. 1967, Physics of Fluids, 10, 1417
  * Langanke et al. (2008) Langanke, K., Martínez-Pinedo, G., Müller, B., et al. 2008, Physical Review Letters, 100, 011101
  * Lattimer & Swesty (1991) Lattimer, J. M., & Swesty, F. D. 1991, Nuclear Physics A, 535, 331
  * Liebendörfer et al. (2001) Liebendörfer, M., Mezzacappa, A., & Thielemann, F. 2001, Phys. Rev. D, 63, 104003
  * Liebendörfer et al. (2009) Liebendörfer, M., Whitehouse, S. C., & Fischer, T. 2009, ApJ, 698, 1174
  * Lund et al. (2012) Lund, T., Wongwathanarat, A., Janka, H.-T., Müller, E., & Raffelt, G. 2012, Phys. Rev. D, 86, 105031
  * Marek & Janka (2009) Marek, A., & Janka, H.-T. 2009, Astrophys. J., 694, 664
  * Marek et al. (2009) Marek, A., Janka, H.-T., Müller, E. 2009, A&A, 496, 475
  * Müller et al. (2010) Müller, B., Janka, H.-T., & Dimmelmeier, H. 2010, ApJS, 189, 104
  * Müller et al. (2012) Müller, B., Janka, H.-T., & Heger, A. 2012, ApJ, 761, 72
  * Müller et al. (2013) Müller, B., Janka, H.-T., & Marek, A. 2013, ApJ, 766, 43
  * Murphy & Burrows (2008) Murphy, J. W., & Burrows, A. 2008, ApJ, 688, 1159
  * Murphy et al. (2013) Murphy, J. W., Dolence, J. C., & Burrows, A. 2013, ApJ, 771, 52
  * Nagakura et al. (2013) Nagakura, H., Yamamoto, Y., & Yamada, S. 2013, ApJ, 765, 123
  * Nordhaus et al. (2010) Nordhaus, J., Burrows, A., Almgren, A., & Bell, J. 2010, ApJ, 720, 694
  * Ohnishi et al. (2006) Ohnishi, N., Kotake, K. & Yamada, S., 2006, ApJ, 641, 1018
  * Ohnishi et al. (2007) —. 2007, ApJ, 667, 375
  * Ott et al. (2008) Ott, C. D., Burrows, A., Dessart, L., & Livne, E. 2008, ApJ, 685, 1069
  * Ott et al. (2013) Ott, C. D., Abdikamalov, E., Mösta, P., et al. 2013, ApJ, 768, 115
  * Rampp & Janka (2000) Rampp, M., & Janka, H.-T. 2000, Astrophys. J. Lett., 539, L33
  * Rosswog & Liebendörfer (2003) Rosswog, S., & Liebendörfer, M. 2003, MNRAS, 342, 673
  * Scheck et al. (2004) Scheck, L., Plewa, T., Janka, H.-T., Kifonidis, K., & Müller, E., 2004, Phys. Rev. Lett., 92, 011103
  * Scheck et al. (2006) Scheck, L., Kifonidis, K., Janka, H.-T., Müller, E. 2006, A&A, 457, 963
  * Scheck et al. (2008) Scheck, L., Janka, H., Foglizzo, T., & Kifonidis, K. 2008, A&A, 477, 931
  * Sumiyoshi et al. (2005) Sumiyoshi, K., Yamada, S., Suzuki, H., et al. 2005, Astrophys. J., 629, 922
  * Suwa et al. (2010) Suwa, Y., Kotake, K., Takiwaki, T., et al. 2010, PASJ, 62, L49+
  * Suwa et al. (2011) Suwa, Y., Kotake, K., Takiwaki, T., Liebendörfer, M., & Sato, K. 2011, ApJ, 738, 165
  * Suwa et al. (2013) Suwa, Y., Takiwaki, T., Kotake, K., et al. 2013, ApJ, 764, 99
  * Takiwaki & Kotake (2011) Takiwaki, T., & Kotake, K. 2011, ApJ, 743, 30
  * Takiwaki et al. (2012) Takiwaki, T., Kotake, K., & Suwa, Y. 2012, ApJ, 749, 98
  * Tamborra et al. (2013) Tamborra, I., Hanke, F., Müller, B., Janka, H.-T., & Raffelt, G. 2013, Physical Review Letters, 111, 121104
  * Thompson et al. (2003) Thompson, T. A., Burrows, A., & Pinto, P. A. 2003, Astrophys. J., 592, 434
  * Wang & Wheeler (2008) Wang, L., & Wheeler, J. C. 2008, ARA&A, 46, 433
  * Wongwathanarat et al. (2010) Wongwathanarat, A., Janka, H.-T., Müller, E. 2010, ApJ, 725, L106
  * Wongwathanarat et al. (2013) Wongwathanarat, A., Janka, H.-T., & Müller, E. 2013, A&A, 552, A126
  * Woosley et al. (2002) Woosley, S. E., Heger, A., & Weaver, T. A. 2002, Reviews of Modern Physics, 74, 1015


# Link Prediction on Textual Edge Graphs

Chen Ling1∗, Zhuofeng Li2∗, Yuntong Hu1, Zheng Zhang1,
Zhongyuan Liu3, Shuang Zheng2, Liang Zhao1
1Emory University 2Shanghai University 3China University of Petroleum
Correspondence to: {chen.ling<EMAIL_ADDRESS>
###### Abstract

Textual-edge Graphs (TEGs), characterized by rich text annotations on edges,
are increasingly significant in network science due to their ability to
capture rich contextual information among entities. Existing works have
proposed various edge-aware graph neural networks (GNNs) or let language
models directly make predictions. However, they often fall short of fully
capturing the contextualized semantics on edges and graph topology,
respectively. This inadequacy is particularly evident in link prediction tasks
that require a comprehensive understanding of graph topology and semantics
between nodes. In this paper, we present a novel framework - Link2Doc,
designed especially for link prediction on textual-edge graphs. Specifically,
we propose to summarize neighborhood information between node pairs as a
human-written document to preserve both semantic and topology information. A
self-supervised learning model is then utilized to enhance GNN’s text-
understanding ability from language models. Empirical evaluations, including
link prediction, edge classification, parameter analysis, runtime comparison,
and ablation studies, on four real-world datasets demonstrate that Link2Doc
achieves generally better performance against existing edge-aware GNNs and
pre-trained language models in predicting links on TEGs.

**footnotetext: Both authors contributed equally to this work.

##  1 Introduction

In network science, the prevalence of networks with rich text on edges, also
known as Textual-edge Graphs (TEGs) [35, 9], increasingly become significant,
as they encapsulate a wealth of relational and contextual information critical
for diverse applications. The text associated with edges in networks can
dramatically deepen our understanding of network dynamics and behavior. For
instance, in a social media network, when a user responds to another’s post,
the reply not only creates a directed edge but also includes specific text
that can reveal the sentiment, intent, or relationship strength between the
users. Similar cases can also be found in citation networks where text on the
edge is the exact reference quote. These examples illustrate how text-rich
edges are pivotal in accurately interpreting and leveraging networked data for
advanced analytical purposes. In TEGs, link prediction is a unique yet open
question due to the complex textual information embedded on edges.

Extensive works have been devoted to studying graphs with rich text, which can
be classified into two categories, i.e., Graph Neural Networks (GNN)-based and
language model-based. GNN-based works have extensively studied the topology
connection between nodes and designed various variants. Specifically, works
[9, 40, 7] typically compress the text embedded on edges to latent vectors by
text encoders (e.g., Word2Vec [25] and BERT [5]), and iteratively merge edge
features with/without node features [15, 36]. The current most advanced edge-
aware GNN [17] tries to refine the text encoder with the GNN training to
obtain better representation, but it still follows the neighbor aggregation
way that may not comprehensively consider overall semantics. On the other
hand, owing to the strong text understanding ability of Large Language Models
(LLMs) [24], researchers [2, 6, 37, 33] have directly used language models to
solve graph mining tasks on textual graphs by designing various prompts to
express or summarize the topology connection into natural language.

While these approaches have advanced the study on text rich graphs, they tend
to simplify the diverse text on edges, potentially losing crucial information
necessary for tasks such as link prediction, where edge text is key to
understanding the relationships within the graph. Both GNN-based and LLM-based
methods may fall short of addressing the link prediction on TEGs due to two
challenges, respectively.

Figure 1: An example of textual-edge graphs: two books are connected by
citation links. Predicting whether there’ll be a citation between $A$ and $E$
needs to jointly consider both topology and semantic information embedded on
nodes and their edges.

Challenge 1: Understand graph topology in language models. For LLM-based
approaches, existing works have worked on prompting LLMs by expressing or
summarizing graph topology into text, but the graph topology is generally
expressed in a linear shape, which may lead to a significant loss of graph-
based structural information. For example, as shown in Figure 1, if we
summarize the relation between Book $A$ and $E$ as Breadth-first Search, the
dependencies along specific paths would be overlooked. This approach would not
capture the multi-hop interactions and the rich contextual dependencies among
nodes and edges. On the other hand, if we summarize all paths from $A$ to $E$,
the same edge, such as the negative reference on edge $C$ to $E$, could appear
in several paths. Representing this repeated edge in text multiple times leads
to unnecessary duplication and potential noise, complicating the model’s
ability to discern the true nature of the relationships. If the graph is too
large, potential overflow of the language model’s context window limitation
also may emerge.

Challenge 2: Comprehensively consider context information on all connections.
For GNN-based methods, predicting links in TEGs requires a comprehensive
examination of all potential paths connecting two nodes. Neighborhood
aggregation approaches often focus on immediate neighbors and fail to account
for the complex interactions that can occur in textual-edge graphs. As shown
in Figure 1, there are many multi-hop paths with different intermediate nodes
between $A$ and $B$, and each edge is annotated with different contexts,
including user descriptions and user comments, describing their complex
relations. It’s already hard for existing GNN-based methods to use one latent
vector to describe the complex context on edges. Moreover, user’s preferences
may also differ from one path to another (i.e., $A\rightarrow C\rightarrow E$
is negative while $A\rightarrow B\rightarrow D\rightarrow E$ is positive),
creating a conflicting semantic landscape. However, GNN’s neighbor aggregation
would treat these paths uniformly, potentially diluting the sentiment
difference in these paths.

Present Work. To effectively make link predictions on TEGs by jointly
considering rich semantic information and graph topology, in this paper, we
propose a novel network representation learning framework, Link2Doc, that
transforms local connections between nodes into a coherent document for better
reflecting graph topology along with semantic information. The crafted
document further enhances GNNs to make link predictions in a contextualized
way. The key contributions are summarized as follows:

  * •

Problem. We formulate the problem of link prediction on textual-edge graphs
and highlight the unique challenges of learning representations on textual-
edge graphs for link prediction.

  * •

Method. We propose an integrated framework to jointly consider topology and
semantic information in textual-edge graphs, which consists of 1) coherent
document composition to summarize local topology information between node
pairs in plain language; and 2) a self-supervised learning module to teach
graph neural networks language processing ability.

  * •

Experiment. We empirically compare our method against existing state-of-the-
arts in four real-world datasets. Results have shown our proposed methods can
elevate the performance of general GNNs and achieve competitive performance
against edge-aware GNNs.

##  2 Related Works

Edge-aware Graph Representation Learning. Earlier research of Graph Neural
Networks (GNNs) [30, 4] tends to only focus on node features. Later on,
research on heterogeneous graph representation learning [34, 21, 22] began to
consider categorical information on edges. In text-attributed graphs, to more
comprehensively utilize edge information during the network representation
learning, some edge-aware GNNs [40, 7, 15, 36] were proposed to consider edge
text by designing various architectures (e.g., attention on edges, node and
edge role switch, etc.). The recent state-of-the-art method EdgeFormer [17]
involved pre-trained language models and proposed to better consider edge text
by designing a cross-attention mechanism to merge node and edge representation
in Transformer layers. However, these approaches still use the neighborhood
aggregation way to obtain graph representation and cannot consider the local
connections as a whole unit. Neighborhood aggregation may not always work
especially when nodes are dissimilar (as shown in Figure 1) [31]. Moreover,
existing edge-aware GNNs tend to deliberately erase text on nodes and only
explore the effect of edge information on various graph-related tasks [17],
which lacks the flexibility to extend to other text-attributed scenarios.

Language Modeling Augmented Graph Learning. Large language models have been
proven to have the ability to interpret graph-structured data [14, 8, 16]. In
the past year, many works [3, 2, 13, 26] have been proposed to prove LLMs have
great potential (and even become state-of-the-art) to classify nodes in text-
attributed graphs. However, how LLMs can better assist link prediction in
text-attributed graphs is still an under-explored area, let alone the more
complicated scenario of edge-attributed graphs that contain rich textual
information on both edges and nodes. Existing works [41, 39, 19, 29] have
tried to distill implicit knowledge from LLMs to smaller GNN models for text-
attributed graph tasks, but they still focus on learning good node embeddings.
In edge-attributed graphs, text on edges cannot be uniformly processed in the
same manner as node text, necessitating more specialized techniques that
account for the unique semantics and structural roles of edge attributes in
enhancing graph-based learning models.

##  3 Link Prediction on Textual-edge Graph

In this section, we begin by introducing key notations and formulating the
problem of link prediction on Textual-edge Graphs. We then describe a novel
way of constructing a transition document that summarizes the relationship
between node pairs for link prediction. Finally, we provide an LLM-enhanced
Graph Neural Network framework that learns the local topology and semantic
information to retain both efficiency and efficacy.

###  3.1 Problem Formulation

A Textual-edge graph (TEG) is a type of graph in which both nodes and edges
contain free-form text descriptions. These descriptions provide detailed,
contextual information about the relationships between nodes, enabling a
richer representation of relational data than in traditional graphs.

######  Definition 1 (Textual-edge Graphs).

A TEG $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is an undirected graph, which
consists of a set of nodes $V$ and a set of edges
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$. Each node
$v_{i}\in\mathcal{V}$ contains a textual description $d_{i}$, and each edge
$e_{ij}\in\mathcal{E}$ also associates with free-form texts $d_{ij}$
describing the relation of $(v_{i},v_{j})$.

In this work, we target at the Link Prediction task on TEGs, where we aim to
predict the existence (or the label) of edges between pairs of nodes
$(v_{i},v_{j})\notin\mathcal{E}$ based on the neighborhood information of
$(v_{i},v_{j})$. Due to the rich edge text information, local edges in TEGs
can inherently be represented by natural language sentences. For example, the
connection $v_{i}\rightarrow e_{ij}\rightarrow v_{i}$ can be represented as
“$d_{i}$ is connected to $d_{j}$ via $d_{ij}$”, which directly describes the
relation in plain text.

Compared to categorical-edge graphs that have edges labeled with simple,
predefined categories, textual-edge graphs feature edges annotated with free-
form text, which offer detailed and contextual relationship descriptions. Take
Figure 1 again as an example, books are connected by textual edges, where text
on edges consists of exact quotations that one book cites another. To predict
whether $A$ and $E$ will have a citation link, we not only need to analyze
semantics embedded within each edge’s description, but different paths may
also depict different semantic meanings due to the varying textual
descriptions and types of relationships they represent. As noted in Figure 1,
the Red Path contains negative reference from $A$ to $E$, while the Blue Path
indicates another group of researchers endorse the research conducted by book
$A$.

Challenge. The rich and complex text information on edges makes the link
prediction on TEGs not a trivial task, and there are two essential
difficulties regulating existing GNN-based and LLM-based methods,
respectively. For edge-aware GNN-based methods, directly combine and update
each node $v_{i}$’s feature based on its neighbor’s
$\mathcal{N}_{v_{i}}(v_{j})$ features as well as features of edges $e_{ij}$.
However, neighborhood aggregation would fall short since semantic information
carried on each edge $d_{ij}$ needs to be viewed in the context of the whole
connections from $s$ to $t$. For LLM-based methods, existing works tend to
prompt language models by summarizing graph topology in a linear manner, e.g.,
“$G_{(s,t)}$ contains $s,v_{1},v_{2},...,v_{n},t$ nodes, $v_{1}$ is connected
to $v_{2}$ via $d_{12}$, $v_{2}$ is connected to $v_{4}$ via $d_{24}$, etc.”
This way may let LLMs fail to understand how information propagates from $s$
to $t$ and the contextual dependencies among nodes.

Figure 2: Overall framework of LLM-enhanced link prediction on Textual-edge
graphs, where orange and blue nodes in $G_{(s,t)}$ belong to $s$’s and $t$’s
local neighborhood (namely $G_{s}$ and $G_{t}$), respectively. Half blue and
half orange nodes denote shared nodes between $G_{s}$ and $G_{t}$.

###  3.2 Overall Architecture

In this work, we introduce Link2Doc, a novel approach that leverages a self-
supervised learning scheme to endow GNNs with text comprehension capabilities
akin to those of LLMs. Link2Doc is designed to preserve and synergize rich
semantic information, topology information, and their interplay within TEGs
for link prediction. We propose learning and aligning representations from two
complementary perspectives: the text view and the graph view. The text view,
termed Text-of-Graph, organizes the text associated with TEG’s nodes in a way
that reflects the graph’s topology, forming a structured document that
inherently captures logical and relational data. Conversely, the graph view,
or Graph-of-Text, transforms the nodes and topology of TEGs into structured
graph data. By employing pretrained language models (PLMs), the text view
adeptly maintains textual integrity, while the graph view, processed through
GNNs, ensures the retention of graph-specific characteristics. Aligning these
views allows each representation to enrich the other, fostering a holistic
understanding where textual nuances inform graph structures and vice versa.

Specifically, as noted in Figure 2 (a), to reduce the search space and to
eliminate the noise from unrelated connections, we propose to formulate a
$(s,t)$-transition graph containing all the possible routes through which $s$
could correlate to $t$ for link prediction.

######  Definition 2 (Transition Graph).

For any pair of two entities $(s,t)$ in the Textual-edge Graph, all paths from
$s$ to $t$ collectively form an $(s,t)$-transition graph, which is denoted by
$G_{(s,t)}$. We use $n$ and $m$ to denote the number of nodes and edges in
$G_{(s,t)}$, respectively. Figure 1 exemplifies an $(s,t)$-transition graph,
where $s$ is Book $A$ and $t$ is Book $B$. In practice, the length of paths
can be upper-bounded by an integer $K$, which can usually be set as the
diameter of the Textual-edge graph.

The transition graph $G_{(s,t)}$, as well as all the text on edges, provide
the necessary information needed to understand the relation between $s$ and
$t$. Next, as shown in Figure 2(b), we separate two subgraphs: $G_{s}$ and
$G_{t}$ from $G_{(s,t)}$ for preserving local neighborhood of $s$ and $t$,
respectively. In Figure 2(c), to view the topology and semantic information of
$G_{(s,t)}$ in a joint unit, we compose a manageable and coherent document
that expresses $G_{(s,t)}$ as a human-written document. Finally, in Figure
2(d), we distill the text processing ability from large language models to
graph neural networks for inference scalability while maintaining performance.

###  3.3 Transition Document Construction

In this work, to address the first challenge, we need to summarize local
relations in $G_{(s,t)}$ to comprehensively understand the relation between
$(s,t)$. Since state-of-the-art LLMs are predominantly trained on human-
written documents and books, in this work, we propose a novel way to express
$G_{(s,t)}$ as a structured document $d_{(s,t)}$ [18], complete with an
introduction, sections, subsections, and a conclusion, to let language models
better understand the overall semantics between $s$ and $t$ with preserving
topology. The overall process is illustrated in Figure 3, and the algorithm is
summarized in Appendix 1 due to the space limit.

Figure 3: Given the transition graph $G_{(s,t)}$, we first split $G_{(s,t)}$
into $G_{s}$ (nodes are marked with orange) corresponding to the local
structure of $s$ ($G_{t}$ is omitted due to space limit). Commonly shared
nodes are marked with half blue and half orange. We transform the local
structure of $G_{s}$ into a paragraph that summarizes hierarchical relation
with $s$ being the root. For better visibility, hidden edges are highlighted
with orange, and commonly shared nodes are highlighted with blue.

Node-centric Paragraph Composition. For source node $s$ and target node $t$,
we first conduct Breadth-first Search (BFS) to extract their respective local
structure with depth $L$, i.e., $G_{s}$ and $G_{t}$ from their transition
graph $G_{(s,t)}$. As shown in Figure 3, nodes in $G_{(s,t)}$ that belong to
$G_{s}$ are marked with orange, and nodes belonging to $G_{t}$ are marked with
blue. The structural data (i.e., BFS tree) obtained is transformed into a
textual paragraph aimed at both human readability and machine processability.
Specifically, taking the BFS tree $G_{s}$ rooted at source node $s$ as an
example, $s$ acts as the main subject of the paragraph’s textual summary. We
conduct pre-order traversal to go over all nodes in both trees. The first and
subsequent levels of BFS neighbors are detailed in separate sections and
subsections, akin to a detailed outline:

  1. 1.

Root: Start with a comprehensive sentence that describes node $s$ and its
immediate connections: “[ROOT s] Node $s$ has three connections. $s$ is
connected to $v_{1}$ via $d_{s1}$, $s$ is connected to $v_{2}$ via $d_{s2}$,
and $s$ is connected to $v_{3}$ via $d_{s3}$’’, where $d_{s1},d_{s2},$ and
$d_{s3}$ are textual descriptions on edges $e_{s1},e_{s2}$, and $e_{s3}$.

  2. 2.

First-hop Neighbors: For each first-hop neighbor of $s$, we provide a section
detailing its connections: “[1]. Node $v_{1}$ has two connections. $v_{1}$ is
connected to $v_{11}$ via $d_{11}$, and $v_{1}$ is connected to $v_{12}$ via
$d_{12}$”; “[2]. Node $v_{2}$ has one connection. $v_{2}$ is connected to
$v_{21}$ via $d_{21}$”; and “[3]. Node $v_{3}$ has two connections. $v_{3}$ is
connected to $v_{31}$ via $d_{31}$, ...”.

  3. 3.

Second (and following)-hop Neighbors: Subsections under each first-hop
neighbor detail further connections: “[1.1] $v_{11}$ is connected to ...”
“[1.2] $v_{12}$ is connected to...”.

This structure is recursively applied up to $L$ levels deep, ensuring each
node’s direct connections are thoroughly described, capturing the intricate
topology of the graph. The notation “[Section X]” serves as a reference back
to earlier parts of the summary where the connected node was initially
described, aiding in understanding the network’s connectivity beyond a simple
hierarchical structure.

Hidden Edges. In many cases, we may not guarantee the neighborhood surrounding
$s$ can form a tree structure. As shown in the transition graph in Figure 3,
node $v_{122}$ is not only the child node of $v_{12}$, $v_{122}$ also links
back to $v_{1}$ to form a triangle structure. To consider a more holistic view
of the node relationships, we add an extra description to the node stating its
connection to pre-existing nodes. Specifically, we introduce the hidden edge
information of node $v_{122}$ in [Sec. 1.2.2] as “In addition, $v_{122}$ is
also linked to [Sec. 1] $v_{1}$ via ...”. By letting each mention of a hidden
edge direct back to the respective section “[Section X]”, we aim to ensure
clarity and maintain the coherence of the graph’s description.

Transition Graph Document Construction. After generating the individual
paragraphs for $s$ and $t$, we then concatenate these into a single document
$d_{(s,t)}$. This unified $d_{(s,t)}$ aims to not only present isolated
descriptions but also to highlight the interconnected nature of $G_{s}$ and
$G_{t}$. In this work, we aim to illuminate the interconnectedness between
$G_{s}$ and $G_{t}$ by identifying and highlighting nodes that appear in both
$G_{s}$ and $G_{t}$’s local structures. These common nodes are pivotal as they
link the context of one paragraph to the other. As shown in Figure 3, the
common nodes are marked with half orange and half blue. For each common node,
we include a cross-reference in the text where the node is mentioned, which is
done by adding a note after the section index. For example, node $v_{122}$ has
a section index “[1.2.2]” in $s$’s paragraph, and a section index “[1.2.1]” in
$t$’s paragraph. We then add ([Sec. 1.2.1] in Paragraph $t$) after the section
index of $v_{121}$ in $s$’s paragraph. We conduct the cross-reference in the
other paragraph reversely.

In practice, we keep the depth $L$ to be half of the diameter of the
$G_{(s,t)}$ so that $G_{s}$ and $G_{t}$ can each cover their close neighbor
information as well as an adequate number of common nodes. We further enhance
the document’s coherence by adding an introduction to the start of the
document. Finally, the generated $d_{(s,t)}$ can be viewed as a structured
document [18]. More details can be found in Figure 3.

###  3.4 LLM-enhanced Representation Learning for Link Prediction

Even though we can obtain a document $d_{(s,t)}$ summarizing topology and
semantic information of $G_{(s,t)}$, scalability still poses a significant
challenge for language models to make predictions on large-scale graphs. To
conduct large-scale link predictions, we need to compose a large number of
documents between node pairs, and many contents in these documents are
duplicated (e.g., the transition documents of $(s,t_{1})$ and $(s,t_{2})$
largely overlap if $t_{1}$ and $t_{2}$ are neighbors). Moreover, $G_{(s,t)}$
with a diameter of $4$ can easily reach thousands of nodes in large graphs
[23], and the number of words in such a document would also exceed the context
window limitation of most language models [24]. However, GNNs are designed to
efficiently process graph structures, which motivates us to distill the text-
processing ability of LLMs into GNNs, thus addressing the second challenge.

Aligning Topology Representation of $G_{(s,t)}$ with Semantic Information.
Although LLMs may not be capable of conducting large-scale link predictions,
the implicit knowledge can still be utilized to train GNNs. In this work, we
leverage LLMs to generate latent embeddings of $d_{(s,t)}$ as
$\tilde{h}_{(s,t)}$ to guide the training of GNNs:

$\displaystyle\tilde{h}_{(s,t)}=f_{LM}\left(d_{(s,t)}\right),\quad\quad
h_{(s,t)}=g\left(f_{GNN}(G_{s})\oplus f_{GNN}(G_{t})\right),$

where $\oplus$ denotes embedding concatenation, $f_{LM}(\cdot)$ and
$f_{GNN}(\cdot)$ denote the LLM query function and GNNs, respectively. We
transform text on nodes and edges with pre-trained language models (e.g., BERT
[5] or LLaMA models [27]) and feed these attributes along with adjacency
matrix of $G_{s}$ and $G_{t}$ to GNNs. The outputs are then concatenated and
transformed into LLM’s embedding space by a projection function $g(\cdot)$
with non-linear transformation. We seed to align the latent embeddings
$\tilde{h}_{(s,t)}$ produced by the LLM with the embeddings $h_{(s,t)}$
generated by the GNN:

$\displaystyle\ell_{KD}=-\mathbb{E}\left[\log\frac{\exp\left(\operatorname{sim}(\tilde{h}_{(s,t)},h_{(s,t)})/\tau\right)}{\sum^{K}_{k=1}\exp\left(\operatorname{sim}(h_{(s,t)},h_{(s,k)})/\tau\right)}\right],$
(1)

where the objective function is based on temperature-scaled cross-entropy loss
(NT-Xent) [1] to enforce the agreement between $\tilde{h}_{(s,t)}$ and
$h_{(s,t)}$ compared with latent embedding $h_{(s,k)}$ from negative pairs.
Furthermore, to calibrate $h_{(s,t)}$ more towards the link prediction (and
edge classification) task, we incorporate standard binary cross-entropy loss
$\ell_{LP}$ for tuning GNNs. Note that for dealing with highly imbalanced
label distribution for edge classification tasks, we use weighted cross-
entropy loss (e.g., Focal Loss [20]) instead.

Finally, the overall objective of the LLM-enhanced Representation Learning for
predicting links on edge-attributed graphs is written as
$\ell=\lambda_{1}\ell_{KD}+\lambda_{2}\ell_{LP}$, where $\lambda_{1}$ and
$\lambda_{2}$ are hyperparameters.

Complexity Analysis. Given the transition graph $G_{(s,t)}$ with the diameter
$K$, we use Breadth-first Search (time complexity $O((N+E)/2$) (BFS) with the
depth $K/2$ to extract $G_{s}$ and $G_{t}$, respectively. We then use pre-
order traversal to obtain the document $d_{(s,t)}$, which leads the total
complexity to be $O(N+E+N)$. The time complexity for Pre-trained LMs to
process $d_{(s,t)}$ is $O(P^{2})$, where $P$ denotes the number of tokens in
$d_{(s,t)}$. Moreover, the GNN module requires $O(|E|\cdot f+N^{2})$, where
$f$ denotes the dimension of the embedding on nodes/edges. Overall, The
complexity encapsulates the stages of BFS tree construction, document
processing with Transformers, and GNN learning, which gives the training time
complexity $O(2N+E+P^{2}+|E|\cdot f+N^{2})$. However, during the inference
stage, the complexity of our work simply reduces to the complexity of normal
GNNs: $O(|E|\cdot f+N^{2})$ as we do not need to construct documents during
the inference phase.

##  4 Experiment

We conduct various experiments, including link prediction, edge
classification, runtime analysis, and ablation study, to verify the
effectiveness of Link2Doc on multiple real-world textual-edge graphs.

###  4.1 Experiment Setup

The focus of the paper is link prediction on textual-edge graphs, which aims
at predicting if there will be a strong connection between two specific nodes
in the Amazon and Goodreads datasets based on their transition graph. For
instance, in GoodRead datasets, we analyze a target user’s reviews of other
items or books, as well as the reviews of the target item or book by other
users. Our aim is to forecast whether there will be a top-rated link (5-star)
between the target user and the target item. We evaluate the performance using
the standard metrics: Area Under ROC Curve (AUC) metric and F1 score. We adopt
Graph Transformer (GTN) [38] as our base GNN for the self-supervised learning
module.

Data. We run experiments on four real-world networks: Amazon-Movie [11],
Amazon-Apps [11], GoodReads-Children [28], and GoodReads-Crime [28]. Amazon is
a user-item interaction network, with reviews serving as textual content
associated with the edges. Goodreads is a reader-book network, that utilizes
readers’ comments as textual information within the edges. More specific
dataset statistics can be found in the Appendix A.2.

Comparison Methods. We compare our model with general GNNs, language model
integrated GNNs, and large language models. For general GNNs, we select
MeanSAGE [10], MaxSAGE [10], and GIN [32], which only use an adjacency matrix
as the input. For language model-enhanced GNNs, we utilize Pre-trained LMs,
e.g., BERT [5], to acquire text representations on edges. Our baselines
consist of BERT + Graph Transformer (GTN) [38] and BERT + GINEConv [12].
Furthermore, we also incorporate state-of-the-art edge-aware GNN - Edgeformer
[17], which is constructed based on graph-enhanced Transformers to combine
language modeling into each layer of the Graph transformer. Finally, we adopt
state-of-the-art LLMs, i.e., LLaMA-2-13B and GPT-3.5-Turbo by directly
translating the transition graph $G_{(s,t)}$ between the node pair $(s,t)$ to
natural language as [6] do. Note that state-of-the-art language model
integrated GNNs, namely EdgeFormer and GINEConv, cannot incorporate text on
nodes. For a fair comparison, we present two variants of our method: Link2Doc
does not consider node texts, and Link2Doc-NT takes node text into account.

Implementation Details. For general GNNs, the dimensions of the initial node
and edge embeddings are set to be 64 and 128 respectively. For language model
integrated GNNs, the dimension of the node embeddings is consistent with that
of general GNN methods. However, the edge embeddings dimension is $3072$,
which is obtained from OpenAI’s embedding model: text-embedding-3-large.
Additionally, for the Edgeformer model, we adhere to the same experimental
settings as outlined in [17]. Our model uses Graph Transformer (GTN) as our
backbone, where both node and edge embeddings mirror those of language model
integrated GNNs. We set $\lambda_{1}=1$ and $\lambda_{2}=2$ respectively. All
GNN baseline layers are set to $2$. We use Adam as the optimizer with a
learning rate of $1e-5$. The batch size is $1024$. For obtaining the embedding
of the generated document, we also incorporate OpenAI’s embedding text-
embedding-3-large with dimension $3072$. We run our model and other baselines
$10$ times with different random seeds and report AUC and F1 on average.

| Goodreads-Children | Goodreads-Crime | Amazon-Apps | Amazon-Movie
---|---|---|---|---
| AUC | F1 | AUC | F1 | AUC | F1 | AUC | F1
General GNN |  |  |  |  |  |  |  |
Max-SAGE | 0.870 | 0.637 | 0.858 | 0.624 | 0.727 | 0.571 | 0.706 | 0.527
Mean-SAGE | 0.828 | 0.611 | 0.829 | 0.615 | 0.700 | 0.569 | 0.686 | 0.525
GIN | 0.859 | 0.571 | 0.857 | 0.577 | 0.705 | 0.543 | 0.692 | 0.512
Edge-aware GNN |  |  |  |  |  |  |  |
GTN | 0.880 | 0.654 | 0.863 | 0.640 | 0.728 | 0.572 | 0.742 | 0.539
GINEConv | 0.881 | 0.657 | 0.864 | 0.636 | 0.701 | 0.573 | 0.692 | 0.543
Edgeformer | 0.882 | 0.662 | 0.862 | 0.643 | 0.722 | 0.580 | 0.744 | 0.540
LLMs |  |  |  |  |  |  |  |
LLaMA-2-13B | 0.832 | 0.573 | 0.869 | 0.587 | 0.694 | 0.509 | 0.643 | 0.482
GPT-3.5-Turbo | 0.878 | 0.609 | 0.889 | 0.604 | 0.712 | 0.512 | 0.659 | 0.503
Link2Doc | 0.902 | 0.705 | 0.901 | 0.652 | 0.762 | 0.588 | 0.753 | 0.553
Link2Doc-NT | – | – | – | – | 0.769 | 0.595 | 0.759 | 0.565

Table 1: The performance comparison of Link Prediction on all datasets (the
higher the better), where the bests are highlighted with bold, and the second
bests are highlighted with underline. Note that $-$ indicates the dataset does
not have text on nodes so that Link2Doc-NT cannot be conducted.

###  4.2 Results on Link Prediction

As can be seen from Table 1, without considering the text on nodes, Link2Doc
can already achieve a generally better performance than other methods.
Specifically, Link2Doc outperforms the second best on average $5$% of both AUC
and F1 across all datasets. We further draw several observations from the
results. 1) There are no clear differences between general GNNs and edge-aware
GNNs: both types of GNNs show comparable performance, with edge-aware GNNs
having a slight edge but not consistently outperforming general GNNs in all
metrics, which implies co-training language models with GNNs still cannot
capture the subtle cues on edge texts. For instance, while Edgeformer achieves
the second-best AUC on the Goodreads-Children dataset, it doesn’t consistently
outperform general GNNs like Max-SAGE across all datasets. 2) Directly
summarizing topology and letting LLMs make predictions may not perform well:
LLMs, such as LLaMA-2-13B and GPT-3.5-Turbo, tend to underperform compared to
specialized GNNs and our proposed Link2Doc. This is evident that state-of-the-
art LLMs may not be able to fully understand graph topology from the linear
topology summarization, highlighting the advantage of the composed document.
3) Text on nodes can further improve the performance: As can be seen from the
table, even though Link2Doc can achieve a generally better performance than
other approaches, by considering the text on nodes, Link2Doc-NT can achieve a
generally better performance than its no node-text version.

###  4.3 Results on Edge Classification

| Amazon-APPs
---|---
AUC | F1
Mean-SAGE | $0.551$ | $0.479$
GINE | $0.573$ | $0.488$
GTN | $0.567$ | $0.503$
Edgeformer | $0.612$ | $0.526$
Link2Doc | 0.626 | 0.541
Table 2: Comparison on Edge Classification on Amazon-APPs dataset.

In the task of edge classification, the model is asked to predict the category
of each edge based on its associated text and local network structure. There
are $5$ categories for edges in the Amazon-APPs dataset (i.e., from 1 star to
5 star). The results of the $5$-class edge-type classification are shown in
Table 2. As clearly can be observed in the table, Link2Doc improves the AUC by
an average of $5\%$ and the F1 score by $4.2\%$ compared to other models,
demonstrating its superior performance in edge classification.

###  4.4 Ablation Study and Parameter Analysis

We further demonstrate the effectiveness of each component in our framework
and analyze the importance of different hyper-parameter settings.

(a) Link Prediction Improvement

(b) Edge Classification Improvement

Figure 4: Leveraging composed documents to enhance base GNNs on Amazon-APPs
dataset.

Performance Elevation from Transition Document. We first aim to check the
general performance elevation brought by the composed transition document
$d_{(s,t)}$. We adopt three GNNs with using BERT to obtain embeddings on edges
and illustrate whether using the composed $d_{(s,t)}$ as a reference would
improve their performance in both link prediction and edge classification
tasks. The results on the Amazon-APPs dataset are presented in Figure 4. As
can be seen from the figure, the document-augmented GNNs excel in their
general version with an average improvement of $5\%$. By summarizing all
relations from $s$ to $t$ as a coherent document, language models can give
positive feedback on the proposed self-supervised learning module to guide
different GNNs in learning.

Figure 5: The performance on Amazon-APPs.

Hyperparameter Analysis. We then aim to investigate the sensitivity of the key
hyperparameter $\lambda_{2}$ and their impact on Link2Doc’s performance.
Specifically, since $\lambda_{1}$ controls the basic objective function for
link prediction, we fix $\lambda_{1}=1$ and show the link prediction
performance on the Amazon-APPs dataset under different $\lambda_{2}$ values
(ranging from $0$ to $5$). As shown in Figure 5, both metrics show consistent
results across varying parameter values. By comparing with the second-best
methods (highlighted with red dash horizontal lines), Link2Doc with various
$\lambda_{2}$ values can achieve overall better results. This demonstrates
that our model maintains superior performance across different configurations,
highlighting its stability and effectiveness.

###  4.5 Runtime Analysis

| Children | Crime
---|---|---
Inference Time (s) |  |
Edgeformer | $1450.67$ | $3307.66$
Link2Doc | $49.35$ | $23$
Training Time (h) |  |
Edgeformer | $12.17$ | $12.65$
Link2Doc | $5.253$ | $7.04$
Table 3: Comparison of Inference and Training Times on Goodreads-Children and
Goodreads-Crime.

We further illustrate the runtime comparison between our proposed Link2Doc
with the state-of-the-art edge-aware GNN - Edgeformer. The comparison table
(Table 3) highlights the efficiency of our method, Link2Doc, which
significantly outperforms Edgeformer in both inference and training times. For
the Goodreads-Children dataset, Link2Doc is approximately 29 times faster in
inference and more than twice as fast in training. On the Goodreads-Crime
dataset, Link2Doc demonstrates an even greater advantage, being about 144
times faster in inference and almost twice as fast in training. These
improvements stem from Link2Doc’s design, which does not require fine-tuning
language models; instead, it builds document representations and uses a pre-
trained GNN, avoiding the extensive matrix calculations in Edgeformer’s cross-
attention design. Consequently, Link2Doc is more scalable and efficient for
large-scale link prediction tasks.

##  5 Conclusion

In this work, we study the problem of link prediction on textual-edge graphs,
where existing GNN-based and LLM-based methods may fall short of jointly
capturing both semantic and topology information to make more accurate link
predictions. We present a novel framework Link2Doc that learns and aligns the
semantic representation and topology representation by 1) building a
structured document to preserve both topology and semantic information; and 2)
designing a self-supervised learning module to let GNNs have text
understanding ability like LLMs. In the experiment, we analyze the strength of
Link2Doc on four real-world datasets, and our method generally outperforms
other approaches from multiple aspects, highlighting the performance
improvement by bridging language models and GNNs with the structured document.

## References

  * [1] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [2] Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al.  Exploring the potential of large language models (llms) in learning on graphs.  ACM SIGKDD Explorations Newsletter, 25(2):42–61, 2024.
  * [3] Zhikai Chen, Haitao Mao, Hongzhi Wen, Haoyu Han, Wei Jin, Haiyang Zhang, Hui Liu, and Jiliang Tang.  Label-free node classification on graphs with large language models (llms).  arXiv preprint arXiv:2310.04668, 2023.
  * [4] Hejie Cui, Jiaying Lu, Shiyu Wang, Ran Xu, Wenjing Ma, Shaojun Yu, Yue Yu, Xuan Kan, Tianfan Fu, Chen Ling, et al.  A survey on knowledge graphs for healthcare: Resources, application progress, and promise.  In ICML 3rd Workshop on Interpretable Machine Learning in Healthcare (IMLH), 2023.
  * [5] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In NAACL-HLT, pages 4171–4186, 2019.
  * [6] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi.  Talk like a graph: Encoding graphs for large language models.  In The Twelfth International Conference on Learning Representations, 2023.
  * [7] Liyu Gong and Qiang Cheng.  Exploiting edge features for graph neural networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [8] Jiayan Guo, Lun Du, and Hengyu Liu.  Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking.  arXiv preprint arXiv:2305.15066, 2023.
  * [9] Xiaojie Guo, Liang Zhao, Cameron Nowzari, Setareh Rafatirad, Houman Homayoun, and Sai Manoj Pudukotai Dinakarrao.  Deep multi-attributed graph translation with node-edge co-evolution.  In 2019 IEEE International Conference on Data Mining (ICDM), pages 250–259, 2019.
  * [10] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In NIPS, pages 1024–1034, 2017.
  * [11] Ruining He and Julian McAuley.  Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering.  In proceedings of the 25th international conference on world wide web, pages 507–517, 2016.
  * [12] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec.  Strategies for pre-training graph neural networks.  arXiv preprint arXiv:1905.12265, 2019.
  * [13] Jin Huang, Xingjian Zhang, Qiaozhu Mei, and Jiaqi Ma.  Can llms effectively leverage graph structural information: when and why.  arXiv preprint arXiv:2309.16595, 2023.
  * [14] Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji-Rong Wen.  Structgpt: A general framework for large language model to reason over structured data.  In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 9237–9251, 2023.
  * [15] Xiaodong Jiang, Pengsheng Ji, and Sheng Li.  Censnet: Convolution with edge-node switching in graph neural networks.  In IJCAI, pages 2656–2662, 2019.
  * [16] Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han.  Large language models on graphs: A comprehensive survey.  arXiv preprint arXiv:2312.02783, 2023.
  * [17] Bowen Jin, Yu Zhang, Yu Meng, and Jiawei Han.  Edgeformers: Graph-empowered transformers for representation learning on textual-edge networks.  In The Eleventh International Conference on Learning Representations, 2022.
  * [18] Yong Kyu Lee, Seong-Joon Yoo, Kyoungro Yoon, and P Bruce Berra.  Index structures for structured documents.  In Proceedings of the first ACM international conference on Digital libraries, pages 91–99, 1996.
  * [19] Yichuan Li, Kaize Ding, and Kyumin Lee.  Grenade: Graph-centric language model for self-supervised representation learning on text-attributed graphs.  EMNLP, 2023.
  * [20] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [21] Chen Ling, Carl Yang, and Liang Zhao.  Deep generation of heterogeneous networks.  In 2021 IEEE international conference on data mining (ICDM), pages 379–388, 2021.
  * [22] Chen Ling, Carl Yang, and Liang Zhao.  Motif-guided heterogeneous graph deep generation.  Knowledge and Information Systems, 65(7):3099–3124, 2023.
  * [23] Chen Ling, Xuchao Zhang, Xujiang Zhao, Yanchi Liu, Wei Cheng, Mika Oishi, Takao Osaki, Katsushi Matsuda, Haifeng Chen, and Liang Zhao.  Open-ended commonsense reasoning with unrestricted answer candidates.  In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
  * [24] Chen Ling, Xujiang Zhao, Jiaying Lu, Chengyuan Deng, Can Zheng, Junxiang Wang, Tanmoy Chowdhury, Yun Li, Hejie Cui, Tianjiao Zhao, et al.  Domain specialization as the key to make large language models disruptive: A comprehensive survey.  arXiv preprint arXiv:2305.18703, 2305, 2023.
  * [25] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781, 2013.
  * [26] Bo Pan, Zheng Zhang, Yifei Zhang, Yuntong Hu, and Liang Zhao.  Distilling large language models for text-attributed graph learning.  arXiv preprint arXiv:2402.12022, 2024.
  * [27] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  arXiv preprint arXiv:2307.09288, 2023.
  * [28] Mengting Wan, Rishabh Misra, Ndapa Nakashole, and Julian McAuley.  Fine-grained spoiler detection from large-scale review corpora.  arXiv preprint arXiv:1905.13416, 2019.
  * [29] Zhihao Wen and Yuan Fang.  Augmenting low-resource text classification with graph-grounded pre-training and prompting.  In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 506–516, 2023.
  * [30] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  IEEE transactions on neural networks and learning systems, 32(1):4–24, 2020.
  * [31] Yiqing Xie, Sha Li, Carl Yang, Raymond Chi-Wing Wong, and Jiawei Han.  When do gnns work: Understanding and improving neighborhood aggregation.  In IJCAI’20: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence,$\\{$IJCAI$\\}$ 2020, volume 2020, 2020.
  * [32] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In ICLR, 2019.
  * [33] Hao Yan, Chaozhuo Li, Ruosong Long, Chao Yan, Jianan Zhao, Wenwen Zhuang, Jun Yin, Peiyan Zhang, Weihao Han, Hao Sun, et al.  A comprehensive study on text-attributed graphs: Benchmarking and rethinking.  Advances in Neural Information Processing Systems, 36:17238–17264, 2023.
  * [34] Carl Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han.  Heterogeneous network representation learning: A unified framework with survey and benchmark.  IEEE Transactions on Knowledge and Data Engineering, 34(10):4854–4873, 2020.
  * [35] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang.  Network representation learning with rich text information.  In IJCAI, volume 2015, pages 2111–2117, 2015.
  * [36] Yulei Yang and Dongsheng Li.  Nenn: Incorporate node and edge features in graph neural networks.  In Asian conference on machine learning, pages 593–608. PMLR, 2020.
  * [37] Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang.  Natural language is all a graph needs.  arXiv preprint arXiv:2308.07134, 2023.
  * [38] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim.  Graph transformer networks.  Advances in neural information processing systems, 32, 2019.
  * [39] Jianan Zhao, Meng Qu, Chaozhuo Li, Hao Yan, Qian Liu, Rui Li, Xing Xie, and Jian Tang.  Learning on large-scale text-attributed graphs via variational inference.  ICLR, 2023.
  * [40] Shichao Zhu, Chuan Zhou, Shirui Pan, Xingquan Zhu, and Bin Wang.  Relation structure-aware heterogeneous graph neural network.  In 2019 IEEE international conference on data mining, pages 1534–1539, 2019.
  * [41] Tao Zou, Le Yu, Yifei Huang, Leilei Sun, and Bowen Du.  Pretraining language models with text-attributed heterogeneous graphs.  arXiv preprint arXiv:2310.12580, 2023.

##  Appendix A Supplemental Material

###  A.1 Algorithm of Transition Document Composition

Data: The transition graph $G_{(s,t)}$, the diameter $K$ of $G_{(s,t)}$.

Result: Composed document $d_{(s,t)}$ with hierarchical relation, hidden edge
references, and cross-paragraph references.

1\. $G_{s}\leftarrow
BFS(\text{ROOT}=s,\text{GRAPH}=G_{(s,t)},\text{DEPTH}=K//2)$;

2\. $G_{t}\leftarrow
BFS(\text{ROOT}=t,\text{GRAPH}=G_{(s,t)},\text{DEPTH}=K//2)$;

;

/* Obtaining local structure of $s$ and $t$’ neighbor by breadth-first search
with depth $K//2$. */

3\. $E_{s}^{\text{hidden}}\leftarrow\\{e_{ij}|\forall\>v_{i}\in G_{s},v_{j}\in
G_{s},e_{ij}\in G_{(s,t)},e_{ij}\not\in G_{s}$};

4\. $E_{t}^{\text{hidden}}\leftarrow\\{e_{ij}|\forall\>v_{i}\in G_{t},v_{j}\in
G_{t},e_{ij}\in G_{(s,t)},e_{ij}\not\in G_{t}$};

;

/* For both subgraphs $G_{s}$ and $G_{t}$, we obtain hidden edges. */

5\. $V^{\text{cross}}\leftarrow V_{s}\cup V_{t}$;

;

/* Get common nodes shared by $G_{s}$ and $G_{t}$. */

6\. Initiate the document $d_{(i,j)}$ with an initial prompt:  ‘‘‘‘We have two
paragraphs that summarize the relation between $s$ and $t$...’’;

7\. for  _each node $v_{i}\in G_{s}$_ do

8\. Assign document sections (e.g., [Sec. 1.1]) following pre-order traversal
of $G_{s}$;

9\. Assign hidden edge following $E_{s}^{\text{hidden}}$ to $d_{(i,j)}$ ;

10\. for  _each node $v_{i}\in G_{t}$_ do

11\. Assign document sections (e.g., [Sec. 1.1]) following pre-order traversal
of $G_{t}$;

12\. Assign hidden edges following $E_{t}^{\text{hidden}}$ to $d_{(i,j)}$ ;

13\. Assign cross-paragraph reference $\forall\>v_{i}\in V^{\text{cross}}$;

Algorithm 1 Transition Document Composition

We provide the full procedure of producing the document $d_{(i,j)}$ based on
the node pair’s transition graph $G_{(s,t)}$ in Algorithm 1. From Line
$1$-$2$, we obtain the respective local structure of $s$ and $t$ based on
their transition graph $G_{(s,t)}$ by BFS search. From Line $3$-$4$, for both
$G_{s}$ and $G_{t}$, we extract hidden edges that are not covered in the BFS
tree. In Line $5$, we get the intersection of the node sets $V_{s}$ and
$V_{t}$ for recording the cross-paragraph nodes. Next, we initiate the
document with the initial prompt and traverse each node in $G_{s}$ and $G_{t}$
to assign document section indices and relations to the document. Finally, we
add hidden edges and cross-paragraph references as denoted in Line $12$-$13$.

###  A.2 Datasets

The statistics of the four datasets can be found in Table 4.

Table 4: Dataset Statistics

Dataset | # Node | # Edge
---|---|---
Goodreads-Children | 192,036 | 734,640
Goodreads-Crime | 385,203 | 1,849,236
Amazon-Apps | 100,468 | 752,937
Amazon-Movie | 173,986 | 1,697,533