Source-linked AI summary
InteractE: Improving Convolution-based Knowledge Graph Embeddings by Increasing Feature Interactions
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, Nilesh Agrawal, Partha Talukdar
TL;DR
Incomplete knowledge graphs require link prediction from learned entity and relation representations, but ConvE captures a limited number of feature interactions. InteractE increases these interactions through feature permutation, checkered reshaping, and circular convolution, with consistent improvements over ConvE across multiple datasets.
Problem
Knowledge graphs are often incomplete, and ConvE’s convolutional approach captures a limited number of entity–relation feature interactions.
Method
InteractE increases feature interactions using feature permutation, checkered feature reshaping, and circular convolution.
Results
InteractE consistently improves link prediction performance across multiple datasets, including average MRR gains of 9%, 7.5%, and 23% over ConvE on FB15k-237, WN18RR, and YAGO3-10.
Takeaways & Limitations
The results support the paper’s hypothesis that increasing heterogeneous feature interactions benefits link prediction.
Takeaways & Limitations
The theoretical analysis restricts reshaped outputs to square matrices, although the authors state that the results extend to the general case.
Abstract
from arXiv · showhide
Most existing knowledge graphs suffer from incompleteness, which can be alleviated by inferring missing links based on known facts. One popular way to accomplish this is to generate low-dimensional embeddings of entities and relations, and use these to make inferences. ConvE, a recently proposed approach, applies convolutional filters on 2D reshapings of entity and relation embeddings in order to capture rich interactions between their components. However, the number of interactions that ConvE can capture is limited. In this paper, we analyze how increasing the number of these interactions affects link prediction performance, and utilize our observations to propose InteractE. InteractE is based on three key ideas -- feature permutation, a novel feature reshaping, and circular convolution. Through extensive experiments, we find that InteractE outperforms state-of-the-art convolutional link prediction baselines on FB15k-237. Further, InteractE achieves an MRR score that is 9%, 7.5%, and 23% better than ConvE on the FB15k-237, WN18RR and YAGO3-10 datasets respectively. The results validate our central hypothesis -- that increasing feature interaction is beneficial to link prediction performance. We make the source code of InteractE available to encourage reproducible research.
1 Introduction
Knowledge graphs are often incomplete, motivating link prediction from learned entity and relation embeddings. InteractE extends ConvE to increase feature interactions, and experiments support their benefit for link prediction.
- Most existing knowledge graphs are incomplete, so link prediction infers missing facts from known facts.
- Shallow embedding methods have limited expressiveness, while increasing embedding size raises parameters and restricts scalability.
- ConvE applies convolutional filters to 2D reshaped entity and relation embeddings to increase component interactions.
- InteractE increases interactions through feature permutation, checkered feature reshaping, and circular convolution.
- The authors release InteractE’s source code and datasets as supplementary material.
2 Related Work
Related work spans non-neural knowledge graph embeddings and convolution-based scoring models, with ConvKB excluded because of inconsistent performance and evaluation concerns.
- Non-neural methods use operations such as dot products and matrix multiplications, with relations represented as vectors, matrices, tensors, or Gaussian distributions.
- ConvTransE applies convolution directly to stacked subject and relation embeddings, while SACN combines weighted graph convolution with ConvTransE.
- ConvKB uses width-1 convolution over stacked subject, relation, and object embeddings, but is excluded because performance is inconsistent and its evaluation procedure was questioned.
3 Background
Knowledge graph link prediction ranks candidate triples using a learned scoring function. ConvE uses 2D convolution over reshaped subject and relation embeddings to score object candidates.
- Link prediction seeks new triples (s′, r′, o′) by learning a scoring function that ranks true or likely facts above invalid ones.
- Knowledge graph embedding methods encode entities and relations, define a triple-validity score, and optimize representations to increase the plausibility of known triples.
- Table 1 catalogs scoring functions across knowledge graph embedding methods and specifies notation for circular correlation, convolution, Hadamard products, and depthwise circular convolution.
- ConvE applies convolution to 2D reshaped subject and relation embeddings, then compares the resulting representation with the object embedding.
4 Notation and Definitions
The paper formalizes reshaping functions that arrange entity and relation embeddings into matrices, then defines interactions as co-occurrences within convolutional submatrices.
- A reshaping function φ transforms entity and relation embeddings into an m × n matrix with m × n = 2d.
- Reshaping functions: Stack reshaping places separately reshaped entity and relation embeddings in vertically stacked matrix blocks.
- Reshaping functions: Alternate reshaping interleaves τ rows from the entity and relation embeddings, with smaller τ producing more frequent alternation.
- Reshaping functions: Chequer reshaping arranges embeddings so adjacent cells never come from the same embedding.
- Interactions: An interaction is a triple consisting of two distinct embedding components and a k-submatrix containing both within the reshaped input.
- Interactions: Interactions are heterogeneous when components come from different embeddings and homogeneous when they come from the same embedding.
5 InteractE Overview
InteractE extends ConvE by targeting additional heterogeneous interactions between entity and relation features. It combines feature permutation, checkered reshaping, and circular convolution.
- InteractE uses multiple feature permutations to capture more possible interactions than a single fixed input order.
- Checkered reshaping replaces ConvE’s simple reshaping and is theoretically shown to be superior to other possibilities.
- Circular convolution captures more feature interactions than standard convolution and operates depth-wise across input permutations.
6 InteractE Details
InteractE embeds entities and relations, permutes them, reshapes each permutation, and applies depth-wise circular convolution. The resulting features are concatenated and projected into the embedding space for scoring.
- InteractE learns d-dimensional entity and relation embeddings, with d defined as d_wd_h.
- The model generates t random permutations of entity and relation embeddings, whose interaction sets are expected to be approximately disjoint.
- InteractE uses checkered reshaping because it captures the maximum heterogeneous interactions between entity and relation features.
- Circular convolution increases interactions relative to standard convolution by using modular indexing on a two-dimensional input.
- The model stacks reshaped permutations as channels, applies depth-wise circular convolution, concatenates outputs, and projects them into R^d.
- The score function uses a learnable weight matrix, ReLU and sigmoid activations, and binary cross-entropy with label smoothing during training.
7 Theoretical Analysis
The theoretical analysis studies how reshaping and padding choices affect feature interactions. It restricts the main analysis to square reshaped matrices while stating that the results extend to the general case.
- The analysis compares multiple 2D reshaping variants by the number of interactions they induce and examines circular padding against standard convolution.
- For simplicity, the analysis assumes square reshaped outputs with m = n, while stating that the results extend to the general case.
- The section presents propositions covering interaction behavior for kernel sizes, padding, reshaping functions, and related parameter settings.
- Table 2 reports link-prediction results for several models on FB15k-237, WN18RR, and YAGO3-10, including comparisons involving InteractE.
8 Experimental Setup
Experiments evaluate InteractE on three standard link-prediction datasets using filtered ranking metrics and comparisons with non-neural and neural baselines.
- 8.1 Datasets: The evaluation uses FB15k-237, WN18RR, and YAGO3-10, which differ in inverse-relation handling, source graph, entity selection, and relation content.
- 8.2 Evaluation Protocol: The filtered setting removes valid triples from corrupted candidate sets during test evaluation.
- 8.2 Evaluation Protocol: Performance is reported with MRR, MR, Hits@1, and Hits@10, averaged across five runs.
- 8.3 Baselines: Baselines include non-neural embedding methods such as DistMult, ComplEx, KBGAN, KBLRN, and RotatE.
- 8.3 Baselines: Neural baselines include R-GCN, ConvE, ConvTransE, and SACN.
9 Results
The experiments compare InteractE with existing methods and test how reshaping, convolution, and permutation choices affect link prediction. Results generally support the claim that richer heterogeneous feature interactions improve performance, with saturation beyond a permutation limit.
- Performance Comparison: InteractE outperforms ConvE on all metrics for FB15k-237 and WN18RR, and on three out of four metrics for YAGO3-10.
- Performance Comparison: 9%, 7.5%, and 23% are InteractE’s average MRR improvements over ConvE on FB15k-237, WN18RR, and YAGO3-10, respectively.
- Performance Comparison: InteractE outperforms other baselines across all metrics on FB15k-237 and on three of four metrics on YAGO3-10.
- Feature Reshaping and Convolution: Checkered reshaping performs best across most scenarios, while alternate reshaping improves over stacked reshaping and lower τ improves MRR.
- Feature Reshaping and Convolution: Circular convolution consistently outperforms standard convolution, supporting the benefit of increased feature interactions.
- Feature Permutations: Increasing feature permutations improves performance on WN18RR and YAGO3-10, leaves FB15k-237 MRR unchanged, and degrades beyond a limit.
- Relation Categories: InteractE is evaluated across one-to-one, one-to-many, many-to-one, and many-to-many relation categories on FB15k-237.
10 Conclusion
InteractE addresses ConvE’s limited feature interactions through feature permutation, checkered reshaping, and circular convolution. Experiments and theoretical analysis report consistent link-prediction improvements across multiple datasets and support the benefit of heterogeneous interactions.
- InteractE captures additional heterogeneous feature interactions to alleviate ConvE’s limitations.
- Its three central ideas are feature permutation, checkered feature reshaping, and circular convolution.
- Extensive experiments demonstrate consistent link-prediction improvement across multiple datasets.
- The paper theoretically analyzes InteractE’s components and empirically validates that increasing heterogeneous feature interaction benefits link prediction.
A Proof of Propositions
The appendix proves propositions about heterogeneous interactions under alternative reshaping, checkered reshaping, and padding schemes. These results characterize how reshaping parameters and circular padding affect interaction counts.
- A k × k feature matrix contains components from reshaped entity and relation embeddings, represented by Ta and Tb blocks of τk components.
- For alternate reshaping, the number of heterogeneous interactions decreases as τ increases and is maximal at τ = 1.
- The appendix also states assumptions such as α = n/(2τ) ∈ N and, when τ < k, k/τ ∈ N for parts of the alternate-reshaping proof.
- The alternate-reshaping proof analyzes separate cases for τ ≥ k − 1 and τ < k − 1.
- For any reshaping, heterogeneous interactions in a k × k matrix depend on the counts x and y of entity and relation components, with Nhet(Mk, k) = 2xy.
- Circular padding preserves additional nonzero interaction opportunities compared with zero padding by avoiding replacement of selected components with zeros.