acceptodds
Under review as a conference paper at ICLR 2027

Observation Limits of Node Attribution under Graph-Level Supervision

Abstract

Node attribution ranks nodes by their relevance to a graph-level outcome, supporting applications such as localizing faulty program statements from test outcomes. Existing evaluations emphasize faithfulness to a trained model, leaving unresolved whether the observations distinguish the responsible node from other candidates. We study the limits that available observations impose on node attribution in real software faults. Our analysis characterizes attainable localization accuracy, relates indistinguishability under shared message passing to equal node scores, and gives upper confidence bounds from observation counts collected separately for each candidate target. To assess the prevalence of this ambiguity, we enrich test coverage with local program descriptors and identify repaired and non-repaired statements that remain indistinguishable under these observations. Such pairs occur in 34.8% of eligible Defects4J faults and 33.1% of eligible Codeflaws faults. The three evaluated architectures and three coverage-based scoring formulas tie on every matched pair, yielding pair AUC 0.50. We then separate the effects of target information and training supervision by independently varying node labels and a node feature encoding oracle target information. On structurally interchangeable EPFL circuit nodes, this target anchor alone gives mean AUC 0.980, compared with 0.511 for node supervision alone, while combining both gives mean pair AUC 1.0. These results connect ambiguity in real workloads to the information required for localization and motivate evaluating node attribution separately from graph-level prediction.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, node attribution, explainability, identifiability, Weisfeiler-Leman test, message passing, fault localization

Reviews

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

This paper studies the limitations of node attribution when models are trained with graph-level supervision. The authors provide a theoretical analysis showing when different node targets cannot be distinguished from the available observations. They evaluate this problem using real software faults from Defects4J and Codeflaws, finding that around one-third of the eligible faults contain repaired and non-repaired statements that remain indistinguishable under the selected features. They also conduct controlled experiments to examine how additional target information and node-level supervision affect localization accuracy, and propose a finite-sample bound on the best achievable accuracy.

Critical strengths
  • The paper highlights an important distinction between graph-level prediction and node-level attribution, showing why accurate predictions do not necessarily imply accurate identification of the responsible nodes.

  • The study includes real-world evaluations on Defects4J and Codeflaws. The finding that around one-third of eligible faults still contain indistinguishable repaired and non-repaired statements after adding program descriptors is interesting.

  • The evaluation covers multiple GNN architectures, fault-localization methods, and controlled experiments. The analysis of target information and node-level supervision helps explain the factors affecting localization accuracy in the evaluated settings.

Critical weaknesses
  • The theoretical novelty of the paper appears limited, as several results build on established findings in Bayesian hypothesis testing and the 1-WL expressivity limitations of GNNs. It is unclear what new theoretical insights the paper provides beyond applying these existing results to node attribution.

  • The proposed finite-sample bound is evaluated only on synthetic observation channels with a small alphabet size. The paper acknowledges that real-world coverage observations can have a much larger alphabet, but does not demonstrate whether the bound provides meaningful estimates for actual software faults.

  • Proposition 4 requires independent observations collected separately for each candidate target. In real fault-localization scenarios, collecting such observations may be difficult because the actual faulty location is unknown.

  • The real-world experiments identify faulty and non-faulty statements that are indistinguishable under the selected features. However, they do not establish whether these statements remain indistinguishable when richer program information is available, limiting the generalizability of the findings.

  • Table 13 shows that none of the six evaluated molecular or motif datasets contain mixed-relevance WL classes at the selected refinement depth, while only 13 of 9,129 sentiment trees contain such classes. Although these results do not invalidate the theoretical findings, they raise questions about how frequently this particular ambiguity occurs in general graph attribution tasks.

  • Section 3.1 indicates that test outcomes are used both as graph-level labels and in the spectrum features provided to the models. This raises concerns about whether the high test-outcome AUROC reported in Table 2 partly reflects information about the prediction targets already available in the inputs.

  • Table 2 reports pooled node AUROC, which includes comparisons between statements from different faults. Since fault localization aims to rank statements within individual faults, per-fault ranking metrics would be more informative. Although the appendices report macro node AUROC for the spectrum methods and optimistic Top-1 ceilings, these do not directly show the Top-1 performance of the trained GNN models.

  • Some prior work shows that many tests in Defects4J are added after the bug is reported or fixed. Since this paper studies limits imposed by available observations, test provenance is directly relevant. It is unclear whether the reported ambiguity rate holds when using only tests available before debugging.

