Rethinking Graph Backdoor Defense: A Topological, Coarse-to-Fine Perspective

Graph Neural Networks (GNNs) power applications from social and financial networks to biology, yet they are vulnerable to backdoor attacks where tiny trigger subgraphs force targeted misclassification while preserving clean accuracy. We present TCF, a Topological Coarse-to-Fine defense that relies only on structure. First, Coarse Structural Pruning (CSP) screens nodes via three near-linear tests—local spectral moments, one-step 1-WL color rarity, and ego-density Z-scores—merged by a unified p-value rule with finite-sample FPR control. Second, a structure-based detector is trained on clean d-hop subgraphs versus compact synthetic triggers from small-world and preferential-attachment priors. Finally, label-flip verification pruning removes a subgraph only if its deletion flips the node’s prediction. On Cora, PubMed, Flickr, and OGB-Arxiv under three state-of-the-art attacks, TCF typically reduces ASR to <5\% while maintaining clean accuracy, indicating topology alone can deliver accurate, scalable graph backdoor defense.