A Semantic Matching Energy Function for Learning with Multi-relational
    Data
Authors: Xavier Glorot, Antoine Bordes, Jason Weston, Yoshua Bengio
ICLR 2013

Abstract: Large-scale relational learning becomes crucial for handling the huge amounts of structured data generated daily in many application domains ranging from computational biology or information retrieval, to natural language processing. In this paper, we present a new neural network architecture designed to embed multi-relational graphs into a flexible continuous vector space in which the original data is kept and enhanced. The network is trained to encode the semantics of these graphs in order to assign high probabilities to plausible components. We empirically show that it reaches competitive performance in link prediction on standard datasets from the literature.

arXiv:1301.3485v2  [cs.LG]  21 Mar 2013
A Semantic Matching Energy Function for Learning
with Multi-relational Data
Xavier Glorot(1), Antoine Bordes(2), Jason Weston(3), Yoshua Bengio(1)
(1) DIRO, Université de Montréal, Montréal, QC, Canada – {glorotxa,bengioy}@iro.umontreal.ca
(2) CNRS - Heudiasyc, Université de Technologie de Compiègne, France – bordesan@hds.utc.fr
(3) Google, New York, NY , USA– jweston@google.com
1 Introduction
Multi-relational data, which refers to graphs whose nodes r epresent entities and edges correspond to
relations that link these entities, plays a pivotal role in m any areas such as recommender systems, the
Semantic Web, or computational biology. Relations are modeled as triplets of the form (subject, relation,
object), where a relation either models the relationship be tween two entities or between an entity and
an attribute value; relations are thus of several types. In s pite of their appealing ability for representing
complex data, multi-relational graphs remain complicated to manipulate for several reasons (noise, het-
erogeneity, large-scale dimensions, etc.), and conveniently represent, summarize or de-noise this kind of
data is now a central challenge in statistical relational learning [2].
In this work, we propose a new model to learn multi-relationa l semantics, that is, to encode multi-
relational graphs into representations that capture the in herent complexity in the data, while seamlessly
deﬁning similarities among entities and relations and prov iding predictive power. Our work is based
on an original energy function, which is trained to assign lo w energies to plausible triplets of a multi-
relational graph. This energy function, termed semantic matching energy , relies on a compact distributed
representation: all elements (entity and relation type) ar e represented into the same relatively low (e.g.
50) dimensional embedding vector space. The embeddings are learnt by a neural network whose partic-
ular architecture and training process force them to capture the structure implicit in the training data and
generalize the graph formed from training triplets. Unlike in previous work [4, 6, 5, 3], in this model,
relation types are modeled similarly as entities. In this wa y, entities can also play the role of relation
type, as in natural language for instance, and this requires less parameters when the number of relation
types grows. We show empirically that this model achieves co mpetitive results on benchmark tasks of
link prediction, i.e., generalizing outside of the set of given valid triplets.
2 Semantic Matching Energy Function
This work considers multi-relational databases as graph mo dels. To each individual node of the graph
corresponds an element of the database, which we term anentity, and each link deﬁnes arelation between
entities. Relations are directed and there are typically se veral different kinds of relations. Let C denote
the dictionary which includes all entities and relation types, and let R ⊂ C be the subset of entities which
are relation types. A relation is denoted by a triplet ( lhs, rel, rhs), where lhs is the left entity, rhs the
right one and rel the type of relation between them.
2.1 Main ideas
The main ideas behind our semantic matching energy function are the following.
• Named symbolic entities (entities and relation types) are associated with a d-dimensional vector
space, termed the “embedding space”. The ith entity is assigned a vector Ei ∈ Rd. Note that more
general mappings from an entity to its embedding are possible.
• The semantic matching energy value associated with a particular triplet (lhs, rel, rhs) is computed
by a parametrized function E that starts by mapping all symbols to their embeddings and th en
combines them in a structured fashion. Our model is termed “semantic matching” because E relies
on a matching criterion computed between both sides of the triplet.
• The energy function E is optimized to be lower for training examples than for other possible
conﬁgurations of symbols.
2.2 Neural network parametrization
The energy function E (denoted SME) is encoded using a neural network, whose architecture ﬁrst pro-
cesses each entity in parallel, like in siamese networks [1] . The intuition is that the relation type should
ﬁrst be used to extract relevant components from each argume nt’s embedding, and put them in a space
where they can then be compared.
(1) Each symbol of the input triplet (lhs, rel, rhs) is mapped to its embeddingElhs, Erel, Erhs ∈ Rd.
(2) The embeddings Elhs and Erel respectively associated with the lhs and rel arguments are used to
construct a new relation-dependent embedding Elhs(rel) for the lhs in the context of the relation
type represented by Erel, and similarly for the rhs: Elhs(rel) = gleft (Elhs, Erel) and Erhs(rel) =
gright (Erhs, Erel), where gleft and gright are parametrized functions whose parameters are tuned
during training. The dimension of Elhs(rel) and Erhs(rel), which we denote p, is low-dimensional
but not necessarily equal to d, the dimension of the entity embedding space.
(3) The energy is computed by "matching" the transformed emb eddings of the left-hand and right-
hand sides: E((lhs, rel, rhs)) = h(Elhs(rel), Erhs(rel)), h is a dot product in our experiments.
We studied two options for the g functions, which lead to two versions of SME:
• Linear form (denoted SME(linear)), in this case g functions are simply linear layers:
Elhs(rel) = gleft (Elhs, Erel) = Wl1E⊺
lhs + Wl2E⊺
rel + b⊺
l .
Erhs(rel) = gright (Erhs, Erel) = Wr1E⊺
rhs + Wr2E⊺
rel + b⊺
r .
with Wl1, Wl2, Wr1, Wr2 ∈ Rp× d, bl, br ∈ Rp and E⊺ denotes the transpose of E. This leads to
the energy: E((lhs, rel, rhs)) = − (Wl1E⊺
lhs + Wl2E⊺
rel + b⊺
l )⊺ (Wr1E⊺
rhs + Wr2E⊺
rel + b⊺
r ).
• Bilinear form (denoted SME(bilinear)), g functions are using 3-modes tensors as core weights:
Elhs(rel) = gleft (Elhs, Erel) = ( Wl ¯× 3E⊺
rel) E⊺
lhs + b⊺
l .
Erhs(rel) = gright (Erhs, Erel) = ( Wr ¯× 3E⊺
rel) E⊺
rhs + b⊺
r .
with Wl, Wr ∈ Rp× d× d (weights) and bl, br ∈ Rp (biases). ¯× 3 denotes the n-mode vector-tensor
product along the 3rd mode. This leads to the following form for the energy: E((lhs, rel, rhs)) =
− ((Wl ¯× 3E⊺
rel) E⊺
lhs + b⊺
l )⊺ ((Wr ¯× 3E⊺
rel) E⊺
rhs + b⊺
r ).
Table 1: Statistics of datasets used in this paper.
Dataset Nb. of relation Nb. of Nb. of observed % valid relations
types entities relations in obs. ones
UMLS 49 135 893,025 0.76
Kinships 26 104 281,216 3.84
Nations 56 14 11,191 22.9
To train the parameters of the energy function E we loop over all of the training data resources and
use stochastic gradient descent with a ranking objective inspired by [7].
3 Empirical Evaluation
To evaluate against existing methods, we performed link prediction experiments on benchmarks from the
literature, whose statistics are in Table 1.
The link prediction task consists in predicting whether two entities should be connected by a given
relation type. This is useful for completing missing values of a graph, forecasting the behavior of a
network, etc. but also to assess the quality of a representat ion. We evaluate our model on UMLS,
Nations and Kinships, following the setting introduced in [ 4]. The standard evaluation metric is area
under the precision-recall curve (AUC). Table 2 presents results of SME along with those of RESCAL,
MRC, IRM, CP (CANDECOMP-PARAFAC) andLFM, which have been extracted from [5, 3].
The linear formulation of SME is outperformed by SME(bilinear) on all three tasks. The largest
differences for Nations and Kinships indicate that, for the se problems, a joint interaction between both
lhs, rel and rhs is crucial to represent the data well: relations cannot be si mply decomposed as a
sum of bigrams. This is particularly true for the complex kin ship systems of the Alyawarra. On the
contrary, interactions within the UMLS network can be repre sented by simply considering the various
(entity,entity) and (entity,relation type) bigrams. Comp ared to other methods, SME(bilinear) performs
similarly to LFM on UMLS but is slightly outperfomed on Nations. On Kinships, it is outperformed by
CP, RESCAL and LFM: on this dataset with complex ternary interactions, either the training process
of the tensor factorization methods, based on reconstructi on, or the combination of bigram and trigram
interactions seems to be beneﬁcial compared to our predicti ve approach. Compared to MRC, which is
not using a matrix-based encoding, SME(bilinear) is highly competitive.
Table 2: Comparisons of area under the precision-recall curve (AUC) for link prediction.
Method UMLS Nations Kinships
SME(linear) 0.983 ± 0.004 0.777 ± 0.025 0.149 ± 0.003
SME(bilinear) 0.985 ± 0.003 0.865 ± 0.015 0.894 ± 0.011
LFM 0.990 ± 0.003 0.909 ± 0.009 0.946 ± 0.005
RESCAL 0.98 0.84 0.95
CP 0.95 0.83 0.94
MRC 0.98 0.75 0.85
IRM 0.70 0.75 0.66
Even if experimental results on these benchmarks are mixed, it is worth noting that, contrary to all
previous methods, SME models relation types as vectors, lyi ng in the same space as entities. From a
conceptual viewpoint, this is powerful, since it models any relation types as a standard entity (and vice-
versa). Hence, SME is the only method that could be directly a pplied on data for which any entity can
also create relationships between other entities.
Acknowledgements
This work was supported by the French ANR (EVEREST-12-JS02-005-01), the Pascal2 European NoE,
the DARPA DL Program, NSERC, CIFAR, the Canada Research Chairs, and Compute Canada.
References
[1] Jame Bromley, Jim W. Bentz, Léon Bottou, Isabelle Guyon, Yann Le Cun, C. Moore, Eduard Säckinger, and
Roopak Shah. Signature veriﬁcation using a siamese time del ay neural network. International Journal of
P attern Recognition and Artiﬁcial Intelligence , 7(4), 1993.
[2] Lise Getoor and Ben Taskar. Introduction to Statistical Relational Learning (Adaptiv e Computation and
Machine Learning) . The MIT Press, 2007.
[3] Rodolphe Jenatton, Nicolas Le Roux, Antoine Bordes, and Guillaume Obozinski. A latent factor model for
highly multi-relational data. In Advances in Neural Information Processing Systems 25 . 2012.
[4] Charles Kemp, Joshua B. Tenenbaum, Thomas L. Grifﬁths, T akeshi Yamada, and Naonori Ueda. Learning
systems of concepts with an inﬁnite relational model. In Proceedings of the 21st national conference on
Artiﬁcial intelligence - V olume 1 , AAAI’06, pages 381–388. AAAI Press, 2006.
[5] Maximilian Nickel, V olker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-
relational data. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference
on Machine Learning (ICML-11) , ICML ’11, pages 809–816. ACM, 2011.
[6] Ilya Sutskever, Ruslan Salakhutdinov, and Josh Tenenbaum. Modelling relational data using bayesian clustered
tensor factorization. In Adv . in Neur . Inf. Proc. Syst. 22 , 2009.
[7] Jason Weston, Samy Bengio, and Nicolas Usunier. Large sc ale image annotation: learning to rank with joint
word-image embeddings. Machine Learning , 81:21–35, 2010.


