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:
- 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.
- 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.
- 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.
- 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