Coreset for Line-Sets Clustering
Authors: Sagi Lotan
Ernesto Evgeniy Sanches Shayda
Dan Feldman
Venue: NeurIPS 2022 Accept (2022)

Abstract: The input to the {line-sets $k$-median} problem is an integer $k \geq 1$, and a set $\mathcal{L} = \{L_1,\dots,L_n\}$
that contains $n$ sets of lines in $\mathbb{R}^d$. The goal is to compute a set $C$ of $k$ centers (points in $\mathbb{R}^d$) that minimizes the sum $\sum_{L \in \mathcal{L}}\min_{\ell\in L, c\in C}\mathrm{dist}(\ell,c)$ of Euclidean distances from each set to its closest center, where $\mathrm{dist}(\ell,c):=\min_{x\in \ell}\norm{x-c}_2$.
An \emph{$\varepsilon$-coreset} for this problem is a weighted subset of sets in $\mathcal{L}$ that approximates this sum up to $1 \pm \varepsilon$ multiplicative factor, for every set $C$ of $k$ centers. We prove that \emph{every} such input set $\set{L}$ has a small $\varepsilon$-coreset, and provide the first coreset construction for this problem and its variants. The coreset consists of $O(\log^2n)$ weighted line-sets from $\set{L}$, and is constructed in $O(n\log n)$ time for every fixed $d, k\geq 1$ and $\varepsilon \in (0,1)$. The main technique is based on a novel reduction to a ``fair clustering'' of colored points to colored centers. We then provide a coreset for this coloring problem, which may be of independent interest. Open source code and experiments are also provided.

