Knowledge graphs (KGs) are typically highly incomplete. Therefore substantial research has been directed toward typically machine-learning-based approaches for knowledge graph completion (KGC), i.e., predicting missing triples from the data stored in the KG. KG embedding models (KGEs) have yielded promising results for KGC. In practice, the data management community typically represents major properties of data through constraints, axioms, or dependencies expressed as logical rules. However, any current KGE cannot capture vital logical rules, i.e., infer missing triples while adhering to such rules. For instance, correctly capturing general composition and jointly capturing composition and hierarchy rules is still an open problem. This work introduces the ExpressivE model that bridges this gap between the data management and machine learning community. ExpressivE embeds pairs of entities as points and relations as hyper-parallelograms in the virtual triple space R2. This model design allows ExpressivE to capture a rich set of logical rules jointly and display any supported rule through the spatial relation of hyper-parallelograms, additionally ofering an intuitive and consistent geometric interpretation of ExpressivE embeddings and captured rules. Experimental results on standard KGC benchmarks reveal that ExpressivE is competitive with state-of-the-art KGEs and even significantly outperforms them on WN18RR. This short paper is based on our recently published ICLR 2023 paper [1].
One of the key challenges in the data management community is to bring together machine learning models and – typically logic-based – data management approaches. This challenge is especially apparent in the field of graph data management, particularly when considering knowledge graphs (KGs) that are typically highly incomplete [2]: On the one hand, the use of machine learning models, called knowledge graph embedding models (KGEs), has achieved promising results for knowledge graph completion (KGC) [3], i.e., for automatically predicting missing triples. On the other hand, the data management community typically represents major properties of data through constraints, axioms, or dependencies expressed as logical rules.
However, there is a major challenge in this: Many KGEs cannot respect vital logical rules – termed capturing rules – which describes a KGE’s ability to infer missing triples while adhering to such logical rules. Composition of relations is a particularly important constraint or dependency for data management – even more so in graph data management, where it allows to describe paths. Recently, however, it was discovered that existing KGEs only capture a fairly limited notion of composition [4, 5, 6, 7], solely capturing compositional definition , not general composition (see Table 1 for the defining formulas). Even more, while existing KGEs capture hierarchy [8, 9, 10, 5] and compositional definition [ 11, 12, 4, 6] individually, they cannot capture both rules simultaneously (see Table 1).
While the extensive research on composition [11, 12, 4, 6] and hierarchy [8, 10, 9, 5] highlights
their importance, any KGE so far is incapable of: (
KGEs, even significantly outperforming them on some datasets.
KGs can be represented as large collections of triples (ℎ, ) over a finite set of relations ∈ R and entities ℎ, ∈ E, where we call ℎ the triple’s head and its tail. In what follows, we assume the standard definition of capturing logical rules [ 12, 5, 1]. This means intuitively that a KGE captures a rule if a set of parameters exists such that the logical rule is captured exactly (i.e., any logically inferrable triple is predicted by the KGE) and exclusively (i.e., no unwanted rule is supported by the KGE’s predictions).
ExpressivE embeds entities ∈ via a vector ∈ R, representing points in the embedding
space R and relations ∈ as hyper-parallelograms in the virtual triple space R2 (see
Figure 1a for a visual representation). More specifically, ExpressivE assigns to a relation for
each of its arity positions ∈ {ℎ, }: (
Where |.| represents the element-wise absolute value of a vector , ⊙ represents the Hadamard product, and ⪯ represents the element-wise less or equal operator. As it is very complex to interpret this model in the embedding space R, we introduce the virtual triple space R2 next that eases reasoning about ExpressivE’s parameters and inference capabilities. (a) (b)
Interpretation. We construct the virtual triple space R2 by concatenating the head ℎ and tail embeddings . We call the 2-dimensional sub-space of R2, created from the -th dimension of ℎ and , the -th correlation subspace, as it visualizes the captured logical rules of this dimension. As visualized in Figure 1a, the relation parameters define a hyper-parallelogram in R2. Using these notions, we analyze ExpressivE’s theoretical capabilities next.
Expressiveness. It is vital for a KGE to be fully expressive [5], i.e., to be able to represent any graph over and , as otherwise, the KGE may underfit certain KGs severely. Theorem 4.1 proves that ExpressivE is fully expressive.
Theorem 4.1 (Expressive Power). ExpressivE can capture any arbitrary graph over and if the embedding dimensionality is at least in (|| * | |).
Proof Sketch. Theorem 4.1 is proven by induction, starting with an ExpressivE embedding that captures the complete graph, i.e., any triple over and is true. Each induction step shows that we can alter the ExpressivE embedding to make an arbitrarily picked triple of the form ( , ) with ∈ , , ∈ and ̸= false. Finally, we add || * | | dimensions to make any self-loop – i.e., any triple of the form ( , ) with ∈ and ∈ – false. □
Logical Rules. Theorem 4.2 reveals that ExpressivE can capture any of the most prominently analyzed rules [11, 12, 8, 10, 9, 5] listed in Table 1.
Theorem 4.2. ExpressivE captures (a) symmetry, (b) anti-symmetry, (c) inversion, (d) hierarchy, (e) intersection, (f) mutual exclusion, (g) general composition, and (h) compositional definition. Figure 1b shows how several one-dimensional ExpressivE embeddings capture rules (a)-(f). ExpressivE captures: (a) symmetry via symmetric hyper-parallelograms, (b) anti-symmetry via hyper-parallelograms that do not overlap with their mirror image, (c) inversion via 2’s hyper-parallelogram being the mirror image of 1’s, (d) hierarchy via 2’s hyper-parallelogram subsuming 1’s, (e) intersection via 3’s hyper-parallelogram subsuming the intersection of 1’s and 2’s, and (f) mutual exclusion via non-overlapping hyper-parallelograms.
Composition. Capturing rules (g)-(h) is more complex. In particular, compositional definition is of the form 1(, ) ∧ 2(, ) ⇔ (, ), where we call the compositionally defined relation. This rule defines a relation that describes the start and end entities of a path →−1 →−2 . Since any two 1 and 2 can instantiate the body of a compositional definition rule, any such pair may produce a new . Interestingly, compositional definition translates analogously into the virtual triple space: Intuitively, this means that the embeddings of any two 1 and 2 define for a convex region — which we call the compositionally defined region — that captures 1(, ) ∧ 2(, ) ⇔ (, ), leading to Theorem 4.3. Based on this insight, ExpressivE captures compositional definition by embedding with the compositionally defined region, defined by the embeddings of 1 and 2. Furthermore, ExpressivE captures general composition by embedding with a hyper-parallelogram that subsumes the compositionally defined region. Finally, capturing composition through the subsumption of spatial regions allows ExpressivE to provably capture composition for 1-N, N-1, and N-M relations. Theorem 4.3. Let 1, 2, ∈ be relations, 1, 2 be their ExpressivE embeddings, and assume 1(, ) ∧ 2(, ) ⇔ (, ) holds. Then there exists a region in the virtual triple space R2 such that (i) 1, 2, and capture 1(, ) ∧ 2(, ) ⇔ (, ) and (ii) is convex. KGE Families. Interpretable KGEs consist of three families [1]: Functional KGEs, embedding relations as functions; bilinear KGEs, embedding relations as bilinear products; and spatial KGEs, embedding relations as regions. ExpressivE is the first KGE belonging to both the spatial and functional family. BoxE [5] is its closest spatial, and RotatE [12] is its closest functional relative.
Space Complexity. For a -dimensional embedding, RotatE and BoxE have each (2|| + 2||), whereas ExpressivE has (|| + 6||) parameters, where || is the number of entities and || the number of relations. Since || << || in most graphs, ExpressivE almost halves the number of parameters for a -dimensional embedding compared to BoxE and RotatE.
Benchmark Results. Table 2 reveals that ExpressivE, with only half the number of parameters of BoxE and RotatE, performs best among its own model family on FB15k-237 and is competitive with TuckER, especially in MRR. Even more, ExpressivE outperforms all competing KGEs significantly on WN18RR. The significant performance increase of ExpressivE on WN18RR is likely due to WN18RR containing both hierarchy and composition rules in contrast to FB15k-237 (similar to the discussion of [5]). Thus, ExpressivE is highly parameter eficient compared to related KGEs while reaching competitive performance on FB15k-237 and even new SOTA performance on WN18RR, supporting the extensive theoretical results of our paper.
In this work, we have introduced ExpressivE, a KGE that (
This work has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/VRG18013, 10.47379/NXT22018, 10.47379/ICT2201]; and the Christian Doppler Research Association (CDG) JRC LIVE. 1https://github.com/AleksVap/ExpressivE [2] R. West, E. Gabrilovich, K. Murphy, S. Sun, R. Gupta, D. Lin, Knowledge base completion via search-based question answering, in: Proceedings of the 23rd International Conference on World Wide Web, WWW ’14, Association for Computing Machinery, 2014, p. 515–526. [3] Q. Wang, Z. Mao, B. Wang, L. Guo, Knowledge graph embedding: A survey of approaches and applications, IEEE Transactions on Knowledge and Data Engineering (2017) 2724–2743. [4] S. Zhang, Y. Tay, L. Yao, Q. Liu, Quaternion knowledge graph embeddings, in: H. M.
Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, R. Garnett (Eds.), Advances in Neural Information Processing Systems 32: Conference on Neural Information Processing Systems, 2019, pp. 2731–2741. [5] R. Abboud, İ. İ. Ceylan, T. Lukasiewicz, T. Salvatori, Boxe: A box embedding model for knowledge base completion, in: H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems 33: Conference on Neural Information Processing Systems, 2020. [6] H. Lu, H. Hu, Dense: An enhanced non-abelian group representation for knowledge graph embedding, CoRR abs/2008.04548 (2020). arXiv:2008.04548. [7] C. Gao, C. Sun, L. Shan, L. Lin, M. Wang, Rotate3d: Representing relations as rotations in three-dimensional space for knowledge graph embedding, in: M. d’Aquin, S. Dietze, C. Hauf, E. Curry, P. Cudré-Mauroux (Eds.), CIKM ’20: The 29th ACM International Conference on Information and Knowledge Management, ACM, 2020, pp. 385–394. [8] B. Yang, W. Yih, X. He, J. Gao, L. Deng, Embedding entities and relations for learning and inference in knowledge bases, in: Y. Bengio, Y. LeCun (Eds.), 3rd International Conference on Learning Representations, 2015. [9] S. M. Kazemi, D. Poole, Simple embedding for link prediction in knowledge graphs, in: S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems 31: Conference on Neural Information Processing Systems, 2018, pp. 4289–4300. [10] T. Trouillon, J. Welbl, S. Riedel, É. Gaussier, G. Bouchard, Complex embeddings for simple link prediction, in: M. Balcan, K. Q. Weinberger (Eds.), Proceedings of the 33nd International Conference on Machine Learning, volume 48 of JMLR Workshop and Conference Proceedings, JMLR.org, 2016, pp. 2071–2080. [11] A. Bordes, N. Usunier, A. García-Durán, J. Weston, O. Yakhnenko, Translating embeddings for modeling multi-relational data, in: C. J. C. Burges, L. Bottou, Z. Ghahramani, K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 26: 27th Conference on Neural Information Processing Systems 2013., 2013, pp. 2787–2795. [12] Z. Sun, Z. Deng, J. Nie, J. Tang, Rotate: Knowledge graph embedding by relational rotation in complex space, in: 7th International Conference on Learning Representations, 2019. [13] D. Rufinelli, S. Broscheit, R. Gemulla, You CAN teach an old dog new tricks! on training knowledge graph embeddings, in: 8th International Conference on Learning Representations, 2020. [14] B. Yang, W. Yih, X. He, J. Gao, L. Deng, Embedding entities and relations for learning and inference in knowledge bases, in: Proceedings of the Third International Conference on Learning Representations, 2015. [15] I. Balazevic, C. Allen, T. M. Hospedales, Tucker: Tensor factorization for knowledge graph completion, CoRR abs/1901.09590 (2019). arXiv:1901.09590.