Questions for authors
  1. Theorem 1 builds on established results in Bayesian hypothesis testing, while Lemma 2 follows the known 1-WL expressivity limitations of message-passing GNNs. Proposition 4 also builds on existing concentration inequalities. Could the authors clarify what new theoretical insights these results provide beyond their application to node attribution?

  2. Can the authors demonstrate a meaningful bound on Defects4J or Codeflaws, or explain how the required observations could be collected in practice?

  3. Could the authors report the Top-1 performance of the trained GNN models, particularly how often the observed ambiguity affects actual fault-localization performance?

1 comment

Thank you for your detailed review. We evaluated per-fault Top-1 with the original checkpoints and tested richer source observations. Highest-score ties reduce localization success, while source context resolves most original matches, showing how the framework connects ranking errors to the information supplied.

1. What is new beyond Bayesian testing and 1-WL?

Our contribution links observation-level identification to equal scores in shared representations and their evaluation consequences. Building on Bayesian testing and 1-WL, we show that swapping relevance within equal-score classes preserves AUC even when the correct node changes. Thus aggregate performance can miss the localization distinction. For finite samples, the count-based bound uses one sampling radius, compared with two for the mixture-TV relaxation. The real-fault rankings below test the evaluation consequence.

2. Actual trained-model Top-1 and the effect of ambiguity

Equivalent repaired/non-repaired candidates reduce tie-aware Top-1 in all three trained architectures. We use the nine original checkpoints and reduced graphs. Top-1 breaks ties uniformly and succeeds on any repaired statement. Percentages average seeds within each fault, then faults.

MethodRoot-held-out: 31 faultsProject-held-out: 19 faults
GraphSAGE17.228.9
GAT15.637.7
Transformer16.141.2
Ochiai20.740.8
DStar20.743.4
Tarantula19.540.8

As the table shows, actual Top-1 varies across architectures and held-out splits. Highest-score ties reduce root-held-out Top-1 by 4.3, 4.8, and 5.4 percentage points for GraphSAGE, GAT, and Transformer relative to optimistically resolving those ties. Every affected group contains a verified repaired/non-repaired equivalent pair. This quantifies ambiguity in fitted rankings and potential recovery from resolving ties, rather than gains achieved by a new localizer.

3. Richer program information

Real source context distinguishes almost all coverage-equivalent pairs. We tested all 924 original pairs in 115 Defects4J faults using fixed buggy-source versions and features. Removing comments and whitespace while retaining identifiers, literals, and operators leaves 54 matched pairs in 16 faults. A fixed two-line context on either side leaves one pair in one fault. This supports enriching observations before changing the scorer. Distinguishable inputs enable separation, while successful localization remains a separate evaluation.

4. Finite-sample bound and target-specific observations

The bound is informative on compressed execution observations when controlled faults supply independent samples per target. All seven original EPFL designs give non-trivial bounds. A fixed ordering selected two existing injected locations per design, each with 2,000 independently sampled uniform inputs. For an equally likely target and one fresh execution, the observation is either the output-failure bit or the healthy/faulty output bits. All 14 bounds hold jointly with 95% confidence: upper accuracies, rounded upward, range from 54.2–54.9% for the binary channel and 54.8–56.4% for the four-symbol channel. The target is diagnosis from that compressed observation, with input vectors and other traces withheld. Controlled injection supplies per-target samples that a single natural fault does not. The Defects4J rankings above separately measure natural-fault ambiguity.

5. Frequency beyond software and the oracle anchor

The molecular and motif controls show that natural masks can already align with distinguishable classes: zero of the six tested datasets has mixed classes at the reported depth, versus 13 of 9,129 sentiment trees. This supports measuring the observation–target relationship for each task, rather than assuming within-class ambiguity is universal. The oracle anchor separately isolates target information from node supervision. Its role is a controlled intervention, while the new source-context comparison supplies realistic program information.

6. Test-outcome features and test provenance

