Revisiting Asymmetries in Black-box Link Stealing against Graph Neural Networks

Graph Neural Networks (GNNs) are increasingly deployed on sensitive relational data, from social networks to healthcare records. However, their outputs can leak private graph structure, enabling link-stealing attacks that infer whether a connection between two entities existed in the training graph. While prior work demonstrates high average performance for such attacks, privacy is fundamentally a worst-case property, not an average one. The key question is whether an adversary can reliably compromise even a small set of critical links under strict precision constraints. We revisit posterior-only link-stealing attacks in a strict black-box setting and show that they remain effective at extremely low false-positive rates, revealing tail-risk vulnerabilities that current evaluations overlook. We further find that intra-class vulnerabilities are suppressed by geometric bottlenecks that collapse discriminative directions in posterior space. Building on this insight, we propose a geometry-aware reconditioning method that reshapes intra-class distances, substantially improving separability without harming reliability. Across multiple real-world graphs and GNNs, this diagnostic correction achieves up to $2\times$ higher success on intra-class pairs than generic attacks, redefining link-privacy evaluation as a tail-risk problem and revealing that posterior leakage remains substantially under-measured in current GNN deployments.