summaries: the paper investigates what neural networks learn when trained with gradient descent, in case parts of the inputs are only partially relevant to the output. The main claim is that GD is what prevents compositionality. In a set of synthetic experiments it is shown that indeed GD learns to use all information in the input, which results in poor generalization ood when only a subset of it was relevant.

summaries: This work analyzes the effect of gradient descent training on the compositionality of the learned model. It is shown that the gradient descent would use all the available information, even when it is redundant to learn the mapping from input to the output. It is then argued that the gradient descent training has the bias against compostionality despite the model architecture. Experiments are conducted on three simple benchmarks to demonstrate that when gradient descent trained model would use redundant information and not generalize compositionally.

summaries: This paper addresses the effects of gradient descent methods onto compositionality and compositional generalization of models. The authors claim that the optimization process imposes the models to deviate compositionality, which is defined with conditional independence among random variables of input, predicted output and the ground-truth. Since compositionality is one of important features of human intelligence, it has been interested widely in the field of AI/ML such as vision, language, neuro-symbolic approaches, common sense reasoning, disentangled representation, and the emergence conditions of compositionality. As it has been not much focused on the relationship with optimizers, it is fresh and interesting. However, it is not easy to figure out the position of this paper from two reasons: (1) the definitions on compositionality in this paper are not so compatible with recent related works, which mostly consider certain structures in models [ICLR19, JAIR20] or representative problems such as visual reasoning [CVPR17] and Raven progressive matrices [PNAS17]. (2) The authors do not consider quantitative approaches such as compositionality [ICLR19] or compositional generalization [ICLR20].

abstractText: In this paper, we argue that gradient descent is one of the reasons that make compositionality learning hard during neural network optimization. We find that the optimization process imposes a bias toward non-compositional solutions. This is caused by gradient descent, trying to use all available and redundant information from input, violating the conditional independence property of compositionality. Based on this finding, we suggest that compositionality learning approaches considering only model architecture design are unlikely to achieve complete compositionality. This is the first work to investigate the relation between compositional learning and gradient descent. We hope this study provides novel insights into compositional generalization, and forms a basis for new research directions to equip machine learning models with such skills for human-level intelligence. The source code is included in supplementary material.

authors:
Vanhoucke
Vijay Vasudevan
Fernanda Viégas
Oriol Vinyals
Pete Warden
Martin Wattenberg
Martin Wicke
Yuan Yu
Xiaoqiang Zheng

title: TensorFlow: Large-scale machine learning on heterogeneous systems

authors:
Jacob Andreas
Marcus Rohrbach
Trevor Darrell
Dan Klein

title: Neural module networks

venue: In IEEE Conference on Computer Vision and Pattern Recognition

authors:
Dzmitry Bahdanau
Shikhar Murty
Michael Noukhovitch
Thien Huu Nguyen
Harm de Vries
Aaron Courville

title: Systematic generalization: What is required and can it be learned

venue: In International Conference on Learning Representations,

authors:
Anas Barakat
Pascal Bianchi

title: Convergence analysis of a momentum algorithm with adaptive step size for non convex optimization

title: The consciousness prior

venue: arXiv preprint arXiv:1709.08568,

authors:
Leon Bottou
Frank E Curtis
Jorge Nocedal

title: Optimization methods for large-scale machine learning

venue: SIAM Review,

authors:
Paco Calvo
John Symons

title: The Architecture of Cognition: Rethinking Fodor and Pylyshyn’s Systematicity Challenge

authors:
Xiangyi Chen
Sijia Liu
Ruoyu Sun
Mingyi Hong

title: On the convergence of a class of adam-type algorithms for non-convex optimization

venue: arXiv preprint arXiv:1808.02941,

title: Elements of information theory

authors:
Soham De
Anirbit Mukherjee
Enayat Ullah

title: Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison to nesterov acceleration

venue: arXiv preprint arXiv:1807.06766,

authors:
John Duchi
Elad Hazan
Yoram Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

authors:
Jerry A Fodor
Ernest Lepore

title: The compositionality papers

authors:
Jerry A Fodor
Zenon W

title: Pylyshyn. Connectionism and cognitive architecture: A critical analysis

authors:
Anirudh Goyal
Alex Lamb
Jordan Hoffmann
Shagun Sodhani
Sergey Levine
Yoshua Bengio
Bernhard Schölkopf

title: Recurrent independent mechanisms

venue: arXiv preprint arXiv:1909:10893v2,

authors:
Alex Graves
Greg Wayne
Ivo Danihelka

title: Neural turing machines

venue: arXiv preprint arXiv:1410.5401,

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

authors:
Mikael Henaff
Jason Weston
Arthur Szlam
Antoine Bordes
Yann LeCun

title: Tracking the world state with recurrent entity networks

venue: arXiv preprint arXiv:1612.03969,

authors:
Irina Higgins
Loic Matthey
Arka Pal
Christopher Burgess
Xavier Glorot
Matthew Botvinick
Shakir Mohamed
Alexander Lerchner

title: β-vae: Learning basic visual concepts with a constrained variational framework

venue: In International Conference on Learning Representations (ICLR),

authors:
Drew A Hudson
Christopher D Manning

title: Gqa: A new dataset for real-world visual reasoning and compositional question answering

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Xisen Jin
Junyi Du
Xiang Ren

title: Visually grounded continual learning of compositional semantics

venue: arXiv preprint arXiv:2005.00785,

authors:
Daniel Keysers
Nathanael Schärli
Nathan Scales
Hylke Buisman
Daniel Furrer
Sergii Kashubin
Nikola Momchev
Danila Sinopalnikov
Lukasz Stafiniak
Tibor Tihon
Dmitry Tsarkov
Xiao Wang
Marc van Zee
Olivier Bousquet

title: Measuring compositional generalization: A comprehensive method on realistic data

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Louis Kirsch
Julius Kunze
David Barber

title: Modular networks: Learning to decompose neural computation

authors:
A. Krizhevsky
I. Sutskever
G.E. Hinton

title: Imagenet classification with deep convolutional neural networks

venue: In NIPS,

authors:
Brenden Lake
Marco Baroni

title: Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks

venue: In International Conference on Machine Learning,

title: Compositional generalization through meta sequence-to-sequence learning

authors:
Brenden M Lake
Tomer D Ullman
Joshua B Tenenbaum
Samuel J Gershman

title: Building machines that learn and think like people

venue: Behavioral and Brain Sciences,

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Shuai Li
Wanqing Li
Chris Cook
Ce Zhu
Yanbo Gao

title: Independently recurrent neural network (indrnn): Building a longer and deeper rnn

venue: In the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Xiang Lisa Li
Jason Eisner

title: Specializing word embeddings (for parsing) by information bottleneck

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing,

authors:
Yuanpeng Li
Liang Zhao
Jianyu Wang
Joel Hestness

title: Compositional generalization for primitive substitutions

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),

authors:
Yuanpeng Li
Liang Zhao
Kenneth Church
Mohamed Elhoseiny

title: Compositional continual language learning

authors:
Francesco Locatello
Stefan Bauer
Mario Lucic
Gunnar Raetsch
Sylvain Gelly
Bernhard Schölkopf
Olivier Bachem

title: Challenging common assumptions in the unsupervised learning of disentangled representations

title: On the convergence of the lms algorithm with adaptive learning rate for linear feedforward networks

venue: Neural Computation,

title: Rethinking eliminative connectionism

venue: Cognitive psychology,

title: The algebraic mind: Integrating connectionism and cognitive science

venue: MIT press,

authors:
Boris T. Polyak
Anatoli B. Juditsky

title: Acceleration of stochastic approximation by averaging

venue: SIAM J. Control Optim.,

authors:
Sashank J Reddi
Satyen Kale
Sanjiv Kumar

title: On the convergence of adam and beyond

venue: In ICLR,

authors:
Clemens Rosenbaum
Ignacio Cases
Matthew Riemer
Tim Klinger

title: Routing networks and the challenges of modular and compositional computation

authors:
David E Rumelhart
Geoffrey E Hinton
Ronald J Williams

title: Learning representations by back-propagating

venue: errors. nature,

authors:
Jake Russin
Jason Jo
Randall C O’Reilly

title: Compositional generalization in a deep seq2seq model by separating syntax and semantics

authors:
Adam Santoro
Ryan Faulkner
David Raposo
Jack W. Rae
Mike Chrzanowski
Theophane Weber
Daan Wierstra
Oriol Vinyals
Razvan Pascanu
Timothy P. Lillicrap

title: Relational recurrent neural networks

venue: arXiv preprint arXiv:1806.01822,

authors:
Noam Shazeer
Azalia Mirhoseini
Krzysztof Maziarz
Andy Davis
Quoc Le
Geoffrey Hinton
Jeff Dean

title: Outrageously large neural networks: The sparsely-gated mixture-of-experts layer

venue: arXiv preprint arXiv:1701.06538,

authors:
Daniel Smilkov
Shan Carter