The high test-outcome AUROC partly reflects outcomes already supplied in the spectrum features. It therefore measures outcome consistency, while localization is evaluated against withheld repair targets through within-fault ranking.

Removing later tests cannot separate an existing coverage-equivalent pair when the buggy program, candidate set, and static descriptors stay fixed: equal coverage columns remain equal after deleting rows, as do their spectrum counts. Therefore the original matched pairs persist for any pre-debug subset of those tests under this fixed candidate universe. The 34.8% figure describes the archived eligible population, rather than a newly filtered historical-test population.

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

This paper investigates the limitations that available observations impose on node attribution, a task that aims to rank nodes according to their relevance to a graph-level outcome. The authors focus particularly on fault localization in software systems, where the objective is to identify faulty program statements based on test outcomes. The paper argues that existing evaluation approaches primarily emphasize faithfulness to a trained model, without sufficiently considering whether the available observations contain enough information to distinguish the responsible node from other candidates. To address this gap, the authors develop a theoretical framework that characterizes the attainable localization accuracy, examines how indistinguishability under shared message passing leads to identical node attribution scores, and derives upper confidence bounds based on observation counts collected separately for each candidate target.

Critical strengths
  1. S1. Well-defined problem formulation. The paper presents an interesting and mathematically grounded problem formulation. The theoretical analysis provides a structured perspective on the limitations of node attribution and the role of observational information in determining localization accuracy.

  2. S2. Important and practically relevant problem. The paper addresses an important problem with potential implications for several applications, including software fault localization and fraud detection. Understanding when observations are sufficient to identify responsible nodes is a relevant research question, particularly in settings where reliable attribution and interpretability are essential.

Critical weaknesses
  1. W1. Limited comparison with state-of-the-art approaches. One of my main concerns is the lack of experimental comparisons with existing state-of-the-art methods for node attribution and fault localization. Although the theoretical analysis is interesting, the evaluation would benefit from stronger baselines to better contextualize the proposed framework and establish its relevance compared to existing approaches.
  2. W2. Insufficient experimental evidence and benchmarking. The reported results do not appear sufficiently strong to support the broader claims of the paper. In particular, the current benchmarking setup seems limited, making it difficult to assess the practical significance and generality of the theoretical findings. I would encourage the authors to conduct a more comprehensive experimental evaluation across additional datasets and benchmark settings to better validate their conclusions.
  3. W3. Limited evaluation across different model architectures. The authors do not sufficiently investigate whether the theoretical findings and empirical observations generalize across different model architectures. In particular, it would be valuable to evaluate the proposed framework using multiple GNN architectures with different message-passing mechanisms and representational capacities. Such experiments would help clarify whether the identified attribution limitations are consistent across architectures or depend on specific modeling choices.
Questions for authors
  1. Q1. Comparison with state-of-the-art foundation models. Is there a particular reason why the authors do not evaluate their approach against recent state-of-the-art foundation models? Given the growing capabilities of foundation models in code understanding and software fault localization, such comparisons could provide additional insights into the practical relevance of the proposed theoretical framework and whether the identified observation limitations also arise in more general-purpose architectures.
1 comment

Thank you for your comments and suggestions. We compared trained GNNs and fault-localization baselines using per-fault Top-1 and tested richer source observations. Ambiguity affects the fitted rankings, while source context resolves most matches, showing why model capacity and available information must be evaluated jointly.

1. Comparisons with attribution and fault-localization methods

Our matched evaluation finds highest-score ambiguity across all three trained architectures. We compare them with Ochiai, DStar, and Tarantula on identical held-out reduced graphs. Per-fault Top-1 uniformly breaks highest-score ties and averages three seeds per neural architecture. Percentages are:

Method31 root-held-out faults19 project-held-out faults
GraphSAGE17.228.9
GAT15.637.7
Transformer16.141.2
Ochiai20.740.8
DStar20.743.4
Tarantula19.540.8

As the table shows, the relative order of the neural architectures changes across the two held-out splits. All three neural models place verified repaired/non-repaired equivalent pairs in some highest-score groups. Optimistically resolving those ties would increase root-held-out Top-1 by 4.3–5.4 percentage points, linking the representation result to fitted-model decisions.

