Robust Markov stability for community detection at a scale learned based on the structure

• URL: http://arxiv.org/abs/2504.11621v1
• Date: Tue, 15 Apr 2025 21:16:14 GMT
• Title: Robust Markov stability for community detection at a scale learned based on the structure
• Authors: Samin Aref, Sanchaai Mathiyarasan,
• Abstract summary: We propose a principled method to select a single robust partition at a suitable scale from the multiple partitions that PyGenStability produces.<n>Our proposed method combines the Markov stability framework with a pre-trained machine learning model for scale selection.<n>We show that PyGenStabilityOne (PO) outperforms 25 other algorithms by statistically meaningful margins.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection, the unsupervised task of clustering nodes of a graph, finds applications across various fields. The common approaches for community detection involve optimizing an objective function to partition the nodes into communities at a single scale of granularity. However, the single-scale approaches often fall short of producing partitions that are robust and at a suitable scale. The existing algorithm, PyGenStability, returns multiple robust partitions for a network by optimizing the multi-scale Markov stability function. However, in cases where the suitable scale is not known or assumed by the user, there is no principled method to select a single robust partition at a suitable scale from the multiple partitions that PyGenStability produces. Our proposed method combines the Markov stability framework with a pre-trained machine learning model for scale selection to obtain one robust partition at a scale that is learned based on the graph structure. This automatic scale selection involves using a gradient boosting model pre-trained on hand-crafted and embedding-based network features from a labeled dataset of 10k benchmark networks. This model was trained to predicts the scale value that maximizes the similarity of the output partition to the planted partition of the benchmark network. Combining our scale selection algorithm with the PyGenStability algorithm results in PyGenStabilityOne (PO): a hyperparameter-free multi-scale community detection algorithm that returns one robust partition at a suitable scale without the need for any assumptions, input, or tweaking from the user. We compare the performance of PO against 29 algorithms and show that it outperforms 25 other algorithms by statistically meaningful margins. Our results facilitate choosing between community detection algorithms, among which PO stands out as the accurate, robust, and hyperparameter-free method.

Related papers

• Efficient Multi-Task Inferencing: Model Merging with Gromov-Wasserstein Feature Alignment [7.436562917907035]
  This paper introduces the Gromov-Wasserstein Scoring Model Merging (GW-SMM) method.<n>It merges models based on feature distribution similarities measured via the Gromov-Wasserstein distance.<n>We validated our approach against human expert knowledge and a GPT-o1-based merging method.
  arXiv  Detail & Related papers  (2025-03-12T19:20:33Z)
• Towards Hyper-parameter-free Federated Learning [1.3682156035049038]
  We introduce algorithms for automated scaling of global model updates. In first algorithm, we establish that a descent-ensuring step-size regime at the clients ensures descent for the server objective. Second algorithm shows that the average of objective values of sampled clients is a practical and effective substitute for the value server required for computing the scaling factor.
  arXiv  Detail & Related papers  (2024-08-30T09:35:36Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  Subset selection is a fundamental problem that can play a key role in identifying smaller portions of the training data. We develop a novel factor 3-approximation algorithm to compute subsets based on the weighted sum of both k-center and uncertainty sampling objective functions.
  arXiv  Detail & Related papers  (2023-12-17T04:41:07Z)
• Morphologically-Aware Consensus Computation via Heuristics-based IterATive Optimization (MACCHIatO) [1.8749305679160362]
  We propose a new method to construct a binary or a probabilistic consensus segmentation based on the Fr'echet means of carefully chosen distances. We show that it leads to binary consensus masks of intermediate size between Majority Voting and STAPLE and to different posterior probabilities than Mask Averaging and STAPLE methods.
  arXiv  Detail & Related papers  (2023-09-14T23:28:58Z)
• Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees [57.67528738886731]
  We study the numerical stability of scalable sparse approximations based on inducing points. For low-dimensional tasks such as geospatial modeling, we propose an automated method for computing inducing points satisfying these conditions.
  arXiv  Detail & Related papers  (2022-10-14T15:20:17Z)
• PointInst3D: Segmenting 3D Instances by Points [136.7261709896713]
  We propose a fully-convolutional 3D point cloud instance segmentation method that works in a per-point prediction fashion. We find the key to its success is assigning a suitable target to each sampled point. Our approach achieves promising results on both ScanNet and S3DIS benchmarks.
  arXiv  Detail & Related papers  (2022-04-25T02:41:46Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)
• Fast Network Community Detection with Profile-Pseudo Likelihood Methods [19.639557431997037]
  Most algorithms for fitting the block model likelihood function cannot scale to large-scale networks. We propose a novel likelihood approach that decouples row and column labels in the likelihood function. We show that our method provides strongly consistent estimates of the communities in a block model.
  arXiv  Detail & Related papers  (2020-11-01T23:40:26Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41:59Z)
• Scope Head for Accurate Localization in Object Detection [135.9979405835606]
  We propose a novel detector coined as ScopeNet, which models anchors of each location as a mutually dependent relationship. With our concise and effective design, the proposed ScopeNet achieves state-of-the-art results on COCO.
  arXiv  Detail & Related papers  (2020-05-11T04:00:09Z)
• Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic [5.395127324484869]
  SplitSGD is a new dynamic learning schedule for optimization. The method decreases the learning rate for better adaptation to the local geometry of the objective function. It essentially does not incur additional computational cost than standard SGD.
  arXiv  Detail & Related papers  (2019-10-18T19:38:53Z)

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.