Peer review:
[Review]:
Semantic Matching Energy Function for Learning with Multi-Relational Data

Paper Summary

This paper deals with learning an energy model over 3-way relationships. Each entity in the relation is associated a low dimensional representation and a neural network associate a real value to each representation triplet. The learning algorithm relies on an online ranking loss. Two models are proposed a linear model and a bilinear model.

Review Summary

The paper is clear and reads well. Its use of the ranking loss function to this problem is an interesting proposition. It could give more details on the ranking loss and the training procedure. The experiments could also be more thorough. My main concern however is that references to a co-author own work have been omitted. This omission means that the authors pretend not to know that a model with better reported performance exists. This should be discouraged and I will recommend the rejection of the paper.

Review

This paper is part of the recent effort of using distributed representation and various loss function for learning relational models. Papers focusing on this line of research include work from A. Bordes, J. Weston and Y. Bengio:
- A Latent Factor Model for Highly Multi-relational Data (NIPS 2012).
  Rodolphe Jenatton, Nicolas Le Roux, Antoine Bordes and Guillaume Obozinski.
- Learning Structured Embeddings of Knowledge Bases (AAAI 2011). 
  Antoine Bordes, Jason Weston, Ronan Collobert and Yoshua Bengio.

The variations among this paper mainly involves  
- model regularization (low rank, parameter tying...)
- loss function

