acceptodds
Under review as a conference paper at ICLR 2027

Certified Constructive Box Embeddings for DAG Taxonomies

Abstract

Embeddings of a taxonomy are usually trained. However, containment holds only up to a residual error, and the geometry reflects the frequencies in the training data. A geometry compiled from the order structure alone can guarantee two properties that no trained embedding offers: certified zero violations on a declared pair family, and retrieval rankings that no corpus frequency has shaped. We build on GRAIL, a classic reachability index that labels each node of a DAG with one interval per random linear extension, and we lift this labelling into the representation space. Instead of drawing extensions at random, we select each embedding dimension as a witness that separates specific pairs from a declared disjointness family. The resulting box embedding has certified zero containment and separation violations on that family, attested by a machine-checkable certificate that any third party can re-verify. Randomised GRAIL labels remain nonzero even at four times the dimension budget, and gradient-trained box baselines leave residual violations even when trained to fit the full graph. Because the geometry never sees a corpus, ranking by box volume never buries rare, specific concepts on GO, MeSH, or WordNet, while every similarity-based ranker prefers popular ones, at retrieval utility matching an oracle prefilter. Construction takes seconds, and full Gene Ontology under , with separation pairs, builds in s. The containment slack between two boxes also predicts held-out edges. Compared with fairly tuned baselines on three datasets, its AUC is higher on the densely multi-parent MeSH, on par on GO, and lower on the nearly tree-shaped WordNet. Symbolic graph features remain above every embedding method. With no task-specific training, the same slack tracks graded lexical entailment on HyperLex at .

Primary area:
learning on graphs and other geometries & topologies
Keywords:
directed acyclic graphs, constructive embeddings, GRAIL, box containment, box embeddings, taxonomy embedding, hierarchical representation, order embeddings, knowledge graphs, reachability labelling

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_gmqFOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper builds box embeddings for DAG taxonomies directly from the graph, without training. Each dimension comes from a topological order, and this alone guarantees that every descendant's box sits inside its ancestors' boxes. The orders are also chosen so that each pair in a user-declared family is disjoint in at least one dimension. Only pairs whose descendant sets don’t overlap can be declared. A greedy procedure packs many separation requirements into each dimension, and a separate checker verifies the final embedding. Experiments on GO, MeSH and WordNet look at construction speed and dimension count, constraint satisfaction, descendant retrieval, held-out edge prediction and graded lexical entailment.

The main contribution seems to be the combination of four things:

  • separation guarantees tied to a chosen policy,
  • orders picked on purpose to separate specific pairs,
  • a practical way to keep the number of dimensions low,
  • output that can be checked independently.
Critical strengths
  1. The paper separates two kinds of requirements. Containment must always hold, while separation is chosen by the user. This makes it clear what is exactly guaranteed, and it gives a useful trade-off between how many pairs are covered and how many dimensions are needed.

  2. The method does not rely on gradient-based training to satisfy the required constraints; they hold by construction. This could be valuable in applications where even a few structural violations are a problem.

Critical weaknesses
  1. The downstream benefit of deliberately choosing the orders is not fully isolated. Although random-order baselines are evaluated for structural violations and MAP, there are no matched comparisons for held-out edge prediction or graded entailment. Applying the same scorers and optional refinement to random or DFS-based labels with the same number of dimensions would help identify the benefits of the proposed selection procedure. The structural guarantees and certificate would remain useful even if downstream accuracy were similar.

  2. The evaluation does not establish whether this preference helps or hurts semantic ranking beyond recovering those relationships. Comparisons with simple depth- and descendant-count-based rankings would help clarify the effect.

Questions for authors

Please refer to the Weakness section.

Additional Questions:

  1. Does monotone in descendant count mean only along ancestor-descendant paths, or across all concepts? Can the authors please compare volume ranking with descendant-count ranking on identical candidate sets?
2 comments

Thank you for the precise questions. All three are answered with new experiments.

Matched comparison with random and DFS labels:

We ran exactly this control. GRAIL labels drawn by randomised DFS, with the dimension of each seed's construction, on the same training graph, scored by the same slack over the same ten seeds (Table 4, new rows). Applying the same refinement changes the control by at most 0.001. Held-out-edge AUC under random negatives:

GOMeSHWordNet
Constructive (submitted order)0.9110.8040.638
Constructive (depth-first order)0.7420.6720.900
GRAIL, same d0.9280.7270.896

On HyperLex the GRAIL labels reach rho 0.766, against 0.741 for the submitted construction and 0.763 for the depth-first one. As you anticipated, the downstream signal comes from the interval labelling, not from the selection. The selection changes the order of the extensions, and that order matters. Neither order is best on every dataset, and we report both without selecting on held-out edges. We rewrote Section 7 around this result.

What the selection does buy is the certificate. Randomised GRAIL labels still leave 288 violations of the declared family on GO at 768 dimensions (Table 2). The selection reaches zero at 191 dimensions, and at 66 with the depth-first order. On MeSH it also gives the strongest geometry, 0.077 AUC above the control.

Depth and descendant-count rankings:

On the same candidate set (Appendix G), descendant-count ranking gives a popularity correlation within 0.004 of volume ranking on every dataset, and depth ranking has the same sign. Volume ranking is therefore not better than these graph statistics. Its value is that the geometry provides the same specificity ranking from arrays alone, without access to the graph, inside the same batched operation as similarity scoring.

On whether the specificity preference helps or hurts semantic ranking, we scored HyperLex with specificity alone (Appendix J). The depth gap reaches rho 0.33, the descendant-count ratio 0.50 and the box-volume ratio 0.32 to 0.47, against 0.74 to 0.77 for the slack. So specificity is a weak semantic score, and it is not what the slack measures. The same table shows that a binary indicator of WordNet reachability reaches 0.760. On HyperLex the slack therefore mostly passes on what the hierarchy already says, and the paper now states this.

Is volume monotone in descendant count?

Only along ancestor chains, where containment forces it. Across arbitrary concepts it is not. In each dimension an interval is at least as long as the node's block, with equality only when the block is contiguous in that extension, so volume correlates with descendant count without being a function of it. We corrected the caption of Table 3 that suggested otherwise.

Thank you for the rebuttal. My concerns are sufficiently addressed and I updated my score.

Reviewer_MsFqOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

To address the limitations of existing gradient-based hierarchical Box Embedding methods—which struggle to strictly enforce hierarchical inclusion and concept separation constraints—this paper proposes a training-free, constructive Box Embedding approach. Based on GRAIL interval labeling, this method employs targeted linear extensions and a greedy strategy to compress representation dimensions, ensuring zero constraint violations for a predefined set of node pairs. Experiments conducted on datasets such as GO, MeSH, and WordNet demonstrate that this approach offers distinct advantages in terms of constraint satisfaction, construction efficiency, and hierarchical retrieval. Furthermore, it exhibits strong generalization capabilities in tasks involving the prediction of previously unseen edges and lexical entailment.

Critical strengths
  1. The method is supported by a solid theoretical foundation. By employing linear expansion and witness selection, the approach achieves hierarchical inclusion and the separation of specified node pairs. It provides formal correctness proofs and machine-verifiable certificates, ensuring that the model’s outputs are both reliable and verifiable.

  2. The experimental evaluation is comprehensive. The paper conducts constraint violation analysis, retrieval experiments, unseen edge prediction, and lexical entailment assessment across three real-world hierarchical graph datasets. Furthermore, it examines the relationship between various separation strategies and representation dimensions. The experimental results effectively demonstrate the method's validity and computational efficiency.

Critical weaknesses
  1. The scope of the "Certified Zero Violations" guarantee is limited. While the paper emphasizes this guarantee, it applies only to a pre-specified set of separation constraints rather than to all pairs of incomparable nodes. For pairs of nodes that share common descendants, the current construction cannot guarantee geometric separation. Furthermore, the P3 strategy has not been fully validated through experiments. Consequently, the paper should more clearly distinguish between guarantees for local constraints and the capacity to represent the entire global hierarchy, and it should analyze the potential implications of node pairs that remain uncovered.

  2. There are persistent shortcomings regarding representation dimensionality and scalability. Although the paper reports fast construction speeds, complex separation strategies require high-dimensional representations. For instance, the P2 strategy for the GO dataset necessitates 292 dimensions, while the P2 construction for WordNet could not be completed due to memory constraints. Moreover, the greedy strategy does not guarantee the attainment of the minimal representation dimensionality.

  3. The conclusions regarding frequency-neutral retrieval lack sufficient validation. The paper primarily assesses frequency-neutral retrieval by examining the Spearman correlation between retrieval rankings and concept popularity. However, the absence of a positive correlation does not equate to strict frequency neutrality; a strong negative correlation, for example, could imply a systematic bias toward low-frequency concepts. Additionally, the Mean Average Precision (MAP) metric used in this work largely reflects the structural coverage quality of the candidate set, which is insufficient to fully characterize the practical retrieval performance of different ranking strategies. It is recommended to incorporate metrics such as Recall@K and NDCG@K, segmented by concept frequency.

