- 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
-
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.
-
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.
-
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.
-
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.
-
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
-
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?
-
Which assumptions on the task, features, and labels justify the connection between homophily, reconstruction, and memorization?
-
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?
-
What insight does the linearized analysis provide beyond the predictability assumptions built into the data model?
-
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?
-
If the assumption is that similar labels share similar features, why using a GNN at all?