acceptodds
Under review as a conference paper at ICLR 2027

Beyond Membership: Blind Spot in Graph Unlearning Audits

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
graph unlearning, machine unlearning, membership inference, graph neural networks, privacy auditing, node classification, right to be forgotten, message passing

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.25 over 4 reviews, above 2% of the others.
Reviewer_v29DOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies the distinction between detecting a node’s training membership and recovering its label after graph unlearning. For ridge regression on fixed message-passing representations, it relates membership exposure before deletion and label reconstruction after supervision deletion through the leave-one-out residual. It also analyzes reconstruction from retained neighborhood information under full node deletion and reports experiments using exact retraining and four approximate unlearning methods on two social networks. The authors advocate evaluating membership inference and label reconstruction separately.

Critical strengths
  • Proposing a distinction between privacy objectives. The paper emphasizes that removing evidence of training participation and preventing sensitive-label inference are different goals, encouraging a more explicit interpretation of unlearning audits. The validity of these views, however, are contested later.

  • An analytically tractable framework. The restricted ridge-regression setting permits an explicit characterization of the relationship between membership exposure and post-deletion label reconstruction, with identifiable assumptions. This is a good first step in a valuable direction.

  • Relevant reference comparisons. The experiments include exact retraining, approximate unlearning methods, and a model-free reconstruction baseline, helping distinguish residual training influence from predictability through retained graph information.

Critical weaknesses
  1. The central problem is insufficiently justified. Recovering a deleted node’s label does not, by itself, establish that information about its training participation remains. A model can also predict the label of a node that never participated in training. Although the paper acknowledges this distinction, it does not convincingly explain why such predictability constitutes a blind spot in evaluating unlearning, rather than a separate attribute-inference problem. The transductive setting alone does not resolve this conceptual issue.

  2. The argument relies on inadequately foregrounded assumptions about structure, features, and labels. Claims that homophilous neighborhoods reveal labels, while other neighborhoods force memorization, require explicit conditions on the prediction task and the relationship between features and labels. These conditions should be central to the motivation, rather than presented as broadly applicable properties of graphs. This concern also applies to Figure 1. The discussion should address the task-dependent perspectives raised by [1].

[1] Arnaiz-Rodriguez and Errica, "Oversmoothing, Oversquashing, Heterophily, Long-Range and More: Demistifying Common Beliefs in Graph Machine Learning", ICLR 2026.

  1. The reconstruction scenario needs a stronger practical justification. The attacker must know the target’s former connections and be able to reinsert a ghost node at the correct location. Although the experimental protocol specifies a blank profile, the introduction does not explain how the resulting feature configuration supports the claimed reconstruction or when this access is realistic. The authors should establish what follows from plausible attacker knowledge and what follows from assuming access to sufficiently informative neighborhood context.

  2. The theoretical interpretation appears reductive. The statement that a model can only remember what its surrounding data cannot explain presents a result for a restricted linearized learner as a general explanation of memorization. My concern is whether the analysis identifies the underlying cause or formalizes predictability already imposed by the assumed data relationships. The contribution beyond this assumed relationship needs to be articulated more clearly.

  3. The presentation severely obstructs scientific understanding. The manuscript exhibits surface-level linguistic fluency but lacks semantic precision and a coherent explanatory progression. Formulaic statements and repeated metaphors prevail over definitions and intuition. Specific examples from the abstract and introduction include:

  • Abstract, p. 1, opening sentences: The text moves from detecting training participation to recovering a node’s label without first clearly distinguishing the two objectives or explaining why the latter changes the interpretation of an unlearning audit.
  • Abstract, p. 1: “These risks” and “They move in opposite directions” have insufficiently precise referents. Likewise, “label-reconstruction risk is highest” leaves unclear whether risk denotes reconstruction accuracy, error, or another quantity. This ambiguity is particularly problematic because risk has an established technical meaning in machine learning.
  • Introduction, p. 1: The assertion that a homophilous node’s label is recoverable from its neighbors’ labels needs explicit task and data assumptions. As written, it introduces a central premise as though it were generally valid [1].
  • Introduction, p. 2: The Netflix re-identification analogy does not explain the connection to determining training participation. It broadens the privacy discussion without clarifying the specific unlearning problem.
  • Introduction, p. 2: Statements such as “a model can only remember what the data around a node fails to explain” and “presence inference reads that stored part” require operational definitions. Similarly, the claim that the observed tradeoff is what “the theorem says must be there” does not communicate its conditions or scope.

