When Witnesses Defend: A Witness Graph Topological Layer for Adversarial Graph Learning

• URL: http://arxiv.org/abs/2409.14161v2
• Date: Tue, 24 Sep 2024 13:51:05 GMT
• Title: When Witnesses Defend: A Witness Graph Topological Layer for Adversarial Graph Learning
• Authors: Naheed Anjum Arafat, Debabrota Basu, Yulia Gel, Yuzhou Chen,
• Abstract summary: We bridge adversarial graph learning with the emerging tools from computational topology, namely, persistent homology representations of graphs. We introduce the concept of witness complex to adversarial analysis on graphs, which allows us to focus only on the salient shape characteristics of graphs, with minimal loss of topological information on the whole graph. Armed with the witness mechanism, we design Witness Graph Topological Layer (WGTL), which systematically integrates both local and global topological graph feature representations, the impact of which is, in turn, automatically controlled by the robust regularized topological loss.
• Score: 19.566775406771757
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Capitalizing on the intuitive premise that shape characteristics are more robust to perturbations, we bridge adversarial graph learning with the emerging tools from computational topology, namely, persistent homology representations of graphs. We introduce the concept of witness complex to adversarial analysis on graphs, which allows us to focus only on the salient shape characteristics of graphs, yielded by the subset of the most essential nodes (i.e., landmarks), with minimal loss of topological information on the whole graph. The remaining nodes are then used as witnesses, governing which higher-order graph substructures are incorporated into the learning process. Armed with the witness mechanism, we design Witness Graph Topological Layer (WGTL), which systematically integrates both local and global topological graph feature representations, the impact of which is, in turn, automatically controlled by the robust regularized topological loss. Given the attacker's budget, we derive the important stability guarantees of both local and global topology encodings and the associated robust topological loss. We illustrate the versatility and efficiency of WGTL by its integration with five GNNs and three existing non-topological defense mechanisms. Our extensive experiments across six datasets demonstrate that WGTL boosts the robustness of GNNs across a range of perturbations and against a range of adversarial attacks, leading to relative gains of up to 18%.

Related papers

• TopoGCL: Topological Graph Contrastive Learning [32.993034801654105]
  Graph contrastive learning (GCL) has recently emerged as a new concept which allows for capitalizing on the strengths of graph neural networks (GNNs) We introduce the concepts of topological invariance and extended persistence on graphs to GCL. Our results show that the new Topological Graph Contrastive Learning (TopoGCL) model delivers significant performance gains in unsupervised graph classification for 11 out of 12 considered datasets and also exhibits robustness under noisy scenarios.
  arXiv  Detail & Related papers  (2024-06-25T03:35:20Z)
• On the Topology Awareness and Generalization Performance of Graph Neural Networks [6.598758004828656]
  We introduce a comprehensive framework to characterize the topology awareness of GNNs across any topological feature. We conduct a case study using the intrinsic graph metric the shortest path distance on various benchmark datasets.
  arXiv  Detail & Related papers  (2024-03-07T13:33:30Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering. Models estimate an initial graph beforehand to apply GCN. Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
  arXiv  Detail & Related papers  (2024-02-25T07:03:37Z)
• Topological Pooling on Graphs [24.584372324701885]
  Graph neural networks (GNNs) have demonstrated a significant success in various graph learning tasks. We propose a novel topological pooling layer and witness complex-based topological embedding mechanism. We show that Wit-TopoPool significantly outperforms all competitors across all datasets.
  arXiv  Detail & Related papers  (2023-03-25T19:30:46Z)
• MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
  We propose an end-to-end model named MentorGNN that aims to supervise the pre-training process of GNNs across graphs. We shed new light on the problem of domain adaption on relational data (i.e., graphs) by deriving a natural and interpretable upper bound on the generalization error of the pre-trained GNNs.
  arXiv  Detail & Related papers  (2022-08-21T15:12:08Z)
• Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing [67.83086131278904]
  Topology-imbalance is a graph-specific imbalance problem caused by the uneven topology positions of labeled nodes. We propose a novel position-aware graph structure learning framework named PASTEL. Our key insight is to enhance the connectivity of nodes within the same class for more supervision information.
  arXiv  Detail & Related papers  (2022-08-17T14:04:21Z)
• Revisiting Adversarial Attacks on Graph Neural Networks for Graph Classification [38.339503144719984]
  We present a novel and general framework to generate adversarial examples via manipulating graph structure and node features. Specifically, we make use of Graph Class Mapping and its variant to produce node-level importance corresponding to the graph classification task. Experiments towards attacking four state-of-the-art graph classification models on six real-world benchmarks verify the flexibility and effectiveness of our framework.
  arXiv  Detail & Related papers  (2022-08-13T13:41:44Z)
• Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling [83.77955213766896]
  Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graphstructured data. To address its scalability issue, graph topology sampling has been proposed to reduce the memory and computational cost of training Gs. This paper provides first theoretical justification of graph topology sampling in training (up to) three-layer GCNs.
  arXiv  Detail & Related papers  (2022-07-07T21:25:55Z)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57:02Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Topological Relational Learning on Graphs [2.4692806302088868]
  Graph neural networks (GNNs) have emerged as a powerful tool for graph classification and representation learning. We propose a novel topological relational inference (TRI) which allows for integrating higher-order graph information to GNNs. We show that the new TRI-GNN outperforms all 14 state-of-the-art baselines on 6 out 7 graphs and exhibit higher robustness to perturbations.
  arXiv  Detail & Related papers  (2021-10-29T04:03:27Z)

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.