acceptodds
Under review as a conference paper at ICLR 2027

Measuring Structure in Graph Benchmark Datasets Using Graph Invariants

Abstract

Progress in graph learning is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from the graph, or whether it even needs to. We propose measuring this using graph invariants, i.e., permutation-invariant, task- agnostic structural descriptors. Our analysis on 26 datasets substantiates three tacit assumptions in graph learning, namely that (i) a curated subset of invariants is more expressive than standard GNNs, (ii) benchmark datasets exhibit structural heterogeneity even when originating from the same domain, and (iii) simple models are often competitive with, and sometimes exceed, approaches based on transformers or message passing. We thus posit that graph invariants should become a standard tool for measuring graph learning task complexity and the relevance of graph structure.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Baseline, Graph datasets, Invariants, Benchmark quality, Graph-level tasks, Expressivity, Generalization, Evaluation practices, Structural bias

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_kXg3OpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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?
  2. 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?
  3. 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

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.

kXg3: The diagnostic conclusions are stronger than the tested representations can support... treats the lack of improvement from invariants as evidence that structure likely plays only a marginal role ... the target may depend on interactions between topology and node-feature placement... Is R3 meant as a diagnostic of the tested representations, or as a broader claim about the prediction task?

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).

kXg3: Likewise, matching BREC distinguishability does not mean the representations have equal expressive power on downstream distributions.

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:

  1. For each of the 26 datasets, we took all graphs that cannot be WL-distinguished.
  2. We calculated all subsets of invariants mentioned in the paper.
  3. Our finding: Regardless of which invariant subset to be used, invariants are capable of distinguishing all such graphs.

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?

kXg3: The statistical comparisons do not establish performance equivalence. The main text says the method is “statistically on a par” with more complex models... The current wording overstates the evidence... can the conclusion be limited to dataset-specific competitiveness and to the methods actually included in the statistical tests?

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.

kXg3: 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?

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.

The authors have addressed all my concerns. I have increased the score to “3. Weak acceptance”.

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

This paper investigates whether graph invariants can provide a simple, interpretable, and task-agnostic approach to characterizing structural information in graph benchmark datasets and evaluating the necessity of complex graph learning architectures. The authors construct graph-level fingerprints from a diverse collection of permutation-invariant structural descriptors and use XGBoost to assess their expressive and predictive capabilities across 26 datasets. The study addresses three questions: whether graph invariants distinguish non-isomorphic graphs beyond the capabilities of common GNNs, whether they reveal structural heterogeneity within and across benchmark domains, and whether they capture structural information relevant to downstream prediction. Experiments on BREC demonstrate that a small subset of invariants achieves strong graph-distinguishing performance, while dataset meta-classification reveals structural differences even after matching basic graph statistics. Predictive experiments further show that combining graph invariants with aggregated node and edge features can yield competitive results against established graph learning models on multiple benchmarks. The authors advocate incorporating invariant-based baselines into graph learning evaluations to better understand dataset characteristics, task complexity, and model-task alignment.

Critical strengths
  1. Useful framework for evaluating graph benchmarks. The main contribution of the paper is not a new graph invariant or learning architecture, but rather the systematic combination of different graph invariants into a unified diagnostic framework. I think bringing together graph theory, structural characterization, expressivity assessment, and conventional supervised learning provides a useful perspective on understanding and evaluating graph benchmark datasets.

  2. Extensive empirical evaluation across diverse datasets. The paper provides a comprehensive evaluation covering 26 graph datasets from different domains. The authors examine several families of graph invariants, consider both full and computationally efficient invariant sets, and evaluate different feature configurations. I particularly appreciate the BREC analysis, which shows that combining structurally diverse invariants can distinguish many graph pairs that are challenging for message-passing architectures.

  3. Clear motivation and well-organized presentation. The paper clearly explains its motivation and introduces three research questions that guide the experimental analysis. The distinction between structural invariants, simple feature aggregation, and their combined representations makes the objectives of the experiments easy to follow. Tables 1-2 and Figures 2-4 provide useful and complementary insights into expressivity, structural heterogeneity, and predictive performance. The appendix also provides mathematical definitions, dataset descriptions, computational costs, and additional experimental results, which help support the main discussion.