title: Deep playground. online demo, 2016

authors:
Alon Talmor
Oyvind Tafjord
Peter Clark
Yoav Goldberg
Jonathan Berant

title: Teaching pre-trained models to systematically reason over implicit knowledge

venue: arXiv preprint arXiv:2006.06609,

authors:
Tijmen Tieleman
Geoffrey Hinton

title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude

venue: COURSERA: Neural networks for machine learning,

authors:
Rachel Ward
Xiaoxia Wu
Leon Bottou

title: Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization

venue: arXiv preprint arXiv:1806.01811,

title: Google’s neural machine translation system: Bridging the gap between human and machine translation

authors:
D. Yu
L. Deng

title: Automatic Speech Recognition

title: Adadelta: an adaptive learning rate method

venue: arXiv preprint arXiv:1212.5701,

authors:
Dongruo Zhou
Yiqi Tang
Ziyan Yang
Yuan Cao
Quanquan Gu

title: On the convergence of adaptive gradient methods for nonconvex optimization

venue: arXiv preprint arXiv:1808.05671,

authors:
Fangyu Zou
Li Shen

title: On the convergence of adagrad with momentum for training deep neural networks

venue: arXiv preprint arXiv:1808.03408,

authors:
Fangyu Zou
Li Shen
Zequn Jie
Weizhong Zhang
Wei Liu

title: A subgradientcient condition for convergences of adam and rmsprop

venue: arXiv preprint arXiv:1811.09358,

heading: 1 INTRODUCTION

text:
Compositional generalization is the algebraic capacity to understand and produce many novel combinations from known components (Chomsky, 1957; Montague, 1970), and it is a key element of human intelligence (Minsky, 1986; Lake et al., 2017) to recognize the world efficiently and create imagination. Broadly speaking, compositional generalization is a class of out-of-distribution generalization (Bengio, 2017), where the training and test distributions are different. A sample in such a setting is a combination of several components, and the generalization is enabled by recombining the seen components of the unseen combination during inference. For example, in the image domain, an object is a combination of multiple parts or properties. In the language domain, a sentence is a combination of syntax and semantics. Each component of an output depends only on the corresponding input component, but not on other variables. We call this the conditional independence property, and will formally introduce in Section 3.
People hope to design machine learning algorithms with compositional generalization skills. However, conventional neural network models generally lack such ability. There have been many attempts to equip models with compositionality (Fodor & Pylyshyn, 1988; Bahdanau et al., 2019), and most efforts focus on designing neural network architectures (Graves et al., 2014; Andreas et al., 2016; Henaff et al., 2016; Shazeer et al., 2017; Li et al., 2018; Santoro et al., 2018; Kirsch et al., 2018; Rosenbaum et al., 2019; Goyal et al., 2019). Recently, multiple approaches showed progress in specific tasks (Li et al., 2019; 2020; Lake, 2019; Russin et al., 2019), but we still do not know why standard approaches seldom achieve good compositionality in general.
In this paper, we argue that there is a bias to prevent parameters from reaching compositional solutions, when we use gradient descent in optimization (please see Figure 1 for illustrations). This is because gradient seeks the steepest direction, so that it uses all possible and redundant input information, which contradicts to the conditional independence property of compositionality. This problem is not due to how gradient is computed, such as back propagation, but caused by the essential property of gradient. We derive theoretical relation between gradient descent and compositionality with information theory. We also provide examples and visualization to show the detailed process of how gradient resists compositionality. Based on the finding, we propose that compositionality learning approaches with model structure design (manual or searching) alone are not likely to achieve complete compositionality.
We hope this research provides new insights and forms a basis for new research directions in compositional generalization, and helps to improve machine intelligence towards human-level. The contributions of this paper can be summarized as follows.
• The novelty of this work is to find the relation between compositional learning and gradient descent in optimization process, i.e., gradient descent resists compositionality.
• We theoretically derive the result and explain why standard approaches with architecture design alone do not address compositionality.

heading: 2 RELATED WORK

text:
Compositionality Humans learn language and recognize the world in a flexible way by leveraging systematic compositionality. The compositional generalization is critical in human cognition (Minsky, 1986; Lake et al., 2017), and it helps humans to connect limited amount of learned concepts for unseen combinations. Though deep learning has many achievements in recent years (LeCun et al., 2015; Krizhevsky et al., 2012; Yu & Deng, 2012; He et al., 2016; Wu & et al, 2016), compositional generalization has not been well addressed (Fodor & Pylyshyn, 1988; Marcus, 1998; Fodor & Lepore, 2002; Marcus, 2003; Calvo & Symons, 2014).
There are observations that current neural network models do not learn compositionality (Bahdanau et al., 2019). Most recently, multiple approaches are proposed to address compositionality in neural networks (Li et al., 2019; 2020; Lake, 2019; Russin et al., 2019) for specific tasks. However, we are still not sure why compositionality is hard to achieve in general cases, and this work discusses about this problem from optimization perspective.
Another line of related work is independent disentangled representation learning (Higgins et al., 2017; Locatello et al., 2019). Its main assumption is that the expected components are statistically independent in training data. This setting does not have transferring problem in test, because all combinations have positive joint probabilities in training (please refer to Section 3).
Compositionality is applied in different areas such as continual learning (Jin et al., 2020; Li et al., 2020), question answering (Andreas et al., 2016; Hudson & Manning, 2019; Keysers et al., 2020), and reasoning (Talmor et al., 2020).
Gradient Descent Gradient descent is a powerful and general purpose optimization tool for solving large scale problems in deep neural networks. It is usually used in a stochastic way (Stochastic Gradient Descent) with mini-batches, and has many variations such as Momentum (Rumelhart et al., 1986), averaging (Polyak & Juditsky, 1992), AdaGrad (Duchi et al., 2011), AdaDelta (Zeiler, 2012), RMSProp (Tieleman & Hinton, 2012), Adam (Kingma & Ba, 2014).
Most of the previous work focus on faster reduction of loss and theoretical convergence analysis of SGD (Bottou et al., 2018; Luo, 1991; Reddi et al., 2018; Chen et al., 2018; Zhou et al., 2018; Zou & Shen, 2018; De et al., 2018; Zou et al., 2018; Ward et al., 2018; Barakat & Bianchi, 2019). In particular, this work focuses on investigating why standard neural network training only achieves limited level of compositionality by studying the relationship between gradient descent and compositionality.

heading: 3 CONCEPTS FOR COMPOSITIONALITY AND GRADIENT DESCENT

text:
We first formulate compositionality using the conditional independence property, and define compositional generalization. We then review properties of gradient for the derivation in the next section.
Conditional Independence Property for Compositionality When multiple hidden variables live in the same representation, and cannot be separated by simply splitting the representation, then these variables are entangled in the representation. For example, color and shape are two hidden variables and they share the same representation of image. Also, syntax and semantics are two hidden variables and they share the same representation of sentence. When we extract the hidden variables from their shared representation, we disentangle them.
We then consider a prediction problem, where input X and output Y have multiple entangled components that are not labeled in data, and they are aligned. For example in machine translation, X1 is input syntax, and X2 is input semantics. Y1 is output syntax, and Y2 is output semantics. The syntax of output Y1 depends only on the syntax of input X1, and the semantics of output Y2 depends only on the semantics of X2. We can formalize the alignments as conditional independence property: Yi depends only on Xi.
∀i : P (Yi|X1, . . . , XK , Y1, . . . , Yi−1, Yi+1, . . . , YK) = P (Yi|Xi).
When a model fits this property, we say it has compositionality. Note that this can be understood as a kind of sparseness property (Bengio, 2017), because it restricts effective connection between input and output components.
Compositional Generalization In compositional generalization, each sample in either training or test is a combination of several components. A test sample has a combination that does not appear in training, but each component of the test sample appears in training. We need to recombine the seen components to generalize to the test sample. We can define compositional generalization probabilistically as follows.
In train, In test, ∀i : P (Xi) > 0, P (X1, . . . , XK) = 0, P (X1, . . . , XK) > 0, ∀i : P (Yi|Xi) is high. P (Y1, . . . , YK |X1, . . . , XK) is predicted high.
Compositionality bridges the gap between training and test distributions to achieve compositional generalization. We first apply chain rule, and then use compositionality as follows.
P (Y1, . . . , YK |X1, . . . , XK) = K∏ i=1 P (Yi|X1, . . . , XK , Y1, . . . , Yi−1) = K∏ i=1 P (Yi|Xi).
When P (Yi|Xi) are all high, their product should also be high. Therefore, a model with compositionality—satisfying this conditional independence property—addresses compositional generalization.
Property of Gradient For a function f(x1, . . . , xK), the gradient∇f is the steepest direction to change the function’s value. Generally, gradient descent methods estimate ∇f using low-order local estimation. By definition, it is the vector of partial derivatives with respective to the inputs.
∇f = ∂f ∂x1 , . . . , ∂f ∂xK
We will use the following definition in later arguments.
Definition 1 (Partial derivative). Partial derivative for an input is the derivative assuming other inputs are constant.
∀i = 1, . . . ,K : ∂f(x1, . . . , xK) ∂xi = df(c1, . . . , xi, . . . , cK) dxi

