# First characterization of the scattering length distribution of vector meson
interaction with deuteron

Xiao-Yun Wang<EMAIL_ADDRESS>Department of physics, Lanzhou University of
Technology, Lanzhou 730050, China  Lanzhou Center for Theoretical Physics, Key
Laboratory of Theoretical Physics of Gansu Province, Lanzhou University,
Lanzhou, Gansu 730000, China  Chen Dong<EMAIL_ADDRESS>Department of
physics, Lanzhou University of Technology, Lanzhou 730050, China  Quanjin Wang
Department of physics, Lanzhou University of Technology, Lanzhou 730050, China

###### Abstract

Under the framework of the vector meson dominance model (VMD), the absolute
scattering lengths of light vector mesons ($\phi$, $\omega$, and $\rho$) with
the deuteron are calculated from the cross sections of vector meson
photoproduction off a deuteron. Additionally, a fitting function is used to
predict the scattering lengths of the heavy vector mesons $J/\psi$-$d$ and
$\Upsilon$-$d$. Based on these results, the distribution of the scattering
lengths $|\alpha_{Vd}|$ between vector mesons and the deuteron is presented
for the first time and compared with the scattering lengths $|\alpha_{Vp}|$
between vector mesons and the proton. It is found that as the mass of the
vector meson increases, the scattering lengths $|\alpha_{Vd}|$ become closer
to $|\alpha_{Vp}|$. Finally, a preliminary analysis and interpretation of
these novel findings are provided based on the hadron size and the
embeddedness of mesons in the nucleus.

##  I Introduction

The photoproduction of electrically neutral vector mesons is a strong
diffraction process Aachen-Bonn-Hamburg-Heidelberg-Munich:1974olt , which is
similar to elastic scattering due to the same quantum number of incoming and
outgoing particles. The process has been fully interpreted through the vector
meson dominated model (VMD) Bauer:1977iq , which suggests that photons
fluctuate into virtual light vector mesons and then scatter elastically
through the target. The VMD model is not limited to investigating the
photoproduction of vector mesons from protons, but is also commonly used to
explore the photoproduction of vector mesons off a deuteron VMD ;
Rogers:2006ug ; Frankfurt:1997ss .

However, when the photon energy is close to the production threshold, the
pseudoscalar meson exchange of the $t$-channel can also produce corresponding
contributions Oh:2000pr , which complicates the investigation of
photoproduction dynamics of vector mesons on a proton target. Additionally,
the complexity at the threshold may result from $s$-channel nuclear resonance.
Therefore, the photoproduction of vector mesons off a deuteron can avoid this
complexity CLAS:2018avi . $\rho$ and $\omega$ are the most common light vector
mesons with a component quark mass of $m_{u}=m_{d}=330$ MeV Zhao:1998rt .
Investigating the reaction of deuterons to heavy vector mesons through the
scattering process of $\rho$ and $\omega$-deuteron interaction can be
enlightening.

The differential cross section of $\gamma d$$\rightarrow$$\rho d$ channel was
first measured by R. L. Anderson et al. in 1971 Anderson:1971ar . They
measured the differential cross section of $\rho$ photoproduction off a
deuteron at incident photon energies of $6$, $12$ and $18$ GeV using the SLAC
$1.6$ GeV/c spectrometer. Since $\rho$-$d$ can be treated as an elastic
scattering process, the authors used the Glauber theory Franco:1965wi ;
Harrington:1968sj  which can well describe $\pi$-$d$ scattering
Fellinger:1969cw ; Bradamante:1970fh  to study $\rho$-$d$. The result showed
that the Glauber theory can well describe the cross section of $\gamma
d$$\rightarrow$$\rho d$ channel in the small $t$ region. In 1974, P. Benz et
al. Aachen-Bonn-Hamburg-Heidelberg-Munich:1974olt  measured the cross section
of $\gamma d$$\rightarrow$$\rho d$ and $\gamma d$$\rightarrow$$\omega d$ in
the incident photon energy range of $1.00\sim 5.00$ GeV at DESY and presented
the effective mass distribution.

In 1997, the VMD model was used to study the photoproduction of vector mesons
at photon energies of $3\sim 30$GeV and to explore the space-time evolution of
small-size quark-gluon configurations Frankfurt:1997ss . This model predicted
the differential cross sections of $\rho$ photoproduction and
electroproduction off a deuteron at different energies. More recently, in
2018, the CLAS at Jefferson Lab CLAS:2018avi  measured a new set of $\omega$
photoproduction data off a deuteron at $E\in(1.4,3.4)$ GeV. Then in 2019, Ref.
Chetry:2019rpw  analyzed this data in detail and presented a new set of
$\rho$-$d$ differential cross sections at $E\in(1.4,3.4)$ GeV. These
experimental data provide a prerequisite for further investigation of the
vector meson-deuteron ($V$-$d$) interaction.

The absolute value of the scattering length characterizes the strength of the
$V$-$d$ interaction. The scattering length of vector meson-proton
$|\alpha_{Vp}|$ interactions has been extensively studied using VMD models
Wang:2022zwz ; Strakovsky:2014wja ; Strakovsky:2020uqs ; Titov:2007xb ;
Wang:2022tuc ; Pentchev:2020kao ; Wang:2022xpw ; Strakovsky:2021vyk . In
particular, it has been shown that the scattering length of $V$-$p$ exhibits
an inverse relationship with the mass (excluding $\rho$-$p$), which is
$|\alpha_{Vp}|$$\propto$$\exp{(\frac{1}{M_{V}})}$. While there is an existing
study Kolybasov:1972bn  that calculates the $\pi$-$d$ scattering length to be
$-0.047$ fm by summing the infinite series of non-relativistic Feynman graphs,
coherence studies on the scattering length of $V$-$d$ still need to be made
available. In our previous work Wang:2022tuc , we extracted the scattering
length of $\phi$-$d$ ($|\alpha_{\phi d}|$) to be $0.014\pm 0.002$ fm, which is
about seven times smaller than $|\alpha_{\phi p}|$. To further observe the
behavior of scattering lengths of different vector meson and deuteron
interactions, we aim to calculate the scattering length of more vector meson-
deuteron interactions using the VMD model.

In this study, we focus on calculating the scattering lengths of $\omega$ and
$\rho$ mesons interacting with the deuteron. To achieve this, we utilize the
considerable photoproduction cross sections of $\rho$-$d$ Chetry:2019rpw  and
$\omega$-$d$ CLAS:2018avi  that have been accumulated through experiments.
Furthermore, we also predict the scattering length of heavy vector mesons
($J/\psi$, $\Upsilon$) interacting with the deuteron. We discuss the
implications of our results based on the size of hadrons and the extent to
which they are embedded in the nucleus.

To provide a clear outline of our work, we first introduce the VMD model and
explain how it is used to associate the differential cross section of vector
meson with the scattering length in Section II. Subsequently, we calculate the
scattering lengths of $\omega$-$d$ and $\rho$-$d$ and present our predictions
for the $J/\psi$-$d$ and $\Upsilon$-$d$ scattering lengths. Finally, we
summarize our results briefly in Section III.

##  II The scattering length for light vector meson-deuteron interaction

The scattering of photons and deuterons is an essential photoproduction
process of vector mesons ($\omega$, $\rho$ and $\phi$). The VMD model VMD ;
Rogers:2006ug ; Frankfurt:1997ss  provides a unique method to investigate the
$\gamma d$$\rightarrow$$Vd$ channel, where $d$ represents the deuteron. In the
Ref. Titov:2007xb , the VMD model connects the differential cross-section of
$\gamma p$$\rightarrow$$Vp$ to the scattering length of vector meson-proton
($V$-$p$) interaction. Given the properties of the VMD model, which also can
be used to relate the $V$-$d$ interaction scattering length $|\alpha_{Vd}|$
with the differential cross section $d\sigma/dt$ of vector meson from the
deuteron at the near-threshold Titov:2007xb ,

$\left.\frac{d\sigma}{dt}\right|_{t=t_{thr}}=\frac{\pi^{2}\alpha_{em}}{g_{V}^{2}\left|\mathbf{{p}_{1}}\right|^{2}}\cdot\left|\alpha_{Vd}\right|^{2},$
(1)

where $\alpha_{em}$ is the fine coupling constant, $t_{thr}$ is the production
threshold of vector meson $t_{thr}=-M_{V}^{2}m_{d}/(M_{V}+m_{d})$ ($m_{d}$ is
the mass of the deuteron) and $g_{V}$ is the VMD coupling constant,

$g_{V}=\sqrt{\frac{\pi\alpha_{em}^{2}M_{V}}{3\Gamma_{e^{+}e^{-}}}}.$ (2)

$\Gamma_{e^{+}e^{-}}$ is the lepton decay width and $M_{V}$ is the meson mass.
In the Eq. (1), $|\mathbf{{p}_{1}|}$ is the initial momentum in the center of
mass frame,

$|\mathbf{{p}_{1}|=\frac{1}{2W}\sqrt{W^{4}-2(m_{1}^{2}+m_{2}^{2})W^{2}+(m_{1}^{2}-m_{2}^{2})^{2}}.}$
(3)

and $|\mathbf{{p}_{3}|}$ is the final momentum,

$|\mathbf{{p}_{3}|=\frac{1}{2W}\sqrt{W^{4}-2(m_{3}^{2}+m_{4}^{2})W^{2}+(m_{3}^{2}-m_{4}^{2})^{2}},}$
(4)

where $W$ is the center of mass energy.

We assume that $R=|\mathbf{{p}_{3}|/|{p}_{1}|}$, so the differential cross
section can be written as a function of $R$, and the relation between
scattering length $|\alpha_{Vd}|$ and differential cross section
$d\sigma/dt(R)$ can be rewritten as,

$|\alpha_{Vd}|=\frac{|\mathbf{{p}_{3}|g_{V}}}{R\pi}\sqrt{\frac{1}{\alpha_{em}}\frac{d\sigma}{dt}}.$
(5)

For $\rho$ mesons, the differential cross sections of $\gamma
d$$\rightarrow$$\rho d$ at $E\in[1.50,2.30]$ GeV ($W\in[3.02,3.49]$) involved
in the Ref. Chetry:2019rpw  are selected to extract the scattering length
$|\alpha_{\rho d}|$. The reason for choosing the interval is that it is
closest to the $\rho$ production threshold $W_{thr}=2.646$ GeV in the
available data. Here, the experimental data are fitted through a differential
form of an exponential function $d\sigma/dt=A\exp{(b(t-t_{thr}))}$
Pentchev:2020kao  to obtain the $d\sigma/dt|_{t=t_{thr}}$, where $A$ and $b$
are two free parameters. The relevant fitting results are presented in Fig. 1,
and the corresponding slopes $b$ and $d\sigma/dt|_{t=t_{thr}}$ for different
energies are shown in Tab. 1. With Eq. (5), we can calculate the scattering
length of $\rho$-d interaction.

Figure 1: The fitting results between the exponential function $d\sigma/dt$
and the experimental differential data Chetry:2019rpw  of $\rho$
photoproduction off a deuteron. Table 1: The $R$, $d\sigma/dt|_{t=t_{thr}}$,
slope $b$ and $|\alpha_{\rho d}|$ for different center of mass energies $W$.

W (GeV) | R |  $\frac{d\sigma}{dt}|_{t=t_{thr}}$ (nb/GeV2) |  $b$ (GeV-2) |  $|\alpha_{\rho d}|$ (fm)
---|---|---|---|---
$3.02$ | $0.73$ | $632.92$ | $2.53$ | $0.068\pm 0.007$
$3.15$ | $0.79$ | $405.41$ | $2.57$ | $0.060\pm 0.007$
$3.26$ | $0.82$ | $308.14$ | $2.60$ | $0.056\pm 0.007$
$3.38$ | $0.85$ | $247.92$ | $2.65$ | $0.053\pm 0.008$
$3.49$ | $0.87$ | $186.68$ | $2.92$ | $0.049\pm 0.008$

The $|\alpha_{\rho d}|$ at different $R$ is shown in Fig. 2 (the dark yellow
squares), which offers a decreasing trend as $R$ increases. However, this
downward trend is not a conclusive criterion and never indicates that the
scattering length of $\rho$-$d$ decreases with increasing energy. In order to
obtain an average calculated value, the root mean square (RMS) is calculated.
The cyan dashed line shows the RMS of these five values, which is calculated
as $\sqrt{\left\langle|\alpha^{2}_{\rho d}|\right\rangle}=0.058\pm 0.017$ fm.
The error band is the error that takes into account all the results.

