CoChat
Sign Up
PreprintCited by 135Advanced Graph Neural NetworksTopic ModelingSemantic Web and Ontologies

Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

Open access
Ren, Hongyu, Hu, Weihua, Leskovec, Jure·2020·arXiv
DOI 10.48550/arxiv.2002.05969arXiv 2002.05969
Open this paper in CoChat — free accountOpen PDF

Abstract

Answering complex logical queries on large-scale incomplete knowledge graphs (KGs) is a fundamental yet challenging task. Recently, a promising approach to this problem has been to embed KG entities as well as the query into a vector space such that entities that answer the query are embedded close to the query. However, prior work models queries as single points in the vector space, which is problematic because a complex query represents a potentially large set of its answer entities, but it is unclear how such a set can be represented as a single point. Furthermore, prior work can only handle queries that use conjunctions ($\wedge$) and existential quantifiers ($\exists$). Handling queries with logical disjunctions ($\vee$) remains an open problem. Here we propose query2box, an embedding-based framework for reasoning over arbitrary queries with $\wedge$, $\vee$, and $\exists$ operators in massive and incomplete KGs. Our main insight is that queries can be embedded as boxes (i.e., hyper-rectangles), where a set of points inside the box corresponds to a set of answer entities of the query. We show that conjunctions can be naturally represented as intersections of boxes and also prove a negative result that handling disjunctions would require embedding with dimension proportional to the number of KG entities. However, we show that by transforming queries into a Disjunctive Normal Form, query2box is capable of handling arbitrary logical queries with $\wedge$, $\vee$, $\exists$ in a scalable manner. We demonstrate the effectiveness of query2box on three large KGs and show that query2box achieves up to 25% relative improvement over the state of the art.

AI snapshot

Written from the paper’s full text.

TL;DR

Query2Box embeds logical queries as boxes (axis-aligned hyper-rectangles) in vector space, so a query represents a set of answer entities rather than a single point. It handles conjunctive and disjunctive existential positive first-order (EPFO) queries by transforming them into disjunctive normal form and reports up to 25% relative improvement over the state of the art.

Key findings

  • Box embeddings naturally model sets: projection translates and expands a box, intersection produces a smaller box inside the inputs, and entity-to-box distance downweights points inside the box via a fixed scalar \(0<\alpha<1\).
  • The paper proves a negative result: handling disjunction with single-point or box embeddings requires embedding dimension/VC dimension proportional to the number of KG entities; on FB15k it finds \(M=13{,}365\) disjoint conjunctive queries while \(|V|=14{,}951\).
  • DNF rewriting makes EPFO queries tractable by answering \(N\) conjunctive queries and taking the minimum distance to any resulting box; this extends any conjunctive-query method to union.
  • On H@3, Q2B averages 0.484 on FB15k, 0.268 on FB15k-237, and 0.306 on NELL995, versus GQE at 0.386, 0.228, and 0.247; the paper reports 9.8% (25% relative), 3.8% (15% relative), and 5.9% (24% relative) higher H@3 than the best baselines, respectively.

Methods

  • Experiments use three KG benchmarks: FB15k, FB15k-237, and NELL995. Models are trained on the first 5 of 9 query structures and evaluated on all 9; evaluation focuses on answers requiring missing edges, i.e. \(J_qK_{\text{test}} \setminus J_qK_{\text{val}}\).
  • Entities are embedded as points and queries as boxes. Projection is \(p+r\) (sum centers and offsets); intersection uses attention over box centers plus a sigmoid-shrunk offset; union is handled by DNF transformation and aggregation via minimum box distance.
  • Training uses negative sampling loss with embedding dimension \(d=400\), margin \(\gamma=24\), \(\alpha=0.2\), Adam with learning rate 0.0001, 250 epochs, minibatch size 512 queries per query structure, and 1 positive plus 128 negative entities per query. Baselines are GQE and GQE-DOUBLE, with ablations Q2B-AVG, Q2B-DEEPSETS, Q2B-AVG-1P, and Q2B-SHAREDOFFSET.

