# Unraveling Diffusion in Fusion Plasma: A Case Study of In Situ Processing
and Particle Sorting

Junmin Gu, Paul Lin, Kesheng Wu,
Lawrence Berkeley National Laboratory, Berkeley, CA,

Seung-Hoe Ku, C.S. Chang, R. Michael Churchill,
Princeton Plasma Physics Laboratory, Princeton, NJ,

Jong Choi, Norbert Podhorszki, Scott Klasky
Oak Ridge National Laboratory, Oak Ridge, TN

###### Abstract

This work starts an in situ processing capability to study a certain diffusion
process in magnetic confinement fusion. This diffusion process involves plasma
particles that are likely to escape confinement. Such particles carry a
significant amount of energy from the burning plasma inside the tokamak to the
diverter and damaging the diverter plate. This study requires in situ
processing because of the fast changing nature of the particle diffusion
process. However, the in situ processing approach is challenging because the
amount of data to be retained for the diffusion calculations increases over
time, unlike in other in situ processing cases where the amount of data to be
processed is constant over time. Here we report our preliminary efforts to
control the memory usage while ensuring the necessary analysis tasks are
completed in a timely manner. Compared with an earlier naive attempt to
directly computing the same diffusion displacements in the simulation code,
this in situ version reduces the memory usage from particle information by
nearly 60% and elapsed time by about 20%.

##  1 Introduction

Understanding the dynamics of the fusion plasma at the edge of magnetic
confinement is critical for developing stable controlled fusion energy. Toward
this goal, the X-point Gyrokinetic Code (XGC) [5, 4, 3] needs to track
particles near the edge, especially those crossing the magnetic separatrix
surface; see an illustration in Fig. 1(a). This work is a preliminary study of
the diffusion process of those particles with high likelihood of escaping
confinement. These particles could remove mass and heat from the fusion plasma
to the scrape-off layer outside the separatrix surface [10, 9]. Since this
process of escaping could happen very quickly, it is therefore necessary to
track the particle positions at every simulation time step. If the particle
trajectories are stored in memory, it would significantly increase the memory
requirements for XGC. An early attempt to compute statistics representing the
diffusion process within the XGC simulation code was found to significantly
increase the memory requirement per particle (more detail in Section 3.1).
This additional memory requirement was considered to be too high for memory-
hungry leadership-class computers; therefore, the team started to explore in
situ processing options.

However, the team encountered a new problem to solve. In a typical in situ
processing use case, the memory required on each analysis node is fixed over
time, while our diffusion calculations involve an unknown number of particles
and a growing number of simulation time steps. This short paper describes our
exploration of implementing this in situ processing for diffusion calculation
with ADIOS [14], with the main focus on (1) how to select the particles to
limit the number of particles to be tracked, (2) how to sort the particles to
build the particle trajectories with a minimal memory requirement, and (3) how
to select the specific quantities to compute to represent the diffusion
processes.

##  2 Background

In this section we will briefly describe the foundation of our work: the XGC
application and the I/O library ADIOS.

|
---|---
(a) | (b)
Figure 1: (a) Cross section of a tokamak overlaid with simulated temperature
from XGC [6]. (b) Outline of separatrix (green) with 8 regions in the fourth
quadrant used for diffusion calculations.
---
(a)
(b)
Figure 2:  (a) Outlines the workflow for XGC simulation and analysis. The
arrow indicates some data is shipped for in situ processing. (b) A detailed
illustration of diffusion analysis tasks. The large box contains the analysis
tasks for step N, while simulation is working on step N+1. Different number of
nodes could be used for processing electrons and ions, in one case, we used 64
nodes for simulation, and 6 nodes for ions and 4 nodes for electrons.

#### XGC

Magnetic confinement fusion developing under large research projects such as
the ITER is expected to achieve stable controlled fusion with significant
energy gain [9, 10]. The X-point Gyrokinetic Code (XGC) [5, 4, 3] is a
critical simulation tool for understanding the dynamics of the plasma
particles near the edge of the magnetic confinement that are essential for
this fusion performance [9]. In particular, the particle and energy transport
process near the separatrix (surface which separated the region of confined
and unconfined plasma) might have significant variation, especially near the
X-point (point on the separatrix where the poloidal magnetic field has a null)
as shown in Fig. 1 (a). And Fig. 1(b) shows a simplified illustration of a
cross section of a tokamak, with separatrix shown in green. The two ends of
the separatrix intersect a specially designed region of the tokamak known as
the diverter. To study the variation of the transport process (specifically
diffusion) along the separatrix, we will be dividing the separatrix into
different regions as illustrated in Fig. 1(b).

To study this diffusion process carefully, the XGC simulation will need to
track massive numbers of particles [6]. Since the masses of the ions and
electrons are very different, their motion is also very different, this work
will track the electrons and ions separately. Fig. 2 shows an illustration of
the overall process of our in situ diffusion calculation, where Fig. 2(a)
shows the overall in situ workflow and Fig. 2(b) provides a high-level view of
the main processing steps on the analysis nodes. We will discuss the analysis
computation in more detail in the next section.

#### ADIOS

Our in situ processing is carried out with the Adaptable I/O System (ADIOS),
which is a high performance I/O framework with a strong support for various
forms of in situ processing [13, 14, 8]. Since the XGC code is already using
ADIOS for its I/O operations, supporting additional in situ processing does
not require significant changes.

The key metaphor for describing the data during in situ processing is the
concept of “steps,” which matches very well with the simulation time steps in
XGC. At the end of each simulation step, information about selected particles
are given to ADIOS to be passed to analysis nodes. Depending on exactly how
these processing operations are carried out, various terms are used to
describe them [15, 2, 12]. In this work, we will use the term in situ
processing and focus on what we believe to be the distinctive features of this
work: control memory usage and the quantities to be computed.

##  3 In situ Particle Sorting to Build Trajectories

As described earlier, the main objective of our in situ analysis is to support
the calculation of the diffusion coefficients from important particle
properties such as energy and position. Because of the mass difference between
electrons and ions in the fusion plasma, we track the diffusion of erelectrons
and ions separately. Conceptually, each simulation time step is to update the
properties of plasma particles, such as position (recorded in toroidal angle,
poloidal angle, minor radius (r), etc.), velocity (v), energy (E), as well as
various flags such as the one used to select the particles for our diffusion
calculation to be explained later. This time-stepping behavior offers an
opportunity for us to examine the state of the particles and select those that
need to be tracked carefully for our diffusion study. Next, we describe the
three main steps: particle selection, trajectory building, and diffusion
calculation.

---
(a)
(b)
Figure 3: Particle tracing plots. (a) Distribution of ions in the 32 segments
along the separatrix. (b) The mean square displacement over time for dr, dE,
and vPar for electrons in the 4th quardrant of the separatrix.

###  3.1 Particle selection

Our initial attempt was to store statistical properties, at every step, into a
2D array for post processing. This required extra memory usage (for the
statistical data) in the simulation code, and additional time to gather and
compute these information at the simulation nodes. Crucially, this approach
will need a post-processing step to build particle trajectories to compute the
desired diffusion quantities. This approach requires a significant increase in
the memory required per particle as well as considerable time for computing
the statistics and storing these quantities to files. Overall, this was judged
to an expensive option.

As a more efficient alternative, we decided to select the relevant particles
and offload all processing tasks to another set of nodes as shown in Fig.
2(a). This approach allows the analysis nodes to perform complex calculations
without slowing down the simulation. We choose to send the relevant data
through the ADIOS I/O library [1] because this I/O library is already used by
XGC [8]. ADIOS uses the same API for a user code to either store data in a
local file system or send data to some (other) compute nodes. Depending where
is the data sent for analysis, the analysis process is variously termed in
situ processing, in transit processing, and so on. In this work, we use the
term of in situ processing to describe the distributed workflow. As in many
other in situ processing use cases, this approach reduces the dependencies
between simulation and analysis. It is a more effective way to conduct complex
analysis at high temporal resolution.

The particles of interest for our diffusion study are those with a high
likelihood of escaping magnetic confinement. The separatrix marks the boundary
where the magnetic field lines inside are closed while the magnetic field
lines outside are open. The charged particles, electrons and ions, generally
follow the magnetic field lines – inside separatrix, the particles mostly
follow the magnetic field lines and stay inside, while these outside of the
separatrix would likely to escape the tokamak. As such, the distance from the
separatrix is a good proxy for the likelihood of a particle escaping. The XGC
code has provided a special flag for measuring this distance and provides a
simple threshold on this distance measure along with additional physics-based
considerations (described next) for particle selection.

To compute the diffusion quantities effectively, we need to ensure the
particle trajectories captures are computed accurately. There are a few known
scenarios where the the computed properties such as position, velocity, and so
on, might not be accurate. For example, when a particle escapes and hits the
diverter plate, the computed properties such as position and velocity could
include sharp discontinuities that are as unrealistic. To deal with these
special cases, the XGC developers have added a separate particle property
known as the diffusion weights111Currently, there are three different weights:
w0, w1, and w2, where the unwanted particles have $w0=-1$..

---
(a)
(b)
(c)
Figure 4: (a) Outlines how a multi-processor analysis node removes particles
from trajectory building process. (b) Shows how the trajectory is built from
step-wise data. (c) An illustration of how a set of trajectories with 6 steps
are divided onto 3 MPI ranks.

###  3.2 Trajectory building