Figure 2: The $|\alpha_{\rho d}|$ derived at different $R$. The cyan dashed
line is the RMS value $\sqrt{\left\langle|\alpha^{2}_{\rho
d}|\right\rangle}=0.058\pm 0.017$ fm. The differential cross section data of
$\rho$ photoproduction is from Ref. Chetry:2019rpw . The cyan error band is
the error band of $|\alpha_{\rho d}|$.

The differential cross sections of $\gamma d$$\rightarrow$$\omega d$ at
$E\in[1.6,3.1]$ GeV ($W\in[3.09,3.89]$ GeV) measured by CLAS at JLAB
CLAS:2018avi  can be used to extract $|\alpha_{\omega d}|$. The variation of
$|\alpha_{\omega d}|$ with $R$ directly extracted from the CLAS data
CLAS:2018avi  is shown in Fig. 3 (the olive green diamond), and the relevant
calculation results are listed in Tab. 2. An inspiring consequence is that the
$|\alpha_{\omega d}|$ tends to stabilize as $R$ increases. Furthermore, one
also calculates its RMS as $\sqrt{\left\langle|\alpha^{2}_{\omega
d}|\right\rangle}=0.052\pm 0.006$ fm, which is represented by the purple
double dot dash line in Fig. 3.

At present, we have calculated the absolute value of the scattering lengths of
$\rho$-$d$, $\omega$-$d$ and $\phi$-$d$. In order to explore the relation
between the mass of vector meson and $|\alpha_{Vd}|$, a fitting function is
obtained by the above results,

$|\alpha_{Vd}|=\exp{[-8.64+(4.45\pm 0.05)\frac{1}{M_{V}}]}.$ (6)

As shown in Fig .4, it is found that the scattering lengths $|\alpha_{Vd}|$
decreases as the mass of the vector meson increases. However, it should be
mentioned that we did not take the value of $|\alpha_{\rho d}|$ into account
when calculating the fitting function above. There are two main reasons, one
is because $|\alpha_{\rho d}|$ itself has a large error. Another reason is
that the width of $\rho$ is much larger than that of other vector mesons
ParticleDataGroup:2022pth , which also leads to inaccuracy in our calculation
of $\rho$-$N$ scattering length using VMD model Wang:2022zwz . It is only a
coincidence that the scattering lengths of $\rho$-$d$ and $\omega$-$d$ are
close at present, and more relevant discussions and modifications to the VMD
model will be continued in the future work.

Figure 3: The scattering length of $\omega$-$d$ interaction obtained from the
differential cross section of $\omega$ photoproduction off a deuteron
extracted from CLAS at JLAB CLAS:2018avi .The purple double dot dashed line is
the RMS value $\sqrt{\left\langle|\alpha^{2}_{\omega
d}|\right\rangle}=0.052\pm 0.006$ fm. The purple band represents the error bar
of $|\alpha_{\omega d}|$. Table 2: The $|\alpha_{\omega d}|$ is obtained from
the different center of mass energies $W$.

W (GeV) | $3.09$ | $3.32$ | $3.59$ | $3.89$
---|---|---|---|---
R | $0.76$ | $0.83$ | $0.88$ | $0.91$
$|\alpha_{\omega d}|$ (fm) | $0.053\pm 0.004$ | $0.051\pm 0.003$ | $0.052\pm 0.003$ | $0.054\pm 0.005$

Table 3: The experimentally measured the strong interaction and RMS radius of
partial hadrons Povh:1990ad ; Solovyev:2020ojc ; Klarsfeld:1986lmi .

State | strong interaction radius (fm) | root mean square radius (fm)
---|---|---
proton |  $0.82\pm 0.02$ Povh:1990ad  |  $0.83$ Solovyev:2020ojc
deuteron | - |  $1.953$ Klarsfeld:1986lmi
$\rho$ |  $0.72\pm 0.05$ Povh:1990ad  | -
$\omega$ |  $0.72\pm 0.05$ Povh:1990ad  | -
$\phi$ |  $0.46\pm 0.02$ Povh:1990ad  | -
$J/\psi$ |  $0.20\pm 0.02$ Povh:1990ad  | -

The $J/\psi$ and $\Upsilon$ are also two crucial vector mesons that have been
frequently analyzed. Especially $J/\psi$, as the most basic $c\bar{c}$ state,
investigating $J/\psi$-$d$ will lead to the more coherent development of
charmonium. With the fitted function Eq. (6), one should predict the
$|\alpha_{J/\psi d}|=0.743\pm 0.061$ am and $|\alpha_{\Upsilon d}|=0.284\pm
0.052$ am. Therefore, we can observe the scattering length distribution of the
interaction between vector meson and deuteron. The scattering length
$|\alpha_{Vp}|$ calculated by VMD model is recalled, and the results combined
with $\alpha_{Vd}$ are summarized in Fig. 5. There exist a realized phenomenon
that the $|\alpha_{Vd}|$ is almost an order of magnitude smaller when compared
with the scattering length of meson-proton $|\alpha_{Vp}|$. In addition, the
larger the mass of the vector meson, the scattering length $|\alpha_{Vd}|$ is
closer to the $|\alpha_{Vp}|$ and the smaller the difference.

The scattering length calculated by the VMD model is supposed as the process
by which vector mesons are embedded into nucleons or nuclei in physics. The
difference in the radius of the hadron involved in the interaction will
influence the depth and degree of embedding. So these phenomena can be
comprehended in terms of the radius of the hadron. The radius of the strong
interaction and RMS for the different hadron states measured from the
experiment Povh:1990ad ; Solovyev:2020ojc ; Klarsfeld:1986lmi  is listed in
Tab. 3, which indicates that the larger the mass of the vector meson, the
smaller the radius. Fig. 6 (a) clearly displays the sizing diagram of vector
mesons and deuteron based on the proton radius. Fig. 6 (b) display the
interaction diagram of $\omega$-$N$ and $J/\psi$-$N$, where $N$ represents
nucleon or deuteron. The radius of the deuteron is about $2.6$ times larger
than that of the proton, the $\omega$ and $J/\psi$ are more fully embedded
into the deuteron, so the scattering lengths of $\omega$-$d$ and $J/\psi$-$d$
are smaller than that of $\omega$-$p$ and $J/\psi$-$p$. The radius of $J/\psi$
is less than that of $\omega$, so the degree of embedding of $J/\psi$ into the
proton is close to that of the deuteron, and $|\alpha_{J/\psi d}|$ is closer
to $|\alpha_{J/\psi p}|$.

Figure 4: The scattering length of vector mesons and deuteron interaction
derived by VMD model. The orange circle is the scattering length of $\phi$-$d$
taken from our previous work Wang:2022tuc . The olive green diamond and the
dark yellow square are the result of $|\alpha_{\omega d}|$ and $|\alpha_{\rho
d}|$, respectively.

##  III Summary

Figure 5: The scattering length of $V$-$d$ interaction obtained by VMD. The
burgundy circles for $|\alpha_{\Upsilon p}|$, $|\alpha_{\alpha_{\phi p}}|$ and
$|\alpha_{\omega p}|$ are taken from Igor’s work Strakovsky:2020uqs ;
Strakovsky:2014wja ; Strakovsky:2021vyk . The result for $|\alpha_{\phi p}|$
represented by the cyan pentagram is received from Ref. Chang:2007fc . The
notations for $|\alpha_{\rho d}|$, $|\alpha_{\omega d}|$ and $|\alpha_{\phi
d}|$ are the same as in Fig. 4. The two black diamonds and purple square are
derived from our previous work Wang:2022zwz ; Wang:2022xpw ; Wang:2022tuc .
And the two blue triangles are the predicted $|\alpha_{\Upsilon d}|$ and
$|\alpha_{J/\psi d}|$.

In this work, the scattering lengths of $\rho$-$d$, $\omega$-$d$ and
$\rho$-$d$ interaction are investigated under the guidance of the VMD model.
Then, the $|\alpha_{J/\psi d}|$ and $|\alpha_{\Upsilon d}|$ are predicted by a
function which is fitted by the result of $|\alpha_{\omega d}|$ and
$|\alpha_{\phi d}|$, and the distribution behaviour of the scattering length
of the interaction between vector meson and deuteron is given for the first
time. A few interesting phenomena are discovered by comparing the scattering
lengths of $V$-$p$ and $V$-$d$ interactions.

One find that the larger radius of the deuteron compared to the proton leads
to a more complete embedding of vector mesons into the deuteron, resulting in
smaller scattering lengths for $V$-$d$ interactions than $V$-$p$ interactions.
Additionally, we observe that the scattering length $|\alpha_{Vd}|$ approaches
$|\alpha_{Vp}|$ as the radius of the vector meson decreases. These results
suggest that the scattering length between two states may be related to their
relative size and embedding degree with each other. For example, since the
size of $\pi$ meson is smaller than that of $\omega$ meson, the degree of
$\pi$ meson embedding in deuteron may be deeper than that of $\omega$ meson,
which may result in a smaller scattering length for $\pi$-$d$ interactions
than for $\omega$-$d$ interactions. This is consistent with a previous
calculation of $|\alpha_{\pi d}|=0.047$ fm Kolybasov:1972bn  using non-
relativistic Feynman graphs, which is smaller than $|\alpha_{\omega d}|$.

Furthermore, considering the fact that the scattering length between heavy
vector mesons and nucleus is smaller than that between light vector mesons and
nucleus, does this also imply that the embedding degree between heavy vector
mesons and nucleus is higher, making it easier to form $J/\psi N$ or $\Upsilon
N$ combination of pentaquark states LHCb:2015yax ; LHCb:2019kea ; Wang:2019krd
; Wang:2019zaw  or molecular states? Therefore, we suggest that experiments
can strengthen research in this area, such as studying the production of
pentaquark states in the heavy quark energy region through hadron-hadron
scattering Wang:2019dsi , which can effectively avoid the influence of
kinematic singularities in the process of pentaquark states production through
heavy hadron decay. Our study on the scattering length between vector mesons
and nucleus may provide useful theoretical references for better understanding
the production of pentaquark states or the binding energy in molecular states
Kaidalov:1992hd .

Overall, this work may provide an important insights into the interaction of
vector mesons with nucleons or nucleus. However, the lack of experimental data
limits our ability to draw definitive conclusions, and additional experimental
data on the $\gamma d$$\rightarrow$$Vd$ scattering cross section is needed to
further refine our understanding of this process.

Figure 6: On the left is a simple diagram of several hadrons. The circles of
blue, cyan, green, yellow, purple, and orange represent the deuteron, proton,
$\rho$, $\omega$, $\phi$, and $J/\psi$, respectively. On the right are graphs
of $\omega$ and $J/\psi$ interacting with the proton and deuteron.

###### Acknowledgements.

This work is supported by the National Natural Science Foundation of China
under Grants No. 12065014 and No. 12047501, and by the Natural Science
Foundation of Gansu province under Grant No. 22JR5RA266. We acknowledge the
West Light Foundation of The Chinese Academy of Sciences, Grant No.
21JR7RA201.

