Learning Representations for Hierarchies with Minimal Support

Authors: benjamin  rozonoyer
michael  boratko
dhruvesh  patel
wenlong  zhao
shib  dasgupta
hung  le
andrew  mccallum
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:02:34

Abstract: When training node embedding models to represent large directed graphs (digraphs), it is impossible to observe all entries of the adjacency matrix during training. As a consequence most methods employ sampling. For very large digraphs, however, this means many (most) entries may be unobserved during training. In general, observing every entry would be necessary to uniquely identify a graph, however if we know the graph has a certain property some entries can be omitted - for example, only half the entries would be required for a symmetric graph. 
In this work, we develop a novel framework to identify a subset of entries required to uniquely distinguish a graph among all transitively-closed DAGs. We give an explicit algorithm to compute the provably minimal set of entries, and demonstrate empirically that one can train node embedding models with greater efficiency and performance, provided the energy function has an appropriate inductive bias. We achieve robust performance on synthetic hierarchies and a larger real-world taxonomy, observing improved convergence rates in a resource-constrained setting while reducing the set of training examples by as much as 99%.

Main paper: 
 introduction: 
 Consider the directed graph and its associated adjacency matrix in Figure 1 . In situations where this adjacency matrix is sparse, we can store it more efficiently by keeping a list of only the positive entries, effectively assuming any pairs not in our list are zero. But what about situations where we cannot assume that we have observed the full graph? For example, when obtaining annotations for edges of an unknown graph, the full adjacency matrix is unknown to us and we obtain the value of any particular entry by requesting an annotation. A less obvious scenario is training a model to represent a given graph. From the model's perspective, every entry of this adjacency matrix is unknown, and it is only observed as a consequence of training. Therefore, it is of interest to determine: what is the smallest set of entries necessary to uniquely determine the graph? In general, the answer is "all of them", but if we assume some structural prior on the graph itself, it may be possible to reduce the number of edges necessary for consideration. For example, if we knew it was a simple graph (no self-loops) we could omit the diagonal. Similarly, for a symmetric graph, we could omit half the entries. For the class of acyclic graphs, we can omit certain entries which, were they to be 1, would form a cycle, and therefore must be 0; however, the explicit characterization of these entries is not as straightforward as the preceding cases. Focusing on the case when the graph is a transitively-closed directed acyclic graph (DAG), as in Figure 1 , it is easy to see that of those entries which are 1, we can omit all but the transitive reduction, i.e. the bold edges, which corresponds to omitting the non-bold "1"s in the adjacency matrix. But what about pruning the zeros? For the graph in Figure 1 , we can prove only 14 of the 49 entries in the adjacency matrix are needed to uniquely distinguish this graph among all transitively-closed DAGs. (See Figure 2 .)EQUATIONIn this work, we first develop a general-purpose framework to identify a subset of entries required to uniquely distinguish a graph among others with some arbitrary graph property (Section 3.1). We then use this framework to construct a set of entries in the adjacency matrix sufficient to uniquely distinguish transitively-closed digraphs (Section 3.2), and prove that this reduced set is also minimal for transitively-closed DAGs (Section 3.3). We show how this can be leveraged to more efficiently train node embedding models for graph representation by defining the notion of "transitivity bias" (Section 4.1), and proving that box embeddings, a common graph representation model, have a transitivity bias (Section 4.3). We then combine these facts into a formal negative sampling procedure (Section 5) and demonstrate that box embeddings do benefit from training on this reduced set of entries (Section 6). 1 For related work in graph theory and representation learning, we refer the reader to Appendix A. 
background: 
 We use the shorthand n := {1, . . . , n}. A semicolon separates the main arguments of a function from parameters which are typically held constant (e.g., f (x; µ, σ)= 1 σ √ 2π e -1 2 ( x-µ σ ) 2). We may omit these secondary parameters when their values are clear from context. We represent a graph G = (V, E) by its adjacency matrix A G ∈ {0, 1} N ×N , where (A G ) u,v = 1 if and only if (u→v) ∈ E. When it is clear from context, we omit the subscript and simply write A. We use arrows to represent edges: black (a→b) denotes a positive edge in E, and red (a→b) a negative edge in the edge complement E (see below).All graphs G = (V, E) in this work will be finite simple2 directed graphs (digraphs), where the edges are a subset of the complement of the diagonal, i.e. with diag(V ) := {(v→v) | v ∈ V }, we have E ⊆ V 2 \ diag(V ) =: offdiag(V ). Given a simple digraph G = (V, E), the complement of G is G = (V, E) where E := offdiag(V ) \ E. The transitive closure of G is G tc = (V, E tc ) where (u, v) ∈ E tc if and only if there exists a directed path from u to v in G. A transitive reduction of a digraph G is a digraph G ′ on V with the fewest number of edges such that (G ′ ) tc = G tc . Note that a transitive reduction need not be a subgraph of G, and in general is not unique. If G is acyclic, however, there is a unique transitive reduction, and it is also a subgraph of G [Aho et al., 1972] . In this case we denote the transitive reduction G tr = (V, E tr ).Given the task of modeling entities V that have a known graph-theoretic structure G = (V, E), a common approach is to learn a node embedding θ : V → Z which maps a node v → θ(v) in embedding space Z. The graph structure is extracted from these geometric representations via an energy function E : V × V → R ≥0 which factors through θ, i.e. there exists a dissimilarity function h : Z × Z → R ≥0 such that E θ (u, v) := E(u, v; θ) = h(θ(u), θ(v)). For example, for undirected graphs it is common to use Z = R D and E θ (u, v) = ∥θ(u) -θ(v)∥. This energy is interpreted as the unnormalized negative log-probability of edge existence. We seek to minimize the energy for positive edges (u→v) by learning representations for which there exists some (global) threshold T such that A uv = 1 if and only if E θ (u, v) ≤ T .One reason to embed nodes is to learn representations end-to-end in conjunction with other objectives via gradient descent. In such a setting, a typical loss function for the graph structure takes the formL full (θ; G) := (u→v)∈E ℓ + (E θ (u, v)) + (u→v)∈E ℓ -(E θ (u, v))where ℓ + and ℓ -are referred to as the positive and negative loss functions, respectively, and the pairs in E and E are referred to as positive and negative edges accordingly.The loss function L full has |V |(|V | -1) terms, and thus is often too computationally demanding to use for training. For digraphs which are sparse, a common workaround is to define a noise probability density function (pdf) p n and design a loss function L noise which replaces the sum over negative edges with an expectation with respect to p n . In practice, Monte Carlo sampling is used to calculate a loss L sampled which approximates L noise .Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Section 7 discusses the limitations of our work. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
