flow-based clustering and spectral clustering: a comparison

• URL: http://arxiv.org/abs/2206.10019v1
• Date: Mon, 20 Jun 2022 21:49:52 GMT
• Title: flow-based clustering and spectral clustering: a comparison
• Authors: Y. SarcheshmehPour, Y. Tian, L. Zhang, A. Jung
• Abstract summary: We study a novel graph clustering method for data with an intrinsic network structure. We exploit an intrinsic network structure of data to construct Euclidean feature vectors. Our results indicate that our clustering methods can cope with certain graph structures.
• Score: 0.688204255655161
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose and study a novel graph clustering method for data with an intrinsic network structure. Similar to spectral clustering, we exploit an intrinsic network structure of data to construct Euclidean feature vectors. These feature vectors can then be fed into basic clustering methods such as k-means or Gaussian mixture model (GMM) based soft clustering. What sets our approach apart from spectral clustering is that we do not use the eigenvectors of a graph Laplacian to construct the feature vectors. Instead, we use the solutions of total variation minimization problems to construct feature vectors that reflect connectivity between data points. Our motivation is that the solutions of total variation minimization are piece-wise constant around a given set of seed nodes. These seed nodes can be obtained from domain knowledge or by simple heuristics that are based on the network structure of data. Our results indicate that our clustering methods can cope with certain graph structures that are challenging for spectral clustering methods.

Related papers

• Enhancing cluster analysis via topological manifold learning [0.3823356975862006]
  We show that inferring the topological structure of a dataset before clustering can considerably enhance cluster detection. We combine manifold learning method UMAP for inferring the topological structure with density-based clustering method DBSCAN.
  arXiv  Detail & Related papers  (2022-07-01T15:53:39Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
  Cut-based directed graph (digraph) clustering often focuses on finding dense within-cluster or sparse between-cluster connections. For flow-based clusterings the edges between clusters tend to be oriented in one direction and have been found in migration data, food webs, and trade data.
  arXiv  Detail & Related papers  (2022-03-02T20:07:04Z)
• Improving Spectral Clustering Using Spectrum-Preserving Node Reduction [1.52292571922932]
  We use spectrum-preserving node reduction to accelerate eigen-decomposition and generate concise representations of data sets. The experimental results show dramatically improved clustering performance when compared with state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-10-24T01:43:12Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  We propose a novel attributed graph clustering network, namely Self-supervised Contrastive Attributed Graph Clustering (SCAGC) In SCAGC, by leveraging inaccurate clustering labels, a self-supervised contrastive loss, are designed for node representation learning. For the OOS nodes, SCAGC can directly calculate their clustering labels.
  arXiv  Detail & Related papers  (2021-10-15T03:25:28Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Biclustering with Alternating K-Means [5.089110111757978]
  We provide a new formulation of the biclustering problem based on the idea of minimizing the empirical clustering risk. We propose a simple and novel algorithm that finds a local minimum by alternating the use of an adapted version of the k-means clustering algorithm between columns and rows. The results demonstrate that our algorithm is able to detect meaningful structures in the data and outperform other competing biclustering methods in various settings and situations.
  arXiv  Detail & Related papers  (2020-09-09T20:15:24Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• 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)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
  arXiv  Detail & Related papers  (2020-04-25T17:52:05Z)
• Robust spectral clustering using LASSO regularization [0.0]
  This paper presents a variant of spectral clustering, called 1-spectral clustering, performed on a new random model closely related to block model. Its goal is to promote a sparse eigenbasis solution of a 1 minimization problem revealing the natural structure of the graph.
  arXiv  Detail & Related papers  (2020-04-08T07:12: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.