## References

  * (1) P. Benz et al. [Aachen-Bonn-Hamburg-Heidelberg-Munich], “Photoproduction of $\rho^{0}$, $\omega$ and $\rho^{-}$ mesons on deuterons at energies between $1$ and $5$ GeV,” Nucl. Phys. B 79, 10-37 (1974).
  * (2) T. H. Bauer, R. D. Spital, D. R. Yennie and F. M. Pipkin, “The Hadronic Properties of the Photon in High-Energy Interactions,” Rev. Mod. Phys. 50, 261 (1978) [erratum: Rev. Mod. Phys. 51, 407 (1979)].
  * (3) Eisenberg, Y. and Haber, B. and Kogan, E. and Ronat, E. E. and Shapira, A. and Yekutieli, G. “Photoproduction of $\rho^{0}$ and $\omega$ in $\gamma d$ interactions at 4.3 GEV,” Nuclear Physics B42 (1972) 349-368.
  * (4) T. C. Rogers, “Vector meson production and the dipole picture in photon-hadron scattering,” UMI-32-31884.
  * (5) L. Frankfurt, W. Koepf, J. Mutzbauer, G. Piller, M. Sargsian and M. Strikman, “Coherent photoproduction and leptoproduction of vector mesons from deuterium,” Nucl. Phys. A 622, 511-537 (1997).
  * (6) Y. S. Oh, A. I. Titov and T. S. H. Lee, “Electromagnetic production of vector mesons at low-energies,” [arXiv:nucl-th/0004055 [nucl-th]].
  * (7) T. Chetry et al. [CLAS], “Differential cross section for $\gamma d\rightarrow\omega d$ using CLAS at Jefferson Lab,” Phys. Lett. B 782, 646-651 (2018).
  * (8) Q. Zhao, Z. P. Li and C. Bennhold, “Omega and rho photoproduction with an effective quark model Lagrangian,” Phys. Lett. B 436, 42-48 (1998).
  * (9) R. L. Anderson, D. Gustavson, J. R. Johnson, I. Overman, D. Ritson, B. H. Wiik, R. Talman and D. Worcester, “A determination of the $\rho$-nucleon cross-section from elastic $\rho$ photoproduction on deuterium,” Phys. Rev. D 4, 3245 (1971).
  * (10) V. Franco and R. J. Glauber, “High-energy deuteron cross-sections,” Phys. Rev. 142, 1195-1214 (1966).
  * (11) D. R. Harrington, “D-wave effects in high-energy proton-deuteron scattering,” Phys. Rev. Lett. 21, 1496-1498 (1968).
  * (12) F. Bradamante, G. Fidecaro, M. Fidecaro, M. Giorgi, P. Palazzi, A. Penzo, L. Piemontese, F. Sauli, P. Schiavon and A. Vascotto, “Pion-deuteron coherent scattering at high-energy,” Phys. Lett. B 31, 87-92 (1970).
  * (13) M. Fellinger, E. Gutman, R. C. Lamb, F. C. Peterson, L. S. Schroeder, R. C. Chase, E. Coleman and T. G. Rhoades, “Elastic scattering of negative pions from deuterons at 2.01, 3.77, and 5.53 Gev/c,” Phys. Rev. Lett. 22, 1265-1269 (1969).
  * (14) T. Chetry, “A Study of the Reaction $\gamma d\rightarrow\pi^{+}\pi^{-}d$ (From Vector Mesons to Possible Dibaryons),” doi:10.2172/1498990.
  * (15) X. Y. Wang, F. Zeng, Q. Wang and L. Zhang, “First extraction of the proton mass radius and scattering length $|\alpha_{\rho^{0}p}|$ from $\rho$0 photoproduction,” Sci. China Phys. Mech. Astron. 66, 232012 (2023).
  * (16) I. I. Strakovsky, S. Prakhov, Y. I. Azimov, P. Aguar-Bartolomé, J. R. M. Annand, H. J. Arends, K. Bantawa, R. Beck, V. Bekrenev and H. Berghäuser, et al. “Photoproduction of the $\omega$ meson on the proton near threshold,” Phys. Rev. C 91, 045207 (2015).
  * (17) A. I. Titov, T. Nakano, S. Date and Y. Ohashi, “Comments on differential cross-section of phi-meson photoproduction at threshold,” Phys. Rev. C 76, 048202 (2007).
  * (18) X. Y. Wang, C. Dong and Q. Wang, “Analysis of the interaction between of $\phi$ meson and nucleus,” Chin. Phys. C 47, 014106 (2023).
  * (19) I. I. Strakovsky, L. Pentchev and A. Titov, “Comparative analysis of $\omega p$, $\phi p$, and $J/\psi p$ scattering lengths from A2, CLAS, and GlueX threshold measurements,” Phys. Rev. C 101, 045201 (2020).
  * (20) X. Y. Wang, F. Zeng and I. I. Strakovsky, “$\psi$(*)p scattering length based on near-threshold charmonium photoproduction,” Phys. Rev. C 106, 015202 (2022).
  * (21) L. Pentchev and I. I. Strakovsky, “$J/\psi$-$p$ Scattering Length from the Total and Differential Photoproduction Cross Sections,” Eur. Phys. J. A 57, 56 (2021).
  * (22) I. I. Strakovsky, W. J. Briscoe, L. Pentchev and A. Schmidt, “Threshold $\Upsilon$-meson photoproduction at the EIC and EicC,” Phys. Rev. D 104, 074028 (2021).
  * (23) V. M. Kolybasov and A. E. Kudryavtsev, “Pion-deuteron scattering length,” Nucl. Phys. B 41, 510-524 (1972).
  * (24) R. L. Workman et al. [Particle Data Group], “Review of Particle Physics,” PTEP 2022, 083C01 (2022).
  * (25) B. Povh and J. Hufner, “Systematics of strong interaction radii for hadrons,” Phys. Lett. B 245, 653-657 (1990).
  * (26) D. Solovyev, T. Zalialiutdinov and A. Anikin, “Proton size from precision experiments on hydrogen and muonic hydrogen atoms,” [arXiv:2009.11520 [physics.atom-ph]].
  * (27) S. Klarsfeld, J. Martorell, J. A. Oteo, M. Nishimura and D. W. L. Sprung, “Determination of the deuteron mean square radius,” Nucl. Phys. A 456, 373-396 (1986).
  * (28) W. C. Chang, K. Horie, S. Shimizu, M. Miyabe, D. S. Ahn, J. K. Ahn, H. Akimune, Y. Asano, S. Date and H. Ejiri, et al. “Forward coherent $\phi$-meson photoproduction from deuterons near threshold,” Phys. Lett. B 658, 209-215 (2008).
  * (29) R. Aaij et al. [LHCb], “Observation of $J/\psi p$ Resonances Consistent with Pentaquark States in $\Lambda_{b}^{0}\to J/\psi K^{-}p$ Decays,” Phys. Rev. Lett. 115, 072001 (2015).
  * (30) R. Aaij et al. [LHCb], “Observation of a narrow pentaquark state, $P_{c}(4312)^{+}$, and of two-peak structure of the $P_{c}(4450)^{+}$,” Phys. Rev. Lett. 122, 222001 (2019).
  * (31) X. Y. Wang, X. R. Chen and J. He, “Possibility to study pentaquark states $P_{c}(4312),P_{c}(4440)$, and $P_{c}(4457)$ in $\gamma p\rightarrow J/\psi p$ reaction,” Phys. Rev. D 99, 114007 (2019).
  * (32) X. Y. Wang, J. He and X. Chen, “Systematic study of the production of hidden-bottom pentaquarks via $\gamma p$ and $\pi^{-}p$ scatterings,” Phys. Rev. D 101, no.3, 034032 (2020)
  * (33) X. Y. Wang, J. He, X. R. Chen, Q. Wang and X. Zhu, “Pion-induced production of hidden-charm pentaquarks $P_{c}(4312),P_{c}(4440)$, and $P_{c}(4457)$,” Phys. Lett. B 797, 134862 (2019).
  * (34) A. B. Kaidalov and P. E. Volkovitsky, “Heavy quarkonia interactions with nucleons and nuclei,” Phys. Rev. Lett. 69, 3155-3156 (1992).


# GREASE: A Generative Model for Relevance Search over Knowledge Graphs

Tianshuo Zhou  National Key Laboratory for Novel Software Technology, Nanjing
University, China<EMAIL_ADDRESS>,  Ziyang Li  National Key
Laboratory for Novel Software Technology, Nanjing University, China
<EMAIL_ADDRESS>,  Gong Cheng  National Key Laboratory for Novel
Software Technology, Nanjing University, China<EMAIL_ADDRESS>,  Jun Wang
Department of Computer Science, University College London, UK
<EMAIL_ADDRESS>and  Yu’Ang Wei  National Key Laboratory for Novel
Software Technology, Nanjing University, China<EMAIL_ADDRESS>
(2020)

###### Abstract.

Relevance search is to find top-ranked entities in a knowledge graph (KG) that
are relevant to a query entity. Relevance is ambiguous, particularly over a
schema-rich KG like DBpedia which supports a wide range of different semantics
of relevance based on numerous types of relations and attributes. As users may
lack the expertise to formalize the desired semantics, supervised methods have
emerged to learn the hidden user-defined relevance from user-provided
examples. Along this line, in this paper we propose a novel generative model
over KGs for relevance search, named GREASE. The model applies to meta-path
based relevance where a meta-path characterizes a particular type of semantics
of relating the query entity to answer entities. It is also extended to
support properties that constrain answer entities. Extensive experiments on
two large-scale KGs demonstrate that GREASE has advanced the state of the art
in effectiveness, expressiveness, and efficiency.

††copyright: none††copyright: acmlicensed††journalyear: 2020††doi:
10.1145/1122445.1122456††conference: WSDM ’20: ACM International Conference on
Web Search and Data Mining; February 03–07, 2020; Houston, TX††booktitle: WSDM
’20: ACM International Conference on Web Search and Data Mining, February
03–07, 2020, Houston, TX††price: 15.00††isbn: 978-1-4503-9999-9/18/06

##  1\. Introduction

Background. In a knowledge graph (KG), nodes are entities associated with
attributes and interconnected with binary relations as edges. Increasingly
many KGs have emerged for various domains, some available as Linked Open Data.
KGs for a focused domain often have a simple schema, e.g., the LinkedIn
KG111https://www.linkedin.com/pulse/machine-learning-linkedin-knowledge-graph-
qi-he/ describes members, companies, and other entities in the professional
domain. There are also generic KGs providing encyclopedic knowledge and hence
having a rich schema consisting of thousands of types of relations and
attributes, such as DBpedia (Lehmann et al., 2015). We illustrate a KG in Fig.
1 as the running example in this paper. It describes movies, their actors and
directors, and awards.

Figure 1. An example of a knowledge graph, where each entity is associated
with a bulleted set of attributes.

An established data mining task for KG-based applications is _relevance
search_ (Lao and Cohen, 2010; Backstrom and Leskovec, 2011; Sun et al., 2011b;
Shi et al., 2012; Yu et al., 2012; Meng et al., 2015; Xiong et al., 2015; Wang
et al., 2016; Fang et al., 2016; Huang et al., 2016; Shi et al., 2017; Gu et
al., 2019). The task is essentially to find entities in a KG that are the most
relevant to an input query entity. However, relevance has a broad range of
meanings, particularly over a schema-rich KG. For example, given Tom Hardy as
the query entity, the user may search for actresses that co-starred with him,
or for American directors that collaborated with him. Unfortunately, non-
expert users lack the expertise to formally characterize the desired semantics
of relevance because the formal query language and the rich schema of the KG
are both difficult to learn.

Problem. To bridge the gap between non-expert users and structured KGs, one
practical solution is to request a small number of examples from the user, and
then to _learn user-defined relevance from user-provided examples_ (Lao and
Cohen, 2010; Backstrom and Leskovec, 2011; Yu et al., 2012; Bu et al., 2014;
Meng et al., 2015; Wang et al., 2016; Fang et al., 2016; Gu et al., 2019). The
user can specify an example in the form of an ordered _query-answer entity
pair_ to illustrate the desired semantics of relevance (Lao and Cohen, 2010;
Meng et al., 2015; Wang et al., 2016). For example, two different users may
provide different sets of examples:

(1) $\begin{split}S_{1}=\\{&\langle\texttt{Dave Chappelle},~{}\texttt{Lady
Gaga}\rangle,\\\ &\langle\texttt{Matt Damon},~{}\texttt{Julia
Roberts}\rangle\\}\,,\\\ S_{2}=\\{&\langle\texttt{Dave
Chappelle},~{}\texttt{Bradley Cooper}\rangle,\\\ &\langle\texttt{Matt
Damon},~{}\texttt{George Clooney}\rangle\\}\,.\end{split}$

The user providing $S_{1}$ aims to find entities that are relevant to Tom
Hardy _just as how_ Lady Gaga is relevant to Dave Chappelle and as how Julia
Roberts is relevant to Matt Damon. The underlying semantics could be
actors—preferably American actresses—that co-starred with Tom Hardy. In this
case, Marion Cotillard and Leonardo DiCaprio are acceptable answers. The user
providing $S_{2}$ has a different need and is looking for American male
directors and/or actors that collaborated with Tom Hardy. Now, Leonardo
DiCaprio and Christopher Nolan become good answers.