heading: 4 GRADIENT DESCENT RESISTS COMPOSITIONALITY

text:
We focus on the early phase of training to show that gradient descent causes a model to use the redundant information to compute output when it has information to reduce the loss. We develop the arguments step by step. We first analyze the influence of the input on an output variable. We then consider the case of entangled inputs and one output. Finally, we discuss the case with entangled inputs and entangled outputs.
The gradient is used to reduce loss, so we aim to relate loss reduction and the influence from input to output. To do that, we use mutual information to describe the influence, and use knowledge from information theory (Definition 2, Theorem 1 and Theorem 2). We also study the impact of gradient descent to the influence, so we relate mutual information with gradient with Proposition 1.
Definition 2 (Markov chain (Cover, 1999) p.34). Random variables X, Y, Z are said to form a Markov chain in that order (denoted by X → Y → Z) if the conditional distribution of Z depends only on Y and is conditionally independent of X .
Theorem 1 (Data-processing inequality (Cover, 1999) p.34). If X → Y → Z, then I(X;Y ) ≥ I(X;Z).
Theorem 2 (Chain rule for information (Cover, 1999) p.24). For random variables X,Y, Z, I(X,Y ;Z) = I(Y ;Z|X) + I(X;Z).
Proposition 1. When ∂Y∂X is defined, I(X;Y ) > 0 ⇐⇒ ∂Y ∂X 6= 0
Proof. I(X;Y ) > 0 means X and Y are not independent, which means Y is not invariant to X .

heading: 4.1 ONE INPUT AND ONE OUTPUT

text:
We first consider a basic setting that the data has a single input X and output Y . A model f with parameters θ has input X and output Ŷ (Figure 2 middle). We optimize a loss function L. Applying the gradient ∇θL(Y, Ŷ ) reduces L(Y, Ŷ ), bringing Y and Ŷ closer. Since Y changes according to X , Ŷ is encouraged to change according to X . We look into details as follows.
In the common supervised learning setting, givenX , the ground truth Y does not depend on prediction Ŷ , which means they form a Markov chain Ŷ → X → Y . We do not require specific form of the loss function, L, but we assume that when it is reduced, Ŷ moves closer to Y , and increases the mutual information I(Ŷ , Y ). Many widely used loss functions encourage increased mutual information between model output and dataset labels. Also, training algorithms are designed to reduce loss when the input has information to do so. These assumptions are likely to hold especially in the early part of training. We also use local linear approximation when discussing gradients, i.e. dx = ∆x. We derive the proof by studying relations between random variables, and show that gradient descent increases the lower bound of mutual information between model input and output, hence the output is dependent on the input.
Proposition 2. If a small change of parameters ∆θ increases I(Y ; Ŷθ), then I(X; Ŷθ+∆θ) is positive with parameters θ + ∆θ. ∀∆θ : ∆I(Y ; Ŷθ) > 0 =⇒ I(X; Ŷθ+∆θ) > 0.
Proof. Since Y and Ŷ are conditionally independent given X , i.e., Ŷ → X → Y , with dataprocessing inequality (Theorem 1), I(Ŷ ;X) ≥ I(Ŷ ;Y ). So I(Y ; Ŷθ+∆θ) is a lower bound of I(X; Ŷθ+∆θ). By definition, ∆I(Y ; Ŷθ) = I(Y ; Ŷθ+∆θ) − I(Y ; Ŷθ), so that I(Y ; Ŷθ+∆θ) = I(Y ; Ŷθ) + ∆I(Y ; Ŷθ). We also have I(Y ; Ŷθ) ≥ 0 by definition. Therefore I(Y ; Ŷθ+∆θ) > 0.
I(X; Ŷθ+∆θ) ≥ I(Y ; Ŷθ+∆θ) = I(Y ; Ŷθ) + ∆I(Y ; Ŷθ) > 0
Proposition 3. If X has information to reduce loss L(Y, Ŷ ), ∂Ŷ∂X 6= 0 for updated parameters.
Proof. Since training algorithm reduces loss, with local linear approximation, gradient descent reduces loss. This increases mutual information, so that Proposition 2 applies. So we have I(X; Ŷθ+∆θ) > 0. With Proposition 1, we have ∂Ŷ∂X 6= 0 for the updated parameters θ + ∆θ.

heading: 4.2 ENTANGLED INPUT AND ONE OUTPUT

text:
Then, we study the case where input X is entanglement of multiple hidden input components X1, . . . , XK , and output is a single variable Ŷ that depends only on Xi. We hope to make Ŷ invariant to Xj ,∀j 6= i. For example, in a parsing task (Li & Eisner, 2019), output parse tree Y depends only on the input syntax X1, but not on input semantics X2.
For the convenience of analysis, we assume we have a fixed differentiable oracle encoder network g and decoder network g−1. g−1 maps X to X1, . . . , XK , and g maps them back.
X = g(X1, . . . , XK) X1, . . . , XK = g −1(X)
We extend the model structure with g and g−1 and use the input to g−1 as model input (Figure 2 left and middle).
Ŷ = fθ ◦ g ◦ g−1(X)
This model is exactly the same as the original one, because there is no additional trainable parameters, and g ◦ g−1 does not change X .
Proposition 4. If Xi has information to reduce loss L(Y, Ŷ ), ∂Ŷ∂Xi 6= 0 for updated parameters.
Proof. With the property of gradient (Definition 1), we can regard Xj ,∀j 6= i as constant values when computing the gradient w.r.t. Xi. So, with linear approximation, Proposition 3 applies.

heading: 4.3 ENTANGLED INPUT AND ENTANGLED OUTPUT

text:
We then discuss the case that output Y is also the entanglement of Y1, . . . , YK . Yi depends only on Xi for all i = 1, . . . ,K. This corresponds to the example of machine translation.
We assume we have a fixed differentiable oracle encoder network h and decoder network h−1. h takes Ŷ as input and produce K outputs Ŷ1, . . . , ŶK = h(Ŷ ), and h maps them back. We extend the model structure with h and h−1 (Figure 2).
Ŷ = h ◦ h−1 ◦ fθ ◦ g ◦ g−1(X)
This model is the same as the original one, because there is no additional trainable parameters and h ◦ h−1 does not change Ŷ . We derive proof with this extended model. The intuitive idea is that the reduction of loss will make each Yi contain more information of Y , and for each Yi, we can apply previous discussion. We denote Ŷ6=i = Ŷ1, . . . , Ŷi−1, Ŷi+1, . . . , ŶK .
Proposition 5. If Xj has information to reduce loss L(Y, Ŷ ) through the change of Ŷi, then ∂Ŷi∂Xj 6= 0,∀j 6= i for updated parameters.
Proof. We first use chain rule of gradient to separate the gradient to sum ofK terms, each corresponding to a Ŷi: ∂L∂θ = ∑K i=1 ∂Ŷi ∂θ ∂L ∂Ŷi . We look at a term for ∂Ŷi∂θ ∂L ∂Ŷi . Ŷ6=i are constant when computing
∂L ∂Ŷi (Definition 1), and Ŷ6=i are not included in ∂Ŷi∂θ , so that we can treat Ŷ6=i as constant for this term. We then look at the conditional mutual information I(Ŷi;Y |Ŷ6=i) for this term. With chain rule for information (Theorem 2), we have I(Ŷ ;Y ) = I(Ŷi;Y |Ŷ6=i) + I(Ŷ6=i;Y ). Since Y and Ŷ6=i are both fixed, I(Ŷ6=i;Y ) is fixed. So the change of I(Ŷ ;Y ) equals to the change of I(Ŷi;Y |Ŷ6=i). Therefore, the reduction of loss L increases the mutual information for the component. We can then apply Proposition 4. With linear approximation, the change of parameters (∆θ) computed with gradient descent is the sum of changes of parameters (∆θi) for each term, i.e., ∆θ = ∑K i=1 ∆θi. It is unlikely that a ∆θi can be cancelled by the sum of other ∆θj , j 6= i, because each component corresponds to different underlying factors, and they are not contradictory. Hence, this proposition holds.
In Proposition 4 and Proposition 5, the gradient is not zero, so an output depends on redundant input (Proposition 2) in both cases. Therefore, gradient descent resists conditional independence property of compositionality.

heading: 5 EXAMPLES

text:
In this section, we show example cases to emphasize that the theoretical result occurs practically. We focus on the conditional independence property, and we design the experiments in the following way. To test the compositionality, we use different training and test distributions, and the test prediction requires compositional generalization. We measure training and test accuracy to evaluate the ability for compositional generalization.
We use two settings in each experiment. In the first setting (A), we use both X1 and X2 as input to the model. In the second setting (B), we only use X1, and remove information of X2 by setting it to be a random input. The model architecture and other settings are the same. By comparing the test performance in the two settings, we show that a model can be trained faster with X2, but it does not hold compositionality. We run experiments for 5 times, and plot the mean and variance at each training step.