Recall that the diffusion quantities are computed from particle trajectories
and the trajectory information for each particle is produced from the XGC
simulation one time step at a time. After each simulation step, the new
positions and other properties become available; such information would be
added to the trajectories of selected particles. As mentioned above, XGC uses
flags to reflect each particle’s current status. To simplify the particle
tracking process, we currently keep only the trajectories whose starting
positions are within a certain distance from the separatrix. As the simulation
proceeds, more particles might drift near the separatrix, which could lead to
a growing number of trajectories to compute. At this time, we do not track
these that came near the separatrix at later time steps for our diffusion
calculations. This implies that at the analysis nodes, upon receiving data of
a new step, the first action is to trim the unwanted particles. Fig. 4(a)
outlines how trimming works. Because the particle ordering is random at each
step, we sort the trimmed data set by particle ID. At the end of the
simulation, the particle trajectories can be built from the sorted data, as
seen in Fig. 4(b).

The above trajectory building process is also a particle sorting process,
because the ultimate output could be regarded as the sorted list of particle
trajectories. In our use case, we keep the number of particles to be tracked
relatively small, even though we track the selected particles for every step
of the simulation, a global sorted list of particle IDs is still small enough
to be kept on each analysis rank. We use this global sorted list of IDs to
filter out unused particles at every step to keep the memory requirement
relatively low. In the current implementation, we use rank 0 to gather and
sort the particle IDs. For larger use cases where the sorting could not be
done with a single analysis node, we place to use a parallel sorting procedure
known as SDS-Sort [7].

At the end of the simulation, the analysis nodes have step-wise properties of
a set of sorted particles. The trajectory of each particle is built by
rearranging the data layout as seen in Fig. 4 (b). Although the size of the
traced particle set is fixed in our use case, the data size grows as the
number of time steps increases, and may not fit in a single node. A scalable
solution is to use a few MPI ranks to build the trajectories, as shown in Fig.
4(c). At the end of the simulation, this trajectory data set will be stored on
disk to be accessed for further exploration.

As an example, a simulation run on 64 Summit nodes (using 6 GPU per node) took
6 hours to finish 900 time steps. During this simulation, the number of tagged
electrons increased from 33k to 28 million. For ions, it went from 272k to 140
million. After trimming and sorting, the trajectory data is about 2 GB for
electrons and 17 GB for ions. The total time on the analysis node to build the
trajectory data sets is less than 2.5 hours using 16 MPI ranks on each node.
The in situ analysis would complete very shortly after the main simulation
code.

###  3.3 Diffusion calculation

With particle information of all steps ready, we now compute the diffusion
quantities. As illustrated in Fig. 1(b), the diffusion quantities are computed
per region along the separatrix. Let ptls be all the particles present in a
region. The diffusion coefficient for a property p (e.g. Energy, velocity) is
defined below (a slightly different formula for property $\psi$.)

$\displaystyle d(p)$ $\displaystyle=(MSQ(p)-M(p)^{2})/(\Delta t*steps)$
$\displaystyle d(\psi)$ $\displaystyle=(MSQ(\psi)-M(\psi)^{2})/(\Delta
t*steps*dpdrs^{2})s$

where $steps$ denote the number of steps taken by XGC, w0 is weight, and
$dpdrs$ is the normalized $\psi$. Furthermore, in the above equations MSQ(p)
and M(p) are:

$\displaystyle MSQ(p)=$
$\displaystyle\sum_{ptls}(\Delta(p)^{2}*w0)/\sum_{ptls}(w0)$ $\displaystyle
M(p)=$ $\displaystyle\sum_{ptls}(\Delta(p)*w0)/\sum_{ptls}(w0)$

The expression $MSQ(p)-M(p)^{2}$ in the above equations is also known as the
mean square displacement.

For our diffusion calculations, each quadrant of the separatrix is divided
into 8 regions. Fig. 2(b) illustrated these 8 regions in the fourth quadrant.
The actual computation procedure are programmed using python as a Jupyter
notebook. It reads in the ADIOS trajectory file, then gathers particles in
each region, computes the mean square displacement and diffusion coefficient
for given properties of particles over all time step, and finally performs the
visualization. For example, Fig. 3(a) shows the distribution of mean square
displacement of E (energy) of electrons at time step near the end of a 64 node
simulation run on the Oak Ridge Leadership Computing Facility (OLCF) Summit
[11] supercomputer. Fig. 3(b) shows how diffusion coefficients change in
regions 0-7 as time evolves.

---
(a)
(b)
Figure 5: (a): Mean square displacement (top) and diffusion coefficient
(bottom) are plotted for psi ($\psi$), E and vPar for ions at regions 0-7.
(b): Poloidal angle Angle View for electrons with the default view with range
from 0.2$\pi$ to 0.9$\pi$.

A region on the separatrix could also be specified through the poloidal
angles, where the initial location (angle 0) can either start at the X-point
of the separatrix, or at the horizontal direction (which is often the default
choice in most polar coordinate systems). Through the poloidal angel, the
whole separatrix has range [0, 2$\pi$]. We can compute the diffusion
coefficients, given a range of poloidal angle. For example, Fig.5(b) shows the
diffusion coefficients of $\psi$, E, vPar222The variable vPar is the velocity
component parallel to the magnetic field. of the electrons with range
[0.2$\pi$, 0.9$\pi$] using default angles.

##  4 Summary and Future Work

We have started an exploration to compute diffusion quantities for fusion
plasma through an in situ workflow. The diffusion of hot plasma particles
through the separatrix toward the diverter of a tokamak is suspected to be a
cause for the collapse of fusion plasma. Therefore, understanding the
diffusion process around the separatrix is important to achieve stable
magnetic confined fusion.

This work connects a state of the art simulation tool for understanding plasma
particles with a novel analysis capability using the ADIOS software for data
transport operations. Our exploration indicates that the in situ approach is
able to control the memory requirement while capturing the most important
particles relevant to the diffusion process.

As the collaboration with plasma physicists deepens, we anticipate the
requirements on particle selection, trajectory building, and diffusion
calculations would evolve and requiring the in situ processing capability to
evolve as well. We are looking forward to these changes that might lead to a
much better understanding of the particle diffusion process.

## Acknowledgements

For this research, LBNL and ORNL scientists were supported by the Exascale
Computing Project (17-SC-20-SC), a joint project of the U.S. Department of
Energy’s Office of Science and National Nuclear Security Administration. PPPL
scientists were supported by DOE FES and ASCR via the SciDAC project High-
fidelity Boundary Plasma Simulation, under Contract No. DE-AC02–09CH11466 to
Princeton University for Princeton Plasma Physics Laboratory. This research
used INCITE resources of the Oak Ridge Leadership Computing Facility, a DOE
Office of Science User Facility supported under Contract No. DE-
AC05-00OR22725, and of the National Energy Research Scientific Computing
Center (NERSC), a U.S. Department of Energy Office of Science User Facility
operated under Contract No. DE-AC02-05CH11231.

## References

  * [1] Adios github page.  https://github.com/ornladios/ADIOS.
  * [2] Andrew C. Bauer, Hasan Abbasi, James Ahrens, Hank Childs, Berk Geveci, Scott Klasky, Kenneth Moreland, Patrick O’Leary, Venkatram Vishwanath, Brad Whitlock, and E. W. Bethel.  In situ methods, infrastructures, and applications on high performance computing platforms.  Computer Graphics Forum, 2016.
  * [3] C.-S. Chang and S.-H. Ku et al.  Whole-volume integrated gyrokinetic simulation of plasma tur- bulence in realistic diverted-tokamak geometry.  In Journal of Physics: Conference Series, 180:012057, 2009.
  * [4] C. S. Chang, S. Klasky, J. Cummings, R. Samtaney, A. Shoshani, L. Sugiyama, D. Keyes, S. Ku, G. Park, S. Parker, N. Podhorszki, H. Strauss, H. Abbasi, M. Adams, R. Barreto, G. Bateman, K. Bennett, Y. Chen, E. D. Azevedo, C. Docan, S. Ethier, E. Feibush, L. Greengard, T. Hahm, F. Hinton, C. Jin, A. Khan, A. Kritz, P. Krsti, T. Lao, W. Lee, Z. Lin, J. Lofstead, P. Mouallem, M. Nagappan, A. Pankin, M. Parashar, M. Pindzola, C. Reinhold, D. Schultz, K. Schwan, D. Silver, A. Sim, D. Stotler, M. Vouk, M. Wolf, H. Weitzner, P. Worley, Y. Xiao, E. Yoon, and D. Zorin.  Toward a first-principles integrated simulation of Tokamak edge plasmas - art. no. 012042.  Scidac 2008: Scientific Discovery through Advanced Computing, 125:12042–12042, 2008.
  * [5] C.-S. Chang and S.-H. Ku.  Spontaneous rotation sources in a quiescent tokamak edge plasma.  Physics of Plasmas (1994-present), 15:062510, 2008.
  * [6] J. Dominski, J. Cheng, G. Merlo, V. Carey, R. Hager, L. Ricketson, J. Choi, S. Ethier, K. Germaschewski, and S.-H. Ku et al.  Spatial coupling of gyrokinetic simulations, a generalized scheme based on first-principles.  Physics of Plasmas, 28:022301, 2021.
  * [7] Bin Dong, Surendra Byna, and Kesheng Wu.  SDS-sort: Scalable dynamic skew-aware parallel sorting.  In Proceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing, HPDC’16, pages 57–68, New York, NY, USA, 2016. ACM.
  * [8] Junmin Gu, Greg Eisenhauer, Scott Klasky, Norbert Podhorszki, Ruonan Wang, and Kesheng Wu.  Exploring large all-flash storage system with scientific simulation.  In Proceedings of the 34th International Conference on Scientific and Statistical Database Management. SSDBM, 2022.
  * [9] G. T. A. Huijsmans, C. S. Chang, N. Ferraro, L. Sugiyama, F. Waelbroeck, X. Q. Xu, A. Loarte, and S. Futatani.  Modelling of edge localised modes and edge localised mode control.  Physics of Plasmas, 22(2):021805, 01 2015.
  * [10] Ralph Kube, Michael Churchill, Seung Hoe Ku, Jong Choi, and CS Chang.  Plasma transport by turbulent homoclinic tangles in diverted tokamak plasmas.  https://meetings.aps.org/Meeting/DPP22/Session/PP11.104, 2022.
  * [11] S. Oral, S.S. Vazhkudai, F. Wang, C. Zimmer, C. Brumgard, J. Hanley, G. Markomanolis, R. Miller, D. Leverman, S. Atchley, and V.V. Larrea.  End-to-end i/o portfolio for the summit supercomputing ecosystem.  In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’19, New York, NY, USA, 2019. Association for Computing Machinery.
  * [12] Franz Poeschel, Juncheng E, William F. Godoy, Norbert Podhorszki, Scott Klasky, Greg Eisenhauer, Philip E. Davis, Lipeng Wan, Ana Gainaru, and Junmin Gu et al.  Transitioning from file-based hpc workflows to streaming data pipelines with openpmd and adios2.  In Driving Scientific and Engineering Discoveries Through the Integration of Experiment, Big Data, and Modeling and Simulation, 2022.
  * [13] The ADIOS project.  https://www.olcf.ornl.gov/center-projects/adios/, circa 2018.  OLCF Website.
  * [14] F.Godoy William, Podhorszki Norbert, Wang Ruonan, Atkins Chuck, Eisenhauer Greg, Gu Junmin, Davis Philip, Choi Jong, Germaschewski Kai, Huck Kevin, Huebl Axel, Kim Mark, Kress James, Kurc Tahsin, Liu Qing, Logan Jeremy, Mehta Kshitij, Ostrouchov. George, Parashar Manish, Poeschel Franz, Pugmire David, Suchyta. Eric, Takahashi Keichi, Thompson Nick, Tsutsumi Seiji, Wan Lipeng, Wolf Matthew, Wu Kesheng, and Klasky Scott.  ADIOS 2: The adaptable input output system. a framework for high-performance data management.  SoftwareX, 12:100561, 2020.
  * [15] Matthew Wolf, Jong Choi, Greg Eisenhauer, Stéphane Ethier, Kevin Huck, Scott Klasky, Jeremy Logan, Allen Malony, Chad Wood, Julien Dominski, et al.  Scalable performance awareness for in situ scientific applications.  In 2019 15th International Conference on eScience (eScience), pages 266–276. IEEE, 2019.


