summaries: This paper proposes to combine the neuro-symbolic concept learner for visual reasoning from language (NS-CL; Mao et al., 2019) with recent unsupervised approaches to learning object-centric representations such as MONet (Burgess et al., 2019) and Slot-Attention (Locatello et al., 2020). While NS-CL normally relies on pre-trained object-detectors (in a supervised fashion) to extract visual representations, the proposed combination (dubbed LORL) use MONet or Slot Attention for this. By additionally back-propagating error signals from language-driven visual reasoning tasks obtained via NS-CL into MONet/Slot-Attention, it is shown how LORL is better able at learning object-centric representations and perform instance segmentation.

summaries: The paper proposes a framework for object-centric representation learning with additional language supervision such as e.g. questions and answers, denoted as Language-mediated, Object-centric Representation Learning (LORL). The authors combine two ideas from prior work, the unsupervised object-centric representation learning and the neural-symbolic concept learning, in one architecture. The model obtains object representations by learning to reconstruct the input image (as in MONet and Slot Attention). The learned representations are used as input to the neural-symbolic program executor, which learns to answer questions about objects. The entire model is trained in three stages: first the reconstruction objective, then the QA objective, and, finally, jointly. Experiments on two datasets demonstrate that the obtained object segmentations have better quality that those of the original unsupervised models. The learned representations are also shown to be effective in several other down-stream tasks.

summaries: This paper proposed an interesting idea that uses language to learn the concept and aid downstream tasks such as segmentation and referential expression interpretation. The authors combine the unsupervised segmentation method (MONet and Slot Attention) with neural symbolic concept learning (NS-CL). By joint training these two objectives, the authors show improvements in the object segmentation and several downstream tasks.

abstractText: We present Language-mediated, Object-centric Representation Learning (LORL), a paradigm for learning disentangled, object-centric scene representations from vision and language. LORL builds upon recent advances in unsupervised object segmentation, notably MONet and Slot Attention. While these algorithms learn an object-centric representation just by reconstructing the input image, LORL enables them to further learn to associate the learned representations to concepts, i.e., words for object categories, properties, and spatial relationships, from language input. These object-centric concepts derived from language facilitate the learning of object-centric representations. LORL can be integrated with various unsupervised segmentation algorithms that are language-agnostic. Experiments show that the integration of LORL consistently improves the object segmentation performance of MONet and Slot Attention on two datasets via the help of language. We also show that concepts learned by LORL, in conjunction with segmentation algorithms such as MONet, aid downstream tasks such as referring expression comprehension.

authors:
Daniel M Bear
Chaofei Fan
Damian Mrowca
Yunzhu Li
Seth Alter
Aran Nayebi
Jeremy Schwartz
Li Fei-Fei
Jiajun Wu
Joshua B Tenenbaum

title: Learning physical graph representations from visual scenes

title: How Children Learn the Meanings of Words

venue: MIT press,

authors:
Christopher P Burgess
Loic Matthey
Nicholas Watters
Rishabh Kabra
Irina Higgins
Matt Botvinick
Alexander Lerchner

title: Monet: Unsupervised scene decomposition and representation

authors:
Eric Crawford
Joelle Pineau

title: Spatially invariant unsupervised object detection with convolutional neural networks

venue: In AAAI,

authors:
Martin Engelcke
Adam R. Kosiorek
Oiwi Parker Jones
Ingmar Posner

title: Genesis: Generative scene inference and sampling with object-centric latent representations

venue: In ICML,

authors:
SM Eslami
Nicolas Heess
Theophane Weber
Yuval Tassa
Koray Kavukcuoglu
Geoffrey E Hinton

title: Attend, infer, repeat: Fast scene understanding with generative models

venue: NeurIPS,

authors:
Fartash Faghri
David J Fleet
Jamie Ryan Kiros
Sanja Fidler

title: Vse++: Improving visual-semantic embeddings with hard negatives

venue: In BMVC,

authors:
Vikash Goel
Jameson Weng
Pascal Poupart

title: Unsupervised video object segmentation for deep reinforcement learning

venue: In NeurIPS,

authors:
Klaus Greff
Antti Rasmus
Mathias Berglund
Tele Hao
Harri Valpola
Jürgen Schmidhuber

title: Tagger: Deep unsupervised perceptual grouping

authors:
Klaus Greff
Sjoerd van Steenkiste
Jürgen Schmidhuber

title: Neural expectation maximization

authors:
Klaus Greff
Raphaël Lopez Kaufman
Rishabh Kabra
Nick Watters
Christopher Burgess
Daniel Zoran
Loic Matthey
Matthew Botvinick
Alexander Lerchner

title: Multi-object representation learning with iterative variational inference

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In CVPR,

authors:
Lawrence Hubert
Phipps Arabie

title: Comparing partitions

venue: Journal of classification,

authors:
Justin Johnson
Andrej Karpathy
Li Fei-Fei

title: Densecap: Fully convolutional localization networks for dense captioning

authors:
Justin Johnson
Bharath Hariharan
Laurens van der Maaten
Li Fei-Fei
C Lawrence Zitnick
Ross Girshick

title: CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning

venue: In CVPR, 2017a

authors:
Justin Johnson
Bharath Hariharan
Laurens van der Maaten
Judy Hoffman
Li Fei-Fei
C Lawrence Zitnick
Ross Girshick

title: Inferring and executing programs for visual reasoning

venue: In ICCV, 2017b

venue: In ICLR,

authors:
Diederik P. Kingma
Max Welling

title: Auto-encoding variational bayes

authors:
Thomas Kipf
Elise van der Pol
Max Welling

title: Contrastive learning of structured world models

authors:
Adam R. Kosiorek
Hyunjik Kim
Ingmar Posner
Yee Whye Teh

title: Sequential attend, infer, repeat: Generative modelling of moving objects

authors:
Zhixuan Lin
Yi-Fu Wu
Skand Vishwanath Peri
Weihao Sun
Gautam Singh
Fei Deng
Jindong Jiang
Sungjin Ahn

title: Space: Unsupervised object-oriented scene representation via spatial attention and decomposition

authors:
Runtao Liu
Chenxi Liu
Yutong Bai
Alan L Yuille

title: Clevr-ref+: Diagnosing visual reasoning with referring expressions

authors:
Francesco Locatello
Dirk Weissenborn
Thomas Unterthiner
Aravindh Mahendran
Georg Heigold
Jakob Uszkoreit
Alexey Dosovitskiy
Thomas Kipf

title: Object-centric learning with slot attention

authors:
Jiayuan Mao
Chuang Gan
Pushmeet Kohli
Joshua B. Tenenbaum
Jiajun Wu

title: The neurosymbolic concept learner: Interpreting scenes, words, and sentences from natural supervision

authors:
Kaichun Mo
Shilin Zhu
Angel X Chang
Li Yi
Subarna Tripathi
Leonidas J Guibas
Hao Su

title: Partnet: A large-scale benchmark for fine-grained and hierarchical part-level 3d object understanding

authors:
M. Nazarczuk
K. Mikolajczyk

title: Shop-vrb: A visual reasoning benchmark for object perception

venue: In ICRA,

authors:
Mihir Prabhudesai
H.F. Tung
Syed Ashar Javed
Maximilian Sieb
Adam W. Harley
K. Fragkiadaki

title: Embodied language grounding with 3d visual feature representations

title: Objective criteria for the evaluation of clustering methods

venue: Journal of the American Statistical association,

authors:
Zhou Ren
Hailin Jin
Zhe Lin
Chen Fang
Alan Yuille

title: Joint image-text representation by gaussian visual-semantic embedding

venue: In ACM MM,

authors:
Olaf Ronneberger
Philipp Fischer
Thomas Brox

title: U-net: Convolutional networks for biomedical image segmentation

venue: In MICCAI,

authors:
Karl Stelzner
Robert Peharz
Kristian Kersting

title: Faster attend-infer-repeat with tractable probabilistic models

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Rishi Veerapaneni
John D Co-Reyes
Michael Chang
Michael Janner
Chelsea Finn
Jiajun Wu
Joshua Tenenbaum
Sergey Levine

title: Entity abstraction in visual model-based reinforcement learning

venue: CoRL,

authors:
Gert Westermann
Denis Mareschal

title: From perceptual to language-mediated categorization

venue: Philosophical Transactions of the Royal Society B: Biological Sciences,

authors:
Hao Wu
Jiayuan Mao
Yufeng Zhang
Yuning Jiang
Lei Li
Weiwei Sun
Wei-Ying Ma

title: Unified visual-semantic embeddings: Bridging vision and language with structured meaning representations

authors:
Jiajun Wu
Joshua B Tenenbaum
Pushmeet Kohli

title: Neural scene de-rendering

title: Object individuation and object identity in infancy: The role of spatiotemporal information, object property information, and language

venue: Acta psychologica,

title: Sortal concepts, object individuation, and language

venue: Trends in Cognitive Sciences,

authors:
Jianwei Yang
Jiasen Lu
Stefan Lee
Dhruv Batra
Devi Parikh

title: Visual curiosity: Learning to ask questions to learn visual recognition

venue: In CoRL,

authors:
Kexin Yi
Jiajun Wu
Chuang Gan
Antonio Torralba
Pushmeet Kohli
Josh Tenenbaum

title: Neuralsymbolic vqa: Disentangling reasoning from vision and language understanding

title: All three operations output a distribution over possible answers. The second argument y is either a word or number, such as TRUE, white, or 4. The Equal operation computes the probability of X=y. In LORL, models are trained to maximize the output probability. B HYPERPARAMETERS For optimization hyperparameters

title: Referring expression comprehension

heading: 1 INTRODUCTION