heading: 5.1 IMAGE CLASSIFICATION

text:
We use MNIST dataset (LeCun et al., 1998) in this experiment. The dataset contains pairs of input image and output label. An image is gray scale with fixed size, and a label is in the set of ten possible values {0, 1, . . . , 9}. We use two original samples (X1, Y1), (X2, Y2) to make one sample (X,Y ). X is the horizontal concatenation of X1 and X2, and Y = Y1. Note that a generated sample does not directly use the label of the second sample Y2.
We have two different settings in the experiment. In the first setting, we have the following data distribution. In training, the data are generated from the original training dataset. The samples are chosen uniformly at random in the corresponding conditions. Y1 is chosen from all possible labels, and X1 with the label is chosen. Y2 is chosen from {Y, Y + 1} (we use modular for labels), and X2 with the label is chosen. In test, the data are generated from the original test dataset. Y1, X1 are chosen in the same way as in training, but Y2 is chosen from the other eight classes {Y +2, Y +3, . . . , Y +9}, and then X2 with the label is chosen. This means, in training, X2 contains a part of information for Y , and X1 contain all information for Y . This is because Y2 is Y with half chance, and Y1 is always Y . We hope the model is trained to make Y not dependent on X2.
The second setting has the same test distribution as the first setting, but the training distributions are different. In training of the second setting, Y2 is chosen from all possible labels, so that X2 does not have information for Y .
For both the first and second settings, we use a standard convolutional neural network model with three convolution layers and two fully-connected layers. The details of model design and optimization can be found in Appendix A.
The results are shown in Figure 3a. The training accuracy improves faster in the first setting than in the second one, indicating that X2 helps to train the model quickly. In the first setting, the gap of training and test accuracy is significantly larger than that in the second setting, meaning the model does not learn compositionality in the first setting. Therefore, this experiment shows that the redundant information X2 is used to help training model quickly, but the model does not learn compositionality.

heading: 5.2 LANGUAGE LEARNING

text:
We also run an experiment of instruction language learning with SCAN dataset (Lake & Baroni, 2018). We focus on Jump task, the most difficult task in the dataset. The input is a command instruction, and the output is a corresponding action sequence. The training data include a one-word command “jump”, but other training data do not contain the word. In test data, the word “jump” appears in a multiple-words sentence with other words. Please see Table 1 for examples.
In this task, syntax and semantics are two entangled components, and it requires compositional generalization to new combinations. Syntax is the way the actions are organized, and semantic is the mapping from word to action. We also design two settings in this experiment. In the first setting, we use the original training and test data, which are from different distributions. In the second setting, we remove the dependency of input semantics to output syntax by using action words uniformly at random, but we still keep the correspondence between input words and output actions.
We use a standard sequence-to-sequence model with LSTM and attention. More details can be found in Appendix B. Following previous works on SCAN dataset, we use sentence accuracy as the evaluation metric. The results are shown in Figure 3b. We can observe that the training accuracy increases faster during the early training (steps 10-25) in the first setting than in the second setting. Also, the gap of training and test accuracy is significantly larger in the first setting than in the second setting, so the model does not learn compositionality in the first setting.

heading: 6 DISCUSSION

text:
We use a simple case to visualize the process for better understanding. We consider two random variables Y1, Y2 ∈ {0, 1}. In training, their joint distribution is uniform on combinations (Y1, Y2) ∈ {(0, 0), (0, 1), (1, 0)}, and zero on (1, 1). In test, (Y1, Y2) = (1, 1). We use uniform noises with range of 1, by subtracting them from the values (Figure 4).
X1 = Y1 − U [0, 1] X2 = Y2 − U [0, 1] We study a prediction problem with two inputs X1, X2 and one output Y1. This problem has a property that X1 contains entire information of Y1, but X2 only contains part of information of Y1. Y1 can be predicted from X1 alone, and X2 is redundant for Y1. We want to train a model f with parameters θ. f has X1, X2 as input and Ŷ as output: Ŷ = f(X1, X2; θ).
This problem requires compositional generalization, and the model needs to have compositionality. The model has three fully-connected hidden layers with ReLU activations, and each hidden layer has eight nodes. More details can be found in Appendix C.
Figure 5 shows the decision boundary for each training step. We see that the initialized parameters at step 0 output wrong predictions for samples in the upper left area, so that the samples in this area are useful to reduce loss, and they push the updated boundary in step 1 to the middle of upper right area. In the following steps, the loss is low and do not change much, so that the boundary remains stable. Therefore, the trained model does not have good compositionality. Note that there can be different solutions for this problem. We use different random seeds, and show that the trained model do not have compositionality (Figure 6).
This visualization shows an example of process for how the gradient descent makes the model to be non-compositional.

heading: 7 CONCLUSIONS

text:
In this paper, we investigate why standard neural network training seldom achieves compositional generalization by studying the relation between compositionality learning and gradient descent during
training. We find that the optimization process poses a bias towards non-compositional solutions, and this is caused by gradient descent. It tends to use all possible and redundant information from input, so that it violates conditional independence property of compositionality. Based on this study, we suggest that if only model structure design is considered in compositionality learning, it is hard to achieve good compositionality. We hope this finding provides new understanding of compositional generalization mechanisms and helps to improve machine learning algorithms for higher level of artificial intelligence.

heading: B LANGUAGE LEARNING

text:
We use a standard sequence to sequence architecture. It has embedding layer, bidirectional LSTM encoder, and unidirectional LSTM with attention decoder. The first and last states of encoder are concatenated as initial state of decoder. The embedding size is 32. The state size is 16 for encoder, and 64 for decoder. We run experiment on Jump task in SCAN dataset. The task contains 14,670 training and 7,706 test samples. In the first setting, we use the original dataset. In the second setting, we changed ’jump’ to other action word and corresponding output symbol uniformly at random.
We use Adam for optimization, with cross entropy loss. We ran 2,000 training steps. Each step has a mini-batch of 256 samples randomly and uniformly selected from training data with replacement. Initial learning rate is 0.01 and it exponentially decays by a factor of 0.96 every 100 steps. We use TensorFlow for implementation.
C VISUALIZATION
The model is a fully-connected neural network, with two input nodes and two output nodes. It has three hidden layers with ReLU activations, and each hidden layer has eight nodes. We use mini-batch size of 10, and we run 1024 steps in training with learning rate 0.1. Please see the original work (Smilkov & Carter, 2016) for more information.


summaries: The paper proposes NeoEA, an approach that further constrains KG embedding with ontology knowledge. The paper first tries to summarize the existing embedding-based entity alignment methods, stating that most of the methods choose TransE as scoring functions. But their embedding features are not aligned well compared to the neural-based or composition-based loss function. The paper, therefore, solves this problem by developing a new NeoEA architecture which shows that adding a KG-invariant ontology knowledge can minimize such difference. The experiment shows the new constraints can improve state-of-the-art baselines.

summaries: Entity alignment plays an important role in improving the quality of cross-lingual knowledge graphs. As one of the most important solutions, embedding-based methods aim at learning a semantic space where the unique entity cross knowledge graphs can have the closest distance. Most of research focus on entity-level granular, but discard the whole picture of embedding space of cross-lingual KGs. Besides the aligned entity pairs as the labelled data, this paper extended the labelled data with the conditional neural and basic axioms, which are actually sets of randomly selected entities or entities with the same relation type. Then the final objective is to align the cross-lingual knowledge graphs by both optimizing the distance of labelled entity pairs and neural axioms.

summaries: In the paper, the authors propose to minimize the discrepancy between pairs of (conditional) neural axioms to align the embedding spaces of different KGs. This method is justified by the authors' study of all kinds of OWL2 properties. The author also studied the influence of margin $\lambda$ on less constrained/long-tail entities. The authors conducted experiments by adding the proposed model on top of the best models for entity alignment. The results are mixed, but the proposed model improves the SEA and RDGCN consistently.

abstractText: Knowledge graph (KG) representation learning for entity alignment has recently received great attention. Compared with conventional methods, these embeddingbased ones are considered to be robuster for highly-heterogeneous and cross-lingual entity alignment scenarios as they do not rely on the quality of machine translation or feature extraction. Despite the significant improvement that has been made, there is little understanding of how the embedding-based entity alignment methods actually work. Most existing methods rest on the foundation that a small number of pre-aligned entities can serve as anchors to connect the embedding spaces of two KGs. But no one investigates the rationality of such foundation. In this paper, we define a typical paradigm abstracted from the existing methods, and analyze how the representation discrepancy between two potentially-aligned entities is implicitly bounded by a predefined margin in the scoring function for embedding learning. However, such a margin cannot guarantee to be tight enough for alignment learning. We mitigate this problem by proposing a new approach that explicitly learns KG-invariant and principled entity representations, meanwhile preserves the original infrastructure of existing methods. In this sense, the model not only pursues the closeness of aligned entities on geometric distance, but also aligns the neural ontologies of two KGs to eliminate the discrepancy in feature distribution and underlying ontology knowledge. Our experiments demonstrate consistent and significant improvement in performance against the existing embedding-based entity alignment methods, including several state-of-the-art ones.

