acceptodds
Under review as a conference paper at ICLR 2027

Label Sharing through Sufficient Graph Explanations

Abstract

Predictive substructures such as functional groups recur across graphs with different backgrounds, so graphs sharing an explanation could share labels. Existing guarantees require such graphs to carry nearly the same label. We show that label sharing needs only sufficiency, meaning that the rest of the graph adds no label information once the explanation is known. Our learner, pooled ERM, gives each training graph the label frequency of its explanation class, fits the resulting weighted majority targets, and averages fitted predictions within observed classes. Since pooling reuses the fitting sample, the proof separates within-class representatives from class counts. Let be the VC dimension of a binary class across the classes of an explanation map . If , the learner returns with probability a deterministic classifier within of the best risk in from labels, even when the ordinary VC dimension is infinite. At label noise within classes is unrestricted, and the dependence cannot be improved in general. Risk-dependent rates refine this bound, and a rate of order holds under exact sufficiency, Bayes realizability, and a positive margin. With supplied explanations, GNNs trained by pooled ERM improve significantly in every controlled setting, with large gains under label noise. With mined keys on real graphs, pooling only within gated keys raises accuracy significantly on TOX21 and AIDS under a strict label budget and never lowers it significantly.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph classification, explanation-assisted learning, sample complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_ZBx4OpenReview ↗
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 κ\kappa 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 3κ/2+ϵ3\sqrt{\kappa/2} + \epsilon from O((d+log⁡(1/δ))/ε2)O((d + \log(1/δ))/ε²) labels, where dd 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
  1. 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 κ=0\kappa = 0. This is interesting and somewhat useful.
  2. The experiments are broad and include sensible controls, such as permuted descriptors, graph-size control, tuned GNNs, GSAT/DIR comparisons.
  3. 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
  1. 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.

  2. 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
  1. 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?

  2. 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
AuthorsOpenReview ↗

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.

  • Where we share labels, the keys are close to sufficient. On real graphs we deploy majority sharing inside gated groups, whose guarantee (Proposition 3.3) charges only for information discarded inside the selected groups. There κ̂ is at most 0.08 nats per gated graph, so a calibrated network cannot beat the key in those groups.
  • The same term explains the cases you highlight. Pooled ERM is constant on observed keys, so on coarse keys it converges to the key alone, and across the 64 settings of Table 24 it is at most 1.43 points from the key's accuracy. Whether pooling every key helps is therefore decided by whether the key is more accurate than a GNN trained on the same labels.
  • On test labels, this key-versus-GNN comparison gives the sign of the full-pooling effect in all 64 settings.

W2 (the real-data results)

Thank you for this detailed breakdown.

  • The deployed hybrid shares labels only within gated groups, the regime explained under W1. Under a strict label budget it never lowers accuracy significantly in any of the 32 cells of Table 2, and selective pooled ERM never lowers it significantly in any of the 64 settings of Table 3.
  • Over tuned networks the hybrid never lowers accuracy significantly on any of the four tasks (Table 5). On AIDS the tuned networks already reach 94–99% and leave few errors to share, while on TOX21 the hybrid keeps significant gains of 1.3–4.6 points.
  • On TOX21 the gains also hold over size controls (Table 12), remain significant over a GPS graph transformer at B ≤ 200 (Appendix F.7), and hold on the original imbalanced data.
AuthorsOpenReview ↗

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.

Reviewer_ZBx4OpenReview ↗

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.

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

The paper studies when a label can be shared between graphs that share an explanation, even when their labels disagree. It claims that this requires only sufficiency: the rest of the graph adds no label information once the explanation is known. It proposes pooled ERM, which works in three steps: (1) each training graph gets its explanation class's label frequency as a soft target, (2) the model is fit by weighted ERM on these group-majority targets, (3) predictions are averaged within each observed class. The main theorem gives a sample complexity of O((d+log(1/delta))/(epsilon)^2), where d is the across-class VC dimension, removing the log d factors of prior work. Experiments include synthetic graphs and real-world molecular datasets.

Critical strengths
  • Strong theoretical contribution: relaxing near-deterministic labels to sufficiency is natural, and the bound is tight in d and epsilon.
  • Simple and effective method: it reduces to weighted ERM and is very robust to label noise when the explanations are sufficient.
  • Extensive evaluation: the authors use paired significance tests and multiple runs per method to report mean and standard deviations.
