Network Interdiction Goes Neural

• URL: http://arxiv.org/abs/2405.16409v1
• Date: Sun, 26 May 2024 02:34:26 GMT
• Title: Network Interdiction Goes Neural
• Authors: Lei Zhang, Zhiqian Chen, Chang-Tien Lu, Liang Zhao,
• Abstract summary: Network interdiction problems are optimization problems involving two players. One aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives.
• Score: 26.308933674471895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Network interdiction problems are combinatorial optimization problems involving two players: one aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives. Such problems typically emerge in an attacker-defender context, encompassing areas such as military operations, disease spread analysis, and communication network management. The primary bottleneck in network interdiction arises from the high time complexity of using conventional exact solvers and the challenges associated with devising efficient heuristic solvers. GNNs, recognized as a cutting-edge methodology, have shown significant effectiveness in addressing single-level CO problems on graphs, such as the traveling salesman problem, graph matching, and graph edit distance. Nevertheless, network interdiction presents a bi-level optimization challenge, which current GNNs find difficult to manage. To address this gap, we represent network interdiction problems as Mixed-Integer Linear Programming (MILP) instances, then apply a multipartite GNN with sufficient representational capacity to learn these formulations. This approach ensures that our neural network is more compatible with the mathematical algorithms designed to solve network interdiction problems, resulting in improved generalization. Through two distinct tasks, we demonstrate that our proposed method outperforms theoretical baseline models and provides advantages over traditional exact solvers.

Related papers

• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
  Combinatorial optimization (CO) is the fundamental problem at the intersection of computer science, applied mathematics, etc. In this paper, we design a family of non-autoregressive neural networks to solve CO problems under positive linear constraints. We validate the effectiveness of this framework in solving representative CO problems including facility location, max-set covering, and traveling salesman problem.
  arXiv  Detail & Related papers  (2024-09-06T14:58:31Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• WeaveNet for Approximating Two-sided Matching Problems [16.014942651874815]
  This paper proposes a novel graph neural network (GNN), textitWeaveNet, designed for bipartite graphs. Our model reached a comparative performance with state-of-the-art algorithms specially designed for stable matching for small numbers of agents.
  arXiv  Detail & Related papers  (2023-10-19T06:32:12Z)
• Graph Reinforcement Learning for Network Control via Bi-Level Optimization [37.00510744883984]
  We argue that data-driven strategies can automate this process and learn efficient algorithms without compromising optimality. We present network control problems through the lens of reinforcement learning and propose a graph network-based framework to handle a broad class of problems.
  arXiv  Detail & Related papers  (2023-05-16T03:20:22Z)
• GNN-based physics solver for time-independent PDEs [1.7616042687330642]
  Time-independent problems pose the challenge of requiring long-range exchange of information across the computational domain for obtaining accurate predictions. We present two graph neural networks (GNNs) to overcome this challenge - the Edge Augmented GNN and the Multi-GNN. We show that both these networks perform significantly better (by a factor of 1.5 to 2) than baseline methods when applied to time-independent solid mechanics problems.
  arXiv  Detail & Related papers  (2023-03-28T02:04:43Z)
• Learning Cooperative Beamforming with Edge-Update Empowered Graph Neural Networks [29.23937571816269]
  We propose an edge-graph-neural-network (Edge-GNN) to learn the cooperative beamforming on the graph edges. The proposed Edge-GNN achieves higher sum rate with much shorter computation time than state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-23T02:05:06Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Learning Autonomy in Management of Wireless Random Networks [102.02142856863563]
  This paper presents a machine learning strategy that tackles a distributed optimization task in a wireless network with an arbitrary number of randomly interconnected nodes. We develop a flexible deep neural network formalism termed distributed message-passing neural network (DMPNN) with forward and backward computations independent of the network topology.
  arXiv  Detail & Related papers  (2021-06-15T09:03:28Z)
• Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis [31.372548374969387]
  We propose to apply graph neural networks (GNNs) to solve large-scale radio resource management problems. The proposed method is highly scalable and can solve the beamforming problem in an interference channel with $1000$ transceiver pairs within $6$ milliseconds on a single GPU.
  arXiv  Detail & Related papers  (2020-07-15T11:43:32Z)
• Graph Neural Networks for Motion Planning [108.51253840181677]
  We present two techniques, GNNs over dense fixed graphs for low-dimensional problems and sampling-based GNNs for high-dimensional problems. We examine the ability of a GNN to tackle planning problems such as identifying critical nodes or learning the sampling distribution in Rapidly-exploring Random Trees (RRT) Experiments with critical sampling, a pendulum and a six DoF robot arm show GNNs improve on traditional analytic methods as well as learning approaches using fully-connected or convolutional neural networks.
  arXiv  Detail & Related papers  (2020-06-11T08:19:06Z)
• Binary Neural Networks: A Survey [126.67799882857656]
  The binary neural network serves as a promising technique for deploying deep models on resource-limited devices. The binarization inevitably causes severe information loss, and even worse, its discontinuity brings difficulty to the optimization of the deep network. We present a survey of these algorithms, mainly categorized into the native solutions directly conducting binarization, and the optimized ones using techniques like minimizing the quantization error, improving the network loss function, and reducing the gradient error.
  arXiv  Detail & Related papers  (2020-03-31T16:47:20Z)

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.