- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper proposes SimGraph for imbalanced graph classification. The framework combines Balanced Pairwise Graph Similarity (BPGS) learning and Size-Adaptive Instance Normalization (SAIN). BPGS treats graph similarity estimation as a pairwise binary classification problem, using asymmetric scaling and a learnable decision boundary. SAIN aims to reduce the effect of graph size on graph representations. The authors conduct extensive experiments on multiple datasets and compare their method against several baselines. The results show that SimGraph achieves state-of-the-art performance.
Critical strengths
The experiments are comprehensive, covering multiple datasets, including large-scale datasets, and different models. The authors also provide the source code, which is helpful for reproducibility.
Critical weaknesses
-
The motivation and justification for the proposed method are not sufficiently clear. The paper identifies size-induced similarity bias as a key problem, but I did not find convincing empirical evidence that directly demonstrates this bias. Figure 1 only provides an illustration, rather than evidence from real datasets. Moreover, most of the proposed components seem incremental, with relatively minor modifications to existing techniques. The paper does not clearly explain how these design choices specifically help reduce size-induced similarity bias. For example, the BPGS loss is essentially a standard BCE loss with an additional scaling factor, while the memory bank is already a common technique in contrastive learning. For SAIN, I am not convinced that the proposed operation makes graph embeddings size-invariant. Since the affine transformation uses graph size information, could it instead introduce more size information into the embeddings? Although the ablation studies show the contributions of different components to the final performance, they do not directly demonstrate how individual design choices in these components reduce similarity bias. I would like to see stronger empirical or theoretical justification for these design choices.
-
The paper is difficult to follow, and the presentation needs improvement. The font size in some tables is too small to read comfortably. Similarly, the figure captions are very small, and the spacing between the figures and their captions is too narrow. These formatting choices appear to violate the conference's formatting requirements. In addition, the method section is somewhat lengthy and tedious to follow. I suggest shortening this section to make room for larger and more readable figures and tables.
Questions for authors
-
Can the authors provide empirical evidence demonstrating the existence of size-induced similarity bias on real datasets? Figure 1 is only an illustration, and it would be helpful to see whether graph size actually affects pairwise similarity in the way described in the paper.
-
How does the asymmetric scaling factor in BPGS specifically address size-induced similarity bias? What makes this design more suitable than the standard BCE loss? Have you tried to replace the BPGS loss with standard BCE loss?
-
Since memory banks are commonly used in contrastive learning, what is their specific role in addressing size-induced similarity bias in this framework?
-
Why does SAIN produce size-invariant graph embeddings when the affine transformation explicitly depends on graph size? Could this operation instead introduce additional size information into the representations?
-
Can the authors provide more direct empirical or theoretical evidence showing that individual design choices in the proposed components actually reduce similarity bias, beyond the performance improvements reported in the ablation studies?
-
Can the authors evaluate SimGraph with smaller labeled training sets, such as 5%, 3%, and 1%, and compare its performance against existing semi-supervised learning methods under these settings?
3 comments
Thank you for the detailed response and additional experimental results. While these clarifications are helpful, I still have concerns about whether the proposed components directly mitigate size-induced similarity bias, particularly the specific contributions of asymmetric scaling in BPGS and size-adaptive normalization in SAIN.
Furthermore, the manuscript has not yet been revised to incorporate the additional evidence and clarifications provided in the rebuttal.
Therefore, I will retain my original rating.
Dear Reviewer ktMM,
Thank you for identifying the two remaining issues: the connection between our components and size-induced similarity bias, and the absence of these clarifications from the manuscript. We agree that classification improvements alone do not establish debiasing. We have now revised the manuscript, with changes highlighted in blue, to distinguish the observed bias, the optimization rationale, and the supporting empirical evidence.
1. The evidence is now in the main text. Table 1 in Section 1 (p. 2) reports held-out pairwise measurements, rather than only an illustration. With the CE encoder, cross-size versus near-size same-class FNR is 62.36% versus 47.06% on D&D and 61.04% versus 35.45% on RDT-B. For different-class pairs, near-size versus cross-size FPR is 49.96% versus 30.87% and 49.02% versus 34.60%, respectively. These establish the two observed error modes. Section 3 now explains the component mechanisms and their limits, while Section 4.3 (pp. 9–10) includes the auxiliary-loss comparison (Table 6), SAIN boundary tests (Table 7), and smaller-label results (Table 8). We also shortened the theoretical discussion and enlarged the large-scale result tables.
2. Asymmetric scaling: its exact role, rather than a size-specific guarantee. Given identical scores, pair masks, and balance weights, setting exactly recovers balanced pairwise BCE. For , the weighted score gradients are
g_-(z)=(1-\alpha)r\sigma(rz).$$ For $r>1$, a different-class pair with $z\ge0$ receives stronger repulsion than under $r=1$; this includes near-size false positives. The positive gradient is bounded by $\alpha/r$, and the positive/negative curvatures at $z=0$ are $\alpha/(4r^2)$ and $(1-\alpha)r^2/4$. Thus, scaling provides smoother positive attraction and sharper negative separation near the boundary. However, **$r$ does not itself identify size-confounded pairs**, and these score-level properties do not guarantee reduced overfitting or size independence. Cross-size constraints come from labeled pair coverage, expanded by the memory bank. Table 6 supports the combined pairwise design: without SAIN, CE+BPGS exceeds SupCon by 3.79–7.41 percentage points and ProGCL by 2.11–6.62 points across four datasets. We explicitly distinguish this comparison from an isolated test of $r$. The existing $r$-sensitivity figure measures class recall, not size-stratified pair errors; it supports the optimization trade-off but is not presented as direct evidence that $r$ alone removes size bias. **3. SAIN: size-conditioned calibration, not unconditional size erasure.** Section 3.2 now uses **“size-modulated”** rather than “size-invariant.” Normalization standardizes per-embedding moments; the affine transform can retain size information. BPGS supplies cross-size pair constraints on that transform, but cannot guarantee that all size shortcuts disappear. We therefore report complementary diagnostics. On RDT-B Low, norm–size correlation decreases from +0.777 to +0.186; on RDT-B High, it decreases only from +0.899 to +0.751 (Appendix I.1, Table 35). In a separate High-imbalance visualization, norms compress from roughly 0–100 to 10.9–11.6 and directional class separation improves (Appendix I.3, Figure 7). Table 7 also reports BACC gains of 8.57 points on IMDB-B and 13.66 points on RDT-B under size-biased class selection, alongside the negative results under size-OOD splits. These support useful calibration in the evaluated settings, not universal invariance. Accordingly, we recommend validation-based selection and caution when size is label-defining. We appreciate the distinction you raised between a plausible mechanism and evidence that isolates its effect. The revision now makes that distinction explicit and places the relevant results in the manuscript for direct inspection.
We thank Reviewer KtMM for the constructive suggestions regarding empirical motivation, component justification, ultra-low-label benchmarks, and presentation.
W1 & Q1: Empirical Evidence of Size-Induced Bias
Evaluating held-out pairs stratified by class pairs, standard CE exhibits lower similarity and higher FNR on cross-size vs. near-size same-class pairs (62.36% vs. 47.06% on D&D; 61.04% vs. 35.45% on RDT-B), and higher FPR on near-size vs. cross-size different-class pairs (49.96% vs. 30.87% on D&D; 49.02% vs. 34.60% on RDT-B). We will integrate these real-dataset statistics into Figure 1.
W1 & Q2: Asymmetric Scaling Factor vs. Standard BCE
Setting r=1 in BPGS exactly recovers balanced pairwise BCE. Setting r=1 asymmetrically bounds positive (1/r) and negative (r) gradients, preventing overfitting on scarce positives while sharpening hard-negative separation (Figure 10). Under aligned tuning budgets (Table 26), CE + BPGS (w/o SAIN) outperforms CE by +9.0–12.7 pp and SupCon/ProGCL by +4.4–7.4 pp across four datasets.
W1 & Q3: Specific Role of the Memory Bank
Under sparse labels, mini-batches rarely cover diverse cross-size positive pairs for minority classes. Using an identical EMA encoder, our memory bank expands distinct cross-size (Δlogn≥log2) positive pairs per epoch from 788.8 to 1,969.1 (D&D) and from 1,746.8 to 6,703.8 (RDT-B), improving BACC from 64.88% (in-batch) to 65.43% (D&D) and from 70.31% to 73.52% (RDT-B).
W1 & Q4: SAIN and Size Information
We agree that conditioning γ(n),β(n) on size performs adaptive size modulation rather than unconditional size erasure: InstanceNorm removes uncontrolled size-coupled moment shifts, while the affine transform retains task-predictive cues (Appendix I.1, Table 32). Boundary tests (Table 36) confirm that SAIN prevents size-shortcut overfitting under
size_sep(+8.57 pp on IMDB-B, +13.66 pp on RDT-B) while preserving predictive signals undersize_mix(+4.09 pp on D&D). We will revise "size-invariant" to "size-modulated" in the main text.W1 & Q5: Direct Component-Level Evidence
Beyond ablation accuracy, our held-out pair FNR/FPR statistics, cross-size bank pair counts, norm–size correlation drops (Table 32), three-panel angular/radial decompositions (Figures 6–8), and subgroup improvements (lifting RDT-B worst-cell accuracy from 48.13% to 52.36%) directly demonstrate how each module mitigates size-induced bias.
Q6: Evaluation with 5%, 3%, and 1% Labeled Training Sets
We evaluated SimGraph on D&D across 10% (118 graphs), 5% (59), 3% (35), and 1% (12) labeled budgets (10 seeds per split), comparing against CE, SupCon, and a semi-supervised Mean Teacher (MT) GNN consistency baseline (Test BACC %):
SimGraph consistently achieves the best performance across all ultra-low label budgets, outperforming CE by +1.58 / +0.62 / +1.13 pp, SupCon by +1.64 / +0.07 / +1.33 pp, and Mean Teacher by +1.90 / +3.48 / +1.10 pp on average at 5% / 3% / 1%, respectively.
W2: Readability and Formatting
We will streamline Section 3 to make it concise, enlarge font sizes across all tables and figure captions, adjust spacing to strictly adhere to formatting guidelines, and fix all citation/typographical errors.