Learning Representations for Hierarchies with Minimal Support
Authors: Benjamin Rozonoyer
Michael Boratko
Dhruvesh Patel
Wenlong Zhao
Shib Sankar Dasgupta
Hung Le
Andrew McCallum
Venue: NeurIPS 2024 poster (2024)
Keywords: graph embeddings
representation learning
Primary area: other
TL;DR: We provide the provably minimal set of entries from the adjacency matrix necessary to train representations for transitively-closed DAGs, provided our energy function has transitivity bias.

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%.

Learning Representations for Hierarchies with Minimal Support
Benjamin Rozonoyer'
Michael Boratko²
Dhruvesh Patel'
Wenlong Zhao'
Shib Dasgupta'
Hung Le
Andrew McCallum
University of Massachusetts Amherst
Googge DeepMind
fbrozonoyer, mrrzonoyer,dhruvesiiee dhruveshpate, wenlongzhao, ssdasgupta, hungle, mecalllm)@@e umass udass.edu mboratko@google. com
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 uniquely identify 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 symmetric graph.
In this work, we develop novel framework to identify subset of entries required to uniquely distinguish graph among all cansitively-closee DAGs. We give an explicit algorithm 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 resource-constraiie setting while reducing the set of training examples by much as 99%.
Introduction
Consider the directed graph and its associated adjacency matrix in Figure In situations where this adjacency matrix is sparse, entries, effectively assuming any pairs not in our list are zero. But what about situations where we cannot assume that have observed the full graph? For example, when obtaining annotations for edges of an unknown graph, the full adjacency matrix unknown to us and we obtain the value of any particular entry by requesting an annotation. A less obvious scenario is training model represent a given graph. From the model's perspective, every entry of this adjacency matrix is unknown, and only observed consequence of training. Therefore, is of interest determine: what is the smallest set of entries necessary to uniquely determine the graph?
store it more efficiently by keeping a list of only the positive
Root
Root
Rust
B
Al
A2
BI
B2
A
3
0
11
0
B
A.
0
Al
A3
A2
B1
AI
A2
B1
B2
A1
A2
B
B2
Figure 2: A sufficient sei of entties in the adjucency matrix uniquely distinguish graph Figure Jamong trasstively-cloee DAGs.
Figure 1:
transitively closed directed tree with brunching factor 2 and depth 2, with the associated adjacency matrix.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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, we knew it was simple graph (no self-loops) we could omit the diagonal. Similarly, for 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 O; however, the explicit characterization of these entries is not as straightforward as the preceding cases. Focusing on the case when the graph is transitively-closed directed acyclic graph (DAG), as in Figure it is easy to see that of those entries which are 1, we can omit all but the transitive reduction, i.c. the bold edges, which corresponds to omitting the -oldoold "I"s in the adjacency matrix. But what about pruning the zeros? For the graph in Figure | we can prove only 14 of the 49 entries in the adjacency matrix are needed to uniquely distinguish this graph among all transitively-closs DAGs. (See Figure 2
In this work, we first develop a general-purposs framework to identify a subset of entries required to uniquely distinguish graph among others with some arbitrary graph property (Section B.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. and proving that box embeddings, a common graph representation model, have a transitivity bias (Section 4.3). We then combine these facts into formal negative sampling procedure (Section [ and demonstrate that box embeddings do benefit from training on this reduced set of entries (Section 6) For related work in graph theory and representation learning, refer the reader to Appendix A
2 Background
We use the shorthand [m]] == (1,...,,, nn.. A semicolon separates the main arguments of a function from parameters which are typically held constant (e.g., f(z; μ, .v25 omit these secondary parameters when their values are clear from context. We represent a graph G= (V, E') by its adjacency matrix Ag E 1J where (Ac)u, = 1 if and only if (u-vo) E E. When it is clear from context, we omit the subscript and simply write A. We use arrows to represent edges: black (a-+5) denotes a positive edge in E, and red (a-+b) negative edge in the edge complement E (see below).
-1_e - 100e-((=0)) 1(=="))). We may
2.1 Directed Graphs (Digraphs)
All graphs G (V, E) in this work will be finite simple directed graphs (digraphs), where the edges are subset of the complement of the diagonal, i.e. with diag(V) == ((v-w)) | E V), we have E C V2 \ diag(V) =: offdiag(1V) (V) Given a simple digraph G = (V, E), the complement of G is G (V, E) where E == offdiag(V (V) \ E. The transitive closure of G is G = (V, E*a) where (u. E Ete if and only if there exists a directed path from u to v in G. A transitive reduction of digraph G is a digraph G' on V with the fewest number of edges such that (G') = G Note that a transitive reduction need not be subgraph of G, and in general is not unique. If G is acyelic, however, there is a unique transitive reduction, and it is also subgraph of G' [Aho al. 1972.. In this case we denote the transitive reduction G E*r.
2.2 Node Embeddings for Capturing Graph Structure
Given the task of modeling entities V that have a known graph-theoretic structure G = (V, F)). a common approach is to learn node embedding 0 V + Z which maps node ++ O(v) in embedding space Z. The graph structure is extracted from these geometric representations via an energy function E V x V + I2 which factors through 0, i.e. there exists dissimilarity function h: x Z - R200 such that Eg (u, v) = E(u, 0; 0) = (w), v), 0(v)). For example, for undirected graphs it is common to use Z R D and Fo v) = [0(n) - (v))]. This energy is interpreted as
embedding A simple digraph is one without multiple edges or self- i.e. the adjacency matrix contains only Os and 1s, with Os on the diagonal. We ignore self- in the graph modeled by the learned representations.
1 Our code and data are available at http:///////gtttaao.c/////////// weaeetttiiiiiirree-eeeee graph-embedding

---

the unnormalized negative log probability of edge existence. We seek to minimize the energy for positive edges (u-+e) by learning representations for which there exists some (global) threshold T such that Aue = if and only if E. Eo(u, v) T.
One reason 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 form
Cran O0; G) =
Σ (M-D)EE
(B),
Σ
(Bo(u,
(u-te)EE
where E and E referred the positive and negalive loss functions, respectively, and the pairs in E' and E are referred to positive and negative edges accordingly.
The loss function Liul has [V[VV] 1) terms, and thus is often too computationally demanding to use for training. For digraphs which are sparse, common workaround is to define a noise probability density function (pdf) pr and design loss function Laoise which replaces the sum over negative edges with expectation with respect to pn- In practice, Monte Carlo sampling is used to calculate a loss Ssampeed which approximates Lnoise-
3 Distinguishing Digraphs via Sidigraphs
We aim to define a new loss function with only a subset of the terms in Lru (which currently include all entries of the adjacency matrix Ac). while having the same minimizer. Thus, we first attempt to determine the minimal number of entries in Ag which would uniquely distinguish G among all those with a given property. To this end, we a digraph where edges have labels + or as a formalism for making explicit the disjoint set of "positive" and "negative" edges required 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.
the notion of signed digraph (a.k.a. "sidigraph")
This framework will allow us to identify the minimal set of entries in the adjacency matrix necessary uniquely distinguish digraph among all those with given property. We apply this framework to transitively-closse 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.
3.1 Preliminary Definitions
While the depiction of the partial adjacency matrix in Figure 2 is clear, in order to formalize this need notion of 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 digraph G (V, E) define the equivalent sidigraph G E,,
This equivalence defines a bijection between digraphs and sidigraphs with |V[(V| - 1) edges. See Figure 3 for depiction of an equivalent sidigraph of the digraph in Figure [
Let H and G be two sidigraphs with the same vertex set V. We say that H is a sub-sidigraph of G, denoted by H C G, if E C E and Ej C Eg. Given some digraph G, identifying a subset of entries in Ag is equivalent to specifying a sidigiag G For this reason, we introduce the following terminology.
Definition 2. We say that sidigraph H is potential distinguisher of a digraph Gf H C G+. Given a sidigraph H. we define the set of digraphs that could potentially be distinguished by H to be GD = [G | G=).
That is, GT contains every digraph G such that H is potential distinguisher. Another way to interpret Gnr that the edge set of every graph G E Gir contains positive edges and no negative edges of H. More formally: GH {Gl VG VH. E C Ec, En O Eg 0).
3

---

Root
B
A1
A2
BI
B2
Root
BI
B2
Root
A1
A2
Root
1
Rool
Roat
0
0
1
0
A
A
+
4
A1
0
0
0
0
0
A1
A1
A2
0
A2
A2
0
0
B1
B1
B2
0
0
0
0
D
D
B2
B2
(a) Adjacency matrix for G
(b) Equivalent sidigraph C#
(c) Minimal sidigraph H
Figure 3: An adjacency mairis (a) and a represeniation the edges in the associated sidigraahh (b), where + in pusition (6, indicates
((++) E E and indicates (i-+) E E . The minimal sidigraph (c) formally cuptures the fact that Figure 2 has the minimal set of entries the adjacency matrix uniquely distinguish among all transitively-cles DAGK
Definition 3. Given some property, we let P be set of all digraphs (on given set of nodes) with this property. We say the sidigraph H distinguishes particular digraph G among all those with the given property if GH n (G}.
3.2 Distinguishing Transitively-Closed Digraphs
In this work, we focus on the case where P contains all transitively-cloeed 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 2(V(() edges; however any transitive reduction G' = (V, EE') often has substantially fewer edges Furthermore, by definition, G the only transitively-closed digraph which contains the edges E'. As consequence, if we let H (V, E', E) we have Gn n {G), which proves the following result.
Proposition 1. Lel = (V, E) be a transitively-closed digraph, and G' = FV, a transitive reduction. Then H EV, distinguishes G among transitively-close digraphs.
The edge complement E might also have 1([V(²) edges, which we would like to reduce while maintaining distinguishability. To see why this should be possible, consider Figure
If (a-+)- E and (a-xd) & then (b+d) & E, since it were we would need to include (a-xd) due to transitivity. Similarly, if (c-xd) E E and (a-x) & E then (a->c) E, since, if it were, transitivity would imply (a-r)- E E. We formalize this the following proposition.
Proposition 2.
Let G EV be which distinguishes G among transifively-closed digraphs. If (a->d) E Fig then
measittivelycllosee digraph: H (V, EH) a sidigraph
(f(a-b) E E, H' = (V, E Ey ((b->(())))))))))))))))(((())( distinguishes G among transitively-closed digraphs. (f(c-d) E H' (V, E Fi \((a->))) distinguishes G among transitively-closed digraphs.
Proof. Recall that H distinguishing G among transitively-closedd digraphs means that NP (G), ie. G (V, E) is the only vransiivell-elosse digraph for which E C E and Ey E 0. Now, note that G" (V, (E+) is the smallest transitively-closed digraph containing the edges Et. and thus G' C G. But this implies E (E EE O E 0, and thus G" G.
Now we prove the proposition hand. We prove the first case, the second follows similarly. Let (a-+) E Ejg. assume (a-bb) E E, and define H' = (V, E Ej {(b-d))). Note that H' C H. and hence 5H C GH
Now suppose K = EK) E GHr P, which implies K is transitively-closed digraph with EØ C Eg and (E₁, \ ((b-d)) n Ex = 0. In particular, as a consequence our observation in the first paragraph, this means (a-+b E Ex. We prove (b-x) $ Ex by contradiction, for if (b-d) E Ex, then since K is transitively-closed we would have (a-d) E Ex which violates our preliminary assumption.
'A canonical example is the transitive closure of a directed path of length where | = (n 1)(n 2). but E = - 1.

---

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.
Algorithm 1 FINNMMINDISTIINNUIIRER
Require: C= EV transitively-closed DAG
I: E" E
@
2: for (a-+d) do
3: for (a-+b) do
4: E= <- ((b-+d)}
5:
end for
b
6:
for (c-xd) do
7:
E F² \ ((a-bc))
Figure Negative edges removable according to Proposition
8:
end for
9:
end for
10: return H' =V, (V,E",E"
3.3 Optimality of FINDMINDISTINGUSHHER
We note that H with cycles it is not possible to uniquely define such 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-closer digraphs, but moreover it is the sidigraph with the minimum number of edges capable of doing so! Below a proof sketch for the informal statement, For the full proof refer to Theorem |
is only defined for DAGs, and indeed for graphs
Appendix B
Proof sketch: The basic idea is to define partially ordered set, a.k.a. poset, 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.
4 Leveraging Sufficient Sidigraphs for Training Node Embeddings
We would like to leverage 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 inductive bias which only permits models capable of representing digraphs in P we should be able to train using only the positive and negatíve edges from any H which can distinguish G among those in P. In some instances, depending on the proportion [] [ E I/[IVI(VV | - 1)}, this may allow full training digraphs which would otherwise require sampling. As show, sampling
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 Csampled (0) will better approximate (o))
4.1 Transitivity Bias
First, we formally define "transitivity bias".
Definition 4. Let Z be an embedding space. We say that an energy function Fg has transitivity bias if, for all embeddings : V - Z, there exists some threshold 2 s.t. for all u, u. w E V, the inequalities (u, v), (v, w) T'' imply Eu(u, w) S T.
We illustrate transitivity bias using the following overly simple embedding model.
((a)-0()) Example 1 (Bit Vectors). Let Z {0, 131V and EBV (u, v; log (()) Then EBv, has a transitivity bias using threshold T = 0, as Eav(u, o; 0) = 0 if and only if Vi E V. ((v); 0(v); = = 0(u), = 1, hence Egv(u, w; 0) = O.
8uu) Thus, if Egv(u, vy 0) EBv(U, w; we have (ww), =1 =
For a given digraph G (V, F.,, we define the bit vector representation of G as Ogy V - (0, 111M where the 4th (for i E V) coordinate is given by
5

---

(ny(u); {
if i equals e or is descendant of v;
otherwise.
Proposition 3. Let G (V, E) be any digraph, then (u u; 0Bv) = if and only if (u, v) E E
Proof. Let (u, v) E E" then there is some path u = + W2 - Wn-1 + = in E. By the definition of gy: we have that (ny(w;; wi+1: (v) = for E [n]] and thus by the transitivity bias observation made in Example ] this implies Egv (u, o; (gv) 0.
Now assume (u, v) & E then is not descendant of which means (v) 0 while gg and hence (nv(u, v; (v) > 0.
With an appropriate threshold, any energy function that has transitivity bias in fact represents transitively-closse digraph:
Proposition 4. If Eg is energy function with transitivity bias, then for any 0 there exists T > such that the digraph with edges {(u, v) Eo(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 Let be a cransitivelyccooee digraph, Eg an energy function with transitivity bias, and H = (V, E Eg) a sidigraph which distinguishes G among transitively closed digraphs. IfT is the threshold associated with the transitivity bias for 0, Es v) S T for all (u, E Egg and Eg (u, v) > T for all (u, v) E Eg then 0 represents the digraph G.
4.2 Box Embeddings and T-Box
We would like energy function to be representation which is tractable and trainable via gradient- descent, which requires the space Z to have differentiable structure. Box embeddings [Vilnis et al. 2018 are 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 will use for experiments.
As introduced in Vilnis al. [2018), box embeddings represent entities using box or hyperrectangle in IR i.e., Cartesian product of intervals
D
I& =2 = [rt, xi] x x... x [rD. Tp C CRD,
d=1
where x < J. for d E [D]. Vilnis et al. [2018) proposed modeling directed graph such that boxes of parents contain their children with energy function
E (u, 0) = - log II
Fo (Oox) O(v)a),
d=1
where the per-dimension parameters endpoints of interval, i.e. 0(u)a [0(u)]. 0(u)2l+ and the per-dimension score defined as
[x 1 [v++v"]] max(min(x* y²) max( , ).0)
FBox((x* ), (yt, yy ))
[[y+.'
max(y" -0
Previous works have highlighted the difficulty optimizing an objective including these hard min and max functions et al. [2019] Dasgupta et al. 22200] We 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 smooth approximation (x),(() Iogg(; (.))). The per-dimension score function is then given by
Box FGT Box ((x* _=),,)),)))))) (vt, )):,))) LSSE (x:
(x* "aae",.)),00 .1)),
LSE,, (y y-,0)
which approximates Foox for sufficiently small r, 0. These T, are additional (global) trainable parameters of the model.

---

4.3 Transitivity Bias of Box Embeddings
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 T appear.
it actually is more similar than it may first
Remark 1. As observed in Boratko et al. [2021b], the box intersection volume calculation can actually be viewed as the L inner-product of characteristic functions boxes, in which case takes an identical form to the energy function for bit vectors. For any functions f. E L (R P). the standard inner product is (f.g) fg- {x))g(x) dr. Now, for any box B C R we let 1 L (xx) be the characteristic function, which is when B and O otherwise. Then the volume of intersection of boxes is
Vol(A B) (1a(2), (z)))
which is also valid if A = B. Thus, we can write the energy function
(Lo(u)) Io(w)) (Io(e), Io(s))
F (u, v; llg
Box embeddings can be quantized into bit vectors 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 Ta be the endpoints of boxes in dimensions d, i.e. Ta == Usev ( (0(v) ((v) 2 ). Let Ma == [Tal, and assign indices Ta =: (ld.m m= such that Then, for each v E V and d E [D]. form the Ma-dimensional vector ((0)d.m = FBOx (0(v)a, (ta.m, 1-)m By construction, this value will be either 0 or 1. Letting ((v) E {0, (0, M2 be the concatenation of {ęp(u)a)==>> we obtain a bit vector representation, p(u)-p(()
Remark 2.
d. S 1d,m+1 for E Ma
for which the energy function E(u, i; (p) = log ((v)-p(w) is such that E(u, u; up) 0 if and only if pp(ud, = which is true if and only if [0(e)) (())t) S [0(4)
<p(v)a.m =1
Most importantly for our purposes, however, is the following proposition.
Proposition 6. The energy function EBox,0 has transitivity bias.
Apart from prior empirical observations that box embeddings work well to embed transitively-closs DAGs Boratko et al. [221aa), Proposition PropositionnSsuugesst should be possible to train box embeddings to represent a transitively- cloosed DAG. In practice, we
on the output of FINDMINDISTINGUISHH train the smooth approximation provided by GT-Box. As T, - 0+, which often happens naturally during training Booaako et al.] aQ we expect it to capture the transitivity even when trained only on the positive and negative edges of the distinguisher provided by the algorithm.
5 Hierarchy-Aware Sampling
In this section formally how we sample edges for loss function, which we term hierarchy-aware sampling. Based on the results in the preceding section, given transitively-close digraph G, if Eg has a transitive bias and the sidigraph = (V, E E can distinguish G among transitively-closed digraphs, then we can train using the following loss function:
Liu Co H)
Σ (Eo(u,)))
Σ (Eo(u, v)).
(u-t)EE
(u-u)EE
In particular, for a transitively-closed DAG G, use H* as returned by Algorithm !
If the cardinality of H' small enough, this may make training using Lha feasible. In gen- eral, 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, which means positives will be sampled from either E or E and negatives will be sampled from E or Ejg.. Even with our reduced set of negatives, there are still far more negatives than positives, and so we adopt the common practice of sampling & negatives for every positive within a batch.
FINDMINDISTINGUUSIEERR
7

---

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 [ we hypothesize that the greatly reduced edge set in hierarchy aware sampling will be sufficient 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. [202Ta] demonstrated superior performance using GT-BoX and random uniform negative sampling: balanced trees, where is the branching factor, the nested Chinese restau- rant process (nCRP) Blei et al., 2010). where is the normalized "new table" probability, and Price's model [rice 1976]. where m is the number of connections for a new node and c is a constant factor added to the probability of vertex receiving edge [ We also test the larger real-world Medical Subject Headings (MeSH) taxonomy Lipscomb [2000), 2020 release. For de- tailed statisties about all graphs refer the reader to Table Appendix
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, ESIM Vec (u. v) == (m)) 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 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, Appendix
- (log((((((())))))
Support and Sampling. For the synthetic graphs we iterate over settings relating the support sets from which uniformly randomly sample positive and negative training edges, respectively:
Sampling positive edges from the transitive reduction E transitive closure E
Sampling negative edges from minimal hicrarchy-awarr set EØr- vs edge complement E. Negative sampling ratio vs = 128 (i.e. per each positive edge seen by the model, 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, limitation which we expect when scaling to larger graphs, such McSH.
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 Fl between the edges of the transitively-close 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 nol interested the best Fl score attainable by these models, but the effect of respective support compare across experimental settings, we plot F1 as a function of the number total examples (both positive and negative edges) processed by the model (e.g. Figure(o). To measure the final performance and rate of convergence, we use the area under the Fl vs. Total Examples curve (AUFIC).
on convergence. To
6.1 Results and Discussion
First note that GT-BOX universally outperforms SIM- VEC the graph modeling experiments. This 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 hierarchy's 's structure on the convergence for the various sampling settings for GT-BoX specifically. With this aim, in Figure 5) we present the AUFIC 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 a reasonable amount of time, whereas, to the contrary, it is possible get through all of Egy- in limited number of epochs, since in many cases the sampling pool is reduced by more than 99% (cf. Table
'Preferential attachment exponent 1.0 throughout.
8

---

Model
Training Edges
Graph Type
RCRP a
10-
Pos.
Neg.
nCRP
Price
0.568
0.796
0,582
GT-Box
0.658
0.775
0.602
1E" Epr1
0.842
0.904
0.849
0.744
0.877
0.909
0.072
0.084
0.158
SIM-VEC
0.180
0.285
0.336
0.098
0,158
0.300
011
0.508
0.409
0.494
Tobal
120
Figure Convergence measured using AUFIC on three graph types for SIM- VEC and GT--Box models with the full reduced set of positive und negative edges provided during training. respectively. Pos. fresp. implies usage of transtive closure (resp. transirive reduction). Analogously, for Neg,, symbols imply usage the the edge complement E and E H- respectively.
Figure 6: While GT-BoX (black squares) with transitivity bins takes full advantage of the hicrarchy-wware E SIM-VIC which does not have a transitivity bias, falls apart under this nogative sampling procedure. The reduction in negative examples from using the pruned negative edges for this particular graph is 95.83%. Negutive ratio throughout.
(2.3
63
08
0.
1.4
32
29.62
08
V. 0.1
10.m-1
DMta's Neroort. 0.1. m-1
Piyoli Www.lc.ieeeet.cco D.1. Ltw.eee----eeaae fum-
1.4
Figure 7: The plots show convergence of GT -TX- for negutive ratio = 4. The now shows the plots for bulanced trees with branching gmaphs with 10, 100, respectively going right. bottom shows the plats for Priec's graph with 0.1. 1.0 and three values of 5, and 10. The number of vertices in each graph is es gis
middle
Figure demonstrates striking trend observed consistently our experiments. While GT-Box with our reduced edge set performs par or better than with the original edge set, in contrast, the performance SIM-VEL degrades significantly. We demonstrate this using a representative example in Figure where, in stark contrast to GT-BoX taking advantage of E and outperforming all SIM-VEC settings, both STM- VEC settings that use Ej fail to converge even to 0.4 F1. This dichotomy hearkens back Proposition 5 which underlines the non-trivial synergy between an energy function with transitivity bias and the hierarchy-awee output of FINDMINDISTIINUUSSEER.

---

Balanced tree. Figure Row visualizes the impact convergence of increasing the branching factor. As branching factor b increases becomes more and more shallow. While Ez. performs well on all values of 6, it particularly stands apart from E in the b 10 setting.
10, we first note that the balanced tree with fixed V
nCRP. a is the normalized "new table" probability, with smaller a implying more separate clusters with deeper hierarchy, and larger implying fewer clusters and more shallow hierarchy. The relative improvement of using F-- is more significant for smaller a.
Price. Price's model is learnable by GT-Box especially quickly under any setting, evidenced by the very high AUFIC scores in Figure [] Higher has the effect making edge attachment more uniformly distributed among nodes. In Figure 11 Row 3 examine convergence values for 0.1, noting that E typically underperforms E but catches up in the limit. As m (out-degree of newly added vertices) increases < 5 < 10, looking at Table [ 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 Σzg. within GT-BoX outperforms sampling from the edge complement, while being a 99.78% reduction. Meanwhile, Ex with SIM-V VEC plummets, consistently with the trend exhibited in Figure 6 This encouraging result on graph with z 2 nodes points not only to the economy of our approach, but the stability and improved performance on large real-world data.
7 Limitations
While the connection between hierarchies and transitivity bias allows to capitalize on it in the form of hierarchy-awar aware sampling, we ac- knowledge that the properties demanded 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 a goal future work.
MeSH k-24,
01 BuA, Ki:
GaiVer. Fj
Another limitation is the extent to which this sort of method would break down for graphs which are, strictly speaking, not transitively-closee but close (in edit distance) to being transitively- closed. Strictly speaking, our proofs do not ap- ply in that setting, and the efficacy of the ap- proach may vary depending on the type of struc- tural changes a particular removal an edge brings about.
15tal Exarppics
105
Figure Convergence of GT-BoX SIM-VEC for Eys M&SH 2020. The minimal nogative edge set Ey converges to the Box,
apart combined with SIM-VDC, consistently with hypothesis about the roquirement transitivity bias for utilizing Eg=.
highest when coupled
8 Conclusion
In this work, we propose a novel framework for identifying sufficient subset of entities in the adjacency matrix which unambiguously specify digraph, given some prior structural knowledge. We demonstrate the usability of this framework for the property of transitively-cloot hierarchies. We derive characterization of the sufficient negative set for such type of graphs, and based on that we devise 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.
DAGs, or
10

---

Acknowledgements
This work was supported in part by IBM Research Al through the Al Horizons Network, the Chan Zuckerberg initiative under the project Scientific Knowledge Base Construction, and National Science Foundation (NSF) grant number 1922992.. Hung Le was supported by an NSF CAREER Award No. CCF-223728, an NSF Small Grant No. CCF-2121952, and Google Research Scholar Award.
References
Alfred V. Aho, Michael R Garey, and Jeffrey D. Ullman. The transitive reduction of directed graph. SIAM Journal on Computing, 1(2:1311-37, 1972.
Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures, ACL, 2018.
Michael Boratko, Dongxu Zhang, Nicholas Monath, Luke Vilnis, Kenneth Clarkson, and Andrew McCallum. Capacity and bias of learned geometric embeddings for directed graphs. NeurIPS, 2021a.
Dongxu Zhang, Michael Boratko, Cameron Musco, and Andrew McCallum. Modeling transitivity and cyclicity in directed graphs via binary code box embeddings. Advances in Neural Information Processing Systems, 35: 15:87-9911,599 2022.
Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smoothing the geometry of probabilistic box embeddings. ICLR, 2019.
Shib Sankar Dasgupta, Michael Boratko, Dongxu Zhang, Luke Vilnis, Xiang Li, and Andrew McCallum. Improving local identifiability in probabilistic box embed- dings. NeurlPS, 2020. URL 2ic5266B8f666bb344cc995/66666633 Absttrrr .html
neurips wwwturps.cc/aaaaee ww/ppppee/02///aaaeeeeeee
Michael Boratko, Javier Burroni, Shib Sankar Dasgupta, and Andrew McCallum. Min/max stability and box distributions. UAI, pages 2146-2155, 2021b.
David M Blei, Thomas Griffiths, and Michael I Jordan. The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies. Journal of the ACM (JACM), 57(2):1-30, 2010.
Derek de Solla Price. A general theory of bibliometric and other cumulative advantage processes.
Journal of the American society for Information science, 27(5):292-306, 1976.
Carolyn E Lipscomb. Medical subject headings (mesh). Bulletin of the Medical Library Association, 88(3):265, 2000.
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Understanding Negative Sampling in Graph Representation Learning. In Proceedings of the 26th ACM SIGKDD In- ternational Conference on Knowledge Discovery & Data Mining, KDD 20, pages 1666-1676, New York, NY, USA, August 2020. Association for Computing Machinery, ISBN 978- 45503-9945--9 URL batttss://doi ott/ 11111111131344 3403218
doi: 10. N0.1145/3394486.4443333
Michael U. Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications natural image statistics. The Journal of Machine Learning Research, 13(mull::07-36.. February 2012. ISSN 1532-4435.
Andriy Mnih and Yee Whye Teh. A fast and simple algorithm for training neural probabilistic language models, 2012.
Tomas Mikolov, llya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL http:ttt////rroeeiiigs www.riinnn......neeeeeeeeeeeeeee cc/paper_
fi fiieeh/eerrraaaa1/1a222222222222
pdf

---

Hidetaka Kamigaito and Katsuhiko Hayashi. Comprehensive Analysis of Negative Sampling in
Knowledge Graph Representation Learning, July 2022. httpp:////axxii
10140 arXiv:2206. 10140 [cs].
Yu Wang, Liang Hu, Wanfu Gao, Xiaofeng Cao, and Yi Chang. AdaNS: Adaptive negative sampling for unsupervised graph representation learning. Pattern Recognition, 136:109266, April 2023.
ISSN 0031-3203. doi: http:////...ccog..000
utt/https:/ //tp::://www... www.sscciieeeeeec.....
Kian Ahrabian, Aarash Feizi, Yasmin Salehi, William L. Hamilton, and Avishek Joey Bose. Structure Aware Negative Sampling in Knowledge Graphs, October 2020. URL http:///a///iittttttttt wrwpaii.orrgaaaaa 2009. 11355 arXiv:2009.1 1135 [cs, stat].
Junyang Chen, Zhiguo Gong, Wei Wang, and Weiwen Liu. HNS: Hierarchical negative sampling for network representation learning. Information Sciences, 542:343-33555 January 2021. ISSN (022--
0255, doi: 10. 10.00..0 URL
com/ con/science.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. DeepWalk: Online Learning of Social Repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, August 2014, doi: 10. 10.114552223330.222372.. URL
httt:///rxivv wwarxivv.or//iee 1403. 6652
arXiv:1403 1003.46666222 [cs].
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating Embeddings for Modeling Multi-relational Data. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://:/// nips Abstract. html
Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning Entity and Relation Embeddings for Knowledge Graph Completion. Proceedings of the AAAI Conference on Artificial Intelligence. 29)1), February 2015, ISSN 2374-3468, 5399, doi: 10. 11t.9//aii.229....000. URL httph:tt////t //jss aaai org wwdgiinex...g// php/ http/////aaatieeeeeeeeee
Maximilian Nickel, Volker Tresp, Peter Kriegel, et al. A three-way model for collective learning multi-relational data. In Icml, volume 11, pages 3 1144422-1104555 3104584, 2011.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding Entities and Relations for Learning and Inference in Knowledge Bases, August 2015. [attp:////axx
org/abs//l 1412. 6575 arXiv:1412.6575 [es].
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex
Embeddings for Simple Link Prediction. 2016. doi: 10.48550/ARXXV..66666 Publisher: arXiv Version Number: 1.
URL https
06357
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Yun Nie, and Jian Tang. RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space, February 2019a. itt/tttp://axxivorrr abt////s///10// 10197
1.Xi::1902.10199 10197 [cs, stat].
Tengwei Song, Jie Luo, and Lei Huang. Rot-pro: Modeling transitivity by projection in knowledge graph embedding. Advances in Neural Information Processing Systems, 34:24695-24706, 2021.
Dhruvesh Patel, Shib Sankar Dasgupta, Michael Boratko, Xiang Li, Luke Vilnis, and Andrew McCallum. Representing joint hierarchies with box embeddings. In Automated Knowledge Base Construction, 2020. URL htRhsttps:t : //wp///eeieee/eeeeeee/eeeeeeeeee met/foorumidde -fr.://ddd-2445SSRRR
Fred S Roberts. On the boxicity and cubicity of graph. Recent progress in combinatorics, 1(1): 301-310, 1969.
Hiroshi Maehara. Space graphs and sphericity. Discrete Applied Mathematics, 7(1):55 1984.
Dhruvesh Patel, Pavitra Dangati, Jay-Yoon Yoon Lee, Michael Boratko, and Andrew McCallum. Modeling label space interactions in multi-label classification using box embeddings. In International Conference on Learning Representations, 2022. URL htt.tpt:///ppeeeevieee net/ net/forummidd tyTH9kDxovh
12

---

Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-emberr reder-embeddings of images and language. ICLR, 2016.
Alice Lai and Julia Hockenmaier. Learning to predict denotational probabilities for modeling entailment. In Proceedings of the 15th Conference of the European Chupter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 721-730, 2017.
Ryota Suzuki, Ryusuke Takahama, and Shun Onoda. Hyperbolic disk embeddings for directed acyclic graphs. International Conference on Machine Learning (ICML), 2019.
R. Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. Graph Drawing, 2011.
Melanie Weber and Maximilian Nickel. Curvature and representation learning: Identifying embedding spaces for relational data. NeurlPS Relational Representution Learning, 2018
Melanie Weber. Neighborhood growth determines geometric priors for relational representation learning. Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgenly Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 2015.
Mare Law, Renjie Liao, Jake Snell, and Richard Zemel. Lorentzian distance learning for hyperbolic representations. International Conference on Machine Learning (ICML), 2019.
Octavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic Entailment Cones for Learning Hierarchical Embeddings, June 2018. Utt.tttt://aarii http:ttp:..aar.i..orrr/aa/////// 1804. 01882 arXiv:1804.00 0180001882...0000 [cs, stat].
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: Large- scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web, pages 1067-1077. May 2015. doi: 10.11452733227:2744193. URL http://arxiv.oo orgo abs/aass//10/ 03578 arXiv:1503.03578 [cs].
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. Pruceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1105-1114, 2016.
Jiankai Sun, Bortik Bandyopadhyay, Armin Bashizade, Jiongqian Liang, P Sadayappan, and Srini- vasan Parthasarathy. Atp: Directed graph embedding with asymmetric transitivity preservation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 265-272, 201 9b.
Aaron Sim, Maciej Wiatrak, Angus Brayne, Páidí Creed, and Sace Paliwal. Directed graph embeddings in preeaniniemanniin manifolds. In International Conference on Machine Learning. pages 9681-9699 PMLR, 2021.
Thomas Kipf and Max Welling Semi- supervipe classification with graph convolutional networks. 2016.
arXiv preprint
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in neural information processing systems, 33: 19314-19326, 2020.
Chao Liu, Xinchuan Li, Dongyang Zhao, Shaolong Guo, Xiaojun Kang, Lijun Dong, and Hong Yao. A-gun: Anchors-awand graph neural networks for node embedding. In Quality, Reliability, Security and Robustness in Heterogeneous Systems: 15th EAI International Conference, @Shine 2019, Shenchen, China, November 22-23, 2019, Proceedings, pages 141-153. Springer, 2020.
Zemin Liu, Trung- Kien Nguyen, and Yuan Fang. Tail-gnn: Tail-node graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, pages 1109-1119, 2021.
13

---

Michat Adamaszek. Note: The smallest nonevasive graph property. Discussiones Mathematicae Graph Theory, 34(4))857-862, 2014.
Aleksander Kelenc, Niko Tratnik, and Ismael G Yero. Uniquely identifying the edges of a graph: the edge metric dimension. Discrete Applied Mathematics, 251:204-220, 2018.
Yisu Peng, Yuxiang Jiang, and Predrag Radivojac. Enumerating consistent sub- sub-graphs of directed acyclic graphs: an insight into biomedical ontologies. Bioinformatics, 34(13):1313-s3) 2018.
Lukas Biewald et al. Experiment tracking with weights and biases. Software available from wandb. com, 2:233, 2020.
14

---

A Related Work
A.1 Negative Sampling for Graph Representation Learning
Yang et al. 2020 conceptually unify much of the research on negative sampling (NS) for graph rep-
resentation learning (GRL) into the SampledNCH framework which is grounded in noise-contrastive estimation [Gutmann and Hyvärinen 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 positíve sampling distribution, i.e. pa (u v) x pa(u w)*, . < a < I,
which supports the empirically-deterne determiind 3/4 in Mikolov al. [2013] 's degree-based sampling.
Examples of better-than--ee than- uniaorm 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) Waang et al. 2023]. A handful of approaches leverage the graph structure directly gather negative examples; in particular, Structure Aware NS (also abbreviated SANS) of Ahrabian et al. [020] selects negatives from a node's k-hop neighborhood. Hierarchical Negative HANS algorithm in nomenclature, relying on 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
Sampling (HNS) [Chen et al.) 2021] is only close
current vertex.
We emphasize that each of these above approaches presupposes undirected graphs and vector embed-
dings of nodes, aligning them with the vast literature on KG embeddings including TransE [Bordes] eet al. 2.13]. TransR [Lin et al. 2015]. RESCAL [Nickel et al. [011]. DistMult (Yang et al. [013]]
ComplEx [TTrouillon et al., 2016). RotatE [Sun et al., (201 and Rot-Pro [Song et al. 2021 (the last
of which models transitive relations via projection operator).
A.2 Hierarchical Representations
Box embeddings can represent any DAG [Boratko et al., 2021a], and more recently have been ex- tended to represent any digraph (Zhang et al. [002]]. Empirically, box embeddings have demonstrated particularly strong performance on transitively-closst
graphs, making them a strong candidate for modeling hierarchies (Patel et al. [020). The use of regions to capture edges in graph has roots in classic graph invariants of boxicity [Roberts) [969] and sphericity [Maehara 1984), which are defined in the undirected setting. In general, one might expect region-based embeddings to have natural bias toward modeling transitivity, as the containment relation is transitive [Patel et al. 20222.
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.) 20199. The highlight of these methods is their ability to represent trees, but they are not necessarily well-alignel with representing transitively-closs digraphs [Boratko et al. 2021a]. Hyperbolic entailment cones [Ganea et al., [2018) combine the benefits of both hyperbolic space and region-based containment transitivity.
A.3 Learning Node Embeddings
The idea of optimizing a loss which is 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 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., 2013 was the first attempt address the scalability of learning node embeddings for scale graphs. Meanwhile, some works focus on learning node embeddings for directed graphs [Ou et al. [016 [Sn et al., 2019b] [Smm et al. [02T]. 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 sufficient sidigraph to reduce the set of edges and non-edges could be leveraged in such contexts as well.
15

---

A.4 Uniquely Distinguishing Graphs
The idea of uniquely distinguishing graph with respect property has been explored in graph theory literature, albeit without special focus on DAGs as in the current work. For property P on n-vertex graphs, Adamaszek [2014) defines P to be "nonevasive" (or "nonelusive") in the context of 2-player game where for each turn, player A is only allowed to ask player B whether pair of nodes forms an edge or not. P is nonevasive if can be determined by A in strictly fewer than (3) turns, Le. by asking fewer questions than edges in complete graph over vertices (it follows that completeness an evasive property). Kelenc et al. 2018 spotlight minimal uniquely distinguishing graphs by introducing the concept of an edge metric dimension the smallest cardinality of set S such that every pair of edges in G is distinguished (w.r.t. node-edge distance) by some vertex in 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.
16

---

B Proof of Optimality
For notational convenience, for each vertex a E G, we add a directed self-loop (a-+a) to indicate that a is reachable from itself. This self-loop will be positive edge in G Adding this self-loop does not destroy the property that is transitively closed.
B.1 A poset for negative edges
We define order < between negative edges as follows.
For every negative edge (a-+b), impose (a-+b) (a-+b). Thus, I is reflexive. Next, define an order between two negative edges outgoing from or incoming to the same vertex. Let be an arbitrary vertex in V. Let (a-+b) and (a-te) be two negative edges out- out-going from Then
we define (a->b N cc) if (c-+b) is a positive edge in G# (in other words, if (c-+b) E E). We call the edge pair ((a->)) (a (a-be) primitive pair. See Figure La). Similarly, let (x~+a) and (y-b) be any two negative edges incoming to a. We define (x->a) N (y~aa if (xr - is positive edge. The edge pair (x->a) and (y-xa) is also 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 3, then we impose (a-+b) 3 (e-x)).
Et
a
E1
y
a
(b)
(a)
Figure 9: (a) Two primitive puins ((a->b), (a->e)) and ((x-+a) (v-+a)). (b) Illustrating the proot of Lemmna]
Our goal is to show that (E, is poset. To this end, we characterize all pairs of negative edges (a-+b) and (c-x) such that (a-+b) 3 (c-rd).
Lemma 1. Let (a-+b) and (c-+) be two edges such that (a-b) I (c-d)). (It could be that a and/or b- = d.) Then (a - c) and (d +bb b) are positive edges.
Proof. We prove by induction. The base cases are for primitive pairs. If (a->b) and (c-+a) are primitive pair, then either a = c or = d. In both cases, the lemma holds by definition of the order I primitive pairs.
e (c-d) be a minimal sequence of orders realizing the order (a (a-+b) 3 (c->d such that every consecutive pair of negative edges (e,, (++1) for every E [1. - a primitive pair. Specifically, (E1, e2) a primitive pair. We consider two cases: (i) E2 = (a-x) and (ii) E2 (y b)) for some vertex y. The two cases symmetric, so we only focus on the first case; see Figure (b). As (a-b) 3 (a xz), (a + b) a positive edge by the definition
Let (a-xb) = 61 62
< on primitive pairs. Since (a-z) - (c-d). by induction, (a + c) and (d + x) are positive edges. This means (d + b) is also positive edge since transitively closed. Thus, the lemma holds. O
We know that Lemma holds even when (a-+b) = (c->d) as in that case c and b = d and both self-loops (a - a) and (b + b) are positive. Now, we are ready to show that = is anti-symmetrie; the proof uses the fact that G is DAG.
Lemma 2. GfG (V, F.) is transitively-clooed DAG, then (F,, =) is poset.
Proof. The order < transitive and reflexive by definition. We now show anti-symmetric by contradiction. Suppose that (a-+b) and (x-+y) are two different negative edges such that (a-bb) =
17

---

(x-by) and (x-xy) 3 (a-+b). Since (a-+b) & (z (z~ty), either 2 & a or # y. We focus on the case # a; the proof for the case b * y the same.
Since (a-+b) N (x-+y), by Lemmal (a + x) is a positive edge. Also by Lemmal 1 as (x (x-+y) I (a-+b), have that (ar a) is also positive edge. However, this contradicts that G is DAG. L
We could reinterpret Proposition 2 in the language of the poset (E.
Corollary 1. Let G be transitively closed DAG. Let H (V. En) be sidigraph which distinguishes G among transitively-closed digraphs. Let e1, be a primitive pair of negative edges in En such that e1 3 E2. Then (V, EH EH {e2)) also distinguishes G among transitively-closed digraphs.
B.2 A proof of optimality
We have shown in Lemma that (E, 3) is poset. Let M be the set of minimal elements this poset; Figure 10 Our proof to show that Algorithm optimal has two steps: (Step 1) the negative edges M are necessary and sufficient for any sidigraph which distinguishes among transitively-closed digraphs, and (Step 2) the sidigraph H output by our algorithm has F = M
a
a
C C-+
+++0
b
C-+
b
d=
b D
Q-+
(a)
(b)
(c)
Figure An equivalent sidigraph G (b) The Hasse diagram of poset the nogative edges with artificially added co. Here 2 = ((d+aa), (b-rc), (a-dd), (c-b)) (c) minimal sidigraph (V, E", My which can distinguish G among transitively closed digraphs.
Proposition 7. G = EV, is a DAG, then H = EV, M3) can distinguish among all crasserively-closedd digraphs.
Proof. Let L be the linear ordering of all edges in E in non-decreasing order of 3. That is. if (x-v)= (a (a-b), then (a-+6 appears before (x-+y) in L. L can obtained by visiting the negative edges in the BFS order in the Hasse diagram with an artificially added maximum element oc to define the root of the BFS tree; see Figure ()).
Let X, F. and O. We then visit all negative edges by the order in L. For each negative edge visited in this order, if & M-, we define X X; \ {e} and increase by 1. Let X, be the last of negative edges after this process terminates. Clearly, X, M-.
By Proposition D (V, E" E can distinguish G. Inductively, we assume that (V, E" X,) can distinguish G for some Let be negative edge such that X,+1 X; \ fe). Since & Mz, there exists a primitive pair of negative edges e' I e. Since e' appears after e in L, both edges are present in X, By Corollary [ (V, E"h X,41) ) can distinguish G among transitively closed digraphs.
have shown by induction that (V, Eu Xt), which also (V, E" Mz), is transitively-closed distinguisher.
Next, we show that any sidigraph capable of distinguishing G among transitively-closed digraphs must contain any M- it's negative set.
Proposition 8. Let H = (V, E Et) be any sidigraph capable of distinguishing G among transitively-closed digrphs. Then M C EØ-
18

---

Proof. We prove by contraction: suppose e (c-+d) is such that (c-d) E M \ Ey. Let G' = ).)). We show below that G' In P, which then means that H cannot distinguish G from G" among transitivelyyclosed digraphs.
Note that G contains all positive edges of H since H is transitively-closed distinguisher. Thus, G' contains all positive edges of Н. Next, we show that G' does not contain any negative edge. Suppose otherwise, G' contains negative (a-+b) Lijz Since (a-+b) & E. the only way for (a-+b) E E'U {e} is because of (c-rd), and in particular, (a-+c) and (d-+b) are both positive edges G. Thus, by Lemma !
(a-+b 3 (c-+d), contradicting that (c->d) E Mz.
Finally, we show that G' is transitively-closee such that b is reachable from but (a - b) & G". Note that b is not reachable from in G since G is transitively closed. This implies: (i) the path from a to b G' must contain the edge (c->d) and (ii) (a-+b) is negative edge in G. By (i), it must be that (a-+c) and (d->b) are positive edges. By (ii) and Lemma (a->b- < (c-+d), contradicting that (c-d) E M
Suppose otherwise, there are two vertices a and
Proposition 7 and Proposition 8 together imply that any transitively dlosed-distinguisher of G with M_ contains a minimum number of negative edges. Thus, to show that our algorithm gives transitively closed distinguisher of G, suffices to show that the set of negative edges M
Theorem 1. Let G (V, E) be any DAG, and let H be the output of FINDMINDISTINGUSSERR (G), so = (V, .V,E,,,, Then H can distinguish among transitively closed digraphs, and has the minimal number of edges of any such sidigraph.
Proof. We focus on showing that Eú -Ma. The latter claim follows from Proposition and Proposition g
Observe that the algorithm considers primitive pairs and, for each pair, removes the negative edge with higher order in the poset (F, Thus, the algorithm never removes negative edge in M from H. giving that M S Exz-
It remains show that F S M2. Suppose otherwise. Then there exists negative edge (a-+b) Eū \ M2. Then by definition of M-, there must be negative edge (x-+y) such that (i) (a-+b and (x-b) make up primitive pair, and (ii) (x->y) 3 (a-+b). Then (a + b) will be removed from H when the algorithm considers (x-+y) in line 4, contradicting that (a- E En-
19

---

C Proofs for Transitivity Bias
Proposition 4. If Eg an energy function with transitivity bias, then for any 0 there exists T such that the digraph with edges {(u,v) Eo(u, v) S T) is transitively closed.
Proof. Let (u, v) E E Then there exists directed path u == w1 7 + WN v in E, hence Egg (WCn Wn++1 S T for all IN I]. Let k E [N 2],. and assume we have Fo (wr, Wk+1) S T. Since Egg (o(w+11, Wk++2 S as well, we apply the definition of transitivity bias to find (g(W1, (x+2) S T. Thus, by induction, we have Eg wx) = (u, v) S.
L
Proposition 5. Let G be a transitively-closs digraph, Eg an energy function with transitivity bias, and H (V, E EH) a sidigraph which distinguishes G among transitively closed digraphs. IfT the threshold associated with the transitivity bias for 0, Eg Eu(u, v) S ' for all (u,v) E.. and Es (u, v) T for all (u, v) E Eg. then represents the digraph G.
Proof. Let F² = {(u, v) Eo(u, v) s 7) then Proposition 4 implies that the digraph G' = (V, F*)
is transitively closed. Due to the assumptions on the values of the energy we have E C E" and F C E'. Since H is sufficient to distinguish transitively-closed digraphs, we have G' = G. as desired.
20

---

D
Results with Error Bars
Model
Training Edges
Graph Type
Pos.
Neg.
BT
nCRP
Price
0.568 0.187
0.796 0.250
0.582 0.240
GT-BoX
0.658 0.103
0.775=0.13 131
0.602#0. 147
0.842=0. 1.54
0.904# 0.058
0.849#0. 112
0.744 0.159
0.877=0.101
0.909#0.042
0.072=0.01 018
0.084+0.07
0.158+0. 172
SIM-VEC
0.180=0.065
0.285+0.1 12
0.336#0.122
0.098=0.03.
0.158=0. 172
0.300#0.218
0.508=0.039
0.409=0.023
0.494#0.151
E
Hyperparameter Tuning
The experiments were run in 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 (1IGB VRAM)
NVIDIA RTX 2080ti (IGGB VRAM)
NVIDIA Quadro RTX 8000 (48GB VRAM)
E.1 Synthetic Graphs
To ensure the competitiveness of all experimental configurations for the synthetic graphs, we tune the learning rate and negative weight Ance for each graph independently by running Bayesian hyper- parameter optimization with W&B Biewald et al. 2020) and for ES taking the values that yielded the best Fl the end of 12 epochs, which empirically observed corresponds to the "elbow" of many per-epoch Fl plots and thus gives a good indication of which settings are resulting in fast convergence. For E" we scaled the number of epochs 60, since the number training examples is substantially smaller for this setting than for transitive closure.
For each of the final experiment runs, fetch the best learning and Xney and run for full 40 epochs for E or 200 for E" recording F1 at every epoch to produce a convergence plot.
E.2
MeSH 2020
Since MeSH has at least thrice the number of nodes any of the synthetic graphs in our experiments, was infeasible to tune hyperparameters over the same settings as for the smaller synthetic graphs. We therefore fix positive edge set E (which empirically performs better than ES), as well as the resource-efficiee negative ratio = 4, and do a Bayesian hyperparameter search for learning rate negative edge (E vs Eg.).
and negative rate Xneg using W&B the cross-product of model type (SIM-Vee GT-Box) and
21

---

F
Graph Family Hyperparameters and Edge Statisties
Graph Type
θ
V
[
E"
E
B1/|E
E //
= 2
8192
90127
90127
8191
67010545
49153
0.1345%
90.91%
99.93%
= 3
8192
60620
60620
8191
67040052
86277
0.0904%
86.49
99.87%
Balanced Tree
8192
44271
44271
8191
67056401
148201
0.066%
81.5%
99.78%
10
8192
31534
31534
67069138
262765
0.047%
74.02%
99.61%
TO
10997.4 .4
40373.6
40373.6
10996.4
120893115.0
1019607.5
0.0334%
72.75%
99.16%
100
9713.8
22090.4
22090.4
9712.8
94326745,4
4035563.3
0.0234%
56.03%
95.72%
nCRP
500
9277.4
17389.5
17389.5
9276.4
86043713.3
1805777.4
0.0202%
46.66%
86.28%
22
0.01, 1.0, m
8192
8669.6
8669.6
8191.0
67092002.4
62675524.2
0.0129%
5.43%
6.58%
c 0.01, = 1.0, m =
8192
50281.7
50281.7
10294.3
67050390.3
27675479.7
0.075%
79.52%
58.72%
Price
0.01, = 1.0, m 10
8192
99878.0
99878.0
13940.9
67000794.0
22324190.0
0.1491%
86.08%
66.68%
0.1. 1.0, m
8192
13834.2
13834.2
8191.0
67086837.8 8
31970202.7
0.0206%
40.3%
52.35%
0.1, 1.0, m
8192
75013.5
75013.5
16418.3
67025658.5
6960419.4
0.1119%
78.05%
89.62%
0.1, 1.0, m
10
8192
138711.9
138711.9
23868.4
66961960.1
4171970.3
0.2072%
82.79%
93.77%
N/A Table 1: Statisties the synthetic tranitively-cleee DAGs used in our experiments (Section 6 "reduced" experimental settings. While graphs under Balanced
McSH 2020
29934
40793
274437
40156
895739985
1953539
0.0046%
85.37%
99.78%
counts for the number posirive/negative edges in the equivalent and optimal distinguishing sidigraphs, and the ratios for the "full" and deterministic, the values of each entry sCRP and Price averaged 10 random sceds.

---

G Plots for = 128
Dilenced
Diirrsed Trea D
Dalenced
02
00
Talll volle
1088 Era male
180
d-
1.2
1.6
12.2
022
0.0
F:2
67.0
05
2.0
2.
Figure The plats convergence
now shows plots balanced branching factors m 2, and 10. The middle row for nCRP graphs with 10, 100, and 500, respectively going left right. The bottom row shows the plots Price's graph 0.1, 7 1.0 three values m 10. mumber vertices graph 215,
negalive
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract makes concrete and specific claims, which are supported by the experiment section.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Section 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 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Section B and Section 4 contain propositions and proofs concerning signed digraphs and transitivity bias, and Appendix Bannd Oopendix/[providee full proofs whenever these were omitted from the main paper due to space constraints.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Section 6 and Appendix D discuss the settings of the experiments and the hyperparameter tuning process.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
25

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide a link to the code and data in footnote on the second page.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ praips.cc/ubblicgguuuee CoodeSubeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, we provide all the details pertaining to experimental settings in Section and Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report standard deviations for the numerical results Appendix D The separation between the models clear enough to not require statistical significance tests.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report the types of GPU used for our experiments in Appendix However, unable to report the exact compute hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://www..ppppp.//.///aaassaaa
Answer: [Yes]
Justification:
The work confirms with NeurlPS Code of Ethics.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification:
The necessary credits are given at appropriate places throughout the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in 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 dataset.
28

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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 the dataset/code/mooel as part 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the 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.
29


Reviews:
[{"review_id": "nCJCRzM4Kr", "reviewer": "Reviewer_ShEU", "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.", "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": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper is well written. The notations are clear and the literature review is sufficient.\n2. By formulating the disjoint subset of notes in a graph in the notion of signed digraph, the proposed FINDMINDISTINGUISHER method is able to optimally handle both acyclic graphs with minimal support.\n3. Box Embeddings is used for node embedding, so that the embeded space has a differentiable structure.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review and questions!\n\n> 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.\n> \n\nThank you for this advice. One highly related application is multi-label classification where the label space forms a taxonomy, and where we model the labels by means of region-based embeddings (cf. e.g. Patel et al. 2022). If the embedding of an instance falls within a region corresponding to some fine-grained label (e.g. a *MacBook Pro*), we would like that label to be contained under all its parent labels in the taxonomy (e.g. *< Laptop < PC < electronics < object*). In large product hierarchies, jointly training the instance embedding model together with label embeddings can be a computationally intensive task, where the label-space training can be alleviated by hierarchy-aware sampling.\n\nA broader potentially fruitful application of hierarchy-awareness is active learning with a human-in-the-loop. As we mention in the Introduction lines 20-22, “*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*”. Building up a taxonomy from open-source human knowledge (and training corresponding embeddings for fast retrieval) can require many human annotations — and as we have observed in the case of MeSH, we can obtain the minimal distinguishing sidigraph with 99% fewer edges (annotations) than in its equivalent sidigraph (cf. rightmost column of Table 1, Appendix H).\n\n> 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.\n> \n\nOnce again, we appreciate this advice and will certainly make the real-world motivations (such as the above-mentioned) more explicit in the introduction to make a stronger paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BUqUoFvWhn", "reviewer": "Reviewer_eH8o", "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.", "questions": "I invite authors to discuss and address the weaknesses/questions I have mentioned above, so that I can consider improving my score.", "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.\n\nNo potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Overall the paper is well-written.\n- Provide an algorithm to uniquely identify transitively-closed DAGs (Alg. 1) and prove its convergence.\n- Theoretically analysis the relation between the transitive bias of an energy discriminating edges and their graph reduction technique.\n- Study the transitive bias of box embeddings and their relations to bit vectors.\n- Empirical study of various negative sampling strategy supporting the relevance of the methodology proposed by authors.", "weaknesses": "*edits after rebuttal in italic* \n\n1. 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)\n\n2. Some points remain unclear to me in the experiments:\n   - 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.\n   - 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 ? \n   - 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' ?\n   - 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.\n\nsmall tipos:\n- L.208, missing word ? we formally `explain`...\n- L.37-38: misleading / big claim, as you study a very specific type of graph.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and insightful questions!\n\n> 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)\n> \n\nThank you for sharing the Rot-Pro paper. It is an interesting work on KG embeddings, much like TransE, RotatE, etc. According to our understanding, Rot-Pro is designed for the task of KG completion, where a KG is a multi-relational graph, i.e. a graph with categorical edge properties. In Rot-Pro, the transitivity is encoded primarily in the relation representation. In contrast, our work focuses on the efficiency of learning representations for directed acyclic graphs — i.e. there is only one relation. Given the success of our approach, extending it to the case of multi-relational KG completion definitely seems interesting, but it is out of scope for the current paper.\n\n> 2a) Could you further detail the architecture and optimization procedure followed in your experiments ?\n> \n\nWe describe the architecture of GT-Box in Section 4.2. For GT-Box, a node is parameterized by two $d$-dimensional corners. The GT-Box score function between two boxes gets computed as in the formula between lines 189-190, its energy function as in the formula between lines 182-183.\n\nConcerning optimization procedure, please refer to Appendix G for details on optimization procedure for Synthetic Graphs (G.1) and MeSH (G.2)\n\n> 2a) 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 ?\n> \n\nThank you for bringing up this point. We would like to note that we did not do hyperparameter tuning for learning rate and negative weight ($\\lambda_{neg}$) with highest attainable F1 as the objective. Rather, we did hyperparameter tuning with fast convergence as the objective — we achieved this heuristically by cutting off training at the end of a fixed number of epochs which we observed corresponded to the “elbow” of the convergence curve, and taking the hyperparameters that yielded the highest F1 at that point. The learning rate and $\\lambda_{neg}$ have therefore been optimized for the purposes of *fastest* convergence, and therefore may underperform on best F1, which was the metric optimized for in Boratko et al. 2021. We detail this hyperparameter optimization procedure for synthetic graphs in Appendix G.1 and for MeSH in Appendix G.2.\n\n> 2a) Their analysis also emphasize that it will be relevant to study the sensitivity w.r.t  across various negative sampling strategy, i encourage you to do so.\n> \n\nWe would be open to experimenting with other negative sampling strategies if you can suggest some particular ones. We were unable to find other relevant negative sampling strategies in Boratko et al. 2021.\n\n> b) 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 ?\n> \n\nApologies for the oversight. We are attaching a 1-page pdf of results for $k=128$ to the global response, and will include it in the appendix. Based on the plots, the advantages of hierarchy-aware negative sampling are more apparent in the low-resource $k=4$ than in the higher-resource $k=128$.\n\n> c) 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' ?\n> \n\nCan you please clarify what you mean by opposite dynamics in those two graph families? Note that since all graphs are generated with (almost) the same number of nodes $|V|$, we always have a tradeoff between depth and breadth, which might confound some conclusions.\n\n> 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.\n> \n\nWe can certainly rerun this training for longer for the camera-ready version. However, we do not think that the trend will change after more epochs.\n\n> small tipos:\n> \n\n> L.208, missing word ? we formally `explain`...\n> \n\n> L.37-38: misleading / big claim, as you study a very specific type of graph.\n> \n\nThank you — we will address these typos promptly!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f4nPfldfiG", "reviewer": "Reviewer_gCXR", "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.", "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?\n- 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)?\n- 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": "Yes, there is a section about the limitations of the work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical grounding of the paper looks good to me, with key properties of the proposed framework and algorithms formally stated and proven. The experiments systematically evaluated the impact of algorithm design choices (e.g. positive/negative edge sets) and data characteristics (e.g. graph structures) on model performance.\n- Learning faithful graph representations with minimal data has important computational benefits and is conceptually valuable for understanding the essential structural information needed to distinguish different graphs. The reduction in training data achieved by the proposed sampling method is substantial. The theoretical framework and practical techniques in this paper could be built upon to develop further improved graph representation learning approaches.", "weaknesses": "- 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? \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review and questions!\n\n> 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?\n> \n\n> …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?\n> \n\nIn this work we have focused on transitivity, but we are certainly on the lookout for other interesting structural properties for which this framework would be useful. One extension we think it would be interesting to explore is relation composition on a multi-relational graph - however, such an exploration would fall outside of the scope of this paper.\n\n> 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.\n> \n\nThank you for your suggestion. Since the total number of edges — both positive and negative — in the sidigraph is $O(|V|^2)$, each set of nested for-loops in Algorithm 1 (lines 2-5 as well as lines 6-9) takes $O(|V|^2)$ time, since the cost of removing a redundant edge is $O(1)$. Moreover, in practice, removing a negative edge in the inner loop will often reduce the number of edges left to iterate over in the outer loop. We will make sure to include this runtime analysis in the camera-ready version.\n\nFor detailed statistics about sidigraph sparsity please refer to Table 1 in Appendix H, where we provide the unpruned number of positive and negative edges of each graph we consider, as well as the ratios of the “reduced” to the “full” sets of positive/negative/total edges. The rightmost column in Table 1 demonstrates that for Balanced Tree, nCRP and MeSH, the reduction in negative edges is drastic (at least 99% for one or more graph configurations of those families).\n\n> 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)?\n> \n\nWhile we do not have a formal proof concerning the influence of particular graph structures on convergence, we would like to refer the reviewer to Table 1 in Appendix H, which shows (in the rightmost column) that for Balanced Trees, the reduction in negative edges contributed by FINDMINDISTINGUISHER is always at least 99%, while it is much less for Price graphs. This suggests that balanced trees can benefit substantially more from the reduction than Price graphs.\n\n> 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?\n> \n\nYes, we agree that hierarchy-aware negative sampling could potentially be used to provide an adaptive noise distribution for training non-embedding GNN models which attempt to learn latent hierarchical structure. To expand on this slightly, while we apply our algorithm to a static DAG, this could also be applied to a dynamic graph, such as an “active learning” setting (eg. where the true graph is unknown and we query humans for the existence or non-existence of particular edges) or the setting you describe, where a model such as a GNN attempts to learn the latent hierarchical structure and the edges presented to the training algorithm update dynamically using our constructive algorithm based on the current model parameters. This is an interesting direction for future exploration!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IOKL7uYdjc", "reviewer": "Reviewer_VFTZ", "summary": "This paper proposes to distinguish a directed graph (digraph) among all transitivity-closed DAGs by finding minimal signed directed graph (sidigraph).\nThis paper exploits this idea to propose a more efficient algorithm for node embedding models.", "questions": "I hope the authors clarify the points raised in the weaknesses section.", "limitations": "NA", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "- Theoretical supports in Sec. 3 for the sidigraph obtained by algorithm 1.", "weaknesses": "- It is not clear regarding prop 2 if the distinguishing serigraph H' is \"lighter\" than the transitive reducted G'.\n\nThis seems to \"shift\" the problem from reducing G to G' to reducing G to H'.\nI do not see the benefit of obtaining H' over directly obtaining G'.\n\n- 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?\n\n- It is difficult to understand the aim of the experiments. In L253, the authors wrote as \n\n> 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\n\nHowever, the very first sentence of the result in L260 is \n\n> First note that GT-BOX universally outperforms SIM-VEC on the graph modeling experiments\n\nIf 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.\n\nThis may be the presentation issue or content-wise issue. Anyhow, I hope the authors clarify these points.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your questions and comments.\n\n> It is not clear regarding prop 2 if the distinguishing serigraph H' is \"lighter\" than the transitive reducted G'.\n> \n\nPlease note that while $G^{\\prime}$ is a digraph with only positive edges specified, $H^{\\prime}$ is a sidigraph with positive edges *as well as explicit negative edges* specified. Thus, if the positive edges of$H^{\\prime}$ are already transitively-reduced, then indeed $H^{\\prime}$ is not lighter than $G^{\\prime}$ *in terms of positive edges.* However, this is not the case *in terms of the negative edges* of the equivalent sidigraph to $G^{\\prime}$.\n\nNote that for $H=(V, E_{H}^{+}, E_{H}^{-})$ at the start of Proposition 2, since we are given that $H$ is a distinguisher of $G^{\\prime}$, we are guaranteed to have $E_{H}^{+} \\subseteq E$ and $E_{H}^{-} \\subseteq \\overline{E}$ by Definition 2. Therefore, removing any negative edge from $H$ to produce $H^{\\prime}$ will necessarily make $H^{\\prime}$ lighter than $H$, i.e., lighter than the equivalent sidigraph to the transitively-reduced $G^{\\prime}$.\n\nFor empirical evidence that $H^{\\prime}$ is lighter than the equivalent sidigraph $H$ in terms of negative edges, please refer to Table 1 of Appendix H, where the rightmost column gives the reduction in negative edges contributed by Algorithm 1 to be as high as 99% for many graph families.\n\n> 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'.\n> \n\nAs noted above, $G^{\\prime}$ can only inform us of the reduction in *positive edges*, and is ambiguous w.r.t. the reduction in negative edges. For the machine learning setting that is explored in the second part of this paper, we need to sample both positive and negative examples (edges) for training — therefore it is not enough to specify $(V, E^{tr})$ as it can imply $(V, E^{tr}, \\overline{E})$, which offers no reduction in negative edges for the sampling pool. Reducing $G$ to $H^\\prime$ implies explicitly reducing it to $(V, E^{tr}, E_{H}^{-})$, which may have orders of magnitude fewer negative edges from which to sample.\n\n> 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?\n> \n\nIndeed, the graph-theoretic question posed by our paper is answered by Proposition 2 and Algorithm 1 which is based on it. However, we would like to understand whether the provable graph-theoretic sufficiency of $H^{*}$ can be exploited by energy-based node embedding models. \n\n\nProposition 4 shows that if the energy-based node embedding model has transitivity bias, then there exists a parameter configuration that can unambiguously represent $G$  if it can represent a distinguisher of $G$ (such as $H^*$). However, the question of whether this configuration is achievable in practice is an empirical one, which our experiments section explores or real data. The experiment section shows that training the transitivity-biased GT-Box with positive and negative edges from $H^*$ achieves the configuration, whereas training SimVec (which does not have transitivity bias) while sampling from the same support set results in very poor performance (see Figure 6, $(E^{tr}, E_{H}^{-})$).\n\n> It is difficult to understand the aim of the experiments. In L253, the authors wrote as\n> \n> \n> > 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\n> > \n\n> However, the very first sentence of the result in L260 is\n> \n> \n> > First note that GT-BOX universally outperforms SIM-VEC on the graph modeling experiments\n> > \n\n> 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?\n> \n\nThank you for pointing this out, and we see how this sentence can be misleading as to the aim of our experiments. Indeed, **the main aim is to understand the impact of {$E^{tc}$,  $E^{tr}$} and of {$\\overline{E}, E_{H}^{-}$} on convergence.** Thus, we were trying to emphasize that it is not the best achievable F1 that is of interest to us, but how the convergence is affected by the support sets. **The fact that SimVec underperformed GT-Box w.r.t. the ultimate F1 (as written in L260) does not obscure the pervasive trend that GT-Box is consistently able to benefit from the hierarchy-aware negative edge set $E_{H}^{-}$, while the performance of SimVec plummets with $E_{H}^{-}$ to the point where SimVec is not able to learn anything useful.** We will certainly revise the first sentence of 6.1 for the camera-ready version, and we appreciate your suggestion!\n\n> 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.\n> \n\nWe note that GTBox is a generalization of a number of models that have transitivity bias. Meanwhile, SimVec reflects a simple but widespread vector-based node embedding model that does not have transitivity bias. Based on Proposition 4, we have strong evidence to believe that analogous models without transitivity bias would exhibit similar poor trends to SimVec when coupled with $E_{H}^{-}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ujGNfCv0ge", "reviewer": "Reviewer_TmQr", "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.", "questions": "Refer to the weakness section above.", "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.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1: A framework is proposed for detecting a sufficient smallest subset of entities in a graph adjacency matrix to specify a digraph. \n\nS2: Details on formulating the problem are provided to help characterize the proposed method.\n\nS3: A series of experimental studies were conducted to show the effectiveness of the proposed method.", "weaknesses": "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. \n\nW2: 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. \n\nW3: 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”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and questions.\n\n> 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.\n> \n\nAll of the additional steps introduced by the hierarchy-aware sampling can be lumped under a one-time preprocessing procedure, as described in Algorithm 1.\n\nSince the total number of edges — both positive and negative — in the sidigraph is $O(|V|^2)$, each set of nested for-loops in Algorithm 1 (lines 2-5 as well as lines 6-9) takes $O(|V|^2)$ time, since the cost of removing a redundant edge is $O(1)$.\n\nIn practice, the preprocessing step of FINDMINDISTINGUISHER can be run on CPU and can be parallelized w.r.t. the negative edges. Moreover, as evidenced in Table 1 Appendix H, the reduction in negative edges is often over 99%. Meanwhile, Figure 5 (GT-Box, rows 3-4) show that the convergence rates of Balanced Tree and nCRP (the graphs with the greatest negative reductions contributed by the reduced negative edges $E_{H}^{-}$) are higher using $E_{H}^{-}$ than using the full negative edge set $\\overline{E}$. We therefore believe that our setup is useful in practice.\n\n> 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.\n> \n\nTo elaborate, the terms $\\ell^{+}(x)=\\lambda_{pos} x$ and $\\ell^{-}(x) = -\\lambda_{neg}~x$ in the loss equation of Section 5 are the same as the terms in Section 2.2 — positive and negative scalars which we call $\\lambda_{pos}$ and $\\lambda_{neg}$, respectively, to weight the energy contribution. We always set $\\lambda_{pos}=1$ and we optimize for the best $\\lambda_{neg}$ (please refer to Appendix G.1 and G.2). Therefore, for SimVec, the expanded loss function is:\n\n$\\sum_{(u,v) \\in E_{H}^{+}}\\ell^{+}(E_{\\theta}(u,v)) + \\sum_{(u,v) \\in E_{H}^{-}}\\ell^{-}(E_{\\theta}(u,v))$\n\n$=\\sum_{(u,v) \\in E_{H}^{+}}\\ell^{+}(-\\log\\sigma(\\theta_u \\cdot \\theta_v)) + \\sum_{(u,v) \\in E_{H}^{-}}\\ell^{-}(-\\log\\sigma(\\theta_u \\cdot \\theta_v))$\n\n$=\\sum_{(u,v) \\in E_{H}^{+}}(-\\log\\sigma(\\theta_u \\cdot \\theta_v)) -\\lambda_{neg}\\sum_{(u,v) \\in E_{H}^{-}}(-\\log\\sigma(\\theta_u \\cdot \\theta_v))$\n\n(The energy function for SimVec is mentioned in line 236 of the paper.) For GT-Box, the expanded loss function is the same, except that the $-\\log\\sigma(\\theta_u \\cdot \\theta_v)$ is replaced by the GT-Box energy function described in lines 181-185.  We hope that this alleviates your concerns regarding reproducibility! We will also provide a link to our implementation upon acceptance.\n\n> 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”.\n> \n\nThank you for these observations — we will take care to improve and proof check our writing!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are sharing a pdf with plots for GT-Box with negative ratio $k=128$ (analogous to Figure 7, which is for $k=4$).

Meta-review: 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.
Decision: Accept (poster)