- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper aims to perform circuit discovery on GNNs by proposing CircuitFACT. For a GNN computation on a particular graph, CircuitFACT unrolls the GNN's computation tree on that instance at the neuron resolution, then uses Shapley values to attribute the computation tree components. The Shapley values are thresholded and the tree is pruned to produce a concise circuit. The authors compare CircuitFACT against a zero-ablated activation patching, finding that CircuitFACT is more reliably able to identify circuits which meet a particular significance threshold.
Critical strengths
- It is interesting that CircuitFACT unrolls both the GNN's internal computation graph and the message-passing computation tree on individual input graphs. This allows for visualization of how a circuit responds to individual nodes, such as Figure 4.
- Using Shapley values rather than activation patching or attribution patching machinery is an interesting difference from existing circuit discovery
Critical weaknesses
-
It is not clear to me why the median is chosen as the "active" cutoff in Eq. (4) rather than a constant cutoff of, say, 0. It seems conceivable that a neuron with a positive activation (but below the median) should still be considered, particularly when there is significant class imbalance or rare node types.
-
I think the -value estimation in Section 5.1 needs further justification, particularly if it is being used to exclude certain circuits from the comparison in Table 1. It seems that the Shapley value is better than zero-ablation mostly with respect to this -value, and I think justifying the -values is necessary to appreciate the comparison between Shapley attribution and zero-ablation.
Questions for authors
Questions
-
Can the authors provide further justification for the median cutoff to consider a neuron "active"?
-
Why threshold circuits based in the estimated -value in Section 5.1? What are the best -values achieved by the unreported zero-ablation circuits?
-
Can the authors provide any runtime analysis (either theoretical or wall-clock) for CircuitFACT? Even with Monte Carlo sampling, Shapley values can be inefficient to estimate; this is part of the original motivation for EAP-style attribution patching, which only requires one backwards pass (or a few, for EAP-IG).
Clarifications
-
Section 5.2 (lns. 461-463) asserts that the zero-ablated circuit retains connections that are uninformative because they contain negative evidence for the predicted class. But isn't this information relevant to the prediction by helping characterize why the confidence isn't higher? Classically, one of the values of SHAP is that it can provide both positive and negative feature contributions, so it seems strange to me to discard this information.
-
Why is the for zero ablation restricted to ?
5 comments
I thank the authors for their response, which has clarified several points. A few of my questions remain:
p-values
Thank you for this clarification. One part of my question has not been answered: what -values are achieved by the non-significant circuits? I understand the trend overall is that Shapley values are more efficient than zero-ablation, but I still find it difficult to evaluate the difference between the two without the full context of their significance. If zero-ablation, for example, routinely identifies circuits that are near chance, then the advantage is very clear; if, on the other hand, zero-ablation circuits are only barely deemed insignificant because the cutoff is (a standard but ultimately somewhat arbitrary choice) then the tradeoff is more nuanced.
Median cutoff
Thank you for clarifying. It makes sense that the cutoff should be selective to keep the Shapley games manageable, and that the median is more robust than the mean in this setting. I would still be interested to see an comparison of this choice at different quantiles or by using the mean, although this is more of a suggestion: I recognize it may be difficult to evaluate this comprehensively in the time remaining, and I weight the first question more heavily.
Distribution of p-values for all circuits
We thank the reviewer for reminding us of this question, which we did not address in our previous response, and we apologize for the oversight. To answer it, we re-ran the significance test on all circuits of the five unseeded runs, for both methods, and report the full distribution of p-values below.
Each circuit is compared with 50 random neuron sets of the same size through two tests, ablation and activation; its p-value is the smaller of the two, and the circuit is significant if p ≤ 0.05. Circuits is the total number of circuits, Sig. (p ≤ 0.05) the percentage of significant ones, and Non-sig. the number of non-significant ones. For the non-significant circuits, Median p (non-sig.) reports their median p-value, and the columns 0.05 < p ≤ 0.10, 0.10 < p ≤ 0.25, 0.25 < p ≤ 0.50 and p > 0.50 show how they are distributed across p-value ranges. A median close to 0.05, or a high value in 0.05 < p ≤ 0.10, would mean that these circuits narrowly miss the threshold, while higher values mean that they are far from it.
The table shows that the zero-ablation circuits that are not significant do not miss the threshold by a small margin: most of them have p-values far above 0.05. The advantage of Shapley therefore does not depend on the choice of the 0.05 threshold, and it still holds with a looser threshold such as 0.10.
| Dataset / Model | Method | Circuits | Sig. (p ≤ 0.05) | Non-sig. | Median p (non-sig.) | 0.05 < p ≤ 0.10 | 0.10 < p ≤ 0.25 | 0.25 < p ≤ 0.50 | p > 0.50 |
|---|---|---|---|---|---|---|---|---|---|
| MUTAG GCN | Shapley | 127 | 57% | 54 | 0.20 | 31% | 26% | 20% | 22% |
| MUTAG GCN | Zero-abl. | 124 | 15% | 106 | 0.38 | 11% | 25% | 31% | 32% |
| MUTAG GIN | Shapley | 147 | 59% | 60 | 0.53 | 10% | 15% | 23% | 52% |
| MUTAG GIN | Zero-abl. | 151 | 30% | 106 | 0.39 | 14% | 19% | 29% | 38% |
| MUTAG GAT | Shapley | 150 | 51% | 74 | 0.27 | 22% | 27% | 24% | 27% |
| MUTAG GAT | Zero-abl. | 146 | 27% | 107 | 0.24 | 23% | 28% | 23% | 25% |
| Mutagenicity GCN | Shapley | 147 | 37% | 93 | 0.20 | 30% | 30% | 19% | 20% |
| Mutagenicity GCN | Zero-abl. | 144 | 12% | 126 | 0.26 | 13% | 36% | 29% | 22% |
| Mutagenicity GIN | Shapley | 154 | 21% | 121 | 0.36 | 10% | 30% | 31% | 29% |
| Mutagenicity GIN | Zero-abl. | 153 | 16% | 128 | 0.31 | 11% | 25% | 37% | 27% |
| Mutagenicity GAT | Shapley | 156 | 35% | 102 | 0.22 | 24% | 38% | 20% | 19% |
| Mutagenicity GAT | Zero-abl. | 144 | 27% | 105 | 0.28 | 18% | 21% | 37% | 24% |
| NCI1 GCN | Shapley | 143 | 38% | 89 | 0.18 | 26% | 36% | 17% | 21% |
| NCI1 GCN | Zero-abl. | 144 | 17% | 120 | 0.29 | 18% | 27% | 24% | 32% |
| NCI1 GIN | Shapley | 153 | 17% | 127 | 0.34 | 8% | 27% | 38% | 28% |
| NCI1 GIN | Zero-abl. | 154 | 19% | 125 | 0.28 | 18% | 26% | 33% | 23% |
| NCI1 GAT | Shapley | 157 | 27% | 115 | 0.20 | 21% | 33% | 24% | 22% |
| NCI1 GAT | Zero-abl. | 148 | 19% | 120 | 0.28 | 15% | 28% | 38% | 19% |
| AIDS GCN | Shapley | 149 | 66% | 50 | 0.12 | 48% | 28% | 8% | 16% |
| AIDS GCN | Zero-abl. | 151 | 36% | 97 | 0.22 | 19% | 37% | 30% | 14% |
| AIDS GIN | Shapley | 147 | 41% | 86 | 0.23 | 27% | 27% | 19% | 28% |
| AIDS GIN | Zero-abl. | 148 | 30% | 103 | 0.32 | 20% | 21% | 36% | 22% |
| AIDS GAT | Shapley | 160 | 53% | 75 | 0.14 | 39% | 29% | 15% | 17% |
| AIDS GAT | Zero-abl. | 127 | 17% | 106 | 0.27 | 21% | 26% | 35% | 18% |
| All | Shapley | 1790 | 42% | 1046 | 0.24 | 23% | 30% | 23% | 25% |
| All | Zero-abl. | 1734 | 22% | 1349 | 0.30 | 17% | 27% | 32% | 25% |
Median cutoff (Eq. 4). We want to retain, for each neuron, only the trees on which it fires strongly relative to its own behaviour. The median provides such a relative, per-neuron criterion: it selects the upper half of each neuron's activation distribution, regardless of its scale, which varies across neurons, layers and architectures. A fixed cutoff at 0 does not have this property: it would treat any positive activation as relevant, so neurons that are weakly but almost always positive would be considered active on nearly every tree, inflating the candidate sets and the cost of the Shapley games. We prefer the median to the mean because activation distributions are typically skewed, with many values close to zero, and the mean is sensitive to this skew and to a few large activations. Regarding rare node types, activity at the input layer is not based on the median: an input feature is active whenever the corresponding atom type is present (Sec. 4), so rare atom types are never filtered out.
p-values (Sec. 5.1). Ablation and activation are strong interventions: setting many neurons to zero or to a high value can change the prediction regardless of which neurons are chosen. The test rules out this possibility by comparing each circuit with K = 50 random sets with the same number of neurons per layer; a circuit is significant only if its effect exceeds that of almost all random sets, i.e., if its effect is due to the specific neurons it contains and not to the size of the intervention. This is a standard Monte Carlo permutation test; the +1 correction (Phipson & Smyth, 2010) avoids zero p-values. The advantage of Shapley does not depend on this filter: the results for all extracted circuits, without any significance filtering, are reported in the "All" rows of Tables 3–6 in the appendix and show the same trend (e.g., on MUTAG, class-0 ablation of 92.3% vs. 26.7% for GAT and 90.3% vs. 9.1% for GIN).
τ for zero-ablation. The values {0.7, 0.8} were selected by a grid search over 0.3 to 0.9, in which they gave the best results for zero-ablation; lower values yielded larger and less effective circuits. We will report the full grid in the appendix.
Runtime. Each Shapley game is local: the value νt(S) is the activation of the target t computed from the activations of the layer below, so each evaluation is a single-layer computation rather than a full forward pass. Estimating the contributions for one target on one computation tree therefore costs M⋅∣Pt∣ such evaluations, where ∣Pt∣ is bounded by the layer width (32 in our models) and is further reduced by the activity filter of Eq. 4. The total cost grows linearly with the number of distinct computation trees and with the number of targets visited during backward tracing. We agree that this is more expensive than EAP, which needs a single backward pass, but Shapley values measure the effect of actual interventions rather than a first-order approximation, which can be inaccurate when activations saturate. Wall-clock times for all configurations are reported below and will be added to the revision.
Negative evidence (Sec. 5.2). We agree that negative contributions are informative, and CircuitFACT does not discard them. Negative evidence is captured at the level of circuits: some circuits support the predicted class and others oppose it (Sec. 5.1, where the latter are tested with the activation intervention), and the prediction results from the combination of these excitatory and inhibitory circuits; the projections in Fig. 4 show both positive (red) and negative (blue) contributions. Within a single circuit, however, all elements should agree in sign, since a circuit is meant to describe one coherent mechanism that pushes the prediction in one direction. Our point in Sec. 5.2 is that the Shapley circuit satisfies this property, whereas the zero-ablation circuit mixes connected neurons with opposing contributions within the same circuit, which makes it a less coherent mechanism. We will clarify this sentence in the revision.
Running times and machine
Total for the 12 runs: 2 h 49 min.
Models (training included) and all extraction and verification runs used this machine and this CPU setup.