authors:
Sören Auer
Christian Bizer
Georgi Kobilarov
Jens Lehmann
Richard Cyganiak
Zachary G. Ives

title: Dbpedia: A nucleus for a web of open data

venue: In ISWC,

authors:
Franz Baader
Sebastian Brandt
Carsten Lutz

title: Pushing the EL envelope

venue: In IJCAI,

authors:
Shai Ben-David
John Blitzer
Koby Crammer
Alex Kulesza
Fernando Pereira
Jennifer Wortman Vaughan

title: A theory of learning from different domains

authors:
Muhao Chen
Yingtao Tian
Mohan Yang
Carlo Zaniolo

title: Multilingual knowledge graph embeddings for cross-lingual knowledge alignment

authors:
Nicolas Courty
Rémi Flamary
Amaury Habrard
Alain Rakotomamonjy

title: Joint distribution optimal transportation for domain adaptation

venue: In NeurIPS,

authors:
Tim Dettmers
Pasquale Minervini
Pontus Stenetorp
Sebastian Riedel

title: Convolutional 2D knowledge graph embeddings

venue: In AAAI,

authors:
MS Fabian
Kasneci Gjergji
WEIKUM Gerhard

title: Yago: A core of semantic knowledge unifying wordnet and wikipedia

venue: In WWW,

authors:
Matthias Fey
Jan Eric Lenssen
Christopher Morris
Jonathan Masci
Nils M. Kriege

title: Deep graph matching consensus

authors:
Yaroslav Ganin
Victor S. Lempitsky

title: Unsupervised domain adaptation by backpropagation

venue: In ICML,

authors:
Lingbing Guo
Zequn Sun
Wei Hu

title: Learning to exploit long-term relational dependencies in knowledge graphs

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

title: Knowledge graph embedding via dynamic mapping matrix

venue: In ACL,

authors:
Seyed Mehran Kazemi
David Poole

title: Simple embedding for link prediction in knowledge graphs

venue: In NeurlIPS, Montréal,

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

title: Learning entity and relation embeddings for knowledge graph completion

authors:
Mehdi Mirza
Simon Osindero

title: Conditional generative adversarial nets

authors:
Dat Quoc Nguyen
Kairit Sirts
Lizhen Qu
Mark Johnson

title: STransE: A novel embedding model of entities and relationships in knowledge bases

authors:
Shichao Pei
Lu Yu
Robert Hoehndorf
Xiangliang Zhang

title: Semi-supervised entity alignment via knowledge graph embedding with awareness of degree difference

authors:
Shichao Pei
Lu Yu
Xiangliang Zhang

title: Improving cross-lingual entity alignment via optimal transport

authors:
Jian Shen
Yanru Qu
Weinan Zhang
Yong Yu

title: Wasserstein distance guided representation learning for domain adaptation

authors:
Zequn Sun
Wei Hu
Chengkai Li

title: Cross-lingual entity alignment via joint attribute-preserving embedding

authors:
Zequn Sun
Wei Hu
Qingheng Zhang
Yuzhong Qu

title: Bootstrapping entity alignment with knowledge graph embedding

authors:
Zequn Sun
Chengming Wang
Wei Hu
Muhao Chen
Jian Dai
Wei Zhang
Yuzhong Qu

title: Knowledge graph alignment network with gated multi-hop neighborhood aggregation

authors:
Zequn Sun
Qingheng Zhang
Wei Hu
Chengming Wang
Muhao Chen
Farahnaz Akrami
Chengkai Li

title: A benchmarking study of embedding-based entity alignment for knowledge graphs. PVLDB, 2020b

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

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

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

title: Complex embeddings for simple link prediction

authors:
Bayu Distiawan Trsedya
Jianzhong Qi
Rui Zhang

title: Entity alignment between knowledge graphs using attribute embeddings

authors:
Denny Vrandečić
Markus Krötzsch

title: Wikidata: a free collaborative knowledgebase

venue: Communications of the ACM,

authors:
Tongzhou Wang
Phillip Isola

title: Understanding contrastive representation learning through alignment and uniformity on the hypersphere

authors:
Zhen Wang
Jianwen Zhang
Jianlin Feng
Zheng Chen

title: Knowledge graph embedding by translating on hyperplanes

authors:
Zhichun Wang
Qingsong Lv
Xiaohan Lan
Yu Zhang

title: Cross-lingual knowledge graph alignment via graph convolutional networks

venue: In EMNLP,

authors:
Yuting Wu
Xiao Liu
Yansong Feng
Zheng Wang
Rui Yan
Dongyan Zhao

title: Relation-aware entity alignment for heterogeneous knowledge graphs

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

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

authors:
Rui Ye
Xin Li
Yujie Fang
Hongyu Zang
Mingzhong Wang

title: A vectorized relational graph convolutional network for multi-relational network alignment

authors:
Hao Zhu
Ruobing Xie
Zhiyuan Liu
Maosong Sun

title: Iterative entity alignment via joint knowledge embeddings

heading: 1 INTRODUCTION

text:
Knowledge Graphs (KGs), such as DBpedia (Auer et al., 2007) and Wikidata (Vrandečić & Krötzsch, 2014), have become crucial data resources for many AI applications. Although a large-scale KG offers structured knowledge derived from millions of facts in the real world, it is still incomplete by nature, and the downstream applications are always demanding for more knowledge. To resolve this issue, the task of entity alignment (EA) is proposed, which exploits the potentially-aligned entities among different KGs to facilitate knowledge fusion and exchange.
Recently, embedding-based entity alignment (EEA) methods (Chen et al., 2017; Zhu et al., 2017; Wang et al., 2018; Guo et al., 2019; Ye et al., 2019; Wu et al., 2019; Sun et al., 2020a; Fey et al., 2020) have been prevailing in this area. Their common idea is to encode semantics into embeddings and estimate the similarities by embedding distance. During this process, a small number of aligned entity pairs (a.k.a., seed alignment) are required as supervision data to align (or merge) the embedding spaces of KGs. These methods either learn an alignment function fa to minimize the difference between two entity embeddings in each seed (Wang et al., 2018), or directly map aligned entities to one embedding vector (Sun et al., 2017). Meanwhile, they also leverage a shared scoring function fs to encode semantics into representations, such that two underlying aligned entities that connect to respective sides of a seed shall have similar characteristics in their feature expression.
Although the effectiveness of current EEA methods are empirically demonstrated (Sun et al., 2020b), little efforts have been made on the theoretical analysis. In this paper, we fill this gap by formally defining a paradigm leveraged by the current methods. We show that the representation discrepancy of an underlying aligned entity pair is bounded in an indirect way by a margin λ in the scoring
function fs. Unfortunately, we further find that this margin-based bound cannot be set as tight as expected, causing that little constrain can be put on the entities with few neighbors.
To mitigate the above problem, we propose neural ontology driven entity alignment (abbr., NeoEA) , in which the entity representations are optimized jointly with a neural ontology. An ontology (Baader et al., 2005) is usually comprised of axioms that define the legitimate relationships among entities and relations. Those axioms make a KG principled (i.e., constrained by rules). For example, an “Object Property Domain” axiom in OWL2 (Baader et al., 2005) claims the valid head entities for a specific relation (e.g., the head entities of relation “birthPlace” should be in class “Person”), and it thus determines the head entity distributions of this relation. The neural ontology in this paper, however, is reversely deduced from the entity distributions. We expect to align the high-level neural ontology to diminish the discrepancy of feature distributions, as well as ontology knowledge, between two KGs.
The main contributions of this paper are threefold:
• We define the paradigm of the current EEA methods, and demonstrate that the embedding discrepancy in each potential alignment pair is implicitly bounded by the margin in the scoring function. We show that this bound cannot be as tight as we expect.
• We propose NeoEA to learn KG-invariant as well as principled representations by aligning the neural axioms of two KGs. We prove that minimizing the difference can substantially align their corresponding ontology-level knowledge, without the assumption about the existence of real ontology data.
• We conducted experiments to verify the effectiveness of NeoEA with several state-of-the-art methods as baselines. The results show that NeoEA can consistently and significantly improve the performance of the EEA methods.

heading: 2 EMBEDDING-BASED ENTITY ALIGNMENT

heading: 2.1 METHODOLOGY