distinguishing digraphs via sidigraphs: 
 We aim to define a new loss function with only a subset of the terms in L full (which currently include all entries of the adjacency matrix A G ), while having the same minimizer. Thus, we first attempt to determine the minimal number of entries in A G which would uniquely distinguish G among all those with a given property. To this end, we turn to the notion of a signed digraph (a.k.a. "sidigraph"), a digraph where edges have labels + or -, as a formalism for making explicit the disjoint set of "positive" and "negative" edges required to uniquely determine G. Edges not present in this sidigraph will be the entries we can omit from our adjacency matrix, given those edges which are present and some structural prior. This framework will allow us to identify the minimal set of entries in the adjacency matrix necessary to uniquely distinguish a digraph among all those with a given property. We apply this framework to transitively-closed digraphs, in which case we prove that certain edges can be pruned. We then prove that, in the case of transitively-closed DAGs, this yields the minimal set of entries. We furthermore provide a concrete algorithm to construct this set of entries from a given adjacency matrix.While the depiction of the partial adjacency matrix in Figure 2 is clear, in order to formalize this we need a notion of a graph which has three possible values, e.g. 1, 0, and "missing". This is captured formally by the notion of a (simple) signed digraph, or sidigraph for short, which is a triple (V, E + , E -) where V is the vertex set, and E + , E -are disjoint subsets of offdiag(V ), referred to as the positive and negative edges, respectively.Definition 1. Given a digraph G = (V, E) we define the equivalent sidigraph G ± := (V, E, E).This equivalence defines a bijection between digraphs and sidigraphs with |V |(|V | -1) edges. See Figure 3 for a depiction of an equivalent sidigraph of the digraph in Figure 1 .Let H and G be two sidigraphs with the same vertex set V . We say thatH is a sub-sidigraph of G, denoted by H ⊆ G, if E + H ⊆ E + G and E - H ⊆ E - G .Given some digraph G, identifying a subset of entries in A G is equivalent to specifying a sub-sidigraph of G ± . For this reason, we introduce the following terminology.Definition 2. We say that a sidigraph H is a potential distinguisher of a digraph G if H ⊆ G ± .Given a sidigraph H, we define the set of digraphs that could potentially be distinguished by H to be GH := {G | H ⊆ G ± }.That is, G H contains every digraph G such that H is a potential distinguisher. Another way to interpret G H is that the edge set of every graph G ∈ G H contains all positive edges and no negative edges of H. More formally: Definition 3. Given some property, we let P be a set of all digraphs (on a given set of nodes) with this property. We say the sidigraph H distinguishes a particular digraph G among all those with the given property if G H ∩ P = {G}.G H = {G | V G = V H , E + H ⊆ E G , E - H ∩ E G = ∅}. Root A B A1 A2 B1 B2 Root 0 1 1 1 1 1 1 A 0 0 0 1 1 0 0 B 0 0 0 0 0 1 1 A1 0 0 0 0 0 0 0 A2 0 0 0 0 0 0 0 B1 0 0 0 0 0 0 0 B2 0 0 0 0 0 0 0 (a) Adjacency matrix for G Root A B A1 A2 B1 B2 Root + + + + + + A - -+ + -- B - - --+ + A1 - -- --- A2 - --- -- B1 - ---- - B2 - ----- (b) Equivalent sidigraph G ± Root A B A1 A2 B1 B2 Root + + A + + -- B --+ + A1 - A2 - B1 - B2 - (c) Minimal sidigraph H *In this work, we focus on the case where P contains all transitively-closed digraphs, and we let G = (V, E) ∈ P be some fixed transitively-closed digraph.We first focus on reducing the positive edges of G ± . An explicit representation of G may well have Ω(|V | 2 ) edges; however any transitive reduction G ′ = (V, E ′ ) often has substantially fewer edges.3 Furthermore, by definition, G is the only transitively-closed digraph which contains the edges E ′ . As a consequence, if we let H = (V, E ′ , E) we have G H ∩ P = {G}, which proves the following result.Proposition 1. Let G = (V, E) be a transitively-closed digraph, andG ′ = (V, E ′ ) a transitive reduction. Then H = (V, E ′ , E) distinguishes G among transitively-closed digraphs.The edge complement E might also have Ω(|V | 2 ) edges, which we would like to reduce while maintaining distinguishability. To see why this should be possible, consider Figure 4 .If (a→b) ∈ E and (a→d) / ∈ E then (b→d) / ∈ E, since if it were we would need to include (a→d) due to transitivity. Similarly, if (c→d) ∈ E and (a→d) / ∈ E then (a→c) / ∈ E, since, if it were, transitivity would imply (a→d) ∈ E. We formalize this in the following proposition.Proposition 2. Let G = (V, E) be a transitively-closed digraph; H = (V, E + H , E - H ) a sidigraph which distinguishes G among transitively-closed digraphs. If (a→d) ∈ E - H , then 1. If (a→b) ∈ E, H ′ = (V, E + H , E - H \{(b→d)}) distinguishes G among transitively-closed digraphs. 2. If (c→d) ∈ E, H ′ = (V, E + H , E - H \{(a→c)}) distinguishes G among transitively-closed digraphs. Proof. Recall that H distinguishing G among transitively-closed digraphs means that G H ∩P = {G}, i.e. G = (V, E) is the only transitively-closed digraph for which E + H ⊆ E and E - H ∩ E = ∅. Now, note that G ′ = (V, (E + H ) tc ) is the smallest transitively-closed digraph containing the edges E + H , and thus G ′ ⊆ G. But this implies E - H ∩ (E + H ) tc ⊆ E - H ∩ E = ∅,and thus G ′ = G. Now we prove the proposition at hand. We prove the first case, the second follows similarly. Let (a→d) ∈ E - H , assume (a→b) ∈ E, and defineH ′ = (V, E + H , E - H \ {(b→d)}). Note that H ′ ⊆ H, and hence G H ⊆ G H ′ . Now suppose K = (V, E K ) ∈ G H ′ ∩ P, which implies K is a transitively-closed digraph with E + H ⊆ E K and (E - H \ {(b→d)}) ∩ E K = ∅.In particular, as a consequence of our observation in the first paragraph, this means (a→b) ∈ E K . We prove (b→d) / ∈ E K by contradiction, for if (b→d) ∈ E K , then since K is transitively-closed we would have (a→d) ∈ E K which violates our preliminary assumption. These two simple prunings, illustrated in Figure 4 , lead us to formulate Algorithm 1, FINDMINDIS-TINGUISHER, which repeatedly removes edges using Proposition 2 until no more can be removed. : G = (V, E) transitively-closed DAG 1: E * ← E 2: for (a→d) ∈ E do 3: for (a→b) ∈ E do 4: E * ← E * \ {(b→d)} 5:end for 6:for (c→d) ∈ E do 7:E * ← E * \ {(a→c)} 8:end for 9: end for 10: return H * = (V, E tr , E * )We note that H * = FINDMINDISTINGUISHER(G) is only defined for DAGs, and indeed for graphs with cycles it is not possible to uniquely define such a sidigraph. (Recall that the transitive closure is not unique for graphs with cycles). In the event that G is acyclic, however, we can prove that H * is not just capable of distinguishing G among transitively-closed digraphs, but moreover it is the sidigraph with the minimum number of edges capable of doing so! Below is a proof sketch for the informal statement. For the full proof refer to Theorem 1 in Appendix B.Proof sketch: The basic idea is to define a partially ordered set, a.k.a. poset, on the set of negative edges of G ± . We then show that the set of all minimal elements in this poset is necessary and sufficient to distinguish G among transitively-closed digraphs. Finally, we observe that our algorithm in the previous section produces the set of all minimal elements and hence its optimality follows.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide a link to the code and data in a footnote on the second page. Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
