Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure

• URL: http://arxiv.org/abs/2404.15065v1
• Date: Tue, 23 Apr 2024 14:12:48 GMT
• Title: Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure
• Authors: Tobias Ladner, Michael Eichelbeck, Matthias Althoff,
• Abstract summary: Graph neural networks are becoming increasingly popular in the field of machine learning. They have been applied in safety-critical environments where perturbations inherently occur. This research addresses the non-passing gap by preserving the dependencies of all elements in the underlying computations.
• Score: 7.133681867718039
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks are becoming increasingly popular in the field of machine learning due to their unique ability to process data structured in graphs. They have also been applied in safety-critical environments where perturbations inherently occur. However, these perturbations require us to formally verify neural networks before their deployment in safety-critical environments as neural networks are prone to adversarial attacks. While there exists research on the formal verification of neural networks, there is no work verifying the robustness of generic graph convolutional network architectures with uncertainty in the node features and in the graph structure over multiple message-passing steps. This work addresses this research gap by explicitly preserving the non-convex dependencies of all elements in the underlying computations through reachability analysis with (matrix) polynomial zonotopes. We demonstrate our approach on three popular benchmark datasets.

Related papers

• Unitary convolutions for learning on graphs and groups [0.9899763598214121]
  We study unitary group convolutions, which allow for deeper networks that are more stable during training. The main focus of the paper are graph neural networks, where we show that unitary graph convolutions provably avoid over-smoothing. Our experimental results confirm that unitary graph convolutional networks achieve competitive performance on benchmark datasets.
  arXiv  Detail & Related papers  (2024-10-07T21:09:14Z)
• Changepoint Detection in Highly-Attributed Dynamic Graphs [0.0]
  We leverage Graph Neural Networks to estimate each snapshot's modularity. Our method is validated through simulations that demonstrate its ability to detect changes in highly-attributed networks. We find our method is able to detect a real-world event within the #Iran Twitter reply network.
  arXiv  Detail & Related papers  (2024-07-09T16:12:44Z)
• Coding schemes in neural networks learning classification tasks [52.22978725954347]
  We investigate fully-connected, wide neural networks learning classification tasks. We show that the networks acquire strong, data-dependent features. Surprisingly, the nature of the internal representations depends crucially on the neuronal nonlinearity.
  arXiv  Detail & Related papers  (2024-06-24T14:50:05Z)
• GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection [51.608147732998994]
  Graph neural networks are increasingly becoming the framework of choice for graph-based machine learning. We propose a new graph neural network architecture that substitutes classical message passing with an analysis of the local distribution of node features.
  arXiv  Detail & Related papers  (2024-01-17T13:04:23Z)
• The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks [0.716879432974126]
  Community detection is an essential tool for unsupervised data exploration and revealing the organisational structure of networked systems. We consider the map equation, a popular information-theoretic objective function for unsupervised community detection, and express it in differentiable tensor form for gradient through descent. Our formulation turns the map equation compatible with any neural network architecture, enables end-to-end learning, incorporates node features, and chooses the optimal number of clusters automatically.
  arXiv  Detail & Related papers  (2023-10-02T12:32:18Z)
• 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)
• BS-GAT Behavior Similarity Based Graph Attention Network for Network Intrusion Detection [20.287285893803244]
  This paper proposes a graph neural network algorithm based on behavior similarity (BS-GAT) using graph attention network. The results show that the proposed method is effective and has superior performance comparing to existing solutions.
  arXiv  Detail & Related papers  (2023-04-07T09:42:07Z)
• USER: Unsupervised Structural Entropy-based Robust Graph Neural Network [22.322867182077182]
  Unsupervised graph neural networks (GNNs) are vulnerable to inherent randomness in the input graph data. We propose USER, an unsupervised robust version of graph neural networks that is based on structural entropy. Experiments conducted on clustering and link prediction tasks under random-noises and meta-attack over three datasets show USER outperforms benchmarks.
  arXiv  Detail & Related papers  (2023-02-12T10:32:12Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• Discriminability of Single-Layer Graph Neural Networks [172.5042368548269]
  Graph neural networks (GNNs) have exhibited promising performance on a wide range of problems. We focus on the property of discriminability and establish conditions under which the inclusion of pointwise nonlinearities to a stable graph filter bank leads to an increased discriminative capacity for high-eigenvalue content.
  arXiv  Detail & Related papers  (2020-10-17T18:52:34Z)

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.