Limitations

  • The paper states a negative result: exactly modeling arbitrary EPFO queries with low-dimensional embeddings is impossible; DNF rewriting may require \(N=\prod_{v\in V_{\text{union}}}|P_v|\) conjunctive queries, though it argues \(N\) may not be large and computations can be parallelized.
  • The paper focuses on EPFO queries whose computation graphs are DAGs, with union as an additional edge type; it does not claim to handle all first-order logic beyond this class.
  • Evident from the text: evaluation is restricted to answers that require missing edges (\(J_qK_{\text{test}} \setminus J_qK_{\text{val}}\)), not full answer sets; link prediction gains are minor, and the paper notes simple link prediction does not require modeling large answer sets.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

DataCite · 10.48550/arxiv.2002.05969

Cites

32 of 32 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

10 of 16 cited sources checked · 6 supported · 2 flagged · accuracy not yet measured

  • Premisecitation
    § ABSTRACT · p. 1

    Prior work models queries as single points in the vector space.

    “However, prior work models queries as single points in the vector space, which is problematic because a complex query represents a potentially large set of its answer entities, but it is unclear how such a set can be represented as a single point.”
    Quote in the paperSubstantial claim2 of 3 sources checked
    • cites Guu et al., 2015 source
    • cites Hamilton et al., 2018 source
    • cites Das et al., 2017

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Premisecitation
    § ABSTRACT · p. 1

    Prior work can only handle queries that use conjunctions and existential quantifiers.

    “Furthermore, prior work can only handle queries that use conjunctions ( ∧ ) and existential quantifiers ( ∃ ).”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites Hamilton et al., 2018 source
  • Findingown data
    § 4.1 KNOWLEDGE GRAPHS AND QUERY GENERATION · p. 8

    Complex logical queries (especially 2p, 3p, ip, pi, up) require modeling a much larger number of answer entities (often more than 10 times) than simple 1p queries.

    “We observe that complex logical queries (especially 2p, 3p, ip, pi, up) indeed require modeling a much larger number of answer entities (often more than 10 times) than the simple 1p queries do.”
    Quote in the paperSubstantial claim
  • Findingown data
    § 4.2 EVALUATION PROTOCOL · p. 8

    On simple link prediction (1p query) task, box embeddings provide minor empirical performance improvement over TransE.

    “On the simple link prediction (1p query) task, box embeddings provide minor empirical performance improvement over TransE, possibly because simple link prediction does not require modeling large sets of entities, as shown in Table 1.”
    Quote in the paperNot a substantial claim
  • Findingnone given
    § 1 INTRODUCTION · p. 2

    Query2box can generalize to new logical query structures that it has never seen during training.

    “(2) QUERY2BOX can generalize to new logical query structures that it has never seen during training;”
    Quote in the paperSubstantial claim
  • Classified as probably not a substantial claim. 17
  • May combine two claims. 23

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning
    § 3.2 REASONING OVER SETS OF ENTITIES USING BOX EMBEDDINGS · p. 5

    When α=1, dist_box reduces to the ordinary L1 distance.

    “When α = 1 , dist box reduces to the ordinary L 1 distance, i.e. , ‖ Cen ( q ) -v ‖ 1 , which is used by the conventional TransE (Bordes et al., 2013) as well as prior query embedding methods (Guu et al., 2015; Hamilton et al., 2018).”
    Quote in the paperNot a substantial claim2 of 3 sources checked
    • cites Bordes et al., 2013

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites Guu et al., 2015 source

      Section 3.4 (p. 3) describes a compositional TransE query model with the traversal operator Tᵣ(xₛ) = xₛ + wᵣ, supporting the citation as an example of a prior query-embedding method. In our copy, the scoring and membership formulas are not decoded, and no readable passage specifies an L1 distance. The paper therefore does not verify the L1-specific part of the citing sentence or its claim about dist_box at α = 1. (LLM, conf=0.78)

      Experimental — accuracy not yet measured
    • cites Hamilton et al., 2018 source

      The citation to Hamilton et al. is attached to the assertion that prior query-embedding methods used ordinary L1 distance, not to the citing paper’s α=1 calculation. In §4, p. 5, Hamilton et al. explicitly state that their method uses cosine distance instead. Their paper does not define dist_box or α. (LLM, conf=0.88)

      Checked by a reasoning model — may be wrong.

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 4.3 BASELINE AND MODEL VARIANTS · p. 9

    The L1 distance is used as the distance between query and entity vectors in GQE.

    “The L 1 distance is used as the distance between query and entity vectors.”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites Hamilton et al., 2018 source

      Section 4 (p. 4) says GQE scores a query–node pair using the distance between their embeddings. Its footnote in Section 4 (p. 5) specifies cosine distance, not L1 distance. (LLM, conf=0.90)

      Checked by a reasoning model — may be wrong.

      Experimental — accuracy not yet measured

  • May combine two claims.

    Interpretationreasoning
    § 3.2 REASONING OVER SETS OF ENTITIES USING BOX EMBEDDINGS · p. 5

    Our geometric intersection operator effectively constrains the center position and models the shrinking set size.

    “Different from the generic deep sets to model the intersection (Hamilton et al., 2018), our geometric intersection operator effectively constrains the center position and models the shrinking set size.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites Hamilton et al., 2018 source

  • May combine two claims.

    Interpretationnone given
    § 3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM · p. 7

    Our DNF-query rewriting scheme is general and is able to extend any method that works for conjunctive queries to handle more general class of EPFO queries.

    “Note that our DNF-query rewriting scheme is general and is able to extend any method that works for conjunctive queries ( e.g. , (Hamilton et al., 2018)) to handle more general class of EPFO queries.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites Hamilton et al., 2018 source

  • May combine two claims.

    Premisecitation
    § 1 INTRODUCTION · p. 1

    Embedding-based query answering robustly handles missing relations and is orders of magnitude faster than subgraph matching.

    “Such approach robustly handles missing relations (Hamilton et al., 2018) and is also orders of magnitude faster, as answering an arbitrary logical query is reduced to simply identifying entities nearest to the embedding of the query in the vector space.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites Hamilton et al., 2018 source

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation
    § 4.3 BASELINE AND MODEL VARIANTS · p. 9

    GQE embeds a query to a single vector and models projection and intersection operators as translation and deep sets, respectively.

    “GQE embeds a query to a single vector, and models projection and intersection operators as translation and deep sets (Zaheer et al., 2017), respectively.”
    Quote in the paperNot a substantial claim1 of 2 sources checked
    • cites Hamilton et al., 2018 source

      Section 4 (pp. 5–6) says GQE generates a single query embedding and implements intersection with a permutation-invariant neural network operating on sets. But its base projection operator uses a trainable matrix (p. 5); translation is a TransE variant described in Section 4.3 (p. 7), not the general GQE projection operator. (LLM, conf=0.90)

      Experimental — accuracy not yet measured
    • cites Zaheer et al., 2017

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Findingown data
    § 3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM · p. 6

    For real-world KGs, there are M ≈ |V| conjunctive queries with non-overlapping answers; in FB15k, M=13,365 and |V|=14,951.

    “For a real-world KG, there are M ≈ |V| conjunctive queries with non-overlapping answers.”
    • Also stated in: § 3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM · p. 6 · plain
      “For example, in the commonly-used FB15k dataset (Bordes et al., 2013), derived from the Freebase (Bollacker et al., 2008), we find M = 13,365, while |V| is 14,951 (see Appendix B for the details).”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites Bordes et al., 2013

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites Bollacker et al., 2008 source

  • May combine two claims.

    Findingnone given
    § 1 INTRODUCTION · p. 2

    Query2box provides strong generalization as it can answer complex queries.

    “(1) QUERY2BOX provides strong generalization as it can answer complex queries;”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.4 MAIN RESULTS · p. 9

    QUERY2BOX significantly and consistently outperforms the state-of-the-art baseline GQE across all query structures, including those not seen during training and those with union operations.

    “As listed in Tables 2, our method significantly and consistently outperforms the state-of-the-art baseline across all the query structures, including those not seen during training as well as those with union operations.”
    • Also stated in: § 5 CONCLUSION · p. 10 · boosted
      “Experimental results on standard KGs demonstrate that QUERY2BOX significantly outperforms the existing work in answering diverse logical queries.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingnone given
    § 1 INTRODUCTION · p. 2

    Query2box is able to implicitly impute missing relations as it can answer any EPFO query with high accuracy even when relations involving answering the query are missing in the KG.

    “(3) QUERY2BOX is able to implicitly impute missing relations as it can answer any EPFO query with high accuracy even when relations involving answering the query are missing in the KG;”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data
    § B DETAILS ABOUT COMPUTING M IN THEOREM 1 · p. 14

    Out of all queries in S1p, 129,717 queries have more than one answer entity.

    “Out of all the queries in S 1p , 129,717 queries have more than one answer entities”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 4.4 MAIN RESULTS · p. 9

    On average, Q2B obtains 9.8% (25% relative), 3.8% (15% relative), and 5.9% (24% relative) higher H@3 than the best baselines on FB15k, FB15k-237, and NELL995, respectively.

    “On average, we obtain 9.8% (25% relative), 3.8% (15% relative), and 5.9% (24% relative) higher H@3 than the best baselines on FB15k, FB15k-237, and NELL995, respectively.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.4 MAIN RESULTS · p. 10

    On FB15k-237, Q2B obtains more than 4% and 2% absolute gain in H@3 compared to Q2B-AVG and Q2B-DEEPSETS, respectively.

    “Specifically, on FB15k-237, Q2B obtains more than 4% and 2% absolute gain in H@3 compared to Q2B-AVG and Q2B-DEEPSETS, respectively.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.4 MAIN RESULTS · p. 9

    Q2B performs well on new queries with the same structure as the training queries and on new query structures never seen during training.

    “Also notice that Q2B performs well on new queries with the same structure as the training queries as well as on new query structures never seen during training”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data
    § B DETAILS ABOUT COMPUTING M IN THEOREM 1 · p. 14

    On FB15k, 308,006 queries of type '1p' are instantiated.

    “On the FB15k, we instantiate 308,006 queries of type '1p', which we denote by S 1p .”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § 3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM · p. 7

    All union operators are removed from Gq(1),...,Gq(N), so all these computation graphs represent conjunctive queries.

    “Furthermore, as all the union operators are removed from G q (1) , . . . , G q ( N ) , all of these computation graphs represent conjunctive queries, which we denote as q (1) , . . . , q ( N ) .”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 1 INTRODUCTION · p. 2

    To answer any EPFO query, Query2box first answers individual conjunctive queries and then takes the union of the answer entities.

    “This means that to answer any EPFO query we first answer individual conjunctive queries and then take the union of the answer entities.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 1 INTRODUCTION · p. 2

    Executing logical operators over boxes results in new boxes, so the operations are closed.

    “(3) Executing logical operators over boxes results in new boxes, which means that the operations are closed;”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S2 (checkable), S4 (based).

    Interpretationnone given
    § 1 INTRODUCTION · p. 2

    Boxes naturally model sets of entities they enclose.

    “(1) Boxes naturally model sets of entities they enclose;”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning
    § 3.2 REASONING OVER SETS OF ENTITIES USING BOX EMBEDDINGS · p. 4

    The benefit of boxes is that unlike a single point, the box has the interior; thus, if an entity is in a set, it is natural to model the entity embedding to be a point inside the box.

    “The benefit is that unlike a single point, the box has the interior ; thus, if an entity is in a set, it is natural to model the entity embedding to be a point inside the box.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM · p. 7

    This modeling aligns well with the union operation; an entity is inside the union of sets as long as the entity is in one of the sets.

    “This modeling aligns well with the union operation; an entity is inside the union of sets as long as the entity is in one of the sets.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM · p. 6

    The dimensionality of logical query embeddings needs to be Θ(|V|), which is not low-dimensional; thus not scalable to large KGs and not generalizable in the presence of unobserved KG edges.

    “In other words, the dimensionality of the logical query embeddings needs to be Θ( |V| ) , which is not low-dimensional; thus not scalable to large KGs and not generalizable in the presence of unobserved KG edges.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given
    § 4.1 KNOWLEDGE GRAPHS AND QUERY GENERATION · p. 8

    For these queries, traditional graph traversal techniques would not be able to find the answers (due to missing relations).

    “Furthermore, for these queries, traditional graph traversal techniques would not be able to find the answers (due to missing relations).”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § ABSTRACT · p. 1

    A complex query represents a potentially large set of answer entities, and it is unclear how such a set can be represented as a single point.

    “However, prior work models queries as single points in the vector space, which is problematic because a complex query represents a potentially large set of its answer entities, but it is unclear how such a set can be represented as a single point.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning
    § 3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM · p. 7

    Since q is logically equivalent to q(1)∨...∨q(N), the aggregated distance function can be defined using box distance.

    “Since q is logically equivalent to q (1) ∨ · · · ∨ q ( N ) , we can naturally define the aggregated distance function using the box distance dist box :”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Study design and conductreasoning
    § 4.1 KNOWLEDGE GRAPHS AND QUERY GENERATION · p. 8

    We always evaluate on queries/entities that were not part of the training set and the method has not seen them before.

    “This means we always evaluate on queries/entities that were not part of the training set and the method has not seen them before.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given
    § 3.2 REASONING OVER SETS OF ENTITIES USING BOX EMBEDDINGS · p. 4

    The adaptive box size effectively models a different number of entities/vectors in the set.

    “The adaptive box size effectively models a different number of entities/vectors in the set.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Interpretationnone given
    § 3.2 REASONING OVER SETS OF ENTITIES USING BOX EMBEDDINGS · p. 5

    The geometric intersection operator generates a smaller box that lies inside a set of boxes.

    “The intuition behind our geometric intersection is to generate a smaller box that lies inside a set of boxes, as illustrated in Fig. 2(B).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationown data
    § 5 CONCLUSION · p. 10

    QUERY2BOX can effectively model and reason over sets of entities as well as handle EPFO queries in a vector space.

    “In this paper we proposed a reasoning framework called QUERY2BOX that can effectively model and reason over sets of entities as well as handle EPFO queries in a vector space.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given
    § D DETAILS ON QUERY GENERATION · p. 15

    During entity and relation assignment, all degenerated queries are specifically filtered out.

    “Note that during the entity and relation assignment, we specifically filter out all the degenerated queries, as shown in Fig. D.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given
    § E DETAILS OF NELL995 DATASET · p. 15

    Entities that only appear in the validation and test sets but not in the training set are filtered out.

    “Note that we filter out all the entities that only appear in the validation and test sets but not in the training set.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Study design and conductreasoning
    § 4.3 BASELINE AND MODEL VARIANTS · p. 9

    For a fair comparison, GQE-DOUBLE is compared so that QUERY2BOX and GQE-DOUBLE have the same number of parameters.

    “For a fair comparison, we also compare with GQE-DOUBLE (GQE with doubled embedding dimensionality) so that QUERY2BOX and GQE-DOUBLE have the same amount of parameters.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Study design and conductreasoning
    § 4.4 MAIN RESULTS · p. 9

    To treat queries equally regardless of the number of answers they have, the evaluation takes the average over queries.

    “Here, to treat queries equally regardless of the number of answers they have, we take average over queries .”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Study design and conductnone given
    § D DETAILS ON QUERY GENERATION · p. 15

    When generating validation/test queries, trivial queries that can be fully answered by subgraph matching on G train / G valid are explicitly filtered out.

    “When generating validation/test queries, we explicitly filter out trivial queries that can be fully answered by subgraph matching on G train / G valid .”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Study design and conductnone given
    § 4.3 BASELINE AND MODEL VARIANTS · p. 9

    Although the original GQE cannot handle EPFO queries, the DNF-query rewriting strategy is applied to extend GQE to handle general EPFO queries in the evaluation.

    “Although the original GQE cannot handle EPFO queries, we apply our DNF-query rewriting strategy and in our evaluation extend GQE to handle general EPFO queries as well.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 4.4 MAIN RESULTS · p. 10

    Different queries have different numbers of answer entities, and the adaptive box size enables better modeling of this.

    “This is most likely because different queries have different numbers of answer entities, and the adaptive box size enables us to better model it.”
    Quote in the paperSubstantial claim
