Inferring Properties of Graph Neural Networks

Dat Nguyen, Hieu M. Vu, Cong-Thanh Le, Bach Le, David Lo, Corina S. PasareanuarXiv 2024 · DOI · OpenReview

TL;DR

This paper introduces GNN-Infer, a novel technique for automatically inferring properties of Graph Neural Networks (GNNs). By converting GNNs to equivalent Feed-Forward Networks (FNNs) on specific substructures, GNN-Infer can leverage existing property inference tools to understand GNN behavior, which is crucial for debugging and defending against attacks like backdoors.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful for analyzing complex, graph-structured data, but their dynamic input structures (varying numbers of nodes and edges) make them notoriously difficult to debug and analyze. Traditional property inference techniques, designed for fixed-size inputs like those in Feed-Forward Networks (FNNs) and Convolutional Neural Networks (CNNs), are not directly applicable to GNNs. This lack of robust analysis tools hinders our ability to understand GNN behavior, assess their robustness against adversarial attacks, and ensure their reliability.

Methods

GNN-Infer tackles this challenge through a four-stage process:

  1. Extracting Influential Substructures: GNN-Infer identifies key subgraphs (influential structures) that significantly contribute to a GNN's predictions. This is achieved using tools like GNNExplainer and gSpan to find frequent and important substructures.
  2. Inferring Properties for Specific Structures: For each identified influential structure, GNN-Infer converts the GNN and the structure into an equivalent FNN. This conversion is proven to be sound and complete. Existing FNN property inference tools (like PROPHECY) are then used to derive structure-specific properties in the form of logical constraints.
  3. Relaxing Structure Constraints: To broaden the applicability of these properties, GNN-Infer relaxes the strict isomorphism requirement to subgraph isomorphism. This allows properties to apply to graphs that contain the influential structure, not just those that are identical to it.
  4. Inferring Dynamic Feature Properties: To further enhance precision, GNN-Infer incorporates dynamic analysis. It trains models (decision trees or linear regressions) on aggregated features that capture the influence of surrounding nodes and edges. These models help refine the properties by accounting for variations in the full graph context.

Datasets

The paper evaluates GNN-Infer on:

  • Synthetic benchmarks: GNNs simulating classic graph algorithms like Breadth-First Search (BFS), Depth-First Search (DFS), and Bellman-Ford (B-F). These benchmarks were constructed with known ground-truth properties.
  • Real-world datasets: Cora and Pubmed, used to train GNNs that were then subjected to backdoor attacks (UGBA).

Key Insights and Ideas

  • Bridging the GNN-FNN Gap: The core innovation is the formal proof and algorithm that allows a GNN with a fixed structure to be reduced to an equivalent FNN. This is a critical step that unlocks the power of existing FNN analysis tools for GNNs.
  • Influential Structures as Proxies: The idea of using frequent and important substructures as proxies for GNN behavior is key. These smaller, representative parts of the graph are more manageable for analysis and reveal significant GNN decision-making patterns.
  • Dynamic Analysis for Precision: Simply inferring properties on isolated substructures can be imprecise. The dynamic analysis step, which considers the broader graph context, significantly improves the accuracy and generalizability of the inferred properties.
  • Properties as Defense Mechanisms: The inferred properties are not just for understanding; they can be directly used to detect and neutralize malicious behaviors, such as backdoor attacks, by identifying and pruning subgraphs that exhibit these properties.

Key Results

  • Correctness on Reference GNNs: GNN-Infer successfully re-discovered 8 out of 13 ground-truth properties for reference GNNs and identified likely-correct properties that approximated the remaining ones.
  • Robust Performance on Trained GNNs: GNN-Infer achieved high proxy accuracy (PA) averaging 0.95 and low proxy error (PE) averaging 0.003 on trained GNNs.
  • Defense Against Backdoor Attacks: When used to defend against the UGBA backdoor attack, GNN-Infer outperformed existing baselines (Prune and Prune+LD) by a significant margin, achieving up to a 30-fold reduction in attack success rate.
  • Efficiency: While some stages like structure extraction can be time-consuming (around 2 hours), the overall process is considered reasonable for offline analysis.

Limitations and Future Work

  • Efficiency of Structure Extraction: The GNNExplainer component for extracting influential structures can be computationally intensive, taking up to 2 hours.
  • Coverage of Inferred Properties: While GNN-Infer aims to generalize properties, their coverage can still be limited, potentially leading to missed backdoor properties.
  • Future Work: The authors plan to improve GNN-Infer's efficiency and explore its application to other tasks like GNN verification. They also suggest investigating how to infer a set of common expected properties for future GNN models, especially since many real-world problems lack pre-defined expected properties.

Summary updated

Abstract

We propose GNNInfer, the first automatic property inference technique for GNNs. To tackle the challenge of varying input structures in GNNs, GNNInfer first identifies a set of representative influential structures that contribute significantly towards the prediction of a GNN. Using these structures, GNNInfer converts each pair of an influential structure and the GNN to their equivalent FNN and then leverages existing property inference techniques to effectively capture properties of the GNN that are specific to the influential structures. GNNINfer then generalizes the captured properties to any input graphs that contain the influential structures. Finally, GNNInfer improves the correctness of the inferred properties by building a model (either a decision tree or linear regression) that estimates the deviation of GNN output from the inferred properties given full input graphs. The learned model helps GNNInfer extend the inferred properties with constraints to the input and output of the GNN, obtaining stronger properties that hold on full input graphs. Our experiments show that GNNInfer is effective in inferring likely properties of popular real-world GNNs, and more importantly, these inferred properties help effectively defend against GNNs' backdoor attacks. In particular, out of the 13 ground truth properties, GNNInfer re-discovered 8 correct properties and discovered likely correct properties that approximate the remaining 5 ground truth properties. Using properties inferred by GNNInfer to defend against the state-of-the-art backdoor attack technique on GNNs, namely UGBA, experiments show that GNNInfer's defense success rate is up to 30 times better than existing baselines.
BibTeX
@misc{nguyen2024inferring,
  author = {Dat Nguyen and Hieu M. Vu and Cong-Thanh Le and Bach Le and David Lo and Corina S. Pasareanu},
  title = {{Inferring Properties of Graph Neural Networks}},
  year = {2024},
  eprint = {2401.03790},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.03790},
}
Figure