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.

Graph Neural Networks (GNNs) are widely used to analyze connected data such as social networks, recommendation systems, and healthcare records. Although these systems typically expose only prediction outputs, our work shows that these outputs can still reveal private relationships hidden in the original data. We study whether an attacker can determine if two people or records were connected in the training data simply by observing a model’s predictions. Unlike prior work that focuses on average attack performance, we examine high-risk situations where attackers aim to make very few mistakes while still uncovering sensitive links. Our results show that these privacy risks remain significant even under strict conditions. We also develop a new method that exposes hidden vulnerabilities missed by existing evaluations, revealing that current graph-based AI systems may leak more sensitive relationship information than previously understood.