text:
Cognitive studies show that human infants develop object individuation skill from diverse sources of information: spatial-temporal information, object property information, and language (Xu, 1999; 2007; Westermann & Mareschal, 2014). Specifically, young infants develop object-based attention that disentangles the motion and location of objects from their visual appearance features. Later on, they can leverage the knowledge acquired through word learning to solve the problem of object individuation: words provide clues about object identity and type. The general picture from cognitive science is that object perception and language co-develop in support of one another (Bloom, 2002).
Our long-term goal is to endow machines with similar abilities. In this paper, we focus on how language may support object segmentation. Many recent works have studied the problem of unsupervised object representation learning, though without language. As an example, factorized, object-centric scene representations have been used in various kinds of prediction (Goel et al., 2018), reasoning (Yi et al., 2018; Mao et al., 2019), and planning tasks (Veerapaneni et al., 2020), but they have not considered the role of language and how it may help object representation learning.
As a concrete example, consider the input images shown in Fig. 1 and the paired questions. From language, we can learn to associate concepts, such as black, pan, and legs, with the referred object’s visual appearance. Further, language provides cues about how an input scene should be segmented into individual objects: a wrong parsing of the input scene will lead to an incorrect answer to the question. We can learn from such failure that the handle belongs to the frying pan (Fig. 1a) and the chair has four legs (Fig. 1b).
Motivated by these observations, we propose a computational learning paradigm, Language-mediated, Object-centric Representation Learning (LORL), associating learned object-centric representations to their visual appearance (masks) in images, and to concepts—words for object properties such as color, shape, and material—as provided in language. Here the language input can be either descriptive sentences or question-answer pairs. LORL requires no annotations on object masks, categories, or properties during the learning process.
In LORL, four modules are jointly trained. The first is an image encoder, learning to encode an image into factorized, object-centric representations. The second is an image decoder, learning to
reconstruct masks for individual objects from the learned representations by reconstructing the input. These two modules share the same formulation as recent unsupervised object segmentation research, and may be realized as methods such as MONet (Burgess et al., 2019) and Slot Attention (Locatello et al., 2020).
The third module in LORL is a pre-trained semantic parser that translates the input sentence into a semantic, executable program, where each concept (i.e., words for object properties such as ‘red’) is associated with a vector space embedding. Finally, the last module, a neural-symbolic program executor, takes the object-centric representation from Module 1, intermediate representations from Module 2, and concept embeddings and the semantic program from Module 3 as input, and outputs an answer if the language input is a question, or TRUE/FALSE if it’s a descriptive sentence. The correctness of the executor’s output and the quality of reconstructed images (as output of Module 2) are the two supervisory signals we use to jointly train Modules 1, 2, and 4.
We integrate the proposed LORL with state-of-the-art unsupervised segmentation methods, MONet (Burgess et al., 2019) and Slot Attention (Locatello et al., 2020). The evaluation is based on two datasets: ShopVRB (Nazarczuk & Mikolajczyk, 2020) contains images of daily objects and question-answer pairs; PartNet (Mo et al., 2019) contains images of furniture with hierarchical structure, supplemented by descriptive sentences we collected ourselves. We show that LORL consistently improves existing methods on unsupervised object segmentation, much more likely to group different parts of a single object into a single mask.
We further analyze the object-centric representations learned by LORL. In LORL, conceptually similar objects (e.g. objects of similar shapes) appear to be clustered in the embedding space. Moreover, experiments demonstrate that the learned concepts can be used in new tasks, such as visual grounding of referring expressions, without any additional fine-tuning.

heading: 2 RELATED WORK

text:
Unsupervised object representation learning. Given an input image, unsupervised object representation learning methods segment objects in the scene and build an object-centric representation for them. A mainstream approach has focused on using compositional generative scene models that decompose the scene as a mixture of component images (Greff et al., 2016; Eslami et al., 2016; Greff et al., 2017; Burgess et al., 2019; Engelcke et al., 2020; Greff et al., 2019; Locatello et al., 2020). In general, these models use an encoder-decoder architecture: the image encoder encodes the input image into a set of latent object representations, which are fed into the image decoder to reconstruct the image. Specifically, Greff et al. (2019); Burgess et al. (2019); Engelcke et al. (2020) use recurrent encoders that iteratively localize and encode objects in the scene. Another line of research (Eslami et al., 2016; Crawford & Pineau, 2019; Kosiorek et al., 2018; Stelzner et al., 2019; Lin et al., 2020) leverages object locality to attend to different local patches of the image. These models often use a pixel-level reconstruction loss. In contrast, we propose to explore how language, in addition to visual observations, may contribute to object-centric representation learning. There have also been work that uses other types of supervisions, such as dynamic prediction (Kipf et al., 2020; Bear et al.,
2020) and multi-view consistency (Prabhudesai et al., 2020). In this paper, we focus on unsupervised learning of object-centric representations from static images and language. Visual concept learning. Learning visual concepts from language and other forms of supervisions provides useful representations for various downstream tasks, such as cross-modal retrieval (Wu et al., 2019), visual-question answering (Yi et al., 2018; Mao et al., 2019), and scene manipulation (Prabhudesai et al., 2020). Previous work has been focusing on various types of representations (Ren et al., 2016; Wu et al., 2017), training algorithms (Faghri et al., 2018) and supervisions (Johnson et al., 2016; Yang et al., 2018). In this paper, we focus on learning visual concepts that can be grounded on object-centric representations. Recent works on object-centric grounding of visual concepts (Wu et al., 2017; Mao et al., 2019; Prabhudesai et al., 2020) have shown great success in achieving high performance in downstream tasks and strong generalization from a small amount of data. However, these methods assume pre-trained object detectors to generate object proposals in the scene. In contrast, our LORL learns to individuate objects and associates concepts with the learned object-centric representations without any annotations on object segmentation masks or properties.

heading: 3 PRELIMINARIES

text: Before delving into our language-mediated object-centric representation learning paradigm, we first discuss a general formulation that unifies multiple concurrent unsupervised object representation learning methods and a neuro-symbolic framework for learning visual concepts from language.

heading: 3.1 UNSUPERVISED OBJECT-CENTRIC REPRESENTATION LEARNING

text:
Given an image I , a typical unsupervised object representation learning model will decompose the scene into a series of slot profiles {(z1, x1,m1), . . . , (zK , xK ,mK)}, where each slot profile is expected to represent an object (or nothing, as the number of slots may be greater than the actual number of objects in the scene). Here zi is the object feature, xi is the object image, and mi is the object mask specifying its location in the scene.
In our paper, we focus on two recent models, MONet (Burgess et al., 2019) and Slot Attention (Locatello et al., 2020). MONet uses a recurrent spatial attention network (Ronneberger et al., 2015) to segment out objects in the scene, and adopts a variational autoencoder (Kingma & Welling, 2014) to encode objects as well as reconstructing object images for self-supervision. At a very high level, its objective function is calculated as
L = ∥∥∥∥∥ ( K∑ k=1 mkxk ) − I ∥∥∥∥∥ 2
2
+ β · K∑
k=1
KL(zk), (1)
where the first term is a pixel-wise L2 reconstruction loss and the second term computes the KL divergence between the distribution of zk’s and a prior Gaussian distribution.
Slot Attention uses a transformer-like attention network (Vaswani et al., 2017) to extract object features, and decode them with convolutional neural networks to component images and object masks. The model is trained by the same reconstruction loss in the form of L2-norm:
L = ∥∥∥∥∥ ( K∑ k=1 mkxk ) − I ∥∥∥∥∥ 2
2
. (2)

heading: 3.2 NEURO-SYMBOLIC CONCEPT LEARNING

text:
The neuro-symbolic concept learner (NS-CL; Mao et al., 2019) learns visual concepts by looking at images and reading paired questions and answers. NS-CL takes a set of segmented objects in a given image as its input, extracts their visual features with a ResNet (He et al., 2015), translates the input question into an executable program by a semantic parser, and executes the program based on the object-centric representation to answer the question. The key idea of NS-CL is to explicitly represent individual concepts in natural language (colors, shapes, spatial relationships, etc.) as vector space embeddings, and associate them with the object embeddings.
NS-CL answers the input question by executing the program based on the object-centric representation. For example, in order to query the name of the white object in Fig. 2, NS-CL first filters out the object by computing the cosine similarity between the concept white and individual object representations, which produces a “mask” vector where each entry denotes the probability that an object has been
selected. The output “mask” on the objects will be fed into the next module and the execution will continue. The last query operation will produce the answer to the question. The vector embeddings of individual objects and the concepts will be jointly trained based on language supervision.

heading: 4 LANGUAGE-MEDIATED, OBJECT-CENTRIC REPRESENTATION LEARNING

text:
Marrying the ideas of unsupervised object-centric representation learning and neuro-symbolic concept learning, we are able to learn an object-centric representation using both visual and language supervision. Fig. 2 shows an overview of Language-mediated, Object-centric Representation Learning (LORL). In LORL, four modules are optimized jointly: an image encoder, an image decoder, a semantic parser, and a neuro-symbolic program executor. Image encoder. Given an input image, we first use the image encoder (Fig. 2a) to individuate objects in the scene and extract an object-centric scene representation. It takes the input image as its input, individuates objects in the scene, and produces a collection of latent slot embeddings {zi}. Image decoder. The decoder (Fig. 2b) takes the object-centric representation produced by the image encoder and produces a 3-tuple for each individual slot (xk,mk, sk), where xk reconstructs the RGB image of the slot, mk reconstructs the mask, and sk ∈ [0, 1] is a scalar indicating the objectness of the slot. That is, whether k-th slot corresponds to a single object in the scene. Here, we have extended the general pipeline we described in Section 3.1 with an objectness indicator. It serves dual purposes. First, it weights each reconstructed component image while generating the reconstructed image. Mathematically, the reconstructed image I ′ is computed as: I ′ = ∑K k=1 sk · (mkxk). Second, it mediates the output of all filter operations in the program executor.
In this paper, we will experiment with two image encoder-decoder options: MONet (Burgess et al., 2019) and Slot Attention (Locatello et al., 2020). They are both compatible with the learning paradigm described above. For both models, we use a single linear layer to predict the objectness score for each slot on top of the second-last layer of their image decoders. Semantic parser. A pre-trained semantic parser (Fig. 2c) will translate the input question into an executable program composed of primitive operations, such as filter, which filters out objects with certain concepts and query, which queries the attribute of the input object. We use roughly the same domain-specific language (DSL) for representing programs as CLEVR (Johnson et al., 2017a, see also Appendix A for details). All concepts that appear in the program, such as white, are associated with distinct, learnable concept embedding vectors. Neuro-symbolic program executor. The program executor (Fig. 2d) takes the object-centric representation from the image encoder {zk}, the objectness score {sk} from the image decoder, the concept embeddings and the program generated by the semantic parser as its input. It executes the program based on the visual and concept representations to answer the question.
The original program executor in NS-CL (Section 3.2) assumes a pre-trained object detector for generating object proposals. In LORL, we associate each object representation with an objectness score sk. Recall that a filter operation in NS-CL produces a mask vector indicating whether an object has been selected. Here, we mediate the output of an filter(c) operation as min(sk,filter(c)). Intuitively, a slot will be selected only if, first, it has concept c and, second, it corresponds to a single object in the scene. Training paradigm. During training, we jointly optimize the image encoder, the image decoder, and the concept embeddings. They are trained by minimizing the loss L:
L = α · Lperception + β · Lreasoning.
For MONet-based image encoder-decoder, we use Equation 1 as the perception loss Lperception, while for Slot Attention-based encoder-decoder, we use Equation 2. The neuro-symbolic program executor produces a distribution over candidate answers to the input question. We use the cross-entropy loss between the predicted answer and the ground truth answer as Lreasoning. We use a three-stage training paradigm in LORL. First, we train the model with only visual inputs with Lperception for N1 epochs. Next, we fix the image encoder and the image decoder, and optimize the concept embeddings with the loss term Lreasoning for N2 epochs. During this second stage, the image encoder and the decoder can already produce descent object segmentation results. Finally, we jointly optimize all three modules for N3 epochs. We provide detailed information about the hyperparameters for different models in Appendix B.