# Quantifying Similarity between Relations with Fact Distribution

Weize Chen1 Hao Zhu1,2 Xu Han1 Zhiyuan Liu1 Maosong Sun1
1 Department of Computer Science and Technology, Tsinghua University, Beijing,
China
State Key Lab on Intelligent Technology and Systems
Institute for Artificial Intelligence
<EMAIL_ADDRESS><EMAIL_ADDRESS>
2 Carnegie Mellon University, Pittsburgh, PA, USA
<EMAIL_ADDRESS>
###### Abstract

We introduce a conceptually simple and effective method to quantify the
similarity between relations in knowledge bases. Specifically, our approach is
based on the divergence between the conditional probability distributions over
entity pairs. In this paper, these distributions are parameterized by a very
simple neural network. Although computing the exact similarity is in-
tractable, we provide a sampling-based method to get a good approximation.

We empirically show the outputs of our approach significantly correlate with
human judgments. By applying our method to various tasks, we also find that
(1) our approach could effectively detect redundant relations extracted by
open information extraction (Open IE) models, that (2) even the most
competitive models for relational classification still make mistakes among
very similar relations, and that (3) our approach could be incorporated into
negative sampling and softmax classification to alleviate these mistakes. The
source code and experiment details of this paper can be obtained from
https://github.com/thunlp/relation-similarity.

##  1 Introduction

††footnotetext: Author contributions: Hao Zhu designed the research; Weize
Chen prepared the data, and organized data annotation; Hao Zhu and Xu Han
designed the experiments; Weize Chen performed the experiments; Hao Zhu, Weize
Chen and Xu Han wrote the paper; Zhiyuan Liu and Maosong Sun proofread the
paper. Zhiyuan Liu is the corresponding author.

Relations111Sometimes relations are also named properties., representing
various types of connections between entities or arguments, are the core of
expressing relational facts in most general knowledge bases (KBs) Suchanek et
al. (2007); Bollacker et al. (2008). Hence, identifying relations is a crucial
problem for several information extraction tasks. Although considerable effort
has been devoted to these tasks, some nuances between similar relations are
still overlooked, (Table 1 shows an example); on the other hand, some distinct
surface forms carrying the same relational semantics are mistaken as different
relations. These severe problems motivate us to quantify the similarity
between relations in a more effective and robust method.

Sentence |  The crisis didn’t influence his two daughters OBJ and SUBJ.
---|---
Correct |  per:siblings
Predicted |  per:parents
Similarity Rank |  2

Table 1: An illustration of the errors made by relation extraction models. The
sentence contains obvious patterns indicating the two persons are siblings,
but the model predicts it as parents. We introduce an approach to measure the
similarity between relations. Our result shows “siblings” is the second most
similar one to “parents”. By applying this approach, we could analyze the
errors made by models, and help reduce errors.

In this paper, we introduce an adaptive and general framework for measuring
similarity of the pairs of relations. Suppose for each relation $r$, we have
obtained a conditional distribution, $P(h,t\mid r)$ ($h,t\in\mathcal{E}$ are
head and tail entities, and $r\in\mathcal{R}$ is a relation), over all head-
tail entity pairs given $r$. We could quantify similarity between a pair of
relations by the divergence between the conditional probability distributions
given these relations. In this paper, this conditional probability is given by
a simple feed-forward neural network, which can capture the dependencies
between entities conditioned on specific relations. Despite its simplicity,
the proposed network is expected to cover various facts, even if the facts are
not used for training, owing to the good generalizability of neural networks.
For example, our network will assign a fact a higher probability if it is
“logical”: e.g., the network might prefer an athlete has the same nationality
as same as his/her national team rather than other nations.

Intuitively, two similar relations should have similar conditional
distributions over head-tail entity pairs $P(\,h,t\mid r\,)$, e.g., the entity
pairs associated with be trade to and play for are most likely to be athletes
and their clubs, whereas those associated with live in are often people and
locations. In this paper, we evaluate the similarity between relations based
on their conditional distributions over entity pairs. Specifically, we adopt
Kullback–Leibler (KL) divergence of both directions as the metric. However,
computing exact KL requires iterating over the whole entity pair space
$\mathcal{E}\times\mathcal{E}$, which is quite intractable. Therefore, we
further provide a sampling-based method to approximate the similarity score
over the entity pair space for computational efficiency.

Besides developing a framework for assessing the similarity between relations,
our second contribution is that we have done a survey of applications. We
present experiments and analysis aimed at answering five questions:

(1) How well does the computed similarity score correlate with human judgment
about the similarity between relations? How does our approach compare to other
possible approaches based on other kinds of relation embeddings to define a
similarity? (§ 3.4 and § 5)

(2) Open IE models inevitably extract many redundant relations. How can our
approach help reduce such redundancy? (§ 6)

(3) To which extent, quantitatively, does best relational classification
models make errors among similar relations? (§ 7)

(4) Could similarity be used in a heuristic method to enhance negative
sampling for relation prediction? (§ 8)

(5) Could similarity be used as an adaptive margin in softmax-margin training
method for relation extraction? (§ 9)

Finally, we conclude with a discussion of valid extensions to our method and
other possible applications.

##  2 Learning Head-Tail Distribution

Just as introduced in § 1, we quantify the similarity between relations by
their corresponding head-tail entity pair distributions. Consider the typical
case that we have got numbers of facts, but they are still sparse among all
facts in the real world. How could we obtain a well-generalized distribution
over the whole space of possible triples beyond the training facts? This
section proposes a method to parameterize such a distribution.

###  2.1 Formal Definition of Fact Distribution

A fact is a triple $(h,r,t)\in\mathcal{E}\times\mathcal{R}\times\mathcal{E}$,
where $h$ and $t$ are called head and tail entities, $r$ is the relation
connecting them, $\mathcal{E}$ and $\mathcal{R}$ are the sets of entities and
relations respectively. We consider a score function
$F_{\theta}:\mathcal{E}\times\mathcal{R}\times\mathcal{E}\rightarrow\mathbb{R}$
maps all triples to a scalar value. As a special case, the function can be
factorized into the sum of two parts: $F_{\theta}(\,h,t;r\,)\triangleq
u_{\theta_{1}}(h;r)+u_{\theta_{2}}(t;h,r)$. We use $F_{\theta}$ to define the
unnormalized probability.

$\tilde{P}_{\theta}(\,h,t\mid r\,)\triangleq\exp F_{\theta}(\,h,r;t\,)$ (1)

for every triple $(\,h,r,t\,)$. The real parameter $\theta$ can be adjusted to
obtain difference distributions over facts.

In this paper, we only consider locally normalized version of $F_{\theta}$:

$\displaystyle u_{\theta_{1}}(h;r)$
$\displaystyle=\log\frac{\exp\tilde{u}_{\theta_{1}}(h;r)}{\sum_{h^{\prime}}\exp\tilde{u}_{\theta_{1}}(h^{\prime};r)},$
(2) $\displaystyle u_{\theta_{2}}(t;h,r)$
$\displaystyle=\log\frac{\exp\tilde{u}_{\theta_{2}}(t;h,r)}{\sum_{t^{\prime}}\exp\tilde{u}_{\theta_{2}}(t^{\prime};h,r)},$

