Online Sparsification of Bipartite-Like Clusters in Graphs

• URL: http://arxiv.org/abs/2508.05437v1
• Date: Thu, 07 Aug 2025 14:28:44 GMT
• Title: Online Sparsification of Bipartite-Like Clusters in Graphs
• Authors: Joyentanuj Das, Suranjan De, He Sun,
• Abstract summary: We present efficient and online sparsification algorithms that find bipartite-like clusters in undirected graphs and directed ones.<n>We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms.
• Score: 4.009237266190497
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 graph clustering algorithms is to find a vertex set of low conductance, a sequence of recent studies highlights the importance of the inter-connection between vertex sets when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online sparsification algorithms that find such clusters in both undirected graphs and directed ones. We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.

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)
• Deep Temporal Graph Clustering [77.02070768950145]
  We propose a general framework for deep Temporal Graph Clustering (GC) GC introduces deep clustering techniques to suit the interaction sequence-based batch-processing pattern of temporal graphs. Our framework can effectively improve the performance of existing temporal graph learning methods.
  arXiv  Detail & Related papers  (2023-05-18T06:17:50Z)
• 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)
• Hub-aware Random Walk Graph Embedding Methods for Classification [44.99833362998488]
  We propose two novel graph embedding algorithms based on random walks that are specifically designed for the node classification problem. The proposed methods are experimentally evaluated by analyzing the classification performance of three classification algorithms trained on embeddings of real-world networks.
  arXiv  Detail & Related papers  (2022-09-15T20:41:18Z)
• 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)
• 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)
• Local Algorithms for Finding Densely Connected Clusters [3.2901541059183432]
  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.
  arXiv  Detail & Related papers  (2021-06-09T17:40:45Z)
• 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)
• Weighted Graph Nodes Clustering via Gumbel Softmax [0.0]
  We present some ongoing research results on graph clustering algorithms for clustering weighted graph datasets. We name our algorithm as Weighted Graph Node Clustering via Gumbel Softmax (WGCGS)
  arXiv  Detail & Related papers  (2021-02-22T05:05:35Z)
• 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)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)

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.