acceptodds
Under review as a conference paper at ICLR 2027

Must Graph Structure Remain Implicit? Explicit Topological Representations via Sparse Decomposition

Abstract

Graph neural networks and graph transformers achieve strong predictive performance but typically encode topology in latent coordinates without directly identifiable structural meaning. Classical graphlet representations expose structural patterns through predefined families. This raises a broader question: can an explicit, data-driven representation support competitive graph learning while keeping topology and attributes separately accessible? Building on sparse network decomposition, we show that explicit, learnable structural coordinates can support competitive prediction while making structural evidence independently auditable and traceable. Our framework combines shared-dictionary encoding of rooted patches with permutation-invariant readout, preserving occurrence-level links and supporting separate topology, attribute, and binding channels. The exact radius- rooted-patch profile refines rounds of 1-WL, while radius-one profiles distinguish some graph pairs unresolved by stable 1-WL. On BREC, the exact pair-rooted profile distinguishes 300 of 400 graph pairs, and a compact 128 atom representation retains nearly all of these distinctions. Across node- and graph-level benchmarks, the framework achieves competitive performance against recent GNN and graph Transformer baselines using conventional predictors. Coalition retraining quantifies standalone and conditional information-source contributions, while molecular case studies demonstrate how structural tracing supports testable chemical hypotheses and fixed-model interventions that identify split-specific structural shortcuts.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Representation Learning + Explicit Topological Representation + Interpretable Graph Learning + Structural Graph Analysis + Structural Information Auditing

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_gMrqOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a graph-learning framework that represents statistics, topology, and attributes separately, using a shared dictionary to learn explicit structural features. The framework achieves competitive predictive performance while enabling analysis of each feature block’s contribution and tracing learned structural components to their original subgraphs.

Critical strengths
  1. The framework keeps graph statistics, topology, and attributes separately accessible, enabling controlled analysis of their standalone and complementary predictive contributions.

  2. The learned structural representation supports tracing dictionary activations to concrete subgraphs, providing useful tools for hypothesis generation and diagnosing model behavior.

Critical weaknesses
  1. The methodological novelty and the benefits of the proposed shared-dictionary representation require clearer justification. Combining structural and attribute information is well established in this domain, as are explicit subgraph representations and graph dictionary learning. Although the paper combines these ideas with occurrence-level tracing, the experiments do not sufficiently isolate what the proposed dictionary construction adds beyond existing approaches.

  2. The effectiveness of topology–attribute integration and the added value of the learned topology representation require further clarification. Although the framework considers concatenation and explicit binding features, it remains unclear whether these mechanisms adequately capture interactions that could benefit from joint, task-adaptive learning. For example, on ENZYMES in Table 3, adding topology reduces performance, suggesting that the necessity of more controlled fusion. Furthermore, comparisons with alternative structural representations under the same downstream predictor—such as graphlet counts, rooted-subgraph descriptors, and persistent-homology features with clearly specified filtrations—would better establish the benefits of the learned dictionary.

  3. The paper claims competitive performance against GNNs and graph transformers, but the TU benchmark comparison in Table 2(a) includes a limited selection of recent baselines. Comparisons with additional graph transformers applicable to graph classification, such as GraphGPS, SGFormer etc, would provide stronger evidence for this claim and better contextualize the proposed framework’s performance.

minor issues

  1. The term “atom” in Figure 1 may be confused with a molecular atom. Labeling it “dictionary atom” or “structural dictionary component” would improve clarity and emphasize the framework’s applicability to general graphs.

  2. The authors state that the implementation code will be made available during the review process, but no anonymous repository link is provided in the paper.

Questions for authors

Please refer to the weakness.

7 comments
AuthorsOpenReview ↗

Topology–Attribute Fusion and New Explicit-Feature Comparisons

We thank the reviewer for recognizing the information-source audits and structural tracing. We clarify the fusion mechanisms and report new controls.

1. Contribution of the shared-dictionary framework

Our contribution develops sparse network decomposition into a general-purpose, explicit graph representation framework. Rooted observations are encoded in shared, learnable coordinates, aggregated through invariant readouts, and integrated with attributes. Links to activating patch occurrences enable information-source auditing, structural tracing, and targeted interventions.