Critical weaknesses
  1. BREC-specific invariant selection limits generalizability. In Section 3.1, the expressive subset is greedily selected based on its ability to distinguish graph pairs in BREC, while Appendix B further tunes the magnitude parameter (q=e−0.42q=e^{-0.42}) to maximize discrimination on the same benchmark. This introduces potential benchmark-specific selection bias, making it unclear whether the observed expressivity generalizes to unseen graph distributions. Moreover, distinguishing a finite set of non-isomorphic graph pairs does not establish broader theoretical expressivity. Evaluating the selected invariants on independent, structurally challenging graph families would strengthen the generality of the conclusions.

  2. Structural heterogeneity does not necessarily imply poor generalization. Section 3.2 demonstrates that graph invariants can distinguish datasets based on structural characteristics, even within the same domain. However, high dataset membership classification accuracy does not necessarily indicate harmful distribution shifts for downstream learning, since structurally different datasets may share similar task-relevant relationships. Although Appendix E explores correlations between structural separability, multi-task performance, and gradient alignment, the experiments simultaneously vary graph distributions and prediction tasks, making it difficult to isolate the impact of structural heterogeneity on generalization.

  3. Computational efficiency lacks an end-to-end comparison. The paper emphasizes the computational advantage of XGBoost over GNNs in hyperparameter tuning. However, this comparison does not fully account for the potentially expensive precomputation of graph invariants, particularly spectral, topological, and curvature-based descriptors. Although computational costs and efficient invariant subsets are discussed in Appendix B, the overall efficiency and scalability remain unclear across varying graph sizes and densities. An end-to-end comparison incorporating invariant extraction, hyperparameter tuning, and training costs against GNN baselines would strengthen the efficiency claims.

  4. Mathematical validity and numerical robustness of graph invariants. Appendix A.1 (Tables S.1-S.3) raises several concerns regarding the mathematical validity of the proposed descriptors. First, the compression-based approximation to Kolmogorov complexity relies on a lexicographically sorted edge list, which does not guarantee permutation invariance under vertex relabeling unless canonical labeling is applied. Second, commute time is computed using the Laplacian pseudoinverse, but its interpretation for disconnected graphs is unclear, since random-walk commute times between disconnected components are infinite. Additionally, several spectral and topological invariants may be sensitive to numerical degeneracies, including zero eigenvalues and singular matrices. The authors should clarify how these cases are handled and verify the permutation invariance and numerical robustness of the computed descriptors, particularly given their central role in the BREC expressivity analysis.

  5. Limited characterization of feature–structure interactions. The proposed graph invariants capture topology independently of node and edge attributes, potentially overlooking important feature-structure interactions in attributed graphs. For instance, molecular graphs with identical unlabeled topology but different atom or bond assignments may exhibit substantially different properties despite sharing the same structural invariants. Moreover, the agg representation captures only restricted local feature aggregation and may fail to represent nonlinear or long-range feature–structure dependencies. Consequently, limited gains from adding invariants do not necessarily imply that graph structure is irrelevant, but may instead reflect limitations of the selected descriptors in capturing task-relevant structural information.

Questions for authors
  1. Validity of the claimed graph invariants (Appendix A.1, Tables S.2-S.3). The compression-based approximation to Kolmogorov complexity appears to depend on vertex labeling because it compresses a lexicographically sorted edge list without explicitly performing canonical labeling. Can the authors demonstrate that this quantity remains unchanged under arbitrary vertex permutations? Similarly, how is commute time defined for disconnected graphs, for which the expected random-walk commute time between components is infinite? Please clarify the handling of these cases and whether the reported invariant fingerprints satisfy permutation invariance numerically.

  2. Generalization of BREC-selected expressive invariants (Section 3.1; Appendix B). The expressive subsets are selected using BREC discrimination performance, and the magnitude parameter is also optimized on BREC. Does this selection introduce a benchmark-specific bias into the resulting expressivity comparison? Can the authors provide evidence that these subsets retain their discriminatory capabilities on graph families not used during selection, particularly strongly regular, cospectral, or other structurally challenging non-isomorphic graph pairs?

  3. Is the full computational pipeline genuinely more efficient (Section 2; Appendix B)? The argument for computational efficiency emphasizes the speed of XGBoost tuning, while invariant extraction is performed separately and can involve expensive spectral or topological operations. Could the authors report end-to-end computational costs, including preprocessing, invariant calculation, hyperparameter optimization, and model training, for both the proposed baseline and comparably tuned GNNs? A scaling analysis with graph size and density would help establish the practical limitations of the approach.

  4. Quantifying incremental structural information (Sections 2-3). How much of the predictive improvement provided by the full invariant collection remains after controlling for simple graph statistics such as node count, edge count, graph density, and degree moments? Could the authors include controlled ablations for individual invariant families and compare their incremental predictive contributions? This would help establish whether the method captures information beyond conventional graph statistics rather than benefiting principally from a larger engineered feature space.