leveraging sufficient sidigraphs for training node embeddings: 
 We would like to leverage a distinguishing sidigraph for more efficient training and improved accuracy of energy-based node embedding models. The prerequisite is an energy function with a useful inductive bias for the digraph property under consideration. In the extreme case of an inductive bias which only permits models capable of representing digraphs in P we should be able to train using only the positive and negative edges from any H which can distinguish G among those in P.In some instances, depending on the proportion[|E + H * | + |E - H * |]/[|V |(|V | -1)],this may allow full training on digraphs which would otherwise require sampling. As we show, sampling can still be used in conjunction with the minimal edge set implied by a sidigraph, and in such situations we expect not only increased efficiency but increased performance, as L sampled (θ) will better approximate L full (θ).First, we formally define "transitivity bias". Definition 4. Let Z be an embedding space. We say that an energy function E θ has transitivity bias if, for all embeddings θ : V → Z, there exists some threshold T ≥ 0 s.t. for all u, v, w ∈ V , the inequalitiesE θ (u, v), E θ (v, w) ≤ T imply E θ (u, w) ≤ T .We illustrate transitivity bias using the following overly simple embedding model.Example 1 (Bit Vectors). Let Z = {0, 1} |V | , andE BV (u, v; θ) := -log θ(u)•θ(v) θ(v)•θ(v). Then E BV,θ has a transitivity bias using threshold T = 0, asE BV (u, v; θ) = 0 if and only if ∀i ∈ V , θ(v) i = 1 =⇒ θ(u) i = 1. Thus, if E BV (u, v; θ) = E BV (v, w; θ) = 0 we have θ(w) i = 1 =⇒ θ(v) i = 1 =⇒ θ(u) i = 1, hence E BV (u, w; θ) = 0.For a given digraph G = (V, E), we define the bit vector representation of G as θ BV : V → {0, 1} |V | , where the i th (for i ∈ V ) coordinate is given byθ BV (v) i := 1 if i equals v or is a descendant of v, 0 otherwise. Proposition 3. Let G = (V, E) be any digraph, then E BV (u, v; θ BV ) = 0 if and only if (u, v) ∈ E tc . Proof. Let (u, v) ∈ E tc , then there is some path u = w 1 → w 2 → • • • → w n-1 → w n = v in E. By the definition of θ GBV , we have that E BV (w i , w i+1 ; θ G BV ) = 0 for i ∈ n , and thus by the transitivity bias observation made in Example 1 this impliesE BV (u, v; θ G BV ) = 0. Now assume (u, v) / ∈ E tc , then v is not a descendant of u, which means θ G BV (u) v = 0 while θ G BV (v) v = 1, and hence E BV (u, v; θ G BV ) > 0.With an appropriate threshold, any energy function that has transitivity bias in fact represents a transitively-closed digraph: Proposition 4. If E θ is an energy function with transitivity bias, then for any θ there exists a T ≥ 0 such that the digraph with edges{(u, v) | E θ (u, v) ≤ T } is transitively closed.This allows us to formalize the notion that training on any H which can distinguish G among transitively-closed digraphs is sufficient. Proposition 5. Let G be a transitively-closed digraph, E θ an energy function with transitivity bias, andH = (V, E + H , E - H ) a sidigraph which distinguishes G among transitively closed digraphs. If T is the threshold associated with the transitivity bias for θ, E θ (u, v) ≤ T for all (u, v) ∈ E + H , and E θ (u, v) > T for all (u, v) ∈ E - H , then θ represents the digraph G.We would like our energy function to be a representation which is tractable and trainable via gradientdescent, which requires the space Z to have differentiable structure. Box embeddings [Vilnis et al., 2018] are a trainable region-based embedding method which demonstrate strong performance for representing digraphs [Boratko et al., 2021a , Zhang et al., 2022] . We provide the requisite background on box embeddings and define the specific model that we will use for our experiments.As introduced in Vilnis et al. [2018] , box embeddings represent entities using a box or hyperrectangle in R D , i.e., a Cartesian product of intervals Vilnis et al. [2018] proposed modeling a directed graph such that boxes of parents contain their children with an energy functionD d=1 [x ⌞ d , x ⌝ d ] = [x ⌞ 1 , x ⌝ 1 ] × . . . × [x ⌞ D , x ⌝ D ] ⊆ R D , where x ⌞ d < x ⌝ d for d ∈ D .E BOX (u, v; θ) := -log D d=1 F BOX (θ(u) d , θ(v) d ),where the per-dimension parameters are endpoints of an interval, i.e. θ(u) d = [θ(u) ⌞ d , θ(u) ⌝ d ],and the per-dimension score is defined asF BOX ((x ⌞ , x ⌝ ), (y ⌞ , y ⌝ )) := |[x ⌞ , x ⌝ ] ∩ [y ⌞ , y ⌝ ]| |[y ⌞ , y ⌝ ]| = max(min(x ⌝ , y ⌝ ) -max(x ⌞ , y ⌞ ), 0) max(y ⌝ -y ⌞ , 0) .Previous works have highlighted the difficulty of optimizing an objective including these hard min and max functions [Li et al., 2019 , Dasgupta et al., 2020] . We use the Global T-BOX model, the most recent solution to this issue, introduced in Boratko et al. [2021a] . Global T-BOX (or GT-BOX) softens the volume calculation by replacing the hard min and max operators with a smooth approximation LSE t (x) := t log( i e xi/t ). The per-dimension score function is then given byF GT-BOX ((x ⌞ , x ⌝ ), (y ⌞ , y ⌝ ); τ, ν) := LSE ν (LSE -τ (x ⌝ , y ⌝ ) -LSE τ (x ⌞ , y ⌞ ), 0) LSE ν (y ⌝ -y ⌞ , 0) ,which approximates F BOX for sufficiently small τ, ν > 0. These τ, ν are additional (global) trainable parameters of the model.While the motivation and formulation of the energy for box embedding functions is quite different than that of the naive bit vector model in Example 1, it actually is more similar than it may at first appear.Remark 1. As observed in Boratko et al. [2021b] , the box intersection volume calculation can actually be viewed as the L 2 inner-product of characteristic functions of boxes, in which case it takes an identical form to the energy function for bit vectors. For any functions f, g ∈ L 2 (R D ), the standard inner product is ⟨f, g⟩ = R D f (x)g(x) dx. Now, for any box B ⊆ R D , we let 1 B (x) be the characteristic function, which is 1 when x ∈ B and 0 otherwise. Then the volume of intersection of boxes isVol(A ∩ B) = ⟨1 A (x), 1 B (x)⟩,which is also valid if A = B. Thus, we can write the energy functionE BOX (u, v; θ) = -log ⟨1 θ(u) , 1 θ(v) ⟩ ⟨1 θ(v) , 1 θ(v) ⟩ .Remark 2. Box embeddings can be quantized into bit vectors in such a way that applying the bit vector energy function to the resulting quantizations preserves the set of node pairs which have zero energy. Given a box embedding θ, for each d ∈ D let T d be the endpoints of boxes in dimensionsd, i.e. T d := ∪ v∈V {θ(v) - d , θ(v) + d }. Let M d := |T d |, and assign indices T d =: {t d,m } M d m=1 such that t d,m ≤ t d,m+1 for m ∈ M d -1 . Then, for each v ∈ V and d ∈ D , form the M d -dimensional vector φ(v) d,m := F BOX (θ(v) d , (t d,m , t d,m+1)). By construction, this value will be either 0 or 1.Letting φ(v) ∈ {0, 1} M d be the concatenation of {φ(v) d } D d=1, we obtain a bit vector representation, for which the energy functionE(u, v; φ) = -log φ(u)•φ(v) φ(v)•φ(v) is such that E(u, v; φ) = 0 if and only if φ(v) d,m = 1 =⇒ φ(u) d,m = 1, which is true if and only if [θ(v) + d , θ(v) + d ] ⊆ [θ(u) - d , θ(u) + d ].Most importantly for our purposes, however, is the following proposition.Proposition 6. The energy function E BOX,θ has a transitivity bias.Apart from prior empirical observations that box embeddings work well to embed transitively-closed DAGs Boratko et al. [2021a] , Proposition 5 suggests it should be possible to train box embeddings on the output of FINDMINDISTINGUISHER to represent a transitively-closed DAG. In practice, we train the smooth approximation provided by GT-BOX. As τ, ν → 0 + , which often happens naturally during training Boratko et al. [2021a] , we expect it to capture the transitivity even when trained only on the positive and negative edges of the distinguisher provided by the algorithm. 
hierarchy-aware sampling: 
 In this section we formally how we sample edges for our loss function, which we term hierarchy-aware sampling. Based on the results in the preceding section, given a transitively-closed digraph G, if E θ has a transitive bias and the sidigraph H = (V, E - H , E + H ) can distinguish G among transitively-closed digraphs, then we can train using the following loss function:L ha (θ; H) := (u→v)∈E + H ℓ + (E θ (u, v)) + (u→v)∈E - H ℓ -(E θ (u, v)).In particular, for a transitively-closed DAG G, we can use H * as returned by Algorithm 1.If the cardinality of H * is small enough, this may make training using L ha feasible. In general, however, we still may need to sample negative edges using some noise distribution, as mentioned in Section 2.2. In practice, we will compare using the sidigraphs G ± and H * = FINDMINDISTINGUISHER(G), which means positives will be sampled from either E or E tr , and negatives will be sampled from E or E - H * . Even with our reduced set of negatives, there are still far more negatives than positives, and so we adopt the common practice of sampling k negatives for every positive within a batch. 