Building on existing sparse decomposition, the dictionary provides a finite, data-dependent vocabulary for expressing local observations through combinations of shared components. K-SVD implements dictionary learning; the controls below assess the construction's predictive utility.

2. Topology–attribute fusion and the ENZYMES results

Separate accessibility is compatible with topology–attribute interactions. Our framework supports both concatenation and explicit binding. Concatenation supplies independently constructed blocks to a nonlinear downstream predictor. Binding additionally associates dictionary activations with attributes of their corresponding roots, structural shells, or local contexts, preserving information about which semantic features accompany a structural component.

In the manuscript's NCI1 audit, adding binding to STASTA improves accuracy by 4.13 percentage points.

ENZYMES exhibits a different regime. Under our audit protocol, AA, SASA, and STASTA achieve 68.07%, 69.73%, and 64.12%, respectively. Attributes are strongly predictive, while the evaluated topology block provides limited complementary utility once statistics and attributes are available. This is consistent with Errica et al. [1], who found that none of their evaluated GNNs exceeded a structure-agnostic baseline on ENZYMES, PROTEINS, or D&D, whereas NCI1 benefited from graph-aware models. Our independent blocks further quantify standalone and conditional utility within a common representation protocol.

We also agree that task-adaptive integration deserves further investigation. Our current implementation uses concatenation and predefined binding operators while learning the dictionary independently of the downstream objective. This leaves room for richer interactions between topology and semantics. Jointly learning structural coordinates and their attribute-conditioned interactions is an important future direction, while preserving the separate accessibility and occurrence-level traceability that enable the audits.

The present experiments do not determine how much additional structural utility such joint optimization could recover on ENZYMES. We will clarify this boundary alongside the observed attribute-dominated regime.

3. Added graphlet, persistent-homology, and direct-patch controls

We evaluated graphlet counts, persistent-homology features, and direct rooted-patch descriptors that bypass dictionary reconstruction on NCI1, MolHIV, and Peptides-func.

The graphlet baseline contains exact counts and within-order frequencies of all connected induced unlabeled graphlets with three to five vertices. The persistent-homology baseline uses lower- and upper-star filtrations of node degree and local clustering coefficient on the graph as a one-dimensional simplicial complex, with triangles unfilled. We vectorize finite H0H_0 birth–death pairs and essential H0/H1H_0/H_1 births using fixed histograms.

All rows below append the same dataset-specific statistics and attribute summaries and use the same splits and downstream XGBoost evaluation protocol.

RepresentationNCI1 Accuracy (%)MolHIV ROC–AUC (%)Peptides-func macro AP (%)
Direct pooled patch descriptors79.6877.2666.97
Dictionary-reconstructed patch descriptors80.8880.1767.63
Graphlet counts75.0173.3364.45
Persistent homology74.0172.9264.27

NCI1 uses split seed 0 with ten outer folds and equal eight-candidate validation searches. MolHIV uses the official scaffold split and classifier seeds 0–9. Peptides-func uses the official split and classifier seed 0. The latter two use shared fixed predictor settings.

The direct and reconstructed patch controls additionally share identical patch inputs, descriptor rules, pooling operations, and dimensions. Reconstruction improves test performance by 1.19, 2.91, and 0.66 percentage points, respectively. The graphlet and persistent-homology comparisons establish advantages over these specified alternative representations under the evaluated protocols. These comparisons use the descriptor-matched configuration, distinct from the full configurations with additional binding features.

[1] Errica et al., ICLR 2020. https://arxiv.org/abs/1912.09893

AuthorsOpenReview ↗

Additional GraphGPS Comparisons on TU Benchmarks

4. Broader Graph Transformer coverage

Following the reviewer's suggestion, we have completed additional GraphGPS evaluations on five TU datasets, covering both attributed and topology-only graphs. Our reproduction uses PyG GPSConv with local GIN/GINE layers, global attention, and random-walk structural encodings.

We follow the manuscript's nested ten-fold splitting and validation/refit procedure with split seed 0. Within each outer fold, eight configurations cover hidden dimensions {64, 128}, depths {3, 5}, and learning rates {0.001, 0.003}. Each candidate is trained for 100 epochs. Configuration and training duration are selected using inner validation, followed by refitting on the outer training partition.

For reference, we include our manuscript's reported mean accuracies alongside the additional GraphGPS results.

DatasetGraphGPS, our reproduction (%)Ours, manuscript (%)
MUTAG83.54 ± 7.1989.20
NCI178.59 ± 0.9683.09
PROTEINS74.58 ± 3.6877.85
IMDB-BINARY66.20 ± 5.6573.87
IMDB-MULTI44.87 ± 4.4350.97

GraphGPS values are means and population standard deviations across ten outer folds for split seed 0. Our manuscript values average ten seed-level ten-fold means, except MUTAG, which uses seed 0 with ten folds. The columns therefore differ in the number of split repetitions; our manuscript means are included to contextualize the new baseline results.

These completed experiments broaden the Graph Transformer comparison across both benchmark groups. We will complete the comparison on the remaining TU datasets used in the manuscript—D&D, ENZYMES, COLLAB, and REDDIT-BINARY—and include the complete results and reproduction configurations in the revised manuscript.

5. Terminology and anonymous implementation

We will replace "atom" in Figure 1 with "dictionary atom" to distinguish learned dictionary components from molecular atoms and clarify their applicability to general graphs.

We are organizing the code and supplementary experiments and will release an anonymized repository within the next few days.

AuthorsOpenReview ↗

Follow-up on Topology–Attribute Fusion and GraphGPS

Thank you again for your suggestions on fusion and the TU comparisons. Our response on fusion clarifies what the ENZYMES audit shows under our protocol and where the current fusion mechanism could be extended. We also posted completed GraphGPS comparisons on five TU datasets, alongside our manuscript results. If there is a specific concern about the fusion mechanism or the benchmark comparison that remains open, we would be happy to clarify it.

Reviewer_BnwkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces an explicit, patch-based feature extraction framework for graph learning. The main idea is to extract small node- and edge-rooted induced subgraphs (radius 1–2), canonicalize them, and sparse-code them against a learned dictionary to build a compact topological vector. This descriptor is then combined with standard graph statistics and attribute summaries to train an XGBoost model. On the theory side, the authors show that this rooted-patch profile refines rr rounds of 1-WL, separates C6C_6 from 2C32C_3, and is incomparable to 2-FWL in the pair-rooted setting.

Critical strengths
  1. The exact-vs-compressed comparison on BREC is useful and carefully designed. Very clean ablation. It nicely isolates receptive-field limits (the CFI pairs) from compression loss (≤2\le 2 pairs lost at K=128K=128), and the Gaussian baseline proves the dictionary is actually doing real work. The theory is also refreshingly careful about what survives compression.
  2. The information-source audits and molecular case studies are interesting. The paper also provides fairly detailed experimental documentation.
Critical weaknesses
  1. The difference from existing methods is small and the pipeline is mostly a combination of existing modules. Zhai et al. (2020) already used ego-network decomposition, K-SVD, and sparse codes for network analysis. Related graph dictionary learning methods also exist (e.g., Liyanage et al., 2023). Most of the theory in Section 4 consists of known results.

[1] X. Zhai, W. Zhou, G. Fei, C. Lu, and G. Hu. "Network sparse representation: Decomposition, dimensionality-reduction and reconstruction." Information Sciences, 521:307–325, 2020.

[2] K. Liyanage, R. Pearsall, C. Izurieta, and B. M. Whitaker. "Dictionary Learning on Graph Data with Weisfieler-Lehman Sub-Tree Kernel and KSVD." IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1–5, 2023.

  1. The motivation is broad and not backed by experiments. The paper also sidesteps WL, NSPDK and ECFP, which are already explicit and traceable representations. It emphasizes explicit and interpretable structural representations, but Eq. (2) only minimizes reconstruction error. It does not ensure that learned atoms have consistent structural meanings. Also, the expressiveness results concern exact patch profiles, not necessarily the learned representation. More importantly, the paper does not show what this approach offers over existing explicit features such as WL subtrees, graphlets, or molecular fingerprints.

  2. The experiments do not clearly establish the benefit of the proposed method. Several headline results do not even use the learned topology block T (PROTEINS, ENZYMES, MolBACE, and Brazil). Direct comparisons with exact patch histograms, ECFP, and simpler compression methods are missing. For the molecular tasks, this is the most natural explicit and traceable competitor. Also missing are a structure-agnostic baseline, GDL/TFGW, and ZINC. The node-level evaluation covers only three small airport graphs.

Questions for authors
  1. Could you clarify the main novelty over Zhai et al. (2020) and related dictionary learning methods? What is the key component that cannot be replaced by existing techniques?
  2. Could you compare against exact patch histograms/WL features and ECFP with the same XGBoost predictor? Comparisons with PCA or random dictionaries would also help isolate the contribution of K-SVD.
  3. How were the final feature configurations selected? Please provide validation results for the candidate views and clarify the selection across the two panels of MolHIV Table 15. Could you also quantify the interpretability and stability of the learned atoms?
3 comments
AuthorsOpenReview ↗

What Does Our Framework Add Beyond Existing Explicit Features?

We thank the reviewer for recognizing the BREC analysis, information-source audits, and molecular case studies. This first response clarifies the contribution and reports the requested representation controls. Our second response addresses selection, interpretability, stability, and evaluation scope.

1. What the framework adds to prior dictionary learning

Our contribution develops sparse network decomposition into a general-purpose, explicit graph representation framework for downstream learning. Local observations are expressed in shared, learnable coordinates, integrated with attributes, and linked to their original occurrences.

We explicitly build on Zhai et al. (2020), including their use of ego-network decomposition and classification. Our extensions include canonical node-/pair-rooted induced observations at configurable radii, invariant aggregation into node-/graph-level representations, separately accessible information blocks, and occurrence-level tracing and intervention.

Liyanage et al. (2023) learn dictionaries over whole-graph WL count vectors. Our dictionary acts on individual connectivity patches before aggregation, preserving links between learned activations and specific occurrences. This difference determines the information being compressed and the level at which it can be inspected. See their methodology: https://www.cs.montana.edu/pearsall/files/dictionary_learning.pdf

K-SVD implements the learning step. Replacing it is compatible with the framework if shared coordinates and occurrence links are preserved. The contribution concerns the representation construction and the analyses it enables.

2. Exact profiles, learned coordinates, and theory

The exact profile characterizes structural information at a chosen observation scope. The dictionary maps observations into a finite shared basis, including previously unseen patches within the supported input domain. Its role differs from assigning a distinct coordinate to each exact patch type.

We will distinguish standard invariance arguments from our construction-specific characterization: equal-depth 1-WL refinement, radius-one separation of some stable-1-WL counterexamples, and incomparability of the radius-two adjacent-pair profile with the pair-based refinement defined in our analysis. These characterize exact profiles. Preservation after compression requires conditions on both encoding and readout.

BREC directly measures retention: the exact profile separates 300/400 pairs; learned dictionaries retain 300/298/299 across three seeds. Identical profiles for the remaining CFI pairs identify information absent at this observation scope.

3. New explicit-feature and compression comparisons

We evaluated exact histograms, WL, Morgan/ECFP, random dictionaries, PCA, and direct-patch descriptors with XGBoost. Full-configuration test scores (%) are:

RepresentationNCI1 Acc.MolHIV AUCPeptides AP
Learned framework82.9981.3471.38
Exact histogram + binding82.5377.9871.32
Cached-order histogram + binding83.8777.7771.47
WL + statistics/attributes83.1476.6471.31
Morgan/ECFP + statistics/attributes81.9276.9470.31
Random dictionary framework83.1678.9770.42

NCI1 uses seed-0 ten-fold nested CV with equal eight-candidate validation searches. MolHIV uses the official scaffold split and classifier seeds 0–9; Peptides-func uses its official split and classifier seed 0. The latter two use shared fixed predictor settings.

WL uses attributed, edge-aware counts over rounds 0–2 and a training-fitted vocabulary. ECFP4 uses 2,048 binary bits; the NCI1 Morgan control uses supplied node categories. Histogram controls replace dictionary coordinates and binding with type counts and type-conditioned binding. Histogram vocabularies are training-fitted. All rows retain the corresponding statistics/attribute summaries. WL/ECFP and dictionary configurations retain their respective feature constructions.

To isolate reconstruction, we also compared original, PCA-reconstructed, and K-SVD-reconstructed patches with identical descriptor rules, pooling, dimensions, and appended statistics/attributes:

Descriptor sourceNCI1 Acc.MolHIV AUCPeptides AP
Original patches79.6877.2666.97
PCA reconstruction81.8079.8564.54
K-SVD reconstruction80.8880.1767.63

This second table uses the separate descriptor-matched configuration. K-SVD improves over direct aggregation on all three datasets, while PCA is stronger on NCI1. The full framework is comparable to strong explicit baselines on NCI1/Peptides and performs better on MolHIV under these protocols. These results establish dataset-dependent utility; cross-dataset transfer of a frozen dictionary has not been tested.

AuthorsOpenReview ↗

Feature Selection and the Stability of Our Molecular Analyses

4. Configurations without the topology block and the attribute baseline

The framework permits independently constructing and removing statistics (SS), topology (TT), and attributes (AA). The audit retrains a common downstream predictor for every coalition, measuring standalone and conditional predictive utility. The AA-only coalition provides an attribute-summary baseline; SASA additionally contains graph statistics.

On ENZYMES, A/SA/STAA/SA/STA achieve 68.07/69.73/64.12%. Attributes dominate, and the evaluated topology block offers little complementary utility once statistics and attributes are present. On NCI1, TT is the strongest isolated source, and binding further improves STASTA by 4.13 percentage points in the manuscript's audit.

This dataset dependence agrees with Errica et al. (2020), who found that none of their evaluated GNNs exceeded the structure-agnostic baseline on ENZYMES, PROTEINS, or D&D, while NCI1 benefited from graph-aware models. Our block-level audit additionally measures standalone and conditional contributions within a common representation protocol. https://arxiv.org/abs/1912.09893

Headline results evaluate validation-selected framework configurations, some of which omit dictionary features. Their scores establish performance of those configurations. The matched controls in our first response evaluate dictionary contribution. We will clarify these distinct experimental purposes.

5. Candidate validation scores and MolHIV Table 15

The historical candidate-view validation ROC-AUC means (%) are:

Panel / candidateDimensionValidation
A: Composition6976.61
A: Reconstructed typed patches62479.66
A: Context32578.75
A: Composition + context39480.45
A: Base: composition + typed patches69382.09
A: Typed patches + context94981.72
A: Full reported view1,01883.41
B: Base + mass coupling3,76583.89
B: Base + root coupling3,76583.13
B: Base + mass/root coupling6,83783.91

Panel B extends the 693-D base with additional coupling operators. Its experiment record identifies the 6,837-D configuration as validation-best. We agree that the 1,018-D configuration is not the highest-validation entry across both panels. We will clarify the candidate families and correct the selection wording. The validation-best listed model scores 83.91/79.23 on validation/test; the reported 1,018-D model scores 83.41/81.47. The supplementary 81.34 result is a fresh evaluation under the shared control settings.

6. What interpretability means and how we tested stability

Reconstruction loss alone does not guarantee that each dictionary atom is a uniquely identifiable chemical motif. Interpretation is grounded in the actual patches activating a coordinate, their recognizable structural families, their statistical associations, and interventions on their activations.

We therefore evaluate stability through occurrence-based alignment. Components from additional dictionary seeds are matched to the reference using validation activation-support overlap without task labels; the match is then held fixed for test evaluation.

For MolBACE, we evaluated dictionary seeds 0–4 and ten classifier seeds per dictionary. Across the four additional dictionaries, test activation-support Jaccard ranges from 0.49 to 0.79. The matched component retains negative training/validation and positive test label associations. We then remove its patch activations and recompute the readout while keeping each fitted predictor fixed. Mean ROC-AUC changes across the ten classifiers are:

Dictionary seedValidation change (pp)Test change (pp)
0-0.875+0.402
1-0.388+0.414
2-1.718+0.282
3-0.088+0.115
4-2.216+0.746

All five dictionary-level means preserve the diagnostic direction, with variation across individual classifier runs. This supports reproducibility of this diagnosed dependency.

For MolHIV, validation-based occurrence matching across four additional dictionary seeds recovers all 383 reference-activated test occurrences in the aryl–N parent family. Overall test support Jaccard ranges from 0.327 to 0.879, indicating variable selectivity. This measures parent-family recovery; it does not constitute a repetition of the full aryl–azo/sulfonate hypothesis test. We will report these limitations.

AuthorsOpenReview ↗

Follow-up on Explicit Baselines and Coordinate Stability

Thank you again for raising the comparison with existing explicit features. Our additional results include exact patch histograms, WL features, fingerprints, and PCA. We also report how the traced molecular patterns and the MolBACE intervention behave across dictionary seeds. We would appreciate your perspective on whether these results clarify what the framework adds, and whether any concern remains that we can address during the discussion.