4 comments

We thank the reviewer for their very detailed review and appreciate that they find all main sections of the paper (sections 3.1-3.3) useful, find the paper clearly motivated and well-organized as well as the evaluations extensive.
Because of the technical depth of their concerns about the invariant computation as well as each of the three main sections, we need some more time to prepare an appropriate answer. We will however try to send our official comment as soon as possible. We apologize for this delay.

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.

3QuL: ... Kolmogorov complexity appears to depend on vertex labeling...

Concerning the Kolmogorov complexity, we removed the invariant in Table S.2 in our revision, which was a documentation error. We agree that a compressed edge list depends on the labelling. For this reason, it was never used in any experiments.

3QuL: ...how is commute time defined for disconnected graphs...

We compute the invariants on the largest connected component of each graph. We added this clarification in Appendix A in our revision. Commute times between components never arise. We apologise for not making this clearer in the paper.

3QuL: ... spectral and topological invariants may be sensitive to numerical degeneracies, including zero eigenvalues and singular matrices... clarify how these cases are handled and verify the permutation invariance and numerical robustness...

Concerning handling of singular matrices and zero eigenvalues, we use pseudo-determinants for Analytic torsion, and 0log⁡0=00\log 0=0 for von Neumann entropy. We added these details in our revision to match our computation. No computed invariant has NaN or infinite values.

3QuL: ... verify the permutation invariance and numerical robustness...

We confirm numerical robustness and permutation invariance. On the 400 reliability pairs on BREC (relabelled graphs) as well as in over 140,000 sampled isomorphism classes from our datasets, the difference on isomorphic graphs is at most floating-point roundoff.

3QuL: The expressive subsets are selected using BREC discrimination performance, and the magnitude parameter is also optimized on BREC. Does this selection introduce a benchmark-specific bias into the resulting expressivity comparison?

Concerning tuning, the only parameter tuned on BREC is the magnitude scale q, and without magnitude, "I" still separates 290/400 pairs (only 2 pairs fewer).
We understand that the reviewer is still concerned about the generalizability from BREC performance. We ran the following experiment to assess to what extent this is an issue for our investigated datasets:

  1. For each of the 26 datasets, we took all graphs that cannot be WL-distinguished.
  2. We calculated all subsets of invariants mentioned in the paper.
  3. Our finding: Regardless of which invariant subset to be used, invariants are capable of distinguishing all such graphs.

We believe that this establishes generalizability in practice and hope that this alleviates the concerns by the reviewer. We note that we here also can not observe any negative impact of a potential benchmark specific selection bias.

3QuL: Can the authors provide evidence that these subsets retain their discriminatory capabilities on graph families not used during selection, particularly strongly regular, cospectral, or other structurally challenging non-isomorphic graph pairs?