Critical weaknesses
  • Theory vs practice gap: The theory assumes sufficient explanations, however the real data keys are mined patterns that may not be sufficient. Could this discussion be given more importance?
  • Presentation: The paper is very dense and hard to follow and understand. There are many key parts in the appendix that can be brought to the main paper to make the main paper more readable, some examples:
    • the gating rule mentioned in the contributions could be detailed more.
    • tuned GNN results can be brought to the main text. Could the authors explain why only one of the tuned experiments is in the main paper?
  • Dated baselines: The backbones (GCN, GIN, GraphSAGE, PNA) and explanation baselines (GSAT, DIR) are relatively old. Recent graph architectures (e.g., graph transformers), noise-robust training methods are not compared. Could the authors add more baselines?
  • Reproducibility: The paper has extensive experiments and it claims that code is included but the anonymized link to the code is not provided. Could the author provide anonymized link so that reproducibility of the experiments can be done?
Questions for authors

Please check weaknesses section.

3 comments
AuthorsOpenReview ↗

Reply to Reviewer aGsn

Dear Reviewer aGsn,

Thank you for the positive assessment of the theory, for noting the paired tests and repeated runs, and for the concrete suggestions. We acted on each of them; all changes are marked in blue in the revised PDF.

W1 (theory versus practice)

Thank you for this suggestion. Our analysis is theoretical, and we test it in two steps. First, experiments that match the assumptions of the theory check its predictions. Exact-risk simulations (Section 5.1) follow the predicted dependence on noise, complexity and discarded information, and on graphs whose supplied keys are sufficient by construction, pooled ERM improves GNNs significantly in all 94 controlled settings (Table 1, Appendix E). Second, to see how the method behaves in real-world settings, where keys are mined and need not be sufficient, we use real molecular and protein graphs under a strict label budget (Tables 2 and 3). New Section 5.4 now discusses the gap between the two in the main text. Theorem 3.1 holds for every key map and charges 3√(κ/2) for the information the key discards, and we now measure how much the mined keys discard.

  • Pooled ERM is constant on observed keys and stays within 1.43 points of the key alone in all 64 strict-budget settings.
  • Inside the gated groups, the held-out estimate κ̂ of the discarded information is at most 0.08 nats per graph, so a calibrated network cannot beat the key there (Section 5.4).
  • The conclusion now contrasts the assumptions of the guarantees, ERM and nearly sufficient keys, with the graph experiments, which use trained networks, mined keys, and a gate that compares key and network on held-out labels.

W2 (presentation; the gating rule; tuned results)

Thank you for these concrete suggestions. Section 4 now states the gate. A group is eligible if it has at least three labels, a unique majority, and smoothed purity (max_c n_tc + 1)/(n_t + 2) at least the reference, which is the GNN's validation accuracy (its balanced accuracy under class imbalance). Tuned-GNN results now appear for all four tasks in the main text (Table 5). For space, the submission showed only TOX21 there, with all four tasks in Appendix D.6. At 50 graphs per class, the hybrid keeps significant gains of 1.3–4.6 points over tuned networks on TOX21.

W3 (baselines)

Thank you for this suggestion. We added experiments for both families you mention, and label sharing keeps significant gains against each.

  • Noise-robust training (Appendix F.4). We ran generalized and symmetric cross-entropy and co-teaching (given the true noise rate) on all 40 noisy supplied-key settings, with identical networks, seeds, labels and checkpoint rule. Pooled ERM beats each of them in all 40 settings, by 5–48 points, because it uses explanation classes as side information that these objectives lack. None of them improves significantly on cross-entropy, and each lowers accuracy significantly in 6–15 settings.
  • Graph transformer (Appendix F.7). We ran a GPS backbone (three GPSConv layers with a GIN local layer, four attention heads, 16-step random-walk encodings) through the paper's own job and scoring code. Under 20% noise on FOUR-MOTIF, pooled ERM improves GPS by 7.6–28.7 points at every budget, all significant, and beats voting at every budget, significantly at four of five. On TOX21 the deployed hybrid gains significantly at B = 100 and 200 (+1.5, +1.1) and is never negative. GPS is a strong base network here, reaching 92–98.5% on AIDS and 64–73% on TOX21.
  • We prioritized these two families because they test whether a stronger network or a noise-robust objective removes the need for label sharing. The comparison with GSAT and DIR remains in Appendix D.8.