Reviewer_5RKWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work present an interesting method that represent graphs with rooted patches, a shared sparse dictionary, and pooled features, such that graph statistics, topology, and attributes are kept separately accessible, and feature activations can be traced back to actual subgraphs. The paper studies expressiveness and prediction across several benchmarks, then uses information-source audits and retrospective molecular case studies to examine what the representations capture.

Critical strengths
  1. The BREC study separates what the local observations miss from what compression loses. A 128-atom dictionary retains 299 of the 300 available distinctions on average, with relabeling checks supporting the result

  2. The complete information-source audits and tracing examples are useful. They connect predictions to actual subgraph occurrences and show both helpful structural signals and cases where those signals fail to transfer

Critical weaknesses
  1. It's unclear how much learned sparse coding adds over simpler explicit features. The downstream study lacks a matched raw-patch or unlearned-dictionary control, and some headline configurations don't use the dictionary (Table 9)

  2. Table 15 reports the model with validation AUC 83.41 on MolHIV, while another panel contains a model with 83.91.

  3. I think this work could benefit from a matched downstream comparison that changes only the dictionary learning, keeping the patch inputs, other features, and predictor fixed.

Questions for authors

How are the 624 reconstructed patch coordinates and 325 context features in Table 15 computed? It's unclear which parts depend on the learned dictionary.

3 comments
AuthorsOpenReview ↗

What Does the Dictionary Add? New Controls and MolHIV Clarifications

We thank the reviewer for recognizing the exact-versus-compressed BREC analysis and the information-source audits and tracing examples. We have completed additional downstream controls to isolate the effects of dictionary learning and reconstruction. We also clarify the interpretation of Table 9, the MolHIV configurations in Table 15, and the construction of its dictionary-dependent features.

1. Added value over direct explicit representations and unlearned dictionaries — Weaknesses 1 and 3

Our central contribution is to develop sparse network decomposition into an explicit graph representation framework for downstream learning. The framework organizes local structural observations into shared, learnable coordinates across graphs, integrates them with attributes, and retains their links to actual subgraph occurrences. K-SVD provides a concrete implementation of the dictionary-learning step within this framework. The reviewer's question therefore motivates evaluating both the utility of this representation construction and the specific contribution of learning the dictionary. We address these through two complementary controls.

Direct patch descriptors versus dictionary reconstruction. Both arms use identical rooted-patch inputs, descriptor construction, pooling operations, and feature dimensions. The direct arm aggregates descriptors obtained from the original patches, while the reconstruction arm aggregates descriptors obtained after sparse reconstruction.

DatasetDirect patch representation (%)Dictionary-reconstructed representation (%)Difference (pp)
NCI1 — Accuracy79.6880.88+1.19
MolHIV — ROC–AUC77.2680.17+2.91
Peptides-func — macro AP66.9767.63+0.66

These results show that the predictive gains in these configurations extend beyond directly pooling the available patch descriptors. They are consistent with a shared reconstruction constraint helping retain task-relevant patterns across observations.

Learned versus fixed random dictionaries. We additionally replaced the learned dictionary with a column-normalized Gaussian dictionary, retaining the patch inputs, dictionary size, sparsity, scaling, readout definitions, other features, and downstream predictor settings. All dictionary-derived features, including binding and context activations, were recomputed using the corresponding dictionary.

Dataset and configurationRandom dictionary (%)Learned dictionary (%)Difference (pp)
NCI1 — structural view77.2879.20+1.92
NCI1 — full STABSTAB83.0482.99−0.05
Peptides-func — structural view60.6764.79+4.12
Peptides-func — full configuration70.4271.38+0.96
MolHIV — full 1,018-dimensional configuration78.9781.34+2.37

Metrics and evaluation repetitions follow the dataset-specific protocols described above. For NCI1, this table holds predictor hyperparameters fixed at those selected by learned-arm inner validation. With independent, equal-budget validation searches, random-dictionary accuracy becomes 77.81% for the structural view and 83.16% for STABSTAB, leaving the qualitative conclusion unchanged.

The learned dictionary improves the evaluated structural-only views and the full Peptides-func and MolHIV configurations. Full NCI1 performance is comparable between learned and random dictionaries. Each comparison uses one learned dictionary realization and one Gaussian draw, with the folds or classifier seeds described above.

2. Interpretation of configurations without dictionary features in Table 9 — Weakness 1

Table 9 documents validation-selected predictive configurations within a framework that permits independently removing information blocks. Some selected configurations consequently omit dictionary-derived features. These entries establish the predictive performance of the selected framework configurations. The matched controls above directly evaluate the contribution of dictionary learning and reconstruction.

The information-source audit examines which sources support prediction on each dataset. Its dataset-dependent findings are consistent with Errica et al. [1], who found that none of their evaluated GNNs surpassed the structure-agnostic baseline on ENZYMES, PROTEINS, or D&D, while NCI1 benefited substantially from graph-aware models.

Our independently removable blocks further quantify standalone and conditional predictive utility under a common audit protocol. On ENZYMES, AA, SASA, and STASTA achieve 68.07%, 69.73%, and 64.12%, respectively. Thus, attributes dominate prediction, and the evaluated topology block provides limited complementary utility once statistics and attributes are available. On NCI1, topology is the strongest isolated source in the audit, and explicit topology–attribute binding provides additional predictive benefit.

AuthorsOpenReview ↗

Supplement of another question

3. MolHIV validation AUC of 83.41 versus 83.91 in Table 15 — Weakness 2

We checked the experiment records. The two values correspond to different feature configurations.

ConfigurationDimensionValidation ROC–AUC (%)Test ROC–AUC (%)
Reported predictive view in Panel A1,01883.4181.47
Mass + root coupling configuration in Panel B6,83783.9179.23

Panel A presents the predictive-view ablation, while Panel B examines additional coupling configurations built upon the 693-dimensional base representation. The experiment record explicitly identifies the 6,837-dimensional configuration as the validation-best candidate within the coupling study.

The reviewer is correct that 83.41 is not the highest validation AUC among all configurations listed across both panels. We will revise the caption and model-selection description to state the candidate families explicitly and identify the 83.91/79.23 configuration as the validation-best entry across the listed configurations. The 1,018-dimensional view will be described as the reported predictive configuration, with its construction and ablations documented accordingly.

The new matched dictionary comparison reports 81.34% for a fresh evaluation of the 1,018-dimensional learned-dictionary configuration under the shared control settings. We will distinguish this supplementary result from the historical Table 15 result.

4. Construction of the 624 reconstructed coordinates and 325 context features — Question for Authors

The full MolHIV configuration contains 69 composition features, 624 reconstructed typed-patch features, and 325 context features.

The 624-dimensional block. For each rooted patch, sparse coding and reconstruction produce x^v=Dαv\hat{x}_v=D\alpha_v, expressed in the original feature scale. A fixed decoder converts this reconstruction into a 208-dimensional descriptor containing:

  • Three 48-dimensional atom-feature blocks for the root and the mean features of the first and second shells.
  • Four 13-dimensional bond-feature blocks for root–first-shell, within-first-shell, first–second-shell, and within-second-shell connections.
  • Twelve structural and shell-size summaries.

Thus, 3×48+4×13+12=2083\times48+4\times13+12=208. Coordinate-wise mean, standard deviation, and maximum across patch occurrences yield 3×208=6243\times208=624 graph-level features.

The decoder uses the original valid-node mask and shell assignments as layout metadata. Reconstructed connectivity, atom values, and bond values depend on the dictionary, while layout-derived quantities remain fixed. The direct-patch control applies the same decoder and pooling to the original patch values.

The 325-dimensional block. We retain five contexts: ring5, ring6, aromatic_ring, multi_ring, and ring_boundary. For context cc and dictionary component kk, the feature is

mc,k(G)=1∣V(G)∣∑v∈V(G)1[v∈c],∣αv,k∣∥αv∥1+ε.m_{c,k}(G)=\frac{1}{|V(G)|}\sum_{v\in V(G)}\mathbf{1}[v\in c]\\,\frac{|\alpha_{v,k}|}{\lVert\alpha_v\rVert_1+\varepsilon}.

Each context contributes 64 activation-mass coordinates and one coverage value, giving 5×(64+1)=3255\times(64+1)=325. The context masks and coverage values are computed from the original molecular graph. The 320 activation-mass coordinates depend on dictionary-derived sparse codes.