where $\tilde{u}_{\theta_{1}}$ and $\tilde{u}_{\theta_{2}}$ are directly
parameterized by feed-forward neural networks. Through local normalization,
$\tilde{P}_{\theta}(\,h,t\mid r\,)$ is naturally a valid probability
distribution, as the partition function $\sum_{h,t}\exp
F_{\theta}(\,h,t;r\,)=1$. Therefore, $P_{\theta}(\,h,t\mid
r\,)=\tilde{P}_{\theta}(\,h,t\mid r\,)$.

###  2.2 Neural architecture design

Here we introduce our special design of neural networks. For the first part
and the second part, we implement the scoring functions introduced in equation
2 as

$\displaystyle\tilde{u}_{\theta_{1}}(h;r)$
$\displaystyle=\mathtt{MLP}_{\theta_{1}}(\bm{r})^{\top}\bm{h},$ (3)
$\displaystyle\tilde{u}_{\theta_{2}}(t;h,r)$
$\displaystyle=\mathtt{MLP}_{\theta_{2}}([\bm{h};\bm{r}])^{\top}\bm{t},$

where each $\mathtt{MLP}_{\theta}$ represents a multi-layer perceptron
composed of layers like $\bm{y}=\mathtt{relu}(\bm{W}\bm{x}+\bm{b})$,
$\bm{h},\bm{r}$, $\bm{t}$ are embeddings of $h,r$, $t$, and $\theta$ includes
weights and biases in all layers.

###  2.3 Training

Now we discuss the method to perform training. In this paper, we consider
joint training. By minimizing the loss function, we compute the model
parameters $\theta^{*}$:

$\displaystyle\theta^{*}$
$\displaystyle=\operatorname*{argmin}_{\theta}\mathcal{L}(G)$ (4)
$\displaystyle=\operatorname*{argmin}_{\theta}\sum_{(\,h,r,t\,)\in G}-\log
P_{\theta}(\,h,t\mid r\,),$

where $G\subset\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ is a set of
triples.222In our applications, the set of triples could be a knowledge base
or a set of triples in the training set etc. The whole set of parameters,
$\theta=\\{\theta_{1},\theta_{2},\\{\bm{e},\forall
e\in\mathcal{E}\\},\\{\bm{r},\forall r\in\mathcal{R}\\}\\}$. We train these
parameters by Adam optimizer Kingma and Ba (2014). Training details are shown
in Appendix C.

Relation Representation | Method | Similarity Quantification
---|---|---
Vectors | TransE Bordes et al. (2013) | $S(r_{1},r_{2})=\exp\left(\bm{r}_{1}^{\top}\bm{r}_{2}/\lVert\bm{r}_{1}\rVert_{2}\lVert\bm{r}_{2}\rVert_{2}\right)$
Vectors | DistMult Yang et al. (2015) | $S(r_{1},r_{2})=\exp\left(\bm{r}_{1}^{\top}\bm{r}_{2}/\lVert\bm{r}_{1}\rVert_{2}\lVert\bm{r}_{2}\rVert_{2}\right)$
Matrices | RESCAL Nickel et al. (2011) | $S(r_{1},r_{2})=\exp(\lVert M_{r_{1}}-M_{r_{2}}\rVert_{F})$
Angles | RotatE Sun et al. (2019) | $S(r_{1},r_{2})=\exp(-\sum_{i=1}^{n}\lvert\bm{r}_{1,i}-\bm{r}_{2,i}\rvert_{1})$
Probability Distribution | Ours | equation 6
Table 2: Methods to define a similarity function with different types of
relation representations

##  3 Quantifying Similarity

So far, we have talked about how to use neural networks to approximate the
natural distribution of facts. The center topic of our paper, quantifying
similarity, will be discussed in detail in this section.

###  3.1 Relations as Distributions

In this paper, we provide a probability view of relations by representing
relation $r$ as a probability distribution $P_{\theta^{*}}(\,h,t\mid r\,)$.
After training the neural network on a given set of triples, the model is
expected to generalize well on the whole
$\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ space.

Note that it is very easy to calculate $P_{\theta^{*}}(\,h,t\mid r\,)$ in our
model thanks to local normalization (equation 2). Therefore, we can compute it
by

$P_{\theta^{*}}(\,h,t\mid
r\,)=\exp(u_{\theta_{1}}(h;r)+u_{\theta_{2}}(t;h,r)).$ (5)

###  3.2 Defining Similarity

As the basis of our definition, we hypothesize that the similarity between
$P_{\theta^{*}}(\,h,t\mid r\,)$ reflects the similarity between relations.333§
5 provides empirical results to corroborate this hypothesis. For example, if
the conditional distributions of two relations put mass on similar entity
pairs, the two relations should be quite similar. If they emphasize different
ones, the two should have some differences in meaning.

Formally, we define the similarity between two relations as a function of the
divergence between the distributions of corresponding head-tail entity pairs:

$\displaystyle S(r_{1},r_{2})=g\Big{(}$ $\displaystyle
D_{\mathrm{KL}}\left(\left.\left.P_{\theta^{*}}(\,h,t\mid
r_{1}\,)\right|\right|P_{\theta^{*}}(\,h,t\mid r_{2}\,)\right),$ (6)
$\displaystyle D_{\mathrm{KL}}\left(\left.\left.P_{\theta^{*}}(\,h,t\mid
r_{2}\,)\right|\right|P_{\theta^{*}}(\,h,t\mid r_{1}\,)\right)\Big{)},$

where $D_{\mathrm{KL}}\left(\left.\left.\cdot\right|\right|\cdot\right)$
denotes Kullback–Leibler divergence,

$\displaystyle D_{\mathrm{KL}}\left(\left.\left.P_{\theta^{*}}(\,h,t\mid
r_{1}\,)\right|\right|P_{\theta^{*}}(\,h,t\mid r_{2}\,)\right)$ (7)
$\displaystyle=\mathbb{E}_{h,t\sim P_{\theta^{*}}(\,h,t\mid
r_{1}\,)}\log\frac{P_{\theta^{*}}(\,h,t\mid r_{1}\,)}{P_{\theta^{*}}(\,h,t\mid
r_{2}\,)}$

vice versa, and function $g(\cdot,\cdot)$ is a symmetrical function. To keep
the coherence between semantic meaning of “similarity” and our definition, $g$
should be a monotonically decreasing function. Through this paper, we choose
to use an exponential family444We view KL divergences as energy functions.
composed with max function, i.e., $g(x,y)=e^{-\max(x,y)}$. Note that by taking
both sides of KL divergence into account, our definition incorporates both the
entity pairs with high probability in $r_{1}$ and $r_{2}$. Intuitively, if
$P_{\theta^{*}}(\,h,t\mid r_{1}\,)$ mainly distributes on a proportion of
entities pairs that $P_{\theta^{*}}(\,h,t\mid r_{2}\,)$ emphasizes, $r_{1}$ is
only hyponymy of $r_{2}$. Considering both sides of KL divergence could help
model yield more comprehensive consideration. We will talk about the advantage
of this method in detail in § 3.4.

###  3.3 Calculating Similarity

Just as introduced in § 1, it is intractable to compute similarity exactly, as
involving $\mathcal{O}(|\mathcal{E}|^{2})$ computation. Hence, we consider the
monte-carlo approximation:

$\displaystyle D_{\mathrm{KL}}\left(\left.\left.P_{\theta^{*}}(\,h,t\mid
r_{1}\,)\right|\right|P_{\theta^{*}}(\,h,t\mid r_{2}\,)\right)$ (8)
$\displaystyle=$ $\displaystyle\mathbb{E}_{h,t\sim P_{\theta^{*}}(\,h,t\mid
r_{1}\,)}\log\frac{P_{\theta^{*}}(\,h,t\mid r_{1}\,)}{P_{\theta^{*}}(\,h,t\mid
r_{2}\,)}$ $\displaystyle\approx$
$\displaystyle\frac{1}{|\mathcal{S}|}\sum_{h,t\in\mathcal{S}}\log\frac{P_{\theta^{*}}(\,h,t\mid
r_{1}\,)}{P_{\theta^{*}}(\,h,t\mid r_{2}\,)},$

where $\mathcal{S}$ is a list of entity pairs sampled from
$P_{\theta^{*}}(\,h,t\mid r_{1}\,)$. We use sequential sampling555Sampling $h$
and $t$ at the same time requires $\mathcal{O}(|\mathcal{E}|^{2})$
computation, while sequential sampling requires only
$\mathcal{O}(|\mathcal{E}|)$ computation. to gain $\mathcal{S}$, which means
we first sample $h$ given $r$ from $u_{\theta_{1}}(h;r)$, and then sample $t$
given $h$ and $r$ from $u_{\theta_{2}}(t;h,r)$.666It seems to be a non-
symmetrical method, and sampling from the mixture of both forward and backward
should yield a better result. Surprisingly, in practice, sampling from single
direction works just as well as from both directions.

###  3.4 Relationship with other metrics

Previous work proposed various methods for representing relations as vectors
Bordes et al. (2013); Yang et al. (2015), as matrices Nickel et al. (2011),
even as angles Sun et al. (2019), etc. Based on each of these representations,
one could easily define various similarity quantification methods.777Taking
the widely used vector representations as an example, we can define the
similarity between relations based on cosine distance, dot product distance,
L1/L2 distance, etc. We show in Table 2 the best one of them in each category
of relation presentation.