heading: 5 EXPERIMENTS

text: We first evaluate whether the representations learned by LORL lead to better image segmentation with the help of language. We then evaluate how these representations may be used for instance retrieval, visual reasoning, and referring expression comprehension.

heading: 5.1 IMAGE SEGMENTATION

text:
Data. We use two datasets for image segmentation evaluation. The first, Shop-VRB-Simple, is based on Shop-VRB (Nazarczuk & Mikolajczyk, 2020), a dataset of complex household objects and question-answer pairs. The second is based on chairs in PartNet (Mo et al., 2019), a dataset where the objects are different parts of a chair. Fig. 3 shows some examples from the two datasets.
Shop-VRB is a visual reasoning dataset, similar to CLEVR (Johnson et al., 2017a), but with complex household objects of different sizes, weights, materials, colors, shapes, and mobility. Because the original Shop-VRB dataset includes very small and highly transparent objects and complex backgrounds, which current unsupervised representation learning models cannot handle, we generate 10K images with a clean background ourselves using large objects from the dataset. We also pair every image with 9 questions, resulting in 90K questions in total. The test split has 960 images and 8.6K questions. We name this variant Shop-VRB-Simple.
While the previous literature on unsupervised object segmentation mainly focuses on settings where objects are spatially disentangled, we also explore how language may help when objects of interest are different parts of a global shape. To this end, we collect a new dataset, PartNet-Chairs, using chair shapes from PartNet. Every image here shows a chair, where each part of the chair (legs, seat, back, arms) is randomly assigned a color. We select six different chair shapes with one or four legs and zero or two arms. We generate 5K images for training. Each image is paired with 8 descriptive sentences generated from human-written templates, resulting in 40K examples in total. The test split has 960 images. Each sentence describes the name and color of parts. We provide all templates in Appendix C. We are interested in whether object-centric representation learning models may separate these parts and whether and how language may help in this scenario.
Baselines. We use MONet (Burgess et al., 2019) and Slot Attention (Locatello et al., 2020) as the image modules (Modules 1 and 2), and evaluate how the incorporation of language may improve their performance. Because MONet is color-sensitive, and on Shop-VRB-Simple, many objects have diverse colors and specular reflection, it does not produce meaningful results there. Thus we only show results with MONet on PartNet-Chairs. We show results with Slot Attention on both datasets.
Metrics. We use three metrics for evaluation. Following Greff et al. (2019), we first use the Adjusted Rand Index (ARI; Rand, 1971; Hubert & Arabie, 1985). It treats segmentation as a clustering problem: each mask is the cluster index that the pixels within belong to. ARI is computed as the similarity between the predicted and ground truth clusters, and ranges from 0 (random) to 1 (perfect match).
In practice, we found this pixel-wise metric is sensitive to the size of objects: a model that infrequently makes mistakes on large objects will have lower ARI than one that frequently mis-segments small objects. Thus, we in addition design two object-centric metrics:
• Ground Truth Split Ratio (GT Split) measures the ratio of objects (GT masks) that are covered by more than one prediction mask. • Prediction Split Ratio (Pred Split) measures the ratio of prediction masks that cover more
than one object (GT mask).
Concretely, we first assign each pixel to the prediction mask with the maximum value at the pixel. We say a prediction mask covers an object if it covers at least 20% of the object’s pixels. The GT and Pred Split ratios are thus defined as:
GTSplit = # of objects that are covered by > 1 masks # of objects that are covered by > 0 masks ; PredSplit = # of masks that cover > 1 objects # of masks that cover > 0 objects .
Ideally, there is a one-to-one correspondence between objects and predicted masks, with both GT Split and Pred Split being 0.
Results. The quantitative results on SHOP-VRB-Simple are summarized in Table 1. We show the mean and standard error on each metric over 3 runs. Since our semantic parsing module is trained on paired question-program pairs, it achieves nearly perfect accuracy (> 99.9%) on test questions. Thus, in later sections, we will focus on evaluating object segmentation, concept grounding, and downstream task performances. LORL helps Slot Attention achieve better segmentation results in all three metrics. From visualizations in Fig. 4, we find that the original Slot Attention model struggles with metallic objects; but with LORL, it performs much better in those cases.
To further explore how LORL helps Slot Attention on failure cases, we calculate the Ground Truth Split Ratio for each object category, and find that Slot Attention most often fail to segment coffee makers, blenders, and toasters as a whole. These objects have complex sub-parts and their appearance changes quickly when the viewpoint changes. With the help of language, Slot Attention improves consistently over its ablative variants across all the three metrics we have, reducing the GT split ratio by 50% on average, as shown in Table 1b.
On PartNet-Chairs, LORL also helps both MONet and Slot Attention improve with a large margin, as shown in Table 2. The results are averaged over 4 runs. MONet in general performs well on this dataset, though it still sometimes merges different parts with the same color into a single mask. An example can be found in Fig. 5, column 3, where the blue arm and the blue bottom in the input image are put into the same mask by MONet. Such an issue is alleviated in LORL + MONet. Fig. 5 also includes examples to show how LORL helps Slot Attention.
As shown in Table 2, the improvement on Slot Attention is larger and more consistent, compared with the improvement on MONet. We hypothesize that this is because the two models adopt different approaches for aligning object features and masks. While MONet uses separate modules for segmentation and object representation learning, Slot Attention obtains masks by directly decoding
k = 1 k = 3 k = 5
Slot Attention 54.07±2.6 43.70±1.7 37.02±1.7 LORL + SA 94.03±0.6 91.03±1.3 87.71±1.7
Table 3: The percentage (%) of retrieved objects that belong to the same category as the query object. With LORL, objects within the same category are more likely to be close to each other in the feature space. The results are averaged over 3 runs.
QA Accuracy
LORL + SA (No FT) 62.79±1.6 LORL + SA 92.72±1.0
Table 4: Our three-stage training paradigm improves visual concept learning. Without fine-tuning (i.e., the third training stage), the question answering accuracy drops by 30%. The results are averaged over 3 runs.
object representations. Having a shared representation might have allowed Slot Attention to gain more from language supervision.

heading: 5.2 INSTANCE RETRIEVAL

text:
We now analyze the learned object representations on Shop-VRB-Simple. We first use them for instance retrieval: for each model, we randomly select a segmented object and use its learned representation to search for its k nearest neighbors in the feature space. Then, for each selected object, we compute how many of the k nearest neighbors belong to the same category. During searching, we only consider object representations whose corresponding mask, after decoding, has at least an Intersection over Union (IoU) of at least 0.75 with a ground truth object mask. We sample 1,000 object features from each model for evaluation.
Table 3 includes results with k = 1, 3, 5, suggesting that the object representations learned by LORL + Slot Attention are better for retrieval, compared with features learned by Slot Attention alone without language. This is because Slot Attention often confuses categories that are visually similar but conceptually different, such as baking tray and chopping board.

heading: 5.3 VISUAL REASONING

text:
As another analysis, we also evaluate how the learned representation of LORL +Slot Attention performs on visual question answering on the Shop-VRB-Simple dataset. Here we compare with an ablated version of LORL, where we only train the model for the first two stages, as stated at the end of Section 4. We do not train the model for the third stage—jointly optimizing or fine-tuning all three trainable modules. We name this ablation LORL + SA (No FT). Through this analysis, we hope to understand the importance of joint training of the vision modules (Modules 1 and 2) and the reasoning module (Module 4).
Table 4 shows that joint training is crucial for visual reasoning. This resonates with the previous result, where visually similar objects are clustered together in the latent space, impeding the usefulness of the information encoded.

heading: 5.4 REFERRING EXPRESSION COMPREHENSION

text:
Finally we evaluate the representations learned by LORL on referring expression comprehension, where given an expression referring to a set of objects in the scene, like “The white plates”, the model is expected to return all of the corresponding object masks. After learning all needed concepts from question-answer pairs, LORL can naturally handle referring expression without any further training, if we assume a pre-trained semantic parser.
We choose the IEP-Ref model (Liu et al., 2019) as our baseline. It uses a module approach and receives direct segmentation supervision. On Shop-VRB, we adapt the code provided by Liu et al. (2019) to generate 17K training examples, only for IEP-Ref, and 1.7K testing referring expressions for evaluating both LORL and IEP-Ref. Measured in Recall@0.5 (the ratio of the recalled objects based on an IoU threshold of 0.5), IEP-Ref performs better than LORL, but the margin is small (90.1% vs. 84.4%). Note that while IEP-Ref has been trained on 17K training examples with ground truth object segmentations, LORL does not require any training data on referring expression comprehension. The relatively comparable results are strong evidence that the representations learned by LORL also transfer to a new task.

heading: 6 CONCLUSION