Questions for authors

Please see the weaknesses.

2 comments

Thank you for the detailed reading. We address the three weaknesses in turn.

Scope of the guarantee:

We agree that the paper should separate the local guarantee from the global picture more clearly, and the revision does. One point was understated in the submission. If two incomparable nodes share a descendant, the boxes of both must contain that descendant's box, so no box embedding with exact containment can make them disjoint, however it is built. The constructively separable pairs (P_3) are therefore the largest family that any containment-faithful box embedding can certify, not a limitation of our construction (Section 3, revised). For the pairs outside the declared family we added a sampled audit (Appendix H). Out of one million random pairs per dataset, the separable pairs outside P_1.5(r=2) overlap at most 3 times in 100,000 with the submitted order and at most once in 100,000 with the depth-first order.

Dimensionality:

The revision addresses this directly. The witness argument fixes only the order between the three priority classes, and a depth-first order inside the classes needs 2.3 to 3.8 times fewer dimensions for the same certificate in every cell (Table 1). GO under P_2 drops from 292 to 77 dimensions, with mean false positives per query falling from 0.011 to 0.005. WordNet under P_1.5(r=2) needs 25 dimensions instead of 73. The depth-first order does not bring P_2 within reach on WordNet. That build fails on the memory needed to store 3.4 billion declared pairs, not on the dimension. The largest WordNet policy we build is P_1.5(r=4) with 139 million pairs, at 32 dimensions. A certifier that streams the pairs instead of storing them is future work, and the limitations name it. We agree that the greedy packer gives no optimality guarantee. Computing the optimum is at least as hard as set cover, and the limitations say so. On random trees under P_1, where one dimension is optimal, the depth-first order needs two or three against 15 to 24 before.

Frequency neutrality and the metrics:

You are right on both counts. A strongly negative correlation means a preference for rare concepts, and on MeSH and WordNet volume ranking has exactly that, because it puts specific concepts first. We removed "frequency-neutral" from the paper and retitled Section 6. The supported claim is narrower. Volume ranking never favours popular concepts (rho <= 0 on every dataset), while every similarity ranker does. You are also right that MAP mostly reflects the candidate set. With binary relevance and a candidate set equal to the descendant set, every retrieved item is relevant, so MAP and NDCG over all descendants do not depend on the order, also at a cutoff. Per frequency bin they do. Following your suggestion we report Recall@10 and NDCG@10 per global frequency bin (Appendix G). On WordNet volume ranking retrieves 0.69 of a query's unattested descendants and 0.30 of its most frequent ones, against 0.67 and 0.57 for similarity. NDCG@10 is 0.92 and 0.16, against 0.86 and 0.35. On MeSH, Recall@10 is 0.87 and 0.70 for the least and most popular tercile, against 0.80 and 0.85, and NDCG@10 is 0.729 and 0.425, against 0.579 and 0.650. The gain sits at the unattested and least popular end. In the lowest attested tercile on GO and WordNet similarity retrieves slightly more (0.62 vs 0.60 and 0.58 vs 0.50), and the paper now says so.

Presentation:

The revision separates the certified family from the uncovered pairs in Section 3, states the full setup of the bias experiment in Section 6, rewrites Section 7 around the matched control, and corrects the captions of Tables 2 to 4. We are glad to clarify any passage that is still hard to follow.

Thank you for the author's reply, which has resolved most of my questions. Meanwhile, after reading other people's comments, I have decided to increase my score.