experiments: 
 The main aim of our experiments is to compare the efficacy on graph representation learning of models with vs without transitivity bias, and random uniform vs hierarchy-aware sampling. As per Proposition 5, we hypothesize that the greatly reduced edge set in hierarchy-aware sampling will be sufficient to faithfully represent the graphs in the embedding space if our model has transitivity bias.Data. We evaluate hierarchy-aware sampling on the heterogeneous synthetic DAGs for which Boratko et al. [2021a] demonstrated superior performance using GT-BOX and random uniform negative sampling: balanced trees, where b is the branching factor, the nested Chinese restaurant process (nCRP) [Blei et al., 2010] , where α is the normalized "new table" probability, and Price's model [Price, 1976] , where m is the number of connections for a new node and c is a constant factor added to the probability of a vertex receiving an edge4 . We also test on the larger real-world Medical Subject Headings (MeSH) taxonomy Lipscomb [2000] , 2020 release. For detailed statistics about all graphs we refer the reader to Table 1 in Appendix F. Models. To evaluate the importance of the model having transitivity bias in order to take advantage of this reduced set of edges, we consider the vector similarity model SIM-VEC which represents each node by an "in" and "out" vector, and computes edges via dot-product,E SIM-VEC (u, v) := -log(σ(θ(u) out • θ(v) in )). Unlike GT-BOX, SIM-VEC does not have transitivity bias Boratko et al. [2021a] . For all of our experiments we fix the dimension to 64; this corresponds to 64-dimensional "in" and "out" embeddings for SIM-VEC, and to the two 64-dimensional corners x ⌞ and x ⌝ of GT-BOX. This makes the number of parameters per node for both models 128. For details on hyperparameter tuning, see Appendix E. Support and Sampling. For the synthetic graphs we iterate over settings relating to the support sets from which to uniformly randomly sample positive and negative training edges, respectively:• Sampling positive edges from the transitive reduction E tr vs transitive closure E tc . • Sampling negative edges from minimal hierarchy-aware set E - H * vs edge complement E. • Negative sampling ratio k = 4 vs k = 128 (i.e. per each positive edge seen by the model, k negative edge sampled uniformly randomly from the support set also get seen).Setting k = 4 mimics the tiny proportion of sampled negatives to the pool of all possible negatives, a limitation which we expect when scaling to larger graphs, such as MeSH.Evaluation. Since we are evaluating the representational capacity of each experimental setting (as opposed to generalization on some held-out edge set), our metric is the F1 between the edges of the transitively-closed DAG we are modeling and the model's scores for those edges. In other words, we are performing binary classification over the full adjacency matrix for the hierarchy in question.We investigate the impact of the available positive and negative support sets on model training; since the representational capacities of vector and box models are well-studied, we are not interested in the best F1 score attainable by these models, but the effect of respective support sets on convergence. To compare across experimental settings, we plot F1 as a function of the number of total examples (both positive and negative edges) processed by the model (e.g. Figure 6 ). To measure the final performance and rate of convergence, we use the area under the F1 vs. Total Examples curve (AUF1C).First note that GT-BOX universally outperforms SIM-VEC on the graph modeling experiments. This is not surprising, as Boratko et al. [2021a] demonstrate the superior inductive bias of GT-BOX for modeling digraphs generally. The aim of our experiments, however, is to investigate the impact of a hierarchy's structure on the convergence for the various sampling settings for GT-BOX specifically.With this aim, in Figure 5 , we present the AUF1C for the convergence curve (area under F1 vs. number of examples) in the limited-example setting of k = 4. In this regime random uniform negative sampling may not be able iterate over all of E in a reasonable amount of time, whereas, to the contrary, it is possible to get through all of E - H * in a limited number of epochs, since in many cases the sampling pool is reduced by more than 99% (cf. Figure 5 demonstrates a striking trend observed consistently in our experiments. While GT-BOX with our reduced edge set performs on par or better than with the original edge set, in contrast, the performance of SIM-VEC degrades significantly. We demonstrate this using a representative example in Figure 6 , where, in stark contrast to GT-BOX taking advantage of E - H * and outperforming all SIM-VEC settings, both SIM-VEC settings that use E - H * fail to converge even to 0.4 F1. This dichotomy hearkens back to Proposition 5, which underlines the non-trivial synergy between an energy function with transitivity bias and the hierarchy-aware output of FINDMINDISTINGUISHER.Balanced tree. Figure 11 Row 1 visualizes the impact on convergence of increasing the branching factor. As branching factor b increases 2 < 5 < 10, we first note that the balanced tree with fixed |V | becomes more and more shallow. While E - H * performs well on all values of b, it particularly stands apart from E in the b = 10 setting. nCRP. α is the normalized "new table" probability, with a smaller α implying more separate clusters with a deeper hierarchy, and a larger α implying fewer clusters and a more shallow hierarchy. The relative improvement of using E - H * is more significant for smaller α. Price. Price's model is learnable by GT-BOX especially quickly under any setting, as evidenced by the very high AUF1C scores in Figure 5 . Higher c has the effect of making edge attachment more uniformly distributed among nodes. In Figure 11 Row 3 we examine convergence values for c = 0.1 , noting that E - H * typically underperforms E but catches up in the limit. As m (out-degree of newly added vertices) increases 1 < 5 < 10, looking at Table 1 we note that hierarchy-aware negative pruning also gets more aggressive as 52.35% < 89.62% < 93.77%.MeSH. As seen in Figure 8 , on the larger real-world MeSH taxonomy, not only does GT-BOX outperform SIM-VEC, but our minimal negative edge set E H * within GT-BOX outperforms sampling from the edge complement, while being a 99.78% reduction. Meanwhile, E H * with SIM-VEC plummets, consistently with the trend exhibited in Figure 6 . This encouraging result on a graph with ≈ 2 15 nodes points not only to the economy of our approach, but to the stability and improved performance on large real-world data. While the connection between hierarchies and transitivity bias allows us to capitalize on it in the form of hierarchy-aware sampling, we acknowledge that the properties demanded of both the data and model are restricted to transitivity. While this does encompass a large variety of relationships observed in real-world graphs, this specific algorithm does not extend easily to new combinations of graph properties and inductive biases, which is a goal of future work. 
limitations: 
 Another limitation is the extent to which this sort of method would break down for graphs which are, strictly speaking, not transitively-closed, but close (in edit distance) to being transitivelyclosed. Strictly speaking, our proofs do not apply in that setting, and the efficacy of the approach may vary depending on the type of structural changes a particular removal of an edge brings about. 