text:
We have proposed Language-mediated, Object-centric Representation Learning (LORL), a paradigm for learning object-centric representations from vision and language. Experiments on Shop-VRBSimple and PartNet-Chairs show that language significantly contributes to learning better representations. This behavior is consistent across two unsupervised image segmentation models.
Through systematic studies, we have also shown how LORL helps models to learn object representations that encode conceptual information, and are useful for downstream tasks such as retrieval, visual reasoning, and referring expression comprehension.

heading: A DOMAIN-SPECIFIC LANGUAGE (DSL)

text: LORL extends the domain-specific language of the CLEVR dataset (Johnson et al., 2017a) to accommodate descriptive sentences. Specifically, we add an extra primitive operation: Equal(X, y). It takes two inputs. In our case, the first argument X is the output of a Query, Exist, or Count operation. All three operations output a distribution over possible answers. The second argument y is either a word or number, such as TRUE, white, or 4. The Equal operation computes the probability of X=y. In LORL, models are trained to maximize the output probability.

heading: B HYPERPARAMETERS

text:
For optimization hyperparameters, we largely adopt original settings in Burgess et al. (2019) and Locatello et al. (2020). Table 5 summarizes the hyperparameters for the loss weights (α and β), the number of training epochs of different stages (N1, N2, N3), and the batch size. We early-stop the training when QA performance converges. We were skipping the second training phase on PartNetChairs because the first training phase (vision-only) yields very poor segmentation performance on this dataset. Establishing a meaningful grounding of concepts could be hard in this case. If we keep the second training phase for LORL + Slot Attention on PartNet-Chairs, the model converges slower in the third training phase (15 more epochs in our experiments), but the final performance remains the same.
Learning rate scheduling For Slot Attention models, during the first training stage (perceptiononly), we use the learning rate schedule described in the original paper on both datasets. Specifically, the initial learning rate is 4 × 10−4, and is fixed 10K iterations. After that, we decay the learning rate by 0.5 for every 100K iterations. On PartNet-Chairs, after the first stage, Slot Attention models continue to use the same learning rate scheduling. For Shop-VRB-Simple, we switch to a fixed learning rate of 0.001 during N2 phase, which takes 20 epochs. After 20 epochs, we decrease the learning rate to 2× 10−4. We further decrease the learning rate to 2× 10−5 after another 65 epochs. We use the Adam optimizer (Kingma & Ba, 2015) for Slot Attention models.
For MONet models, we use RMSProp with a learning rate of 0.01 during the first stage, and use 0.001 for the second and the third stage.
Meanwhile, we also follow NS-CL (Mao et al., 2019) to use curriculum learning. Specifically, in the second training stage, we limit the number of objects in the scene to be 3. In the third training stage, we gradually increase the number of objects in the scene and the complexity of the questions.

heading: C PARTNET-CHAIRS DATASET

