Reliable Graph Neural Networks via Robust Aggregation

• URL: http://arxiv.org/abs/2010.15651v1
• Date: Thu, 29 Oct 2020 14:55:20 GMT
• Title: Reliable Graph Neural Networks via Robust Aggregation
• Abstract summary: Perturbations targeting the graph structure have proven to be extremely effective in reducing the performance of Graph Neural Networks (GNNs) Traditional defenses such as adversarial training do not seem to be able to improve robustness. This work is motivated by the observation that adversarially injected edges effectively can be viewed as additional samples to a node's neighborhood aggregation function.
• Score: 1.7188280334580197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Perturbations targeting the graph structure have proven to be extremely effective in reducing the performance of Graph Neural Networks (GNNs), and traditional defenses such as adversarial training do not seem to be able to improve robustness. This work is motivated by the observation that adversarially injected edges effectively can be viewed as additional samples to a node's neighborhood aggregation function, which results in distorted aggregations accumulating over the layers. Conventional GNN aggregation functions, such as a sum or mean, can be distorted arbitrarily by a single outlier. We propose a robust aggregation function motivated by the field of robust statistics. Our approach exhibits the largest possible breakdown point of 0.5, which means that the bias of the aggregation is bounded as long as the fraction of adversarial edges of a node is less than 50\%. Our novel aggregation function, Soft Medoid, is a fully differentiable generalization of the Medoid and therefore lends itself well for end-to-end deep learning. Equipping a GNN with our aggregation improves the robustness with respect to structure perturbations on Cora ML by a factor of 3 (and 5.5 on Citeseer) and by a factor of 8 for low-degree nodes.

Related papers

• Improving Graph Neural Networks via Adversarial Robustness Evaluation [2.1937382384136637]
  Graph Neural Networks (GNNs) are one of the most powerful types of neural network architectures. However, GNNs are vulnerable to noise in the graph structure. In this paper, we propose using adversarial robustness evaluation to select a small subset of robust nodes that are less affected by noise.
  arXiv  Detail & Related papers  (2024-12-14T14:47:20Z)
• Sparse Decomposition of Graph Neural Networks [20.768412002413843]
  We propose an approach to reduce the number of nodes that are included during aggregation. We achieve this through a sparse decomposition, learning to approximate node representations using a weighted sum of linearly transformed features. We demonstrate via extensive experiments that our method outperforms other baselines designed for inference speedup.
  arXiv  Detail & Related papers  (2024-10-25T17:52:16Z)
• Robust Node Representation Learning via Graph Variational Diffusion Networks [7.335425547621226]
  In recent years, compelling evidence has revealed that GNN-based node representation learning can be substantially deteriorated by perturbations in a graph structure. To learn robust node representation in the presence of perturbations, various works have been proposed to safeguard GNNs. We propose the Graph Variational Diffusion Network (GVDN), a new node encoder that effectively manipulates Gaussian noise to safeguard robustness on perturbed graphs.
  arXiv  Detail & Related papers  (2023-12-18T03:18:53Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  We modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods.
  arXiv  Detail & Related papers  (2023-12-16T14:09:23Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [92.05291395292537]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories. First, emphnode-wise architectures pre-compute individual embeddings for each node that are later combined by a simple decoder to make predictions. Second, emphedge-wise methods rely on the formation of edge-specific subgraph embeddings to enrich the representation of pair-wise relationships.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• 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)
• SIGMA: Similarity-based Efficient Global Aggregation for Heterophilous Graph Neural Networks [12.302311645194775]
  Graph neural networks (GNNs) realize great success in graph learning but suffer from performance loss when meeting heterophily. We propose SIGMA, an efficient global heterophilous GNN aggregation integrating the structural similarity measurement SimRank.
  arXiv  Detail & Related papers  (2023-05-17T05:35:49Z)
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization [80.90206641975375]
  This paper focuses on improving the performance of GNNs via normalization. By studying the long-tailed distribution of node degrees in the graph, we propose a novel normalization method for GNNs. The $scale$ operation of ResNorm reshapes the node-wise standard deviation (NStd) distribution so as to improve the accuracy of tail nodes.
  arXiv  Detail & Related papers  (2022-06-16T13:49:09Z)
• Interpolation-based Correlation Reduction Network for Semi-Supervised Graph Learning [49.94816548023729]
  We propose a novel graph contrastive learning method, termed Interpolation-based Correlation Reduction Network (ICRN) In our method, we improve the discriminative capability of the latent feature by enlarging the margin of decision boundaries. By combining the two settings, we extract rich supervision information from both the abundant unlabeled nodes and the rare yet valuable labeled nodes for discnative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• EIGNN: Efficient Infinite-Depth Graph Neural Networks [51.97361378423152]
  Graph neural networks (GNNs) are widely used for modelling graph-structured data in numerous applications. Motivated by this limitation, we propose a GNN model with infinite depth, which we call Efficient Infinite-Depth Graph Neural Networks (EIGNN) We show that EIGNN has a better ability to capture long-range dependencies than recent baselines, and consistently achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-02-22T08:16:58Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  We propose the Explicit Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph as a partially observed Markov Random Field. It contains explicit pairwise factors to model output-output relations and uses a GNN backbone to model input-output relations. We conduct experiments on various datasets, which shows that our model can effectively improve the performance for semi-supervised node classification on graphs.
  arXiv  Detail & Related papers  (2021-07-27T19:47:53Z)
• Learnt Sparsification for Interpretable Graph Neural Networks [5.527927312898106]
  We propose a novel method called Kedge for explicitly sparsifying the underlying graph by removing unnecessary neighbors. Kedge learns edge masks in a modular fashion trained with any GNN allowing for gradient based optimization. We show that Kedge effectively counters the over-smoothing phenomena in deep GNNs by maintaining good task performance with increasing GNN layers.
  arXiv  Detail & Related papers  (2021-06-23T16:04:25Z)

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.