Beyond Membership: Blind Spot in Graph Unlearning Audits

Graph unlearning is commonly considered successful when a membership inference attack performs no better than chance in determining whether a deleted node was used for training. For graph data, however, this criterion is incomplete. A node's label can often be inferred from its neighbors, which remain in the graph after deletion. The label of a deleted node may therefore remain recoverable even when a membership attack detects no evidence of training participation. In an exactly solvable model, we show that these risks are governed by a common quantity: the leave-one-out residual, which measures the part of a node's label that its neighborhood cannot explain. They move in opposite directions. When the neighborhood explains the label well, the node leaves little membership signal in the model, but its label remains easy to reconstruct from the retained graph. When the neighborhood is less informative, reconstruction becomes harder while membership leakage increases. This exposure persists even under exact retraining—the reference standard that approximate unlearning methods seek to match—because unlearning modifies only the model and the information lives in the retained graph. Across multiple unlearning methods and real-world graphs, our experiments support the theoretical prediction: membership attacks are least effective precisely where label-reconstruction risk is highest. Membership inference alone is therefore an incomplete audit of graph unlearning and should be paired with reconstruction-based evaluation.