Local Algorithms for Finding Densely Connected Clusters

• URL: http://arxiv.org/abs/2106.05245v1
• Date: Wed, 9 Jun 2021 17:40:45 GMT
• Title: Local Algorithms for Finding Densely Connected Clusters
• Authors: Peter Macgregor and He Sun
• Abstract summary: Local graph clustering is an important technique for analysing massive graphs. Recent studies highlight the importance of the inter-connection between clusters when analysing real-world datasets.
• Score: 3.2901541059183432
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most (local) graph clustering algorithms is to find a vertex set of low conductance, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study local algorithms for finding a pair of vertex sets defined with respect to their inter-connection and their relationship with the rest of the graph. The key to our analysis is a new reduction technique that relates the structure of multiple sets to a single vertex set in the reduced graph. Among many potential applications, we show that our algorithms successfully recover densely connected clusters in the Interstate Disputes Dataset and the US Migration Dataset.

Related papers

• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering. Models estimate an initial graph beforehand to apply GCN. Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
  arXiv  Detail & Related papers  (2024-02-25T07:03:37Z)
• DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization [5.329981192545312]
  We propose a novel method, DGCluster, which primarily optimize the modularity objective using graph neural networks and scales linearly with the graph size. We extensively test DGCluster on several real-world datasets of varying sizes, across multiple popular cluster quality metrics. Our approach consistently outperforms the state-of-the-art methods, demonstrating significant performance gains in almost all settings.
  arXiv  Detail & Related papers  (2023-12-20T01:43:55Z)
• 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)
• On Learning the Structure of Clusters in Graphs [3.8073142980733]
  In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently.
  arXiv  Detail & Related papers  (2022-12-29T15:26:19Z)
• A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource [87.7460720701592]
  This paper introduces formulaic definition, evaluation, and development in this field. The taxonomy of deep graph clustering methods is presented based on four different criteria, including graph type, network architecture, learning paradigm, and clustering method. The applications of deep graph clustering methods in six domains, including computer vision, natural language processing, recommendation systems, social network analyses, bioinformatics, and medical science, are presented.
  arXiv  Detail & Related papers  (2022-11-23T11:31:11Z)
• GLCC: A General Framework for Graph-level Clustering [5.069852282550117]
  This paper studies the problem of graph-level clustering, which is a novel yet challenging task. We propose a general graph-level clustering framework named Graph-Level Contrastive Clustering (GLCC) Experiments on a range of well-known datasets demonstrate the superiority of our proposed GLCC over competitive baselines.
  arXiv  Detail & Related papers  (2022-10-21T11:08:10Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  We present two-time approximation algorithms for hierarchical clustering. The significance of our work is demonstrated by the empirical analysis on both synthetic and real-world data sets.
  arXiv  Detail & Related papers  (2021-12-16T17:52:04Z)
• Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
  We propose a novel unsupervised graph representation model by contrasting cluster assignments, called as GRCCA. It is motivated to make good use of local and global information synthetically through combining clustering algorithms and contrastive learning. GRCCA has strong competitiveness in most tasks.
  arXiv  Detail & Related papers  (2021-12-15T07:28:58Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Higher-Order Spectral Clustering of Directed Graphs [8.997952791113232]
  Clustering is an important topic in algorithms, and has a number of applications in machine learning, computer vision, statistics, and several other research disciplines. We present a nearly-linear time algorithm for digraph clustering, and show that our proposed algorithm can be implemented in sublinear time under reasonable assumptions.
  arXiv  Detail & Related papers  (2020-11-10T13:06:37Z)

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.