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) - Real-time Trajectory-based Social Group Detection [22.86110112028644]
We propose a simple and efficient framework for social group detection.
Our approach explores the impact of motion trajectory on social grouping and utilizes a novel, reliable, and fast data-driven method.
Our experiments on the popular JRDBAct dataset reveal noticeable improvements in performance, with relative improvements ranging from 2% to 11%.
arXiv Detail & Related papers (2023-04-12T08:01:43Z) - 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.