Robust Graph Neural Networks via Probabilistic Lipschitz Constraints
- URL: http://arxiv.org/abs/2112.07575v1
- Date: Tue, 14 Dec 2021 17:33:32 GMT
- Title: Robust Graph Neural Networks via Probabilistic Lipschitz Constraints
- Authors: Raghu Arghal, Eric Lei, and Shirin Saeedi Bidokhti
- Abstract summary: Graph neural networks (GNNs) have recently been demonstrated to perform well on a variety of network-based tasks.
GNNs are susceptible to shifts and perturbations on their inputs, which can include both node attributes and graph structure.
- Score: 7.359962178534361
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph neural networks (GNNs) have recently been demonstrated to perform well
on a variety of network-based tasks such as decentralized control and resource
allocation, and provide computationally efficient methods for these tasks which
have traditionally been challenging in that regard. However, like many
neural-network based systems, GNNs are susceptible to shifts and perturbations
on their inputs, which can include both node attributes and graph structure. In
order to make them more useful for real-world applications, it is important to
ensure their robustness post-deployment. Motivated by controlling the Lipschitz
constant of GNN filters with respect to the node attributes, we propose to
constrain the frequency response of the GNN's filter banks. We extend this
formulation to the dynamic graph setting using a continuous frequency response
constraint, and solve a relaxed variant of the problem via the scenario
approach. This allows for the use of the same computationally efficient
algorithm on sampled constraints, which provides PAC-style guarantees on the
stability of the GNN using results in scenario optimization. We also highlight
an important connection between this setup and GNN stability to graph
perturbations, and provide experimental results which demonstrate the efficacy
and broadness of our approach.
Related papers
- Graph Neural Network-Based Bandwidth Allocation for Secure Wireless
Communications [46.342827102556896]
We propose a user scheduling algorithm to schedule users satisfying an instantaneous minimum secrecy rate constraint.
We optimize the bandwidth allocations with three algorithms namely iterative search (IvS), GNN-based supervised learning (GNN-SL), and GNN-based unsupervised learning (GNN-USL)
arXiv Detail & Related papers (2023-12-13T09:34:16Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining.
Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
arXiv Detail & Related papers (2023-10-05T02:58:29Z) - Graph Neural Network Based Node Deployment for Throughput Enhancement [20.56966053013759]
We propose a novel graph neural network (GNN) method for the network node deployment problem.
We show that an expressive GNN has the capacity to approximate both the function value and the traffic permutation, as a theoretic support for the proposed method.
arXiv Detail & Related papers (2022-08-19T08:06:28Z) - Anomal-E: A Self-Supervised Network Intrusion Detection System based on
Graph Neural Networks [0.0]
This paper investigates Graph Neural Networks (GNNs) application for self-supervised network intrusion and anomaly detection.
GNNs are a deep learning approach for graph-based data that incorporate graph structures into learning.
We present Anomal-E, a GNN approach to intrusion and anomaly detection that leverages edge features and graph topological structure in a self-supervised process.
arXiv Detail & Related papers (2022-07-14T10:59:39Z) - Superiority of GNN over NN in generalizing bandlimited functions [6.3151583550712065]
Graph Neural Networks (GNNs) have emerged as formidable resources for processing graph-based information across diverse applications.
In this study, we investigate the proficiency of GNNs for such classifications, which can also be cast as a function problem.
Our findings highlight a pronounced efficiency in utilizing GNNs to generalize a bandlimited function within an $varepsilon$-error margin.
arXiv Detail & Related papers (2022-06-13T05:15:12Z) - Comparative Analysis of Interval Reachability for Robust Implicit and
Feedforward Neural Networks [64.23331120621118]
We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs)
INNs are a class of implicit learning models that use implicit equations as layers.
We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs.
arXiv Detail & Related papers (2022-04-01T03:31:27Z) - Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
Graph neural networks (GNNs) aim to model the local graph structures and capture the hierarchical patterns by aggregating the information from neighbors.
It is a challenging task to develop an effective aggregation strategy for each node, given complex graphs and sparse features.
We propose Policy-GNN, a meta-policy framework that models the sampling procedure and message passing of GNNs into a combined learning process.
arXiv Detail & Related papers (2020-06-26T17:03:06Z) - Resource Allocation via Graph Neural Networks in Free Space Optical
Fronthaul Networks [119.81868223344173]
This paper investigates the optimal resource allocation in free space optical (FSO) fronthaul networks.
We consider the graph neural network (GNN) for the policy parameterization to exploit the FSO network structure.
The primal-dual learning algorithm is developed to train the GNN in a model-free manner, where the knowledge of system models is not required.
arXiv Detail & Related papers (2020-06-26T14:20:48Z) - 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) - Stochastic Graph Neural Networks [123.39024384275054]
Graph neural networks (GNNs) model nonlinear representations in graph data with applications in distributed agent coordination, control, and planning.
Current GNN architectures assume ideal scenarios and ignore link fluctuations that occur due to environment, human factors, or external attacks.
In these situations, the GNN fails to address its distributed task if the topological randomness is not considered accordingly.
arXiv Detail & Related papers (2020-06-04T08:00:00Z)
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.