These problems continue in Section 3.1, where definitions and facts are presented consecutively with little intuition or connective explanation. Figure placement and readability also need attention, particularly around Figure 3. A substantial rewrite is necessary to make the problem, assumptions, and conclusions accessible and precise.

Questions for authors
  1. What does successful label reconstruction establish about a deleted node’s prior training participation? How does the proposed concern differ from predicting the label of a never-trained node?

  2. Which assumptions on the task, features, and labels justify the connection between homophily, reconstruction, and memorization?

  3. In what realistic deployment can an attacker obtain the target’s archived connections and submit a ghost query? How does the chosen ghost feature vector affect the argument?

  4. What insight does the linearized analysis provide beyond the predictability assumptions built into the data model?

  5. Can the abstract and introduction explicitly define the two attack objectives and their relationship, replace ambiguous terminology, and state the conditions behind the claimed tradeoff?

  6. If the assumption is that similar labels share similar features, why using a GNN at all?

Reviewer_o7mMOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

Paper Summary

The paper argues that membership-inference audits alone do not capture whether a deleted node’s label remains recoverable from the retained graph. For ridge regression on fixed graph representations, it derives a relationship between membership exposure and post-deletion label reconstruction through a leave-one-out residual, and establishes a structure-only reconstruction lower bound under a contextual stochastic block model. The authors evaluate exact retraining and several approximate unlearning methods on Pokec-n and Cornell5, comparing membership inference with label reconstruction using a ghost query and model-free baselines. The results show that labels can remain recoverable from retained graph information even when membership inference is near chance after exact retraining.

Critical strengths

Critical Strengths

  1. The paper distinguishes two privacy questions that membership inference does not answer. It separates whether a model reveals that a node participated in training from whether the node’s label can still be inferred from the retained graph. This distinction can help prevent overinterpreting a chance-level membership attack as evidence that all sensitive information has become unrecoverable.

  2. The paper provides a formal analysis and evaluates the distinction after exact retraining. Its residual-based analysis relates membership exposure to label reconstruction under a defined model, while experiments on two real-world graphs include exact retraining and model-free baselines. These results support the claim that some post-deletion label exposure can come from retained graph information rather than residual influence in the unlearned model.

Critical weaknesses

Critical Weaknesses

  1. The paper’s central observation may add limited insight beyond known graph-based attribute inference. That labels can remain predictable from a node’s neighbors after the node is deleted from a model is intuitive in homophilous graphs and closely related to established attribute-inference results. The paper should more clearly establish what its analysis and audit add beyond confirming this phenomenon, and how they change practical unlearning evaluations or defense decisions.

  2. The theoretical and empirical evidence has limited scope. The formal relationship is derived for ridge regression on fixed representations under specific assumptions, while the experiments cover two graphs and one GCN setting. This leaves unclear whether the proposed relationship applies to common nonlinear GNNs and realistic deletion settings. The ghost-query evaluation also assumes access to archived neighborhood information, which limits how broadly its practical implications can be interpreted.

Questions for authors

Questions For Authors

  1. Evidence affecting the recommendation: What does the residual-based analysis establish beyond prior results on graph-based attribute inference? Can the authors identify a concrete auditing or defense decision that changes when label reconstruction is measured alongside membership inference?

  2. Clarification: Which assumptions are essential to the relationship between membership exposure and label reconstruction? How should readers interpret this result for nonlinear GNNs, where graph representations may change after node deletion?

  3. Clarification: What information and model access does the ghost-query attacker require, particularly regarding archived edges and the ability to query a reconstructed node? How do the conclusions change when the attacker lacks this information or access?

Reviewer_gvcJOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This work highlights that membership inference attacks (common in graph unlearning literature) is not enough to measure the effectiveness of unlearning. The authors argue that while membership inference could reveal no membership of the forgotten nodes in the training data, sensitive information, such as labels, can still be inferred about those nodes from their retained neighbours. In other words, the very target of unlearning in removing sensitive information about forgotten nodes is not necessarily covered by membership inference metrics alone. They show that, under a perfectly solvable model, the leave-one-out residual explains this tradeoff. In other words, the leave-one-out residual measures the part of a node's label that is unrecoverable by knowing its neighbours' labels alone. They argue that this behaviour is present even in the retrained model (a model trained from scratch on only the retained data), which is the golden standard in most machine unlearning works.

Critical strengths

None

Critical weaknesses