Challenges. It has been common to assume that the user-defined relevance can
be represented by one or more _meta-paths_ (Lao and Cohen, 2010; Sun et al.,
2011b; Yu et al., 2012; Bu et al., 2014; Meng et al., 2015; Wang et al., 2016;
Shi et al., 2017; Gu et al., 2019). A meta-path is a sequence of relation
types, i.e., a path at the schema level. For example, the co-starring relation
underlying $S_{1}$ is characterized by the following meta-path:

(2)
$\mathcal{P}_{1}:~{}\texttt{[query]}\xleftarrow{\texttt{stars}}\cdot\xrightarrow{\texttt{stars}}\texttt{[answer]}\,.$

The collaboration relation underlying $S_{2}$ is characterized partially by
$\mathcal{P}_{1}$ and partially by

(3)
$\mathcal{P}_{2}:~{}\texttt{[query]}\xleftarrow{\texttt{stars}}\cdot\xrightarrow{\texttt{director}}\texttt{[answer]}\,.$

The key challenge to these methods is the selection and weighting of meta-
paths. Existing methods train discriminative models to directly learn the
weights of meta-paths from user-provided examples (Lao and Cohen, 2010; Yu et
al., 2012; Bu et al., 2014; Meng et al., 2015; Wang et al., 2016; Gu et al.,
2019), but have exhibited the following limitations.

  * •

Their _discriminative models_ rely on negative examples that are sampled
automatically as the user only provides positive examples. Identifying high-
quality negative examples is algorithmically challenging and computationally
demanding.

  * •

They are focused on meta-path based relevance, but cannot support the
representation of _properties_ , such as gender and nationality in the above
example. Their capability of characterizing user needs is somewhat limited.

Contributions. In this work we address the two challenges and propose GREASE,
a novel Generative model for RelEvAnce SEarch over KGs. Our implementation has
been open source.222http://ws.nju.edu.cn/relevance/grease/ Our contributions
are summarized as follows.

  * •

We treat the weight of a meta-path as a posterior probability, and devise a
_generative model_ with cost-effective approximations. Our model does not rely
on negative examples, and has outperformed existing methods in both
effectiveness and efficiency in the experiments.

  * •

We extend the model to support not only meta-path based relevance of answer
entities to the query entity, but also _properties that constrain answer
entities_. The extension allows to represent more expressive user-defined
relevance.

Organization. We formulate the problem in Section 2. Our generative model is
described in Section 3, and is extended to support properties in Section 4.
Based on that, our search algorithm is given in Section 5. We report
experiments in Section 6, compare related work in Section 7, and finally
conclude the paper in Section 8.

##  2\. Problem Formulation

Let $\mathbb{R}$ denote the set of all real numbers. We assume countable
pairwise disjoint sets of entities $\mathcal{V}$, relation types
$\mathcal{R}$, attribute types $\mathcal{A}$, and attribute values
$\mathcal{L}$.

###### Definition 2.1 (Knowledge Graph).

A knowledge graph (KG) is a directed graph denoted by $G=\langle
V,E,\Psi\rangle$, where

  * •

$V\subseteq\mathcal{V}$ is a finite set of entities represented as nodes,

  * •

$E\subseteq V\times\mathcal{R}\times V$ is a finite set of relations between
entities represented as directed edges, and

  * •

$\Psi:V\mapsto\mathtt{P}(\mathcal{A}\times\mathcal{L})$, where
$\mathtt{P}(\cdot)$ represents power set, is a function that associates each
entity $v\in V$ with a finite set of attributes
$\Psi(v)\subseteq\mathcal{A}\times\mathcal{L}$.

For an entity $v\in V$, its _properties_ consist of

(4) $\Phi(v)=\\{\langle a,l\rangle:\langle a,l\rangle\in\Psi(v)\text{ or
}\langle v,a,l\rangle\in E\\}\,.$

For example, in Fig. 1, the properties of Suburbicon consist of an attribute
$\langle\texttt{genre},~{}\texttt{Comedy}\rangle$ and two relations
$\langle\texttt{stars},~{}\texttt{Matt Dameon}\rangle$ and
$\langle\texttt{director},~{}\texttt{George Clooney}\rangle$.

We define _path_ in a standard way. It is acyclic, and its edges are not
required to follow the same direction. However, in the remainder of the paper
we always write right arrows and rewrite left arrow $\xleftarrow{r}$ as
$\xrightarrow{r^{-1}}$, where $r^{-1}$ represents the inverse of
$r\in\mathcal{R}$. We write a path
$p:v_{0}\xrightarrow{r_{1}}v_{1}\xrightarrow{r_{2}}\cdots\xrightarrow{r_{l}}v_{l}$
from $v_{0}$ to $v_{l}$ as $v_{0}\rightsquigarrow_{p}v_{l}$ for short. The
length of a path is the number of its edges.

###### Definition 2.2 (Meta-Path).

A meta-path is a sequence of relation types $\mathcal{P}:r_{1}r_{2}\cdots
r_{l}$, where $r_{1},\ldots,r_{l}\in\mathcal{R}$ are relation types (or their
inverses), and $l$ is called the length of $\mathcal{P}$ denoted by
$\mathtt{len}(\mathcal{P})=l$. A path $p$ in a KG follows $\mathcal{P}$,
denoted by $p\models\mathcal{P}$, if $p$ is in the form of
$p:v_{0}\xrightarrow{r_{1}}v_{1}\xrightarrow{r_{2}}\cdots\xrightarrow{r_{l}}v_{l}$.

For example, the two meta-paths shown in Eq. (2) and Eq. (3) are formalized as
follows:

(5)
$\mathcal{P}_{1}:\texttt{stars}^{-1}~{}\texttt{stars}\,,\qquad\mathcal{P}_{2}:\texttt{stars}^{-1}~{}\texttt{director}\,.$

Their lengths are both 2. $\mathcal{P}_{2}$ is followed by path

(6)

$\texttt{Tom
Hardy}\xrightarrow{\texttt{stars}^{-1}}\texttt{Inception}\xrightarrow{\texttt{director}}\texttt{Christopher
Nolan}\,.$

###### Definition 2.3 (Relevance Search).

Given a KG denoted by $G=\langle V,E,\Phi\rangle$, let
$\mathtt{rel}:\mathcal{V}\times\mathcal{V}\mapsto\mathbb{R}$ be a user-defined
real-valued function. For $u,v\in V$, $\mathtt{rel}(u,v)$ returns the
relevance of $v$ to $u$. Let $k<|V|$ be a predetermined positive integer. For
an input query entity $q\in V$, relevance search is to find top-$k$ answer
entities $\mathtt{Ans}(q)\subseteq(V\setminus\\{q\\})$ that are the most
relevant to $q$ in terms of $\mathtt{rel}$.

Following (Lao and Cohen, 2010; Meng et al., 2015; Wang et al., 2016), we
assume the user provides a small number of ordered query-answer entity pairs
as _examples_ , to exemplify the desired $\mathtt{rel}$ which is not directly
accessible to the search system.

###### Definition 2.4 (Relevance Search by Example).

Extending Definition 2.3, the problem turns into learning a function
$\mathtt{rel}$ under the supervision of a set of user-provided examples
denoted by $S$. Each example is an ordered query-answer entity pair $\langle
s,t\rangle\in V\times V$, where $s$ is called the source entity and $t$ is the
target entity, such that $v\in\mathtt{Ans}(q)$ is relevant to $q$ just as how
$t$ is relevant to $s$.

For example, $S_{1}$ and $S_{2}$ in Eq. (1) are two sets of examples for the
query entity Tom Hardy. They indicate different $\mathtt{rel}$ functions.

##  3\. Generative Relevance Model

Following Definition 2.4, the $\mathtt{rel}$ function is conditioned on a set
of user-provided examples $S$, so we rewrite $\mathtt{rel}(q,v)$ as
$\mathtt{rel}(q,v|S)$. Previous research computes meta-path based relevance
(Lao and Cohen, 2010; Sun et al., 2011b; Yu et al., 2012; Bu et al., 2014;
Meng et al., 2015; Wang et al., 2016; Shi et al., 2017; Gu et al., 2019).
Along this line, we decompose $\mathtt{rel}$ into a linear combination of
weighted relevance over a set of meta-paths denoted by
$\boldsymbol{\Omega}_{\text{mp}}=\\{\mathcal{P}_{1},\ldots,\mathcal{P}_{n}\\}$:

(7)
$\mathtt{rel}(q,v|S)=\sum_{\mathcal{P}_{i}\in\boldsymbol{\Omega}_{\text{mp}}}{\gamma(q,v|\mathcal{P}_{i})\cdot\mathtt{Pr}(\mathcal{P}_{i}|S)\cdot\mathtt{J}(\mathcal{P}_{i})}\,,$

where $\gamma(q,v|\mathcal{P}_{i})$ measures the real-valued relevance of $v$
to $q$ w.r.t. a particular meta-path $\mathcal{P}_{i}$,
$\mathtt{Pr}(\mathcal{P}_{i}|S)$ represents the weight of $\mathcal{P}_{i}$,
and $\mathtt{J}(\mathcal{P}_{i})$ is a regularization term to prevent
overfitting. Meta-paths and their weights are to be learned from $S$. For
example, with $S_{1}$ in Eq. (1), the meta-path $\mathcal{P}_{1}$ in Eq. (5)
should have a large weight because for every example in $S_{1}$, there exists
a path in Fig. 1 that follows $\mathcal{P}_{1}$ and connects the source entity
to the target entity.

To establish $\mathtt{rel}$, below we describe the selection of
$\boldsymbol{\Omega}_{\text{mp}}$, and the computation of $\gamma$,
$\mathtt{Pr}$, and $\mathtt{J}$.

###  3.1. Meta-Path Selection

As $\mathtt{rel}$ is exemplified by $S$, we select
$\boldsymbol{\Omega}_{\text{mp}}$ based on $S$. Our
$\boldsymbol{\Omega}_{\text{mp}}$ contains all possible meta-paths that can be
derived from $S$. A meta-path $\mathcal{P}_{i}$ is in
$\boldsymbol{\Omega}_{\text{mp}}$ if there exists a path in the KG such that
it follows $\mathcal{P}_{i}$ and it connects the source entity to the target
entity in some user-provided example:

(8) $\boldsymbol{\Omega}_{\text{mp}}=\bigcup_{\langle s,t\rangle\in
S}{\\{\mathcal{P}:\exists
p\models\mathcal{P},~{}s\rightsquigarrow_{p}t\\}}\,.$

###  3.2. Meta-Path Based Relevance

Extensive research has been conducted to measure the relevance of $v$ to $q$
w.r.t. a particular meta-path $\mathcal{P}_{i}$ (Sun et al., 2011a; Lao and
Cohen, 2010; Sun et al., 2011b; Xiong et al., 2015; Shi et al., 2012). This is
outside the focus of this paper, and we extend _path count_ (Sun et al.,
2011a) as our measure:

(9)
$\begin{split}\gamma(q,v|\mathcal{P}_{i})&=\min\\{\mathtt{pc}(q,v,\mathcal{P}_{i}),~{}\alpha_{\text{mp}}\\}\,,\\\
\mathtt{pc}(q,v,\mathcal{P}_{i})&=|\\{p:p\models\mathcal{P}_{i}\text{ and
}q\rightsquigarrow_{p}v\\}|\,,\end{split}$

where $\mathtt{pc}(q,v,\mathcal{P}_{i})$ represents the number of paths in the
KG that follow $\mathcal{P}_{i}$ and connect $q$ to $v$, and
$\alpha_{\text{mp}}>0$ is a parameter to limit the value of $\mathtt{pc}$ and
prevent highly skewed values. For example, in Fig. 1, for $\mathcal{P}_{2}$ in
Eq. (5) we have

(10) $\mathtt{pc}(\texttt{Tom Hardy},~{}\texttt{Christopher
Nolan},~{}\mathcal{P}_{2})=1\,,$

because there is only one path shown in Eq. (6) that follows $\mathcal{P}_{2}$
and connects Tom Hardy to Christopher Nolan.

###  3.3. Generative Meta-Path Weighting