W4 (code)

Thank you for asking for this. The code is now in the supplementary material, and the Reproducibility Statement of the revision points to it. It covers data construction, key mining and gating, network training with pooled ERM, the strict-budget protocol, statistics, and the exact-risk numerical studies, and its README maps each experiment to the tables it produces.

Thank you again for the constructive review; we would be glad to clarify anything further.

Reviewer_aGsnOpenReview ↗

Score Increase to 3

Dear Authors,

Thank you so much for addressing the concerns and weaknesses seriously, and for providing more results. Most of my concerns and questions are addressed, and I'm increasing my score to 3.

AuthorsOpenReview ↗

Reply to Reviewer aGsn

Dear Reviewer aGsn,

Thank you for carefully reading our response and the new results, and for raising your score. Your suggestions have clearly improved the paper. The main text now discusses the gap between sufficient and mined keys (Section 5.4), states the gating rule (Section 4), and reports tuned-network results for all four tasks (Table 5), and the appendix adds comparisons with noise-robust objectives and a graph transformer (Appendices F.4 and F.7).

Your first point, on the gap between theory and practice, also led to one further experiment (Appendix F.8, Table 35). It tests pooled ERM under label noise on real molecules, with keys from domain knowledge rather than keys sufficient by construction. With the ten toxicophore descriptors of MUTAGENICITY as keys and 20% label noise, pooled ERM is more accurate than the GNN trained on the same labels in 23 of the 24 settings with at most 100 graphs per class, by 3.7 points on average.

If any concern remains open, we would be glad to address it in the remaining days of the discussion period.

Thank you again for your time and constructive feedback.

Reviewer_av6ZOpenReview ↗
Rating
2(+1)
Confidence
3(+2)
Informativeness
2(+1)
Presentation
2(+1)
Soundness
2(+1)
Read review
Paper summary

This paper studies label sharing across graphs with different class labels under the assumption that commonly shared explanations can have different labels. The authors claim that deterministic label consistency should be relaxed.

Critical strengths

The paper provides a theoretical analysis to support its claims.

Critical weaknesses
  • The overall representation is generally poor. Especially, the abstract is overly technical, with mathematical notations.
  • The motivation for label-sharing is not convincing, and the support for the claims is weak.
  • The authors argue that existing methods have assumptions that sharing explanations generally shares the same labels, while the claims are not supported with experiments.
Questions for authors
  1. Could the authors explain how existing graph explanation methods, such as GNNExplainer, restrict label sharing issues? And what issues arise in the specific scenario in real-world settings?
  2. Could the authors provide experimental evidence that relaxing the deterministic label-sharing assumption can eventually improve the explanation quality? Compare with the current explanation methods for graphs, including GNNExplainer, PGExplainer, and RG-EXplainer.
4 comments
AuthorsOpenReview ↗

Reply to Reviewer av6Z(1/2)

Dear Reviewer av6Z,

Thank you for your review and for the direct questions. We address each point below; all changes are marked in blue in the revised PDF.

W1 (presentation; the abstract)

Thank you for this comment. We rewrote the sentences of the abstract that used notation in words, and its other sentences are unchanged. In plain terms, the paper asks how many labels are needed to train a graph classifier when explanations, such as toxicophores in molecules, recur across graphs but do not fix their labels. Earlier guarantees for sharing labels between graphs with the same explanation require these graphs to have (nearly) the same label. We propose pooled ERM, which trains each graph toward the label frequency of the training graphs sharing its explanation rather than toward its own label. We prove that it comes close to the best classifier from few labels whenever the explanation is sufficient, that is, the rest of the graph adds no label information, even if labels within an explanation disagree. We then test it with GNNs on synthetic and real graphs. The revision also states the gating rule explicitly in Section 4, adds Section 5.4 on when pooling helps, and moves the tuned-network results for all four tasks into the main text (Table 5).

W2 (motivation for label sharing)

