Topology-Guided Sampling for Fast and Accurate Community Detection

• URL: http://arxiv.org/abs/2108.06651v1
• Date: Sun, 15 Aug 2021 03:20:10 GMT
• Title: Topology-Guided Sampling for Fast and Accurate Community Detection
• Authors: Frank Wanye, Vitaliy Gleyzer, Edward Kao, Wu-chun Feng
• Abstract summary: We present an approach based on topology-guided sampling for accelerating block partitioning. We also introduce a degree-based thresholding scheme that improves the efficacy of our approach at the expense of speedup. Our results show that our approach can lead to a speedup of up to 15X over block partitioning without sampling.
• Score: 1.0609815608017064
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection is a well-studied problem with applications in domains ranging from computer networking to bioinformatics. While there are many algorithms that perform community detection, the more accurate and statistically robust algorithms tend to be slow and hard to parallelize. One way to speed up such algorithms is through data reduction. However, this approach has not been thoroughly studied, and the quality of results obtained with this approach varies with the graph it is applied to. In this manuscript, we present an approach based on topology-guided sampling for accelerating stochastic block partitioning - a community detection algorithm that works well on graphs with complex and heterogeneous community structure. We also introduce a degree-based thresholding scheme that improves the efficacy of our approach at the expense of speedup. Finally, we perform a series of experiments on synthetically generated graphs to determine how various graph parameters affect the quality of results and speedup obtained with our approach, and we validate our approach on real-world data. Our results show that our approach can lead to a speedup of up to 15X over stochastic block partitioning without sampling while maintaining result quality and can even lead to improvements of over 150% in result quality in terms of F1 score on certain kinds of graphs.

Related papers

• Evolvable Agents, a Fine Grained Approach for Distributed Evolutionary Computing: Walking towards the Peer-to-Peer Computing Frontiers [0.0]
  We propose a fine grained approach with self-adaptive migration rate for distributed evolutionary computation. We analyse the approach viability by comparing how solution quality and algorithm speed change when the number of processors increases. With this experimental setup, our approach shows better scalability than the Island model and a equivalent robustness on the average of the three test functions under study.
  arXiv  Detail & Related papers  (2024-01-30T18:11:31Z)
• Addressing Noise and Efficiency Issues in Graph-Based Machine Learning Models From the Perspective of Adversarial Attack [2.1937382384136637]
  We propose treating noisy edges as adversarial attack and use a spectral adversarial robustness evaluation method to diminish the impact of noisy edges on the performance of graph algorithms. Our method identifies those points that are less vulnerable to noisy edges and leverages only these robust points to perform graph-based algorithms.
  arXiv  Detail & Related papers  (2024-01-28T10:03:37Z)
• Contraction-Guided Adaptive Partitioning for Reachability Analysis of Neural Network Controlled Systems [5.359060261460183]
  We present a contraction-guided adaptive partitioning algorithm for improving interval-valued reachable set estimates in a nonlinear feedback loop. By leveraging a decoupling of the neural network verification step and reachability partitioning layers, the algorithm can provide accuracy improvements for little computational cost. We report a sizable improvement in the accuracy of reachable set estimation in a fraction of the runtime as compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-04-07T14:43:21Z)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  Graph outlier detection is an emerging but crucial machine learning task with numerous applications. We present the first comprehensive unsupervised node outlier detection benchmark for graphs called UNOD.
  arXiv  Detail & Related papers  (2022-06-21T01:46:38Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Accelerated Graph Learning from Smooth Signals [10.426964757656743]
  A fast dual-based proximal gradient algorithm is developed to tackle a strongly convex, smoothness-regularized network inverse problem. Unlike existing solvers, the novel iterations come with global convergence rate guarantees and do not require additional step-size tuning.
  arXiv  Detail & Related papers  (2021-10-19T01:02:57Z)
• Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity [57.275753974812666]
  Federated learning involves learning from data samples distributed across a network of clients while the data remains local. In this paper, we propose a novel straggler-resilient federated learning method that incorporates statistical characteristics of the clients' data to adaptively select the clients in order to speed up the learning procedure.
  arXiv  Detail & Related papers  (2020-12-28T19:21:14Z)
• Progressive Spatio-Temporal Graph Convolutional Network for Skeleton-Based Human Action Recognition [97.14064057840089]
  We propose a method to automatically find a compact and problem-specific network for graph convolutional networks in a progressive manner. Experimental results on two datasets for skeleton-based human action recognition indicate that the proposed method has competitive or even better classification performance.
  arXiv  Detail & Related papers  (2020-11-11T09:57:49Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.