To further address the reviewers concern about generalization of expressivity to challenging graphs not used during selection, we perform an expressivity analysis on the collection of strongly regular graphs on at most 64 vertices by Ted Spence (https://www.maths.gla.ac.uk/~es/srgraphs.php):

  • We computed invariants on the 13 families of strongly regular graphs with at least two members in Spence's catalogue.
  • Together, they contain 43,705 graphs, or 560 million 3-WL-indistinguishable pairs in total.
  • I separates all but 3 of these pairs, and S all but 198 (both more than 99.9999%).
  • I_eff and S_eff miss 0.001% and 0.02%.

We see only very minor reductions in expressivity when restricting to expressive subsets in this analysis. We believe that this confirms and strengthens our findings on BREC.

3QuL: Is the full computational pipeline genuinely more efficient? ...report end-to-end computational costs, including preprocessing, invariant calculation, hyperparameter optimization, and model training...

To illustrate the end-to-end computational cost, we give an example on the largest dataset, PCQM4Mv2. We hope that this demonstrates the radically different computational cost. Invariant computation here takes ≈84 CPU-hours without any parallelization. This can be brought down to a few hours on a server with e.g., 32 available cores. Preprocessing takes around 8 minutes. And at that point, every further hyperparameter tuning-iteration takes minutes up to around half an hour. However, only a single run of a GNN wth typical parameters on PCQM4mv2 takes up to multiple days with the same hardware.

As additional information for the reviewer: Invariant calculation runs once per dataset, parallelises over graphs, and is reused across all input configurations, 150 tuning trials, all seeds, folds and targets.
Likewise, summation and aggregation of node features (preprocessing) can be processed once for all trials and configurations. Both are simple iterated summation operations performed within seconds, dominated by the invariant computation.
Once computed, training time does no longer depend on graph size, whereas a GNN re-processes the full graph in every forward pass. We thus were not suprised to observe that training a GNN with common parameters is more than a factor of 150 times slower than fitting XGBoost in our tests. Hence a comparable tuning is not feasible for GNNs.

3QuL: A scaling analysis with graph size and density would help establish the practical limitations of the approach.

The empirical performance is shown in Table S.6 of our submission across datasets with different graph sizes and densities. Additionally, we added the corresponding theoretical complexity in Tables S.1 to S.4 in our revision. In summary, we find that, unless individual large graphs in a dataset become highly-connected, empirical performance is neglibible since the computation can be trivially parallelized.

Dense graphs are the limitation we explicitely state in section 4, which is why we defined the efficient invariant sets.

3QuL: How much of the predictive improvement provided by the full invariant collection remains after controlling for simple graph statistics such as node count, edge count, graph density, and degree moments?

Simple graph statistics are already accounted for. In section 3.2, graphs are matched exactly on nn, mm and ∑vdv2\sum_v d_v^2 (hence also density), so these carry no signal. Invariants still reach 58–89% pairwise accuracy (chance: 50%).
For section 3.3, "agg" contains nn, 2m2m, ∑vdv2\sum_v d_v^2 (after 0, one and two rounds of aggregation) on all datasets with unit node features. On all four such datasets, invariants alone beat "agg". For example on COLLAB 74.7->79.8 (accuracy).

3QuL: Structural heterogeneity does not necessarily imply poor generalization... does not necessarily indicate harmful distribution shifts for downstream learning...

We agree that separability does not directly imply harm or poor generalization for a downstream task, hence we make no such claims. Section 3.2 offers it as a partial explanation.

3QuL: ... potentially overlooking important feature-structure interactions in attributed graphs... the agg representation captures only restricted local feature aggregation and may fail to represent nonlinear or long-range feature–structure dependencies.

We agree that graph structure alone does not capture all the information relevant to prediction. This distinction from features and structure-feature interaction is precisely why we investigate structural invariants separately. The individual configurations should not be understood as candidates to beat SOTA. They come as a package to assess which structural properties contribute to predictive performance across datasets. And the gap to trained GNNs measures to which degree non-linear feature–structure dependencies matter.

3QuL: ... limited gains from adding invariants do not necessarily imply that graph structure is irrelevant...

We thank the reviewer for the careful reading, One of our conclusions (R3) was framed too broadly; we have rectified this in our revision and will rephrase 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 six-layer GIN). Only if neither show a gain over the structure agnostic "sum", R3 should apply. This is quantified by overlapping confidence intervals for these 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 itself only points towards low relevance of global structure.
It becomes a statement about the relevance of structure for a task in general 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 methods that use information beyond the 2D graph. This also goes for "Proteins", this can be observed 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 believe that this addresses the reviewer’s concerns and we hope that this may be reflected in their assessment of the paper.

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

