Learning Representations for Hierarchies with Minimal Support

Thank you for your review and questions.

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.

All of the additional steps introduced by the hierarchy-aware sampling can be lumped under a one-time preprocessing procedure, as described in Algorithm 1.

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)$.

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

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.

To 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:

$\sum_{(u,v) \in E_{H}^{+}}\ell^{+}(E_{\theta}(u,v)) + \sum_{(u,v) \in E_{H}^{-}}\ell^{-}(E_{\theta}(u,v))$

$=\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))$

$=\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))$

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

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

Thank you for these observations — we will take care to improve and proof check our writing!

Thank you very much for your questions and comments.

It is not clear regarding prop 2 if the distinguishing serigraph H' is "lighter" than the transitive reducted G'.

Please 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}$.

Note 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}$.

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

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

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

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?

Indeed, 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.

Proposition 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}^{-})$).

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

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

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

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

If the authors want to show that the proposed algorithm outperforms the existing one, then probably the authors want to compare with many more. If not, what is this sentence?

Thank 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!

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.

We 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}^{-}$.

Thank you for your encouraging review and questions!

While the paper demonstrates the effectiveness of transitivity bias and hierarchy-aware negative sampling for DAGs, the authors could discuss whether these ideas extend to learning representations of other graph families characterized by different structural properties. Are there other useful inductive biases worth incorporating into node embeddings and corresponding "structure-aware" sampling strategies?

…The framework of sidigraphs for distinguishing graphs with a given property seems quite general. Have the authors considered instantiating it for properties other than transitivity?

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

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.

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

For 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).

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)?

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

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?

Yes, 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!

Thank you for your review and insightful questions!

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)

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

2a) Could you further detail the architecture and optimization procedure followed in your experiments ?

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

Concerning optimization procedure, please refer to Appendix G for details on optimization procedure for Synthetic Graphs (G.1) and MeSH (G.2)

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 ?

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

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.

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

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 ?

Apologies 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$.

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' ?

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

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.

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

small tipos:

L.208, missing word ? we formally explain...

L.37-38: misleading / big claim, as you study a very specific type of graph.

Thank you — we will address these typos promptly!

Thank you for your encouraging review and questions!

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.

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

A 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).

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.

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