Exact and rapid linear clustering of networks with dynamic programming

• URL: http://arxiv.org/abs/2301.10403v2
• Date: Fri, 8 Dec 2023 21:53:54 GMT
• Title: Exact and rapid linear clustering of networks with dynamic programming
• Authors: Alice Patania, Antoine Allard, Jean-Gabriel Young
• Abstract summary: We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension. Existing algorithms, such as the critical gap method and other strategies, only offer approximate this problem.
• Score: 0.5371337604556311
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, for example prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions to this problem. Here, we introduce a dynamic programming approach that returns provably optimal solutions in polynomial time -- O(n^2) steps -- for a broad class of clustering objectives. We demonstrate the algorithm through applications to synthetic and empirical networks and show that it outperforms existing heuristics by a significant margin, with a similar execution time.

Related papers

• Optimization and Learning in Open Multi-Agent Systems [1.0249620437941]
  This article introduces a novel distributed algorithm to address a broad class of problems in "open networks" The proposed algorithm is used to solve dynamic consensus or tracking problems on different metrics of interest.
  arXiv  Detail & Related papers  (2025-01-28T10:40:09Z)
• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  We consider the task of minimizing the sum of convex functions stored in a decentralized manner across the nodes of a communication network. Lower bounds on the number of decentralized communications and (sub)gradient computations required to solve the problem have been established. We develop the first optimal algorithm that matches these lower bounds and offers substantially improved theoretical performance compared to the existing state of the art.
  arXiv  Detail & Related papers  (2024-05-28T10:28:45Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  We study the problem of distributed multi-level optimization over a network, where agents can only communicate with their immediate neighbors. We propose a novel gossip-based distributed multi-level optimization algorithm that enables networked agents to solve optimization problems at different levels in a single timescale. Our algorithm achieves optimal sample complexity, scaling linearly with the network size, and demonstrates state-of-the-art performance on various applications.
  arXiv  Detail & Related papers  (2023-10-10T00:21:10Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies. A neural network is employed to act as structure prior and reveal the underlying signal interdependencies. Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
  arXiv  Detail & Related papers  (2022-03-29T21:00:39Z)
• Efficient Direct-Connect Topologies for Collective Communications [2.9394897655215555]
  We provide an algorithmic framework for constructing direct-connect topologies optimized for the latency vs. bandwidth trade-off associated with the workload. Our approach synthesizes many different topologies and schedules for a given cluster size and degree and then identifies the appropriate topology and schedule for a given workload.
  arXiv  Detail & Related papers  (2022-02-07T16:59:05Z)
• An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees [4.007017852999008]
  We propose a new iterative algorithm to cluster networks with side information for nodes. We show that our algorithm is optimal under the Contextual Symmetric Block Model.
  arXiv  Detail & Related papers  (2021-12-20T12:04:07Z)
• Network Clustering for Latent State and Changepoint Detection [0.0]
  We propose a convex approach for the task of network clustering. We provide an efficient algorithm for convex network clustering and demonstrate its effectiveness on synthetic examples.
  arXiv  Detail & Related papers  (2021-11-01T21:51:45Z)
• Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training [10.14260510961573]
  We address the challenge of finding algorithms for online allocation (i.e. bipartite matching) using a machine learning approach. In this paper, we focus on the AdWords problem, which is a classical online budgeted matching problem of both theoretical and practical significance.
  arXiv  Detail & Related papers  (2020-10-16T14:33:11Z)
• A black-box adversarial attack for poisoning clustering [78.19784577498031]
  We propose a black-box adversarial attack for crafting adversarial samples to test the robustness of clustering algorithms. We show that our attacks are transferable even against supervised algorithms such as SVMs, random forests, and neural networks.
  arXiv  Detail & Related papers  (2020-09-09T18:19:31Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)

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.