Coreset for Line-Sets Clustering
Sagi Lotan gggg.lota@@gmil.com
Ernesto Evgeniy Sanches Shayda ernestosanchees@maill com
Dan Feldman com
Robotics Big Data Labs,
Computer Science Department, University of Haifa
Abstract
The input to the line-sets k-median problem is an integer k 1, and set L {L,,..., } that contains n sets of lines Rd, The goal is to compute a set of centers (points in IRd) that minimizes the sum ElEg minegt,eec dist((, c) Euclidean distances from each set to its closest center, where dist(E, c) := minæet || - cll An e-coreset for this problem is a weighted subset of sets in C that approximates this sum up of & centers. We prove that every such input set L has a small e-coreset, and provide the first coreset construction for this problem and its variants. The coreset consists (log" n) weighted line-sets from C. and is constructed in On log n) time for every fixed d, k 2 and ε E (0, 1). The main technique is based on a novel reduction to "fair clustering" of colored points to colored centers. We then provide coreset for this coloring problem, which may be of independent interest. Open source code and experiments are also provided.
multiplicative factor, for every
Introduction
In the classic k-meaa clustering problem, the input is a set P of n points in a metric space (X' dist), and integer 1. The goal is compute a C* of k centers (points in 2') that minimizes the sum of squared distances over each point E P to its nearest center in C*, i.e., to compute
C
arg min CCR,ICl=
E C),
where D(p, C) == min.ec dist (p, This problem is arguably the most common clustering problem formulation, both industry and academy; see references e.g. in 20 31 36).
A natural generalization is to replace this input set P of points by set P of n sets in X. The distance from such an input set P P between the closest point-center pair. This problem is called k-mean for sets; see e.g. 26 and references therein. Its goal to compute
C* of centers can then be defined the distance
C E arg min E(P,C), PEP
where (PP, C) == milper D(p, C). special case where every such set E P line in X RR.d This problem is called k-mean for lines; see e.g. [10 35). Its goal is to compute set C* of l points in IR such that
C* E arg min E(e,o). OCRd_CCk= TEP
(2)
This paper considers a further generalization of the last problem, where the input is a set of n sets, each contains multiple lines as follows.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(b)
(C)
sets (in different colorsi, each contains pair (m 2) of lines (some color) the plane (X 5.)). The closest line the stars in each pair of lines bold. Application: (b) set of n. 3 drones. each equipped with an on-board 2D camera. takes a mupshoot of point R² (the black line in D2 which is the intersection the image's plane with the camera's pin hole. [e) The
Figure Line-sets Chustering (a) The
Jine-sets mean (black stars) of
1 star). Dut to missing depth, each such goint
corresponds pixel the 2D image's plane, estimated position of the drone from the noizy observations is inaccurate, we use m 2 guesses or consecutive images over time (blue and red line). One of them (in bold) closer the observed point.
Line-sets clustering. The input to the line-sets k-mean problem is an integer L = (LI,.... ] J of n sets, where each set L = {l....., fm in L consists of m 2 1 lines in IR The goal is to compute a set C* of k points in F that minimizes its sum of squared distances over every set of lines in L, i.c.
1, and a set
C* E
E D(L.O). CCRdICCE LEC
arg min
(3)
Here, D(L, min C), the shortest squared distance between point in C' its closest 7EL
line in L; see [.
1.1 Motivation
The classic k-clustering of points has numerous applications, and the l line-sets clustering is its natural generalization. It is thus not surprising that these applications can be casily generalized and extended. We give examples from different research fields follows.
Handling missing data. natural application clustering of data with missing values, as described e.g. in [10]. Here, each record in the input data-set is represented by point in d dimensions. If an entry is missing, we may replace by all possible values, resulting in line in Rd that parallel to one of the axes. Similarly. if the missing entry is discrete, i.e., can be one in a finite set of options, results in a set of points. Our paper handles combination of them both. An example of this can be found in Dataset 4 in our experimental results for California housing. The entries may be the number of the apartment or floor, which corresponds to a set of values. A monthly rent a continuous line. Together they correspond to line-sets. Another perspective
variable, which corresponds would be of sets clustering with missing values, where most of the applications in (26) may be generalized using our work.
Computer vision. In the fundamental 3D model reconstruction problem, we are given pixels (features). Each pixel is from a different 2D image that captures the same point in R.3 i.e., the real world. Such 2D pixel corresponds the pixel in the image plane. The goal is to estimate the location of the point in R based on the set of 2D images. The task of estimating a 3D point location given a single set of lines called Triangulation. Due to uncertainty and noise, feature extraction algorithms usually identify m 2 1 pixels in each image as the captured point, without certainty about which of the pixels are noise and which are correct. Here, the center is this desired point in R3, and every image is represented by m lines. To obtain a model or a "3D point-cloud" [18] of the 3D object. See Fig. (right).
line in R that passes through the camera's pinhole and
we may wish to compute & points (centers)
Colored point-sets clustering applications. This paper reduces the line-sets clustering problem to clustering sets of colored points, which has its own applications. An example is the facility location problem, as in the home and work example in Section 3. Another application is text documents clustering, as explained in Section 5] Here, every document is represented by a set of colored vectors, where each vector corresponds to a paragraph in a "bag of words" representation. Each color represents different type of paragraph, e.g., introduction, summary, main section, theorem, etc.

---

More generally, the problem is relevant where each facility is useful for specific subset of input clients.
We hope that this paper will open the research toward more complex and general shapes that may yield better approximations to high-ways and polygons such as k segments (as in 38 25 or k-subspaces instead of lines.
arcs
1.2 Generalizations and computation models
Our main technique handle the problems above, and especially their streaming, distributed, and parallel versions, is to design data summaries (often called coresets) for the & line-sets clustering problem, and its corresponding set of queries. We may then naive algorithms such exhaustive search on the small coreset to extract the approximated solution, or apply existing heuristics and obtain faster results.
In the following definition, pseudo distance D(p 4) assigns a non-negative number for any pair p.q E Rd. The pseudo distance between sets then the distance between the closest pair, as in ( above. See exact definition and constraints in Definition 2.
Definition 1.1 (Coreset). Let k: 2 be an integer. and (L...... L be an input set, where each = (ei..... .. E L consists of m lines Rd. For given approximation ervor parameter E E (0, 1) and an integer k 2 1, an e-coreset of C for k line-sets clustering over a pseudo distance D is weighted set S S L that approxinates the sum of pseudo distances to & from every set C of centers Rdd, up to a multiplicative factor of E. More precisely, there is a weight function v: S [0, oo) such that for every sel C C Rdd of size |C1 S k.
D(L - Σ v(LLD((L S Se EEEDLL.O LEC
LEC
LES
In particular, an (optimal) line-sets k-mean C" of the weighted set (S, v) is a (1 + apprrxxiiantoonnn to the k-line-sets mean of L. This is the strongest type of coresets (sometimes called "strong coreset" 333 4I), in the sense that it approximates every query C, and not just, say, the optimal solution. It is also a weighted subset of the input, unlike a sketch, linear combination, or general subsets of lines in Rd which are not a subset of C; see next Section 1.3
1.3 Related work
Clustering n points by ls center points is a fundamental problem in machine learning 40
Applica-
tions can be found in operations research (6 8) statistics (20) and computational geometry 4 4 43].
including constant factor approximations (randomized (2) and deterministic 77 Many of the recent results [13] 21 are based on coresets (under different definitions) that can usually be computed in time that near-linear in the input size and number of centers. The size of these coresets usually (k1))0(1), where 5 (0, 1) parameter that represents the approximation error.
lines. Such a coreset was suggested in [35] whose size log² (m) & for any constant & > 0, and is improved in our paper. For the case that the lines are parallel to the axes, coresets were suggested in [TO]. These results also hold for j-dimensional linear subspaces, but only if they are parallel to the axes of I The main motivation is handling j missing entries in each database's 's record (point).
For the special case m = 1, our coreset in Definition I.I is for k-means
Coresets for input sets of points, lines, and fair clustering appeared relatively recently. Coreset for (point)-sets clustering as in Eq. (T), where each set consists of m points, was suggested in (26 and
its size is 1o k0(m).
Our main technical result is a coreset for colored (points) clustering, where the sets and centers are colored, and each input point can be served by center of the same color. This approach is strongly related to fair clustering, where each group is represented by a color.
Variations of fair clustering were suggested in 12 23 27 and references therein. Coresets for fair clustering were suggested in [39]. This paper generalizes some of these results in the sense that the input points colored sets, but the centers are also colored.
3

---

Our coreset constructions, many of the recent coreset constructions, is based on the Feldman- Langberg framework ( I5 29 This framework reduces the problem of computing a coreset to the problem of computing the importance (sensitivity) for each of the input points/sets.
1.4 Main contributions
We suggest the first coreset construction for line-sets clustering whose size (number of weighted sets) is sub-linear in the number of input sets. This is by reduction to another problem. fair clustering (colored points) with colored centers, which may be of independent interest. We then suggest coreset for this type of fair clustering problems. More precisely, we provide the following contributions for every pseudo distance D, constant approximation enror E (0, 1), and constant integers d, k, m 2 1. See the corresponding theorems for exact bounds.
(i) An E-coreset S C C for line-sets clustering of any set C of sets, each consists of at most m lines; see Theorem 4.1
(it) An E-coreset S C P for colored sets clustering of any set P of n sets in X'; See Theorem 4.2
Each of these coresets has size |S| E Ollog" n) and can be computed in O(n log n) time, with high probability. The following results are straightforward implication of the above results, using existing merge-reduce frameworks 1
(iti) Support for streaming data in insertion time and memory that is logarithgt in the number n of the sets seen so far in the stream.
(iv) Support for parallel computations on data that may be distributed on M machines using 1/M amortized insertion time.
(v) Support for deletion of sets from the stream in goly-logarithmic time during the streaming, but using memory that is linear with n.
(vi) FPTAS in time (n logn), n). by running an exhaustive search on the corresponding small corsets.
Dependencies on input parameters. Our first result above is in fact an I.TAS (linear time approxi- mation scheme), since the asymptotic running time depends polynomially on 1/s, and near-linear in n. The dependency on d is polynomial, and the exponential dependency on & and m is unavoidable due to known lower bounds for special cases e.g. in [19] 26). These are worst-case bounds, and the actual approximations errors are much smaller in practice as shown in the experimental results; see Section
1.5 Novel technique: from line-sets to fair clustering
Existing coresets for point-sets clustering are heavily based on the triangle inequality between pair of points, which is not satisfied for the case of lines. On the other hand, existing coresets for lines were reduced to coresets for weighted centers, which do not support sets as an input. The main challenge in this paper is to combine these two results. This is by suggesting novel reduction and coresets for centers, which may be of independent interest and borrows techniques from fair clustering. To our knowledge, this is the first link of this type between geometric shapes and fairness. We hope it will open the door for many other coresets; see Section
Our reduction is based on the following three steps.
Grouping. Algorithm 3 in Section 3.2 recursively chooses very "dense" constant fraction of sets n that are close to m center points (robust medians) 8m = [bi,...,
. bm vth line in each of these sets is then translated its median bi for every [m]. At this stage reduced our problem to compute sensitivity for | E (n) sets of lines that form m "stars": see Fig. 2(a)
see Definition [2.) The
Reduction to points. The distance from each line that intersects a robust median 6; (say, the origin) to query center e; E C' its distance to unit vector in the same direction, weighted by the norm of the vector; see Fig. ((b) This distance can be approximated, up to a constant factor, by replacing c; with its projection on the sphere c// ||c/]| and its antipodal point -ca/ ||c/]|-
Colored sets and centers. The new problem is now to compute sensitivity for n sets, each contains unit spheres; see Fig. 2 Each center in the set C' of & queries is duplicated m times in m colors. The result a set of 2mn weighted centers on m unit sphere with an additional constraint: the ith center can "serve" only the lines on the ith sphere.
m colored points

---

(a)
(b)
(c)
set L of triplets of lines, each in different color. The first line in each triplet intersects the same yellow (robust median) point by, and similarty for the other lines and medians b2. b3. (b) The distance from every colored line to a query center c E IR2 (black star) is the same as its distance from the star in the same color multiplied by the distance from the center to its median. (c) The distance between line I (in green) and the point e (black) is the distance between e' (blue) and multiplied by (black brackets). This distance is approximated the distance ||c pell stated Claim C.3
Figure [a)
Preliminaries
The results in this paper hold not only for squared distance functions but for other functions such as non- squared distances or M-estimators. To generalize this notion, we use the following pseudo distance over metric space (X, díst.;; ie., for the case of input lines, we assume that X' _ and dist is the Euclidean norm. That is, the metric space is (R& I1-112) but lip below can still be any function that satisfies the following log- log Lipschitz condition.
many examples of such functions in (66.. From Section 3.2
Definition 2.1 (Pseudo-distance D). Let lip: [0, 0o) - 10, oo) be a non-decreasing function that satisfies the following condition: There is a constant r E (0, oo) such that for every x, >> 0 we have lip(zx) < z" lip(()). Let (X, dist) be a metric space, and D be function that maps every pair of points p,c X
D(p c) lip(dist(p,c))
For pair of finite sets P,C C X, denote D(P, C) == millpe D(p,e), =(P.))= and D(p, C) = ,)
The motivation behind the last definition is that it satisfies the following pair of properties.
Lemma 2.2 (weak triangle (42).. Let X, D, and r be as defined in Definition 2.1 Then D satisfies the following ("weak triangle") inequalities (i)-ii) for every p, 9, E X:
(i) For = max(2 1}, D(p. 9) & p(D(p, c) + D(c, 4)).
(ii) For (4r 4) D(p,c) (( <D(p. B(p.c)
In the rest of the paper, for an integer n 2 we denote [n] = {1,...,nn] n). Also, unless otherwise stated D, X, r are as stated in Definition 2.1
For both the line-sets clustering and the colored-sets clustering problems/ccoresets, the input is set of n sets, each of size m. We call it (n, m)-set for short as follows.
Definition 2.3 (1,, m))set). For a given integer mn 1, m-set P a of m items, i.e. |P| m. For an additional integer n 2 1, an (n, m)-ttt is a set of n m-sels.
Definition 2.4 ((1, mooordeded--st) An m-ordered set P is an ordered-set of m 2 1 points in X. An (n, -o)orrdere-- is a set of n 2 wn-ordered-sets.
Informally, robust median for optimization problem at hand is an element b that approximates the optimal value of this optimization problem, with some leeway on the number of input elements considered. In the context of facility location, the facility (center) needs to serve only subset of the closest clients (input points).
Let P be an (n, m)-set, C' C X' and y E (0, 1]. We denote by closest (P, C.T) the set that is the union of [P]]] sets P E P with the smallest value of D(P,C),ic i...
closest (P,C,))
arg min
Σ D(P.C).
@CP: Q| PEQ
5

---

proj
proj(
proj(
proj(
(a)
(b)
(c) k=
(d) k =2
Figure Example sets projections for Definition 2.7 (a) The projection Pf (top 5 points) onto the ordered
set = (red stars) yields [PP, B) (5 dark blue points), ie., the union of 3 points proj(P: (3) (3 on the
=/ (top / lines) onto the ordered set (red stars) yields TLL B) (5 dark blue lines), T.e., the union of 3 lines proj( B) (translated to to the stars) with the 2 remaining lines proj L, B). Colored-set k-clustering: The inputt is
stars) with the remaining points proj P, B). (b) The projection
n. 5 pairs of points that correspond home/work addresses (in blue and black). [c]] center, which a restaurant (black fork and knife). Its distance to a person is the distance to her office (black suitcase). [d] = 2 centers: a restaurant (black fork and knife) and grocery shop (blue cart). Each person chooses the closest restaurant to her office or the closest grocery to her home.
For simplicity of notation, define closest(P, C) closest(P, C, (P)) one of the closest items C' in P. Here and the rest of the paper ties are broken arbitrarily. Definition 2.5 (Robust median [66). Let P be an (n, me) in X, y E (0, 1], and
D' = minsEx Epeckoeent(P (P.b),n)
D(P,b).
For E (0, and a 2 0, point b E X is a (1, T. a) -eedam for P if
Exectooss PP (P.0))
D(P,b)
(P,7).
Definition 2.6 (Translation). Let be point in X. Than (i) For every p X, define T(p, b) = b.
and (fi) If X IRd for every line e in Rd we define T(e, b) to be line parallel to E that intersects b. In what follows, we define the projection of set (points or lines) over set of points; see Fig. 3
Definition 2.7 (Set projection). Let m. be a pair of integers such that S j I m. Let P be either an m-set of points X or an in-set of lines in X Rdd Let B (bi,..., ... by) be ordered j-set of points in X. Let E P denote the closest item {pi} = closest {b) ) to by. For every inleger i (2, .......7 .....--j] j}, recursively define pi be the closest item {p:} closest {pI (pI.-...P--11) (b:))
in P (PI,.... -P--13 } to by. We denote,
(i) (Po B) = (T(pi, bi),... T(pj, b,)} as the j items in P that were projected onto B. (ii) proj (), = P\ (PI.....,P.. .P}} as the m - items in P that were not projected onto B. (iil) T(P.B) PPoj(P, U (Poj((P as the projection of P onto B
(iv) For projection over empty define proj(P, 0) T(P.0) = P.
3 Sensitivity
Our main coreset construction (Algorithm 4 is a standard non-uniform sampling algorithm based on Feldman-Langbery framework [14]. The main challenge in this framework is to compute the importance of each input set, known as sensitivity. Our main contribution is an algorithm that computes this sensitivity with provable guarantees its running time and the total sensitivity, which implies the size of the resulting coreset.
As explained in the novelty section, we provide coreset construction for line-sets, by bounding sensitivity of constant fraction of the input lines recursively. Section 3.2 provides sensitivity bound for lines-sets clustering, by translating the input lines into robust medians, converting the translated lines into colored points, and then compute sensitives for colored-sets as Section 3.1
Definition 3.1 (Line-set Sensitivity). Let C be an (n, m)-set of lines in TRd and let l 2 1 be an integer. We define the sensitivity of every such set L E L of lines be
DLL C) CCRA,ICI= Evec D(L
Sc.((L)
sup
where the supremum is over every set C of k points in Hd such that D(L, C) 0.

---

3.1 Colored sets
In this subsection, we bound the sensitivity for the colored sets clustering. Here, the input a P of n m-ordered-sets (the order resembles the colors of the points) in a metric space (X', d) equipped with distance function D, and an integer A: 2 1. The goal is to compute a colored set CC X x [m] of k pairs, each consisting to the sets. Here, the distance to each ordered-set P E P is the minimum distance from center in C to point P which has the same color,
point and index (color) in [m] that minimizes the sum distances
E arg min C' C'cxx(m),IC'== Pm))
Σ
min Dtc, (c.0)EC"
Example. Suppose we want to provide convenient food source for workers whose home and work addresses are represented by pairs of GPS coordinates (points on the plane). Each person can either buy ingredients lunchtime; see Fig
grocery and make a lunch box at home, or go to a restaurant during
In order make the reduction to sets of lines, we need coreset for this problem that supports weights. Hence, we define the weighted version of this problem.
Definition 3.2 (weighted colored center). A weighted colored center in X is triplet (c, 1), where e E X, w 2 0, and Z an integer. We define the weighted distance from an m-ordered set P (1), - Pm) to colored weighted center é' = (c, w. 1) to be [ D(pr,
ift m
D(P,c) = D(P. (c,ww, 1
otherwise
The distance between a finite set C of weighted colored centers, and an m-ordered-set P is defined by D(P, C) = min D(P,c) c'), and the cost between and an (n, m))derereed set P is the sum D(P.C) = -P.C)=EPEP D(P.C).C))..
Overview of Algorithm Given a set P of m-ordered-sets and an integer k 2 1. Algorithm 1 computes a set 1 of center points (used only for the analyses) and set P C P of "similar" m-ordered-sets, which are approximately equally important for the problem at hand; see Lemma 3.3
On the E-th iteration of the external loop (Line 2 the algorithm computes fraction of O p m-sets from P that are similar in the sense that there are m dense balls of small radii, each contains at least one point from each set.
Algorithm 1: CS CS-DENSE(P, k)
Input An (n, m) mnddredered-set P in X. and integer k 1. Output A pair (P BTT) where Pm and B X x [m] ; see Lemma 3.3
1
Pf P: 0:
20
2 for : 1 to do
for == to do
P Proj( PP B
(PPEP--)] // see Definition 2.7
Compute 2h
2
median by. E [m (e 1)] for p--1 P
// see Definition 2.5 and suggested implementation in Algorithm
Pf = P
proj(P, R. E closest P (b)) 1-7 4k
11 Pf contains every m-set P such that proj B is the fraction of the closest (1 -)k(k) seta in p' to the center b,; see
Definition 2.7
B = B ( b
P = P." : D
Return (P 8T)
Lemma 3.3 (sensitivity of colored-sets). Let be an (n,, orddered--- in X, k > 1 be an integer,
and let (Pm BTT be the output of call to CS- CS-DENSE(P. k); see Algorithm 1. Then [P E O (n), and for every set P E Pm and set C X [0, oc) x [m] of [C| weighted colored centers
such that D(P, C)
have
D(P.C)
< 28
Epep D(P'.))
P

---

3.2 Line-sets
Overview of Algorithm
2
Given an (m, m))-stttttteseee C of lines, and set B C 1ed that both satisfy the condition
of Lemma C.4 and an integer & 2 1. Algorithmooutphe outputs a function 8 & - [0. xc) that maps every set L E C. of lines upper bound s(L) of its sensitivity. This is done by reduction colored-sets clustering. Intuitively, the distance between projected set of lines (see Fig. (a) and a center can be approximated by a distance between colored set and a set of colored centers (projections the original center) as shown in Fig.
Algorithm GROUPED GROUPED-SENSITIIEE (C, B)k)
Input :An integer & 2 1, an (n,,m) msstttstttt of lines, and set (bi..... .o......bm) yn points both R such that for every set L = (f1.....fm) E and every E [m]] the line & intersects by. Output :A sensitivity function s: L + [0, 00), for every set L E L. Line 1
every E [rm], set 8 = {ar E R || bil 1}
For every L E L. set P(L) == (4, n S. A 2m-ordered set
3 p: {P(L) L/// An (n, 2m) -- ordered set 2mak
while [P] , = CS-DENSE(P, / see Algorithm
5
for every P E pm do
2mk
(P())= = [P:
// see Lemma 3.3
: P(PP""
9 for every Q P do
Line 5
10
sQ) ;
11 for every LE L do s(L) = (2
12 Return
Overview of Algorithm Given an (n, m))-st C of lines, and an integer 2 1, Algorithm B Doutputs pair of sets (Lm+1 )T) All the m-sets in g are similar in the sense that their sensitivity with respect original problem is small and equal. The algorithm consists of two parts. The first part (Lines extracts a subset of the original data that can be "grouped" (see Fig, 2(a) with little effect the sensitivity related to the original set. The second part (Lines 9-10), uses Algorithm to extract the biggest subset of this subset whose sensitivity can be bounded.
Algorithm 3: L.S-DENS((C,)
Input An (n, m)eset & and an integer k 2 1. Output: A pair
Line
where L C L and 8mh C Rd ordered set.
1
IT:= := 20
L = = :
for : to m do
Line
Compute 2k 7,4 4
median b' E Rd for L
// Algorithm for suggested implementation
L = ( (
proj(I, B cloarst E 1, (b) 1
Line
B = BB Ufb
;i-1; = (proi(L, B C see Fig 3
L = [proj(L, BTTh L L
= COOUUPDD-SENSTIVIVVCC. DT //// see Algorithm c is set of sets
L +1+ = aig
Line
LEE"
// biggest cluster whose sets have equal sensitivity
Return (Lm+1,
Lemma 3.4. Let C be an (n, m)--et of lines in Rd, and 2 be an integer. Let (cm+1 1 be the output of a call to LS-DENSE k); see Algorithm 3 Then, for every L E Lm+11 we have (L,((L) E O(k)

---

From Sensitivity to Coreset
As previously stated, there are many frameworks (such as [1] which provide coreset given an upper bound of the sensitivity as in Lemma an3 and upper bound for the VC-dimension as given in Section B In what follows we present a general algorithm that uses such a framework.
Overview of Algorithm 4 Given an (n, m)-set of lines in F an integer k 2 1, an error parame- ter E E (0, 1). and a probability of failure E (0, 1), Algorithm 4 computes E-coreset (C, v) for L. First, the algorithm (Lines 1-7) recursively extracts subset with known sensitivities using LS- LS-DENSE until all sets are assigned a sensitivity, then calls an existing framework to compute the coreset (Line 8).
Algorithm 4: CORESET(L, k. n);; see Theorem 4.1
Input
An (n, m) & of lines in R", positive integer 2 1, desired coreset size r) 1.
Output
A pair (C, v), where C & and
0o).
2
c"-1
while
2. do
(cm=1
8T7) LS-DENSE( k)// see Algoritha
every L 1m
e(L) Lm+1
C C c
for every L do L) =1
(C, v) : CORESET (W(C, 8,4)// aee Algorithm Return(C, v)
Theorem 4.1. Let C be an (n, me- of lines in Rd, k 1 be an integer. E, (0, 1), and let
yo oog ) (2k) + logz (1) be integer, where is sufficiently large constant that can be determined from the proof. Let (C, u) be the output of a call to CORESET k, 1)); see Algorithm
n
in the Appendix. Then, Claims (i)- hold as follows.
(i) With probability at least 1 5. (C, v) is an E-coreset of for the k-line-sets of size |C|
(ii) The pair (C,u) can be computed n log(n) (2k) (mm)) time.
By modifying 3f Algorithm 4 to call CS-DENSE rather than LS-DENSE, as well as straight- forward modifications over the input, one can achieve coreset construction for Colored-sets clustering as follows.
Theorem 4.2. Let k, m 2 be constant integers, let P be an (n, ord-ordeed--se set in Rd. E, E (0, 1), mn' "llgn (2k) + logg (1) be integer, where is sufficiently large constant that can be determined from the proof. There is an algorithm that given P, ke and 8 returns with probability at least 8 an e-coreset of for colored-sets k-mean of size n in (2k()) ((mk)
and let 1
time.
Experimental Results
We implemented our coreset construction algorithms for both Colored-sets and Line-sets. In this section we test there empirical performance on synthetic and real data. Open source available in (32). Since provide the first coreset construction for the given problems, we compare our results to a single baseline a random uniform sampling of the same number points as in the coreset. Except for the case of (n, 1) -s-sets of lines where also compare to the existing coreset for lines k-mean 355
Colored-sets data-sets
(i A synthetic dataset of size 10000 with outliers by sampling colored points from set of Gaussians with different parameters corresponding to different colors. For each color there are two overlapping Gaussians for modeling the inliers of size 4950 each and one Gaussian more than three standard deviations away of size 100 for modeling the outliers.
(ii) The Reuters-21578 data-set from 330, which results in sets of points corresponding to each paragraph each document. Additionally we divide paragraphs into categories: beginning (first third), main part (middle third) ending (last third). This results in each document being represented as a set of m=3 colored points corresponding to sets of paragraphs of different categorics.

---

08 (1) m 2,k
DB Gii m - 3, m
D6 (R)
DB (ii) m 3, k
Croer neto (ens
Connent
Crrer repctio))
Connect
Ereer neto repstaen)
Connect
Connect
unitarm sampling
Untomm sampling Nul cala
untorm sampling
Unformm sampling Fall dula
hul cata
hull dota
2.0-
0.0
Sample
DB (MI1
(tv) 2,
DB (Iv]
DB (Ivi
k
Dro cogr-atte (reaton)
Undoorm sampling
Emer matte cepattonn
unioom
Uniform sampling
unformm sampling
full date
Full
Fall data
12a
127
10"
12"
10
12'
10
101
10
307
102
Sample Sibe
Sample tite (II)
Sample size
Sample $2e
(iI))
Connat has dumsrng
Crnatt dureting
167 Sample sizo
Sumple size
Figure 4: Experimental results. See detoils in Section
Line-sets data-sets
(iii) A synthetic dataser that consists of the colored points dataset from the previous section, after removing the colors from the points. Each point was then turned into a line by assigning it to random direction according to similar mixture of Gaussians.
(iv) We used California housing prices data-set (37 in witch we introduced uncertainty by removing two of the 9 dimensions each point. We removed one discrete value which created sets and one continuous value which created the lines.
The experiment. For each data set, and for different values of m, k, we conduct the following experiments. For every E (10- 2 a coreset (a) of size a using our algorithm, a uniform sample (2(a) of the data-set of size a, and for the corresponding experiments coreset Sa(a) of size a using 335 Then we generated a set Q, |Q] = 500 queries: half of them are k-means that were computed using generalization of the EM heuristic, and the rest were randomly and uniformly sampled from the ground set. Finally, for every i E {1,2} we computed the maximum approximation error
Erep D(S Q) - -rer D(P,Q)
S,,e(()) max
QE
ΣrEo D(P,Q)
Results for the corresponding databases (i)-(iv) are shown in Fig.
Discussion Our coresets out-preform uniform sampling in most of the experiments. As expected, when the data is uniformly distributed, the sensitivity of each point is close, and uniform sampling is already coreset. Increasing is and m yields more isolated clusters, which explains why the error for the uniform samplings becomes higher compared to the coreset's 's error. As is in previous paper, the empirical error very small compared to the theoretical worst-case bounds, even for small coresets.
Conclusion and Future Work
The paper suggests the first coresets for 1: line-sets clustering via a reduction to coresets for colored- sets clustering of independent interest. We expect that this paper will open line of research for many possible directions. For example, projectivedd clustering of sets. That is, replacing the outputted point centers by A linear subspaces of Rdd each of dimension j 2 1. Another direction is to handle inputs sets of subspaces, each of dimension j > 1. Extending non-linear shapes is another direction. Although, the main contribution of this paper is the theoretical breakthrough and results. However, we also expect that our code can be extended and applied for real-wor wallworld systems that have similar problems, such as [4 34].
10

---

References
[1] K. Agarwal, G. Cormode, Z. Huang. M. Phillips, Z. Wei, and K. Yi. Mergeable summaries.
ACM Transactions Database Systems (TODS), 38(4):1-28, 2013.
[2] S. Alipour. Approximation algorithms for probabilistic k-center clustering. In 2020 IEEE International Conference on Data Mining (ICDM). pages 1-11, 2020.
[3] M. Anthony and P. L.. Bartlett. Neural network learning: Theoretical foundations. Cambridge University press, 2009.
[4] D. Arthur and S. Vassilvitskii. How slow is the k-means method? In Proceedings of the secnny annual symposium on Computational Geometry (SoCG), pages 144-153, 2006.
[5] D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. Technical report, Stanford, 2006.
[6] H. Azzag, G. Venturini, A. Oliver, and C. Guinot. hierarchical ant based clustering algorithm and its use in three real-world applications. European Journal of Operational Research, 179(3):906-922 922006992222222 2007.
[7] A. Barger and D. Feldman. Deterministic coresets for k-means of big sparse data. Algorithms, 13(4):92, 2020.
[8] Bartolozzi, A. de Gaetano, E. Di Lena, S. Marino, L. Nieddu, and G. Patrizi. Operational research techniques in medical treatment and diagnosis: A review. European Journal of Operational Research, 121(3):335446, 2000.
[9] V. Braverman, D. Feldman, and H. Lang. New frameworks for offline and streaming coreset constructions. arXiv preprint arXiv:1612.00889 2016.
[10] V. Braverman, S. Jiang, R. Krauthgamer, and X. Wu. Coresets for clustering with missing values. Advances Neural Information Processing Systems (Neur[PS), 14:17660-17372 2021.
[11] V. Braverman, S. H.-C. Jiang, R. Krauthgamer, and X. Wu. Coresets for ordered weighted clustering. In International Conference on Machine Learning (ICML), pages 744-753. PMLR, 2019.
[12] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 30. Curran Associates, Inc., 2017.
[13] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. new coreset framework for clustering. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing (STOC), pages 169-182, 2021.
[14] D. Feldman, Kfir, and X. Wu. Coresets for gaussian mixture models of any shape, 2019.
[15] D. Feldman and M. Langberg. unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing (STOC), pages 569-57 578,, 2011.
[16] D. Feldman and L. J. Schulman. Data reduction for weighted and outseer-reistant clustering. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1354.1354. SIAM, 2012.
[17] Gao, M. Langberg, and L. Schulman. Clustering lines in high-dimensional space: Classifi- cation of incomplete data. ACM Trans. Algorithms, 7(1), Dec. 2010.
[18] A. Geiger, Ziegler, and C. Stiller. Stereoscan: Dense 3d reconstruction in real-time, In 2011 IEEE intelligent vehicles symposium (IV), pages (68-968.77 IEEE, 2011.
[19] S. Har-Peled. Coresets for discrete integration and clustering. In International Conference Foundations of Software Technology and Theoretical Computer Science, pages 33 33-44. Springer, 2006.
11

---

[20] J. A. Hartigan and M. A. Wong. Algorithm as 136: A k-means clustering algorithm. Journal of the royal statistical sociery. series c (applied statistics), 28(1):100-188 1979.
[21] L. Huang and N. K. Vishnoi. Coresets for clustering in euclidean spaces: Importance sampling is nearly optimal. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1416-1429, 2020.
[22] S. Izadi, D. Kim, O. Hilliges, D. Molyneaux, R. Newcombe, P. Kohli, J. Shotton, S. Hodges, D. Freeman, A. Davison, al. Kinectfusion: real-time 3d reconstruction and interaction using a moving depth camera. In Proceedings of the 24th annual ACM symposium User interface software and technology. pages 559-568, 2011.
[23] M. Joseph, M. Kearns, Morgenstern, and A. Roth. Fairness in learning: Classic and contextual bandits. arXiv preprini arXiv: 2016.
[24] I. Jubran, F, Fares, Y. Alfassi, F, Ayoub, and D. Feldman. Newton-pnp: Real-time visual navigation for autonomous toy-drones. arXiv preprint arXiv:2203.02686, 2022.
[25] I. Jubran, E. E. S. Shayda, I. Newman, and D. Feldman. Coresets for decision trees of signals. In Thirty-Fifth Conference on Neural Information Processing Systems (NeurIPS), 2021.
[26] I. Jubran, M. Tukan, A. Maalouf, and D. Feldman. Sets clustering. International Conference on Machine Learning (ICML), 2020.
[27] T. Kamishima, S. Akaho, H. Asoh, and J. Sakuma. Fairness-aware classifier with prejudice remover regularizer. In Joint European Conference on Machine Learning and Knowledge Discovery Databases, pages 35-50. Springer, 2012.
[28] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu. local search approximation algorithm for k-means clustering. Computational Geometry, 28(2-3):89-11 112,, 2004.
[29] M. Langberg and L. J. Schulman. Universal e-approximators for integrals. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 598-607. SIAM. 2010.
[30] D. Lewis. Reuters-2151 text categorization test collection, distribution 1.0. http: // www. research. att. com 1997.
[31] J. Li. W. Wu, T. Wang, and Y. Zhang. One step beyond histograms: Image representation using markov stationary features. In 2008 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 1-8, 2008
[32] S. Lotan, E. E. S. Shayda, and D. Feldman. Coreset for lines sets clustering open source code. https: //g1 thub. com/ http:///eeetttooccaa//sseeooeaae 1iwe clusterin 2022.
[33] M. Lucic, O. Bachem, and A. Krause. Strong coresets for hard and soft bregman clustering with applications to exponential family mixtures. In Artificial intelligence and statisties (AISTAT), pages 1-9, PMLR, 2016.
[34] A. Maalouf, I. Jubran, and D. Feldman. Fast and accurate least-mean-squares solvers. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[35] Y. Marom and D. Feldman. k-means clustering of lines for big data. In Advances in Neural Information Processing Systems (NeurIPS), pages 12817-12826, 2019.
[36] R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy. The effectiveness of lloyd-type methods for the k-means problem. Journal of the ACM (JACM), 1-22 2013.
[37] R. K. Pace and Barry. California housing daasst..attps//ssiiitlleeen htt.aaaataaaatttaaaoaoaaaaaaaaaa
/ htw.::ackiii.tlle.m....ooaaaaaaa stable/
1997.
12

---

[38] G. Rosman, M. Volkov, D. Feldman. J. W. Fisher III, and D. Rus. Coresets for k-segmentation of streaming data. In Z. Ghahramani, M. Welling, C. Cortes, Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 27. Curran Associates, Inc., 2014.
[39] M. Schmidt, C. Schwiegelshohn, and C. Sohler. Fair coresets and streaming algorithms for fair k-means. In International Workshop Approximation and Online Algorithms, pages 231-251. Springer, 2019.
[40] X. Shen, W. Liu, I. Tsang, F. Shen, and Q.-. Sun. Compressed k-means for large-scale clustering. In Thirty-first AAAI conference on artificial intelligence, 2017.
[41] C. Sohler and D. P. Woodruff, Strong coresets for k-median and subspace approximation: Goodbye dimension. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 802-813 813. IEEE, 2018.
[42] A. Statman, L. Rozenberg, and D. Feldman. k-means+++: Outliers-rsisttnt clustering. Algo- rithms, 13:311, 11 2020.
[43] A. Vattani. K-means requires exponentially many iterations in the plane. Discrete & Computational Geometry, 5564):596-616, 2011.
13


Reviews:
[{"review_id": "X1YgTE7geyl", "reviewer": "Reviewer_KAjB", "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.\n \n", "questions": "Could the authors explain why the algorithms work? E.g., \n- What is the intuition behind Lemma 3.4?\n- How to obtain the coreset size in Theorem 3.5 from Lemma 3.4?", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nMy main concerns are the writing and the significance.\n- 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.\n- 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.\n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nThanks for the response. The revised pdf is better in writing. I raise my score accordingly.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RvU4LBfoqKR", "reviewer": "Reviewer_y2Tf", "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.\n\nEven 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.\n\nThe 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.\n\nThis 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.\n\nExperiments 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.\n", "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.\n\n2. 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?\n\nMinor comments:\n\n1. Line 211: “Langberg-Feldman” -> “Feldman-Langberg”\n2. Line 246: “lth”->’l-th”\n3. Line 4 of algorithm 1, it’s better to use \\mid in the set notation – currently the spacing is too small.\n4. Line 260, “that are both satisfy” -> “that both satisfy”\n", "limitations": "Yes, and it has been discussed in the checklist.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe paper is well written and a comparison with previous works seems to be comprehensive.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1U9YBBX1F_s", "reviewer": "Reviewer_fpBB", "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.", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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. \n\nThe 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).\n\nA 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept