acceptodds
Under review as a conference paper at ICLR 2027

Shape-Matched Evaluation of Returned SEGO Coding Trees on Molecular Scaffold Shift

Abstract

Recognizing molecules with unfamiliar core frameworks is an important task for molecular property models. Hierarchical graph representations organize vertices into nested groups. Their detection performance, however, leaves open what the chosen groups reveal beyond the hierarchy's shape. We introduce a comparison that preserves group sizes and branching while randomizing vertex membership. We apply it to coding trees from a structural entropy guided graph detector and evaluate the edges retained within groups before representation learning. On molecular scaffold splits, these summaries yield positive average ranking gains over the random reference. The evidence depends on the detector and on how the reference is estimated: repeated evaluations retain positive means at the original randomization budget, while larger ensembles leave the gain uncertain. This comparison helps distinguish information in the chosen groups from that captured by a hierarchy of the same shape. The core code is provided in the supplementary material.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph out-of-distribution detection, structural entropy, coding trees, molecular graphs, permutation controls, anomaly detection

Reviews

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

The paper proposes a shape-matched evaluation of SEGO coding trees that preserves hierarchy branching and group sizes while randomizing vertex membership. Using edge-fraction summaries for molecular scaffold-shift detection, it examines whether SEGO’s selected memberships provide information beyond hierarchy shape, finding small gains that depend on the detector and reference estimation.

Critical strengths
  1. The shape-matched randomization provides a controlled way to assess whether selected vertex memberships contribute useful information beyond hierarchy branching and group sizes.

  2. The paper transparently reports uncertainty and conducts sensitivity analyses across detectors, tree heights, randomization budgets, and repeated pipelines, helping clarify the robustness and limitations of its findings.

Critical weaknesses
  1. The main contribution is a shape-preserving randomization control applied to an existing hierarchy construction, which limits the methodological novelty. In addition, the paper needs to justify its conceptual advance over established constrained-randomization evaluations more clearly.

  2. The experimental evaluation covers only a limited number of datasets. Additional molecular datasets, including larger datasets such as ogbg-molpcba, and additional hierarchy methods would help establish the generalizability of the findings. Furthermore, the experiments provide limited evidence of a reliable advantage over the shape-matched reference.

  3. The analysis uses compact edge-fraction summaries before neural representation learning. It does not test whether replacing SEGO’s coding trees with shape-matched random trees changes the performance of the complete SEGO pipeline. Consequently, the findings cannot directly explain the hierarchy’s contribution to SEGO’s reported success.

Questions for authors
  1. What conceptual or methodological advance does the proposed shape-matched control offer over established constrained-randomization evaluations?

  2. How well do the findings generalize to larger molecular datasets, such as ogbg-molpcba, and alternative hierarchy constructions? Given the small gains and their sensitivity to reference estimation, what evidence supports a reliable advantage over the shape-matched reference?

  3. How does replacing SEGO’s coding trees with shape-matched random trees affect the complete SEGO pipeline? Would the conclusions drawn from compact edge-fraction summaries remain valid after neural representation learning?

3 comments
AuthorsOpenReview ↗

Response to Reviewer

W1 / Q1: Advance over generic constrained randomization.

Our contribution is to evaluate the gains from vertex membership separately from graph-dependent hierarchy shape. A hierarchy construction determines group sizes, branching structure and vertex membership together. Comparing returned and random trees without matching their shapes mixes these factors. We fix the original graph, every group size and all branching relations, randomizing only vertex membership to establish a membership control within the same shape.

On this basis, we separately evaluate absolute detection performance, gain over a construction's own shape reference, and gain differences between constructions. Each construction uses its own shape reference, allowing comparisons between hierarchy methods with different shapes. The added average-linkage comparison provides a concrete example: its Ledoit–Wolf gain is +0.0545 [0.0291, 0.0804], yet its absolute PC is only 0.5078.

The reference expectation of edge fractions can also be computed exactly from group sizes (Eq. 4), providing an analytically tractable comparison baseline.

W2 / Q2: Larger molecular data, alternative hierarchies and reliable advantage.

We extended the evaluation to the large-scale ogbg-molpcba dataset. Using the exact reference mean, the mean Ledoit–Wolf membership gain is +0.0163.

We also added shortest-path average-linkage as a hierarchy comparator. SEGO, the connectivity proxy and average-linkage use the same fitting samples and matched pairs, each with its own shape-matched reference.

The full results and intervals for all three detectors on ogbg-molpcba are reported below.

DetectorGain [95% OOD-identity interval]
Ledoit–Wolf+0.016281 [0.013657, 0.018835]
kNN-5−0.006701 [−0.008265, −0.005133]
Isolation Forest−0.003008 [−0.005625, −0.000427]

W3 / Q3: What changes after neural learning.

We conducted a paired scaffold-retraining extension using the full HCL and HRN architecture across five datasets and three training seeds. Returned and randomized memberships share the same hierarchy shape, initialization and training budget.

With the tree encoder updated during training and the actual tree–graph loss used for scoring, mean PC is 0.686957 for returned memberships and 0.674919 for randomized memberships, an average increase of approximately 1.20 percentage points. The gain changes sign across training seeds.

The two variants respectively retain the optimization and scoring behavior of the inspected source, or enable tree-encoder parameter updates and use the actual tree–graph loss for scoring.

Execution variantReturned PCRandom PCGain [95% OOD-identity interval]
Source behavior0.6777850.677493+0.000292 [−0.011508, 0.012441]
Corrected optimization and scoring0.6869570.674919+0.012037 [−0.003545, 0.028354]

We sincerely thank the reviewer for their valuable feedback. We hope that our responses have addressed your concerns. As the rebuttal period is coming to an end, we would be happy to further discuss any remaining questions or concerns. If our responses have resolved your concerns, we would greatly appreciate it if you could reconsider your assessment of our paper in light of our clarifications.

Reviewer_q5m8OpenReview ↗

Response to reviwer

Thank you for the response. However, my concerns have not been fully resolved. The response only demonstrates performance gains, but the methodological advantage of the randomization control remains unclear. Therefore, I will keep my score.

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

The paper aims to assess whether vertex groupings learned by structural-entropy coding trees retain useful information beyond random group assignments. They use molecular scaffold-based OOD detection to compare the learned tree's performance with that of shape-matched randomized trees. They observe modest improvement.

Critical strengths
  1. The paper addresses an interesting and relevant question about the information captured by learned graph hierarchies and its utility for OOD detection.

  2. The empirical evaluation is reasonably extensive, incorporating multiple datasets, detection methods, and sensitivity analyses. I also appreciate the authors' attention to uncertainty and cautious interpretation of the findings.

Critical weaknesses
  1. The authors use a limited set of edge summaries in this paper. These statistics discard substantial information from the original connectivity patterns and hierarchical organization. Furthermore, because structural-entropy optimization is designed to identify groups that respect graph connectivity, it is not surprising that it outperforms random vertex assignments. It is unclear what substantive insight these comparisons establish. IT does not address whether the learned hierarchy offers meaningful advantages over alternative graph-aware representations.

  2. Although the empirical evaluation includes multiple molecular datasets and sensitivity analyses, the reported improvements in OOD discrimination are small, and their statistical robustness is uncertain. The evaluation is also restricted to a particular family of structural shifts, without any systematic investigation of different types of graph anomalies. Consequently, the experiments do not sufficiently establish when the proposed summaries are informative for OOD detection, what structural information drives their performance, or when they might fail.

Questions for authors
  1. Please include and discuss how your work relates to "Wu, J., Chen, X., Shi, B., Li, S., & Xu, K. (2023, July). Sega: Structural entropy guided anchor view for graph contrastive learning. In International Conference on Machine Learning (pp. 37293-37312). PMLR." Their Section 5.3 Ablation Study does similar comparisons between optimized and random coding trees.

  2. Please explain why you chose within-group edge fraction as your main summary. I can imagine that using topological structure, a structural entropy profile, or another embedding of the full coding tree may capture richer information. Group-specific or intra-group connectivity may also contain important information you are discarding.

  3. Your OOD simulation study should be strengthened to incorporate different structural shifts. I suggest investigating a null scenario (no distributional shift), a community-structure shift in a stochastic block model (or a similar model), a degree-driven shift, and perhaps a structural shift not reflected in edge retention. This would provide insights into the specificity and detection limits of the proposed evaluation. This would also help generalize the finding to a broader setup.

  4. I think the fact that a learned graph hierarchy will outperform a random assignment is not surprising. The modest OOD performance improvement makes me think the summary choice is not optimal. Please explain why this random graph alternative is meaningful. Comparison to a graph-aware hierarchy method should provide stronger evidence.

3 comments
AuthorsOpenReview ↗

Response to Reviewer

W1 / Q1: Relation to SEGA (Wu et al., ICML 2023).

The key distinction is what is controlled and what the comparison can consequently answer. Section 5.3 of SEGA compares an entropy-guided anchor view with a random balanced binary coding tree of the same height, two. Our reference additionally fixes the original graph, every group size and every branching relation of each returned tree, randomizing only vertex membership. Wu et al., ICML 2023.

Trees of equal height can still differ in group sizes and branching structure, so a performance difference between optimized and random trees can reflect both shape and membership. The shape-matched control separates these factors, allowing a more specific question: Given the shape selected by a construction, how much additional detection benefit do its selected memberships provide? The same control applies to other hierarchy constructions, enabling comparison of their respective gains beyond their own shape references.

W1 / Q2: Why edge fractions, and what they discard.

Edge fractions provide coordinates with a consistent meaning and an analytically tractable reference for shape-matched comparisons. Each level measures the fraction of connectivity retained within groups, making returned and randomized memberships directly comparable. The exact reference expectation is determined by group sizes (Section 3.1 and Eq. 4), allowing us to distinguish edge retention expected from the shape from the retention observed for the selected memberships.

This summary captures connectivity retention across hierarchy levels, while full topology, structural-entropy profiles and tree embeddings can describe additional structural properties. An explicit construction illustrates the distinction: within fixed six-vertex groups, two triangles and one six-cycle have identical edge counts and vertex degrees, producing identical edge summaries despite different triangle counts. This example specifies the structural information captured by edge fractions and the additional information that richer representations can supply.

W2 / Q3: No-shift, community-shift and degree-shift diagnostics.

All four requested diagnostic categories are complete. Across 13,500 simulated graphs, the summary provides positive reference-relative gains for two detectors under the community shift, while the degree shift reverses the gain for all three. Q2 gives the additional fixed-hierarchy blind spot.

The community comparison holds expected degree at four. Its returned PC is 0.565–0.593, while the four degree features give approximately 0.5. Under the degree shift, the shape reference reaches approximately 0.95 and degree features approximately 0.997, exceeding returned PC of approximately 0.72. Thus the signal captured by the summary depends on the shift being tested.

All pooled no-shift absolute-PC intervals include 0.5, with one single-seed exception. The community result also varies with graph size: at n = 24, all SEGO-minus-proxy gain differences are negative point estimates. The table reports pooled returned-minus-reference gains, with nominal intervals conditional on the realized panel and fitted detectors.

ShiftLedoit–WolfkNN-5Isolation Forest
None: ER to iid ER−0.0117 [−0.0407, 0.0163]+0.0030 [−0.0300, 0.0350]−0.0110 [−0.0410, 0.0187]
Community: ER to SBM+0.0490 [0.0183, 0.0787]+0.0330 [−0.0007, 0.0667]+0.0660 [0.0340, 0.0980]
Degree: ER mean 2 to 4−0.2200 [−0.2440, −0.1953]−0.2400 [−0.2653, −0.2140]−0.2390 [−0.2643, −0.2127]

W1 / Q4: Why the reference is informative, and graph-aware alternatives.

We compare gains in OOD ranking, rather than within-group edge retention. The random reference preserves the original graph, every group size and all branching relations, changing only vertex membership. An optimization preference for connected groups therefore does not by itself answer whether those memberships provide detection gains beyond hierarchy shape.

For the graph-aware hierarchy comparison, we added shortest-path average-linkage alongside the connectivity proxy. Using the same fitting samples and matched molecular pairs, each construction has its own shape-matched reference, and we directly compare gains between constructions.

We sincerely thank the reviewer for their valuable feedback. We hope that our responses have addressed your concerns. As the rebuttal period is coming to an end, we would be happy to further discuss any remaining questions or concerns. If our responses have resolved your concerns, we would greatly appreciate it if you could reconsider your assessment of our paper in light of our clarifications.

Thank you for the clarifications and additional simulations, which address several of my concerns. They do not address the comparison with graph-aware alternatives. Adding average linkage is helpful, but the results do not include the actual comparisons or uncertainty estimates. My concern about the robustness of the detection gains on the molecular benchmarks also remains unresolved. I retain my weak-reject recommendation for now.

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

This paper introduces a shape-matched evaluation for testing whether the vertex memberships selected by a graph hierarchy contain information beyond its shape. It compares edge-retention summaries from SEGO coding trees with randomized memberships preserving group sizes and branching, using separately fitted anomaly detectors on matched molecular scaffold-shift pairs. The returned hierarchies show small positive average gains under the primary setting, but the gains depend on the detector, reference estimation, and feature controls.

Critical strengths
  • The shape-matched reference cleanly separates hierarchy membership from hierarchy shape.
  • The matched evaluation reduces obvious node-count and mean-degree confounding.
  • The uncertainty and sensitivity analyses are relatively comprehensive.
Critical weaknesses
  • The technical contribution and empirical scope are narrow.
  • The membership advantage is small and sensitive to reference estimation.
  • Simple structural controls weaken the proposed interpretation.
  • The analysis is disconnected from SEGO’s claimed performance mechanism.
Questions for authors
  1. The edge-retention vector does not directly measure redundancy-eliminated essential information. wℓw_\ell records only the fraction of edges retained within groups. Why is this statistic an appropriate proxy for redundancy removal or essential structural information?

  2. The primary representation comparison is asymmetric. The returned representation contains [wret,wret−μR][w^{ret},w^{ret}-\mu_R], whereas the random representation contains [μR,σR][\mu_R,\sigma_R], whose second halves have different meanings. Why should their separately fitted detector performance isolate the effect of membership?

  3. The observed gain may be explained by simple degree structure. In Table 3, degree statistics outperform the SEGO edge features under kNN and Isolation Forest, while the degree-plus-returned versus degree-plus-random gains are statistically uncertain. Can the authors control for the full degree distribution or use a degree-aware null model?

  4. The primary conclusion is sensitive to the randomization budget. At R=2048R=2048, the gains decrease and all crossed confidence intervals include zero, while Equation 4 provides the exact reference mean. Why is R=64R=64 retained as the primary analysis instead of an exact or demonstrably converged reference?

  5. The analysis does not explain SEGO’s claimed performance mechanism. SEGO attributes its effectiveness to redundancy-eliminated essential information and multi-grained triplet contrastive learning, but this paper stops before representation learning. Could the authors replace only the returned memberships with shape-matched random memberships inside the complete SEGO pipeline and report final OOD performance?

  6. The experiments do not establish that the gain is specific to SEGO. In Table 6, the gain difference between SEGO and the connectivity-guided proxy is statistically uncertain for every detector. Does the result reflect structural-entropy optimization or merely a generic preference for grouping connected vertices?

  7. The statistical inference applies to a selected matched population. The evaluation retains 83.6% of OOD molecules but only 55.5% of node-count strata, and the bootstrap does not explicitly account for scaffold-family dependence. Can the authors report per-dataset coverage and scaffold-clustered uncertainty?

  8. The generality of the proposed evaluation remains unclear. The experiments cover one hierarchy method, one hand-designed proxy, attribute-free molecular graphs, and scaffold shifts. Can the authors validate the framework on additional hierarchy constructions and non-molecular graph OOD settings?

3 comments
AuthorsOpenReview ↗

Response to Reviewer

Thank you for your careful review and valuable feedback.

W1 / Q1: What the edge summary measures.

The edge-retention vector provides a testable connectivity readout for the structural information preservation emphasized by SEGO: it records the fraction of edges retained within groups at each hierarchy level. Holding the graph and hierarchy shape fixed, we compare the edge summaries and OOD rankings of selected and randomized memberships to test whether this organization of connectivity provides detection information beyond the shape reference. The coordinates have consistent meanings and an exact reference expectation conditional on group sizes (Section 3.1 and Eq. 4). Here, redundancy removal and essential information motivate the mechanism question; edge fractions specifically measure connectivity retention.

W2 / Q2: Representation asymmetry and the estimand.

The result is not confined to the asymmetric full representation. Section 3.2 and Table 10 already compare only the shared edge-fraction coordinates. Section 4.2 defines the target as a difference between separately fitted representations, rather than a fixed-scorer causal effect.

Using shared edge-fraction coordinates and the exact reference mean, Ledoit–Wolf yields a gain of +0.0217 with a nominal 95% interval of [0.0007, 0.0422]. The positive gain for this detector therefore persists after removing the coordinate-semantics mismatch and reference-mean sampling error.

DetectorShared-coordinate gain with exact mean [95% OOD-identity interval]
Ledoit–Wolf+0.0217 [0.0007, 0.0422]
kNN-5+0.0032 [−0.0196, 0.0243]
Isolation Forest+0.0091 [−0.0127, 0.0303]

W3 / Q3: Degree-composition control.

To test whether the gains arise from within-group degree composition, we permute only equal-degree vertices, preserving the full degree histogram of every group along with the original graph and hierarchy shape. The controlled gain estimates remain positive for all three detectors and are no lower than their counterparts under the unconstrained exact-mean reference. Thus, the stricter within-group degree control does not reduce the observed mean gains.

DetectorReturned minus degree-conditioned reference [95% OOD-identity interval]
Ledoit–Wolf+0.0222 [−0.0005, 0.0434]
kNN-5+0.0133 [−0.0091, 0.0353]
Isolation Forest+0.0144 [−0.0075, 0.0358]

W2 / Q4: Exact moments and reference-budget sensitivity.

To address reference convergence, we computed the exact mean and exact marginal standard deviation and use the exact-reference results as the basis for this comparison, eliminating Monte Carlo estimation error in the reference moments. The table also includes the R=64 setting selected during development for comparison.

DetectorOriginal R=64 gainExact-moment gain [95% OOD-identity interval]
Ledoit–Wolf+0.0218+0.0054 [−0.0127, 0.0232]
kNN-5+0.0199+0.0069 [−0.0116, 0.0247]
Isolation Forest+0.0187+0.0127 [−0.0080, 0.0327]

W4 / Q5: Membership replacement after full-architecture retraining.

We conducted a paired scaffold-retraining extension using the full HCL and HRN architecture across five datasets and three training seeds. Returned and randomized memberships share the same hierarchy shape, initialization and training budget.

In the variant that updates the tree encoder and scores with the actual tree–graph loss, mean PC is 0.686957 for returned memberships and 0.674919 for randomized memberships, an average increase of approximately 1.20 percentage points. The gain changes sign across the three training seeds.

The two variants respectively retain the optimization and scoring behavior of the inspected source, or enable tree-encoder parameter updates and use the actual tree–graph loss for scoring.

Execution variantReturned PCRandom PCGain [95% OOD-identity interval]
Source behavior0.6777850.677493+0.000292 [−0.011508, 0.012441]
Corrected optimizer and scoring0.6869570.674919+0.012037 [−0.003545, 0.028354]
AuthorsOpenReview ↗

Response to Reviewer[2]

W1 / Q6: Construction-specific gain versus absolute performance.

With within-group degree composition fixed, the Ledoit–Wolf gain difference between SEGO and the connectivity proxy is +0.0489 [0.0153, 0.0827], showing that the two graph-aware constructions have different membership gains under this control. The table further reports SEGO gain minus proxy or average-linkage gain with nominal 95% intervals.

The proxy comparison uses degree-conditioned references, while the average-linkage comparison uses shape-matched exact-mean references.

Comparison and interval typeLedoit–WolfkNN-5Isolation Forest
SEGO−proxy, degree control, primary OOD identity+0.0489 [0.0153, 0.0827]+0.0214 [−0.0122, 0.0542]+0.0295 [−0.0028, 0.0614]
SEGO−average-linkage, primary OOD identity−0.032847 [−0.067256, 0.000106]−0.001235 [−0.034038, 0.030301]−0.005311 [−0.035861, 0.026220]
SEGO−average-linkage, ID-identity sensitivity−0.032847 [−0.060458, −0.006011]−0.001235 [−0.028113, 0.025044]−0.005311 [−0.031244, 0.021777]

Q7: Coverage and scaffold-family uncertainty.

The paired evaluation retains 2,391 OOD molecules, or 83.6% of the official OOD population. The 55.5% cited in the review measures coverage of node-count strata with eligible training–OOD overlap, rather than molecule retention. Relative to all raw OOD node-count strata, coverage is 46.7%. The table gives both molecule and stratum coverage for each dataset.

To examine scaffold-family dependence, we additionally performed bootstrap analyses clustered by chiral and achiral scaffolds. Within each evaluation context, every retained OOD chiral scaffold family is a singleton, so this clustering defines the same partition as molecular identity. With the exact-moment reference, the results clustered by OOD chiral scaffold are:

DetectorGain [95% scaffold-clustered interval]
Ledoit–Wolf+0.0054 [−0.0129, 0.0236]
kNN-5+0.0069 [−0.0114, 0.0260]
Isolation Forest+0.0127 [−0.0081, 0.0332]

The dataset breakdown combines validation and test contexts:

DatasetMatched OOD moleculesOfficial OOD moleculesRetained size strataEligible-overlap size strata
BACE2603034564
BBBP3064084687
SIDER1862863892
Tox211,4001,56776124
ClinTox2392963871
Total2,3912,860243438

W1 / Q8: Additional constructions and shift settings.

We extend the evaluation to an additional graph-aware hierarchy and controlled non-molecular graph OOD settings, testing applicability across constructions and responses to different structural shifts.

Additional hierarchy construction. We added shortest-path average-linkage alongside SEGO and the connectivity proxy, with a separate shape-matched reference for each construction. Average-linkage has a Ledoit–Wolf relative gain of +0.0545 and an absolute PC of 0.5078, showing how the same evaluation applies to different hierarchies while distinguishing relative gain from absolute detection performance.

Non-molecular graph OOD. Across 13,500 simulated graphs, we compare no shift, community shift and degree shift. Under the community shift with equal expected degree, the Ledoit–Wolf and Isolation Forest gains are +0.0490 [0.0183, 0.0787] and +0.0660 [0.0340, 0.0980], respectively. These provide positive examples of shape-matched evaluation in controlled non-molecular graph OOD settings.

Thank you for the response and additional experiments. The new analyses partially address the representation asymmetry and reference estimation. However, my main concerns remain.

  • The edge-retention vector is clarified as a connectivity readout, but no evidence connects it to redundancy-eliminated essential information. Thus, the mechanism gap remains.
  • The supplementary experiments still do not establish membership benefit or explain SEGO’s claimed performance mechanism. The exact and degree-conditioned intervals include zero, while the full-pipeline gain is insignificant and unstable.
  • The contribution remains narrow and is not shown to be SEGO-specific. The response does not address the statistically uncertain difference from the connectivity-guided proxy, scaffold-dependent inference, or generality beyond the molecular setting.

Overall, the rebuttal does not resolve the principal concerns regarding the paper’s motivation, mechanism, and contribution. I therefore maintain my current score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.