- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies when labels can be shared across graphs that contain the same explanation (e.g. a toxicophore). The authors assume the explanation is "sufficient", meaning the rest of the graph adds at most nats of label information given the explanation, and propose to use "pooled ERM."
Each training graph gets the label frequency of its explanation class as a soft target, and predictions are averaged within observed classes. They prove an oracle bound of from labels, where is the across-class VC dimension, along with risk-dependent and fast-rate variants. The authors perform experiments on synthetic constructions and real graph classification tasks.
Critical strengths
- The theoretical result removes the deterministic-label assumption of earlier work on label reuse (Shao et al., Zheng et al.) and allows arbitrary label noise within an explanation class at . This is interesting and somewhat useful.
- The experiments are broad and include sensible controls, such as permuted descriptors, graph-size control, tuned GNNs, GSAT/DIR comparisons.
- The authors report unflattering results in the appendix, such as full pooling hurting with mined keys and the Full-budget drop on MUTAGENICITY.
Critical weaknesses
-
The theoretical guarantees rely on a very strong assumption that is not established in practice. The paper assumes that the explanation contains essentially all the information needed to predict the label. However, the authors do not show that their mined explanations satisfy this assumption on real graphs. It is therefore unclear how relevant the main theoretical guarantees are to the practical setting.
-
The real-world results are not particularly promising. Specifically, 21 of the 24 significant improvements in Table 3 are concentrated on AIDS and TOX21. Breaking down the results by benchmark: On AIDS, the authors construct a simple control using just graph-size, and that beats the hybrid on 3/4 of the tested backbones. Tuning the GNN also largely eliminates the gains. DIR with GIN also outperforms the hybrid at every non-Full budget. On DHFR and PROTEINS, the method results in mostly insignificant improvements. TOX21 is the main dataset where meaningful gains remain, but the authors evaluate on an artificially balanced subset rather than the original, heavily imbalanced dataset. Since the proposed method relies on within-group label frequencies and majority voting, it is unclear whether these gains would hold on the original data distribution. On the controlled synthetic tasks, simple test-time majority voting is already enough to obtain most of the improvement. Furthermore, pooling can actually hurt performance substantially. For example, pooling all mined groups reduces accuracy by up to 12.4 points on AIDS (Table 24), and pooled ERM loses over 6 points on MUTAGENICITY with the full training pool (Table 26). The positive real-world results depend heavily on selective gating and retaining the original GNN's predictions elsewhere.
Overall, I find the theoretical contribution interesting, but the empirical results do not convincingly establish a sufficiently useful or general method for graph classification. A large portion of the practical benefit can already be obtained through simpler approaches, and the strongest gains either disappear against better baselines or depend heavily on the specific dataset and preprocessing choices.
Questions for authors
-
What is the practical advantage of the proposed method over simpler label-sharing approaches? In several experiments, majority voting already captures most of the improvements, and on real datasets, the gains depend heavily on selective gating and falling back to the original GNN. What does pooled ERM itself contribute beyond these simpler alternatives?
-
How relevant are the theoretical guarantees to the practical setting? The main guarantees assume that the explanation is approximately sufficient, but this is not established for the mined explanations used in the real-world experiments. Given that pooling can substantially hurt accuracy when the explanations are not sufficiently informative, what evidence supports applying the theoretical results to these settings?
8 comments
Reply to Reviewer ZBx4(2/2)
W2, continued (TOX21 on the original imbalanced distribution)
Thank you for raising this; we reran the experiment on the full data.
- Balanced-risk form. Because accuracy rewards predicting the inactive class under 11.6% positives, we score balanced accuracy and use class weights in training, in group counts and in the gate reference on the full 8,169-molecule collection. Sufficiency is preserved, and the weights enter only the estimation constants. Against a class-weighted GNN on the same strict budgets, gated majority sharing raises balanced accuracy in all 20 settings of four backbones, significantly in 13 (up to +4.2), and AUPRC significantly in 14 (Table 30).
- Selective pooled ERM is positive in 16 of the 20 settings and never lowers balanced accuracy significantly.
Details are in Table 4, Appendix F.3 and Tables 29–30.
W3 and Q1 (what pooled ERM adds beyond simpler sharing)
Thank you for this question. Pooled ERM goes beyond voting where the theory says it should, under label noise, with many rare keys, and on keys never seen in training.
- Label noise. Pooled training beats test-time voting on the same keys. On FOUR-MOTIF with 20% noise it gains +3.03*/+2.34* (GCN/GIN) at 5 graphs per class and +3.19*/+3.80* at 50 (Table 21).
- Many rare keys. In a new experiment (10, 20 and 40 motif types, up to 821 possible keys, 20% noise), pooled ERM is ahead of voting in 35 of 42 settings, significantly in 10, and never significantly behind.
- With the full pool the lead grows with the number of keys, to 4.7 points at L = 40, mostly on seen keys, where voting copies the noisy labels of keys seen only once or twice.
- On keys never seen in training, voting can only return the GNN, while the network trained by pooled ERM is more accurate in 36 of 38 cells, by up to 16 points where unseen keys are common.
- Noise-robust objectives. Under the same noise, pooled ERM beats generalized and symmetric cross-entropy and co-teaching in all 40 settings, by 5 to 48 points, because these objectives use no explanation classes (Appendix F.4).
The practical rule that follows on real data is to share labels where held-out labels show that the key beats the network, which is what the gate does, and to pool every key when labels are scarce or noisy and the key is informative.
Thank you again for the thorough review; we would be glad to discuss any of these points further.
I maintain my Weak Reject recommendation
Thank you for the detailed rebuttal and additional experiments. I appreciate the new evaluation on the original imbalanced TOX21 dataset, which addresses one of my earlier concerns. The experiments with rare explanation classes and noisy labels are also useful.
After examining the new results, however, I still have substantial concerns about the practical contribution.
First, regarding the connection between theory and practice, my understanding is that the new estimate of discarded label information is based on the difference in held-out cross-entropy between a key-only predictor and a calibrated GNN. This does not establish that the keys are approximately sufficient. A small difference between these two predictors does not necessarily mean that the full graph contains little additional label information (e.g., the GNN might simply fail to exploit that information). While Theorem 3.1 formally allows arbitrary key maps, the bound is only useful when the discarded-information term is sufficiently small. I do not think the new analysis adequately establishes this for the mined keys.
Second, the rebuttal reports that pooled ERM is within 1.43 points of the key-only predictor across all 64 real-data settings, with an average difference of just 0.36 points. This actually reinforces my original concern that most of the practical benefit comes from simple label sharing and selective gating, rather than pooled ERM itself. The new experiments with rare keys give evidence that pooled ERM can outperform majority voting in certain synthetic settings, but does this advantage actually hold on real datasets?
Finally, while the new TOX21 results are positive, the broader empirical picture remains mixed. On AIDS, the gains largely disappear with tuned GNNs, and the earlier graph-size and DIR comparisons remain concerning. DHFR and PROTEINS also show little consistent improvement. Overall, the practical gains still seem quite task-dependent.
Taking new information into account, I will maintain my rating of 2 (Weak Rejection). I think the theoretical contribution is definitely interesting, and the rebuttal has strengthened the evaluation in several ways. On the other hand, the real-world results still do not establish a sufficiently general or meaningful advantage over simpler alternatives. For these reasons, I believe the paper currently falls short of the ICLR acceptance bar.
Reply to Reviewer ZBx4(1/2)
Dear Reviewer ZBx4,
Thank you for the careful reading and for recognizing the theoretical contribution and the controls. Below we answer each weakness together with the related question and add new evidence; all changes are marked in blue in the revised PDF.
W1 and Q2 (the sufficiency assumption; relevance of the theory)
Thank you for these questions. Our analysis is theoretical, and we test it in two steps. First, experiments that match its assumptions check its predictions. Exact-risk simulations follow the predicted dependence on noise, complexity and discarded information, and with supplied keys that are sufficient by construction, pooled ERM improves GNNs significantly in all 94 controlled settings (Table 1, Appendix E). Second, on real graphs the keys are mined, and Theorem 3.1 still applies, because it holds for every key map and charges 3√(κ/2) for the information the key discards. New Section 5.4 measures this information and shows how it governs the real-data results.
W2 (the real-data results)
Thank you for this detailed breakdown.