We initiate the study of coresets for clustering in graph metrics, i.e., the shortest-path metric of edge-weighted graphs. Such clustering problems (on graph metrics) are essential to data analysis and used for example in road networks and data visualization. Specifically, we consider @math -Clustering, where given a metric space @math , the goal is to minimize, over all @math -point center sets @math , the objective @math . This problem is a well-known generalization of both k-Median ( @math ) and k-Means ( @math ). A coreset is a compact summary of the data that approximately preserves the clustering objective for every possible center set. Coresets offer significant efficiency improvements in terms of running time, storage, and communication, including in streaming and distributed settings. Our main result is a near-linear time construction of a coreset of size @math for @math -Clustering in a graph @math whose treewidth is @math . The construction is based on the framework of Feldman and Langberg [STOC 2011], and our main technical contribution, as required by this framework, is a uniform bound of @math on the shattering dimension under any point weights. Previously, the only construction applicable to graph metrics, even for @math , was a generic one with size @math where @math [Feldman and Langberg, STOC 2011]. We complement our construction with an @math size lower bound, which matches our construction's linear dependence on @math . This further provides the first proof that the @math factor in the generic upper bound is indeed necessary, and also justifies restricting the graph topology.
Coresets for clustering in Euclidean spaces @math have been well studied. @cite_3 constructed the first strong coreset for both and with an exponential size dependence on @math . @cite_12 improved the dimensionality dependence to be polynomial for both and . @cite_32 designed coresets for with size independent of @math . @cite_38 generalizeed this result to . Recently, coreset for generalized clustering objective receives attention from the research community, for example, @cite_19 obtained simultaneous coreset for . For another special case @math , which is the clustering, an @math -coreset of size @math can be constructed in near-linear time @cite_13 @cite_26 . Many NP-hard graph optimization problems may be solved in polynomial time or even linear time in bounded treewidth graphs, including maximum independent set, hamiltonian path and chromatic number @cite_8 @cite_23 @cite_6 . The main approach to solving these problems is dynamic programming. Generally, Courcelle's Theorem @cite_4 states that any graph optimization problem that can be described by Monadic Second-Order Logic is solvable in linear time in bounded treewidth graphs.
@cite_38 @cite_26 @cite_4 @cite_8 @cite_32 @cite_3 @cite_6 @cite_19 @cite_23 @cite_13 @cite_12
2963702702 2964292545 2229238337 1992598798
We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of Kahn's result that a disjoint union of copies of Kd;d maximizes the number of independent sets of a bipartite d-regular graph, Galvin and Tet ali's result that the independence polynomial is maximized by the same, and Zhao's extension of both results to all d-regular graphs. For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a union of copies of Kd;d. Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstrom. In probabilistic language, our main theorems state that for all d-regular graphs and all �, the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity � are maximized by Kd;d. Our method involves constrained optimization problems over distributions of random variables and applies to all d-regular graphs directly, without a reduction to the bipartite case. Using a variant of the method we prove a lower bound on the occupancy fraction of the hard-core model on any d-regular, vertex-transitive, bipartite graph: the occupancy fraction of such a graph is strictly greater than the occupancy fraction of the unique translationinvariant hard-core measure on the infinite d-regular tree We consider the problem of clustering a graph @math into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables @math , where @math is the incidence matrix of a graph @math , @math is the vector of unknown vertex variables (with a uniform prior), and @math is a noise vector with Bernoulli @math i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of @math is possible if and only the graph @math is connected, with a sharp threshold at the edge probability @math for Erdős-Renyi random graphs. The first goal of this paper is to determine how the edge probability @math needs to scale to allow exact recovery in the presence of noise. Defining the degree rate of the graph by @math , it is shown that exact recovery is possible if and only if @math . In other words, @math is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph @math , defining the degree rate as @math , where @math is the minimum degree of the graph, it is shown that the proposed method achieves the rate @math , where @math is the spectral gap of the graph @math . @d can be approximated up to (1 + e)-factor, for an arbitrary small e > 0, using the O(k e2)-rank approximation of A and a constant. This implies, for example, that the optimal k-means clustering of the rows of A is (1 + e)-approximated by an optimal k-means clustering of their projection on the O(k e2) first right singular vectors (principle components) of A. A (j, k)-coreset for projective clustering is a small set of points that yields a (1 + e)-approximation to the sum of squared distances from the n rows of A to any set of k affine subspaces, each of dimension at most j. Our embedding yields (0, k)-coresets of size O(k) for handling k-means queries, (j, 1)-coresets of size O(j) for PCA queries, and (j, k)-coresets of size (log n)O(jk) for any j, k ≥ 1 and constant e e (0, 1 2). Previous coresets usually have a size which is linearly or even exponentially dependent of d, which makes them useless when d n. Using our coresets with the merge-and-reduce approach, we obtain embarrassingly parallel streaming algorithms for problems such as k-means, PCA and projective clustering. These algorithms use update time per point and memory that is polynomial in log n and only linear in d. For cost functions other than squared Euclidean distances we suggest a simple recursive coreset construction that produces coresets of size The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C 1,…,C k ⊆P such that @math is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results. The first result is a sublinear-time (4+e)-approximation algorithm for the min-sum k-clustering problem in metric spaces. The running time of this algorithm is @math for any constant k and e, and it is o(n 2) for all k=o(log n log log n). Since the full description size of the input is Θ(n 2), this is sublinear in the input size. The fastest previously known o(log n)-factor approximation algorithm for k>2 achieved a running time of Ω(n k ), and no non-trivial o(n 2)-time algorithm was known before. Our second result is the first pass-efficient data streaming algorithm for min-sum k-clustering in the distance oracle model, i.e., an algorithm that uses poly(log n,k) space and makes 2 passes over the input point set, which arrives in form of a data stream in arbitrary order. It computes an implicit representation of a clustering of (P,d) with cost at most a constant factor larger than that of an optimal partition. Using one further pass, we can assign each point to its corresponding cluster. To develop the coresets, we introduce the concept of α -preserving metric embeddings. Such an embedding satisfies properties that the distance between any pair of points does not decrease and the cost of an optimal solution for the considered problem on input (P,d′) is within a constant factor of the optimal solution on input (P,d). In other words, the goal is to find a metric embedding into a (structurally simpler) metric space that approximates the original metric up to a factor of α with respect to a given problem. We believe that this concept is an interesting generalization of coresets.