GNNExplainer supplies a complementary comparison because independently optimized masks can assign different scores to matched nodes. In its matched 31-fault evaluation, it breaks all 25 pair ties and ranks the repaired member higher in nine, giving pair AUC 0.36 and Top-1 0%. Thus score separation alone is insufficient evidence of target recovery. The controlled comparisons also include gradient-times-input, feature occlusion, and integrated gradients. These comparisons test the distinction between score separation and target recovery.

2. Benchmark breadth and practical generality

The real-software evidence covers two languages and fault populations: 330 eligible Defects4J faults and 2,509 Codeflaws faults. After adding the specified local descriptors, matched faults occur in 34.8% and 33.1%, spanning five Java projects and 550 C problem groups. On the same 2,349 Codeflaws faults, expanding the shipped test suite reduces matches from 34.5% to 31.9%. This comparison shows that collecting more observations removes some ambiguity while leaving some candidates unresolved.

For a richer observation channel, real source context distinguishes almost all original coverage-equivalent pairs. Across all 924 original Defects4J matched pairs, adding actual buggy-source line tokens leaves 54 pairs in 16 faults. A fixed two-line window on either side leaves one pair in one fault. Consequently, the practical recommendation is to introduce target-relevant source information before attributing unresolved candidates solely to model capacity. Identifying distinct source contexts and correctly choosing the repaired statement remain separate tasks.

The natural-mask controls identify where the mechanism applies. None of the six molecular/motif datasets has mixed-relevance WL classes at the reported depth, whereas 13 of 9,129 sentiment trees do. Executable circuit and Python-AST interventions separately test known target mechanisms.

3. Different message-passing architectures

The matched-candidate limitation persists across mean aggregation, additive attention, and multihead dot-product attention, tested with GraphSAGE, GAT, and a bipartite Transformer. On Codeflaws, all nine combinations of these architectures with native scores, gradient-times-input, and feature occlusion tie the matched candidates, including the 282 held-out pairs. Their common pair AUC of 0.50 follows the supplied representations despite differing scores elsewhere.

Broader executable-graph comparisons include GCN, GIN, GPS, and PNA. Across five architecture families and two executable domains, 30 primary runs attain graph accuracy 1.00 while architecture–domain mean within-orbit AUC ranges from 0.49 to 0.51. These controlled observations separate prediction from localization across aggregation mechanisms.

4. Foundation models and their additional information

We hold the supplied information fixed to isolate observation limits from differences in architecture. A foundation-model leaderboard changes both information and architecture, answering a different question. The observation theorem covers any estimator, including a foundation model, when its complete information has the same target-conditioned law. The 1-WL lemma specifically assumes shared message passing. Source text, pretrained knowledge, and execution feedback give code foundation models richer observations than our coverage graphs. The source-context results show why this matters. Thus the theorem supplies a criterion for their full information, while the 34.8% rate belongs to the measured coverage channel.

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

The paper studies limitations of node attribution under graph-level supervision. It distinguishes insufficient observation information from constraints of shared message-passing models and derives statistical bounds on localization accuracy. Experiments on real software faults and controlled graphs examine ambiguous candidate nodes and the effects of additional target information.

Critical strengths
  • The paper distinguishes limitations of available information from limitations of model representations.
  • Experiments on two real fault datasets provide useful evidence that ambiguous candidates persist after adding local program descriptors.
Critical weaknesses
  1. The practical significance of the empirical ambiguity remains unclear.

The ambiguity measurements are useful, but they rely primarily on coverage information and relatively coarse local program descriptors. Table 1 shows that adding these descriptors already substantially reduces the proportion of faults with indistinguishable candidates. It remains unclear how much ambiguity would persist with richer, practically available information, such as source context, data-flow dependencies, or execution-state observations. Although the paper evaluates additional tests and feature interventions, these experiments do not fully address this question. In particular, the oracle target-anchor experiment directly encodes the target identity rather than demonstrating that such information can be recovered from realistic program observations. Further analysis would help establish the practical significance of the reported ambiguity.

  1. The practical utility of the statistical bound remains insufficiently demonstrated.