Weighting scheme is the key to the effectiveness of the $\mathtt{rel}$
function, and is the focus of our work. Different from existing discriminative
methods (Lao and Cohen, 2010; Yu et al., 2012; Bu et al., 2014; Meng et al.,
2015; Wang et al., 2016; Gu et al., 2019), we treat weight
$\mathtt{Pr}(\mathcal{P}_{i}|S)$ as a posterior probability and propose a
novel _generative model_. In the following, we will also use
$\mathtt{Pr}(\cdot)$ to denote the probability of an event. We estimate
probabilities based on the KG and learn $\mathtt{Pr}(\mathcal{P}_{i}|S)$ from
$S$.

Specifically, we rewrite $\mathtt{Pr}(\mathcal{P}_{i}|S)$ using Bayes’
theorem:

(11)
$\begin{split}\mathtt{Pr}(\mathcal{P}_{i}|S)&=\frac{\mathtt{Pr}(\mathcal{P}_{i})\cdot\mathtt{Pr}(S|\mathcal{P}_{i})}{\mathtt{Pr}(S)}\propto\mathtt{Pr}(\mathcal{P}_{i})\cdot\mathtt{Pr}(S|\mathcal{P}_{i})\,,\end{split}$

where the posterior $\mathtt{Pr}(\mathcal{P}_{i}|S)$ is proportional to the
prior $\mathtt{Pr}(\mathcal{P}_{i})$ times the likelihood
$\mathtt{Pr}(S|\mathcal{P}_{i})$. Below we separately compute the prior and
the likelihood.

Computation of the Prior. For the prior $\mathtt{Pr}(\mathcal{P}_{i})$, recall
that a meta-path is a sequence of relation types
$\mathcal{P}_{i}:r_{1}r_{2}\cdots r_{l}$. We assume the probability of
observing the $i$-th relation type $r_{i}$ in the context history of the
preceding $(i-1)$ relation types $r_{1}r_{2}\cdots r_{i-1}$ can be
approximated by the probability of observing it in the shortened context
history of the preceding relation type $r_{i-1}$, i.e., the _first-order
Markov property_. This assumption is reasonable and also common on graphs.
Specifically, random walks on graphs satisfy this property. Formally, we have

(12) $\begin{split}\mathtt{Pr}(\mathcal{P}_{i})&=\mathtt{Pr}(r_{1}r_{2}\cdots
r_{l})=\mathtt{Pr}(r_{1})\prod_{i=2}^{l}{\mathtt{Pr}(r_{i}|r_{1}r_{2}\cdots
r_{i-1})}\\\
&\approx\mathtt{Pr}(r_{1})\prod_{i=2}^{l}{\mathtt{Pr}(r_{i}|r_{i-1})}\,,\end{split}$

which in turn will give rise to the following estimation of
$\mathtt{Pr}(\mathcal{P}_{i})$ if we estimate $\mathtt{Pr}(r_{1})$ and
$\mathtt{Pr}(r_{i}|r_{i-1})$ from frequency counts:

(13)
$\mathtt{Pr}(\mathcal{P}_{i})\propto\mathtt{pc}(r_{1})\prod_{i=2}^{l}{\frac{\mathtt{pc}(r_{i-1}r_{i})}{\mathtt{pc}(r_{i-1})}}\,,$

where $\mathtt{pc}(\mathcal{P})$ represents the number of paths in the KG that
follow meta-path $\mathcal{P}$:

(14) $\mathtt{pc}(\mathcal{P})=|\\{p:p\models\mathcal{P}\\}|\,.$

In Eq. (13), computing $\mathtt{pc}$ according to Eq. (14) is inexpensive
because those meta-paths are very short, being not longer than 2. For example,
in Fig. 1, for $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ in Eq. (5) we have

(15)
$\mathtt{pc}(\mathcal{P}_{1})=18\,,\quad\mathtt{pc}(\mathcal{P}_{2})=7\,.$

Meanwhile, as the reverse direction of $\mathcal{P}_{i}$ is also meaningful,
we can use the probability of observing the $i$-th relation type $r_{i}$ in
the context history of the succeeding relation type $r_{i+1}$, and then make
assumptions and estimate probabilities in a similar way:

(16)
$\begin{split}\mathtt{Pr}(\mathcal{P}_{i})\propto\mathtt{pc}(r_{l})\prod_{i=1}^{l-1}{\frac{\mathtt{pc}(r_{i}r_{i+1})}{\mathtt{pc}(r_{i+1})}}\,.\end{split}$

To improve the robustness of our model, we take the arithmetic mean of Eq.
(13) and Eq. (16) as the final value of $\mathtt{Pr}(\mathcal{P}_{i})$.

This arithmetic mean also provides an approximation of
$\mathtt{pc}(\mathcal{P})$ for a long meta-path $\mathcal{P}$. The
approximation is useful because it may be infeasible to compute the exact
frequency count in Eq. (14) on a large KG when $\mathcal{P}$ is long.
Formally, for $\mathcal{P}:r_{1}r_{2}\cdots r_{l}$, let
$\mathtt{apc}(\mathcal{P})$ denote this approximation of
$\mathtt{pc}(\mathcal{P})$. We have

(17)
$\begin{split}\mathtt{apc}(\mathcal{P})&=\begin{cases}\mathtt{pc}(\mathcal{P})&\mathtt{len}(\mathcal{P})\leq
2\,,\\\
\frac{1}{2}(\mathtt{apc}_{\text{start}}(\mathcal{P})+\mathtt{apc}_{\text{end}}(\mathcal{P}))&\mathtt{len}(\mathcal{P})>2\,,\end{cases}\end{split}$

where $\mathtt{apc}_{\text{start}}$ and $\mathtt{apc}_{\text{end}}$ denote the
right-hand side of Eq. (13) and Eq. (16), respectively. This approximation
will be used later.

Computation of the Likelihood. For the likelihood
$\mathtt{Pr}(S|\mathcal{P}_{i})$, the user-provided examples in $S$ are
trivially considered to be conditionally independent given $\mathcal{P}_{i}$:

(18) $\mathtt{Pr}(S|\mathcal{P}_{i})=\prod_{\langle s,t\rangle\in
S}{\mathtt{Pr}(\langle s,t\rangle|\mathcal{P}_{i})}\,.$

$\mathtt{Pr}(\langle s,t\rangle|\mathcal{P}_{i})$ represents the probability
that a path following $\mathcal{P}_{i}$ connects $s$ to $t$, which we estimate
from frequency counts:

(19) $\mathtt{Pr}(\langle
s,t\rangle|\mathcal{P}_{i})\approx\frac{\mathtt{pc}(s,t,\mathcal{P}_{i})}{\mathtt{apc}(\mathcal{P}_{i})}\,,$

where $\mathtt{pc}(s,t,\mathcal{P}_{i})$ is computed by Eq. (9), and
$\mathtt{apc}(\mathcal{P}_{i})$ is an approximation of
$\mathtt{pc}(\mathcal{P}_{i})$ computed by Eq. (17).

To improve the robustness of our model, _smoothing_ is needed to avoid cases
where $\mathtt{pc}(s,t,\mathcal{P}_{i})=0$ which in turn will lead to
$\mathtt{Pr}(S|\mathcal{P}_{i})=0$. In such a case, we replace the zero value
of $\mathtt{pc}(s,t,\mathcal{P}_{i})$ with the following small non-zero value:

(20)
$\frac{\mathtt{apc}(\mathcal{P}_{i})}{|\mathtt{ST}(s)|\cdot|\mathtt{ST}(t)|}\,,$

where $\mathtt{apc}(\mathcal{P}_{i})$ is computed by Eq. (17), and
$\mathtt{ST}(\cdot)$ denotes the set of entities that have the same (most
specific) type as a given entity. Type is an attribute appearing in almost
every KG. The above value represents the average number of paths that follow
$\mathcal{P}_{i}$ and connect two entities of the same type as $s$ and as $t$.

###  3.4. Regularization

Long meta-paths are complex and may _overfit user-provided examples_. We
impose a penalty on the complexity of $\mathcal{P}_{i}$. Specifically, we
penalize long meta-paths with the following regularization term:

(21)
$\mathtt{J}(\mathcal{P}_{i})=e^{-\beta\cdot\mathtt{len}(\mathcal{P}_{i})}\,,$

where $\mathtt{len}(\mathcal{P}_{i})$ denotes the length of $\mathcal{P}_{i}$,
and $\beta>0$ is a decay factor.

##  4\. Extended Facet-based Relevance

Previous research only computes meta-path based relevance (Lao and Cohen,
2010; Sun et al., 2011b; Yu et al., 2012; Bu et al., 2014; Meng et al., 2015;
Wang et al., 2016; Shi et al., 2017; Gu et al., 2019). We extend meta-paths to
facets. A _facet_ is either a meta-path or a property that constrains answer
entities. Accordingly, we extend the $\mathtt{rel}$ function in Eq. (7) by
adding a linear combination of weighted relevance over a set of properties
denoted by $\boldsymbol{\Omega}_{\text{prop}}=\\{\langle
a_{1},l_{1}\rangle,\ldots,\langle a_{n},l_{n}\rangle\\}$:

(22)
$\begin{split}\mathtt{rel}(q,v|S)&=\sum_{\mathcal{P}_{i}\in\boldsymbol{\Omega}_{\text{mp}}}{\gamma(q,v|\mathcal{P}_{i})\cdot\mathtt{Pr}(\mathcal{P}_{i}|S)\cdot\mathtt{J}(\mathcal{P}_{i})}\\\
&+\sum_{\langle
a_{i},l_{i}\rangle\in\boldsymbol{\Omega}_{\text{prop}}}{\gamma(q,v|\langle
a_{i},l_{i}\rangle)\cdot\mathtt{Pr}(\langle
a_{i},l_{i}\rangle|S)}\,,\end{split}$

where $\gamma(q,v|\langle a_{i},l_{i}\rangle)$ measures the real-valued
relevance of $v$ to $q$ w.r.t. a particular property $\langle
a_{i},l_{i}\rangle$, and $\mathtt{Pr}(\langle a_{i},l_{i}\rangle|S)$
represents the weight of $\langle a_{i},l_{i}\rangle$. A property is already
simple and hence regularization is not needed. Properties and their weights
are also to be learned from $S$. For example, with $S_{1}$ in Eq. (1), two
properties $\langle\texttt{gender},~{}\texttt{F}\rangle$ and
$\langle\texttt{country},~{}\texttt{US}\rangle$ should have large weights
because they constrain all the target entities in $S_{1}$.

To establish the extended $\mathtt{rel}$, below we describe the selection of
$\boldsymbol{\Omega}_{\text{prop}}$, and the computation of $\gamma$ and
$\mathtt{Pr}$ for properties.

###  4.1. Property Selection

A property $\langle a_{i},l_{i}\rangle$ is in
$\boldsymbol{\Omega}_{\text{prop}}$ if it constrains the target entity in some
user-provided example:

(23) $\boldsymbol{\Omega}_{\text{prop}}=\bigcup_{\langle s,t\rangle\in
S}{\Phi(t)}\,.$

###  4.2. Property-Based Relevance

We measure the relevance of $v$ w.r.t. $\langle a_{i},l_{i}\rangle$ according
to whether $\langle a_{i},l_{i}\rangle$ is a property that constrains $v$,
which is independent of $q$:

(24) $\gamma(q,v|\langle
a_{i},l_{i}\rangle)=\begin{cases}\alpha_{\text{prop}}&\langle
a_{i},l_{i}\rangle\in\Phi(v)\,,\\\ 0&\langle
a_{i},l_{i}\rangle\notin\Phi(v)\,,\end{cases}$

where $\alpha_{\text{prop}}>0$ is a parameter to tune the importance of
properties relative to meta-paths in the computation of the extended
$\mathtt{rel}$.

###  4.3. Generative Property Weighting

Similar to our generative model for weighting meta-paths, we treat weight
$\mathtt{Pr}(\langle a_{i},l_{i}\rangle|S)$ as a posterior probability, and
rewrite it using Bayes’ theorem:

(25) $\mathtt{Pr}(\langle a_{i},l_{i}\rangle|S)\propto\mathtt{Pr}(\langle
a_{i},l_{i}\rangle)\cdot\mathtt{Pr}(S|\langle a_{i},l_{i}\rangle)\,,$