The article proposes to use graph invariants as a simple baseline for graph level tasks. On BREC, the authors show that a set of just 4 invariants is sufficient to overall outperform all tested GNNs. Using XGBoost on such invariants (together with aggregated node features) achieves comparable performance to several established GNNs. Furthermore, the authors show that such invariants are capable of telling graphs from different datasets apart.

Critical strengths

The need for proper baseline methods is real. The authors correctly point out that the field often just compares against other complex models without considering more basic approaches which might already be sufficient for many tasks. This gives the paper some practical value, even if the contribution itself is limited.

Critical weaknesses

The approach contains very little novelty. Computing a set of invariants and running XGBoost on them is quite straightforward rather than a research contribution in itself. I believe this article is a good reminder that there is a need for proper baselines but the contribution in itself offers almost no novelty or insights and its execution and presentation fall short of the high ICLR standards.

Questions for authors
  • Do the authors have an explanation for why certain combinations of invariants achieve such good results?
  • What is the complexity of computing invariants?
3 comments

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.

mW5q: Computing a set of invariants and running XGBoost on them is quite straightforward rather than a research contribution... good reminder that there is a need for proper baselines... offers almost no novelty or insights and its execution and presentation fall short of the high ICLR standards.

We respectfully disagree with this. We present novel findings that do not exist in the literature. While we make use of existing mehods, our combination of invariants and our in-depth evaluation is novel and we are not aware of any work preceding ours that attempts to do so. Our paper does not claim that computing the invariants constitutes a contribution; rather, it is the setting of our framework. We furthermore want to point out that solidifying and rigorously proving pre-existing folklore results is an important contribution to the field.

We appreciate that the reviewer agrees with us on the need for proper baselines. We want to point out some recent work---which appeared after our submission, but which we shall discuss moving forward. Said work employs an MLP baseline to assess mostly node-level tasks; we believe that our work, with an explainable set of features that is deliberately kept minimal, naturally complements such a benchmarking endeavor.

Finally, the reviewer mentions that the contribution falls short of standards. We are sorry to hear this but would welcome more concrete feedback on specific shortcomings.

mW5q: Do the authors have an explanation for why certain combinations of invariants achieve such good results?

We believe this to be the case because different invariants cover different structural aspects of a graph (e.g. cycles) that are relevant for specific tasks. We deliberately did not tune a set of invariants on a per-dataset basis. This is why we used the BREC dataset to choose invariants in an unbiased way, i.e., a way that does not depend on a specific labeled graph-level task. As our paper states, we are not considering the performance of invariants to indicate the need to go back to feature engineering; rather, we want to point out their role as simple baselines that should be outperformed.

mW5q: What is the complexity of computing invariants?

The empirical performance is shown in Table S.6 of our submission. Additionally, we added the corresponding theoretical complexity in Tables S.1 to S.4 in our revision. In summary, we find that, unless individual large graphs in a dataset become highly-connected, empirical performance is neglibible since the computation can be trivially parallelized.

We thank the reviewer for engaging with our work and hope that we have alleviated their concerns. We remain available for any additional questions or comments.

Thank you for the response.

It is unclear to me what the authors mean by the word 'framework' beyond comparing XGBoost on a few feature configurations. I also dont see what is rigorously proven. The paper only provides some empirical evidence.

Concerning the presentation, I find the figures to be unconventional and often confusing. While Fig 1 is meant to show that the invariants are complementary, it is not possible to tell whether this is actually the case. Fig 2 is overloaded and hard to read. Fig 3 shows only datasets with gains. I believe simple tables would be clearer in all three cases.

We thank you for your follow-up,

Our work is empirical in nature, and so is our evidence. Further, we do not claim formal proofs and we consider this not to be a weakness.

We are glad to hear the reviewer's remaining concerns are minor. Subsequently, we would be happy to improve the presentation of our figures for a camera-ready version to make them more clear.

Comments on the paper

1 comment
AuthorsOpenReview ↗

End of discussion period

Dear Reviewers,

We thank you again for your reviews and for engaging with our work. We would like to remind you that the discussion period ends today. If you have remaining concerns or questions, we would very much appreciate hearing them and would be happy to discuss further.

Otherwise, we are grateful for your feedback, which has helped us making corrections and improve the presentation of the paper. You can see all changes highlighted in blue in the revision.

Kind regards,

The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.