A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time

Summary

This paper studies the problem of constructing a spectral clustering oracle with sublinear pre-processing and query time complexity. The paper introduces a new algorithm which improves on previous methods with respect to the running time at the expense of a slightly worse approximation guarantee. In contrast with previous methods, the new algorithm is more practical as demonstrated by experiments on synthetic data.

Strengths

On the theoretical side, this paper introduces a new sublinear-time clustering oracle with guarantees which improve on the previous state of the art in terms of running time. The new proof techniques are introduced in quite a natural way and the intuition is clearly explained. An important contribution of this paper is that the proposed algorithm is practical and admits an implementation.

Weaknesses

The theoretical improvements over the previous algorithms are quite small (in particular, the improvement over [30]), however I don't view this as a major weakness given that the new algorithm is more practical. The statement of Theorem 1 is quite difficult to follow. For example, the parameter $\xi$ doesn't seem to be introduced or explained intuitively. The experimental evaluation is quite limited - it does not include comparison with any other method, and does not report the running time of the algorithm. If the algorithm cannot be compared with that of [30] or [14], consider stating why this is the case in section 4.

Questions

What is the purpose of $\xi$ in Theorem 1? As far as I can see from the Theorem statement, it only appears in the running times, and always in the denominator - why not always set it to $1$? Is it possible to experimentally compare the algorithm with [30] and [14]? ### Typos * Line 133 - space missing after '.' * Line 144 - space missing after reference [7] * Line 145 - Noted -> Note * Line 246 - dose -> does * Line 262 - space missing after 'Theorem'

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are adequately addressed.

Summary

This paper studies oracles for spectral graph clustering, i.e., local algorithms that answer membership queries for single nodes in a spectral clustering of a graph. There is a line of research on testing cluster structure in degree-bounded graphs, and recently, the learning version of the problem studied in this paper has become popular. Besides a result for robust clustering oracles by Peng, this works is closely related to a paper by Gluch et al. Compared to the work of Gluch et al., this submission improves the preprocessing time to $O(n^{1/2 + O(\epsilon / \phi^2)})$, which is better by a factor of approximately $2^{poly(k/e)}$ at the expsense of requiring a conductance gap of approximately $\Omega(1/poly(k))$, which is worse by approximately a $poly(k)/\log(k)$ factor, and a misclassification error of $O(poly(k) \epsilon)$, which is worse by approximately a $k / \log(k)$ factor. The misclassification error is the fraction of vertices that are assigned to the wrong cluster (compared to the ground truth clustering). The query time of the two algorithms is roughly the same. In a nutshell, the result in this submission trades an additional polynomial dependency in conductance gap and misclassification error against the removal of an exponential dependency in preprocessing time. The authors experimentally confirm the misclassification error and query complexity proven in their theorems. This work builds up on the dot product oracle introduced by Gluch et al. The algorithm in the latter work estimates the means of the clusters (in an embedding space) and uses the dot product oracle to estimate the closest cluster center (mean) for a query node. The exponential preprocessing time arises from the former part. In the present submission, the authors propose an algorithm that doesn't estimate the cluster means, but compares the dot product between node embedding directly. Intuitively, if two nodes belong to the same cluster, they have a large dot product with their cluster mean, and so they should also have a large dot product with each other. This modification also results in the aforementioned trade off, i.e., the increased misclassification error and the stronger requirement on cluster separation. The question answered by this paper arises naturally from the work of Gluch et al.: Do we need to compute the cluster means explicitly? While the answer may not be surprising (no, but there is a trade off), it requires some work to actually prove this, as the formal argument is not simple and obvious. The intention of the experiments is not clear to me, as there is no comparison with other algorithms, or insights how the theoretical algorithm needs to be modified and tuned for applications. Rebuttal: Rating changed from weak accept to accept due to authors' rebuttal responses.

Strengths

* The question explored in this paper is natural. * The paper confirms an intuitive concept of spectral embeddings for clustering.

Weaknesses

* The result in this paper is not very surprising or better than one would expect. It seems more like a reasonable trade off. * The experiments seem currently not very useful.

Questions

Note: It seems to me that a comparison of the conductance gap of your result and [14] is missing.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

-

Summary

This paper proposes a spectral clustering oracle with sublinear pre-processing time and query time. The query is in the form of $(G, x)$ where $G$ is a graph with underlying clusters and $x \in V$ is a vertex. The goal is to (1) construct the oracle efficiently, (2) report which cluster vertex $x$ belongs to efficiently. Comparing to the previous work, the main contribution is improvement on the pre-processing time, which reduces exponential to polynomial on $O(k/\varepsilon)$, but blows up the misclassification error from $\log k$ to $\text{poly}(k)$, also slightly relaxing an assumption on the gap between inner and outer conductance. The query time is asym-same. The main technique is to replace the exhaustive search for each sampled vertex to decide a vertex $x$ belongs to a cluster with center $\mu$, with estimating the inner product of their spectral embeddings. It is proved the magnitude of the inner product roughly shows if two vertices belong to the same cluster.

Strengths

- The paper is clearly written and well organized. - The result is neat, the proposed algorithms are more easy to implement comparing to previous ones. - I think for a theory paper, having experiments is always a plus. However, there is a mentality that either do it well or just don't do it. The experiments can be improved or at least clarified better.

Weaknesses

- The major concern is that the contribution of the main result is quite limited. Yes, $O(k/\varepsilon)$ is an important factor, but it still in the $\tilde{\Omega}(\sqrt{n})$ regime, not to mention compromise on others. I actually like the robustness result better. - On the experiments, if the authors want to keep and improve the section, I would suggest: - (1) Clarify the evaluation. I believe the theoretical result on the error is the number of query instances? Then the current report does not look like so, is it the fraction? - (2) The issue of query complexity is not mentioned before. It is out of blue. Explain why you do it. - (3) Add the robustness experiments.

Questions

For the oracle results, there is another measure-of interest on the space. It would be good to report and compare with previous ones on this. Just some curiosity on the lower bound. Is there any result stating something like: to obtain a small error, at least some space / time is needed? Another suggestion is to give some conceptual description of good and bad vertices before the definition, maybe in the main technique part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

See above. My reason to give the current assessment is mainly on the technical novelty limit.