Here we provide two intuitive reasons for using our proposed probability-based
similarity: (1) the capacity of a single fixed-size representation is limited
— some details about the fact distribution is lost during embedding; (2)
directly comparing distributions yields a better interpretability — you can
not know about how two relations are different given two relation embeddings,
but our model helps you study the detailed differences between probabilities
on every entity pair. footnote 8 provides an example. Although the two
relations talk about the same topic, they have different meanings. TransE
embeds them as vectors the closest to each other, while our model can capture
the distinction between the distributions corresponds to the two relations,
which could be directly noticed from the figure.

Figure 1: Head-tail entity pairs of relation “be an unincorporated community
in” (in blue) and “be a small city in” (in red) sampled from our fact
distribution model. The coordinates of the points are computed by t-sne Maaten
and Hinton (2008) on the concatenation of head and tail
embeddings888Embeddings used in this graph are from a trained TransE model..
The two larger blue and red points indicate the embeddings of these two
relations.

Figure 2: Spearman correlations between human judgment and models’ outputs.
The inter-subject correlation is also shown as a horizontal line with its
standard deviation as an error band. Our model shows the strongest positive
correlation with human judgment, and, in other words, the smallest margin with
human inter-subject agreement. Significance: ***/**/* := p < .001/.01/.05.

##  4 Dataset Construction

We show the statistics of the dataset we use in Table 3, and the construction
procedures will be introduced in this section.

###  4.1 Wikidata

In Wikidata Vrandečić and Krötzsch (2014), facts can be described as (Head
item/property, Property, Tail item/property). To construct a dataset suitable
for our task, we only consider the facts whose head entity and tail entity are
both items. We first choose the most common 202 relations and 120000 entities
from Wikidata as our initial data. Considering that the facts containing the
two most frequently appearing relations (P2860: cites, and P31: instance of)
occupy half of the initial data, we drop the two relations to downsize the
dataset and make the dataset more balanced. Finally, we keep the triples whose
head and tail both come from the selected 120000 entities as well as its
relation comes from the remaining 200 relations.

###  4.2 ReVerb Extractions

ReVerb Fader et al. (2011) is a program that automatically identifies and
extracts binary relationships from English sentences. We use the extractions
from running ReVerb on Wikipedia999http://reverb.cs.washington.edu/. We only
keep the relations appear more than 10 times and their corresponding triples
to construct our dataset.

###  4.3 FB15K and TACRED

FB15K Bordes et al. (2013) is a subset of freebase. TACRED Zhang et al. (2017)
is a large supervised relation extraction dataset obtained via crowdsourcing.
We directly use these two dataset, no extra processing steps were applied.

##  5 Human Judgments

Following Miller and Charles (1991); Resnik (1999) and the vast amount of
previous work on semantic similarity, we ask nine undergraduate subjects to
assess the similarity of 360 pairs of relations from a subset of Wikidata
Vrandečić and Krötzsch (2014)101010Wikidata provides detailed descriptions to
properties (relations), which could help subjects understand the relations
better. that are chosen to cover from high to low levels of similarity. In our
experiment, subjects were asked to rate an integer similarity score from 0 (no
similarity) to 4 (perfectly the same)111111The detailed instruction is
attached in the Appendix F. for each pair. The inter-subject correlation,
estimated by leaving-one-out method Weiss and Kulikowski (1991), is r =
$0.763$, standard deviation = $0.060$. This important reference value (marked
in Figure 2) could be seen as the highest expected performance for machines
Resnik (1999).

To get baselines for comparison, we consider other possible methods to define
similarity functions, as shown in Table 2. We compute the correlation between
these methods and human judgment scores. As the models we have chosen are the
ones work best in knowledge base completion, we do expect the similarity
quantification approaches based on them could measure some degree of
similarity. As shown in Figure 2, the three baseline models could achieve
moderate ($0.1\text{--}0.5$) positive correlation. On the other hand, our
model shows a stronger correlation ($0.63$) with human judgment, indicating
that considering the probability over whole entity pair space helps to gain a
similarity closer to human judgments. These results provide evidence for our
claim raised in § 3.2.

##  6 Redundant Relation Removal

Open IE extracts concise token patterns from plain text to represent various
relations between entities, e.g.,, (Mark Twain, was born in, Florida). As Open
IE is significant for constructing KBs, many effective extractors have been
proposed to extract triples, such as Text-Runner Yates et al. (2007), ReVerb
Fader et al. (2011), and Standford Open IE Angeli et al. (2015). However,
these extractors only yield relation patterns between entities, without
aggregating and clustering their results. Accordingly, there are a fair amount
of redundant relation patterns after extracting those relation patterns.
Furthermore, the redundant patterns lead to some redundant relations in KBs.

Recently, some efforts are devoted to Open Relation Extraction (Open RE) Lin
and Pantel (2001); Yao et al. (2011); Marcheggiani and Titov (2016); ElSahar
et al. (2017), aiming to cluster relation patterns into several relation types
instead of redundant relation patterns. Whenas, these Open RE methods adopt
distantly supervised labels as golden relation types, suffering from both
false positive and false negative problems on the one hand. On the other hand,
these methods still rely on the conventional similarity metrics mentioned
above.

In this section, we will show that our defined similarity quantification could
help Open IE by identifying redundant relations. To be specific, we set a toy
experiment to remove redundant relations in KBs for a preliminary comparison
(§ 6.1). Then, we evaluate our model and baselines on the real-world dataset
extracted by Open IE methods (§ 6.2). Considering the existing evaluation
metric for Open IE and Open RE rely on either labor-intensive annotations or
distantly supervised annotations, we propose a metric approximating recall and
precision evaluation based on operable human annotations for balancing both
efficiency and accuracy.

Triple Set | $|\mathcal{R}|$ | $|\mathcal{E}|$ | #Fact | Section
---|---|---|---|---
Wikidata | 188 | 112,946 | 426,067 |  § 5 and § 6.1
ReVerb Extractions | 3,736 | 194,556 | 266,645 | § 6.2
FB15K | 1,345 | 14,951 | 483,142 |  § 7.1 and § 8
TACRED | 42 | 29,943 | 68,124 |  § 7.2 and § 9

Table 3: Statistics of the triple sets used in this paper.

###  6.1 Toy Experiment

In this subsection, we propose a toy environment to verify our similarity-
based method. Specifically, we construct a dataset from Wikidata121212The
construction procedure is shown in § 4.1. and implement Chinese restaurant
process131313Chinese restaurant process is shown in Appendix B. to split every
relation in the dataset into several sub-relations. Then, we filter out those
sub-relations appearing less than 50 times to eventually get 1165 relations.
All these split relations are regarded as different ones during training, and
then different relation similarity metrics are adopted to merge those sub-
relations into one relation. As Figure 2 shown that the matrices-based
approach is less effective than other approaches, we leave this approach out
of this experiment. The results are shown in Table 4.

Method | P | R | $F_{1}$
---|---|---|---
Vectors (TransE) | 0.28 | 0.14 | 0.18
Vectors (DistMult) | 0.44 | 0.41 | 0.42
Angles | 0.48 | 0.43 | 0.45
Ours | 0.65 | 0.50 | 0.57
Table 4: The experiment results on the toy dataset show that our metric based
on probability distribution significantly outperforms other relation
similarity metrics.

###  6.2 Real World Experiment

In this subsection, we evaluate various relation similarity metrics on the
real-world Open IE patterns. The dataset are constructed by ReVerb. Different
patterns will be regarded as different relations during training, and we also
adopt various relation similarity metrics to merge similar relation patterns.
Because it is nearly impossible to annotate all pattern pairs for their
merging or not, meanwhile it is also inappropriate to take distantly
supervised annotations as golden results. Hence, we propose a novel metric
approximating recall and precision evaluation based on minimal human
annotations for evaluation in this experiment.

#### Approximating Recall and Precision

##### Recall

Recall is defined as the yielding fraction of true positive instances over the
total amount of real positive141414Often called relevant in information
retrieval field. instances. However, we do not have annotations about which
pairs of relations are synonymous. Crowdsourcing is a method to obtain a large
number of high-quality annotations. Nevertheless, applying crowdsourcing is
not trivial in our settings, because it is intractable to enumerate all
synonymous pairs in the large space of relation (pattern) pairs
$\mathcal{O}(|\mathcal{R}|^{2})$ in Open IE. A promising method is to use
rejection sampling by uniform sampling from the whole space, and only keep the
synonymous ones judged by crowdworkers. However, this is not practical either,
as the synonymous pairs are sparse in the whole space, resulting in low
efficiency. Fortunately, we could use normalized importance sampling as an
alternative to get an unbiased estimation of recall.

######  Theorem 1.

151515See proof in Appendix A

Suppose every sample $x\in X$ has a label $f(x)\in\\{0,1\\}$, and the model to
be evaluated also gives its prediction $\hat{f}(x)\in\\{0,1\\}$. The recall
can be written as

$Recall=\mathbb{E}_{x\sim U}\mathbb{I}[\hat{f}(x)=1],$ (9)

where $U$ is the uniform distribution over all samples with $f(x)=1$. If we
have a proposal distribution $q(x)$ satisfying $\forall
x,f(x)=1\wedge\hat{f}(x)=1\Rightarrow q(x)\neq 0$, we get an unbiased
estimation of recall:

$Recall\approx\sum_{i=1}^{n}\mathbb{I}[\hat{f}(x_{i})=1]\hat{w}_{i},$ (10)

where $\hat{w}_{i}$ is a normalized version of
$w_{i}=\frac{\mathbb{I}[f(x_{i})=1]}{\tilde{q}(x_{i})}$, where $\tilde{q}$ is
the unnormalized version of q, and $\\{x_{i}\\}_{i=1}^{n}$ are i.i.d. drawn
from $q(x)$.

##### Precision

Similar to equation 9, we can write the expectation form of precision:

$Precision=\mathbb{E}_{x\sim U^{\prime}}\mathbb{I}[f(x)=1],$ (11)

where $U^{\prime}$ is the uniform distribution over all samples with
$\hat{f}(x)=1$. As these samples could be found out by performing models on
it. We can simply approximate precision by Monte Carlo Sampling:

$Precision\approx\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}[f(x_{i})=1],$ (12)

where $\\{x_{i}\\}_{i=1}^{n}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}U^{\prime}$.

In our setting, $x=(r_{1},r_{2})\in\mathcal{R}\times\mathcal{R}$, $f(x)=1$
means $r_{1}$ and $r_{2}$ are the same relations, $\hat{f}(x)=1$ means
$S(r_{1},r_{2})$ is larger than a threshold $\lambda$.

Figure 3: Precision-recall curve on Open IE task comparing our similarity
function with vector-based and angle-based similarity. Error bar represents
$95\%$ confidential interval. Bootstraping is used to calculate the
confidential interval.

(a) FB15K

(b) TACRED

Figure 4: Similarity rank distributions of distracting relations on different
tasks and datasets. Most of the distracting relations have top similarity
rank. Distracting relations are, as defined previously, the relations have a
higher rank in the relation classification result than the ground truth.

Figure 5: Improvement of using similarity in a heuristic method for negative
sampling. MRR denotes the mean reciprocal rank.

#### Results

The results on the ReVerb Extractions dataset that we constructed are
described in Figure 3. To approximate recall, we use the similarity scores as
the proposal distribution $\tilde{q}$. 500 relation pairs are then drawn from
$\tilde{q}$. To approximate precision, we set thresholds at equal intervals.
At each threshold, we uniformly sample 50 to 100 relation pairs whose
similarity score given by the model is larger than the threshold. We ask 15
undergraduates to judge whether two relations in a relation pair have the same
meaning. A relation pair is viewed valid only if 8 of the annotators annotate
it as valid. We use the annotations to approximate recall and precision with
equation 10 and equation 12. Apart from the confidential interval of precision
shown in the figure, the largest $95\%$ confidential interval among thresholds
for recall is $0.04$161616The figure is shown in Figure 6. From the result, we
could see that our model performs much better than other models’ similarity by
a very large margin.

##  7 Error Analysis for Relational Classification

In this section, we consider two kinds of relational classification tasks: (1)
relation prediction and (2) relation extraction. Relation prediction aims at
predicting the relationship between entities with a given set of triples as
training data; while relation extraction aims at extracting the relationship
between two entities in a sentence.

###  7.1 Relation Prediction

We hope to design a simple and clear experiment setup to conduct error
analysis for relational prediction. Therefore, we consider a typical method
TransE Bordes et al. (2013) as the subject as well as FB15K Bordes et al.
(2013) as the dataset. TransE embeds entities and relations as vectors, and
train these embeddings by minimizing

$\mathcal{L}=\sum_{(h,r,t)\in\mathcal{D}}[d(\bm{h}+\bm{r},\bm{t})-d(\bm{h}^{\prime}+\bm{r}^{\prime},\bm{t}^{\prime})+\gamma]_{+},$
(13)

where $\mathcal{D}$ is the set of training triples, $d(\cdot,\cdot)$ is the
distance function, $(h^{\prime},r^{\prime},t^{\prime})$171717Note that only
head and tail entities are changed in the original TransE when doing link
prediction. But changing $r^{\prime}$ results in better performance when doing
relation prediction. is a negative sample with one element different from
$(h,r,t)$ uniformly sampled from
$\mathcal{E}\times\mathcal{R}\times\mathcal{E}$, and $\gamma$ is the margin.

During testing, for each entity pair $(h,t)$, TransE rank relations according
to $d(\bm{h}+\bm{r},\bm{t})$. For each $(h,r,t)$ in the test set, we call the
relations with higher rank scores than $r$ distracting relations. We then
compare the similarity between the golden relation and distracting relations.
Note that some entity pairs could correspond to more than one relations, in
which case we just do not see them as distracting relations.

###  7.2 Relation Extraction

For relation extraction, we consider the supervised relation extraction
setting and TACRED dataset Zhang et al. (2017). As for the subject model, we
use the best model on TACRED dataset — position-aware neural sequence model.
This method first passes the sentence into an LSTM and then calculate an
attention sum of the hidden states in the LSTM by taking positional features
into account. This simple and effective method achieves the best in TACRED
dataset.

###  7.3 Results

Figure 5 shows the distribution of similarity ranks of distracting relations
of the above mentioned models’ outputs on both relation prediction and
relation extraction tasks. From Figures 4(a) and 4(b), we could observe the
most distracting relations are the most similar ones, which corroborate our
hypothesis that even the best models on these tasks still make mistakes among
the most similar relations. This result also highlights the importance of a
heuristic method for guiding models to pay more attention to the boundary
between similar relations. We also try to do the negative sampling with
relation type constraints, but we see no improvement compared with uniform
sampling. The details of negative sampling with relation type constraints are
presented in Appendix E.

| Model | P | R | $F_{1}$
---|---|---|---|---
Traditional | Patterns | 86.9 | 23.2 | 36.6
| LR | 73.5 | 49.9 | 59.4
Neural | CNN | 75.6 | 47.5 | 58.3
| CNN-PE | 70.3 | 54.2 | 61.2
| SDP-LSTM Xu et al. (2015) | 66.3 | 52.7 | 58.7
| LSTM | 65.7 | 59.9 | 62.7
| PA-LSTM Zhang et al. (2017) | 65.7 | 64.5 | 65.1
Neural+Ours | PA-LSTM (Softmax-Margin Loss) | 68.5 | 64.7 | 66.6

Table 5: Improvement of using similarity in softmax-margin loss.

##  8 Similarity and Negative Sampling

Based on the observation presented in § 7.3, we find out that similar
relations are often confusing for relation prediction models. Therefore,
corrupted triples with similar relations can be used as high-quality negative
samples.

For a given valid triple $(h,r,t)$, we corrupt the triple by substituting $r$
with $r^{\prime}$ with the probability,

$p=\frac{S(r,r^{\prime})^{1/\alpha}}{\sum_{r^{\prime\prime}\in{\mathcal{R}\backslash\\{r\\}}}S(r,r^{\prime\prime})^{1/\alpha}},$
(14)

where $\alpha$ is the temperature of the exponential function, the bigger the
$\alpha$ is, the flatter the probability distribution is. When the temperature
approaches infinite, the sampling process reduces to uniform sampling.

In training, we set the initial temperature to a high level and gradually
reduce the temperature. Intuitively, it enables the model to distinguish among
those obviously different relations in the early stage and gives more and more
confusing negative triples as the training processes to help the model
distinguish the similar relations. This can be also viewed as a process of
curriculum learningBengio et al. (2009), the data fed to the model gradually
changes from simple negative triples to hard ones.

We perform relation prediction task on FB15K with TransE. Following Bordes et
al. (2013), we use the "Filtered" setting protocol, i.e., filtering out the
corrupted triples that appear in the dataset. Our sampling method is shown to
improve the model’s performance, especially on Hit@1 (Figure 5). Training
details are described in Appendix C.

##  9 Similarity and Softmax-Margin Loss

Similar to § 8, we find out that relation extraction models often make wrong
preditions on similar relations. In this section, we use similarity as an
adaptive margin in softmax-margin loss to improve the performance of relation
extraction models.

As shown in Gimpel and Smith (2010), Softmax-Margin Loss can be expressed as

$\displaystyle\mathcal{L}=$
$\displaystyle\sum_{i=1}^{n}-\theta^{T}f(x^{(i)},r^{(i)})+$ (15)
$\displaystyle\log\sum_{r\in\mathcal{R}(x^{(i)})}\exp\\{\theta^{T}f(x^{(i)},r)+\text{cost}(r^{(i)},r)\\},$

where $\mathcal{R}(x)$ denotes a structured output space for $x$, and $\langle
x^{(i)},r^{(i)}\rangle$ is $i^{th}$ example in training data.

We can easily incorporate similarity into cost function
$\text{cost}(r^{(i)},r)$. In this task, we define the cost function as $\alpha
S(r^{(i)},r)$, where $\alpha$ is a hyperparameter.

Intuitively, we give a larger margin between similar relations, forcing the
model to distinguish among them, and thus making the model perform better. We
apply our method to Position-aware Attention LSTM (PA-LSTM)Zhang et al.
(2017), and Table 5 shows our method improves the performance of PA-LSTM.
Training details are described in Appendix C.

##  10 Related Works

As many early works devoted to psychology and linguistics, especially those
works exploring semantic similarity Miller and Charles (1991); Resnik (1999),
researchers have empirically found there are various different categorizations
of semantic relations among words and contexts. For promoting research on
these different semantic relations, Bejar et al. (1991) explicitly defining
these relations and Miller (1995) further systematically organize rich
semantic relations between words via a database. For identifying correlation
and distinction between different semantic relations so as to support learning
semantic similarity, various methods have attempted to measure relational
similarity Turney (2005, 2006); Zhila et al. (2013); Pedersen (2012); Rink and
Harabagiu (2012); Mikolov et al. (2013b, a).

With the ongoing development of information extraction and effective
construction of KBs Suchanek et al. (2007); Bollacker et al. (2008); Bizer et
al. (2009), relations are further defined as various types of latent
connections between objects more than semantic relations. These general
relations play a core role in expressing relational facts in the real world.
Hence, there are accordingly various methods proposed for discovering more
relations and their facts, including open information extraction Brin (1998);
Agichtein and Gravano (2000); Ravichandran and Hovy (2002); Banko et al.
(2007); Zhu et al. (2009); Etzioni et al. (2011); Saha et al. (2017) and
relation extraction Riedel et al. (2013); Liu et al. (2013); Zeng et al.
(2014); Santos et al. (2015); Zeng et al. (2015); Lin et al. (2016), and
relation prediction Bordes et al. (2013); Wang et al. (2014); Lin et al.
(2015b, a); Xie et al. (2016).