Thank you for raising this. Our motivation is whether explanations can improve learning. Explanations of graph labels, such as predictive substructures, often recur across many graphs. When graphs share an explanation, the label of one graph carries information about the others, so a classifier could be learned from fewer labels. Molecules are an example. Their labels come from laboratory measurements, such as the Ames tests behind mutagenicity data, while the substructures that drive them, such as toxicophores, recur across many molecules. A toxicophore, however, raises the probability that a molecule is mutagenic without fixing its label. The paper supports its claims at three levels.

  • Theory. Pooled ERM competes with the best classifier of the original class from a number of labels set by an across-class VC dimension, for any label noise within explanation classes, and this dependence is optimal (Theorem 3.1).
  • Controlled graphs. With supplied explanations, pooled ERM improves GNNs significantly in all 94 controlled settings, by up to 43 points under 20% label noise (Table 1, Appendix E), and it beats noise-robust training objectives in all 40 noisy settings (Appendix F.4).
  • Real graphs. Under a strict label budget, the hybrid, which shares labels only within gated groups, improves mean accuracy in 31 of 32 cells, significantly in 17, and lowers it significantly in none (Table 2). On TOX21 the gains also hold over tuned networks and on the original imbalanced data (Tables 4 and 5).

W3 (evidence that labels disagree within explanations)

Thank you for raising this point; the revision now measures this disagreement (Appendix F.1, Table 27). Earlier label-reuse theory assumes that the explanation (nearly) determines the label. Shao et al. (2022) assume deterministic labels on each orbit, and Zheng et al. (2024) require two graphs with the same explanation to disagree in label with probability at most ε/32. On MUTAGENICITY, two molecules with the same set of ten toxicophore descriptors have different labels with probability 0.37 (0.49 for two random molecules), and 98% of molecules lie in descriptor sets that contain both labels. For the keys we mine on four other datasets the rate is 0.21 to 0.46. The ε/32 condition would therefore need ε > 1, so it cannot hold for any useful accuracy target. In a controlled example (Figure 1), copying a group member's label, as those learners do, leaves up to 15% excess risk under within-class noise, and even the group majority leaves about 6%, while pooled ERM converges to the best classifier.

AuthorsOpenReview ↗

Reply to Reviewer av6Z(2/2)

Q1 (GNNExplainer and related methods; issues in real-world settings)

Thank you for this question. GNNExplainer, PGExplainer and RG-Explainer explain a trained model's predictions rather than decide which graphs share labels, so the restriction we discuss comes from label-reuse guarantees, not from these explainers. In our framework their outputs are possible keys that group graphs, and what matters for sharing labels across a key is its sufficiency for the label, I(Y;G|T(G)), rather than its fidelity to a model. Two issues arise on real data. First, labels within a key disagree (W3), so a learner that copies the label of a training graph with the same key inherits label noise, whereas pooled ERM trains toward the label frequency of the key. Second, a coarse key discards information, so pooling every key helps while labels are scarce (Section 5.4). The revision estimates on held-out labels how much information a key discards (Section 5.4, Appendix F.2).

Q2 (explanation quality; comparison with explainers)

Thank you for this suggestion. Our goal is to reduce the number of labels needed to train a classifier, using explanations as given, rather than to improve explanation quality, so the paper evaluates classification accuracy under label budgets and noise. The related work now notes that the outputs of explainers can serve as keys that group graphs. The closest comparison with explanation-based learners is Appendix D.8, which compares classification accuracy with GSAT and DIR. The hybrid is ahead of both on TOX21 from five graphs per class on. Because our method does not produce explanations, we did not compare explanation quality with GNNExplainer, PGExplainer or RG-Explainer; as noted under Q1, their outputs could instead serve as keys for pooled ERM.

Thank you again; we hope the notation-free abstract and the new measurements make the question and its motivation clearer.

Reviewer_av6ZOpenReview ↗

Reply

I thank the authors for addressing my previous concerns and helping me better understand the proposed method. Most of my concerns were addressed well. Despite the solid theoretical contribution on label sharing, I still find it difficult to assess the practical value of the proposed framework in real-world settings, especially after considering the authors’ responses to the other reviewers. More recent interpretable GNN methods have reported competitive or improved classification performance relative to GSAT and DIR on certain benchmarks. This raises the question of whether the proposed framework offers practical benefits beyond its theoretical contributions. Since the rebuttal resolved several of my concerns, I will raise my score to 2.

AuthorsOpenReview ↗

Follow-up reply to Reviewer av6Z

Dear Reviewer av6Z,

Thank you very much for the follow-up and for raising your score. We are glad that you find the theoretical contribution solid and that most of your concerns have been addressed. We understand that the remaining question is whether the framework has practical value, given that recent interpretable GNNs improve on GSAT and DIR. We would like to share our view on this point, in some detail.

1. We see interpretable GNNs as complementary to our framework.

They address a different question, namely which substructure explains a prediction, whereas ours is how many labels a classifier needs when explanations recur and labels are noisy. The two can be combined. The hybrid is applied to the frozen predictions of a trained network. It needs no retraining and, under the strict budget of Table 2, reads no label beyond those the network already uses. Pooled ERM changes only the training targets of a given backbone. A recent interpretable GNN could therefore serve as the base network, and its explanations as the keys, so progress on interpretable GNNs would also benefit our method.

2. The gain remains with stronger networks.

By Proposition 3.3, the gain is the error the network makes in the selected groups beyond what the explanation alone achieves there, less a small estimation cost, and the gate keeps the network everywhere else. This is consistent with what we observe. On TOX21 the hybrid keeps significant gains of 1.3 to 4.6 points over networks tuned on validation labels (Table 5), and it improves a GPS graph transformer significantly at budgets of 100 and 200 labels without lowering its accuracy at any budget (Appendix F.7). Under the strict budget on four real benchmarks, it improves mean accuracy in 31 of 32 settings, significantly in 17, and never lowers it significantly (Table 2).

3. With few labels, the comparison with GSAT and DIR looks different.

Accuracies of interpretable GNNs are usually reported with all training labels. In our matched comparison on four real tasks with our reimplementations (Appendix D.8, Table 20), GSAT exceeds the mean accuracy of the plain GNN in 26 of 64 settings and DIR in 22. The hybrid is at or above the plain GNN in 62, above GSAT in 51 and above DIR in 46. On TOX21 it is ahead of both at every budget from five graphs per class, by 0.6 to 6.1 points. We therefore think that an improvement over GSAT and DIR with full labels may not carry over to the label-scarce setting, where our gains are measured against plain and tuned GNNs and GPS.

4. The setting arises in practice.

Labels of molecules come from laboratory assays, which are costly and noisy. On real molecules with their toxicophore descriptors as explanations and 20% label noise, pooled ERM is more accurate than the GNN trained on the same labels in 23 of 24 settings with at most 100 graphs per class, by 3.7 points on average and up to 7.6 (Appendix F.8). On the original imbalanced Tox21 collection, the hybrid raises balanced accuracy in all 20 settings, significantly in 13 (Table 4).

We report every unfavorable setting, in the paper and throughout this discussion, and we hope this is not read as an absence of practical value. The paper's main contribution is the theory, and we hope the results above show that it carries over to real graphs where labels are scarce or noisy.

If you have a particular method or benchmark in mind, we would be grateful if you could share it, and we would be happy to clarify how it relates to our framework. We would also welcome any other concern that remains open for you.

Thank you again for your time and thoughtful engagement.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response(1/2)

We thank the three reviewers for their careful reviews and concrete suggestions. We are glad that Reviewer aGsn sees the move from near-identical labels to sufficiency as a strong theoretical contribution, and that Reviewer ZBx4 finds it interesting and values the controls. The reviewers asked for a clearer presentation, a closer link between the theory and the mined keys (aGsn, ZBx4), stronger baselines and evidence (all three), and code (aGsn). We uploaded a revised PDF, with changes in blue. The theorems, the learner and the gate are unchanged. In brief, the revision makes three points.

  • The main contribution is the learning guarantee. Experiments that match its assumptions test its predictions, and real graphs with mined keys show how it applies in practice.
  • On real graphs, majority sharing inside gated groups (Section 4, Proposition 3.3) never lowers accuracy significantly under a strict label budget (Table 2) or against tuned networks (Table 5). Its TOX21 gains under scarce labels remain significant against tuned networks and on the original imbalanced data. Pooled ERM goes beyond voting under label noise and with rare or unseen explanation classes.
  • A new held-out estimate, κ̂, quantifies how much information a mined key discards (Section 5.4, Appendix F.2).

1. Labels within explanations disagree (av6Z). On MUTAGENICITY, two molecules with the same set of ten toxicophore descriptors have different labels with probability 0.37 (0.49 for two random molecules), and 98% of molecules lie in descriptor sets that contain both labels. For the keys we mine on TOX21, AIDS, DHFR and PROTEINS the rate is 0.21 to 0.46. The condition of Zheng et al. (2024), disagreement at most ε/32, would require ε > 1 on every dataset (Appendix F.1, Table 27).

2. Theory and mined keys (aGsn W1, ZBx4 Q2; new Section 5.4).

  • Pooled ERM is constant on each observed key, so on coarse keys it converges to the predictor that uses the key alone, and Theorem 3.1 charges for the information the key discards. Across the 64 strict-budget settings of Table 24, pooled ERM is at most 1.43 points from the key alone (the majority training label of each key), 0.36 on average.
  • Hence pooling every key helps while the key alone beats a GNN trained on the same labels. On test labels this comparison gives the sign of the full-pooling effect in all 64 settings, which follows from the mechanism.
  • κ̂ is the held-out cross-entropy of the key's label frequencies minus that of a calibrated GNN or ensemble, a lower estimate of I(Y;G|T(G)).
  • Where the gate accepts groups (20–56% of test graphs in those runs), κ̂ is at most 0.08 nats per gated graph and 0.016 nats weighted by coverage, the form Proposition 3.3 charges, so a calibrated network cannot beat the key inside the gated groups, and selective pooling never significantly lowers accuracy.

3. The original imbalanced TOX21 (ZBx4). We reran the strict-budget protocol on the full Tox21 AhR collection, with 8,169 molecules, 11.6% active, B = 100–2000, four backbones and 30 paired runs per cell. Rebuilt from the same source, the collection reproduces the paper's balanced subset exactly.

  • Because accuracy rewards predicting the inactive class, we score balanced accuracy and run every method in its balanced-risk form, with class-weighted training, class-weighted group counts, and the network's balanced validation accuracy as the gate reference. Reweighting by the label preserves sufficiency; the weights enter only the estimation constants.
  • Against a class-weighted GNN, gated majority sharing raises balanced accuracy in all 20 settings, significantly in 13, by up to 4.2 points (pre-registered verdict "effective"), and AUPRC significantly in 14 (new Table 30).
  • Selective pooled ERM is positive in 16 of the 20 settings and never lowers balanced accuracy significantly.
  • Pooling every key helps at small budgets (+3.7 to +6.6 points for GCN and GIN at B ≤ 200).

4. Baselines (aGsn W3).

  • Noise-robust training (Appendix F.4). We ran generalized and symmetric cross-entropy and co-teaching (given the true noise rate) on all 40 noisy supplied-key settings, with the same networks, seeds, noisy labels and checkpoint rule as cross-entropy training. Pooled ERM beats each of them in all 40 settings, by 5–48 points, because it uses explanation classes, which these objectives lack. None of them improves significantly on cross-entropy, and they lower accuracy significantly in 15, 6 and 10 settings.
  • Graph transformer (Appendix F.7). We ran a GPS backbone (GPSConv with a GIN local layer, random-walk encodings) through the same job and scoring code. On FOUR-MOTIF with 20% noise, pooled ERM improves GPS by 7.6–28.7 points at every budget, all significant. On TOX21 the deployed hybrid gains significantly at B = 100 and 200 (+1.5, +1.1) and never loses. GPS is a strong base network here, reaching 92–98.5% on AIDS and 64–73% on TOX21.
AuthorsOpenReview ↗

General response(2/2)

5. Beyond voting (ZBx4 Q1; Appendix F.5). We regenerated the explanation-class family with 10, 20 and 40 motif types (up to 821 possible keys, many of them rare), under 20% label noise.

  • Pooled ERM beats the GNN in all 42 settings (99.0–99.9% with the full pool, against 81–91%). It is ahead of ungated voting in 35, significantly in 10, and never significantly behind.
  • With the full pool its lead over voting 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 falls back to 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.

6. Presentation (all). The abstract no longer uses notation. Section 4 states the gate, namely at least three labels, a unique majority, and smoothed purity at least the network's validation accuracy. Tuned-GNN results for all four tasks are in the main text (Table 5).

7. Code (aGsn W4). The supplementary material now includes the code for the graph pipeline (data construction, pattern mining, selection and gating, network training, the strict-budget protocol, scoring and statistics) and the numerical studies.

We thank the reviewers again and would be glad to discuss any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.