Quantum Motif Clustering

• URL: http://arxiv.org/abs/2111.13222v2
• Date: Fri, 23 Jun 2023 13:49:46 GMT
• Title: Quantum Motif Clustering
• Abstract summary: We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the other two make use of quantum approximate counting, and all of them obtain square-root like speedups over the fastest classical algorithms in various settings.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the other two make use of quantum approximate counting, and all of them obtain square-root like speedups over the fastest classical algorithms in various settings. In order to use approximate counting in the context of clustering, we show that for general weighted graphs the performance of spectral clustering is mostly left unchanged by the presence of constant (relative) errors on the edge weights. Finally, we extend the original analysis of motif clustering in order to better understand the role of multiple `anchor nodes' in motifs and the types of relationships that this method of clustering can and cannot capture.

Related papers

• Revisiting the Quantum-Guided Cluster Algorithm: Improvements and Numerical Experiments [0.0]
  We study correlation-guided cluster algorithms for solving the Max-Cut problem.<n>We extend the cluster construction by incorporating next-nearest-neighbor (NNN) information.<n>We also outline an extension toward a correlation-guided Markov-chain Monte Carlo algorithm.
  arXiv  Detail & Related papers  (2026-06-01T07:41:46Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• ClusterFuG: Clustering Fully connected Graphs by Multicut [20.254912065749956]
  In dense multicut, the clustering objective is given in a factorized form as inner products of node feature vectors. We show how to rewrite classical greedy algorithms for multicut in our dense setting and how to modify them for greater efficiency and solution quality.
  arXiv  Detail & Related papers  (2023-01-28T11:10:50Z)
• DeepCluE: Enhanced Image Clustering via Multi-layer Ensembles in Deep Neural Networks [53.88811980967342]
  This paper presents a Deep Clustering via Ensembles (DeepCluE) approach. It bridges the gap between deep clustering and ensemble clustering by harnessing the power of multiple layers in deep neural networks. Experimental results on six image datasets confirm the advantages of DeepCluE over the state-of-the-art deep clustering approaches.
  arXiv  Detail & Related papers  (2022-06-01T09:51:38Z)
• Local Motif Clustering via (Hyper)Graph Partitioning [1.9121961872220465]
  We build a hypergraph and a graph model which both represent the motif-distribution around the seed node. We solve these models using sophisticated algorithms designed for (hyper)graph. Our algorithm computes communities with a motif conductance value being one third on average in comparison against the communities computed by the state-of-the-art tool MAPPR.
  arXiv  Detail & Related papers  (2022-05-11T12:16:01Z)
• 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)
• Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
  We propose a novel clustering algorithm, which con-siders the smoothness of data for the first time. Our key idea is to cluster tiny clusters, whose centers constitute smooth graphs. Although in this paper, we singly focus on multi-scale situations, the idea of data smoothness can certainly be extended to any clustering algorithms.
  arXiv  Detail & Related papers  (2020-09-10T05:21:20Z)
• KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks by Exploiting k-core Decomposition and Motifs [6.1734015475373765]
  Spectral clustering is one of the most commonly used algorithms for graph-structured data (networks) We propose an efficient graph clustering algorithm, KCoreMotif, specifically for large networks by exploiting k-core decomposition and motifs. Comparative results demonstrate that the proposed graph clustering algorithm is accurate yet efficient for large networks.
  arXiv  Detail & Related papers  (2020-08-21T12:21:05Z)
• 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)

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.