Learning-Augmented Hierarchical Clustering

Thank you for your careful review, positive evaluation, and helpful questions. Our responses and clarifications are as follows.

Relation To Broader Scientific Literature

Thanks for pointing out the additional papers related to our work. We will add them and some discussions about the connections.

I do think the assumption of large probability of success (p=9/10) was surprising to me, as in other works (e.g. max-cut and max IS with predictions) the emphasis is on overcoming barriers using arbitrarily small probability of success. I would suggest that an abridged discussion of this assumption be presented closer to the statements of the main theorems, as currently it could be overlooked in the main body of the paper.

After reading Appendix I.1, it is now my understanding that for arbitrary (adversarial) incorrect responses, a significantly large probability of success is necessary (see Questions below), while for randomly-chosen incorrect responses, probability $½+\varepsilon$ does suffice. Is this understanding correct?

(Q2) In Appendix I.1, I am confused about some of the remarks about general success probabilities. The penultimate line states “...we remark our algorithm would work for any success probability ½ + C for sufficiently large C.

We answer these concerns and questions together here since all of them are related to the success probability of the learning-augmented oracle. We first want to say that the reviewer’s understanding of our algorithm is correct: in the setting of adversarial noise, the success probability should be at least $1/2+C\geq 3/4$, and $9/10$ suffices. On the other hand, if the errors of the oracle are random, we should be able to ensure correctness with $1/2+\varepsilon$ for any constant $\varepsilon>0$ (we forgot to mention “constant” in the current Appendix I.1 and will add that in the final version).

The reason our algorithm should work with a sufficiently high success probability is exactly due to the hierarchical structure of the problem. In both max-cut and MIS papers (which we are sufficiently familiar with), the errors in the algorithm are ‘one-shot’. However, in the HC problem, if the construction of the partial tree is wrong at any level, the error will propagate to all subsequent nodes, and it is not clear how one could control the error if this happens. Furthermore, the oracles in the max-cut and MIS papers are about ‘memberships’, while the oracle in our setting is about ‘relationships’. The latter type of oracle does not give any trivial solution or even a ‘partial solution to be fixed’ (like the case in the MIS paper). Therefore, a constant success probability much larger than $1/2$ is necessary.

In the exposition, $\delta$ is used to denote success probability, while later $p$ is used.

Thanks for the catch! We will unify this and use $p$ as the success probability.

Is there an intuitive reason why the results established in this work only apply to the Mosely-Wang (MW) and Dasgupta (Das) objectives, as opposed to the Cohen-Adad (CA) objective? In particular, it is striking that the impossibility results for oblivious algorithms for both MW and Das stem from the Small Set Expansion hypothesis, whereas impossibility results for the CAobjective stem from UCG. Is the fact that your results focus on MW and Das implicitly connected to this divide?

We do not believe our results are connected to the division between the UGC vs. small set expansion. The reason is that our constructions for the weakly and strongly consistent partial trees are objective-oblivious, and we can also construct these partial trees w.r.t. the Cohen-Addad objective. The reason for us not getting results for the Cohen-Addad objective is due to the limited bandwidth, we are not sure how the error would propagate in the CA objective. It will be an interesting direction to explore as a future step.

Thank you for your insightful questions and positive evaluation. Our responses to the questions are as follows.

The error probability of the splitting oracle cannot be too large

We agree with the reviewer that this is a limitation of our algorithm, and due to the combinatorial nature of many subroutines, it’s unclear exactly what minimal error can be tolerated on this front. However, we hope that modern ML models can achieve decent accuracy across the entirety of the similarity graph, which may consist of a number of dissimilar items.

We agree that additional experiments could add value to the paper. We have conducted preliminary experiments on social network-like graphs and plan to expand the discussion accordingly.

Typos

Thanks for pointing these out. We will make changes accordingly.

Implementing the oracle in small space

This is a great question. We are not exactly sure how the oracle could be implemented in small space. However, since the input of the oracle is only triplets of vertices, and the output is essentially an ordering, the model size could be very small (say, for a 3-layer neural network, we could implement with 3xNx1 with one N-node hidden layer). Of course, to ensure good performances, the actual model might need to be bigger. We could also use cloud-based services, and the aim is to reduce the memory cost on local machines. For instance, we could query the triplets to LLMs and implement the streaming algorithm on our local machine. Exploring whether these ideas work is an interesting direction to pursue.

Potential sublinear time algorithms