Proposition 4 provides a finite-sample upper confidence bound on optimal localization accuracy, but its empirical evaluation is limited to small synthetic observation spaces. Appendix D explicitly acknowledges that the bound becomes uninformative for the full Codeflaws coverage alphabet. Although this does not affect its mathematical validity, it raises questions about its practical utility. The paper would be strengthened by demonstrating a non-trivial bound on at least one realistic observation setting, potentially using a meaningful compression of coverage information, and discussing the resulting trade-off between statistical tightness and information loss.

Questions for authors

See Weaknesses

1 comment

Thank you for your constructive feedback. We tested real source context and collected independent executions for controlled faults on the seven EPFL designs. Source context resolves most original matches, while the execution counts yield non-trivial bounds, showing how practical value depends on the observations supplied.

1. Does realistic source context resolve the measured ambiguity?

Real source context distinguishes almost all original coverage-equivalent pairs. We evaluated all 924 pairs across 115 Defects4J faults, fixing the source revision, pairs, tokenizer, and context width in advance. We removed comments and whitespace while preserving identifiers, literals, and operators. File names, line numbers, and repair identity were excluded from the features. The table counts original pairs that remain identical after each refinement.

Supplied observationRemaining pairsFaults with a remaining pair
Coverage + original local descriptors924115
Also source-line tokens5416
Also two source lines on each side11

As the table shows, readily available source context removes most of the original representation matches. This supports your proposed direction and gives the framework a practical use: identify which information distinguishes candidates before selecting a more capable localizer. The source-context comparison measures input distinguishability. We assess actual localization separately below using the original trained models.

The oracle target-anchor experiment addresses a different question: it crosses target information with node supervision to separate their effects. The anchor's near-perfect ranking is a controlled intervention, whereas the source-context result above demonstrates an observation available without knowing the repaired node. Data-flow and execution state would similarly define richer channels whose candidate distinctions should be evaluated on their own terms.

2. Does ambiguity affect actual fault-localization decisions?

Verified ambiguity reduces tie-aware Top-1 in all three trained architectures. We used the nine original checkpoints on 31 root-held-out and 19 project-held-out reduced graphs. Root-held-out Top-1 is 17.2%, 15.6%, and 16.1% for GraphSAGE, GAT, and Transformer, respectively, using uniform breaking of highest-score ties. Relative to optimistically choosing the repaired member of those same highest-score groups, the losses are 4.3, 4.8, and 5.4 percentage points. Every affected group contains a verified equivalent repaired/non-repaired pair. Thus the matches occur at the decision boundary of fitted models, beyond the existence of an ambiguous pair somewhere in a graph. These differences quantify optimistic tie resolution for the original scores.

3. When can the finite-sample bound be practically informative?

The bound is informative for compressed execution observations with independent execution samples for each controlled fault: all seven original EPFL real circuit designs yield non-trivial bounds. Before execution, a fixed ordering selected two existing fault locations per design with the same output and fault type. Each location received 2,000 independently drawn uniform binary inputs. For diagnosis from one fresh execution, the candidate prior is uniform over these two locations. The two prespecified observations are the output-failure bit (K=2K=2) and the pair of healthy/faulty output bits (K=4K=4). Input vectors, fault identity, and other traces are withheld from this compressed localizer.

Across all seven designs, Proposition 4 bounds optimal accuracy by 54.2–54.9% for the binary observation and 54.8–56.4% for the four-symbol observation, rounding upward. A union-bound allocation gives joint 95% confidence for all 14 bounds. These values come from executed target-conditioned counts, with known injected locations supplying the independent sampling. They demonstrate an informative bound on real designs under controlled faults, separate from natural Defects4J or Codeflaws records.

Compression can reduce estimation uncertainty while removing target information: if T=h(O)T=h(O), then AT≤AOA_T\leq A_O, because a rule using TT is also available from OO. The four-symbol channel retains healthy/faulty output values, while the binary channel keeps their mismatch. The four-symbol channel's larger alphabet raises the statistical allowance from about 4.2 to 4.7 percentage points at the same sample size. Accordingly, the bounds concern these one-execution summaries, not diagnosis with complete inputs or many traces. The source-context result above illustrates the complementary benefit of retaining richer observations. Both comparisons show why a useful certificate must match the information actually supplied to the localizer.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.