- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper examines graph invariants as structural descriptors for graph learning benchmarks. It combines invariants with XGBoost and compares them against summed and linearly aggregated node features on 26 datasets. The paper also runs BREC distinguishability experiments and dataset-membership prediction, including comparisons matched on basic graph statistics. The authors propose these inexpensive baselines as a way to study structural information and to test whether more complex graph models actually bring benefits.
Critical strengths
- The baseline is practical and broadly evaluated. Comparing eight input configurations on 26 datasets gives a useful reference point for asking whether complex graph models really improve over cheap alternatives. The runtime measurements and detailed experimental settings make this contribution practically useful.
- The structural heterogeneity analysis has a meaningful control. Matching node count, edge count, and the second degree moment makes the evidence stronger that some molecular datasets remain structurally distinguishable beyond these basic statistics. This makes the dataset-membership experiments more informative than an uncontrolled comparison of graph collections.
Critical weaknesses
- The diagnostic conclusions are stronger than the tested representations can support. Recommendation R3 on page 9 treats the lack of improvement from invariants as evidence that structure likely plays only a marginal role. I do not think that follows. A finite descriptor set plus one predictor failing to improve does not establish structural irrelevance; the target may depend on interactions between topology and node-feature placement that these representations discard. Likewise, matching BREC distinguishability does not mean the representations have equal expressive power on downstream distributions. This matters because diagnosing structural relevance is one of the paper’s main motivations.
- The statistical comparisons do not establish performance equivalence. The main text says the method is “statistically on a par” with more complex models, but Appendix D.3 acknowledges that the relevant MCB analyses involve only two to four datasets and have limited power. The LRGB comparison is explicitly described as descriptive. Not detecting a significant difference is not the same as showing equivalence. The TU analysis also excludes methods with incomplete results, which further limits the comparison. The current wording overstates the evidence for parity with strong graph models.
Questions for authors
- What assumptions would justify reading “no improvement from the selected invariants” as evidence that graph structure itself is only marginally relevant? Is R3 meant as a diagnostic of the tested representations, or as a broader claim about the prediction task?
- If the statistical-parity claim is kept, what practical equivalence criterion and analysis support it? If not, can the conclusion be limited to dataset-specific competitiveness and to the methods actually included in the statistical tests?
- Does the compact four-invariant subset contain mean commute time, as stated in Section 3.1 and Table S.7, or normalized von Neumann entropy, as shown in Figure 1? Which definition was used for the reported BREC and downstream results?
2 comments
The authors have addressed all my concerns. I have increased the score to “3. Weak acceptance”.
We thank the reviewer for their assessment. As a token of respect for their time, we provide concise & brief answers. We are happy to expand and add more details if the reviewer is interested.
We thank the reviewer for the careful reading, the conclusion R3 was framed too broadly; we have rectified this in our revision and rephrased R3 as: "If neither aggregated features nor invariants provide a gain over summed features, structure captured by these representations only plays a marginal role. If, in addition, trained graph models do not exceed this baseline (R2), we consider the dataset to be of limited use for benchmarking graph learning."
As additional information for the reviewer: R3 refers to the tested configurations and their combinations in Tables S.14/S.16. It should not only refer to invariants, but also to structure captured by the "agg" configuration (linearized GIN). Only if neither show a gain over the structure agnostic "sum", R3 should apply. This is quantified by overlapping confidence intervals of configurations for "BACE" and "Proteins". Further, S.16 also shows cases where Local structure suffices (BBBP, PCQM4Mv2, Flow), here "agg+I" ≈ "agg" > "sum". But this only points towards low relevance of global structure.
It becomes a statement about the relevance of structure for a task together with (R2), i.e., when trained graph models also fail to beat the baseline. Our comparison with the literature points towards this for "BACE" in table S.19, where only "Gem" and "Uni-Mol" outperform our baseline, both using information beyond the 2D graph. We observe this also for "Proteins", as shown in table S.19. This agrees with an earlier finding of Errica et al., where a baseline of sum-pooled node features followed by an MLP outperforms GNNs on "Proteins" (first entry in table S.18).
We understand that the reviewer is concerned about the generalizability from BREC performance to downstream tasks. We ran the following experiment to assess to what extent this is an issue:
We believe that this establishes generalizability and hope that this alleviates the concerns by the reviewer.
Would the reviewer also be interested in preliminary results on data from the House of Graphs database, where we believe that invariants are also capable of distinguishing non-isomorphic graphs?
We agree that the probative value of the statistical tests is limited. We therefore changed the wording in our revision to "are not significantly worse than the compared transformer, message-passing, and graph-kernel baselines on a sample of datasets from the TU, MoleculeNet, and LRGB benchmarks". This is in line with the wording in the appendix.
Furthermore, we also added more comparison partners to Table S.18 (TU), and another dataset to Table S.18 and Table S.19 (MoleculeNet) to improve the value of the MCB analysis.
We thank the reviewer for catching this inconsistency. Table S.7 is correct; indeed, normalised von Neumann entropy is not part of "S" (the expressive subset of invariants). All further experiments after Section 3.1 refer to the respective invariants sets in Table S.7. Unfortunately, Figure 1 has an error because it was manually generated; we have replaced it and removed the erroneous invariant in our revision. None of our statements change due to this replacement.
We sincerely thank the reviewer for their insightful review, which helped us improve the presentation of this paper. We hope to have addressed the reviewer's concerns and are available for any other comments.