We believe it is possible to revise our weakly consistent partial tree algorithm to achieve sublinear (i.e., $o(n^2)$) time. The `counterpart testing’ subroutine, as we could see in the construction of the strongly consistent partial tree, could be made $O(n \log{n})$ time. Due to the balanced partition, this part should take $\tilde{O}(n)$ time across the algorithm. However, the ‘root test’, which is crucial to the correctness of our algorithm, still requires $O(n^2)$ time. Making this part sublinear time appears to require more work, and is an interesting direction to explore as future research.

Performance of the algorithm with random noise

Due to the persistent noise and the combinatorial nature of our algorithm, it is difficult to get something in the form of query-quality trade-offs. If the noises are random, for the adversarial example we mentioned in appendix I.1, as long as $\varepsilon=\Omega(1/n)$, we should be able to obtain enough signals to distinguish the cases for the two sides. We also realize that the way it is currently written is not precise, and we meant to say that if the noise is random, we could guarantee correctness for any constant $\varepsilon$ (as opposed to some fixed $C\geq 1/4$). We will make changes about this in future versions.

Thank you for your detailed review and insightful questions. Our responses and clarification are as below.

The paper deviates from the standard setting of learning-augmented algorithms, which assumes no guarantees on the quality of predictions.

Although there is a body of literature that assumes no guarantees on the quality of predictions, we believe the setting with performance guarantees for the predictions is also quite standard, especially for graph-related problems. To that end, we have expanded the discussion on the “algorithms with $\epsilon$-accurate predictions”, including “Learning-Augmented Streaming Algorithms for Approximating Max-Cut” (DVP [ITCS’25]), “Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems” (COGLP [NeurIPS’24]), and “Learning-augmented Maximum Independent Set” (DBSW [APPROX’24]).

We want to emphasize that since we study an offline problem (as opposed to an online one), we could always guarantee robustness studied in the online learning-augmented algorithm literature by running a separate algorithm without prediction. In the end, we could evaluate the costs of the two HC trees (with and without predictions) and output the one with the lower cost.

Discussions about “algorithm actively decides when to query predictions, rather than receiving them as a fixed input”

We agree that our algorithm requires adaptivity, and we can add more discussion about this in future versions. Thanks for providing the related literature.

Assuming an oracle with p=0.9 accuracy is quite restrictive.

First, we want to clarify that our discussion did not mention the error probability of $1+\varepsilon$ but rather $1/2+\varepsilon$ and $1/2+\Omega(1)$. Due to the offline nature of our problem, indeed, we could recover the best result for hierarchical clustering when the prediction is bad by simply running a separate algorithm without using any prediction. We also discussed a simple example (in I.1) that requires the correct probability to be at least 3/4. This is due to the combinatorial subroutines used in our algorithm

Accessibility.

We thank the reviewer for the comments on readability. We have strived to make the paper readable by inserting multiple figures and explaining things in detail as much as possible, e.g., by providing intuition for both our algorithm and our analysis in the technical overview that is Appendix B. Although elements of our results have multiple moving parts and are complex to describe, we completely agree that accessibility is an important part of the paper. Thus, we will continue to make editorial passes over the document to improve presentation.

The accuracy of the oracle is denoted $1-\delta$ vs. $p$

We thank the reviewer for pointing this out, and we have made changes accordingly.

In Section 5, the complexity of Algorithm 3 seems quadratic and not near linear.

We view the input as the similarity graph with $\Omega(n^2)$ edges on $n$ vertices, so that the input size is $\Omega(n^2)$ and thus our algorithm that has runtime roughly quadratic in the number of vertices actually has runtime near-linear in the input size. We have clarified this point.

The bound in Proposition 13.

We only deal with discrete random variables in this paper, and for all the applications of Proposition 13, we only used supports on $\{0,1\}$. For discrete random variables with supports as a (finite) set of value between $[0,1]$, the bound should be true also. We agree that Chernoff bounds on continuous random variables might be different, and we will make Proposition 13 more precise in later versions.

Thank you for your careful review and positive evaluation. Our responses are as follows.

Additional References

We agree with the reviewer that discussing the related papers and in particular the role of adversarial noise will help demonstrate the challenges with constructing a near-optimal tree. We thank the reviewer for pointing out the additional references; we have added these discussions to the new version.

O(n^2) time vs. ‘near-linear’.

Due to the construction of weak partial trees, the run time of the algorithm is $\tilde{O}(n^2)$ even if the input graph has $m=o(n^2)$ edges. However, since the similarity graph on $n$ vertices has $\Omega(n^2)$ edges, our algorithm is still near-linear time. We have clarified this point in the updated version.

Furthermore, we believe it is possible to revise our weakly consistent partial tree algorithm to input sparsity runtime, i.e., $o(n^2)$ runtime when the similarity graph is sparse. This could be an interesting direction to pursue as a future step.

Other Comments or Suggestions.

We have addressed these points – thanks for the suggestions!