Class Pair Distance Calibration for Robust Graph Neural Networks

Distance based graph defenses can suppress useful messages when edges between different classes have large representation distances. CLASP divides each edge distance by the median for its predicted class pair, then applies a robust penalty to the relative distance. Each pair thus has its own reference scale. If retained edges form a majority of a perturbed bucket and their distance drift is bounded, we bound the new median using their clean order statistics and the drift bound. We evaluate CLASP in a two layer GCN and in HARA, which combines ego, one hop, and two hop channels. With full training labels and five shared attack edits, matched GCN controls show mean accuracy gains of 7.7 percentage points on Cora and 4.0 on Actor, and losses of 1.0 point on Roman-Empire and Amazon-Ratings. The system comparison uses unequal tuning budgets, with HARA's search expanded after earlier test results and final parameters selected on validation data. Across seven datasets and four attack families, HARA exceeds the strongest recorded fixed baseline in 24 of 48 budget scenarios, mostly under shared and local attacks.