conclusion: 
 In this work, we propose a novel framework for identifying a sufficient subset of entities in the adjacency matrix which unambiguously specify a digraph, given some prior structural knowledge.We demonstrate the usability of this framework for the property of transitively-closed DAGs, or hierarchies. We derive a characterization of the sufficient negative set for such type of graphs, and based on that we devise a novel hierarchy-aware sampling technique. Our approach is efficient and robust when used in conjunction with an energy-based node embedding model possessing the appropriate inductive bias, which, for hierarchies, is transitivity bias. , 2012, Mnih and Teh, 2012] . Additionally, they demonstrate that (for vector node representations), the optimal negative sampling distribution is positively but sub-linearly correlated to the positive sampling distribution, i.e.p n (u | v) ∝ p d (u | v) α , 0 < α < 1,which supports the empirically-determined 3/4 in Mikolov et al. [2013] 's degree-based sampling.Examples of better-than-uniform NS for GRL include, in chronological order, Markov chain Monte Carlo NS (MCNS) [Yang et al., 2020] , self-adversarial NS (SANS) [Kamigaito and Hayashi, 2022] ,Adaptive NS (AdaNS) [Wang et al., 2023] . A handful of approaches leverage the graph structure directly to gather negative examples; in particular, Structure Aware NS (also abbreviated SANS) of Ahrabian et al. [2020] selects negatives from a node's k-hop neighborhood. Hierarchical Negative Sampling (HNS) [Chen et al., 2021] is only close to our HANS algorithm in nomenclature, relying on a hierarchical dirichlet process to model neighbor proximity information, while borrowing its approach from DeepWalk's [Perozzi et al., 2014] random walks for skip-gram prediction of the current vertex.We emphasize that each of these above approaches presupposes undirected graphs and vector embeddings of nodes, aligning them with the vast literature on KG embeddings including TransE [Bordes et al., 2013] , TransR [Lin et al., 2015] , RESCAL [Nickel et al., 2011] , DistMult [Yang et al., 2015] ,ComplEx [Trouillon et al., 2016] , RotatE [Sun et al., 2019a] , and Rot-Pro [Song et al., 2021] (the last of which models transitive relations via a projection operator). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The work done in this paper is largely theoretical and we don't see an immediate and direct societal impact for the work in its current form.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: The necessary credits are given at appropriate places throughout the paper. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Box embeddings can represent any DAG [Boratko et al., 2021a] , and more recently have been extended to represent any digraph [Zhang et al., 2022] . Empirically, box embeddings have demonstrated particularly strong performance on transitively-closed graphs, making them a strong candidate for modeling hierarchies [Patel et al., 2020] . The use of regions to capture edges in a graph has roots in classic graph invariants of boxicity [Roberts, 1969] and sphericity [Maehara, 1984] , which are defined in the undirected setting. In general, one might expect region-based embeddings to have a natural bias toward modeling transitivity, as the containment relation is transitive [Patel et al., 2022] . Additional region-based embeddings which use cones [Vendrov et al., 2016, Lai and Hockenmaier, 2017] or discs [Suzuki et al., 2019] have also been proposed.Another prominent line of work for graph representation leverages the negative curvature of hyperbolic space to embed trees without distortion [Sarkar, 2011 , Weber and Nickel, 2018 , Weber, 2020] . A variety of approaches to training hyperbolic representations with gradient descent have been proposed, to great success [Nickel et al., 2015 , Law et al., 2019] . The highlight of these methods is their ability to represent trees, but they are not necessarily well-aligned with representing transitively-closed digraphs [Boratko et al., 2021a] . Hyperbolic entailment cones [Ganea et al., 2018] combine the benefits of both hyperbolic space and region-based containment transitivity.The idea of optimizing a loss which is a sum over positive and negative edges captures the approach of training node embeddings in all the work mentioned in the preceding section, however, there are also a variety of other approaches to learning node embeddings. DeepWalk [Perozzi et al., 2014] and node2vec [Grover and Leskovec, 2016] use random walk-based algorithms to generate node embeddings for undirected graphs. LINE [Tang et al., 2015] was the first attempt to address the scalability of learning node embeddings for large-scale graphs. Meanwhile, some works focus on learning node embeddings for directed graphs [Ou et al., 2016 , Sun et al., 2019b , Sim et al., 2021] .While more conventionally used in settings where node features are present, graph neural networks (GNNs) [Kipf and Welling, 2016] , which iteratively aggregate node features using the local graph structure, have been used to learn node embeddings [Chen et al., 2020 , Liu et al., 2020 , 2021] . While these approaches are not directly addressed in this work, the general notion of using a sufficient sidigraph to reduce the set of edges and non-edges could be leveraged in such contexts as well.The idea of uniquely distinguishing a graph with respect to a property has been explored in graph theory literature, albeit without a special focus on DAGs as in the current work. For a property P on n-vertex graphs, Adamaszek [2014] defines P to be "nonevasive" (or "nonelusive") in the context of a 2-player game where for each turn, player A is only allowed to ask player B whether a pair of nodes forms an edge or not. P is nonevasive if it can be determined by A in strictly fewer than n 2 turns, i.e. by asking fewer questions than edges in a complete graph over n vertices (it follows that completeness is an evasive property). Kelenc et al. [2018] spotlight minimal uniquely distinguishing graphs by introducing the concept of an edge metric dimension as the smallest cardinality of a set S such that every pair of edges in G is distinguished (w.r.t. node-edge distance) by some vertex in S.An appealing application of this graph-theoretic line of thought might be selecting the smallest set of edges from an ontology for the purpose of human annotations to facilitate active learning; Peng et al.[2018] present an algorithm for enumerating consistent subgraphs of DAGs, which are often used for ontologies in the biomedical domain.For notational convenience, for each vertex a ∈ G, we add a directed self-loop (a→a) to indicate that a is reachable from itself. This self-loop will be a positive edge in G ± . Adding this self-loop does not destroy the property that G is transitively closed.We define an order ⪯ between negative edges as follows.For every negative edge (a→b), we impose (a→b) ⪯ (a→b). Thus, ⪯ is reflexive. Next, we define an order between two negative edges outgoing from or incoming to the same vertex. Let a be an arbitrary vertex in V . Let (a→b) and (a→c) be two negative edges out-going from a. Then we define (a→b)⪯ (a→c) if (c→b) is a positive edge in G ± (in other words, if (c→b) ∈ E).We call the edge pair ((a→b), (a→c)) a primitive pair. See Figure 9 (a). Similarly, let (x→a) and (y→a) be any two negative edges incoming to a. We define (x→a) ⪯ (y→a) if (x → y) is a positive edge. The edge pair (x→a) and (y→a) is also a primitive pair.Finally, we extend ⪯ to satisfy transitivity: if there exist three edges such that (a→b) ⪯ (c→d) and (c→d) ⪯ (e→f ) such that currently there is no relationship between (a→b) and (e→f ) under ⪯, then we impose (a→b) ⪯ (e→f ). Our goal is to show that (E, ⪯) is a poset. To this end, we characterize all pairs of negative edges (a→b) and (c→d) such that (a→b) ⪯ (c→d). Proof. We prove by induction. The base cases are for primitive pairs. If (a→b) and (c→d) are a primitive pair, then either a = c or b = d. In both cases, the lemma holds by definition of the order ⪯ on primitive pairs. Let (a→b) = e 1 ⪯ e 2 ⪯ . . . ⪯ e t = (c→d) be a minimal sequence of orders realizing the order (a→b) ⪯ (c→d) such that every consecutive pair of negative edges (e i , e i+1 ) for every i ∈ [1, t -1] is a primitive pair. Specifically, (e 1 , e 2 ) is a primitive pair. We consider two cases: (i) e 2 = (a→x) and (ii) e 2 = (y→b) for some vertex y. The two cases are symmetric, so we only focus on the first case; see Figure 9 Since (a→b) ⪯ (x→y), by Lemma 1, (a → x) is a positive edge. Also by Lemma 1, as (x→y) ⪯ (a→b), we have that (x → a) is also a positive edge. However, this contradicts that G is a DAG.We could reinterpret Proposition 2 in the language of the poset (E, ⪯):Corollary 1. Let G be a transitively closed DAG. Let H = (V, E + H , E - H ) be a sidigraph which distinguishes G among transitively-closed digraphs. Let e 1 , e 2 be a primitive pair of negative edges in E - H such that e 1 ⪯ e 2 . Then (V, E + H , E - H \ {e 2 }) also distinguishes G among transitively-closed digraphs.We have shown in Lemma 2 that (E, ⪯) is a poset. Let M ⪯ be the set of minimal elements of this poset; see Figure 10 . Our proof to show that Algorithm 1 is optimal has two steps: ( Step Here M ⪯ = {(d→a), (b→c), (a→d), (c→b)} (c) a minimal sidigraph (V, E tr , M ⪯ ) which can distinguish G among transitively-closed digraphs.Proposition 7. If G = (V, E) is a DAG, then H = (V, E tr , M ⪯ ) can distinguish G among all transitively-closed digraphs.Proof. Let L be the linear ordering of all edges in E in non-decreasing order of ⪯. That is, if (x→y) ⪯ (a→b), then (a→b) appears before (x→y) in L. L can be obtained by visiting the negative edges in the BFS order in the Hasse diagram with an artificially added maximum element ∞ to define the root of the BFS tree; see Figure 10(b) .Let X 0 = E and i = 0. We then visit all negative edges by the order in L. For each negative edge e visited in this order, if e ̸ ∈ M ⪯ , we define X i+1 = X i \ {e} and increase i by 1. Let X t be the last set of negative edges after this process terminates. Clearly, X t = M ⪯ .By Proposition 1, (V, E tr , X 0 ) can distinguish G. Inductively, we assume that (V, E tr , X i ) can distinguish G for some i. Let e be a negative edge such that X i+1 = X i \ {e}. Since e ̸ ∈ M ⪯ , there exists a primitive pair of negative edges e ′ ⪯ e. Since e ′ appears after e in L, both edges are present in X i . By Corollary 1, (V, E tr , X i+1 ) can distinguish G among transitively closed digraphs.We have shown by induction that (V, E tr , X t ), which also is (V, E tr , M ⪯ ), is a transitively-closed distinguisher.Next, we show that any sidigraph capable of distinguishing G among transitively-closed digraphs must contain any M ⪯ in it's negative set.Proposition 8. Let H = (V, E - H , E + H ) be any sidigraph capable of distinguishing G among transitively-closed digrphs. Then M ⪯ ⊆ E - H .Proof. We prove by contraction: suppose e = (c→d) is such that(c→d) ∈ M ⪯ \ E - H . Let G ′ = (V, E ∪ {e}). We show below that G ′ ∈ G H ∩ P, which then means that H cannot distinguish G from G ′ among transitively-closed digraphs.Note that G contains all positive edges of H since H is a transitively-closed distinguisher. Thus, G ′ contains all positive edges of H. Next, we show that G ′ does not contain any negative edge. Suppose otherwise, G ′ contains a negative (a→b) ∈ E - H . Since (a→b) ̸ ∈ E, the only way for (a→b) ∈ E ∪ {e} is because of (c→d), and in particular, (a→c) and (d→b) are both positive edges in G. Thus, by Lemma 1, (a→b) ⪯ (c→d), contradicting that (c→d) ∈ M ⪯ .Finally, we show that G ′ is transitively-closed. Suppose otherwise, there are two vertices a and b such that b is reachable from a but (a → b) ̸ ∈ G ′ . Note that b is not reachable from a in G since G is transitively closed. This implies: (i) the path from a to b in G ′ must contain the edge (c→d) and (ii) (a→b) is a negative edge in G. By (i), it must be that (a→c) and (d→b) are positive edges. By (ii) and Lemma 1, (a→b) ⪯ (c→d), contradicting that (c→d) ∈ M ⪯ .Proposition 7 and Proposition 8 together imply that any transitively closed-distinguisher of G with M ⪯ contains a minimum number of negative edges. Thus, to show that our algorithm gives a transitively closed distinguisher of G, it suffices to show that the set of negative edges is M ⪯ . Theorem 1. Let G = (V, E) be any DAG, and let H be the output of FINDMINDISTINGUISHER(G), so H = (V, E tr , M ⪯ ). Then H can distinguish G among transitively closed digraphs, and has the minimal number of edges of any such sidigraph.Proof. We focus on showing that E - H = M ⪯ . The latter claim follows from Proposition 7 and Proposition 8.Observe that the algorithm considers primitive pairs and, for each pair, removes the negative edge with a higher order in the poset (E, ⪯). Thus, the algorithm never removes a negative edge inM ⪯ from H, giving that M ⪯ ⊆ E - H . It remains to show that E - H ⊆ M ⪯ . Suppose otherwise.Then there exists a negative edge (a→b) ∈ E - H \ M ⪯ . Then by definition of M ⪯ , there must be a negative edge (x→y) such that (i) (a→b) and (x→y) make up a primitive pair, and (ii) (x→y) ⪯ (a→b). Then (a → b) will be removed from H when the algorithm considers (x→y) in line 4, contradicting that (a→b) ∈ E - H .Proposition 4. If E θ is an energy function with transitivity bias, then for any θ there exists a T ≥ 0 such that the digraph with edges{(u, v) | E θ (u, v) ≤ T } is transitively closed. Proof. Let (u, v) ∈ E tc . Then there exists a directed path u := w 1 → • • • → w N =: v in E, hence E θ (w n , w n+1 ) ≤ T for all n ∈ N -1 . Let k ∈ N -2, and assume we have E θ (w 1 , w k+1 ) ≤ T . Since E θ (w k+1 , w k+2 ) ≤ T as well, we apply the definition of transitivity bias to find E θ (w 1 , w k+2 ) ≤ T . Thus, by induction, we haveE θ (w 1 , w N ) = E θ (u, v) ≤ T .Proposition 5. Let G be a transitively-closed digraph, E θ an energy function with transitivity bias, and H = (V, E + H , E - H ) a sidigraph which distinguishes G among transitively closed digraphs. If T is the threshold associated with the transitivity bias for θ, E θ (u, v) ≤ T for all (u, v) ∈ E + H , andE θ (u, v) > T for all (u, v) ∈ E - H , then θ represents the digraph G. Proof. Let E ′ = {(u, v) | E θ (u, v) ≤ T }, then Proposition 4 implies that the digraph G ′ = (V, E ′ )is transitively closed. Due to the assumptions on the values of the energy we haveE + H ⊆ E ′ and E - H ⊆ E ′ .Since H is sufficient to distinguish transitively-closed digraphs, we have G ′ = G, as desired. The experiments were run in a single-node, single-GPU setup on a cluster with the following GPU architectures:• NVIDIA Tesla M40 (24GB VRAM) • NVIDIA GeForce GTX TITAN X (12GB VRAM) • NVIDIA GeForce GTX 1080 Ti (11GB VRAM) • NVIDIA RTX 2080ti (11GB VRAM) • NVIDIA Quadro RTX 8000 (48GB VRAM)To ensure the competitiveness of all experimental configurations for the synthetic graphs, we tune the learning rate and negative weight λ neg for each graph independently by running Bayesian hyperparameter optimization with W&B Biewald et al. [2020] and for E tc taking the values that yielded the best F1 at the end of 12 epochs, which we empirically observed corresponds to the "elbow" of many per-epoch F1 plots and thus gives a good indication of which settings are resulting in fast convergence. For E tr , we scaled the number of epochs to 60, since the number of training examples is substantially smaller for this setting than for transitive closure.For each of the final experiment runs, we fetch the best learning rate and λ neg and run for a full 40 epochs for E tc or 200 for E tr , recording F1 at every epoch to produce a convergence plot.Since MeSH has at least thrice the number of nodes as any of the synthetic graphs in our experiments, it was infeasible to tune hyperparameters over all the same settings as for the smaller synthetic graphs. We therefore fix positive edge set E tc (which empirically performs better than E tr ), as well as the resource-efficient negative ratio k = 4, and do a Bayesian hyperparameter search for learning rate and negative rate λ neg using W&B over the cross-product of model type (SIM-VEC vs GT-BOX) and negative edge set (E vs E H * ).Graph Type 1 : Statistics for the synthetic transitively-closed DAGs used in our experiments (Section 6), counts for the number of positive/negative edges in the equivalent and optimal distinguishing sidigraphs, and the ratios for the "full" and "reduced" experimental settings. While graphs under Balanced Tree are deterministic, the values of each entry for nCRP and Price are averaged over 10 random seeds.Θ |V | |E| |E tc | |E tr | |E| |E H * | |E|/|E| 1 -|E tr |/|E tc | 1 -|E H * |/|E|G Plots for k = 128 NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Our code and data are available at https://github.com/iesl/geometric-graph-embedding.A simple digraph is one without multiple edges or self-loops, i.e. the adjacency matrix contains only 0s and 1s, with 0s on the diagonal. We ignore self-loops in the graph modeled by the learned representations.A canonical example is the transitive closure of a directed path of length n, where|E tc | = (n -1)(n -2), but |E tr | = n -1.Preferential attachment exponent γ = 1.0 throughout. 


Decision: This paper presents a novel procedure to identify a unique directed acyclic graph among all such possible graphs by querying the minimum possible potential edges (entries in the adjacency matrix). The authors utilize this framework to develop hierarchy-aware sampling for training node embeddings more efficiently, reducing the number of training samples required. They also report experiments on synthetic hierarchies and real-world taxonomies, demonstrating the efficiency of their method. 

I think the authors propose both an interesting theoretical question, and evaluate practical impact from exploiting known structure of the underlying graph. I think this is an interesting avenue for research, and can motivate up several follow-up works. I recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper addresses the challenge of training node embedding models on large directed graphs (digraphs) where it is impractical to observe all entries of the adjacency matrix during training, necessitating sampling methods. Recognizing that many entries remain unobserved in very large digraphs, the authors develop a novel framework to identify a minimal subset of entries required to uniquely distinguish a graph among all transitively-closed directed acyclic graphs (DAGs). They provide an explicit algorithm to compute this minimal set and empirically demonstrate that training node embedding models with this subset improves efficiency and performance, assuming the energy function has an appropriate inductive bias. Experiments on synthetic hierarchies and a large real-world taxonomy show robust performance, with improved convergence rates and a reduction in training examples by up to 99%, making the method highly effective in resource-constrained settings.
strength_weakness: strength_weakness: 1. The effciency and robustness of the proposed method is verified via experiments on various types of hierarchies, including Balanced tree, nCPR, Price, and MeSH. However, it could be of more intuitive if the generic motivation of pursuing hierarchy-awareness can be illustrated with real world applications.
questions: questions: It would be appreciate if the author can illustrate the motivation of this work in the pursuit of effciency and robustness in learning representations for hierarchy with minimal support.
limitations: limitations: N/A
paper_summary: paper_summary: Authors propose an algorithm to identify a subset of entries required to uniquely distinguish a graph among all transitively-closed DAGs, based on the theoretical analysis of transitive reduction of the associated signed digraph. These newly identified subsets are leveraged to learn node embeddings via contrastive learning approaches based on negative sampling more efficiently. The relevance of this novel contrastive approach is empirically validated on several synthetic datasets of DAG and one real-world dataset, leading to comparable or better performances than vanilla negative sampling strategies.
strength_weakness: strength_weakness: *edits after rebuttal in italic* 

1. As expressed by authors the range of applications relating to their study remains significantly narrow even if interesting. It could be of interest to compare their approach on the studied datasets with methods enforcing transitivity while covering a broader score e.g Rot-Pro (Song & al, 2021 in the paper)

2. Some points remain unclear to me in the experiments:
   - a) *[partly adressed]* Could you further detail the architecture and optimization procedure followed in your experiments ? Results reported in Figure 1 (Boratko & al, 2021) with d=128 (as you set) seems to be significantly better than the ones you report for sim-vec, could you clarify this matter ? Their analysis also emphasize that it will be relevant to study the sensitivity w.r.t $d$ across various negative sampling strategy, i encourage you to do so. It would also be of interest to check if these rankings are consistent while using another transitive representation learning scheme like GT-box.
   - b) *[Done]* From L.245, I expected comparison between k=4 and 128 but only results for k=4 are reported in the paper. Could you explain why and potentially fix that ? 
   - c) *[partly adressed]* Unclear analysis of results for synthetic dataset, potentially to be refined by studying correlations with some dataset statistics. For instance, why are there opposite dynamics w.r.t to the depth between 'balanced tree' and 'nCRP' ?
   - d) Experiments on real datasets stopped too early ? It could be of interest to pursue experiments on the real dataset reported in Figure 8 until specific models seem to have converged as dynamics with small number of samples seem more erratic.