For both semantic relations and general relations, identifying them is a
crucial problem, requiring systems to provide a fine-grained relation
similarity metric. However, the existing methods suffer from sparse data,
which makes it difficult to achieve an effective and stable similarity metric.
Motivated by this, we propose to measure relation similarity by leveraging
their fact distribution so that we can identify nuances between similar
relations, and merge those distant surface forms of the same relations,
benefitting the tasks mentioned above.

##  11 Conclusion and Future Work

In this paper, we introduce an effective method to quantify the relation
similarity and provide analysis and a survey of applications. We note that
there are a wide range of future directions: (1) human prior knowledge could
be incorporated into the similarity quantification; (2) similarity between
relations could also be considered in multi-modal settings, e.g., extracting
relations from images, videos, or even from audios; (3) by analyzing the
distributions corresponding to different relations, one can also find some
“meta-relations” between relations, such as hypernymy and hyponymy.

## Acknowledgements

This work is supported by the National Natural Science Foundation of China
(NSFC No. 61572273, 61532010), the National Key Research and Development
Program of China (No. 2018YFB1004503). Chen and Zhu is supported by Tsinghua
University Initiative Scientific Research Program, and Chen is also supported
by DCST Student Academic Training Program. Han is also supported by 2018
Tencent Rhino-Bird Elite Training Program.

## References

  * Agichtein and Gravano (2000) Eugene Agichtein and Luis Gravano. 2000.  Snowball: Extracting relations from large plain-text collections.  In _Proceedings of JCDL_ , pages 85–94.
  * Angeli et al. (2015) Gabor Angeli, Melvin Jose Johnson Premkumar, and Christopher D Manning. 2015.  Leveraging linguistic structure for open domain information extraction.  In _Proceedings of ACL_ , pages 344–354.
  * Banko et al. (2007) Michele Banko, Michael J Cafarella, Stephen Soderland, Matthew Broadhead, and Oren Etzioni. 2007.  Open information extraction from the web. In _Proceedings of IJCAI_ , pages 2670–2676.
  * Bejar et al. (1991) Isaac I Bejar, Roger Chaffin, and Susan E Embretson. 1991.  Cognitive and psychometric analysis of analogical problem solving.
  * Bengio et al. (2009) Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. 2009\.  Curriculum learning.  In _Proceedings of ICML_ , pages 41–48.
  * Bizer et al. (2009) Christian Bizer, Jens Lehmann, Georgi Kobilarov, Sören Auer, Christian Becker, Richard Cyganiak, and Sebastian Hellmann. 2009.  Dbpedia-a crystallization point for the web of data.  _Web Semantics: science, services and agents on the world wide web_ , 7:154–165.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008\.  Freebase: a collaboratively created graph database for structuring human knowledge.  In _Proceedings of SIGMOD_ , pages 1247–1250.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Proceedings of NIPS_ , pages 2787–2795.
  * Brin (1998) Sergey Brin. 1998.  Extracting patterns and relations from the world wide web.  In _Proceedings of WWW_ , pages 172–183.
  * ElSahar et al. (2017) Hady ElSahar, Elena Demidova, Simon Gottschalk, Christophe Gravier, and Frederique Laforest. 2017.  Unsupervised open relation extraction.  In _Proceedings of ESWC_ , pages 12–16.
  * Etzioni et al. (2011) Oren Etzioni, Anthony Fader, Janara Christensen, Stephen Soderland, and Mausam Mausam. 2011.  Open information extraction: the second generation.  In _Proceedings of IJCAI_ , pages 3–10.
  * Fader et al. (2011) Anthony Fader, Stephen Soderland, and Oren Etzioni. 2011.  Identifying relations for open information extraction.  In _Proceedings of EMNLP_ , pages 1535–1545.
  * Gimpel and Smith (2010) Kevin Gimpel and Noah A Smith. 2010.  Softmax-margin crfs: Training log-linear models with cost functions.  In _Proceedings of NAACL_ , pages 733–736.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Lin and Pantel (2001) Dekang Lin and Patrick Pantel. 2001.  Dirt@ sbt@ discovery of inference rules from text.  In _Proceedings of SIGKDDs_ , pages 323–328.
  * Lin et al. (2015a) Yankai Lin, Zhiyuan Liu, Huanbo Luan, Maosong Sun, Siwei Rao, and Song Liu. 2015a.  Modeling relation paths for representation learning of knowledge bases.  In _Proceedings of EMNLP_ , pages 705–714.
  * Lin et al. (2015b) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015b.  Learning entity and relation embeddings for knowledge graph completion.  In _Proceedings of AAAI_ , pages 2181–2187.
  * Lin et al. (2016) Yankai Lin, Shiqi Shen, Zhiyuan Liu, Huanbo Luan, and Maosong Sun. 2016.  Neural relation extraction with selective attention over instances.  In _Proceedings of ACL_ , pages 2124–2133.
  * Liu et al. (2013) ChunYang Liu, WenBo Sun, WenHan Chao, and Wanxiang Che. 2013.  Convolution neural network for relation extraction.  In _Proceedings of ICDM_ , pages 231–242.
  * Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-sne.  _JMLR_ , 9:2579–2605.
  * Marcheggiani and Titov (2016) Diego Marcheggiani and Ivan Titov. 2016.  Discrete-state variational autoencoders for joint discovery and factorization of relations.  _TACL_ , 4:231–244.
  * Mikolov et al. (2013a) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013a.  Efficient estimation of word representations in vector space.  In _Proceedings of ICLR_.
  * Mikolov et al. (2013b) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013b.  Distributed representations of words and phrases and their compositionality.  In _Proceedings of NIPS_ , pages 3111–3119.
  * Miller (1995) George A Miller. 1995.  Wordnet: a lexical database for english.  _Communications of the ACM_ , 38:39–41.
  * Miller and Charles (1991) George A Miller and Walter G Charles. 1991.  Contextual correlates of semantic similarity.  _Language and cognitive processes_ , 6:1–28.
  * Nickel et al. (2011) Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011.  A three-way model for collective learning on multi-relational data.  In _Proceedings of ICML_ , pages 809–816.
  * Owen (2013) Art B. Owen. 2013.  _Monte Carlo theory, methods and examples_.
  * Pedersen (2012) Ted Pedersen. 2012.  Duluth: Measuring degrees of relational similarity with the gloss vector measure of semantic relatedness.  In _Proceedings of SemEval 2012_ , pages 497–501.
  * Ravichandran and Hovy (2002) Deepak Ravichandran and Eduard Hovy. 2002.  Learning surface text patterns for a question answering system.  In _Proceedings of ACL_ , pages 41–47.
  * Resnik (1999) Philip Resnik. 1999.  Semantic similarity in a taxonomy: An information-based measure and its application to problems of ambiguity in natural language.  _Journal of artificial intelligence research_ , 11:95–130.
  * Riedel et al. (2013) Sebastian Riedel, Limin Yao, Andrew McCallum, and Benjamin M Marlin. 2013.  Relation extraction with matrix factorization and universal schemas.  In _Proceedings of NAACL_ , pages 74–84.
  * Rink and Harabagiu (2012) Bryan Rink and Sanda Harabagiu. 2012.  Utd: Determining relational similarity using lexical patterns.  In _Proceedings of SemEval 2012_ , pages 413–418.
  * Saha et al. (2017) Swarnadeep Saha, Harinder Pal, et al. 2017.  Bootstrapping for numerical open ie.  In _Proceedings of ACL_ , volume 2, pages 317–323.
  * Santos et al. (2015) Cicero Nogueira dos Santos, Bing Xiang, and Bowen Zhou. 2015.  Classifying relations by ranking with convolutional neural networks.  In _Proceedings of ACL-IJCNLP_ , pages 626–634.
  * Suchanek et al. (2007) Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007.  Yago: a core of semantic knowledge.  In _Proceedings of WWW_ , pages 697–706.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In _Proceedings of ICLR_.
  * Turney (2005) Peter D Turney. 2005.  Measuring semantic similarity by latent relational analysis.  In _Proceedings of IJCAI_ , pages 1136–1141.
  * Turney (2006) Peter D Turney. 2006.  Similarity of semantic relations.  _Computational Linguistics_ , 32:379–416.
  * Vrandečić and Krötzsch (2014) Denny Vrandečić and Markus Krötzsch. 2014.  Wikidata: a free collaborative knowledgebase.  _Communications of the ACM_ , 57:78–85.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014.  Knowledge graph embedding by translating on hyperplanes.  In _Proceedings of AAAI_ , pages 1112–1119.
  * Weiss and Kulikowski (1991) Sholom M Weiss and Casimir A Kulikowski. 1991.  _Computer systems that learn: classification and prediction methods from statistics, neural nets, machine learning, and expert systems_.
  * Xie et al. (2016) Ruobing Xie, Zhiyuan Liu, and Maosong Sun. 2016.  Representation learning of knowledge graphs with hierarchical types. In _Proceedings of IJCAI_ , pages 2965–2971.
  * Xu et al. (2015) Yan Xu, Lili Mou, Ge Li, Yunchuan Chen, Hao Peng, and Zhi Jin. 2015.  Classifying relations via long short term memory networks along shortest dependency paths.  In _Proceedings of EMNLP_ , pages 1785–1794.
  * Yang et al. (2015) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding entities and relations for learning and inference in knowledge bases.  In _Proceedings of ICLR_.
  * Yao et al. (2011) Limin Yao, Aria Haghighi, Sebastian Riedel, and Andrew McCallum. 2011.  Structured relation discovery using generative models.  In _Proceedings of EMNLP_ , pages 1456–1466.
  * Yates et al. (2007) Alexander Yates, Michael Cafarella, Michele Banko, Oren Etzioni, Matthew Broadhead, and Stephen Soderland. 2007.  Textrunner: open information extraction on the web.  In _Proceedings of NAACL_ , pages 25–26.
  * Zeng et al. (2015) Daojian Zeng, Kang Liu, Yubo Chen, and Jun Zhao. 2015.  Distant supervision for relation extraction via piecewise convolutional neural networks.  In _Proceedings of EMNLP_ , pages 1753–1762.
  * Zeng et al. (2014) Daojian Zeng, Kang Liu, Siwei Lai, Guangyou Zhou, and Jun Zhao. 2014.  Relation classification via convolutional deep neural network.  In _Proceedings of COLING_ , pages 2335–2344.
  * Zhang et al. (2017) Yuhao Zhang, Victor Zhong, Danqi Chen, Gabor Angeli, and Christopher D Manning. 2017\.  Position-aware attention and supervised data improve slot filling.  In _Proceedings of EMNLP_ , pages 35–45.
  * Zhila et al. (2013) Alisa Zhila, Wen-tau Yih, Christopher Meek, Geoffrey Zweig, and Tomas Mikolov. 2013\.  Combining heterogeneous models for measuring relational similarity.  In _Proceedings of NAACL_ , pages 1000–1009.
  * Zhu et al. (2009) Jun Zhu, Zaiqing Nie, Xiaojiang Liu, Bo Zhang, and Ji-Rong Wen. 2009.  Statsnowball: a statistical approach to extracting entity relationships.  In _Proceedings of WWW_ , pages 101–110.

