Wasserstein-based Kernels for Clustering: Application to Power Distribution Graphs

• URL: http://arxiv.org/abs/2503.14357v1
• Date: Tue, 18 Mar 2025 15:40:55 GMT
• Title: Wasserstein-based Kernels for Clustering: Application to Power Distribution Graphs
• Authors: Alfredo Oneto, Blazhe Gjorgiev, Giovanni Sansavini,
• Abstract summary: This work explores kernel methods and Wasserstein distance metrics to develop a computationally tractable clustering framework.<n>The framework is flexible enough to be applied in various domains, such as graph analysis and image processing.<n>A case study involving two datasets of 879 and 34,920 power distribution graphs demonstrates the framework's effectiveness and efficiency.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Many data clustering applications must handle objects that cannot be represented as vector data. In this context, the bag-of-vectors representation can be leveraged to describe complex objects through discrete distributions, and the Wasserstein distance can effectively measure the dissimilarity between them. Additionally, kernel methods can be used to embed data into feature spaces that are easier to analyze. Despite significant progress in data clustering, a method that simultaneously accounts for distributional and vectorial dissimilarity measures is still lacking. To tackle this gap, this work explores kernel methods and Wasserstein distance metrics to develop a computationally tractable clustering framework. The compositional properties of kernels allow the simultaneous handling of different metrics, enabling the integration of both vectors and discrete distributions for object representation. This approach is flexible enough to be applied in various domains, such as graph analysis and image processing. The framework consists of three main components. First, we efficiently approximate pairwise Wasserstein distances using multiple reference distributions. Second, we employ kernel functions based on Wasserstein distances and present ways of composing kernels to express different types of information. Finally, we use the kernels to cluster data and evaluate the quality of the results using scalable and distance-agnostic validity indices. A case study involving two datasets of 879 and 34,920 power distribution graphs demonstrates the framework's effectiveness and efficiency.

Related papers

• Faithful Density-Peaks Clustering via Matrix Computations on MPI Parallelization System [7.594123537718585]
  Density peaks clustering (DP) has the ability of detecting clusters of arbitrary shape and clustering non-Euclidean space data. We present a faithful and parallel DP method that makes use of two types of vector-like distance matrices and an inverse leading-node-finding policy. Our method is capable of clustering non-Euclidean data such as in community detection, while outperforming the state-of-the-art counterpart methods in accuracy when clustering large Euclidean data.
  arXiv  Detail & Related papers  (2024-06-18T06:05:45Z)
• Spectral Clustering for Discrete Distributions [22.450518079181542]
  Traditionally, clustering of discrete distributions (D2C) has been approached using Wasserstein barycenter methods. We show that spectral clustering combined with distribution affinity measures can be more accurate and efficient than barycenter methods. We provide theoretical guarantees for the success of our methods in clustering distributions.
  arXiv  Detail & Related papers  (2024-01-25T03:17:03Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Wasserstein $K$-means for clustering probability distributions [16.153709556346417]
  In the Euclidean space, centroid-based and distance-based formulations of the $K$-means are equivalent. In modern machine learning applications, data often arise as probability distributions and a natural generalization to handle measure-valued data is to use the optimal transport metric. We show that the SDP relaxed Wasserstein $K$-means can achieve exact recovery given the clusters are well-separated under the $2$-Wasserstein metric.
  arXiv  Detail & Related papers  (2022-09-14T23:43:16Z)
• Learning non-Gaussian graphical models via Hessian scores and triangular transport [6.308539010172309]
  We propose an algorithm for learning the Markov structure of continuous and non-Gaussian distributions. Our algorithm SING estimates the density using a deterministic coupling, induced by a triangular transport map, and iteratively exploits sparse structure in the map to reveal sparsity in the graph.
  arXiv  Detail & Related papers  (2021-01-08T16:42:42Z)
• Kernel learning approaches for summarising and combining posterior similarity matrices [68.8204255655161]
  We build upon the notion of the posterior similarity matrix (PSM) in order to suggest new approaches for summarising the output of MCMC algorithms for Bayesian clustering models. A key contribution of our work is the observation that PSMs are positive semi-definite, and hence can be used to define probabilistically-motivated kernel matrices.
  arXiv  Detail & Related papers  (2020-09-27T14:16:14Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Wasserstein Exponential Kernels [13.136143245702915]
  We study the use of exponential kernels defined thanks to the regularized Wasserstein distance. We show that Wasserstein squared exponential kernels are shown to yield smaller classification errors on small training sets of shapes.
  arXiv  Detail & Related papers  (2020-02-05T17:31:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.