text:
Table 6 illustrates all templates that we use to generate descriptive sentences on the PartNet-Chairs dataset. We also show the corresponding latent programs for each template.
In PartNet-Chairs, all programs for descriptive sentences end with an Equal operator, which evaluates to true iff. both of its arguments are equal to each other. We train our model with paired images and sentences, by maximizing the probability that the first argument equals to the second argument.
Table 6 (Continued)
Template Example Sentence Latent Program
There is a <part name>; its color is <color>. There is a back; its color is purple.
Scene, Filter[Back], Query[Color], Equal[Purple]
The <part name> is <color>.
The back is purple. Scene, Filter[Back], Query[Color], Equal[Purple]
There is/are <number> <color>? (<part name>/part) <relation> the <color>? ( <part name>/part).
There is a green seat and a yellow leg is behind it.
Scene, Filter[Green, Seat], Unique, Relate[Behind], Filter[Yellow, Leg], Exist, Equal[True]
There is/are <number> <color>? (<part name>/part) <relation> the <color>? ( <part name>/part).
There is a green seat and no yellow leg is behind it.
Scene, Filter[Green, Seat], Unique, Relate[Behind], Filter[Yellow, Leg], Exist, Equal[False]
<number> <color>? (<part name>/part) is/are <relation> the <color>? ( <part name>/part).
0 leg is behind the brown leg. Scene, Filter[Brown, Leg], Unqiue, Relate[behind], Filter[Leg], Count, Equal[0]
There is a <color>? ( <part name>/part); <number> <color> <part name> is/are <relation> it.
There is a brown leg; 0 leg is behind it.
Scene, Filter[Brown, Leg], Unqiue, Relate[behind], Filter[Leg], Count, Equal[0]
The number of <color>? (<part name> /part) that is/are <relation> <color>? (<part name>/part)is <number>.
The number of leg that is behind the brown leg is 0.
Scene, Filter[Brown, Leg], Unqiue, Relate[behind], Filter[Leg], Count, Equal[0]
There is a <color>? (<part name> /part) <relation> the <color>? (<part name> /part). There is a blue back behind the seat.
Scene, Filter[Seat], Unqiue, Filter[Blue, Back], Relate[behind], Exist, Equal[True]
There is no <color>?<part name> <relation> the <color>? ( <part name>/part).
There is no blue back to the right of the seat.
Scene, Filter[Seat], Unqiue, Relate[right], Filter[Blue, Back], Exist, Equal[False]
Table 6 (Continued)
Template Example Sentence Latent Program
There is a <color>? ( <part name>/part) and a <color>? (<part name>/part) is <relation> it.
There is a seat and a blue back is to the right of it.
Scene, Filter[Seat], Unqiue, Relate[Right], Filter[Blue, Back], Exist, Equal[True]
There is a <color>? ( <part name>/part); there is no <color>? <part name> <relation> it. There is a green seat; there is no blue back to the right of it. Scene, Filter[Seat], Unqiue, Relate[Right], Filter[Blue, Back], Exist, Equal[False]
The color of the <part name> (that is)? <relation> the <color>? ( <part name>/part) is <color>.
The color of the leg left of the red arm is blue. Scene, Filter[Red, Arm], Unique, Relate[Left], Filter[Leg], Query[Color], Relate[behind], Equal[Blue]
There is a <part name> <relation> the <color>? ( <part name>/part); its color is <color>
There is a leg to the left of the red arm; its color is blue. Scene, Filter[Red, Arm], Unique, Relate[Left], Filter[Leg], Query[Color], Equal[Blue]
The name of the <color>? ( <part name>/part) (that is)? <relation> the <color>? ( <part name>/part) is <part name>.
The name of the cyan part that is in front of the yellow seat is leg.
Scene, Filter[Yellow, Seat], Unique, Relate[Front], Filter[Cyan], Query[Part Name, Equal[Leg]
The <color>? ( <part name>/part) (that is)? <relation> the <color>? ( <part name>/part) is called <part name>.
The cyan part that is in front of the yellow seat is called leg.
Scene, Filter[Yellow, Seat], Unique, Relate[Front], Filter[Cyan], Query[Part Name, Equal[Leg]
D IMPLEMENTATION DETAILS
In this section, we provide additional implementation details of our experimental setups and metrics.
GT and Pred split ratios. In this paper, we have introduced two new metrics for evaluating the performance of unsupervised object segmentation: namely, the GT split ratio and and the Pred split ratio.
A simple example of how we can compute GT/Pred split ratios is shown in Fig. 6. At a high level, the GT split ratio computes the percentage of objects that are split into multiple parts in model segmentation. Meanwhile, Pred split ratio computes the percentage of objects that are merged into a single object in model segmentation. We introduce these two new metrics because the ARI score is evaluated at the pixel level and does not account for the variance of object sizes. By contrast, GT split and Pred split metrics are computed at the object level. This difference is illustrated in Fig. 7.
For concrete examples, in the Fig. 6 (a.1), two objects, the chopping board and the thermos, are wrongly segmented. In Fig. 6 (a.2), only one object mis-segmented. However, the ARI score of the first image is much higher because the coffee maker has a large size. GT split ratio is evaluated on the object level and thus favor the second one. Similarly, in the Fig. 6 (b.1) , the four legs are merged into two masks, while in Fig. 6 (b.2), the seat and the back of the chair are merged into a single object. However, the first segmentation result has a significantly higher ARI score because the chair legs only contribute to a small area in the image. In this paper, we propose to jointly use ARI scores and the proposed GT/Pred split ratio to evaluate segmentation masks.

heading: SA (Locatello et al., 2020) 23.71±1.5 23.45±4.1 8.91±0.7 7.47±0.9

heading: SA + Obj score 83.4±1.8 16.57±1.5 12.71±0.8

text:
Throughout the paper, we have been using IoU=0.2 as the threshold while computing the GT/Pred split ratios. Table 7 summarizes the results with different IoU thresholds. LORL consistently improves the baseline.
Referring expression comprehension. In this experiment, the data is generated using the code adapted from Liu et al. (2019). It contains two types of expressions, the first one directly refers to an object by its properties: for example, “the white plate”. The second type of sentences refers to the object by relating it with another object: for example, “the object that is in front of the mug.” The output of the model is the masks of all referred objects. The dataset is composed of the same set of concepts and same DSL as in the Shop-VRB-Simple.
We use the IEP-Ref model proposed in Liu et al. (2019) as a baseline. It is adapted from its prior work IEP (Johnson et al., 2017b). IEP-Ref first translates the referring expression into a sequence of primitive operations, which are implemented as different modular networks. The model takes the image feature extracted by a CNN as input and executes the program by chaining these component networks. It outputs a segmentation mask on objects being referred to. During training, groundtruth segmentation masks are needed.
For all methods, including ours and the baseline, we assume a pretrained semantic parser. Since the neuro-symbolic program executor outputs a distribution over all objects indicating whether they are selected, we directly multiply its output with the object segmentation masks to get the final output.

heading: E ADDITIONAL RESULTS

text:
The following section presents a collection of ablation studies on different modules of LORL, as well as a few extensions.
Objectness score. To validate the effectiveness of the proposed objectness score module, we hereby compare two models: the original Slot Attention model and the Slot Attention model augmented with the proposed objectness score module. Both models are trained using images only (there is no language in the loop), on the Shop-VRB-Simple dataset. The Table 8 summarizes the result. The objectness module alone does not contribute to the segmentation performance.
Question type. In this section, we investigate how different types of questions affect LORL. We use the Shop-VRB-Simple dataset for evaluation. There are three types of questions in the dataset, counting (e.g., how many plates are there?), existence (e.g., is there a toaster?), and query (e.g., what is the color of the mug?). We train LORL +SA with only one single type of questions (the number of total questions is the same).
Results are summarized in Table 9. In general, training on all three types of questions improves the segmentation accuracy. The largest gain comes from the query question. Interestingly, the best result is achieved when trained on the original dataset, where the ratio of counting, existence, and query questions is 1:1:7. Note that all these models are trained with the same number of questions and thus they are directly comparable with each other.
Data efficiency. In addition, we provide another analysis by comparing models trained with different number of question-answer pairs. The results are shown in Table 10. Adding more language data consistently improves the result. All results are based on the LORL +SA model trained on the Shop-VRB-Simple dataset.
Visual reasoning baselines. To establish a baseline for visual reasoning tasks, we present the results of two visual reasoning approaches IEP (Johnson et al., 2017b) and NS-CL (Mao et al., 2019) for reference on the Shop-VRB-Simple dataset, as shown in Table 11. All models are trained with the same set of question-answer pairs. Note that NSCL has the access to a pretrained object detection module, while LORL +SA and IEP do not. LORL +SA outperforms IEP, which is trained with exactly the same amount of supervision as ours. It also achieves a comparable result as NS-CL.
Integration with SPACE. SPACE (Lin et al., 2020) is another popular method for unsupervised object-centric representation learning. SPACE uses parallel spatial attention to decompose the input scene into a collection of objects, and it is also compatible with the proposed learning paradigm LORL. We include additional results of LORL +SPACE on the CLEVR dataset. Shown in the Table 12, LORL +SPACE shows a significant advantage over the vanilla SPACE model. Additionally, we find that SPACE shows poor segmentation results on Shop-VRB-Simple and ParNet-Chairs, no matter whether it is integrated with LORL. For example, it frequently segments complex objects into too many fragments on Shop-VRB-Simple. We conjecture that this is because SPACE was designed for segmenting objects of similar sizes.
Baseline using language supervision. We also conducted an additional baseline model that uses language supervision in a different way. Specifically, based on the Slot Attention model, we use a GRU to directly encode question and answer, and concatenate it with the image feature to obtain the
object representation. On Shop-VRB-Simple, this model does not show improvement over the Slot Attention baseline: ARI=76.4%, GT Split=29.2%, Pred Split=13.6%. This suggests the effectiveness of LORL.
Concept quantification. Although LORL without the objectness score can achieve a comparable result in terms of QA accuracy, objectness score is crucial if we want to evaluate how models discover objects in images. Here, we show that, on the Shop-VRB-Simple dataset, LORL +SA shows significant improvement in recovering a holistic scene representation.
Specifically, we extract a scene graph for each scene, where each node corresponds to a detected object. We represent each node i as a set of conceptsCi associated with the object (e.g., {large, brown, wooden, chopping board}). We associate a concept with a detected object if its cosine similarity with the object representation is greater than 0. We heuristically remove nodes that are not associated with any concepts (by treating them as “background” objects) or have objectness scores that are smaller than 0.5. This results in a scene graph, where each node corresponds to a detected object. In the following, we compare it against the groundtruth scene graph.
For each pair of groundtruth node i and detected node j, we compute the concept IoU score based on their associated concepts Ci and Cj as:
IoUij = |Ci ∩ Cj | |Ci ∪ Cj |
Next, we perform a maximum weight matching between the detected scene graph and the groundtruth scene graph with the Hungarian algorithm. We use the IoU score as the weight for every edge and remove edges whose IoU score is smaller than a given threshold. Finally, based on the macthing, we
can compute the precision and recall of the detected scene graph. We show the average precision and recall over the entire test set images in Table 13. The results suggest that objectness score significantly improves the precision of the extracted concepts.


summaries: The work utilizes relational background knowledge contained in logical rules to conduct multi-relational reasoning for knowledge graph (KG) completion. This is different from the superficial vector triangle linkage used in embedding models. It solves the KG completion task through rule-based reasoning rather than using rules to obtain better embeddings. Experiments on FB15K, WN18, and a new dataset FB15K-R demonstrate the effectiveness of the proposed model EM-RBR.

summaries: The paper seek to improve KG representation (e.g. for link prediction and question answering) by combining logical reasoning (logical rule templates) with statistical methods (TransE). Rules are mined from the KG using AMIE and recursive backward steps are taken, using the mined rules, to determine if a fact is true.

summaries: The paper proposes a framework (EM-RBR) for doing Knowledge Base (KB) completion. Instead of the direct triple score from an embedding based method, EM-RBR allows the triple score to be calculated as a composition of the scores of the rules mined from the KB. EM-RBR uses a BFS type algorithm that recursively searches for reasoning paths connecting the triple while also updating the score.  The authors show that EM-RBR when used as an addendum to a translation-based embedding method (such as TrasnE, TransH) is able to outperform them. They show their results on FB15k and WN18.

abstractText: Knowledge graph completion aims to predict the missing links among the knowledge graph (KG),i.e., predicting the possibility that a certain triple belongs to the knowledge graph. Most mainstream embedding methods focus on fact triplets contained in the given KG, however, ignoring the rich background information provided by logic rules driven from knowledge base implicitly. Limited to the modeling of algebraic space, contradictory in expressing certain relational patterns usually exists in the embedding models. Therefore, the representation of the knowledge graph is incomplete and inaccurate. To solve this problem, in this paper, we propose a general framework, named EM-RBR(embedding and rulebased reasoning), capable of combining the advantages of reasoning based on rules and the state-of-the-art models of embedding. EM-RBR aims to utilize relational background knowledge contained in rules to conduct multi-relation reasoning link prediction. In this way, we can find the most reasonable explanation for a given triplet to obtain higher prediction accuracy. In experiments, we demonstrate that EM-RBR achieves better performance compared with previous models on FB15k, WN18 and our new dataset FB15k-R, especially the new dataset where our model perform futher better than those state-of-the-arts. We make the implementation of EM-RBR available at https://github.com/1173710224/ link-prediction-with-rule-based-reasoning.

authors:
Antoine Bordes
Jason Weston
Ronan Collobert
Yoshua Bengio

title: Learning structured embeddings of knowledge bases

venue: In Twenty-Fifth AAAI Conference on Artificial Intelligence,

authors:
Antoine Bordes
Nicolas Usunier
Alberto Garcia-Duran
Jason Weston
Oksana Yakhnenko

title: Translating embeddings for modeling multi-relational data

venue: In Advances in neural information processing systems,

authors:
Antoine Bordes
Xavier Glorot
Jason Weston
Yoshua Bengio

title: A semantic matching energy function for learning with multi-relational data

venue: Machine Learning,

authors:
Rajarshi Das
Shehzaad Dhuliawala
Manzil Zaheer
Luke Vilnis
Ishan Durugkar
Akshay Krishnamurthy
Alex Smola
Andrew Mccallum

title: Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning

authors:
Rajarshi Das
Shehzaad Dhuliawala
Manzil Zaheer
Luke Vilnis
Ishan Durugkar
Akshay Krishnamurthy
Alexander J. Smola
Andrew McCallum

authors:
Tim Dettmers
Pasquale Minervini
Pontus Stenetorp
Sebastian Riedel

title: Convolutional 2d knowledge graph embeddings

venue: AAAI Conference on Artificial Intelligence (AAAI-18),

authors:
Xin Dong
Evgeniy Gabrilovich
Geremy Heitz
Wilko Horn
Ni Lao
Kevin Murphy
Thomas Strohmann
Shaohua Sun
Wei Zhang

title: Knowledge vault: A web-scale approach to probabilistic knowledge fusion

venue: In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining,

authors:
Luis Antonio Galárraga
Christina Teflioudi
Katja Hose
Fabian Suchanek

title: Amie: association rule mining under incomplete evidence in ontological knowledge bases

venue: In Proceedings of the 22nd international conference on World Wide Web,

authors:
Matt Gardner
Partha Talukdar
Jayant Krishnamurthy
Tom Mitchell

title: Incorporating vector space similarity in random walk inference over knowledge bases

venue: In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP),

authors:
Jens Graupmann
Ralf Schenkel
Gerhard Weikum

title: The spheresearch engine for unified ranked retrieval of heterogeneous xml and web documents

authors:
Shu Guo
Quan Wang
Lihong Wang
Bin Wang
Li Guo

title: Jointly embedding knowledge graphs and logical rules

venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,

title: Knowledge graph embedding with iterative guidance from soft rules

venue: arXiv preprint arXiv:1711.11231,

title: The expression of a tensor or a polyadic as a sum of products

venue: Journal of Mathematics and Physics,

authors:
Raphael Hoffmann
Congle Zhang
Xiao Ling
Luke Zettlemoyer
Daniel S. Weld

title: Knowledgebased weak supervision for information extraction of overlapping relations. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, HLT

authors:
Guoliang Ji
Shizhu He
Liheng Xu
Kang Liu
Jun Zhao

title: Knowledge graph embedding via dynamic mapping matrix

venue: In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers),

authors:
Rudolf Kadlec
Ondrej Bajgar
Jan Kleindienst

title: Knowledge base completion: Baselines strike back

venue: arXiv preprint arXiv:1705.10744,

authors:
Seyed Mehran Kazemi
David Poole

title: Simple embedding for link prediction in knowledge graphs

authors:
Stanley Kok
Pedro Domingos

title: Statistical predicate invention

venue: In Proceedings of the 24th international conference on Machine learning,

authors:
Timothée Lacroix
Nicolas Usunier
Guillaume Obozinski

title: Canonical tensor decomposition for knowledge base completion

venue: In ICML,

authors:
Ni Lao
William W. Cohen

title: Relational retrieval using a combination of path-constrained random walks

venue: Mach. Learn.,

authors:
Ni Lao
Tom Mitchell
William W Cohen

title: Random walk inference and learning in a large scale knowledge base

venue: In Proceedings of the Conference on Empirical Methods in Natural Language Processing,

authors:
Hailun Lin
Yong Liu
Weiping Wang
Yinliang Yue
Zheng Lin

title: Learning entity and relation embeddings for knowledge resolution

venue: Procedia Computer Science,

authors:
Yankai Lin
Zhiyuan Liu
Maosong Sun
Yang Liu
Xuan Zhu

