Source-linked AI summary
ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs
Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, Feng Wu
TL;DR
Existing geometry-based query embeddings struggle with negation, limiting their coverage of first-order logical queries. ConE represents entities and queries as Cartesian products of two-dimensional cones and defines geometric operators for all FOL operations. Across benchmark datasets, it significantly outperforms previous state-of-the-art methods, including on queries with negation.
Problem
Existing geometry-based models have difficulty modeling negated queries because complements of points and boxes are not points or boxes.
Method
ConE represents entities and queries as Cartesian products of two-dimensional cones, using intersection, union, and closure-complement operators for FOL reasoning.
Results
ConE significantly outperforms previous state-of-the-art methods on benchmark datasets, with relative MRR improvements over BETAE on both non-negated and negated queries.
Takeaways & Limitations
ConE provides a geometric query embedding model that handles conjunction, disjunction, and negation within one framework.
Takeaways & Limitations
ConE models only entity sets corresponding to answers of real-world queries, excluding sets produced solely by theoretically possible nonsensical compositions.
Abstract
from arXiv · showhide
Query embedding (QE) -- which aims to embed entities and first-order logical (FOL) queries in low-dimensional spaces -- has shown great power in multi-hop reasoning over knowledge graphs. Recently, embedding entities and queries with geometric shapes becomes a promising direction, as geometric shapes can naturally represent answer sets of queries and logical relationships among them. However, existing geometry-based models have difficulty in modeling queries with negation, which significantly limits their applicability. To address this challenge, we propose a novel query embedding model, namely Cone Embeddings (ConE), which is the first geometry-based QE model that can handle all the FOL operations, including conjunction, disjunction, and negation. Specifically, ConE represents entities and queries as Cartesian products of two-dimensional cones, where the intersection and union of cones naturally model the conjunction and disjunction operations. By further noticing that the closure of complement of cones remains cones, we design geometric complement operators in the embedding space for the negation operations. Experiments demonstrate that ConE significantly outperforms existing state-of-the-art methods on benchmark datasets.
1 Introduction
Multi-hop reasoning over knowledge graphs uses FOL queries, but geometry-based query embeddings struggle with negation. ConE addresses this by representing entities and queries with cone products and supporting all FOL operations.
- Query embedding maps entities and FOL queries into low-dimensional spaces, following computation graphs and scoring answers by embedding similarity.
- Geometric models represent entity sets as interpretable regions, such as points and boxes, with membership indicating query answers.
- Existing point- and box-based geometric models cannot represent negation because their complements are not points or boxes.
- ConE represents entities and queries as Cartesian products of two-dimensional cones, using cone inclusion to identify answer entities.
- ConE models conjunction, disjunction, and negation through cone intersection, union, and geometric complement operators.
2 Related Work
Prior work embeds multi-hop logical queries using paths, geometric shapes, probability distributions, and complex objects. ConE follows the geometric-embedding line while targeting all FOL operations.
- Path-based methods traverse intermediate entities from anchor nodes, which leads to exponential computation cost.
- Embedding-based methods place FOL queries in low-dimensional spaces using geometric shapes, probability distributions, or complex objects.
- ConE differs from earlier geometric query embeddings by handling all FOL operations.
- Related geometric embedding research includes translation, rotation, complex operations, boxes, and convex cones for knowledge graphs and ontologies.
3 Preliminaries
The preliminaries define KG query answering, FOL query structure, computation graphs, and the cone geometry used by ConE. Logical operators correspond to set operations, while sector-cones provide the geometric representation.
- Knowledge Graphs: A knowledge graph consists of entities, relations, and factual subject–predicate–object triples.
- First-Order Logic: FOL query answering uses existential quantification, conjunction, disjunction, and negation; universal quantification is excluded.
- First-Order Logic: Queries are represented in disjunctive normal form as disjunctions of conjunctions over anchor, existentially quantified, and target variables.
- Computation Graphs: A computation graph represents entity sets at nodes and logical operations on entity sets at edges.
- Computation Graphs: Relation traversal maps to projection, conjunction to intersection, disjunction to union, and negation to complement.
- Two-dimensional cones: A sector-cone is a closed two-dimensional cone whose itself or closure-complement is convex; sector-cones remain cones under closure-complement, union, and intersection.
- Two-dimensional cones: A sector-cone is parameterized by an axis angle and aperture, with points lying within the corresponding angular interval.
- Two-dimensional cones: Cartesian products of sector-cones are represented as vectors in K^d, where K is the space of axis–aperture pairs.
4 Cone Embeddings
ConE embeds entities and query answer sets as Cartesian products of sector-cones, then composes projection, intersection, union, and complement operators. Its design uses semantic averaging, cardinality control, and closure-complement geometry.
- Embedding design: ConE builds embeddings for conjunctive queries and entities, then generates other query embeddings by applying logical operators.
- Embedding design: Entities are represented by cone products with zero apertures, while query regions use apertures to define their boundaries.
- Scope: The model need not represent entity sets arising only from theoretically possible but nonsensical query compositions.
- Logical operators: Projection maps an entity set to adjacent entities through a relation-dependent function implemented with relation translations and a neural network.
- Logical operators: Intersection represents conjunction using cone embeddings whose semantic centers are combined by semantic averaging and apertures by cardinality control.
- Logical operators: Semantic averaging maps axes to unit-circle points, computes an attention-weighted average, and maps the result back to angles.
- Logical operators: Union represents disjunction as a set of cone embeddings, with DNF restricting the union operation to the final computation-graph step.
- Logical operators: Complement represents negation through closure-complement, using complementary apertures and opposite semantic centers.
5 Experiments
Experiments evaluate ConE on benchmark knowledge graphs for query answering, generalization, answer-set cardinality, and approximation of logical set operations. ConE outperforms prior models, while its learned apertures track answer-set cardinality and its neural operators approximate projection and intersection.
- Experimental Settings: Experiments use FB15k, FB15k-237, and NELL995 with conjunctive, negated, and unseen query structures.Training and validation include 1p/2p/3p/2i/3i and 2in/3in/inp/pni/pin; generalization is tested on ip/pi/2u/up.
- Experimental Settings: The evaluation targets non-trivial answers requiring at least one unobserved edge in the answer path.Validation and test answers are computed as differences between answer sets under progressively expanded knowledge graphs.
- Main Results: 19.7%, 12.0%, and 10.6% relative MRR improvements over BETAE are achieved on the three datasets for queries without negation.ConE also gains up to 24.2% over Q2B and improves on query structures absent from training, including a 38.9% gain for 2u on FB15k over BETAE.
- Main Results: 25.4%, 9.3%, and 8.5% relative MRR improvements over BETAE are achieved on FB15k, FB237, and NELL for queries with negation.GQE and Q2B are excluded from these comparisons because they cannot model negation.
- Modeling the Cardinality of Answer Sets: ConE’s learned aperture embeddings correlate with answer-set cardinality and outperform BETAE across all tested query structures on FB15k.Cardinality is represented by the L1 norm of the aperture embedding and evaluated using Spearman’s rank correlation.
- The Designed Operators and the Real Set Operations: ConE uses exact non-parametric union and complement operators, while neural projection and intersection operators provide approximations for tractable training.Experiments assess projection inclusion, intersection overlap, and handling of empty intersections.
6 Conclusion
The conclusion presents ConE as a geometric query embedding model for multi-hop FOL queries over knowledge graphs. It reports that ConE models all FOL operations and significantly outperforms prior state-of-the-art models on benchmark datasets.
- ConE represents entity sets as Cartesian products of cones and designs corresponding logical operations for multi-hop FOL query answering.
- ConE is presented as the first geometric query embedding model able to model all FOL operations.
- Experiments show that ConE significantly outperforms previous state-of-the-art models on benchmark datasets.
- Adapting ConE to natural-language queries is identified as a future direction for improving its applicability.
A Proof for Proposition 1
The proof establishes that sector-cones are always axially symmetric by considering convex and non-convex cases. The supplied section also includes experimental and dataset materials unrelated to the proposition.
- Proof for proper cones: Proper cones in R2 are axially symmetric because their symmetry degree reaches the upper bound from Lemma 1.The argument sets n = 2 in Lemma 1, obtaining as(K) = 1.
- Convex case: Convex sector-cones are axially symmetric whether they have nonempty interior, contain a line, or have empty interior.These cases correspond respectively to proper cones, half spaces, and rays.
- Non-convex case: Non-convex sector-cones are axially symmetric because their closure-complements are closed convex cones with the same symmetry axis.The proof transfers the axis of symmetry from the closure-complement back to the original sector-cone.
- Conclusion: A sector-cone is therefore always axially symmetric, as stated in Proposition 2.The result follows by combining the convex and non-convex cases.
B.2 Training Protocal
The experiments use a single GPU and a grid search over optimization, embedding, sampling, and loss hyperparameters. MRR is the evaluation metric, with higher values indicating better performance.
- Implementation: All experiments run on a single Nvidia Geforce RTX 3090 GPU using PyTorch and the official BETAE implementation for fair comparison.The implementation uses a three-layer MLP with 1600 hidden neurons and ReLU activation where applicable.
- Hyperparameter search: The grid search varies learning rate, batch size, embedding size, negative sample size, and margin γ across specified candidate sets.The searched embedding sizes are 200, 400, and 800.
- Evaluation: Mean Reciprocal Rank (MRR) is used for evaluation, and higher MRR indicates better performance.MRR is defined as the average reciprocal rank across query results.
C.1 Results of BETAE with Embedding Dimension 800
The appendix compares BETAE at embedding dimensions 400 and 800 and explains why the main text reports the 400-dimensional results. The reported comparisons concern MRR results with and without negation.
- Dimension comparison: BETAE with embedding dimension 400 performs slightly better than BETAE with dimension 800.The appendix presents these comparisons in Tables 6 and 7.
- Reporting choice: The main text reports BETAE with embedding dimension 400 because its results are slightly better than those of the 800-dimensional version.The reported tables cover queries without negation and queries with negation across FB15k, FB237, and NELL.
C.2 Results on Disjunctive Queries
The appendix compares two implementations of disjunctive queries: DNF and De Morgan’s law. De Morgan’s-law results are competitive with DNF, but DNF performs better because sector-cones cannot represent all such union queries well.
- Disjunction implementations: ConE implements disjunctive queries using either DNF or De Morgan’s law.The two implementations are denoted 2u-N/up-N and 2u-M/up-M, respectively.
- Experimental results: Results for 2u-M/up-M are competitive with 2u-N/up-N, and all these results outperform BETAE.The comparison is reported for disjunctive queries on FB15k, FB237, and NELL.
- Representation limitation: ConE using De Morgan’s law performs worse than ConE using DNF.Using complements for unions always produces sector-cone representations, but not all such queries are well represented by sector-cones.
C.3 Correlation Results
ConE’s learned apertures correlate with answer-set variability, and its geometric inclusion criterion supports answer-entity identification. Additional experiments assess comparisons, stability, and the approximation error introduced by De Morgan’s law.
- Correlation Results: ConE’s learned embeddings effectively model answer-set cardinality across the evaluated datasets.Spearman and Pearson correlation tables evaluate the relationship between learned embeddings and the number of answers; the authors conclude that ConE models cardinality effectively.
- Comparison with EmQL: ConE significantly outperforms EmQL and other baselines on the FB15k generalization setting.The comparison uses the same FB15k dataset as EmQL.
- Stability: ConE’s performance is stable across five random seeds for both EPFO queries and queries with negation.The reported standard variances are small for both query categories.
- Union Approximation: The De Morgan approximation has an average overlap ratio of 0.4618 with the real union, indicating substantial discrepancy.The experiment compares ¬(¬A ∩¬B) with A ∪B over 8000 randomly generated sector-cone pairs.
- Answer-Set Variability: Large answer sets with small apertures can reflect low semantic variability or omitted answer entities, with the latter contributing to imperfect performance.The learned cone embedding may not include every answer entity, especially for validation and test queries.
- Answer-Set Variability: ConE’s apertures are evaluated against answer-set variety using SemanticAverage, maximum squared distance, and rank correlations.The experiment computes entity-set variation and correlates it with learned query apertures on FB15k.
- Answer-Entity Identification: Geometry-based inclusion determines answer entities, and ConE outperforms Query2Box on queries without negation.The evaluation reports precision and recall on validation and test queries; Query2Box is omitted for negated queries.
F Qualitative Analysis Between ConE and Query2Box
ConE differs from Query2Box in its geometric representation and operators, especially projection and complement. The comparison also reports similar computational complexity and training speed, while noting privacy disclosure as a potential societal impact of automatic reasoning.
- Embedding space: Cones can represent a finite universal entity set and its subsets through bounded apertures, whereas Query2Box boxes have unbounded offsets.Cones with aperture 2π represent the universal set, with smaller apertures representing subsets.
- Operators: ConE’s projection operator can produce larger or smaller apertures depending on the relation, unlike Query2Box’s always-expanded, translated boxes.The passage notes that some relation projections should not enlarge the represented entity set.
- Operators: ConE can model symmetric relations through axis rotations, while Query2Box’s translation-based projection cannot.For a symmetric relation, ConE can learn to rotate axes by π in the described one-dimensional example.
- Operators: Query2Box does not provide a clear box-based complement operation because complements of boxes are no longer boxes.This limits the direct use of boxes for modeling complement operations.
- Efficiency: ConE answers disjunctive-normal-form queries by answering each conjunctive query with constant-time cone operations, followed by fast search.The stated computational complexity is similar to Query2Box.
- Efficiency: ConE’s training speed is close to Query2Box and faster than BetaE, although GQE is the most time-efficient model.The comparison uses average time for 100 training steps with equal embedding parameters on one RTX 3090 GPU.
- Societal impact: Automatic reasoning with ConE may disclose private information when knowledge graphs are built from public data and used for multi-hop reasoning.The paper identifies privacy disclosure as a potential negative societal impact.