The work is poorly written and doesn't flow naturally. The language used reads odd in most sections. Are the authors sure this is how they would love to present the material? A few examples for this poor writing in arguably the most important section: PRELIMINARIES AND THREAT MODEL.

  • Line 192: "exact for supervision deletion". What does exact here mean? It is in terms of what? What is supervision deletion?
  • Line 193: "exact unlearning". What is exact unlearning? Where is it defined? How is it performed? Is it retraining or approximate unlearning?
  • In line 196, it is said that "a query at ν\nu returns zz". So, zz is the output returned for a query ν\nu. However in line 201 (and repeated in line 205) it is said that "The attacker sees one noisy query zz at ν\nu". So, is zz a query or an output?
  • Line 201: The attacker could see yνy_{\nu}, but yνy_{\nu} was said to be a secret label in line 186. If the attacker could know the label yνy_{\nu}, then why is it called secret?
  • Line 205: "After deletion is honored exactly". What does it mean for deletion to be honoured?
  • Line 206: "the retained prediction (under node deletion, via a ghost query on archived context)". What does it mean for the prediction to be retained? So the node is deleted but its prediction (whatever that means) is retained? What is a ghost query? What is a context here and how can it be archived?
  • Starting in line 209: "The two threat models are deliberately asymmetric — reconstructing a label the adversary already holds is vacuous — and the population statements keep the label-informed membership convention explicit". This statement is not understandable. Which threat models are meant here? What does it mean for them to be deliberately asymmetric? In other words, why are they kept asymmetric? What is the benefit of that (since it is "deliberate")?
  • In line 212: Assumption 1 is completely ambiguous. What is a "retained fit"? Is it an unlearned model? Fitted how? Why is the near interpolation assumption mentioned here if it is only used for the appendix results? What is the near-interpolation assumption anyway? Why is this version informal while it is in the main text?

These ambiguities are present in all sections of this draft. I think the draft requires a major rewrite before it is ready for a review. I recommend the authors to rewrite the prose using an academic, precise, and simple-to-read style, clean of inconsistencies.

Questions for authors

None.

Reviewer_zD9sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper argues that the standard way to verify graph unlearning is incomplete. Today, a deletion is judged "successful" when a membership inference attack (MIA) can no longer tell the user was in the training set. But on a graph, a user's label is often predictable from their friends, who remain after the user is deleted so the label can stay exposed even when the MIA sees nothing. The paper shows both risks are controlled by one quantity i.e., how much of the user's label their neighbors fail to explain and the two risks move in opposite directions. Users whose neighbors explain their label well pass the MIA cleanly but are easy to reconstruct, while users whose neighbors do not explain their label are detected by the MIA but hard to reconstruct. Theorem 1 proves this trade-off in a simplified model, and shows it survives even exact retraining, because deletion changes only the model while the label lives in the retained graph. On Pokec-n and Cornell5, about 20% and 16% of users pass the membership audit, yet one query on their friend list recovers the label of 88% and 85% of them. The authors conclude that membership audits should be paired with reconstruction-based audits.

Critical strengths
  1. The paper identifies that a clean MIA audit does not mean the label is safe.
  2. The coupling result is new.
  3. The paper proves and shows that exact retraining does not remove the exposure, because the label lives in the retained graph, not the model.
Critical weaknesses
  1. The leakage channel itself is known. Prior work already shows a node's attributes can be inferred from its retained neighbors. What is new here is the framing.
  2. The study uses only two homophilous social graphs, with one task each. It does not test other graph types, tasks, or low-homophily settings.
Questions for authors
  1. Your theorem assumes a fixed linear head on frozen features (the NTK regime). Does the opposite-direction frontier still hold for nonlinear GNNs trained end to end? On the real graphs, how much of the result depends on freezing the representation versus training it jointly?
  2. The effect is strongest under homophily. Does it still appear on heterophilous graphs, or on non-social graphs where neighbors are less predictive of the label?
  3. What does the paper add beyond Yuan et al. (2024) and Olatunji et al. (2023), which already show labels are recoverable from retained neighbors? If the unlearning-audit framing and the exact-retraining test are removed, what new finding remains?
  4. Is label reconstruction something an unlearning audit should be responsible for, given that the label is carried by the neighbors' data rather than the deleted node's own record? How would you separate "the node was forgotten" from "the neighborhood still predicts the label"?

[a] Yuan et al. Unveiling privacy vulnerabilities: Investigating the role of structure in graph data (2024) [b] Olatunji et al. Does black-box attribute inference attack on graph neural networks constitute a privacy risk? (2023)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.