36 of 36

  • The paper relies on this without support.

    Handling queries with logical disjunctions remains an open problem.

    “Handling queries with logical disjunctions ( ∨ ) remains an open problem.”

  • The paper relies on this without support.

    Computational complexity of subgraph matching is exponential in query size, and thus cannot scale to modern KGs.

    “(1) Computational complexity of subgraph matching is exponential in the query size, and thus cannot scale to modern KGs;”

  • The paper relies on this without support.

    Subgraph matching is very sensitive as it cannot correctly answer queries with missing relations.

    “(2) Subgraph matching is very sensitive as it cannot correctly answer queries with missing relations.”

  • The authors state this as an assumption.

    For the proof, assigning a single entity embedding to all entities in a query's denotation set is without loss of generality.

    “For the sake of modeling Q , without loss of generality, we consider assigning a single entity embedding v q i to all v ∈ J q i K , so there are M kinds of entity vectors, v q 1 , . . . , v q M .”

  • The paper relies on this without support.

    Simple link prediction does not involve logical reasoning nor handling a large set of answer entities.

    “Note that in the case of simple link prediction, we do not expect a huge performance gain by using box embeddings as link prediction does not involve logical reasoning nor handling a large set of answer entities.”
5 of 5

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Query2Box and BoxE make use of boxes in the loss function of their models, but entities themselves are represented as vectors.

    “Query2Box (Ren et al., 2020) and BoxE (Abboud et al., 2020) make use of boxes in the loss function of their models, however entities themselves are represented as vectors, and thus these models do not benefit from the probabilistic semantics of box embeddings, which we rely on heavily for modeling UKGs.”

    From Probabilistic Box Embeddings for Uncertain Knowledge Graph Reasoning (2021) · cites this paper as Ren et al., 2020

  • BEUrRE makes use of a learned transform for each relation, differs from Ren et al. in that entities themselves are boxes, and differs from both Ren et al. and Dasgupta et al. in the structure of the learned transform.

    “Similarly to Ren et al. (2020) and Dasgupta et al. (2021), we also make use of a learned transform for each relation, however we differ from Ren et al. (2020) in that entities themselves are boxes, and differ from both in the structure of the learned transform.”

    From Probabilistic Box Embeddings for Uncertain Knowledge Graph Reasoning (2021) · cites this paper as Ren et al., 2020

Cites

Flagged first, then by citations

Research works printed but not linked: 2

  1. John Venn. I. on the diagrammatic and mechanical representation of propositions and reasonings. The London, Edinburgh, and Dublin philosophical magazine and journal of science , 10(59):1-18, 1880.
  2. Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS) , pp. 3391-3401, 2017.

Cited by

Sorted by citations

Related

Authors
Ren, H., Hu, W., & Leskovec, J.
Affiliations
Stanford University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2002.05969
arXiv
2002.05969
OpenAlex
W2994695355
Cited by
135
References
31
Citations by year
2025: 9 · 2024: 11 · 2023: 35 · 2022: 20 · 2021: 44 · 2020: 16
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • TIB Data Manager
  • International Conference on Learning Representations
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Semantic Web and Ontologies
Keywords
knowledge graph reasoning, box embeddings, vector space representation, disjunctive normal form, incomplete knowledge graphs, existential quantifier

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-23.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-23.

Cited sources are checked by gpt-6-sol.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review