small tipos:
- L.208, missing word ? we formally `explain`...
- L.37-38: misleading / big claim, as you study a very specific type of graph.
questions: questions: I invite authors to discuss and address the weaknesses/questions I have mentioned above, so that I can consider improving my score.
limitations: limitations: The authors have made an effort to address the limitations of their work, I encourage them to answer the questions above to ensure that all potential limitations have been covered.

No potential negative societal impact.
paper_summary: paper_summary: This paper proposes a novel framework for identifying a minimal subset of entries in the adjacency matrix that uniquely distinguishes a directed acyclic graph (DAG) among all transitively-closed DAGs. The authors provide a provably optimal algorithm for computing this minimal set. They then leverage these insights to develop hierarchy-aware sampling, which allows training node embedding models more efficiently by focusing only on the essential graph information. Specifically, they prove that models with an inductive bias of transitivity, such as box embeddings, can learn faithful representations of hierarchies using substantially fewer training examples selected by their sampling approach. Experiments on synthetic and real-world graphs demonstrate that their method significantly reduces training data by up to 99% while maintaining or improving model performance and convergence rates compared to uniform negative sampling.
strength_weakness: strength_weakness: - While the paper demonstrates the effectiveness of transitivity bias and hierarchy-aware negative sampling for DAGs, the authors could discuss whether these ideas extend to learning representations of other graph families characterized by different structural properties. Are there other useful inductive biases worth incorporating into node embeddings and corresponding "structure-aware" sampling strategies? 
- The experiments focus on evaluating hierarchy-aware sampling, but there is less empirical analysis of the FINDMINDISTINGUISHER algorithm itself, e.g. runtime complexity, actual sparsity of computed sidigraphs, etc. Knowing when the sidigraph is substantially smaller than the original graph is important for determining when hierarchy-aware sampling is computationally beneficial.
questions: questions: - The framework of sidigraphs for distinguishing graphs with a given property seems quite general. Have the authors considered instantiating it for properties other than transitivity?
- Do the authors have intuition or theory on why hierarchy-aware sampling provides a greater speed-up on some graphs than others (e.g. balanced trees vs Price graphs)?
- Could hierarchy-aware sampling also improve the computational efficiency of non-embedding GNN approaches for learning hierarchical structures, since they also implicitly perform a form of negative sampling via contrastive estimation?
limitations: limitations: Yes, there is a section about the limitations of the work.
paper_summary: paper_summary: This paper proposes to distinguish a directed graph (digraph) among all transitivity-closed DAGs by finding minimal signed directed graph (sidigraph).
This paper exploits this idea to propose a more efficient algorithm for node embedding models.
strength_weakness: strength_weakness: - It is not clear regarding prop 2 if the distinguishing serigraph H' is "lighter" than the transitive reducted G'.