Regarding regularization, your proposition, Jenatton et al, and RESCAL are highly related. Basically your bilinear model seems to introduce a rank constrain on the 3D tensor representing all the relation {R_k, forall k} as in RESCAL notation. Basically your bilinar model decomposes R_k = (E_{rel,k} W_l) (W_r E_{rel,k})^T while the NIPS2012 model decomposes R_k as a linear combination of rank one matrices shared accross relations. Like Jenatton et al, you brake the symetry of the left and right relations.

Regarding loss, RESCAL uses MSE, Jenatton et al uses logistic loss and you use a ranking loss.

This differences result in different AUCs. Jenatton et al is always better, RESCAL and your model are close. Given that Jenatton et al and RESCAL precede your submission. I feel it is necessary to check one thing at a time, i.e. training a model parameterized like RESCAL / Jenatton et al / yours with all three losses. This would give the best combination. This could give an empirical advantage to your ideas (either parameterization or ranking loss) over Jenatton et al.

Given that your model is worse in terms of AUC compared to Jenatton et al. I feel that you should at least explain why and maybe highlight some other advantages of your approach. I am disappointed that you do not refer to Jenatton et al: you know about this paper (shared co-author), the results on the same data are better and you do not even mention it.

Typos/Details

Intro: unlike in previous work -> put citation here.
2.2 (2) even if it remains low dimensional, nothing forces the dimension of ... -> barely understandable rephrase this sentence.