A Quantum Algorithm for Assessing Node Importance in the st-Connectivity Attack

• URL: http://arxiv.org/abs/2502.00446v1
• Date: Sat, 01 Feb 2025 14:40:52 GMT
• Title: A Quantum Algorithm for Assessing Node Importance in the st-Connectivity Attack
• Authors: Iain Burge, Michel Barbeau, Joaquin Garcia-Alfaro,
• Abstract summary: Problems in distributed security often map naturally to graphs. Cooperative game theory has been used to create nuanced and flexible notions of node centrality. This work describes a quantum approach to approximating the importance of nodes that maintain a target connection.
• Score: 0.8739101659113155
• License:
• Abstract: Problems in distributed security often map naturally to graphs. The centrality of nodes assesses the importance of nodes in a graph. It is used in various applications. Cooperative game theory has been used to create nuanced and flexible notions of node centrality. However, the approach is often computationally complex to implement classically. This work describes a quantum approach to approximating the importance of nodes that maintain a target connection. Additionally, we detail a method for quickly identifying high-importance nodes. The approximation method relies on quantum subroutines for st-connectivity, approximating Shapley values, and finding the maximum of a list. Finding important nodes relies on a quantum algorithm for finding the maximum. We consider st-connectivity attack scenarios in which a malicious actor disrupts a subset of nodes to perturb the system functionality. Our methods identify the nodes that are most important with the aim of minimizing the impact of the attack. The node centrality metric identifies where more redundancy is required and can be used to enhance network resiliency. Finally, we explore the potential complexity benefits of our quantum approach in contrast to classical random sampling.

Related papers

• A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
  We study the problem of removing $k$ edges from a network to minimize the information centrality of a target node. We propose three approximation greedy algorithms using novel techniques such as random walk-based Schur complement approximation and fast sum estimation. To complement our theoretical analysis, we conduct a comprehensive set of experiments on synthetic and real networks with over one million nodes.
  arXiv  Detail & Related papers  (2023-09-09T13:54:34Z)
• Communication-Efficient Decentralized Federated Learning via One-Bit Compressive Sensing [52.402550431781805]
  Decentralized federated learning (DFL) has gained popularity due to its practicality across various applications. Compared to the centralized version, training a shared model among a large number of nodes in DFL is more challenging. We develop a novel algorithm based on the framework of the inexact alternating direction method (iADM)
  arXiv  Detail & Related papers  (2023-08-31T12:22:40Z)
• Network Centralities in Quantum Entanglement Distribution due to User Preferences [5.243460995467895]
  This paper studies the centralities of the network when the link layer topology of entanglements is driven by usage patterns of peer-to-peer connections. It shows that the edge centralities (measured as usage of individual edges during entanglement distribution) of the entangled graph follow power law distributions. These findings will help in quantum resource management, e.g., quantum technology with high reliability and lower decoherence time may be allocated to edges with high centralities.
  arXiv  Detail & Related papers  (2023-08-16T07:00:09Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• Reasoning Graph Networks for Kinship Verification: from Star-shaped to Hierarchical [85.0376670244522]
  We investigate the problem of facial kinship verification by learning hierarchical reasoning graph networks. We develop a Star-shaped Reasoning Graph Network (S-RGN) to exploit more powerful and flexible capacity. We also develop a Hierarchical Reasoning Graph Network (H-RGN) to exploit more powerful and flexible capacity.
  arXiv  Detail & Related papers  (2021-09-06T03:16:56Z)
• A QUBO formulation for top-$\tau$ eigencentrality nodes [0.0]
  We lay the foundations for solving the eigencentrality problem of ranking the importance of the nodes of a network with scores from the eigenvector of the network. The problem is reformulated as a quadratic unconstrained binary optimization (QUBO) that can be solved on both quantum architectures. The results focus on correctly identifying a given number of the most important nodes in numerous networks given by the sparse vector solution of our QUBO formulation of the problem of identifying the top-$tau$ highest eigencentrality nodes in a network on both the D-Wave and IBM quantum computers.
  arXiv  Detail & Related papers  (2021-05-01T05:35:44Z)
• Graph neural network based approximation of Node Resiliency in complex networks [1.629817296011086]
  We propose a graph neural network (GNN) based framework for approximating node resilience in large complex networks. The proposed framework defines a GNN model that learns the node rank on a small representative subset of nodes. The scalability of the framework is demonstrated through the prediction of node ranks in real-world graphs.
  arXiv  Detail & Related papers  (2020-12-26T05:37:18Z)
• Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
  We propose a graph meta-learning framework -- Graph Prototypical Networks (GPN) GPN is able to perform textitmeta-learning on an attributed network and derive a highly generalizable model for handling the target classification task.
  arXiv  Detail & Related papers  (2020-06-23T04:13:23Z)
• Quantized Decentralized Stochastic Learning over Directed Graphs [54.005946490293496]
  We consider a decentralized learning problem where data points are distributed among computing nodes communicating over a directed graph. As the model size gets large, decentralized learning faces a major bottleneck that is the communication load due to each node transmitting messages (model updates) to its neighbors. We propose the quantized decentralized learning algorithm over directed graphs that is based on the push-sum algorithm in decentralized consensus optimization.
  arXiv  Detail & Related papers  (2020-02-23T18:25:39Z)

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.