This seems to "shift" the problem from reducing G to G' to reducing G to H'.
I do not see the benefit of obtaining H' over directly obtaining G'.

- The scope of this paper is unclear. In the introduction, the key question is bolded and may be answered Prop. 2. However, what is the rest of the paper?

- It is difficult to understand the aim of the experiments. In L253, the authors wrote as 

> We investigate the impact of the available positive and negative support sets on model training; since the representational capacities of vector and box models are well-studied, we are not interested in the best F1 score attainable by these models, but the effect of respective support sets on convergence

However, the very first sentence of the result in L260 is 

> First note that GT-BOX universally outperforms SIM-VEC on the graph modeling experiments

If the authors want to show that the proposed algorithm outperforms the existing one, then probably the authors want to compare with many more. If not, what is this sentence? I think that this experiment aims to show the superiority of the proposed algorithm by comparing it with SIM-VEC from the viewpoint of the effect of respective support sets on convergence. Thus, I think the authors want to compare with more.

This may be the presentation issue or content-wise issue. Anyhow, I hope the authors clarify these points.
questions: questions: I hope the authors clarify the points raised in the weaknesses section.
limitations: limitations: NA
paper_summary: paper_summary: This paper develops a framework to identify a subset of entries required to uniquely distinguish a graph among all transitively-closed DAGs. It achieves robust performance on synthetic hierarchies and a larger real-world taxonomy.
strength_weakness: strength_weakness: W1:  The end-to-end efficiency is not clearly evaluated in this work, making it a bit unclear to assess the significance of the work in practice. For example, the proposed technique helps learn representations with minimal entries supported during training, where the minimal entries lead to reduced complexity in terms of computation; however, the hierarchy-aware sampling process itself adds additional operations, which may or may not result in increased overall complexity. 

W2: The hierarchy aware sampling is a key technique in the proposed solution. The authors should elaborate the sampling process. The loss function provided in Section 5 seems relying on several not-well-defined terms, making it a bit concerned about the repeatability of the work. 

W3: The presentation should be improved. For example, in Section 5,  the verb is missing in the first sentence. I assume the authors mean “formally —> formulate”.
questions: questions: Refer to the weakness section above.
limitations: limitations: The authors called out the limitations in term of extending the proposed method to new combinations of graph properties and inductive biases, as well as that  the efficacy can vary when applying the method to graphs not transitively closed.

Comments: title: Thank you for reviewing our rebuttal!
Thank you for reviewing our rebuttal!
Feedback on rebuttal
Thank you for your clarifications!
Thank you very much for the rebuttal
Answer to author
comment: Hi authors, thanks for the response and sharing your thoughts. I believe I was asking about the impact of the super nodes of the original input graph. If I am correct, the high reduction rate of the negative support set is related to the equivalent sidigraph, conceptually introduced by the proposed method, rather than the original structural density or node degrees of the input graph. Since the equivalent sidigraph can be significantly denser (orders of the magnitude) than the input graph structure, the high reduction rate of negative support set per se would not convincingly address the concern regarding the super nodes in large scale graphs. Hence, I would like to maintain my opinion.
Thank you for reviewing our rebuttal!

> According to the complexity analysis in the rebuttal, the concern remains as in reality many graphs have very skewed degree distributions, which imply possible efficiency challenges around super nodes.
> 

Indeed, some graphs are not as benefitted by the reduction in FINDMINDISTINGUISHER as other (compare the moderate reductions in Price graphs, Table 1, Appendix H, vs the drastic reduction in Balanced Trees). However, **on a large real-world hierarchy such as MeSH, the provably minimal support set does indeed reduce the negative support set by over 99% (cf. Table 1), while converging faster than the full negative support set (cf. Figure 8)**. Thus, our graph-theoretically optimal reduction is impactful in a real-world setting. We have also experimentally validated our theoretical findings on 3 distinct families of transitively-closed DAGs to yield a diverse suite of synthetic graphs. Could you please let us know if you have a particular graph or graph family in mind?

> The additional details for the hierarchy aware sampling improves the clarity a bit, but the novelty is not very clear given the key role of hierarchy aware sampling in the proposed solution.
> 

