Scoring Anomalous Vertices Through Quantum Walks

• URL: http://arxiv.org/abs/2311.09855v3
• Date: Tue, 17 Sep 2024 20:50:39 GMT
• Title: Scoring Anomalous Vertices Through Quantum Walks
• Authors: Andrew Vlasic, Anh Pham,
• Abstract summary: For unlabeled data, anomaly detection on graphs is a method to determine which data points do not posses the latent characteristics that is present in most other data. We propose a first quantum algorithm to calculate the anomaly score of each node by continuously traversing the graph with a uniform starting position of all nodes.
• Score: 0.26013878609420266
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: With the constant flow of data from vast sources over the past decades, a plethora of advanced analytical techniques have been developed to extract relevant information from different data types ranging from labeled data, quasi-labeled data, and data with no labels known a priori. For data with at best quasi-labels, graphs are a natural representation of these data types and have important applications in many industries and scientific disciplines. Specifically, for unlabeled data, anomaly detection on graphs is a method to determine which data points do not posses the latent characteristics that is present in most other data. There have been a variety of classical methods to compute an anomalous score for the individual vertices of a respected graph, such as checking the local topology of a node,random walks, and complex neural networks. Leveraging the structure of the graph, we propose a first quantum algorithm to calculate the anomaly score of each node by continuously traversing the graph with a uniform starting position of all nodes. The proposed algorithm incorporates well-known characteristics of quantum random walks, and, taking into consideration the NISQ era and subsequent ISQ era, an adjustment to the algorithm is given to mitigate the increasing depth of the circuit. This algorithm is rigorously shown to converge to the expected probability, with respect to the initial condition.

Related papers

• Online Network Inference from Graph-Stationary Signals with Hidden Nodes [31.927912288598467]
  We present a novel method for online graph estimation that accounts for the presence of hidden nodes. We then formulate a convex optimization problem for graph learning from streaming, incomplete graph signals.
  arXiv  Detail & Related papers  (2024-09-13T12:09:09Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection [84.0718034981805]
  We introduce a novel framework called Anomaly-Denoised Autoencoders for Graph Anomaly Detection (ADA-GAD) In the first stage, we design a learning-free anomaly-denoised augmentation method to generate graphs with reduced anomaly levels. In the next stage, the decoders are retrained for detection on the original graph.
  arXiv  Detail & Related papers  (2023-12-22T09:02:01Z)
• A fast topological approach for predicting anomalies in time-varying graphs [0.0]
  A persistence diagram (PD) from topological data analysis (TDA) has become a popular descriptor of shape of data with a well-defined distance between points. This paper introduces a computationally efficient framework to extract shape information from graph data. In a real data application, our approach provides up to 22% gain in anomalous price prediction for the cryptocurrency transaction networks.
  arXiv  Detail & Related papers  (2023-05-11T01:54:45Z)
• Joint graph learning from Gaussian observations in the presence of hidden nodes [26.133725549667734]
  We propose a joint graph learning method that takes into account the presence of hidden (latent) variables. We exploit the structure resulting from the previous considerations to propose a convex optimization problem. We compare the proposed algorithm with different baselines and evaluate its performance over synthetic and real-world graphs.
  arXiv  Detail & Related papers  (2022-12-04T13:03:41Z)
• Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation [61.39364567221311]
  Graph-level anomaly detection (GAD) describes the problem of detecting graphs that are abnormal in their structure and/or the features of their nodes. One of the challenges in GAD is to devise graph representations that enable the detection of both locally- and globally-anomalous graphs. We introduce a novel deep anomaly detection approach for GAD that learns rich global and local normal pattern information by joint random distillation of graph and node representations.
  arXiv  Detail & Related papers  (2021-12-19T05:04:53Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner? Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
  arXiv  Detail & Related papers  (2021-06-08T16:10:36Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  We propose an end-to-end structural temporal Graph Neural Network model for detecting anomalous edges in dynamic graphs. In particular, we first extract the $h$-hop enclosing subgraph centered on the target edge and propose the node labeling function to identify the role of each node in the subgraph. Based on the extracted features, we utilize Gated recurrent units (GRUs) to capture the temporal information for anomaly detection.
  arXiv  Detail & Related papers  (2020-05-15T09:17:08Z)
• Semi-supervised Anomaly Detection on Attributed Graphs [43.69966808278313]
  We propose a simple yet effective method for detecting anomalous instances on an attribute graph with label information of a small number of instances. The proposed method embeds nodes on the attributed graph in the latent space by taking into account their attributes. In experiments with five real-world attributed graph datasets, we demonstrate that the proposed method achieves better performance than various existing anomaly detection methods.
  arXiv  Detail & Related papers  (2020-02-27T10:06:22Z)

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.