text:
We first summarize the common paradigm employed by most existing EEA methods (Chen et al., 2017; Sun et al., 2017; Zhu et al., 2017; Sun et al., 2018; Wang et al., 2018; Pei et al., 2019a; Guo et al., 2019; Wu et al., 2019; Ye et al., 2019; Sun et al., 2020a):
Definition 1 (Embedding-based Entity Alignment). The input of EEA is two KGs G1 = (E1,R1, T1), G2 = (E2,R2, T2), and a small subset of aligned entity pairs S ⊂ E1 × E2 as seeds to connect G1 with G2. An EEA model consists of two neural functions: an alignment function fa, which is used to regularize the embeddings of pairwise entities in S; and a scoring function fs, which scores the representations based on the joint triple set T1∪T2. EEA estimates the alignment score of an arbitrary entity pair (e1i , e 2 j ) by their geometric distance d(e 1 i , e 2 j ), where e 1 i , e 2 j denote the embeddings of e 1 i , e2i respectively.
It is worth noting that, the existing EEA methods have different settings in relation seed alignment. Some works (Chen et al., 2017; Zhu et al., 2017) assume that all aligned relation pairs are known in advance. Others (Sun et al., 2017; 2018) suppose that the number of relations is much smaller than that of entities, i.e., |R| |E|, which means that the training data for aligning relations is sufficient. In this paper, we do not explore the details of relation seed setting. We assume that the relation representations for a well-trained EEA model are aligned.
The existing works have explored the diversity of fa. The pioneering work MTransE (Chen et al., 2017) proposed to learn a mapping matrix to cast an entity representation e1i to the feature space of G2. SEA (Pei et al., 2019a) and OTEA (Pei et al., 2019b) extended this approach by leveraging adversarial training to learn the projection matrix. Recently, a simpler yet more efficient choice was widely-used, which directly maps (e1i , e 2 i ) ∈ S to one embedding vector ei (Sun et al., 2017; Zhu et al., 2017; Trsedya et al., 2019; Guo et al., 2019). Also, researchers (Wang et al., 2018; Pei et al., 2019a; Wu et al., 2019) started to leverage a softer way to incorporate seed information, in which the distance between entities in a positive pair (i.e., supervised data in S) is minimized, while that referred to the negative one will be enlarged. As the most common choice, we consider fa as
Euclidean distance between two embeddings, such that the corresponding alignment loss can be written as follows:
La = ∑
(e1i ,e 2 i )∈S
||e1i − e2i ||+ ∑
(e1 i′ ,e 2 j′ )∈S −
ReLU (α− ||e1i′ − e2j′ ||), (1)
where S− denotes the sampled set of negative pairs. α is the minimal margin allowed between entities in each negative entity pair.
On the other hand, the scoring function fs can be also designed diversely. Most methods (Chen et al., 2017; Sun et al., 2017; Pei et al., 2019a) choose TransE as their scoring function, i.e., fs(ei, r, ej) = ||ei + r− ej ||, (ei, r, ej) ∈ T1 ∪ T2. The corresponding loss is:
Ls = ∑
τ∈T1∪T2
ReLU (fs(τ)− λ) + ∑
τ ′∈T −1 ∪T − 2
ReLU (λ− fs(τ ′)), (2)
where T −1 and T − 2 are negative triple sets. Ls is a margin-based loss in which the distance d(ei+r, ej) in a positive triple should at least be smaller than λ ≥ 0, while larger than λ for negative ones. Note that, the negative triples are usually generated by randomly replacing the head or tail entity of a positive triple. If we only look at the replaced entity, minimizing the above loss can be also understood as randomly pushing entities away from this entity. This phenomena has also been studied in Wang & Isola (2020).
Additionally, some graph neural network (GNN) based methods (Wang et al., 2018; Sun et al., 2020a; Wu et al., 2019) do not directly optimize fs. They encode the semantic information inside graph convolution. Therefore, the output vectors of GNN will be regarded as entity embeddings to feed into fa. For example, Ye et al. (2019); Wu et al. (2019); Sun et al. (2020a) leverage TransE as scoring function in the aggregation of relational neighbors.

heading: 2.2 UNDERSTANDING EEA

text:
We illustarte how an EEA model works by an example. Let (e1x, e 2 y) ∈ G1 × G2 be a potentiallyaligned entity pair. Each entity in this pair has only one neighbor, connected by the same relation r1 = r2. We assume that their neighbors are actually a pair of entities (e1i , e 2 i ) ∈ S . Therefore, if an EEA model is well-trained and almost optimal, we should have e1i = e 2 i (as La is minimized) and r1 = r2 (denoted by r for simplicity). According to Equation 2, we have:
||fs(e1x, r, e1i )|| ≈ ||fs(e2y, r, e2i )|| ≤ λ. (3)
Take the scoring function of TransE as fs, we then derive:
||e1x + r− e1i || ≤ λ, ||e2y + r− e2i || ≤ λ. (4)
As e1i = e 2 i , we can conclude that:
Proposition 1 (Discrepancy Bound). The representation difference of two potentially-aligned entities is bound by , which is proportional to the hyper-parameter λ:
||e1x − e2y|| ≤ ∝ λ. (5)
The above proposition suggests that decreasing the value of margin λ will tighten the feature discrepancy of entities in the underlying aligned entity pairs. However, we soon find that λ cannot be set as small as we want.
We consider a more complicated yet realistic example, where each entity in (e1x, e 2 y) has a considerable number of neighbors. We denote the corresponding triple sets of e1x, e 2 y as T 1ex , T 2 ey , respectively. In this setting, a well-trained EEA model should satisfy that:
∀τ ∈ T 1ex ∪ T 2 ey , ||fs(τ)|| ≤ λ. (6)
Evidently, TransE with a small margin is not sufficient to fully express the semantics contained in T 1ex ∪ T 2 ey , which has already been explored by previous works (Trouillon et al., 2016; Kazemi & Poole, 2018; Sun et al., 2019). Some empirical statistics (Sun et al., 2018) also illustrate such results. However, enlarging the margin λ will bring significant variance between e1x and e 2 y .
On the other hand, if the scoring function does not belong to the TransE family, e.g., it is neural-based like ConvE (Dettmers et al., 2018) or composition-based like ComplEx (Trouillon et al., 2016), both of which are fully expressive (Kazemi & Poole, 2018). In this case, entities with a large number of neighbors can be correctly modeled, while those with only few neighbors are less constrained. Therefore, those models allow even more diversity between e1x and e 2 y. We believe this is why they performed badly in EA task (Guo et al., 2019; Sun et al., 2020b).
In short, most existing works adopt the above implicit strategy to learn cross-KG representations for EA, which makes them struggled in balancing between the bound and the expressiveness. In this paper, we explore a new direction to explicitly align the feature distributions of two KGs, which ensures the embeddings tight and expressive.

heading: 3 NEURAL ONTOLOGY

heading: 3.1 NEURAL AXIOM AND NEURAL ONTOLOGY ALIGNMENT

text:
In real-world KGs, entities and their relation triples conform with the axioms in ontologies (Baader et al., 2005). Similarly, we call the feature distributions “neural axioms“, as aligning them also allows us to regularize the entity embeddings at a high level.
We start by defining the basic neural axiom: Definition 2 (Basic Neural Axiom).
AE ={e | e ∼ E}. (7)
Aligning the basic neural axioms A1E and A2E of two KGs is trivial, as we can take the advantages of existing domain adaptation methods (Ben-David et al., 2010; Ganin & Lempitsky, 2015a;b; Courty
et al., 2017; Shen et al., 2018), which aims to learn domain-invariant representations for various tasks. We consider the adversarial learning based ones (Ganin & Lempitsky, 2015a; Shen et al., 2018). In this way, a KG discriminator is leveraged to distinguish entity representations of G1 from those of G2 (or vice versa), while the embeddings will try to confuse the discriminator. Therefore, the same semantics in two KGs shall be encoded in the same way into the embeddings to fool the discriminator.
Specifically, if we regard two KGs G1, G2 as two different domains, and their embedding vectors as “learnable features”, we can align the above axioms by an empirical Wasserstein distance based loss (Arjovsky et al., 2017; Shen et al., 2018):
LAE = EAE1 [fw(e)]− EAE2 [fw(e)], (8)
where fw is the learnable domain critic that maps the embedding vector to a scalar value. As suggested in (Arjovsky et al., 2017), the empirical Wasserstein distance can be approximated by maximizing LAE , if the parameterized family of fw are all 1-Lipschitz. However, from Figure 1a, we observe that the trained embeddings are nearly uniformly distributed in the feature space, which we can also derive from Equation 1 and Equation 2. Recall that the alignment loss La consists of two terms. The first is∑
(e1i ,e 2 i )∈S
||e1i − e2i ||, (9)
which aims to minimize the difference of embeddings for each positive pair. The cardinality of S is usually small. But this contrastive requires a large size of negative samples, which means that ||S|| ||S−||. Therefore, the model more focuses on the second term∑
(e1 i′ ,e 2 j′ )∈S −
ReLU (α− ||e1i′ − e2j′ ||), (10)
of which the main target is to randomly push the embeddings of different entities away from each other. Furthermore, Ls is also a contrastive loss, and has a similar effect on maximizing the pairwise distance between each positive entity and its corresponding sampled negative ones. Therefore, we conclude that: Proposition 2 (Uniformity). The entity embeddings tend to be uniformly distributed in feature space as an EEA model is optimized.
The above proposition suggests that only aligning the basic axioms may be insufficient to facilitate EEA. Hence, we propose conditional neural axioms which are more specific and expressive.