title: Learning entity and relation embeddings for knowledge graph completion

venue: In Twenty-ninth AAAI conference on artificial intelligence,

authors:
Tomas Mikolov
Ilya Sutskever
Kai Chen
Greg S Corrado
Jeff Dean

title: Distributed representations of words and phrases and their compositionality

authors:
Dai Quoc Nguyen
Tu Dinh Nguyen
Dat Quoc Nguyen
Dinh Phung

title: A novel embedding model for knowledge base completion based on convolutional neural network

venue: arXiv preprint arXiv:1712.02121,

title: An overview of embedding models of entities and relationships for knowledge base completion

venue: arXiv preprint arXiv:1703.08098,

authors:
Maximilian Nickel
Volker Tresp
Hans-Peter Kriegel

title: A three-way model for collective learning on multi-relational data

venue: In Icml,

authors:
Meng Qu
Jian Tang

title: Probabilistic logic neural networks for reasoning

venue: In Advances in Neural Information Processing Systems,

authors:
Tim Rocktäschel
Sameer Singh
Sebastian Riedel

title: Injecting logical background knowledge into embeddings for relation extraction

venue: In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Ali Sadeghian
Mohammadreza Armandpour
Patrick Ding
Daisy Zhe Wang

title: Drum: End-toend differentiable rule mining on knowledge graphs

authors:
Richard Socher
Danqi Chen
Christopher D Manning
Andrew Ng

title: Reasoning with neural tensor networks for knowledge base completion

authors:
Zhiqing Sun
Zhi-Hong Deng
Jian-Yun Nie
Jian Tang

title: Rotate: Knowledge graph embedding by relational rotation in complex

venue: space. CoRR,

authors:
Kristina Toutanova
Danqi Chen

title: Observed versus latent features for knowledge base and text inference

venue: In The 3rd Workshop on Continuous Vector Space Models and their Compositionality,

authors:
Théo Trouillon
Johannes Welbl
Sebastian Riedel
Éric Gaussier
Guillaume Bouchard

title: Complex embeddings for simple link prediction

authors:
Pengwei Wang
Dejing Dou
Fangzhao Wu
Nisansa de Silva
Lianwen Jin

title: Logic rules powered knowledge graph embedding

authors:
William Yang Wang
William W Cohen

title: Learning first-order logic embeddings via matrix factorization

venue: In Ijcai,

authors:
Zhen Wang
Jianwen Zhang
Jianlin Feng
Zheng Chen

title: Knowledge graph embedding by translating on hyperplanes

venue: In Twenty-Eighth AAAI conference on artificial intelligence,

authors:
Evgenia Wasserman Pritsker
William Cohen
Einat Minkov

title: Learning to identify the best contexts for knowledge-based WSD

venue: In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing,

authors:
Wenhan Xiong
Thien Hoang
William Yang Wang

title: Deeppath: A reinforcement learning method for knowledge graph reasoning

authors:
Bishan Yang
Wen-tau Yih
Xiaodong He
Jianfeng Gao
Li Deng

title: Embedding entities and relations for learning and inference in knowledge bases

venue: arXiv preprint arXiv:1412.6575,

authors:
Fan Yang
Zhilin Yang
William W Cohen

title: Differentiable learning of logical rules for knowledge base reasoning

authors:
Shuai Zhang
Yi Tay
Lina Yao
Qi Liu

title: Quaternion knowledge graph embedding

authors:
Yuyu Zhang
Xinshi Chen
Yuan Yang
Arun Ramamurthy
Bo Li
Yuan Qi
Le Song

title: Efficient probabilistic logic reasoning with graph neural networks

venue: arXiv preprint arXiv:2001.11850,

heading: 1 INTRODUCTION

text:
Knowledge graph (KG) has the ability to convey knowledge about the world and express the knowledge in a structured representation. The rich structured information provided by knowledge graphs has become extremely useful resources for many Artificial Intelligence related applications like query expansion (Graupmann et al., 2005), word sense disambiguation (Wasserman Pritsker et al., 2015), information extraction (Hoffmann et al., 2011), etc. A typical knowledge representation in KG is multi-relational data, stored in RDF format, e.g. (Paris, Capital-Of, France). However, due to the discrete nature of the logic facts (Wang & Cohen, 2016), the knowledge contained in the KG is meant to be incomplete (Sadeghian et al., 2019). Consequently, knowledge graph completion(KGC) has received more and more attention, which attempts to predict whether a new triplet is likely to belong to the knowledge graph (KG) by leveraging existing triplets of the KG.
Currently, the popular embedding-based KGC methods aim at embedding entities and relations in knowledge graph to a low-dimensional latent feature space. The implicit relationships between entities can be inferred by comparing their representations in this vector space. These researchers (Bordes et al., 2013; Mikolov et al., 2013; Wang et al., 2014; Ji et al., 2015; Lin et al., 2015; Nguyen et al., 2017) make their own contributions for more reasonable and competent embedding. But the overall effect is highly correlated with the density of the knowledge graph. Because embedding method always fails to predict weak and hidden relations which a low frequency. The embedding will converge to a solution that is not suitable for triplets owned weak relations, since the training set for embedding cannot contain all factual triplets.However, reasoning over the hidden relations can covert the testing target to a easier one. For example, there is an existing triplet (Paul, Leader-Of, SoccerTeam) and a rule Leader-Of(x,y) =⇒ Member-Of(x,y) which indicates the leader of a soccer
team is also a member of a sport team. Then we can apply the rule on the triplet to obtain a new triplet (Paul, Member-of, SportTeam) even if the relation Member-of is weak in knowledge graph.
Besides, some innovative models try to harness rules for better prediction. Joint models (Rocktäschel et al., 2015; Wang et al., 2019; Guo et al., 2016) utilize the rules in loss functions of translation models and get a better embedding representation of entities and relations. An optimization based on ProPPR (Wang & Cohen, 2016) embeds rules and then uses those embedding results to calculate the hyper-parameters of ProPPR. These efforts all end up on getting better embedding from rules and triplets, rather than solving completion through real rule-based reasoning, which is necessary to address weak relation prediction as mentioned before. Compared with them, EM-RBR can perform completion from the reasoning perspective.
Usually, there are some contradictions in the mathematical space of existing embedding-based models. Take transE (Bordes et al., 2013) and RotatE (Sun et al., 2019) as examples. For the relation pattern R(x, y) ⇒ R(y, x), i.e., a symmetrical relation, transE cannot model it as described in Sun et al. (2019). While RotatE can not model some relation pattern. For example, transitive relation R, w.r.t R(x, y)∧R(y, z)⇒ R(x, z). We assume that the embedding of the relation R under RotatE is eiθR , abbreviated as r. Formula 1 is necessary and sufficient to transitivity. So we will get r2 = r, which means that eiθR = 1, so θR = 0, θR ∈ [0, 2π). θR = 0 denotes that R is a reflexive relation. That is all the embedding of the transitive relation will be trained to have the nature of the reflexive relation, which is out of our expect.
x · r = y, y · r = z, x · r = z (1) In addition to the above problems, transE and RotatE models cannot model data that has multiple relations between two entities. TransR (Lin et al., 2015) can solve this problem by training the relationship as a transformation matrix. But none of them can solve the problem that an entity has the same relation with multiple other entities. For example, there are two triples (h, r, t1), (h, r, t2) in the knowledge graph(t1 6= t2). For the transE model, h+ r is a fixed result. So a wrong equation r1 = r2 will exist under transE model. The other two mathematical models are no exception.
The above-mentioned shortcomings can be solved by defining the relation pattern in a rule directly. Morivated by this, We propose a novel framework EM-RBR combing embedding and rule-based reasoning, which is a heuristic search essentially. In the development of the joint framework EMRBR, we meet two challenges. On the one hand, we use AMIE (Galárraga et al., 2013) to auto-mine large amount of rules but not manually. However, these rules automatically mined sometimes are not completely credible. Therefore, it is necessary to propose a reasonable way to measure rules to pick proper rules when reasoning. On the other hand, it is known that traditional reasoningbased methods will give only 0 or 1 to one triplet to indicate acceptance or rejection for the given knowledge graph. This conventional qualitative analysis lacks the quantitative information as the embedding models. So the result of EM-RBR need to reflect the probability one triplet belonging to the knowledge graph.
Three main contributions in EM-RBR are summarized as follows:
• EM-RBR is flexible and general enough to be combined with a lot of embedding models. • We propose a novel reasoning algorithm, which can distinguish a given triplet with other
wrong triplets better. • We propose a novel rating mechanism for auto-mined reasoning rules and each rule will be
measured properly in our framework.
In the remaining of this paper, we will explain how our model works in Section 2, experiments in Section 3 and related work in Section 4.

heading: 2 METHOD

text:
Our motivation is to use rules to make up for the shortcomings of embedding model. When the mathematical space of a certain embedding model is not enough to represent a certain relation pattern, the relation pattern can be declared through rules. For example, for the symmetric relationship R, we declare a rule R(x, y) ⇒ R(y, x). When scoring a certain triple (a,R, b) under transE model, we can take min(s(a,R, b), s(b, R, a)) as the The final score of the triple. This is equivalent
to finding another triple that can explain the rationality of this triple through rules. Although the relation between the new triplet and the original triplet cannot be expressed in the algebraic space of embedding, the most reasonable explanation can be found through rules to solve the defects of the model.
The core idea of our framework is to conduct multi-relation path prediction in deeper context from reasoning perspective, that is in the form of heuristic search. Before explaining the concrete reasoning algorithm, let’s take an overview of our framework in Section 2.1.

heading: 2.1 OVERVIEW

text:
Definition 2.1. Rule: A rule in our framework is in the form of B1(x, z) ∧ B2(z, y) =⇒ H(x, y) or B(x, y) =⇒ H(x, y).
We model a knowledge graph as a collection of facts G = {(h, r, t)|h, t ∈ E , r ∈ R}, where E and R represent the set of entities and relations in the knowledge graph, respectively. The steps of our framework are as follows corresponding to Figure 1.
Step 1. We invoke an embedding model to get a set Ξ ∈ R(|E|+|R|)×k containing the k-dimensional embedding of entities and relations in G.
Step 2. We apply AMIE (Galárraga et al., 2013) on G to get the reasoning rule set Ω, where each rule meets Definition 2.1.
Step 3. The reasoning rules are measured based on the embedding of relations contained in the rule, which will explained in Secion 2.2.2.
Step 4. Reasoning is conducted for a given triplet (h, r, t), which will be described in Section 2.2.