We stress that **the key novelty of this paper is the minimal size of the support set rather than the sampling procedure**. Indeed, we use the same sampling procedure as in Boratko et al. 2021, and demonstrate that it yields comparable or better convergence even if sampling out of a support set of negative edges that is reduced by as much as 99%. Therefore, **we intentionally kept the sampling procedure the same between lines 74-75 and 211-212, in order to compare the impact of the respective support sets on convergence**.
Thanks again for the authors' efforts on addressing my comments. According to the complexity analysis in the rebuttal, the concern remains as in reality many graphs have very skewed degree distributions, which imply possible efficiency challenges around super nodes. The additional details for the hierarchy aware sampling improves the clarity a bit, but the novelty is not very clear given the key role of hierarchy aware sampling in the proposed solution. Overall, I would like to maintain my opinion on this paper.
Thank you for reviewing our rebuttal!

> The authors may want to more explain on the motivation behind the second part in introduction, as in the similar manner as the first part.
> 

The motivation for the second part is to demonstrate that the graph-theoretic results can be applied in practice, by leveraging a machine learning model with transitivity bias. (See also lines 41-45 in the introduction).

> Also, as far as I understand, comparing two on transitivity bias is not enough. […]
> 

We selected models for empirical evaluation with two goals in mind:

------------------

1. Validate that our theoretical claims can be obtained in the practical setting, in the context of things such as hyperparameter selection and stochasticity in the training loop.

To do so, it was necessary to demonstrate that a model with transitivity bias could achieve similar performance when training on our proposed reduced edge set (up to 99.9% reduction) as when trained on the full edge set. As such, we needed to select a model which (a) had strong modeling capacity on transitively closed DAGs, and (b) satisfied the formal definition of transitivity bias, as in Definition 4. Box embeddings were the obvious choice to satisfy (a), having the best performance of any model on transitively closed DAGs as reported in Boratko et al. 2021. We then proved that box embeddings satisfy (b) in Proposition 5. We then tested the model, and observed that it was, indeed, able to obtain similar or better results when using our reduced edge set.

This, on its own, is enough to validate that the theoretical claims at least can be obtained in practice.

------------------

2. Empirically demonstrate that the facet of transitivity bias is important.

For this purpose, we needed to choose a model which (a) had strong modeling capacity on transitively closed DAGs, but (b) did not satisfy the formal definition of transitivity bias from Definition 4. Again, SimVec is the logical choice here based on the results from Boratko et al. 2021 - it obtains perfect performance on modeling transitively closed DAGs (once given sufficient dimensionality), however can easily be shown to not satisfy Definition 4. The substantial performance gap on SimVec when using the reduced set of edges supports our conclusion. 

------------------
In particular, we do not intend these empirical results to justify a universal claim regarding all models which have or do not have transitivity bias - such a claim is already supported by the theoretical results. Rather, our intention is for these empirical results to demonstrate an existential claim that the theoretical results can be leveraged in practice.

A complete analysis of existing embedding models and the extent to which they have or do not have transitivity bias is actually rather subtle and outside the scope of this work. First, while geometric intuition suggests that it is likely that any region-based model (such as Order Embeddings or disks) would have transitivity bias in the sense of Definition 4, it ultimately depends on technical details related to the energy function. In particular, the proof for box embeddings does not trivially translate to the case of Hyperbolic Entailment Cones. Second, there are more subtle distinctions (e.g. a notion of “weak transitivity bias”, wherein the set of parameters for which the energy function can be thresholded to yield a transitively-closed DAG is sufficiently large) which would be relevant for such a detailed analysis.
I have read the rebuttal and thank the authors for their candid responses.

I maintain my positive opinion on this paper.
I thank the reviewers for their response to my review in their rebuttal. Several of their comments directly address the concerns I raised, while others acknowledge that certain points I highlighted represent potential avenues for future research. The paper presents interesting findings, and I believe the authors would benefit from further academic discussions on this research topic. In consideration of the aforementioned factors, I have determined to increase my assessment score.
Thank you for your clarifications!

> 2-a) sensitivity to $d$:
> 

While we think the sensitivity to $d$ is indeed interesting to explore, we are not sure we understand the motivation for this study. We have set $d=64$ in our experiments by analogy to the best-performing setting of Boratko et al. 2021 (cf. Figure 1, row 3 in their paper) because we expected that setting to draw the contrast between regular and hierarchy-aware sampling most sharply, reducing confounding factors such as training instability, which could easily result from too small a $d$. Meanwhile, setting $d > 64$ seemed excessive, as $d=64$ already gives enough capacity for both the models to represent the graphs perfectly.

Boratko et al. also show that setting $d=8$ (Figure 1, row 1) results in very poor performance for the SimVec baseline even with $\overline{E}$. For our experiments, we think this would obscure the salient trend of $E_{H^*}^{-}$ causing SimVec (a non-transitivity-biased baseline) to crash.

> 2-b) k=4 vs k=128
> 

We agree with your observation that $k=4$ appears to benefit more from $E_{H^*}^-$ than does $k=128$, for which the convergence curves for $\overline{E}$ and $E_{H^*}^-$ are closer together. We think this is to be expected, because the more negatives we sample from the unpruned pool $\overline{E}$, the more likely it is that we draw “high-signal” negative edges, i.e., the $E_{H^*}^-$ edges which we explicitly filter for using FINDMINDISTINGUISHER. Meanwhile, if we sample very few negative edges, drawing from an unpruned pool will likely result in fewer “high-signal” negative samples per positive example, and will take longer to converge. This trend actually makes our approach more attractive for larger graphs, where the distribution of $\overline{E}$ makes it unlikely to sample many high-signal edges using a small negative ratio $k$.

> 2-c) Balanced tree vs nCRP
> 

Thank you for clarifying this interesting observation. We would like to refer the reviewer to [Figure 4 in the appendix of Boratko et al. 2021](https://proceedings.neurips.cc/paper_files/paper/2021/file/88d25099b103efd638163ecb40a55589-Supplemental.pdf) for a visualization of a Balanced Tree vs an nCRP graph. We note that Balanced Tree graph is characteristically less random than the nCRP graph. Therefore we hypothesize that the reduced set of negatives $E_{H^*}^-$ is more uniformly informative for the Balanced Tree graphs than for the remaining nCRP graphs, and the change from $\alpha=100$ to $\alpha=500$ for the nCRP might not actually be a trend inverse to the observed Balanced Tree trend.
Thank you for your effort on the rebuttal.

While I think that motivation for the first part is well presented and the results are very sound, the second part is largely improved.

The authors may want to more explain on the motivation behind the second part in introduction, as in the similar manner as the first part. Also, as far as I understand, comparing two on transitivity bias is not enough. Is the GT-Box is the ONLY generalized model that has the transitivity bias? Is there any model that has a transitivity bias other than the family of GT-Box? Is there any other possible baseline other than sim-vec? Why you can say that the transition bias has effects on convergence only comparing two, where other factors than transitivity bias may involve?

Due to this concern, I keep my score.
Thank you for your rebuttal, some of my concerns have been correctly addressed. Could you please complete your rebuttal by answering my following questions in order to reach a final decision?

> 2-a) Their analysis also emphasize that it will be relevant to study the sensitivity w.r.t $d$ across various negative sampling strategy.

Sorry for the misunderstanding, I was essentially referring to studying the sensitivity w.r.t $d$ (d=64*2=128) in your experiments e.g $(d=64, 32..)$, with the different positive and negative sets as you did in the main paper.

2-b) Thank you for these additional experiments. Could you analyze these results e.g by comparing performances between $k=4$ and $k=128$? $E_{H^*}^-$ seems significantly less relevant in the second case than the first one.

> 2-c) Unclear analysis of results for synthetic datasets ...

From figure 7 and your descriptions, if I understand correctly, the smaller $b$ gets for balanced trees, the deeper they are and the less relevant the use of $E_{H^*}^-$ seems. Whereas for nCRP, the smaller $\alpha$, the deeper the hierarchies (in the same way as with b for trees), but the most relevant seems to be $E_{H^*}^-$. So could you explain these opposite dynamics ?
Thank you to the authors for addressing the review comments and providing additional details, including the loss formulation. I will review the rebuttal carefully and consider these details for further evaluation to determine if any changes to the score are warranted.
We thank the reviewers for their comments, questions, and feedback. Multiple reviewers found the paper well-written (ShEU, eH80) and impactful (gCXR), with clear theoretical contributions (eH80, VFTZ, gCXR) and sufficient empirical support (eH80, gCXR, TmQr).
We hope to have fully addressed questions in the individual replies to each reviewer.