heading: 3.2 CONDITIONAL NEURAL AXIOM

text:
Conditional neural axioms describe the entity (or triple) feature distributions under specific semantic conditions. Definition 3 (Conditional Neural Axioms).
AEh|ri = {e | ri, e ∼ {e | ∀e ′, (e, ri, e ′) ∈ T }} AEh,t|ri = {(eh, et) | ri, (eh, et) ∼ {(eh, et) | (eh, ri, et) ∈ T }}
(11)
where AEh|ri denotes the head entities feature distribution conditioned on the relation embedding ri, the similar to AEh,t|ri (we reduce (eh, ri, et)|ri to (eh, et)|ri for simplicity). Numerous methods are proposed to process the neural conditioning operation, ranging from addition and concatenation (Mirza & Osindero, 2014; Wang et al., 2014; Yang et al., 2015), to matrix multiplication (Lin et al., 2015a; Ji et al., 2015; Nguyen et al., 2016). Comparing with elaborating this operation, we value more on its common merit, which can be understood as projecting the entities to a relation-specific subspace (Wang et al., 2014; Lin et al., 2015a; Nguyen et al., 2016). Hence, the corresponding feature distributions conditioned on different relation embeddings become discriminative, rather than almost uniformly distributed in original feature space (Lin et al., 2015a).
Furthermore, conditional neural axioms capture high-level ontology knowledge.
Theorem 1 (Expressiveness). Aligning the conditional neural axioms minimizes the discrepancy of two KGs at ontology level.
Proof. See Appendix A for details. We take AEh|ri as an example, which can summarize the empirical “Object Property Domain” axiom of ri in OWL2 (Baader et al., 2005). Supposed there exists such an axiom that states the head entities of ri should belong to some specific class c (e.g., only head entities under class "Person" have the relation "birthPlace"). We further suppose that there exists a classifier fc(e) ∈ [0, 1], such that fc(ej) = 1 if head entity ej belongs to class c, and 0 otherwise. Then, with the knowledge of the given axiom, one may derive the following rule:
∀e ∈ {e | ∀e′, (e, ri, e′) ∈ T1 ∪ T2}, fc(e) = 1, (12)
which is equivalent to: EA1
Eh|ri [fc(e)] = EA2 Eh|ri [fc(e)] = 1, (13)
both of which means that all head entities of ri in either KG should be correctly classified to c. Then, we have:
EA1 Eh|ri [fc(e)]− EA2 Eh|ri [fc(e)] = 0. (14)
In fact, we do not have such knowledge about ri and class c, instead we can leverage a neural function fc′(e|ri) to empirically estimate fc. In this way, AsEh|ri and A t Eh|ri are supposed to be aligned to minimize the loss correponding to the above rule. Therefore, we deduce this problem back to a similar form to Equation 8, i.e.,
LAEh|ri = EA1Eh|ri [fc ′(e | ri)]− EA2 Eh | ri [fc′(e|ri)], (15)
which suggests that aligning the above conditional neural axioms can minimize the discrepancy of potential “Object Property Domain” axioms between two KGs.
Example 1 (OWL2 axiom: ObjectPropertyDomain). As shown in Figure 1b and Figure 1c, we assume that the head entity of relation “genre” are under class “Work of Art” (although it does not exist in the dataset). It is clear that the head entity feature distributions are only partially algined in Figure 1b, while those in Figure 1c are matched well.
In Figure 1d we illustrate a more complicated example. The head entities of relations “genre” and “writer” mainly belong to “Work of Art”, which show overlapped distributions (blue-orange, pink-purple) in the figure. By contrast, there exists a clear decision boundary between them and the distributions conditioned on relation “birthPlace” (red-green), as the head entities of relation
“birthPlace” are under class “Person”.
Example 2 (OWL2 axiom: SubObjectPropertyOf). We consider two relations “musicalArtist” and “artist” as example, where the former one is the sub-relation of the later one. In Figure 1e, the triple distributions conditioned on “musicalArtist” (pink-purple) are covered by those conditioned on “artist” (orange-blue).

heading: 3.3 ARCHITECTURE OF NEOEA

text:
We illustrate the overall structure of NeoEA in Figure 2. It can be divided into three modules:
Entity Alignment. This module aims at encoding the semantics of KGs into embeddings. Almost all existing EEA models can be used here, no matter what the input data looks like (triples or a adjacency matrix).
KG Sampling. For each KG, we choose to sample a sub-KG to estimate the data distributions of neural axioms. Comparing with separately sampling candidates for each axiom, it is more efficient especially when the size of KGs get bigger, because we only sample once at each iteration.
Neural Ontology Alignment. As aforementioned, for each pair of representation distributions, we align them by minimizing the empirical Wasserstein distance. Please see Appendix B for the detailed implementation of neural ontology alignment.

heading: 4 EXPERIMENTS

text: In this section, we empirically verify the effectiveness of NeoEA by a series of experiments, with several state-of-the-art methods as baselines.

heading: 4.1 IMPLEMENTATION

text:
We illustrate the implementation of NeoEA in Algorithm 1. The whole framework is based on the OpenEA project (Sun et al., 2020b), which includes the implementations of latest EEA methods. Specifically, we implemented neural ontology as an external module, based on which we modified only the initialization of the original project. In this sense„ the EEA methods were unaware of the existence of neural ontologies. Furthermore, we kept the optimal hyper-parameter settings in OpenEA to ensure fair comparison.
We selected several best-performing and representative methods as our baselines:
• BootEA (Sun et al., 2018), a TransE-based EEA model with only structure data. • SEA (Pei et al., 2019a), a TransE-based model with both structure and attribute data. • RSN (Guo et al., 2019), an RNN-based EEA model with only structure data. • RDGCN (Wu et al., 2019), a GCN-based model with both structure and attribute data.
The data distributions of some previous benchmarks such as JAPE (Sun et al., 2017) and BootEA (Sun et al., 2018) are clearly different from those of real-world KGs, which means that conducting experiments on those benchmarks cannot reflect the realistic performance of an EEA model (Guo et al., 2019; Sun et al., 2020b). Therefore, we consider the latest benchmark (Sun et al., 2020b), which consists of four sub-datasets, with two different density settings. Specifically, “D-W”, “D-Y” denote “DBpedia (Auer et al., 2007)-WikiData (Vrandečić & Krötzsch, 2014)”, “DBpedia-YAGO (Fabian et al., 2007)”, respectively. “EN-DE” and “EN-FR” denote two cross-lingual datasets, both of which
are sampled from DBpedia. “V1” denotes the sampled KGs having the similar distributions as the original KGs, while “V2” denotes the sampled KGs with doubled density. For detail statistics, please refer to Sun et al. (2020b).
Algorithm 1 NeoEA 1: Input: two KGs G1, G2, the alignment seed set S, the EEA modelM(fs, fa), number of steps
for NeoEA n; 2: Initialize all variables; 3: repeat 4: for i := 1 to n do 5: Sample sub-KGs from respective KGs G1, G2; 6: Compute the Wasserstain distance based loss Lw for each pair of neural axioms; 7: Optimize the Wasserstain distance critic fw by maximizing Lw. 8: end for 9: Sample sub-KGs from respective KGs G1, G2;
10: Compute Wasserstain distance based loss Lw for each pair of neural axioms; 11: Compute the losses Lr, Ls of the EEA modelM; 12: Optimize the EEA model and embeddings by minimizing Lr, Ls, Lw; 13: until the alignment loss on validation set converged.

heading: 4.2 EMPIRICAL COMPARISONS

text: The main results are shown in Table 1, from which we find that: (1) The performance of four baseline models varied from different datasets, but all of them gained improvement with NeoEA. (2) The performance improvement on SEA and RDGCN was more significant than that on BootEA and RSN, as both BootEA and RSN are not typical EEA models. BootEA has a sophisticated bootstrapping procedure, which may be difficult to be injected with NeoEA. RSN tries to capture long-term dependencies among entities and relations. The complicated objective may be conflict with NeoEA more or less. However, on some datasets (e.g., EN-DE, V1), we still observe relatively significant improvement. Therefore, we believe the performance of these two models can be further refined through a joint hyper-parameter turning with NeoEA, which we leave to future work.

heading: 4.3 ABLATION STUDY