Accordingly, the random-dictionary control recomputes both the reconstructed typed-patch block and the dictionary-conditioned context activations, while retaining the same composition features, context definitions, and coverage values. We will include these definitions and dependency distinctions in the revised appendix.

Reference

[1] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A Fair Comparison of Graph Neural Networks for Graph Classification. ICLR 2020. https://arxiv.org/abs/1912.09893

AuthorsOpenReview ↗

Follow-up on the Matched Dictionary Controls

Thank you again for suggesting the matched downstream comparison. Our response includes both a learned-versus-fixed dictionary comparison and a direct-versus-reconstructed patch comparison. It also clarifies the MolHIV feature blocks and the two validation scores in Table 15. If you have a chance before the discussion closes, we would appreciate hearing whether these additions address your main concern about what dictionary learning contributes.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Rebuttal Updates

Dear Area Chair, With the discussion period nearing its end, we wanted to point you to three updates in our responses: matched controls for the learned dictionary, comparisons with existing explicit features and checks of molecular case stability, and additional GraphGPS results and clarifications on topology–attribute fusion. We would appreciate your help inviting feedback on any remaining concerns while there is still time for us to clarify them. Thank you for your time.

AuthorsOpenReview ↗

Rebuttal Summary: What Explicit Structural Coordinates Enable and What Dictionary Learning Adds

Dear Area Chair,

Our paper asks whether graph topology can be learned explicitly and support competitive prediction while keeping the underlying structural evidence accessible. We build on sparse network decomposition to learn a shared structural vocabulary from rooted graph patches. Patches from different graphs are encoded in the same coordinates, and each activation remains linked to the patch that produced it. This lets us use conventional classifiers for prediction, measure what topology contributes alongside attributes, and trace a model’s reliance on a structural pattern back to specific occurrences. We summarize below the evidence most relevant to the questions raised across the reviews.

What does learning the dictionary add? During rebuttal, we compared learned and fixed Gaussian dictionaries while holding the patch inputs, feature construction, data splits, and predictor settings fixed. On MolHIV, learning the dictionary raised mean test ROC–AUC from 78.97% to 81.34% in the full configuration across ten paired classifier seeds. On Peptides-func, it raised test macro-AP from 60.67% to 64.79% in the structural view and from 70.42% to 71.38% in the full configuration. On NCI1, topology-only accuracy increased from 77.28% to 79.20%, while the full configurations were essentially tied (83.04% fixed, 82.99% learned). The gain from learning the vocabulary therefore depends on the dataset and on which other inputs are available. We also clarify one comparison from the discussion: on MolHIV, learned topology alone achieved 73.27% test ROC–AUC and persistent homology alone achieved 64.29%. The 72.92% result combined persistent homology with 69 molecular composition features.

What do the explicit coordinates let us inspect? On BREC, we can identify where structural distinctions are lost. The 100 unresolved CFI pairs already have identical multisets of exact radius-two adjacent-pair-rooted patches, before any dictionary compression. Of the 300 pairs distinguishable at that scope, the compact dictionary retained 299 on average across three dictionary seeds. On MolBACE, we could examine a fitted predictor at the level of individual occurrences. We traced one coordinate to an aryl-like local environment, removed only its corresponding patch activations, and recomputed the predictions with the model held fixed. Validation ROC–AUC fell and test ROC–AUC rose across all ten classifier seeds. This identified a specific structural pattern that helped validation ranking but impaired test ranking.

What does the information-source audit measure? Reviewers 1 and 3 raised related questions about attributing predictive performance to topology. The main prediction table reports validation-selected configurations. Section 5.4 measures the standalone and conditional predictive utility of the blocks themselves. Zheng et al. (2024) study how label, structural, and feature homophily relate to GNN performance. Our audit asks which inputs support prediction on a given task: we retrain the same downstream learner on all eight combinations of graph statistics, learned topology, and attributes under identical splits. On ENZYMES, statistics and attributes yield 69.73% accuracy, which falls to 64.12% when learned topology is added. The audit thus makes the attribution explicit: the selected configuration achieves its reported accuracy using statistics and attributes, and the learned topology block provides no additional predictive gain in that comparison.

We thank the reviewers for prompting these controls and clarifications, and the Area Chair for considering them alongside the original submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.