where the posterior $\mathtt{Pr}(\langle a_{i},l_{i}\rangle|S)$ is
proportional to the prior $\mathtt{Pr}(\langle a_{i},l_{i}\rangle)$ times the
likelihood $\mathtt{Pr}(S|\langle a_{i},l_{i}\rangle)$. Below we separately
compute the prior and the likelihood.

Computation of the Prior. For the prior $\mathtt{Pr}(\langle
a_{i},l_{i}\rangle)$, it represents the probability that the property $\langle
a_{i},l_{i}\rangle$ constrains an entity in the KG, which we estimate from
frequency counts:

(26) $\mathtt{Pr}(\langle a_{i},l_{i}\rangle)=\frac{|\\{v\in V:\langle
a_{i},l_{i}\rangle\in\Phi(v)\\}|}{|V|}\,,$

where $V$ is the set of entities in the KG.

Computation of the Likelihood. For the likelihood $\mathtt{Pr}(S|\langle
a_{i},l_{i}\rangle)$, similar to Eq. (18), the user-provided examples in $S$
are trivially considered to be conditionally independent given $\langle
a_{i},l_{i}\rangle$:

(27) $\begin{split}\mathtt{Pr}(S|\langle a_{i},l_{i}\rangle)&=\prod_{\langle
s,t\rangle\in S}{\mathtt{Pr}(\langle s,t\rangle|\langle
a_{i},l_{i}\rangle)}=\prod_{\langle s,t\rangle\in S}{\mathtt{Pr}(t|\langle
a_{i},l_{i}\rangle)}\,,\end{split}$

where the last equation holds because the property $\langle
a_{i},l_{i}\rangle$ constrains answer entities which correspond to the target
entity $t$ in a user-provided example, and hence $\langle a_{i},l_{i}\rangle$
is independent of the source entity $s$ in the example.

$\mathtt{Pr}(t|\langle a_{i},l_{i}\rangle)$ represents the probability that an
entity constrained by $\langle a_{i},l_{i}\rangle$ is $t$, which we estimate
from frequency counts:

(28) $\mathtt{Pr}(t|\langle a_{i},l_{i}\rangle)=\begin{cases}\frac{1}{|\\{v\in
V:\langle a_{i},l_{i}\rangle\in\Phi(v)\\}|}&\langle
a_{i},l_{i}\rangle\in\Phi(t)\,,\\\ 0&\langle
a_{i},l_{i}\rangle\notin\Phi(t)\,.\end{cases}$

To improve the robustness of our model, _smoothing_ is also needed here to
avoid cases where $\mathtt{Pr}(t|\langle a_{i},l_{i}\rangle)=0$ which in turn
will lead to $\mathtt{Pr}(S|\langle a_{i},l_{i}\rangle)=0$. In such a case, we
replace the zero value of $\mathtt{Pr}(t|\langle a_{i},l_{i}\rangle)$ with a
small non-zero value $\frac{1}{|V|}$.

##  5\. Search Algorithm

Finally, we present an efficient implementation to support learning the
proposed model from user-provided examples in an online environment and
returning answer entities promptly.

0: A KG $G=\langle V,E,\Psi\rangle$, a query entity $q$, a set of user-
provided examples $S$, an upper bound $L$ on the length of allowable meta-
paths, and a positive integer $m$.

0: $k$ top-ranked entities that are relevant to $q$.

1: $\boldsymbol{\Omega}_{\text{mp}}\leftarrow$ MPSearch($G,S,L$);

2: $\boldsymbol{\Omega}_{\text{prop}}\leftarrow\bigcup_{\langle s,t\rangle\in
S}{\Phi(t)}$;

3:
$\boldsymbol{\Omega}\leftarrow\boldsymbol{\Omega}_{\text{mp}}\cup\boldsymbol{\Omega}_{\text{prop}}$;

4: for all $\Omega_{i}\in\boldsymbol{\Omega}$ do

5: Compute $\mathtt{Pr}(\Omega_{i}|S)$;

6: end for

7: $\boldsymbol{\Omega}_{\text{top}}\leftarrow$ $m$ meta-paths in
$\boldsymbol{\Omega}_{\text{mp}}$ with the largest weights;

8:
$C\leftarrow\bigcup_{\mathcal{P}_{i}\in\boldsymbol{\Omega}_{\text{top}}}{\\{v\in
V:\exists p\models\mathcal{P}_{i},~{}q\rightsquigarrow_{p}v\\}}$;

9: for all $v\in C$ do

10: Compute $\mathtt{rel}(q,v|S)$;

11: end for

12: return $k$ top-ranked entities in $C$

Figure 2. The GREASE algorithm.

###  5.1. Algorithm

The full GREASE algorithm is presented in Fig. 2. MPSearch (line 1) finds
$\boldsymbol{\Omega}_{\text{mp}}$ which is defined by Eq. (8). It performs
$|S|$ bidirectional searches—one for each example in $S$, starting
simultaneously from the source entity and the target entity. The search space
is restricted to meta-paths that are not longer than $L$, which is a
predetermined upper bound. Then we find $\boldsymbol{\Omega}_{\text{prop}}$
(line 2) which is defined by Eq. (23). $\boldsymbol{\Omega}_{\text{mp}}$ and
$\boldsymbol{\Omega}_{\text{prop}}$ comprise $\boldsymbol{\Omega}$ (line 3),
namely all the facets to consider for computing $\mathtt{rel}$ in Eq. (22).
For each facet $\Omega_{i}\in\boldsymbol{\Omega}$, we compute
$\mathtt{Pr}(\Omega_{i}|S)$ according to Section 3.3 and Section 4.3 (lines
4–6). The $m$ meta-paths in $\boldsymbol{\Omega}_{\text{mp}}$ with the largest
weights are denoted by $\boldsymbol{\Omega}_{\text{top}}$ (line 7). All the
entities that are connected from $q$ by a path following a meta-path in
$\boldsymbol{\Omega}_{\text{top}}$ form candidate answer entities, denoted by
$C$ (line 8). Here, we only use $m$ meta-paths to identify candidate answer
entities for efficiency considerations. For each candidate answer entity, its
extended relevance to $q$ is computed (lines 9–11), and the $k$ top-ranked
ones are returned.

###  5.2. Indexing

To support efficient computation in an online environment, we precompute and
index the following statistics.

We index the frequency counts for all the meta-paths in the KG that are not
longer than 2, so their $\mathtt{pc}$ values defined by Eq. (14) are
retrievable in $O(1)$, and for any other meta-path, its approximate
$\mathtt{pc}$ value (i.e., $\mathtt{apc}$) defined by Eq. (17) is computable
in $O(L)$.

We also index the frequency counts for all the properties in the KG, so Eq.
(26) and Eq. (28) are computable in $O(1)$.

We index the frequency counts for all the entity types in the KG, so
$|\mathtt{ST}(\cdot)|$ in Eq. (20) is computable in $O(1)$.

###  5.3. Complexity Analysis

Let $\Delta$ be the maximum degree of the nodes in the KG. Let $\Xi$ be the
maximum number of properties that constrain an entity in the KG.
$\boldsymbol{\Omega}_{\text{mp}}$ is computed in
$O(|S|\cdot\Delta^{\lceil\frac{L}{2}\rceil})$ using bidirectional search, and
$\boldsymbol{\Omega}_{\text{prop}}$ is computed in $O(|S|\cdot\Xi)$.

To compute the posterior $\mathtt{Pr}(\Omega_{i}|S)$, when $\Omega_{i}$ is a
meta-path $\mathcal{P}_{i}$, the prior $\mathtt{Pr}(\mathcal{P}_{i})$ is
computed by Eq. (13) and Eq. (16) in $O(L)$, and the likelihood
$\mathtt{Pr}(S|\mathcal{P}_{i})$ is computed by Eq. (18) in $O(L+|S|)$ where
$\mathtt{pc}(s,t,\mathcal{P}_{i})$ has been computed during MPSearch. When
$\Omega_{i}$ is a property $\langle a_{i},l_{i}\rangle$, the prior
$\mathtt{Pr}(\langle a_{i},l_{i}\rangle)$ is computed by Eq. (26) in $O(1)$,
and the likelihood $\mathtt{Pr}(S|\langle a_{i},l_{i}\rangle)$ is computed by
Eq. (27) in $O(|S|)$.

The candidate answer entities $C$ are computed in $O(m\cdot\Delta^{L})$.

The computation of the $\mathtt{rel}$ function does not further increase the
asymptotic time complexity of the algorithm.

To conclude, in practice, the running time of the entire algorithm is probably
dominated by MPSearch.

##  6\. Experiments

We empirically compared our approach with several state-of-the-art methods
based on a variety of queries over two popular KGs. Both effectiveness and
efficiency were tested.

###  6.1. Datasets

Table 1. Statistics about KGs

KG | Entity | Relation | Relation | Attribute
---|---|---|---|---
Type | Type
DBpedia 2016-10 | 5,900,558 | 18,746,174 | 661 | 2,065
(Mappingbased Objects)
YAGO 3.1 | 4,295,825 | 12,430,700 | 37 | 1
(yagoFacts)

Knowledge Graphs. Our experiments were based on two popular large-scale KGs:
DBpedia (Lehmann et al., 2015) (version 2016-10) and YAGO (Mahdisoltani et
al., 2015) (version 3.1). For DBpedia, we obtained a KG from two files:
_Mappingbased Objects_ and _Instance Types_. For YAGO, we obtained a KG from
two files: _yagoFacts_ and _yagoSimpleTypes_. The files are in RDF format,
where RDF literals and types were treated as attributes, and the other RDF
triples became relations. Some statistics about these KGs are summarized in
Table 1. Note that YAGO was to be used with the queries created in (Gu et al.,
2019) where attributes are not involved. So we followed (Gu et al., 2019) to
only import _yagoFacts_ and _yagoSimpleTypes_ which contain relations but no
attributes except for type.

Table 2. Query Groups with Examples

