acceptodds
Desk rejected at ICLR 2027

RAISE: Relational Inference for Label-Efficient Subgraph Classification

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

In biological and social networks, label-efficient subgraph classification predicts labels for designated subgraphs in a shared background graph from a small labeled training subset. In this setting, predictions depend on which labeled subgraphs are informative for a query. Structural similarity alone does not fully capture source–query relations: structurally similar queries can contain different vertices and relate differently to the same labeled source. These relations may help classify queries with no same-class labeled examples among their closest structural matches. We introduce RAISE (Relation-Aligned Inference from Sparse Examples), which encodes aligned membership and diffusion responses on common background-vertex coordinates in a fixed, label-free relational kernel. Kernel ridge regression learns class-specific source coefficients, while class-wise diffusion aggregation supplies complementary evidence. One round of self-training adds high-confidence pseudo-labeled training subgraphs, followed by a dependence-aware refit using the same kernel. Across four benchmarks at 2–20% label budgets, RAISE improves average micro- and macro-F1 over PADEL by 4.71 and 6.74 percentage points, respectively, and achieves the highest aggregate cross-subset agreement. Controlled studies suggest that these relations add predictive information beyond the evaluated structural representations. Code is available [here](https://anonymous.4open.science/r/iclr2027-RAISE-code-4548).

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Subgraph classification, Label-efficient learning, Relational inference, Graph kernels, Semi-supervised learning, Self-training

Reviews

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

The paper studies label-efficient classification of designated subgraph sets in a shared background graph. The authors note that two structurally similar queries may have different relations to the same labeled source. Existing subgraph representations often do not preserve this instance-relation correspondence. The authors propose RAISE. RAISE constructs a fixed, label-free relational kernel on common background vertex coordinates from membership relations and diffusion relations. Kernel ridge regression learns class-specific source coefficients. Class-wise diffusion aggregation supplies complementary evidence. One round of self-training adds high-confidence pseudo-labeled examples from the unlabeled training pool. It then performs a weighted refit on the same fixed kernel that accounts for dependence. Experiments use four benchmarks: PPI-BP, HPO-METAB, HPO-NEURO, and EM-USER. Label budgets range from two percent to twenty percent. RAISE improves average micro-F1 and macro-F1 over PADEL by 4.71 and 6.74 percentage points, respectively. It also achieves the highest cross-subset Cohen's kappa. The authors also use labeled-source exchange, relation reassignment, synthetic relation-strength experiments, and missing-member experiments. These support the claim that relation correspondence is predictive.

Critical strengths
  1. The fixed, label-free relational kernel is separated from sparse-label inference, and the computational efficiency is notable. RAISE constructs membership and diffusion relations once into a fixed kernel, and labels enter prediction only through kernel ridge regression coefficients and class-wise aggregation. Across the 120 main-table conditions, the total time is 0.22 hours, far below PADEL’s 139.6 hours. This idea of reusing relations plus lightweight fitting has practical value for low-label subgraph classification and also makes the label-use path easier to audit.
  2. The correspondence interventions and counterexample experiments are relatively convincing. The labeled-source exchange fixes the query, the number of labels, and the class composition, and replaces only one labeled source; it shows that the relational kernel is more sensitive to sources with stronger diffusion relations to the query. Relation reassignment preserves the full kernel spectrum, rank, and scale while only shuffling instance–relation pairing, and RAISE degrades monotonically as the permutation fraction increases. Synthetic experiments further show that RAISE is advantageous when relations carry class information, whereas the structural kernel is advantageous when internal shape carries class information. These results support the core mechanism of the paper and honestly delimit its applicability.
Critical weaknesses
  1. The incremental contribution of the complete method is small. The core gains come mainly from the relational kernel and self-training. The ablations show that replacing the structural kernel with the fixed relational kernel brings about 5.68 points of micro-F1, and self-training adds about 1.85 points. Class-wise diffusion aggregation adds only about 0.35 points, and dependence-aware refitting adds only about 0.20 points, mainly from HPO-NEURO. The advantage of complete RAISE over the fixed relational kernel plus self-training is very small. The title and abstract emphasize the complete RAISE pipeline, but the ablations indicate that what really matters is the fixed relational kernel and one round of self-training. The complexity of dependence-aware refitting is disproportionate to its gain. The authors should position the contribution more clearly as a relational kernel plus lightweight sparse-label inference, rather than presenting the complete pipeline as the main innovation.
  2. The paper performs column standardization and prediction rules on the prediction set, which includes validation and test queries. Although labels are not used, the moments of test-query scores are used. All methods are claimed to share this rule, but readers may still worry that this transductive standardization favors RAISE’s kernel scores. In addition, on PPI-BP at two percent labels, RAISE’s micro-F1 is 35.47, lower than PADEL’s 37.61 and Member + 1-hop Ridge’s 38.11. The main text mainly reports the average over two to twenty percent and does not sufficiently explain the failure mode at extremely low labels. If the method claims applicability from two to twenty percent, this cell should be reported and analyzed.
Questions for authors
  1. Can the authors report a version that does not use test-query moments—for example, estimating standardization moments only on the labeled set or the unlabeled training pool, and then applying them to test data?
  2. On PPI-BP at two percent labels, RAISE is lower than PADEL and Member + 1-hop Ridge. Can the authors analyze the reason: is it overfitting of kernel ridge regression with very few sources, pseudo-label selection bias, or instability of diffusion aggregation under extremely low labels?
  3. Labeled-source exchange is performed only on PPI-BP. Can the authors reproduce the same pattern on HPO-METAB or EM-USER—that same-class sources with stronger relations raise the margin, while other-class sources with stronger relations lower it?
4 comments
AuthorsOpenReview ↗

Response to Reviewer Xu3g (1/2)

Thank you for the detailed reading.

Q1 / W2. A version without test-query moments. Yes; removing test-query moments leaves performance virtually unchanged. With every other setting frozen:

Moments estimated onMicro-F1Macro-F1κ
Prediction set Z (paper)55.4052.940.469
Unlabeled training pool U only55.3052.840.470
U only, and HPO-NEURO thresholds from U instead of the prevalence quota on Z55.3152.850.470
Labeled set L only54.2851.940.468

So RAISE does not need test-query scores for standardization: moments from the unlabeled training pool give essentially the same results. Against the paper version, the paired difference is −0.10, and per-subset differences range from −0.49 to +0.16. In the third row, no moment or decision threshold uses test-query scores. The fixed kernel remains transductive as defined in Section 3: it is built once from the graph and all designated member sets, without labels.

On whether standardization favors RAISE: applied to every method's saved test scores, the same standardization still leaves RAISE first. In the paper, column standardization applies to RAISE and the matched KRR controls of Table 2, while external baselines keep their native scores. Under the shared standardization, the best external baseline reaches 49.79 micro-F1 (PADEL) and 47.35 macro-F1 (Member + 1-hop Ridge), against 55.13 and 52.76 for RAISE.

Q2 / W2. PPI-BP at 2% labels (25 labeled sources). In this cell, the micro-F1 gap to PADEL already appears at the first KRR fit (31.45 vs 37.61), before pseudo-labels or aggregation enter. Each subsequent stage narrows the gap and raises both scores:

StageMicro-F1Macro-F1
K0-KRR (first fit)31.4528.10
+ self-training33.4629.08
+ aggregation34.9730.99
+ dependence-aware refit (RAISE)35.4731.29
PADEL37.6124.29

So neither pseudo-label selection nor aggregation causes this gap.

The initial gap stems from the decision rule, not from a weaker KRR fit. RAISE standardizes each class column before the argmax, whereas the baselines take the argmax of their native scores. Keeping every fit fixed, we swap only this step (using saved test scores for the baselines). Entries are micro / macro-F1:

MethodNative argmaxColumn-standardized
K0-KRR (first fit)37.99 / 17.8731.45 / 28.10
PADEL37.61 / 24.2929.56 / 25.53
Member + 1-hop Ridge38.11 / 17.4330.69 / 24.30

Under a matched decision rule, the first fit is level with or ahead of both baselines in micro-F1. Under a native argmax, it assigns 84.3% of test queries to the largest class, much as Ridge does. Standardization changes how predictions are distributed across classes:

MethodMicro-F1Macro-F1Predicted as largest classPredicted as two largestLowest class recall
Test set (true shares)––31.4%56.0%–
RAISE35.4731.2918.0%38.1%18.2%
PADEL37.6124.2939.4%72.3%4.4%
Member + 1-hop Ridge38.1117.4384.7%95.2%0.0%

In this skewed cell, standardization trades micro-F1 for macro-F1 by spreading predictions across smaller classes. PADEL and Ridge concentrate their predictions on the largest classes, and PADEL recalls only 4.4% and 5.5% of two smaller classes. RAISE covers every class but predicts the largest class less often than its true share.

The micro-F1 difference in this cell lies within test-query sampling variation: the paired bootstrap interval for RAISE minus PADEL is −2.14 [−6.79, 2.52]. On three new random partitions it averages −0.2 points, with a macro-F1 advantage of +7.5. At the same 2% budget, RAISE leads PADEL on the other three tasks (HPO-METAB 34.13 vs 27.49, HPO-NEURO 51.48 vs 46.78, EM-USER 59.59 vs 48.98; Tables C.2–C.4). Over all 16 task–budget cells, RAISE exceeds PADEL in 13 on micro-F1 and 15 on macro-F1. Section 5.2 now reports this cell, and Appendix J.7 gives the analysis.

AuthorsOpenReview ↗

Response to Reviewer Xu3g (2/2)

Q3. Source exchange beyond PPI-BP. Yes; the margin pattern holds on HPO-METAB and EM-USER at all four budgets. Same-class sources with stronger relations raise the true-class margin and other-class sources lower it, with larger shifts under K0 than under WL. Because few pairs meet the strict WL tolerance on these tasks, we widen it in tiers. The table below reports the tier with the most swaps, which also has the smallest contrast; Appendix J.4 lists all tiers. Entries are mean margin changes over all four budgets:

Task (tier; swaps)Same-class source: K0 / WLOther-class source: K0 / WLContrast, K0−WL [95% CI, query bootstrap]
PPI-BP (strict; 2,344)+0.979 / +0.001−0.541 / +0.002+1.52 [1.37, 1.68]
HPO-METAB (4× WL tolerance; 4,700)+0.632 / +0.253−0.234 / −0.077+0.54 [0.41, 0.68]
EM-USER (4× WL tolerance, size ratio 2; 978)+1.595 / +0.736−1.400 / −0.776+1.48 [1.08, 1.89]

The contrast is the K0−WL difference on same-class swaps minus the same difference on other-class swaps.

W1. Contribution of the late components. The complete method targets two results, both reported in the abstract and Table 1: accuracy with few labels and agreement of predictions across labeled subsets. As you note, accuracy comes mostly from the relational kernel and one self-training round, which add 5.68 and 1.85 micro-F1 on the 50 fresh subsets (Table 2b). Class-wise aggregation acts mainly on agreement. In the setting of Table 1 (four tasks, 2/5/10/20% labels, the original five labeled subsets, RAISE's hyperparameters unchanged; Appendix J.7):

SettingMicro-F1Cross-subset κ
K0-KRR + self-training (no aggregation, independent refit)54.920.414
+ class-wise aggregation55.140.469
+ dependence-aware refit (RAISE)55.400.469
SSNP (highest κ among baselines, Table 1)40.300.380

Aggregation raises κ from 0.414 to 0.469, more than half of RAISE's 0.089 lead over the most stable baseline. On the 50 fresh subsets at 5% and 10% labels, it likewise raises κ from 0.397 to 0.462, more than the 0.038 from self-training (Table 2b), and it lowers cross-subset prediction disagreement by 5.47 points for the quarter of queries least related to the labeled sources and by 3.00 for the most related quarter (Appendix J.7). Much of the agreement result therefore comes from aggregation, a gain that the small micro-F1 increment does not show. Aggregation itself is a class-wise average with one fixed weight.

The dependence-aware refit addresses a property of self-training on overlapping subgraphs: on three tasks, the pseudo-label errors of sources that share members are positively correlated beyond a permutation baseline (Table E.7). It costs little. It adds no hyperparameter, solves the same form of linear system as the first fit, and changes only the residual weighting. The 0.22 hours for all 120 main-table conditions that you note include aggregation and the refit, and a complete fit from cached relations averages 0.14 s. On the 50 fresh subsets, the refit adds 0.20 [0.13, 0.27] micro-F1 over independent weighting. The gain grows when errors are shared more strongly: under controlled error injection it rises from +0.28 to +0.80 against a diagonal treatment as the shared-error strength goes from 0 to 0.9, and it reaches +2.43 to +3.33 for pseudo-source sets with high member overlap on three tasks (Appendix J.2).

The revised Introduction now presents the evidence that instance-specific relations add predictive information beyond structural similarity before the method, and states the role of each component: the kernel records the relations once, KRR fits class-specific source contributions, aggregation stabilizes the inference, and one self-training round with the refit extends supervision. Section 4.3 now describes source deletion in one sentence, with the details in Appendix A.3.

We hope these results answer your questions and concerns, and we would be grateful if you would reconsider your score.

Dear Reviewer Xu3g,

Thank you again for your review. As the discussion period ends on November 18, we wanted to check whether our responses and the revised PDF (changes shown in blue) have addressed your questions. In brief, moments from the unlabeled training pool alone give 55.30 micro-F1, against 55.40 in the paper version (Appendix J.6); RAISE exceeds PADEL in 13 of the 16 task–budget cells on micro-F1 and in 15 on macro-F1 (Section 5.2); and class-wise aggregation raises cross-subset κ from 0.414 to 0.469, against 0.380 for SSNP (Appendix J.7).

If any point remains open, in particular on the PPI-BP 2% cell or the role of the late components, we would be glad to clarify it before the deadline.

Best regards,
The Authors

Dear Reviewer Xu3g,

Thank you again for your review. With the discussion period closing at the end of November 18 (AoE), we wanted to follow up once more in case our earlier message was missed. We would be glad to hear whether our responses address your questions, in particular the check without test-query moments (Appendix J.6) and the PPI-BP 2% analysis (Appendix J.7), and to clarify anything that remains.

Best regards,
The Authors

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

This paper proposes RAISE, a framework for label-efficient subgraph classification that exploits instance-specific relations beyond structural similarity. RAISE constructs a fixed, label-free relational kernel by combining membership correspondence and graph diffusion responses, and performs class-specific inference through kernel ridge regression and class-wise diffusion aggregation. It further incorporates one round of self-training with dependence-aware refitting to leverage unlabeled subgraphs. Experiments on four benchmarks under little label budgets demonstrate improvements in classification performance and prediction consistency over existing baselines.

Critical strengths
  1. The paper addresses label-efficient subgraph classification and highlights the limitations of structural similarity in capturing instance-specific relations, presenting a clear and meaningful research position.

  2. The proposed framework combines membership correspondence and graph diffusion relations into a fixed relational kernel, offering an alternative perspective to conventional subgraph representation learning.

  3. The paper conducts source-exchange, relation-reassignment, and synthetic experiments to further validate the predictive value of instance-specific relational information.

Critical weaknesses
  1. Although the motivation for exploiting shared vertex membership is intuitively reasonable, the paper does not sufficiently explain why such correspondence should provide class-discriminative information. While the experiments demonstrate the predictive value of instance-specific relations, the specific relationship between membership overlap and label agreement is not explicitly analyzed. Additional theoretical insights or direct empirical evidence from real-world datasets would strengthen this motivation and clarify the conditions under which membership correspondence is informative for classification.

  2. Both components incorporate neighborhood information and may encode overlapping relational patterns. I notice the ablation studies demonstrate the effectiveness of the combined kernel, but they do not adequately establish the complementarity of the two components or justify their equal-weight fusion in Equation (2). A more principled explanation or targeted analysis is needed to support this central design choice.

  3. The proposed method models pseudo-label error dependencies through the product of membership and pseudo-target similarities. While the positive definiteness analysis and empirical results provide some support for this design, they do not fully explain why this specific multiplicative formulation appropriately captures the underlying error dependencies. A more direct theoretical justification, ideally establishing the relationship between the proposed covariance structure and pseudo-label error correlations under reasonable assumptions, would further strengthen the methodological foundation.

Questions for authors

See Weaknesses.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 1tt9 (1/2)

Thank you for the careful review.

W1. Why shared membership is class-discriminative. On all four tasks, label agreement rises with membership overlap and, at comparable WL similarity, with diffusion relation.

Direct evidence on the real tasks (training subgraphs and training labels only; agreement is class equality, or Jaccard similarity on multilabel HPO-NEURO):

  • Pairs sharing no member agree in label at or below the base rate (PPI-BP 19.7% vs 20.0%, HPO-METAB 14.7% vs 16.7%, HPO-NEURO 11.6% vs 14.0%, EM-USER 44.3% vs 49.8%). Agreement rises with overlap. Highest-overlap decile among pairs sharing at least one member, vs base rate: PPI-BP 0.543/0.200, HPO-METAB 0.322/0.167, HPO-NEURO 0.262/0.140, EM-USER 0.622/0.498.
  • Within WL-similarity strata, stronger diffusion relations accompany higher agreement in 10/10 strata on PPI-BP, HPO-METAB, and HPO-NEURO, and 9/10 on EM-USER.
  • Under sparse supervision, the relevant reference is the most related labeled source. Mean label agreement with that source is 2.0× the base rate on PPI-BP (0.400 vs 0.202), 2.7× on HPO-METAB (0.444/0.167), 2.3× on HPO-NEURO (0.353/0.156), and 1.25× on EM-USER (0.626/0.501).

When this holds. The mean of the two within-class expected overlaps exceeds the cross-class expected overlap whenever the classes' membership profiles differ. Let π_c(v) be the probability that background vertex v belongs to a class-c subgraph. For two subgraphs drawn independently from their respective classes, the expected shared-member count is ⟨π_c, π_c'⟩, or ‖π_c‖² for a same-class pair. For any two classes:

=\frac12\\|\pi_c-\pi_{c'}\\|^2.$$ Equality holds only when π_c = π_c'. While this identity describes a class-conditional average, agreement with the most related labeled source supplies the evidence for individual queries. Because designated sets are small relative to the graph, exact overlap can be rare (2.2% of PPI-BP training pairs share a vertex). Diffusion replaces π_c with π_c P and relates sets without shared vertices, which helps when π_c varies smoothly over the graph. Because P is symmetric with eigenvalues in [−1, 1], ‖(π_c − π_c')P^h‖ does not increase with h; the depth ablation in Appendix J.3 shows that short, non-zero depths lead on these tasks. Conversely, relations carry no class information when classes differ only in internal shape. In our synthetic study, with informative shapes and class-independent relations, RAISE stays near chance (51.17) while WL-KRR reaches 75.00; as relations become class-dependent, RAISE rises to 98.00. The revision adds this analysis as Appendix J.1, with a pointer from Section 4.1. **W2. Complementarity and equal weighting.** Membership and diffusion relations lead on different tasks and share one scale after trace normalization, so equal weighting keeps both without choosing one per task. Varying the membership weight η in K0 = η·TN(K_mem) + (1−η)·TN(R2), with everything else frozen in the full pipeline, gives: | η | 0 | 0.25 | 0.5 (RAISE) | 0.75 | 1 | |---|---|---|---|---|---| | Validation micro-F1 | 53.43 | 53.16 | 53.20 | 52.81 | 52.52 | | Test micro-F1 | 55.13 | 55.47 | 55.40 | 55.10 | 54.86 | Full weight on diffusion is better on the HPO tasks (HPO-METAB 50.28 vs 48.06, HPO-NEURO 58.10 vs 55.37), whereas full weight on K_mem is better on PPI-BP (44.50 vs 43.36) and EM-USER (71.53 vs 68.78). Choosing the wrong endpoint costs 1.1–2.8 points, while K0 stays within 0.10–1.57 of the better endpoint on every task. Across the four tasks, the curve is flat around η = 0.5, within 0.23 of the best fixed weight on validation and 0.07 on test, and the centered kernel alignment (CKA) of K_mem and R2 is 0.46–0.68 (Appendix J.3). Because class-wise aggregation always uses R2, even the endpoints do not use one term alone, so we also remove aggregation to compare the terms alone. On PPI-BP, where exact overlap is sparsest, equal weight then beats both terms in KRR with self-training: | Kernel (no aggregation) | Validation micro-F1 | Test micro-F1 | |---|---|---| | Diffusion only | 43.41 | 41.04 | | K_mem only | 43.16 | 40.63 | | Equal weight | **44.91** | **42.92** | Both terms include neighborhood information, but the one-hop block of K_mem adds information beyond R2. We split K_mem into its two blocks in the full pipeline: | Blocks kept | Used alone (η = 1) | Inside K0 (η = 0.5) | |---|---|---| | Exact members only | 54.14 | 55.02 | | One-hop expansion only | 53.54 | 55.43 | | Both | 54.86 | 55.40 | The one-hop block and R2 have CKA 0.36–0.59, and removing that block from K0 lowers micro-F1 from 55.40 to 55.02. Used alone, the two blocks together beat either block on the four-task mean and on PPI-BP and HPO-METAB. Through the self-loop of A + I_n, the one-hop block keeps each member's own direct contribution (Appendix J.3).
AuthorsOpenReview ↗

Response to Reviewer 1tt9 (2/2)

W3. Justification of the multiplicative dependence model. The product form in Ω is the covariance of an explicit projection-error model, which the revision adds as Appendix J.2. The intuition, for single-label tasks: in the model, an error at vertex v in the fitted field for class c (w_c in step 1) shifts the pseudo-label score of exactly those pseudo sources that both contain v and carry pseudo-label c. Because two pseudo sources share this error only when both conditions hold, their dependence is the product of member overlap and pseudo-label agreement rather than their sum. The model follows the first KRR fit:

  1. First-fit class scores are linear in the vertex responses. Because K0 is a Gram matrix, each score f_ic equals ⟨x_i, w_c⟩ plus an intercept, where x_i stacks subgraph i's membership, one-hop, and diffusion responses at background vertices, and w_c = Σ_j W_jc x_j is the fitted class field.
  2. On the membership block of x_i, which is half the row-normalized membership ½M̄_i, two sources share coordinates exactly when they share members. An error of w_c at some vertices of this block shifts the class-c scores of every pseudo source with members at those vertices. The model keeps only this block.
  3. Projecting the class-score errors onto the normalized pseudo-target T̄_i yields the scalar error Σ_c T̄_ic δf_ic. For a single-label pseudo source, this is the error in the score of its pseudo-label.

For fixed memberships and pseudo-targets, we model this scalar error as

si=⟨Mˉi⊗Tˉi,ε⟩+ei,s_i=\langle\bar M_i\otimes\bar T_i,\varepsilon\rangle+e_i,

where ε is the class-field error on the membership block, and its entries and the noises e_i are mutually independent with equal variance. Then

Cov⁡(si,sj)∝δij+(Mˉi⋅Mˉj)(Tˉi⋅Tˉj).\operatorname{Cov}(s_i,s_j)\propto\delta_{ij}+(\bar M_i\cdot\bar M_j)(\bar T_i\cdot\bar T_j).

This matches the pseudo block of Ω, including its diagonal of two, and factors into member overlap times target agreement. The target factor is the indicator of equal pseudo-labels on single-label tasks and 1 − 2d_H/C on multilabel tasks, where d_H is the Hamming distance. RAISE uses this matrix to model source dependence across all class columns in the refit.

Real-task residuals show this overlap-dependent correlation. Across 50 fresh subsets, the excess overlap-weighted error correlation of pseudo sources above within-stratum permutations is positive in both halves on PPI-BP (+0.331), HPO-METAB (+0.101), and HPO-NEURO (+0.020) (Table E.7; EM-USER has only 18 eligible pairs, too few for a stable estimate). In a single-fit diagnostic that centers residuals within pseudo-target and confidence strata, the excess overlap-weighted residual alignment is positive in all 60 low-label conditions (Appendix E.5).

In controlled error injection, the refit's gain grows with the strength of shared errors and with member overlap. We inject pseudo-label errors that share a per-class field on vertices with strength ρ, u_ic = ρ⟨M̄_i, g_c⟩ + √(1−ρ²)·e_ic, flipping the largest 20% or 40%. Against a diagonal treatment with the same pseudo-source weight, the four-task mean gain of the refit rises from +0.28 at ρ = 0 to +0.43 at ρ = 0.5 and +0.80 at ρ = 0.9. For pseudo-source sets chosen with low and with high overlap (30% flipped), the gain at ρ = 0.9 is −0.68 and +2.43 on HPO-METAB, +1.09 and +2.66 on HPO-NEURO, and +0.14 and +3.33 on EM-USER. On PPI-BP, where pseudo sources share almost no members, the gain stays near zero.

With the original pseudo-labels on the real tasks, the refit adds +0.20 [0.13, 0.27] micro-F1 over independent weighting, with the 95% interval above zero.

We hope the label-agreement evidence, the weight and block ablations, and the error model answer your three weaknesses, and we would be grateful if you would reconsider your score.

Dear Reviewer 1tt9,

Thank you again for your review. With the discussion period closing on November 18, we would like to know whether our responses and the revised PDF (changes in blue) resolve your three concerns. For W1, on training labels, pairs in the top overlap decile share a label 1.25–2.7 times as often as the base rate (Section 1, Appendix J.1). For W2, equal weighting is within 0.10–1.57 points of the better endpoint (η = 0 or 1) on every task (Appendix J.3). For W3, Appendix J.2 derives the product form in Ω as the covariance of an explicit projection-error model, and Section 4.3 now points to it.

If something is still unclear, particularly why shared membership separates classes, we would be glad to explain further before the deadline.

Best regards,
The Authors

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

This paper proposes RAISE (Relation-Aligned Inference from Sparse Examples), a framework for label-efficient subgraph classification on a shared background graph. The key motivation is that structural similarity alone may fail to capture instance-specific relationships between labeled subgraphs and unlabeled queries, particularly when structurally similar labeled examples do not provide sufficient support for the query’s true class.

RAISE constructs a fixed, label-free relational kernel by combining subgraph membership, neighborhood, and pooled diffusion information. Based on this kernel, the method employs kernel ridge regression to learn class-specific source contributions and class-wise diffusion aggregation to provide complementary prediction scores. It further incorporates one round of confidence-based self-training, followed by dependence-aware refitting that accounts for correlations among pseudo-labeled subgraphs.

The method is evaluated on four biological and social network benchmarks under certain label budgets. Experimental results show improvements in average micro-F1 and macro-F1 compared to baselines. Additional ablation studies evaluate the effectiveness of their designs.

Critical strengths
  1. Good Empirical Performance. The proposed RAISE framework demonstrates promising empirical performance across four subgraph classification benchmarks under different label budgets (2%, 5%, 10%, and 20%). As reported in Table 1, RAISE achieves average micro-F1 and macro-F1 scores of 55.40% and 52.94%, outperforming PADEL by 4.71% and 6.74%, respectively. The improvements are particularly noticeable on HPO-METAB and HPO-NEURO, suggesting that the proposed relational representations are effective in biological network classification tasks.

  2. Comprehensive Ablation Studies. The paper provides extensive experiments to investigate the contributions of the proposed components. In Table 2, the authors compare different relational representations under matched prediction settings, showing that replacing the WL kernel with the proposed relational kernel consistently improves classification performance. For instance, under KRR, the average micro-F1 increases from 48.35% to 53.57%. The component-level experiments further examine the effects of self-training, class-wise diffusion aggregation, and dependence-aware refitting, helping identify the sources of the overall improvement.

Critical weaknesses
  1. Limited Methodological Novelty. Although RAISE achieves promising empirical results, its methodological novelty appears relatively limited. The overall framework largely builds on established techniques, including handcrafted graph features, kernel ridge regression, class-wise similarity aggregation, and confidence-based self-training. Specifically, the proposed relational kernel combines normalized membership features, one-hop neighborhood responses, and pooled diffusion representations through fixed Gram matrices. The resulting kernel is then used in standard kernel-based supervised learning, while the additional aggregation branch resembles class-prototype-based inference. The main contribution therefore seems to lie in the construction and combination of task-specific relational features rather than the development of a fundamentally new learning mechanism.

  2. Insufficient Justification for Relational Feature Design. The relational kernel relies on several manually specified design choices, but the underlying principles guiding them are not sufficiently established. For example, the authors combine membership overlap, one-hop random-walk neighborhood features, and two-step pooled diffusion responses. However, it remains unclear why they selected these propagation depths, or whether alternative diffusion orders or multi-scale relational representations might yield more informative features. Similarly, the weighted pooling strategy emphasizes vertices based on their membership rarity and connectivity beyond subgraph boundaries, but the paper does not fully explain which graph properties would make these weighting criteria beneficial.

Questions for authors
  1. Could the authors further clarify the fundamental methodological novelty of RAISE compared with existing graph kernel and propagation-based approaches? In particular, what distinguishes the proposed relational inference framework from applying standard kernel-based classification to carefully engineered relational features?

  2. What motivates these specific feature choices and propagation depths? Are there general principles guiding the construction of the relational kernel, and under what graph conditions should these features be expected to provide complementary information?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Wb9W (1/2)

Thank you for the clear questions.

W1 / Q1. Novelty relative to kernel classification on engineered features. RAISE's methodological contribution is to keep and use the member and diffusion correspondence between a specific source and a query, in the shared background-vertex coordinates. Two subgraphs with the same WL color histogram have the same WL kernel value with any labeled source; RAISE gives them different relation values according to which members they share with that source and on which background vertices their diffusion responses overlap. Its kernel is unchanged when the background graph and all member sets are renumbered together, so this distinction does not depend on an arbitrary vertex numbering (Section 4.1).

This construction also differs from subgraph-level message passing. S2N and CoS2N translate subgraphs into nodes of a graph linked through shared members and edges, and pass messages there; RAISE keeps the responses at every background vertex and adds two-step diffusion. In Table 1, RAISE exceeds S2N and CoS2N by 10.4 and 8.5 micro-F1 points. On these fixed relations, RAISE fits per-class source weights with KRR, aggregates diffusion responses by class, and performs one self-training round. Standard self-training refits as if pseudo-labels were independent; RAISE's refit models correlated residuals for pseudo sources that share members and pseudo-labels (Section 4.3).

Four controlled comparisons test whether this correspondence carries label information beyond the evaluated structural representations, each against another explanation of the gain:

  1. Structural similarity in another form? On training labels, within fixed WL strata, stronger diffusion relations accompany higher label agreement in 39 of 40 strata.
  2. The predictor? As you note, replacing WL with K0 under matched prediction raises micro-F1 from 48.35 to 53.57 with KRR. The gain is 4.99 with self-training and holds on 50 fresh labeled subsets.
  3. One engineered kernel? Heat and personalized-PageRank kernels on the same coordinates and pipeline, with α chosen on validation, give 52.30–54.16, above every baseline in Table 1 (the best is PADEL at 50.69). K0 (55.40) adds a further 1.2–3.1 points, with one configuration for all tasks and budgets.
  4. A global property of the kernel? The gain follows which instance carries which relation. Reassigning relations among 2, 5, 10, and 20% of instances, with labels, splits, and the kernel's spectrum, rank, and scale fixed, lowers RAISE's micro-F1 at 10% labels step by step from 59.92 to 49.52, which is below WL-KRR (Section 5.4). For single pairs on PPI-BP at 5% labels, with the query, the label count, and the source-class composition fixed, exchanging one labeled source for a WL-matched source with a stronger diffusion relation raises the true-class margin in 253 of 254 same-class swaps and lowers it in 375 of 479 other-class swaps under K0-KRR, while WL-KRR margins stay near zero. The pattern holds on HPO-METAB and EM-USER under relaxed matching (Appendix J.4).

Together, these comparisons show that shared members and diffusion-response overlap between a labeled subgraph and a query carry label information that structural summaries discard. For subgraph classification with few labels, this gives a way to classify queries that lack structurally similar labeled examples of their class. On support-gap queries, whose true class is observed among the labeled sources but absent from their five WL-nearest ones, RAISE exceeds PADEL by 5.65, 14.42, and 5.73 micro-F1 points on PPI-BP, HPO-METAB, and HPO-NEURO (Section 5.3). The reverse case holds as well: when classes differ only in internal shape, a structural kernel is the better choice (our answer to Q2). The revised Introduction now presents this evidence before the method.

AuthorsOpenReview ↗

Response to Reviewer Wb9W (2/2)

W2 / Q2. Principles behind the feature choices. Three principles guide the kernel:

  • Subgraphs are compared on the shared background-vertex coordinates.
  • Each relation is a Gram matrix of responses, so the kernel is positive semidefinite by construction.
  • Diffusion is kept short: it connects disjoint sets, but each step can also contract class differences.

Depth. Depths 1 and 2 lead every other setting on both validation and test, and depth 2 is the shortest positive depth that is positive semidefinite by construction. Because R2 = (BP)(BP)ᵀ compares the one-step diffusion responses of two subgraphs, the relation spans two steps in total (depth 2). Odd depths need not be positive semidefinite; in the table below they use the positive part of the symmetrized relation. Two steps already relate almost all pairs: on PPI-BP only 2.1% of subgraph pairs share a member, whereas 97.4% are related after two steps (HPO-METAB 43.9 → 100%, EM-USER 83 → 100%).

Diffusion depth012 (RAISE)346multi-scale (2, 4, 6)
Validation micro-F149.5453.6053.2050.9350.0348.1251.95
Test micro-F152.7054.1855.4053.4152.4351.3254.12

Per task, validation selects depth 2 on PPI-BP, HPO-NEURO, and EM-USER, and depth 1 on HPO-METAB.

Pooling weights. Each member is weighted by two properties: rarity across designated sets and boundary connectivity. Rarity targets graphs where some vertices belong to many designated sets, keeping them from dominating comparisons. Boundary connectivity up-weights members with edges leaving the set, which carry its diffusion response to the rest of the graph. Micro-F1 is 53.21 for uniform pooling, 53.06 for rarity only, 54.82 for boundary connectivity only, and 55.40 for both; boundary connectivity gives most of the gain, and rarity adds +0.58 on top of it.

Graph conditions under which the relations help. The relations carry class information when classes draw members from different vertex distributions: the expected cross-class overlap is then below the mean of the two within-class overlaps (Appendix J.1). They carry none when classes differ only in internal shape. In our synthetic study, RAISE then stays near chance (51.17) while WL-KRR reaches 75.00, and RAISE rises to 98.00 as relations become class-dependent. On PPI-BP, where exact overlap is sparsest, the two terms complement each other: with each kernel used alone in KRR with self-training and no aggregation, equal weighting beats both on validation and test. Neither term is best everywhere (diffusion on the HPO tasks, K_mem on PPI-BP and EM-USER), and the equal-weight default stays within 0.10–1.57 points of the better endpoint on every task (Appendix J.3).

We hope these results answer your two questions, and we would be grateful if you would reconsider your score.

Dear Reviewer Wb9W,

Thank you again for your review. As the discussion period closes on November 18, we would like to ask whether our responses and the revised PDF (changes in blue) address your two questions. The main evidence now appears in the Introduction. With the ridge predictor fixed, swapping the WL kernel for the relational kernel adds 5.22 micro-F1 points (Table 2a). If we instead reassign the relations of 20% of instances, keeping labels and the kernel spectrum unchanged, RAISE drops from 59.92 to 49.52 at 10% labels, below WL-KRR (Section 5.4).

We would welcome any further question, in particular on how RAISE differs from kernel classification on engineered features.

Best regards,
The Authors

Dear Reviewer Wb9W,

Thank you again for your review. As the discussion period closes at the end of November 18 (AoE), we would like to briefly follow up on our responses to your questions on novelty and feature design. The relation-reassignment result in Section 5.4 is the most direct evidence of what distinguishes RAISE. If any point remains unclear, we would be glad to clarify it before the deadline.

Best regards,
The Authors

Comments on the paper

1 comment

We thank the reviewers for careful and specific reviews. Reviewers describe the research position as "clear and meaningful" and the framework as an alternative perspective to conventional subgraph representation learning (1tt9). They find that the correspondence experiments validate the predictive value of instance-specific relations (1tt9) and are "relatively convincing" (Xu3g). They also note good empirical performance with comprehensive ablations (Wb9W), and efficiency: 0.22 hours for all 120 main-table conditions, against 139.6 hours for PADEL (Xu3g).

Shared questions are addressed below, and reviewer-specific questions in the individual replies. None of the new analyses changes RAISE, its hyperparameters, or the main table, and the new results are in Appendix J.

GR1. Label information beyond structural similarity (1tt9, Wb9W)

On training labels, label agreement rises with membership overlap on all four tasks, and within fixed WL strata, stronger diffusion relations accompany higher label agreement in 39 of 40 strata. Under the same KRR, replacing WL with K0 adds 5.22 micro-F1 on the original split and +3.88 / +3.50 / +5.70 on three new random splits. Section 1 now presents this evidence before the method, Section 4.1 states the condition under which it holds, and Appendix J.1 gives the argument.

GR2. Design choices (1tt9, Wb9W)

  • Product form of the dependence structure (1tt9): it is the covariance of an explicit error model (Section 4.3, Appendix J.2).
  • Complementarity of the two kernel terms and equal weighting (1tt9): ablations of the kernel weights and of the two blocks of the membership kernel.
  • Diffusion depth and pooling (Wb9W): ablations of depth, pooling, and standard diffusion kernels (heat, personalized PageRank).

GR3. Robustness of the main comparison

Two further checks support the main comparison beyond the labeled-subset intervals of Section 5.2: test-query resampling (paired across methods, 2,000 draws) and three new random train/validation/test splits per task. The new splits keep the original sizes and use one labeled subset per task and budget; their test sets overlap the originals by only 8–22%, and all listed methods were rerun. The bootstrap interval excludes zero against all nine baselines, and RAISE exceeds PADEL in 11 of 12 split–task combinations.

RAISE minusOriginal split, test-query bootstrap: micro [95% CI]Macro [95% CI]Three new splits: microMacro
PADEL+4.71 [2.95, 6.45]+6.74 [5.13, 8.24]+3.51 / +3.94 / +3.16+6.34 / +6.28 / +7.01
ISNN+6.56 [4.41, 8.67]+9.92 [7.95, 11.83]+5.15 / +5.40 / +5.30+8.11 / +9.37 / +8.92
Member + 1-hop Ridge+6.62 [4.36, 8.95]+10.15 [8.51, 11.72]+3.17 / +4.27 / +5.53+7.81 / +7.54 / +8.73

On the new splits, the margin over PADEL is largest at 2% labels (+6.24 micro, +10.46 macro). Appendix J.5 reports the intervals and the new splits.

Summary of revisions

Changes in the revised PDF are shown in blue.

  • Section 1: direct evidence for the research question, placed before the method (1tt9, Wb9W), and the role of each component (Xu3g).
  • Section 4.1: class-conditional argument, pooling weights, equal weight, and depth (1tt9, Wb9W).
  • Section 4.3: error model for the dependence structure (1tt9) and a shorter description of source deletion.
  • Section 5.1: scope of standardization and a version without test-query moments (Xu3g; results in our reply to Xu3g).
  • Section 5.2: analysis of very low budgets (Xu3g).
  • Section 5.4: the source exchange on HPO-METAB and EM-USER, where the margin pattern holds at all four budgets (Xu3g; Appendix J.4).
  • Appendix J (new): the supporting tables and analyses.

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

Related papers

Discussion (0)

Sign in to comment.