Reviewer_w9aEOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Rather than training box embeddings from a loss function, this paper compiles axis-aligned box embeddings from the constraints of a DAG taxonomy. It builds on GRAIL (2010), a compact reachability index for DAGs, taking its stacked-interval labelling and replacing its random draws with deliberately chosen linear extensions that separate a declared family of incomparable pairs, packing many such pairs into one extension greedily (set cover over the declared family). In contrast with box embeddings learned by gradient descent on a loss function, this method guarantees containment for every DAG ancestor relation and guarantees separation for every incomparable pair in a declared policy family. In addition it provides a checkable certification of this fidelity with respect to the policy. There are experimental results on build scaling, a violation audit of trained baselines, frequency-neutral retrieval by volume, and held-out edge prediction plus HyperLex via containment slack.

Critical strengths

A quickly-induced compact representation DAG containment representation that comes with guarantees is delightful. There are clear advantages over random GRAIL labeling for the paper's certified-geometric-representation setting. P1.5(r) is a nice idea. It addresses a key weakness of GRAIL in a practical way.

Critical weaknesses

While it is interesting to see the analysis of violations that come from the gradient descent learning, the Gumbel Box learning is a deliberately soft probabilistic model that you have (arguably unfairly) scored on hard disjointness. The Gumbel Box loss function has a meta-parameter for sharpness of the box edge which could be tuned toward more hardness, and it can be tuned during training (sort of like simulated annealing). I'd like to hear more about how you tuned this model, exploring sharpening schedules. It would also be nice to report results in a way that more fairly report its behavior near the decision boundaries. For example, how many of the Gumbel DAG violations were right at its soft edge, versus more substantively violated. On a related note, this method takes the DAG as given and faithfully matches all of it. I'd be interested in more discussion of generalization, or of discovering "errors" in the human-provided DAG, which arguably a gradient method might find better. For example, could you provide even a small qualitative result, like “the 50 highest-overlap-ratio pairs on WordNet, of which N look like curation errors to us”. To be clear, I'm not saying that gradient methods should always be the preferred choice, I'd just like to see more discussion of the tradeoffs.

Questions for authors

I understand the theoretical advantages of this methods, but can you say more about who the ideal "customer" is for this method? What is the motivating use case?

See "Weaknesses" above, which include some requests.

1 comment

Thank you for the positive assessment and the precise suggestions.

Gumbel box tuning and violations at the soft edge:

You are right that the comparison was not fair to the Gumbel model. The submitted row used the default constant temperature beta = 1, which at d = 191 fits the training edges only partly (mean P(parent | child) = 0.45). We trained it on full GO under eight schedules: constant beta in {1, 5, 20}, linear annealing from 1 to 5, 20 and 100, and two runs that add the declared P_1.5(r=2) pairs as extra negatives, so that the loss sees the family the validator checks (Appendix F). The best schedule, annealing to beta = 20 with the declared pairs, fits the edges (0.99) and lowers the violations from 305,675 to 37,889 on siblings and from 3.2 million to 259,033 on P_1.5(r=2). Containment violations rise from 1,940 to 10,826, a trade-off we see in every sharpening schedule. This row now replaces the old one in Table 2.

On how deep the violations are:

in the best schedule 78% of the disjointness violations overlap by more than three soft-edge widths 1/beta in every dimension, under 1% lie within a tenth of a width, and every containment violation exceeds three widths. So the residuals are not an artefact of the soft edge. We also report the model's own reading. Because box volume is a product over 191 dimensions, 56% of the hard violations have a model overlap probability below 0.01, and the model treats them as nearly disjoint. We state this in the paper. A consumer that needs a set-valued answer still has to choose a threshold, and no threshold comes with a guarantee. We also reran held-out edge prediction with this schedule over the same ten seeds. AUC under random negatives rises from 0.591 to 0.826 on GO and from 0.603 to 0.721 on MeSH, and falls from 0.771 to 0.714 on WordNet, so Table 4 now shows both settings. For comparison, our construction reaches 0.911 / 0.804 / 0.638 with the submitted order and 0.742 / 0.672 / 0.900 with the depth-first order. Neither order is best on every dataset, and we report both without selecting on held-out edges.

Generalisation and errors in the taxonomy:

We agree that this is the central trade-off and added it to the limitations. The construction reproduces the taxonomy as given, errors included. A trained model compresses, so its disagreements with the curators can point at errors. Following your suggestion, Appendix I lists the 50 WordNet non-edges that order embeddings trained on the full graph read most strongly as is-a. We chose order embeddings because they are the strongest learned baseline on WordNet. An LLM annotator proposed a label for each pair and one author reviewed them. Three of the 50 are omissions in WordNet: Cicero is not listed as a writer although Seneca and Pliny are, and two poisonous herbs are missing under vascular plant. Three more we leave open, because they hinge on sense distinctions that we cannot settle, for example whether Paris green counts as an organic compound. The other 44 are category errors of the model (sulfur dioxide as an organic compound). So most disagreements in this sample are errors of the model, and between three and six of 50 point at the taxonomy. We ran the same exercise on our geometry. In the depth-first build 372 non-edges lie strictly inside the box of the proposed parent, clustered under a few large boxes such as location. With at most two pairs per proposed parent, eight of them enter the list. Two are omissions (dark bread and graham bread under nutriment, a gap between WordNet's food branches) and one is open. One related result surprised us. With the depth-first order the compiled slack predicts held-out WordNet edges better than order embeddings (AUC 0.900 vs 0.843, p < 2e-7), so a compiled geometry can also rank candidate missing edges, while staying faithful to the edges it was given.

Who is the customer?

The motivating case is a hierarchy-aware prefilter inside a vector retrieval system: literature or records annotated with MeSH, ICD or GO terms, where a query for a concept must return every document under that concept and nothing from a declared disjoint branch. Such systems score text similarity and hierarchy in one batched operation over arrays, often cannot run a graph database next to the vector index, and in clinical or regulatory settings must show an auditor that the filter cannot drop a descendant. The construction ships the hierarchy as boxes in the same array format, plus a certificate that anyone can re-check. For plain reachability on a static graph a classical index such as GRAIL with post-filtering remains the right tool, as the introduction says.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the reviewers for careful and constructive reviews. The comments led to new experiments and to one improvement of the method. The main text of the revised PDF uses the additional page.

1. A depth-first order inside the construction (MsFq, gmqF):

The witness argument fixes only the order between the three priority classes of the Kahn sort. Inside a class the submitted construction takes nodes first-in first-out. Taking them depth-first instead, with randomised child order, keeps the certificate and needs 2.3 to 3.8 times fewer dimensions in every cell at the same structural MAP and an equal or lower mean false-positive count. Gene Ontology under P_2 drops from 292 to 77 dimensions (Table 1, new columns). We keep the submitted order as the default, because the two orders differ in held-out edge prediction (point 2).

2. A matched GRAIL control for the downstream results (gmqF):

We scored GRAIL labels of the same dimension, on the same training graph, with the same slack and refinement, over the same ten seeds. They reach held-out-edge AUC 0.928 / 0.727 / 0.896 (GO / MeSH / WordNet) and HyperLex rho 0.766. The downstream signal therefore comes from the interval labelling, not from certification. Certification can keep it: the submitted order leads the control by 0.077 AUC on MeSH, the depth-first order matches it on WordNet, where the training graph is a tree, and on GO the certified geometry trails by 0.017. Neither order is best on every dataset (the submitted order reaches 0.638 on WordNet, the depth-first order 0.742 and 0.672 on GO and MeSH). We report both and did not select an order on held-out edges. Section 7 is rewritten accordingly.

3. A fair Gumbel box baseline (w9aE):

The submitted Gumbel row used the model's default constant temperature, which fits the training edges only partly at d=191 (mean P(parent | child) = 0.45). We now report the best of eight temperature schedules. Its residual violations shrink but stay in the tens to hundreds of thousands, and they are not soft-edge effects (Appendix F). The edge-prediction table shows the model under both its default and the annealed schedule, since neither is better on every dataset.

4. Audits and corrections (MsFq, gmqF):

New appendices quantify separation outside the declared family, compare volume ranking with descendant-count and depth ranking on the same candidate set, and add Recall@10 and NDCG@10 per frequency bin. We retitled Section 6, which overstated "frequency neutrality", and the bias setup now states which box builds and which MeSH subsample were used.

All new results are reproducible from the anonymised repository with one driver script per experiment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.