| Desired Semantics (Facets) | Example Query and Answers
---|---|---
| Query Entity | User-Provided Examples |  Query Intent | Answer Entities
D1 | starring-1 director | Howard Duff | $\langle\text{Stephen Wight},~{}\text{Susan Tully}\rangle$ |  director of a movie starring Howard Duff | George Sherman
$\langle\text{Vijay Chavan},~{}\text{Kedar Shinde}\rangle$ | Andre deToth
D2 | almaMater-1 foundedBy-1 | Bowdoin College | $\langle\text{Duke University},~{}\text{Duolingo}\rangle$ |  organization founded by a Bowdoin alumnus | Netflix
$\langle\text{Yale University},~{}\text{Allied Corp}\rangle$ | Pure Software
D3 | starring starring-1 | Charlie Chaplin | $\langle\text{Bam Margera},~{}\text{Brandon Novak}\rangle$ |  actor and also director of a movie starring Charlie Chaplin | Mack Swain
starring director-1 | $\langle\text{Rahul Bose},~{}\text{Koel Purie}\rangle$ | Lloyd Bacon
D4 | almaMater almaMater-1 | Hagan Bayley | $\langle\text{Ewan Birney},~{}\text{Antony Galione}\rangle$ |  Hagan Bayley’s schoolmate that won the same award | John Mollon
award award-1 | $\langle\text{George Porter},~{}\text{Charles Coulson}\rangle$ | Henry Gilman
D5 | architecturalStyle architecturalStyle-1 | De Rohan Arch | $\langle\text{Morson's Row},~{}\text{PaceKing House}\rangle$ |  architecture with the same style and location as the De Rohan Arch | Hompesch Gate
location location-1 | $\langle\text{Evergreen (Virginia)},~{}\text{Greer House}\rangle$ | La Borsa
D6 | starring-1 director director-1 | Tanya Chisholm | $\langle\text{Casey Kasem},~{}\text{Fantastic Max}\rangle$ |  comedy directed by the director of a movie starring Tanya Chisholm | The Last Halloween
$\langle\text{genre},~{}\text{Comedy}\rangle$ | $\langle\text{Michael Milhoan},~{}\text{Party Down}\rangle$ | A Fairly Odd Summer
D7 | almaMater almaMater-1 foundedBy-1 | Vitalik Buterin | $\langle\text{Peter Clyne},~{}\text{SpringSource}\rangle$ |  software company founded by Vitalik Buterin’s schoolmate | Databricks
$\langle\text{industry},~{}\text{Software}\rangle$ | $\langle\text{Felix Villars},~{}\text{Lightbend Inc.}\rangle$ | Waterloo Maple
D8 | influenced-1 influenced | Leo Strauss | $\langle\text{Denis Diderot},~{}\text{Leonhard Euler}\rangle$ |  physicist influenced by the same person as Leo Strauss | Isaac Newton
$\langle\text{field},~{}\text{Physics}\rangle$ | $\langle\text{Herbert Feigl},~{}\text{Albert Einstein}\rangle$ | David Hilbert
D9 | affiliation affiliation-1 | Carleton College | $\langle\text{Viterbo University},~{}\text{Fisk University}\rangle$ |  private school affiliated with the same organization as Carleton College | Manhattan College
$\langle\text{type},~{}\text{Private school}\rangle$ | $\langle\text{Verdon College},~{}\text{DePaul University}\rangle$ | Drake University
D10 | museum-1 author | Metropolitan Museum of Art | $\langle\text{National Gallery},~{}\text{Georges Seurat}\rangle$ |  Parisian artist with artworks housed by Metropolitan Museum of Art | Georges Seurat
$\langle\text{birthPlace},~{}\text{Paris}\rangle$ | $\langle\text{Van Gogh Museum},~{}\text{Robert Delaunay}\rangle$ | Jacques-Louis David

Queries. We reused 320 query
instances333http://ws.nju.edu.cn/relevance/relsue/ given in (Gu et al., 2019)
which were divided into 8 groups (D11–D14 and Y1–Y4). However, this dataset is
still limited in two aspects. First, attributes are not considered. Second,
the query entity is required to appear as the source entity in every user-
provided example, because the method proposed in (Gu et al., 2019) was
specifically designed for this scenario. To overcome these two limitations, we
created 800 query instances444http://ws.nju.edu.cn/relevance/grease/ which
were divided into 10 groups (D1–D10).

Our creation of D1–D10 followed a common practice in related work (Wang et
al., 2016; Gu et al., 2019). Compared with D11–D14 and Y1–Y4 created in (Gu et
al., 2019), our D1–D10 are more generalized as they allow the source entity in
a user-provided example to be different from the query entity, and they are
more challenging as D6–D10 involve properties. In general, their desired
semantics of relevance are more complex than all the known queries used in the
literature.

Specifically, each group of D1–D10 contains 80 query instances, and their
desired semantics of relevance are represented by the same set of predefined
facets. We sampled 100 random source-target entity pairs from DBpedia as a
pool such that their relevance conformed to the predefined semantics. We chose
20 random pairs from the pool and took their source entities as our query
entities. For each query entity, based on the predefined semantics of
relevance, we labeled gold-standard answer entities, and created 4 query
instances by choosing different numbers of random pairs from the pool as user-
provided examples: $|S|\in\\{2,3,4,5\\}$. Table 2 illustrates each group with
one query instance under $|S|=2$ and two of its gold-standard answer entities.

The creation of D11–D14 and Y1–Y4 in (Gu et al., 2019) adopted a similar
procedure, and we refer the reader to (Gu et al., 2019) for details. D11–D14
are based on DBpedia, and Y1–Y4 are based on YAGO. Each group contains 40
query instances.

###  6.2. Baselines

To compare with the state of the art, we chose five strong baselines: PRA (Lao
and Cohen, 2010), RelSim (Wang et al., 2016), RelSUE (Gu et al., 2019), ProxE
(Liu et al., 2017), and D2AGE (Liu et al., 2018). We intended to also compare
with FSPG (Meng et al., 2015), but we could not obtain its implementation from
its authors and we failed to re-implement it due to some missing details in
the algorithm.

All the chosen baseline methods except for RelSUE could be tested with all the
query instances in our experiments. RelSUE requires the query entity to appear
as the source entity in every user-provided example, so it could only be
tested with D11–D14 and Y1–Y4 created by the authors of RelSUE.

We obtained implementations of RelSUE, ProxE, and D2AGE from their authors,
and we re-implemented PRA and RelSim. For PRA, RelSim, ProxE, and D2AGE, we
consistently set their bounds on meta-path length to 3, being sufficiently
large for representing all the semantics of relevance in our experiments.
RelSUE automatically generated meta-paths of varied lengths.

PRA, RelSim, and RelSUE automatically sampled $10\cdot|S|$ negative examples
for training. For ProxE and D2AGE, a training example is a triple $\langle
u,v,w\rangle$ where entity $v$ is more relevant to query entity $u$ than
entity $w$. We generated 100 such triples for each query instance by extending
our positive example $\langle u,v\rangle$ with a random entity $w$ having the
same type as $v$.

###  6.3. Configuration and Variant of GREASE

For our proposed approach GREASE, by default we set $\alpha_{\text{mp}}=5$ in
Eq. (9), $\alpha_{\text{prop}}=2$ in Eq. (24), $\beta=10$ in Eq. (21), $L=3$
and $m=3$ in Algorithm 2. A parameter study will be reported in Section 6.5.

For D1–D5, D11–D14, and Y1–Y4 where only meta-paths but no properties are
involved, we implemented a variant of GREASE using only meta-paths as facets,
denoted by GREASE-np.

###  6.4. Effectiveness Evaluation

Evaluation Metric. For each query instance, the gold standard is a set of
relevant answer entities. Each tested method computed $k$ top-ranked answer
entities. Their quality was measured by the Normalized Discounted Cumulative
Gain (NDCG) at rank position $k$, referred to as NDCG@$k$. Due to space
limitations, we only present NDCG@10 scores (i.e., $k=10$).

Table 3. NDCG@10 on D1–D5 Method | $|S|=2$ | $|S|=3$ | $|S|=4$ | $|S|=5$
---|---|---|---|---
PRA | 0.535 | 0.636 | 0.599 | 0.639
RelSim | 0.452 | 0.562 | 0.555 | 0.575
ProxE | 0.484 | 0.467 | 0.480 | 0.503
D2AGE | 0.549 | 0.509 | 0.555 | 0.637
GREASE | 0.782 | 0.737 | 0.734 | 0.763
GREASE-np | 0.846 | 0.850 | 0.865 | 0.862
Table 4. NDCG@10 on D6–D10 Method | $|S|=2$ | $|S|=3$ | $|S|=4$ | $|S|=5$
---|---|---|---|---
PRA | 0.295 | 0.293 | 0.337 | 0.339
RelSim | 0.329 | 0.403 | 0.428 | 0.439
ProxE | 0.445 | 0.440 | 0.450 | 0.426
D2AGE | 0.366 | 0.381 | 0.397 | 0.401
GREASE | 0.831 | 0.840 | 0.866 | 0.874

Results on D1–D5. The average NDCG@10 scores on D1–D5 are presented in Table
3. The results are categorized by number of user-provided examples (i.e.,
$|S|$). GREASE outperformed all the baselines by at least 0.101–0.233 under
different values of $|S|$. GREASE-np achieved even higher scores, exceeding
the baselines by at least 0.214–0.297. Recall that for the query instances in
D1–D5, their desired semantics of relevance are represented by only meta-
paths. Therefore, the superiority of GREASE-np over the baselines demonstrated
the effectiveness of our proposed generative model for weighting meta-paths.

Compared with GREASE-np, the small drops in GREASE’s scores suggested that its
extended model mistakenly assigned large weights to some properties. The
extended model is expressive in characterizing user-defined relevance but is
then more prone to errors due to the expansion of the search space.
Nevertheless, the satisfying performance of GREASE showed that it achieved a
good trade-off between expressiveness and accuracy.

Another finding was GREASE and GREASE-np already achieved high scores when
$|S|=2$. Their performance did not increase notably when $|S|$ increased. It
indicated that using our approach, users can obtain quite accurate answers
with a small effort.

Results on D6–D10. The average NDCG@10 scores on D6–D10 are presented in Table
4. Query instances in D6–D10 require using properties that constrain answer
entities. Not surprisingly, GREASE largely surpassed all the baselines by at
least 0.386–0.435 under different values of $|S|$, as it was the only method
that explicitly processed properties. It confirmed the expressiveness of our
extended model in supporting the representation of user-defined relevance.

Table 5. NDCG@10 on D11–D14 Method | $|S|=2$ | $|S|=3$ | $|S|=4$ | $|S|=5$
---|---|---|---|---
PRA | 0.465 | 0.520 | 0.550 | 0.568
RelSim | 0.644 | 0.656 | 0.654 | 0.666
RelSUE | 0.901 | 0.952 | 0.948 | 0.971
ProxE | 0.410 | 0.402 | 0.410 | 0.371
D2AGE | 0.627 | 0.672 | 0.746 | 0.697
GREASE | 0.971 | 0.978 | 0.953 | 0.973
GREASE-np | 0.995 | 0.968 | 0.942 | 0.968
Table 6. NDCG@10 on Y1–Y4 Method | $|S|=2$ | $|S|=3$ | $|S|=4$ | $|S|=5$
---|---|---|---|---
PRA | 0.215 | 0.144 | 0.144 | 0.181
RelSim | 0.274 | 0.336 | 0.357 | 0.367
RelSUE | 0.770 | 0.843 | 0.873 | 0.880
ProxE | 0.568 | 0.592 | 0.562 | 0.608
D2AGE | 0.670 | 0.637 | 0.735 | 0.647
GREASE | 0.724 | 0.861 | 0.860 | 0.900
GREASE-np | 0.673 | 0.677 | 0.674 | 0.703

Results on D11–D14 and Y1–Y4. The average NDCG@10 scores on D11–D14 and Y1–Y4
are presented in Table 5 and Table 6, respectively. Query instances in D11–D14
and Y1–Y4 represent a special case of our problem, where the query entity
appears as the source entity in every user-provided example. RelSUE was
specifically optimized for this scenario and represented the state of the art.
Its scores were very high on D11–D14, in the range of 0.901–0.972 under
different values of $|S|$. GREASE performed even better, although their
differences were not large: 0.002–0.070. On Y1–Y4, GREASE led when $|S|=3$ and
$|S|=5$, whereas RelSUE was better when $|S|=2$ and $|S|=4$. We concluded that
GREASE was comparable with RelSUE in this special setting. It demonstrated the
effectiveness and generalizability of our approach.

Figure 3. Influence of parameters on our approach.

###  6.5. Parameter Study

In Fig. 3, we present the influence of the five parameters on our approach:
$L$, $m$, $\alpha_{\text{prop}}$, $\beta$, and $\alpha_{\text{mp}}$.

$L$ and $m$ in Algorithm 2 tune the trade-off between expressiveness and
efficiency in our approach. $L$ bounds the length of allowable meta-paths, and
$m$ bounds the number of meta-paths used to identify candidate answer
entities. All the desired semantics of relevance in our experiments can be
represented by meta-paths not longer than 3. GREASE exactly peaked when $L=3$.
Its scores did not change much when $L$ increased to 4. That would give us
more flexibility in practice. As to $m$, our approach achieved good results
when $m$ was small, owing to the high quality of the computed meta-paths with
the largest weights. When $m$ was larger, more noise could be introduced, but
the performance of our approach appeared rather stable.

$\alpha_{\text{prop}}$ in Eq. (24) tunes the importance of properties relative
to meta-paths. On D1–D5 where properties are not needed, larger values of
$\alpha_{\text{prop}}$ led to poorer results. The setting of this parameter
would depend on the needs of the application.

$\beta$ in Eq. (21) tunes the degree of penalizing long meta-paths to prevent
overfitting. $\alpha_{\text{mp}}$ in Eq. (9) bounds the value of path count to
prevent highly skewed values. The performance of GREASE was more sensitive to
$\beta$ on D1–D5 than on D6–D10, because D1–D5 totally rely on meta-paths. The
performance was generally not very sensitive to $\alpha_{\text{mp}}$ unless it
was inappropriately set to 1 which disabled path count.

###  6.6. Efficiency Evaluation

Our experiments were performed on a 3.40GHz Xeon. The precomputed indexes for
GREASE only used 190MB for DBpedia and 123MB for YAGO.

In Fig. 4, for each method we report its average running time per query
instance. GREASE satisfyingly completed a search task in less than 1s on
DBpedia (D1–D14), at least an order of magnitude faster than all the
baselines. It used less than 10s on YAGO (Y1–Y4), being comparable with RelSUE
which was optimized for this special scenario. The results demonstrated the
efficiency of our approach.

PRA, RelSim, and GREASE ran slower on YAGO than on DBpedia. These methods
search the KG to generate all possible meta-paths of a bounded length. YAGO
contains much more paths to explore than DBpedia—about 40 times in our
experiments, due to the existence of hub nodes in YAGO.

In Fig. 5, we show the influence of $|S|$ on the efficiency of GREASE. The
influence was not significant on DBpedia (D1–D14), which suggested the
scalability of our approach. However, on YAGO (Y1–Y4), the running time
exhibited a linear correlation with $|S|$.

##  7\. Related Work

###  7.1. Unsupervised Similarity Search

Relevance search originates from similarity search, for which methods are
mainly based on random walks. ObjectRank (Balmin et al., 2004) computes the
stationary probability that a random surfer starting from the query entity is
at a particular entity as their similarity. PathSim (Sun et al., 2011b)
requires random walks to follow a predefined meta-path, to compute similarity
with a specified type of semantics. JoinSim (Xiong et al., 2015) uses a
slightly different measure. PReP (Shi et al., 2017) extends PathSim and
JoinSim. It computes cross-meta-path synergy, which goes beyond a linear
combination of meta-paths. In (Huang et al., 2016), meta-path is extended to
meta-structure which is a directed acyclic graph.

These methods have found application in entity resolution and entity
clustering (Sun et al., 2012) where similarity measurement is the core task.
However, similarity is only one special type of relevance. Without the
supervision of the user, these methods are not suitable for the more
generalized relevance search because they cannot distinguish between a wide
range of semantics of relevance on a KG.

Figure 4. Average running time per query instance.

###  7.2. Supervised Relevance Search

Relevance is rather ambiguous on a schema-rich KG. Unfortunately, users may
not have the expertise to formally characterize the desired semantics of
relevance, due to the complexity of the query language or the richness of the
schema. In order to learn user-defined relevance, existing methods are mainly
supervised by user-provided examples. An early work is SRW (Backstrom and
Leskovec, 2011), which leverages user-provided examples to supervise random
walks for computing relevance. In (Yu et al., 2012; Bu et al., 2014),
predefined meta-paths are used to constrain random walks, and user-provided
examples are used to learn the weights of the meta-paths. However, it is
unrealistic to predefine meta-paths for all possible types of information
needs that users may have on a schema-rich KG. It is also difficult for a non-
expert user to identify appropriate meta-paths from numerous candidates.

To tackle the problem, PRA (Lao and Cohen, 2010) and RelSim (Wang et al.,
2016) automatically generate all possible meta-paths but they have to bound
the length of an allowable meta-path because the number of possible meta-paths
increases exponentially with length. In (Fang et al., 2016), length-bounded
meta-path is extended to size-bounded meta-graph. In FSPG (Meng et al., 2015)
and RelSUE (Gu et al., 2019), there is no explicit length bound, but long
meta-paths are penalized and hence are more likely to be pruned in their
greedy search algorithms. All these methods train a discriminative model to
learn the weight of each meta-path or meta-graph from user-provided positive
examples and randomly sampled negative examples. By contrast, we present a
generative model which does not rely on negative examples. It outperforms the
above discriminative methods in the experiments, in both effectiveness and
efficiency. Moreover, our approach generalizes meta-paths into facets which
also include properties that constrain answer entities, and hence it supports
more expressive representation of user-defined relevance.

Some recent efforts learn graph embedding models for relevance (Liu et al.,
2017, 2018). However, they did not show better performance than other methods
in our experiments. Their complex models may be more suitable for the link
prediction task (Cai et al., 2018; Martínez et al., 2017), where large
training sets are available. In relevance search, a user is not likely to
provide many examples to supervise.

Figure 5. Average running time of GREASE per query instance.

###  7.3. Other Related Problems

Other related problems include graph query by example (Jayaram et al., 2015)
and exemplar query answering (Mottin et al., 2016), but their technical
challenges and methods are fundamentally different. Their input is a tuple of
entities (Jayaram et al., 2015) or a keyword query (Mottin et al., 2016)
provided by the user as an example. The example is expanded (Jayaram et al.,
2015) or mapped (Mottin et al., 2016) into a subgraph of the KG, called a
query graph, to capture the user’s query intent. The output is a set of other
top-ranked subgraphs of the KG that are similar to the query graph. By
contrast, relevance search is mainly focused on the selection, weighting, and
combination of meta-paths to represent the user-defined relevance between the
source entity and the target entity in the user-provided examples.

##  8\. Conclusions

We proposed GREASE, a new approach to relevance search over KGs. Compared with
existing methods, GREASE is distinguished by its more effective generative
model for weighting meta-paths, its more expressive facet-based representation
of relevance with properties, and its efficient implementation. These
technical contributions have been demonstrated in an extensive evaluation.

One limitation of our approach is that our estimation of probabilities is
largely based on frequency counts in the KG. However, KGs in the real world
may be inexact or incomplete, which may affect the accuracy of our estimation.
We have used smoothing methods to partially address this issue, but further
attempts may be helpful, e.g., using external knowledge. In future work, we
will also consider using ontological schemata and reasoning services to handle
more complex semantics of relevance.

## References

  * (1)
  * Backstrom and Leskovec (2011) Lars Backstrom and Jure Leskovec. 2011.  Supervised random walks: predicting and recommending links in social networks. In _Proc. WSDM_. 635–644.  https://doi.org/10.1145/1935826.1935914
  * Balmin et al. (2004) Andrey Balmin, Vagelis Hristidis, and Yannis Papakonstantinou. 2004\.  ObjectRank: Authority-Based Keyword Search in Databases. In _Proc. VLDB_. 564–575.
  * Bu et al. (2014) Shaoli Bu, Xiaoguang Hong, Zhaohui Peng, and Qingzhong Li. 2014\.  Integrating meta-path selection with user-preference for top-k relevant search in heterogeneous information networks. In _Proc. CSCWD_. 301–306.  https://doi.org/10.1109/CSCWD.2014.6846859
  * Cai et al. (2018) HongYun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. 2018\.  A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications.  _IEEE Trans. Knowl. Data Eng._ 30, 9 (2018), 1616–1637.  https://doi.org/10.1109/TKDE.2018.2807452
  * Fang et al. (2016) Yuan Fang, Wenqing Lin, Vincent Wenchen Zheng, Min Wu, Kevin Chen-Chuan Chang, and Xiaoli Li. 2016.  Semantic proximity search on graphs with metagraph-based learning. In _Proc. ICDE_. 277–288.  https://doi.org/10.1109/ICDE.2016.7498247
  * Gu et al. (2019) Yu Gu, Tianshuo Zhou, Gong Cheng, Ziyang Li, Jeff Z. Pan, and Yuzhong Qu. 2019\.  Relevance Search over Schema-Rich Knowledge Graphs. In _Proc. WSDM_. 114–122.  https://doi.org/10.1145/3289600.3290970
  * Huang et al. (2016) Zhipeng Huang, Yudian Zheng, Reynold Cheng, Yizhou Sun, Nikos Mamoulis, and Xiang Li. 2016\.  Meta Structure: Computing Relevance in Large Heterogeneous Information Networks. In _Proc. SIGKDD_. 1595–1604.  https://doi.org/10.1145/2939672.2939815
  * Jayaram et al. (2015) Nandish Jayaram, Arijit Khan, Chengkai Li, Xifeng Yan, and Ramez Elmasri. 2015.  Querying Knowledge Graphs by Example Entity Tuples.  _IEEE Trans. Knowl. Data Eng._ 27, 10 (2015), 2797–2811.  https://doi.org/10.1109/TKDE.2015.2426696
  * Lao and Cohen (2010) Ni Lao and William W. Cohen. 2010.  Relational retrieval using a combination of path-constrained random walks.  _Machine Learning_ 81, 1 (2010), 53–67.  https://doi.org/10.1007/s10994-010-5205-8
  * Lehmann et al. (2015) Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. 2015.  DBpedia - A large-scale, multilingual knowledge base extracted from Wikipedia.  _Semantic Web_ 6, 2 (2015), 167–195.  https://doi.org/10.3233/SW-140134
  * Liu et al. (2017) Zemin Liu, Vincent W. Zheng, Zhou Zhao, Fanwei Zhu, Kevin Chen-Chuan Chang, Minghui Wu, and Jing Ying. 2017.  Semantic Proximity Search on Heterogeneous Graph by Proximity Embedding. In _Proc. AAAI_. 154–160.
  * Liu et al. (2018) Zemin Liu, Vincent W. Zheng, Zhou Zhao, Fanwei Zhu, Kevin Chen-Chuan Chang, Minghui Wu, and Jing Ying. 2018.  Distance-Aware DAG Embedding for Proximity Search on Heterogeneous Graphs. In _Proc. AAAI_.
  * Mahdisoltani et al. (2015) Farzaneh Mahdisoltani, Joanna Biega, and Fabian M. Suchanek. 2015\.  YAGO3: A Knowledge Base from Multilingual Wikipedias. In _Proc. CIDR_.
  * Martínez et al. (2017) Víctor Martínez, Fernando Berzal, and Juan Carlos Cubero Talavera. 2017.  A Survey of Link Prediction in Complex Networks.  _ACM Comput. Surv._ 49, 4 (2017), 69:1–69:33.  https://doi.org/10.1145/3012704
  * Meng et al. (2015) Changping Meng, Reynold Cheng, Silviu Maniu, Pierre Senellart, and Wangda Zhang. 2015.  Discovering Meta-Paths in Large Heterogeneous Information Networks. In _Proc. WWW_. 754–764.  https://doi.org/10.1145/2736277.2741123
  * Mottin et al. (2016) Davide Mottin, Matteo Lissandrini, Yannis Velegrakis, and Themis Palpanas. 2016.  Exemplar queries: a new way of searching.  _VLDB J._ 25, 6 (2016), 741–765.  https://doi.org/10.1007/s00778-016-0429-2
  * Shi et al. (2012) Chuan Shi, Xiangnan Kong, Philip S. Yu, Sihong Xie, and Bin Wu. 2012.  Relevance search in heterogeneous networks. In _Proc. EDBT_. 180–191.  https://doi.org/10.1145/2247596.2247618
  * Shi et al. (2017) Yu Shi, Po-Wei Chan, Honglei Zhuang, Huan Gui, and Jiawei Han. 2017.  PReP: Path-Based Relevance from a Probabilistic Perspective in Heterogeneous Information Networks. In _Proc. SIGKDD_. 425–434.  https://doi.org/10.1145/3097983.3097990
  * Sun et al. (2011a) Yizhou Sun, Rick Barber, Manish Gupta, Charu C. Aggarwal, and Jiawei Han. 2011a.  Co-author Relationship Prediction in Heterogeneous Bibliographic Networks. In _Proc. ASONAM_. 121–128.  https://doi.org/10.1109/ASONAM.2011.112
  * Sun et al. (2011b) Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. 2011b.  PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks.  _PVLDB_ 4, 11 (2011), 992–1003.
  * Sun et al. (2012) Yizhou Sun, Brandon Norick, Jiawei Han, Xifeng Yan, Philip S. Yu, and Xiao Yu. 2012\.  Integrating meta-path selection with user-guided object clustering in heterogeneous information networks. In _Proc. SIGKDD_. 1348–1356.  https://doi.org/10.1145/2339530.2339738
  * Wang et al. (2016) Chenguang Wang, Yizhou Sun, Yanglei Song, Jiawei Han, Yangqiu Song, Lidan Wang, and Ming Zhang. 2016.  RelSim: Relation Similarity Search in Schema-Rich Heterogeneous Information Networks. In _Proc. SDM_. 621–629.  https://doi.org/10.1137/1.9781611974348.70
  * Xiong et al. (2015) Yun Xiong, Yangyong Zhu, and Philip S. Yu. 2015.  Top-k Similarity Join in Heterogeneous Information Networks.  _IEEE Trans. Knowl. Data Eng._ 27, 6 (2015), 1710–1723.  https://doi.org/10.1109/TKDE.2014.2373385
  * Yu et al. (2012) Xiao Yu, Yizhou Sun, Brandon Norick, Tiancheng Mao, and Jiawei Han. 2012.  User guided entity similarity search using meta-path selection in heterogeneous information networks. In _Proc. CIKM_. 2025–2029.  https://doi.org/10.1145/2396761.2398565