Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The paper studies the problem of clustering $n$ sets of $m$ lines. In detail, the objective is to compute $k$ means that minimize the squared Euclidean distance to the closest point on the closest line in each of the $n$ sets. This problem is a novel generalization of the $k$-means for lines clustering problem, which has already been studied in the literature.
strengths_and_weaknesses: The paper is well written and the problem is somewhat interesting, though I am not completely convinced on the motivation of studying this problem. The authors motivate it by giving an example with missing values. However, the missing value is arbitrary and the objective function is a chain of minima, which makes me doubt the practical expressiveness of a solution.

The reduction from the problem given $n$ sets of $m$ lines to $n$ sets of $m$-tuples of points (colored points) is interesting (as is the latter problem). Unfortunately, little of the analysis has made it into the main paper. 

The general result is obtained by an application of the sensitivity sampling framework, which is a standard in the coreset literature (at least for sum-based clustering objectives).

A minor weakness is that the related work is treated a bit superficially. The coreset size from the $k$-means for lines work is not stated -- it would be interesting to compare their size to the coreset size of the work at hand. Furthermore, the experiments are very basic and only compare to uniform random sampling -- it would be much more interesting to also include here the work of [33] and compare to them for $m=1$. Also it is sometimes not clear whether the authors are aware that projective clustering has already been (extensively) studied.
questions: My suggestion is to remove the experiments and include more theoretical work. It would be nice to put the reduction to colored points into focus.
limitations: No potentially negative societal impact in sight.
review_title: null

final_score: 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.
review_content: summary: This paper proposes the problem of k-clustering for a collection of sets of lines. In this new problem, each “data point” is a set of 1D lines in R^d. The goal is still to find a center set in R^d of k points, such that the sum of “distance” to every data point is minimized, where this “distance” is defined as the minimum distance from the center set C to the nearest line from a line set.

Even though the problem looks artificial at the first glance, it does have natural and important applications. For instance, as pointed by the authors, the line clustering itself might be viewed as clustering points each with a single missing numerical feature (so all possible realizations of that missing coordinate form a line), and a further missing categorical feature results in a set of lines.

The paper focuses on studying the coreset for the line sets clustering problem. As usual, the definition of coreset is still to preserve the cost for every possible center set C \subseteq R^d, up to 0 < \epsilon < 1 relative error. The main result is an efficient coreset construction with size poly(m log n / eps) k^{mk}, where m is the (max) number of lines in each line set.

This result might be viewed as a generalization of previous papers [26, 28], which deal with the case m = 1 or the case of sets of points. To resolve the new challenge of m > 1 lines, an auxiliary problem called clustering with colored sets is considered, where a color corresponds to a line in a line set, and it is used to ensure that only one line that achieves the minimum is assigned to the center set. The overall approach is similar to [26] and [28] which is also based on the sensitivity sampling framework, but the colored version of clustering is a necessary new step, especially used to compute the sensitivity. I find it natural and elegant.

Experiments that evaluate the empirical size-vs-accuracy of the proposed coresets are conducted, compared with a uniform sampling baseline, on both synthetic and real datasets with moderate size (~10^4 points). The results show an error curve that is superior to uniform sampling in the sense that it achieves much better error for smaller coreset size, and both algorithms converge when the number of coreset points reaches ~10^3.

strengths_and_weaknesses: Overall, I think this is a nice generalization of [26] and [28], especially considering the motivation for dealing with the missing value on categorical features. The result is probably nearly the best that one can obtain using current techniques, but this also means that one still does not have a full understanding of the problem, and new techniques and/or lower bound are much appreciated. Even though this paper certainly has theoretical value, the experiment result seems not completely convincing.

The paper is well written and a comparison with previous works seems to be comprehensive.
questions: 1. It seems uniform sampling already performs well enough from the experiment – I understand the error curve is slightly better, but I don’t think that matters a lot in practice. Can you justify the absolute advantage of your coreset over uniform sampling? At least I cannot see it from the plot, nor from your interpretation of the result.

2. You mentioned several times the colored clustering problem is tightly related to fair clustering. I can see they seem to be related, but the more concrete/formal relation is not clear to me. In particular, does this give you any result for the setting of fair clustering directly?

Minor comments:

1. Line 211: “Langberg-Feldman” -> “Feldman-Langberg”
2. Line 246: “lth”->’l-th”
3. Line 4 of algorithm 1, it’s better to use \mid in the set notation – currently the spacing is too small.
4. Line 260, “that are both satisfy” -> “that both satisfy”

limitations: Yes, and it has been discussed in the checklist.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper investigates the line-sets k-median problem, whose goal is to compute a set of k centers that minimizes the total Euclidean distances from each set of lines to its closest center. The authors propose an algorithm that constructs a small-size coreset for the line-sets k-median problem, based on a novel reduction to a colored point-sets clustering problem and a coreset algorithm for this problem.
 

strengths_and_weaknesses: This paper proposes a new problem:  the line-sets k-median problem, a generalization of clustering lines. The proposed coreset algorithm is non-trivial and relies on a reduction to a colored point-sets clustering problem. 

My main concerns are the writing and the significance.
- I don't think the line-sets k-median problem is common in practice. The authors provide a discussion on the applications, e.g., computer vision, but somehow artificial. The studied problem is more like a technical problem instead of a practical one.
- The technical part is difficult to read. 1) Def 3.2 appears a little late, while the authors have mentioned ordered-set before. 2) No discussion or explanations on the algorithms, which makes the reading not easy. 3) The main coreset algorithm is in the appendix, which makes me surprised. 4) By the algorithms, I don't understand what the technical difficulty is and why the algorithm is correct. Some intuitions should be given.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Thanks for the response. The revised pdf is better in writing. I raise my score accordingly.
questions: Could the authors explain why the algorithms work? E.g., 
- What is the intuition behind Lemma 3.4?
- How to obtain the coreset size in Theorem 3.5 from Lemma 3.4?
limitations: Yes
review_title: null

Meta-review: metareview: The paper gives new coresets for sets of lines in a high dimensional space. The problem comes from modeling an input data point with 2 missing attributes, one continuous and one discrete, as a set of lines. Previous results only worked with missing continuous attributes. The reviewers appreciate the technical contribution of the paper and it might lead to additional results for data with more general patterns of missing attributes. On the other hand, the contribution seems somewhat limited as the previous works for missing continuous attributes can handle a general number of missing attributes, up to 10-20 whereas the formulation here is very specific, albeit with 1 discrete attribute. More experimental evaluation comparing with previous coreset results in common special case would also strengthen the paper.
confidence: Less certain
Decision: Accept