text:
We designed an ablation study which is expected to empirically prove some claims in Section 3. We choose the current state-of-the-art model RDGCN as our baseline. As shown in Table 2, “Full”
Table 2: Results of ablation study based on the best-performing model RDGCN, on V1 datasets.
Models EN-FR EN-DE D-W D-Y
H@1 H@5 MRR H@1 H@5 MRR H@1 H@5 MRR H@1 H@5 MRR
Full .775 .868 .817 .846 .908 .874 .527 .671 .592 .941 .972 .955 Partial .771 .863 .813 .840 .900 .871 .523 .669 .590 .936 .971 .952 Basic .755 .853 .799 .827 .895 .858 .512 .656 .578 .931 .969 .948 Original .755 .854 .800 .830 .895 .859 .515 .669 .584 .931 .969 .949
Figure 3: Normalized histgrams of alignment rankings on EN-FR, V1 (left, long-tail entities; right, popular entities).
Table 3: Average ranking improvement.
Datasets Overall Popular Long-tail
EN-FR 63.5 36.9 116.7 EN-DE 13.0 8.1 23.4 D-W 43.5 34.5 61.3 D-Y 119.3 59.2 214.2
denote NeoEA with full set of neural axioms. “Partial” denotes NeoEA that removed the conditional triple axioms. We further removed the conditional entity axioms from “Partial” to construct “Basic”, and the last one “Original” denotes the original EEA model. From the results we observe that: (1) Aligning basic axioms was less effective or even harmful to the model, which verifies Proposition 2 (Uniformity). (2) Aligning only a part of conditional axioms AEh|ri ,AEt|ri that describe entity feature distributions conditioned on relation representations was significantly helpful for the model. (3) Additional improvement was observed on the model with the full conditional axioms. Note that, the improvement from “Partial” to “Full” was not as significant as that from "Basic" to “Partial”. This is because that the conditional triple axioms mainly describe the axioms between relations (see Appendix A). Due to the sampling strategy of the existing datasets, the number of relations is relatively small. Few correlated relation pairs exist in the datasets, resulting in limited improvement with conditional triple neural axiom alignment.

heading: 4.4 FURTHER ANALYSIS ON THE BOUND

text: We have shown that the discrepancy between each underlying aligned pair is bounded by associated with λ, in Section 2. But we still expect to obverse empirical statistics to verify this point. To this end, we manually split the entities into two group: (1) long-tail entities, which are disconnected to seeds and have at most two neighbors; (2) popular entities, the remaining. We draw the histgrams of alignment rankings w.r.t. respective groups based on the EEA model SEA. From Figure 3, we can find that the proportion of the inexact alignments (i.e., ranking > 5) for long-tail entities is evidently larger than that of popular entities, especially for the bins [50, 100]. This verified that the long-tail entities are less constrained compared to those popular entities. Furthermore, with NeoEA, the rankings of those long-tail entities were also improved more significantly compared with those of popular entities, which empirically proved that NeoEA tightened the representation discrepancy of those entities that were less restrained. We report the average ranking improvement on four datasets (V1) in Table 3, which shows consistent observations.

heading: 5 CONCLUSION

text: In this paper, we proposed a new approach to learn representations for entity alignment. We proved its expressiveness theoretically and demonstrated its efficiency by conducting experiments on the latest benchmarks. We observed that four state-of-the-art EEA methods gained evident improvements with NeoEA. Finally, we showed that the proposed conditional neural axioms are the key to improve the performance of current EEA methods.

heading: A PROOF FOR THEOREM 1

text:
Aligning the conditional neural axioms minimizes the discrepancies of two KGs at ontology level.
Proof. We split the proofs by different axioms referred to OWL2 (Baader et al., 2005).
ObjectPropertyDomain | ObjectPropertyRange. The proof for ObjectPropertyDomain has been presented in Section 3, and that for ObjectPropertyRange is similar.
ReflexiveObjectProperty | IrreflexiveObjectProperty. If we say that a relation ri is reflexive, it must satisfy
∀(e, ri, e′) ∈ T , (e, ri, e) ∈ T , (16) which means each head entities of ri must be connected by ri to itself. The above rule suggests that we can align such axioms by minimizing the discrepancy between triple distributions conditioned on relation ri, i.e., aligning A1E(h,t)|ri with A 2 E(h,t)|ri . The similar to IrreflexiveObjectProperty axiom.
FunctionalObjectProperty | InverseFunctionalObjectProperty. We first introduce FunctionalObjectProperty axiom. It compels each head entity e connected by relation ri to have exact one tail entity, implying the following rule:
∀(e, ri, e′) ∈ T ,∀e′′ ∈ E , (e, ri, e′′) /∈ T . (17) Evidently, the above rule is also related to the triple distribution conditioned on ri. The similar to the InverseFunctionalObjectProperty axiom.
SymmetricObjectProperty | AsymmetricObjectProperty. The first axiom can state a relation ri is symmetric, that is,
∀(e, ri, e′) ∈ T , (e′, ri, e) ∈ T . (18)
It is also related to the triple distributions referred to ri, implying that directly aligning A1E(h,t)|ri with A2E(h,t)|ri is sufficient to minimize the difference. The proof for AsymmetricObjectProperty axiom is similar.
SubObjectPropertyOf | EquivalentObjectProperties | DisjointObjectProperties | InverseObjectProperties. We show that these axioms also define rules related to triple distributions condionted on relations. We start from SubObjectPropertyOf, which can state that relation ri is a subproperty of relation rj (e.g., “hasDog” is one of the subproperties of “hasPet”). We formulate it as:
∀(e, ri, e′) ∈ T , (e′, rj , e) ∈ T . (19) To algin the potential SubObjectPropertyOf axioms between two KGs, we can respectively align (A1E(h,t)|ri ,A 2 E(h,t)|ri) and (A 1 E(h,t)|rj ,A 2 E(h,t)|rj ), such that the joint one (A 1 E(h,t)|ri,rj ,A 2 E(h,t)|ri,rj ) will also be aligned.
Similarly, if ri and rj are equivalent, we can interpret the axiom as
∀(e, ri, e′) ∈ T , (e′, rj , e) ∈ T ; ∀(e, rj , e′) ∈ T , (e′, ri, e) ∈ T . (20) If they are disjoint, the corresponding rule will be
∀(e, ri, e′) ∈ T , (e, rj , e′) /∈ T . (21) If they are inverse to each other, the rule is
∀(e, ri, e′) ∈ T , (e′, rj , e) ∈ T . (22)
TransitiveObjectProperty. We show that this axiom are also related to triple distributions conditioned on ri. Supposed that a relation ri is transitive, then one can derive the following rule:
∀(e, ri, e′) ∈ T &(e′, ri, e′′) ∈ T , (e, ri, e′′) ∈ T , (23) which means we can align the potential TransitiveObjectProperty axioms via minimizing the distribution discrepancy between A1E(h,t)|ri and A 2 E(h,t)|ri .

heading: B NEURAL ONTOLOGY ALIGNMENT

text:
There exist several ways to implement the neural ontology alignment module. But it must satisfy two requirements: (1) Suitability. As mentioned in Section 2, different EEA benchmarks have different assumptions about the relation alignments, which means that in some cases we cannot obtain all aligned relation pairs in advance. (2) Efficiency. As there may exist millions of triples, we should consider the efficiency of performing the conditioning operations.
Therefore, in our implementation, we do not perform pair-wise sampling, either the pair-wise neural axiom alignment. We share the parameters of Wasserstein-distance critic only in each type of neural axiom, which saves parameters and avoid the situation that some relations only have a small number of corresponding triples. Furthermore, this also allows us to perform fast mini-batch training by aligning the axioms belonging to the same type in one operation. Given the sample KGs G′1 = (E ′1,R′1, T ′1 ), G′2 = (E ′2,R′2, T ′2 ), the corresponding batch loss is:
Lsep = LAE′ + ( ∑ r′∈R′1 EAE′ h |r′ [fh|r(e|r′)]− ∑ r′∈R′2 EAE′ h |r′ [fh|r(e|r′)])
+ ( ∑ r′∈R′1 EAE′ h,t |r′ [fh,t|r(eh, et|r′)]− ∑ r′∈R′2 EAE′ h,t |r′ [fh,t|r(eh, et|r′)]),
(24)
where LAE′ is the basic axiom loss under the sampled KGs. fh|r and fh,t|r are the critic functions of the two types of neural axioms, respectively. The loss Lbatch will approximate to that in a pair-wise calculation when the batch size is considerably greater than the number of relations. We take the second term of the above equation as example. For pair-wise estimation, the corresponding loss should be: ∑
(r1,r2)∈Sr
(EAE′ h |r1 [fh|r(e|r1)]− EAE′ h |r2 [fh|r(e|r2)])
= ∑
(r1,r2)∈Sr
EAE′ h |r1
[fh|r(e|r1)]− ∑
(r1,r2)∈Sr
EAE′ h |r2
[fh|r(e|r2)], (25)
where Sr ⊂ R1 × R2 denotes the set of all aligned relation pairs. The above equation suggests that the pair-wise loss is based to the respective relation sets of two KGs, not constrained by each pair of aligned relations. Oftentimes, the number of relations is much smaller than the number of sampled triples in one batch, which means thatR′1,R′2 in Equation 24 can cover a large proportion of elements in the full relation setsR1,R2. Therefore, we used Lsep to approximate the pair-wise loss in the implementation.