##  Appendix A Proofs to theorems in the paper

###### Proof.

$\displaystyle Recall$
$\displaystyle=\frac{\sum_{x}\mathbb{I}[f(x)=1\wedge\hat{f}(x)=1]}{\sum_{x}\mathbb{I}[f(x)=1]}$
(16)
$\displaystyle=\sum_{x}\frac{\mathbb{I}[f(x)=1\wedge\hat{f}(x)=1]}{\sum_{x^{\prime}}\mathbb{I}[f(x^{\prime})=1]}$
$\displaystyle=\sum_{x}\frac{\mathbb{I}[f(x)=1]\mathbb{I}[\hat{f}(x)=1]}{\sum_{x^{\prime}}\mathbb{I}[f(x^{\prime})=1]}$
$\displaystyle=\sum_{x}\frac{\mathbb{I}[f(x)=1]}{\sum_{x^{\prime}}\mathbb{I}[f(x^{\prime})=1]}\mathbb{I}[\hat{f}(x)=1]$
$\displaystyle=\sum_{x}P_{U}(x)\mathbb{I}[\hat{f}(x)=1]$
$\displaystyle=\mathbb{E}_{x\sim U}\mathbb{I}[\hat{f}(x)=1]$

If we have a proposal distribution $q(x)$ satisfying $\forall
x,f(x)=1\wedge\hat{f}(x)=1\Rightarrow q(x)\neq 0$, then equation 16 can be
further written as

$\displaystyle Recall$ $\displaystyle=\mathbb{E}_{x\sim
q}\mathbb{I}[\hat{f}(x)=1]\frac{P_{U}(x)}{q(x)}$ (17)

Sometimes, it’s hard for us to compute normalized probability $q$. To tackle
this problem, consider self-normalized importance sampling as an unbiased
estimation Owen (2013),

$\displaystyle\mathbb{E}_{x\sim
q}\mathbb{I}[\hat{f}(x)=1]\frac{P_{U}(x)}{q(x)}$ (18)
$\displaystyle\approx\frac{\sum_{i=1}^{n}\mathbb{I}[\hat{f}(x_{i})=1]P_{U}(x_{i})/q(x_{i})}{\sum_{i=1}^{n}P_{U}(x_{i})/q(x_{i})}$
$\displaystyle=\frac{\sum_{i=1}^{n}\mathbb{I}[\hat{f}(x_{i})=1]w_{i}}{\sum_{i=1}^{n}w_{i}}\hskip
10.0pt(w_{i}=\frac{\mathbb{I}[f(x_{i})=1]}{\tilde{q}(x_{i})})$
$\displaystyle=\sum_{i=1}^{n}\mathbb{I}[\hat{f}(x_{i})=1]\hat{w}_{i},$

where $\hat{w}_{i}$ is the normalized version of $w$. ∎

##  Appendix B Chinese Restaurant Process

Specifically, for a relation $r$ with currently $m$ sub-relations, we turn it
to a new sub-relation with probability

$p=\frac{\alpha}{\alpha+n+1}$ (19)

or to the $k^{th}$ existing sub-relation with probability

$p=\frac{n_{k}}{\alpha+n+1}$ (20)

where $n_{k}$ is the size of $k^{th}$ existing sub-relation, $n$ is the sum of
the number of all sub-relationships of $r$, and $\alpha$ is a hyperparameter,
in which case we use $\alpha=1$.

##  Appendix C Training Details

In Wikidata and ReVerb Extractions dataset, we manually split a validation
set, assuring every entity and relation appears in validation set also appears
in training set. While minimizing loss on the training set, we observe the
loss on the validation set and stop training as validation loss stops to
decrease. Before training our model on any dataset, we use the entity
embeddings and relation embeddings produced by TransE on the dataset as the
pretrained embeddings for our model.

###  C.1 Training Details on Negative Sampling

The sampling is launched with an initial temperature of 8192. The temperature
drops to half every 200 epochs and remains stable once it hits 16.
Optimization is performed using SGD, with a learning rate of 1e-3.

###  C.2 Training Details on Softmax-Margin Loss

The sampling is launching with an initial temperature of 64. The temperature
drops by 20% per epoch, and remains stable once it hits 16. The alpha we use
is 9. Optimization is performed using SGD, with a learning rate of 1.

##  Appendix D Recall Standard Deviation

Figure 6: The recall standard deviation of different models.

As is shown in Figure 6, the max recall standard deviation for our model is
0.4, and 0.11 for TransE.

##  Appendix E Negative Samplilng with Relation Type Constraints

In FB15K, if two relations have same prefix, we regard them as belonging to a
same type, e.g., both /film/film/starring./film/performance/actor and
/film/actor/film./film/performance/film have prefix film, they belong to same
type. Similar to what is mentioned in § 8, we expect the model first to learn
to distinguish among obviously different relations, and gradually learn to
distinguish similar relations. Therefore, we conduct negative sampling with
relation type constraints in two ways.

###  E.1 Add Up Two Uniform Distribution

For each triple $(h,r,t)$, we have two uniform distribution $U_{all}$ and
$U_{type}$. $U_{all}$ is the uniform distribution over all the relations
except for those appear with $(h,t)$ in the knowledge base, and $U_{type}$ is
the uniform distribution over the relations of the same type as $r$. When
corrupting the triple, we sample $r^{\prime}$ from the distribution:

$U=\alpha U_{all}+(1-\alpha)U_{type},$ (21)

where $\alpha$ is a hyperparameter. We set $\alpha$ to 1 at the beginning of
training, and every $k$ epochs, $\alpha$ will be multiplied by decrease rate
$\gamma$. We do grid search for $k\in\\{50,70,100\\}$ and
$\gamma\in\\{0.9,0.95,0.98\\}$, but no improvement is observed.

###  E.2 Add Weight

We speculate that the unsatisfactory result produced by adding up two uniform
distribution is because that for those types with few relations in it, a small
change of $\alpha$ will result in a significant change in $U$. Therefore, when
sampling a negative $r^{\prime}$, we add weights to relations that are of the
same type as $r$ instead. Concretely, we substitute $r$ with $r^{\prime}$ with
probability $p$, which can be calculated as:

$p=\begin{cases}\frac{1+\epsilon}{N}&r^{\prime}\in\mathcal{T}(r)\\\
\frac{1}{N}&\text{otherwise}\end{cases}$ (22)

where $\mathcal{T}(r)$ denotes all the relations that are the same type as
$r$, $\epsilon$ is a hyperparameter and $N$ is a normalizing constant. We set
$\epsilon$ to 0 at the beginning of training, and every $k$ epochs, $\epsilon$
will increase by $\gamma$. We do grid search for $k\in\\{50,70,100\\}$ and
$\gamma\in{0.5,1}$, still no improvement is observed.

##  Appendix F Wikidata annotation guidance

We show the guidance provided for the annotators here.

  * •

A pair of relations should be marked as 4 points if the two relations are only
two different expressions for a certain meaning.

Example: (study at, be educated at)

  * •

A pair of relations should be marked as 3 points if the two relations are
describing a same topic, and the entities that the two relations connect are
of same type respectively.

Example: (be the director of, be the screenwriter of), both relations relate
to movie, and the types of the entities they connect are both (person, movie).

  * •

A pair of relations should be marked as 2 points if the two relations are
describing a same topic, but the entities that the two relations connect are
of different type respectively.

Example: (be headquartered in, be founded in), both relations relate to
organization, but the types of the entities they connect are different, i.e.,
(company, location) and (company, time)

  * •

A pair of relations should be marked as 1 points if the two relations do not
meet the conditions above but still have semantic relation.

Example: (be the developer of, be the employer of)

  * •

A pair of relations should be marked as 0 points if the two relations do not
have any connection.

Example: (be a railway station locates in, be published in)