heading: 2.2 REASONING ALGORITHM

text:
Definition 2.2. initial state: Initial state is represented as a set consisting of a single triplet, i.e.{(h, r, t)}. state: According to the initial state and the state’s expansion method described in Section 2.2.1, each state is represented as a set a triples.
This reasoning algorithm is the core of our framework and it’s a heuristic search. The input of this algorithm is a triplet (h, r, t). State in the search space is as Definition 2.2. Each state has two
scores, i.e. H and L. H is the heuristic score of state and L is the score of the state. The calculation of scores is explained in Section 2.2.2.
The target of search is to compute Φ∼(h,r,t) = minstate∈S{L∼state(h, r, t)} for a specific triple (h, r, t). The score Φ of a triplet meets Φ ≥ 1. The smaller Φ is, the triplet belongs to knowledge graph with greater probability.
The pseudo code of search is as shown in Appendix B. We use a priority queue Q to store states in ascending order of H. The initial state is the target triplet itself, whose H is 1. Push the initial state into Q and then begin the loop until Q is empty.
During the search process, pop the top of Q as the current state scur. It will not be extended if Hscur ≥ Φ, otherwise we will extend it by matching rules to get new states. For each new state snew, compute its scoreHsnew and Lsnew . IfHsnew < Lscur , the state will then be pushed into Q.

heading: 2.2.1 MATCHING AND EXTENSION

text:
State is a set of triplets, the initial state is the target triplet itself. Intermediate states are extended from the initial state. So essentially, the extension of a state is extension of the triplets in the state. For a triplet (h, r, t), the process of matching and extension is roughly as follows:
1. Find rules ω ∈ Ω in the form of B1(x, z) ∧B2(z, y) =⇒ H(x, y)1, where H = r. 2. Assign entities to variables in the rule, i.e. x = h, y = t. 3. Find all z0 that satisfy (x,B1, z0) ∈ G or (z0, B2, y) ∈ G, where x = h, y = t. 4. (h, r, t) is extended to {(h,B1, z0), (z0, B2, t)}. A triplet always has multiple extensions.
For example, we expand the target triplet in the initial state. There are two triplets in the sub-state, and either of them must be in the knowledge graph. When the sub-state is further expanded, the triplet in the knowledge graph need not to be expanded. Therefore, there should be m+ 1 triplets in each sub-state after extending m times. And at least m of them belong to the knowledge graph.

heading: 2.2.2 COMPUTATION OF H AND L

text:
H∼O(h, r, t) denotes the heuristic score of triplet (h, r, t) when extended to stateO andL∼O(h, r, t) is the corresponding state score.
H∼O(h, r, t) = ∏
(B1∧B2⇒H)∈∆Path
ω(B1, B2, H) w.r.t, ω(B1, B2, H)← e ||B1+B2−H|| k (2)
H∼O(h, r, t) is defined as Equation 2 indicating the product of the scores of all the rules. ∆Path represents the set of the rules used in the extension from the initial state to the current state. ω(B1, B2, H) is the score of rules in the shape of B1 ∧B2 ⇒ H .
L∼O(h, r, t) = H∼O(h, r, t) ∗ ∏
(Oh,Or,Ot)∈O
s∼transX(Oh,Or,Ot) (3)
L∼O(h, r, t) is defined as Equation 3 indicating the product of H∼O(h, r, t) and the scores of all the triplets in the state. O denotes the state and (Oh,Or,Ot) is a triplet belongs to O. s∼transX(Oh,Or,Ot) is the embedding score of this triplet as defined in Equation 4.
s∼transX(Oh,Or,Ot) = {
1 if (Oh,Or,Ot) ∈ G ||Oh +Or −Ot||/k + 1 if (Oh,Or,Ot) /∈ G (4)
Rule’s score To evaluate the score of rule B1(x, z) ∧ B2(z, y) =⇒ H(x, y), we visualize the three triplets of this rule in a two-dimensional space in Figure 3 of Appendix A. In our model, if a rule has a high confidence, it should satisfy ‖x+H−y‖ ≈ ‖x+B1−z+z+B2−y‖. We have H ≈ B1 +B2, so we can use ‖B1 + B2 −H‖ to evaluate the score of the rule. k is the dimension of embedding.
1The rules we analyzed here are in the form of B1(x, z) ∧ B2(z, y) =⇒ H(x, y). As for rules like B(x, y) =⇒ H(x, y), the process is similar and will not be overtalked here.
The smaller score, the higher confidence. To make the dimension in the calculation uniform, we divide the score of the rule by k. And then perform the e exponential transformation to get the form in the Equation 2. The reason for this transformation will be explained in section 2.4.
Triplet’s score ||Oh +Or −Ot|| is the score of triplet (Oh,Or,Ot) in transE model2. The smaller the value, the more likely the triplet is in G. When (Oh,Or,Ot) ∈ G, the score is assumed to be 0. The same to rule’s score, we also perform a certain transformation on the scores of the triplets, which is to divide by k and add 1.

heading: 2.3 EXAMPLE

text:
Assumption 2.1. We put all the necessary message in Table 3 and 4. Apart from that, we make two assumptions. One is that we use the same symbol ri to represent a rule’s symbol and rule’s score. Another is that we define some data relations as Equation 5.
r1r3r5 > L∼s3(h, r, t) & H∼s7(h, r, t) > Φ∼(h,r,t) (5)
In this section, we use an example to illustrate our algorithm as shown in Figure 23. The initial state s0 only contains one triplet (h, r, t), and its state score and heuristic score are both 1. At the beginning, the priority queueQ has only one element, i.e. the initial state with its scores. The search process is as follows, and the necessary message is defined in Assumption 2.1.
I. s0 matches r1 and r2 and extends to s1 and s2 respectively. s2 is a termination state for the triplets in s2 are all in G. We use L∼s2(h, r, t) to update Φ∼(h,r,t) and push s1 into Q.
II. Pop the top of queue s1. Use it to update Φ∼(h,r,t) and then extend it to three new states which will be pushed to Q.
2Here we take transE as an example, so we use ||Oh +Or −Ot||. If the combined model changes, this formula should change to the form in the combined model, too.
3There will be some conflicts in the usage of symbols. For these symbols, it’s only valid in this example.
III. Pop the top of queue s3 to update Φ∼(h,r,t) and extend it with matching the rule r5. Since r1r3r5 > L∼s3(h, r, t), i.e. the solution produced by this path will not be the global minimum. As a consequence, this state is no longer extended.
IV. Pop the top of queue s4 to update Φ∼(h,r,t) and extend to get two new states s6, s7.
V. Pop the top of queue s6 to update Φ∼(h,r,t) and extend to s8, s9 after the rule r7.
VI. Pop the top of queue s7 and nowH∼s7(h, r, t) > Φ∼(h,r,t). So s7 and the remaining states in Q need not extend. Therefore, all the remaining states in Q become termination states. The search stops.

heading: 2.4 ANALYSE

heading: IS THE ALGORITHM SURE TO BE EFFECTIVE?

text:
For three real number a, b, c(a, b, c > 1), it’s possible that c > a ∗ b ∗ 1. Consider triplet (h, r, t) and ruleB1(x, z)∧B2(z, y) =⇒ H(x, y) ,w.r.t r = H . If c represents the score of (h, r, t), a represents the score of the rule, b represents the score of the expanded new triplet that not in the knowledge graph, and 1 represents the score of the expanded new triplet that in the knowledge graph. Then the score of (h, r, t) will be reduced to a ∗ b, i.e. we use the new expanded triplets and the rule to evaluate (h, r, t).
Of course, this optimization will be effective only on the correct triplets. For the wrong triplets, another wrong triplet with a large score will be obtained after rule matching. So c > a ∗ b in this occasion is a very unlikely event. As a result, the correct triplets are optimized, and the wrong triplets will generally not be optimized. Therefore, from a macro perspective, the ranking of the correct triplets will increase.

heading: IS THIS ALGORITHM A TERMINATING ALGORITHM?

text:
The heuristic score of a state is the product of scores of all the rules along the reasoning path. The scores of the rules are all number greater than 1, so when a search path is long enough, H must be greater than Φ. So the search must be able to stop.
WHAT IS THE PRINCIPLE WHEN DESIGNING THE CALCULATION OF RULES AND TRIPLETS?
From the above, we require that the scores of rules and triplets are greater than 1 and close to 1. Given that each dimension of embedding obtained by the translation model is a number less than 1 and close to 0, we divide the score by the corresponding dimension k and then add 1 to meet our requirements. In addition, in order to highlight the importance of rules in the calculation, we use exponential changes for rules instead of plus 1.

heading: 3 EXPERIMENT

text: We would like to prove two things. One is that EM-RBR is a valid reinforced model, i.e. EMRBR(X) model always performs better than X model. Another is that EM-RBR will beat all of the current state-of-the-arts on a data set with rich rules.

heading: 3.1 EXPERIMENT SETUP

text:
Dataset: We evaluate EM-RBR on FB15k, WN18 (Bordes et al., 2013), FB15k237 (Toutanova & Chen, 2015) and WN18RR (Dettmers et al., 2017). We propose a new data set FB15k-R, whose test set contains rich rule information as described in Appendix D.
Metrics: We use a number of commonly used metrics, including Mean Rank (MR), Mean Reciprocal Rank (MRR), and Hit ratio with cut-off values n = 1,10. MR measures the average rank of all correct entities and MRR is the average inverse rank for correct entities. Hits@n measures the proportion of correct entities in the top n entities. MR is always greater or equal to 1 and the lower MR indicates better performance, while MRR and Hits@n scores always range from 0.0 to 1.0 and
higher score reflects better prediction results. We use filtered setting protocol (Bordes et al., 2013), i.e., filtering out any corrupted triples that appear in the KB to avoid possibly flawed evaluation.
Baseline: To demonstrate the effectiveness of EM-RBR, we compare with a number of competitive baselines: TransE (Bordes et al., 2013), TransH (Wang et al., 2014), TransR (Lin et al., 2015), TransD (Ji et al., 2015), RUGE (Guo et al., 2017), ComplEx (Trouillon et al., 2016), DistMult (Kadlec et al., 2017) and MINERVA (Das et al., 2017a). Among these state-of-arts, TransE, TransH, TransR and TransD are combined with our reasoning framework. These 8 models are evaluated on 4 standard datasets to prove that our framework is a real reinforced framework. In the end, all the baselines and combined models are evaluated on FB15k-R.
Implementation: For TransE, TransH, TransR and TransD, we set the same parameters, i.e., the dimensions of embedding k = 100, learning rate λ = 0.001, the margin γ = 1. We traverse all the training triplets for 1000 rounds. Other parameters of models are set as the same with the parameters in the published works (Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015)4. For RUGE, we set the embedding dimension k = 100 and other hyper-parameters are the same with Guo et al. (2017)5. For ComplEx and DistMult, all the parameters are consistent with Trouillon et al. (2016)6. For MINERVA, we use the implementation of Das et al. (2017a)7.

heading: 3.2 EXPERIMENT RESULTS

text:
Firstly, we compare EM-RBR(X) with transX model on FB15k, WN18, FB15k237 and WN18RR. Experimental Results are shown in Table 6. Among the four datasets, the performance on WN18RR is not optimized much cause this dataset is too sparse and its result is shown in E.
When evaluating on FB15k ,WN18 and FB15k-237, our model has improved all the metrics compared with the translation model in the baseline, especially MRR and Hits@1 on each dataset. For example, EM-RBR(D) improve Hits@1 on WN18 from 0.296 to 0.752 compared to transD. While our EM-RBR doesn’t have obvious optimization on WN18RR, cause the dataset is too sparse. We have show the experiment result in Appendix E.
Secondly, we compare all the baselines mentioned above on FB15k-R, each triplet in this data set can match a lot of rules so that they can be optimized extremely under EM-RBR. The result is in Table 2. Among those baselines, MINERVA shows the best performance for the test set is rich in rules. While the performance is further optimized compared to MINERVA.
4https://github.com/thunlp/Fast-TransX 5https://github.com/iieir-km/RUGE 6https://github.com/ttrouill/complex 7https://github.com/shehzaadzd/MINERVA

heading: 3.3 RESULT ANALYSIS

text: Actually, only a small part of triples in the test set is optimized. In FB15k, the ratio of this optimization is 1/6. Various metrics have been improved much even with this small ratio. The capabilities of our model can be fully demonstrated on the FB15k-R, because each triplet in this set has many rules that can be matched to obtain a good optimization effect. We have recorded each triple’s rank under transX and EMRBR(X) respectively as shown in Appendix F.

heading: 4 RELATED WORK

text: For the path-based methods, Lao et al. (2011) uses Path Ranking Algorithm (PRA) (Lao & Cohen, 2010) to estimate the probability of an unseen triplet as a combination of weighted random walks. Zhang et al. (2020) and (Qu & Tang, 2019) are both the combination of Markov logic network and embedding. Kok & Domingos (2007) is mainly a clustering algorithm, clustering entity sets under multiple relationship categories. Gardner et al. (2014) makes use of an external text corpus to increase the connectivity of KB. The Neural LP model (Yang et al., 2017) compiles inferential tasks into differentiable numerical matrix sequences. Besides, many studies have modeled the path-finding problem as a Markov decision-making process, such as the DeepPath model (Xiong et al., 2017) and MINERVA (Das et al., 2017b). For the embedding methods, Nguyen (2017) has organized the existing work. Our paper divides all embedding methods into four categories, which are: translation, Bilinear & Tensor, neural network and complex vector. Firstly, for translation, the Unstructured model (Bordes et al., 2014) assumes that the head and tail entity vectors are similar without distinguishing relation types. The Structured Embedding (SE) model (Bordes et al., 2011) assumes that the head and tail entities are similar only in a relation-dependent subspace. Later, there are transE, transR, transH (Bordes et al., 2013; Lin et al., 2015; Wang et al., 2014), etc. Sadeghian et al. (2019) mines first-order logical rules from knowledge graphs and uses those rules to solve KBC. Additionally, other work (Yang et al., 2017; Galárraga et al., 2013) can extract some highquality rules from knowledge base. For the second type, DISTMULT (Yang et al., 2014) is based on the Bilinear model (Nickel et al., 2011) where each relation is represented by a diagonal matrix rather than a full matrix. SimplE (Kazemi & Poole, 2018) extends CP models (Hitchcock, 1927) to allow two embeddings of each entity to be learned dependently. The third method is to implement embedding with a neural network. Apart from the models mentioned in Section 1, NTN (Socher et al., 2013) and ER-MLP (Dong et al., 2014) also belong to this method. Fourthly, instead of embedding entities and relations in real-valued vector space, ComplEx (Trouillon et al., 2016) is an extension of DISTMULT in the complex vector space. ComplEx-N3 (Lacroix et al., 2018) extends ComplEx with weighted nuclear 3-norm. Also in the complex vector space, RotatE (Sun et al., 2019) defines each relation as a rotation from the head entity to the tail entity. QuatE (Zhang et al., 2019) represents entities by quaternion embeddings (i.e., hypercomplex-valued embeddings) and models relations as rotations in the quaternion space.

heading: 5 CONCLUSION & FUTURE WORK

text:
This paper introduces an innovative framework called EM-RBR combining embedding and rulebased reasoning, which can be easily integrated with any translation based embedding model. Unlike
previous joint models trying to get better embedding results from rules and triplets, our model allows solving completion from the reasoning perspective by conducting multi-relation path prediction, i.e. a breadth first search. We also demonstrate that EM-RBR can efficiently improve the performance of embedding methods for KGC. This makes the existing translation based embedding methods more suitable and reliable to be used in the real and large scale knowledge inference tasks.
There are two possible directions in the future. On one hand, we will combine our model with more embedding models, not just the translation-based embedding model. On the other hand, we are going to extract more and more reliable association rules to optimize our work. As mentioned above, only a part of triples are optimized when evaluating on FB15k. The fundamental reason for the rest is that there is no corresponding rule for matching. If these two problems are solved, EM-RBR can be better improved.

heading: A RULE’S VISUALIZATION

heading: B PSEUDO CODE

text: Algorithm 1 EM-RBR Input: (h, r, t) Output: Φ∼(h,r,t)

heading: C DATA MESSAGE IN EXAMPLE

text:
state triplets s1 (h,B1,m1)
? (m1, B2, t) s2 (h,B3,m2) (m2, B4, t) s3 (h,B5,m3)
? (m3, B6,m1) (m1, B2, t) s4 (h,B5,m4)
? (m4, B6,m1) (m1, B2, t) s5 (h,B7,m5)
? (m5, B8,m1) (m1, B2, t) s6 (h,B9,m6) (m6, B10,m4)
? (m4, B6,m1) (m1, B2, t) s7 (h,B11,m7) (m7, B12,m4)
? (m4, B6,m1) (m1, B2, t) s8 (h,B9,m6) (m6, B13,m8)
? (m8, B14,m4) (m4, B6,m1) (m1, B2, t) s9 (h,B9,m6) (m6, B13,m9) (m9, B14,m4) ? (m4, B6,m1) (m1, B2, t)

heading: D DATASET USED IN OUR EXPERIMENT

text:
Some triples in the test set of FB15k are selected to make up of a new test set named FB15k-R. We construct the new test set with the following steps. Firstly, sort all triples in the test set by some indicator, denoted as Z(h, r, t). Secondly, randomly select triples within different ranking ranges with a certain probability distribution, until 1,000 triples are selected. The probability distribution is described as Equaion 6.
P (event) =  0.1, event← select a triple whose Z = 0 0.2, event← select a triple whose ranking ≤ 10000 0.3, event← select a triple with ranking τ, τ > 10000 & τ ≤ 30000 0.4, event← select a triple whose ranking ≥ 30000 & Z 6= 0 (6)
Z(h, r, t) can be calculated as one of the candidates in the following.
• The number of rules each triple can match, and the matching method is the same to that in Section 2.2.1.
• The number of valid rules each triple can match. A valid rule meets ω < s∼transE(h, r, t), where ω denotes the score of a rule and s∼transE(h, r, t) denotes the score of the triple under transE.
• The maximum s∼transE(h, r, t)− ωrule for each triple, and rule ∈ rule(h,r,t). rule(h,r,t) is the set of rules (h, r, t) can match.
• s∼transE(h, r, t) − s∼reasoning(h, r, t), where s∼reasoning(h, r, t) denotes the score of (h, r, t) under EM-RBR(transE).
In our formal experiment, we choose the last strategy to generate FB15k-R.

heading: E EXPERIMENT RESULT OF WN18RR

text:
The metrics reported in this table is not better than that reported in other work8. The different hyperparameters result in this. This experiment is a verification of the enhancement effect, so it makes sense only when comparing transX and EM-RBR(X).
8https://github.com/thunlp/OpenKE

heading: F SINGLE TRIPLE RANKING ANALYSIS

text: In order to better understand the specific situation being optimized on each triplet. We respectively analyzed the corresponding ranking of each triplet under the translation model and the EM-RBR model when the head entity replacement and tail entity replacement were performed. The results were displayed in Table 7. The data item in the table is the result of sorting from largest to smallest value of s∼trans − s∼ER, where s∼trans is the ranking under the corresponding translation model and s∼E−R is the ranking under the corresponding EM-RBR model.

heading: 9 18355 2 4525 R 55951 2 3699 L 25500 1 585 R

heading: 8 14035 2 4862 L 13358 5 3741 R 54283 52 674 L

heading: 7 30883 2 5674 R 47722 2 3977 R 38773 1 640 L

heading: 6 33243 2 5883 R 33004 1 4490 L 55951 2 673 L

heading: 5 33004 1 6253 L 24243 1 4547 L 32849 1 701 L

heading: 4 36133 2 6884 L 47722 2 4569 L 24314 1 714 R

heading: 3 18355 2 7525 L 18355 2 7231 R 34891 2 733 R

heading: 2 47722 2 13900 L 32966 3 8551 L 42675 1 868 R

heading: 1 47722 2 14141 R 18355 2 12689 L 15105 2 966 L