acceptodds
Under review as a conference paper at ICLR 2027

Spectral Graph Features for Learned Heuristics in Automated Planning

Abstract

A common approach in learning for automated planning is to train a domain-dependent heuristic on small problems and apply it to larger ones. Recent work showed that 1-Weisfeiler–Leman (1-WL) can extract effective features from planning states, outperforming deep-learning approaches while reducing training time to seconds. This result motivates the study of alternative graph-based features. Spectral graph methods are a natural candidate because they are well studied and can capture global structure that finite-round 1-WL may miss. We present the first study of spectral features for learning heuristic functions in classical planning. Our results show that spectral features outperform 1-WL in multiple domains.

Primary area:
applications to robotics, autonomy, planning
Keywords:
classical planning, learning for planning, heuristic search, spectral analysis

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 4 reviews, above 27% of the others.
Reviewer_T3o2OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper tests whether spectral descriptors of Instance-Learning Graphs (ILGs) can replace the four-round 1-WL color histograms in WL-GOOSE for learning domain-specific planning heuristics. Holding the rest of the WL-GOOSE pipeline fixed (ILG encoding, Scorpion training states, Ridge/LSVR/GPR regressors, and GBFS in Fast Downward), the authors evaluate nine spectral families—with and without color counts—across 63 configurations on the 900 IPC 2023 Learning Track problems. Overall, the best spectral setup (return moments plus color counts with GPR) solves 513 tasks, essentially tying 1-WL with GPR at 516, though with complementary domain strengths: return moments win on Transport and Rovers, while losing on Blocksworld and Childsnack. The paper rounds this out with a cost analysis, out-of-fold (OOF) error diagnostics, and theoretical limit results (feature-collision bounds and path-graph extrapolation failure).

Critical strengths

Clean, Controlled Empirical Design & Transparency: By changing only the feature map, the paper cleanly isolates the effect of the graph representation—something rare in learning-for-planning comparisons. Reporting all 63 configurations (alongside separate search and feature-extraction times, OOF diagnostics, and promised code) transparently answers key ablation questions regarding edge labels, color counts, sign/basis invariance, and regressor choice.

A Compact, Fixed-Dimensional Alternative to 1-WL: Return moments form a tiny, fixed-dimensional feature vector that requires no training-dependent vocabulary, yet they nearly match the coverage of full 1-WL histograms. This is a strong practical finding because it avoids the vocabulary-growth and unseen-feature issues of WL histograms while remaining lightweight.

Critical weaknesses

Overclaimed Headline Results and Test-Set Selection Bias: The abstract claims spectral features "outperform 1-WL... achieving SOTA performance," whereas the body accurately notes they "closely compete" (513 vs. 516 tasks, 4/3/3 domain split, and 1.14× more expansions on shared tasks). This is a parity result, not SOTA—especially without comparisons to recent WL improvements (Hao et al., 2025), classical baselines (LAMA, h FF ), or GNNs. Moreover, selecting the best of ~60 spectral configurations directly on the 900 test problems (against just three 1-WL variants), alongside tuning on a "90-task screen" and reporting single runs without variance estimates, makes a 3-task margin shaky. Configurations should be selected via OOF error or a held-out validation split. Compounding this, Table 1 claims to show the best configuration per family, but Table 3 shows better LSVR + counts results than Table 1's Ridge entries for SignBasis (341 vs. 330), normalized heat transfer (435 vs. 414), and raw heat transfer (468 vs. 423)—the last of which would be the third-best family overall.

Unexamined Disconnect Between Global Motivation, Bipartite Redundancy, and Local Winners: Because the paper evaluates existing descriptors rather than proposing a new method, its value hinges on explaining why and when spectral features work. The paper motivates spectral features via global structure, yet the global families perform worst, while the winner—length-4 return moments—is a purely local message-passing statistic. Because ILGs are bipartite, odd walks vanish and q=4 return moments mostly count 4-cycles (e.g., symmetric road(a,b)/road(b,a) pairs in Transport), which 1-WL misses. Bipartiteness also makes the spectrum of S symmetric about 0 (and L norm about 1), meaning the top and bottom eigenvalues, distribution quantiles, and SignInv/SignBasis eigenvector budgets are redundant pairs—halving the effective information in those families. Finally, the paper repeatedly claims that complementarity with 1-WL motivates combining them (the domain oracle hits 564), yet omits a cheap feature-concatenation experiment that would turn a speculative claim into a concrete contribution.

Questions for authors

Questions for Authors:

What is the coverage when concatenating 1-WL with return moments + counts across each regressor, and what is the per-task union of the two leading setups?

Why did Table 1 default to Ridge for SignBasis and both heat-transfer variants when Table 3 has stronger LSVR + counts results? Does your 1-WL baseline match the original WL-GOOSE coverage?

Can you report test coverage when configurations are selected strictly via OOF error or a held-out validation split (without touching the 900 test problems or overlapping screens)?

Did you account for bipartite spectral symmetry when allocating the endpoint and eigenvector budgets, or are the upper/lower halves redundant?

Since OOF error on small training instances doesn't test size extrapolation, how do prediction error and unseen 1-WL color fractions scale across test problems binned by ILG size? Additional Feedback & Minor Cleanup:

Missing Recent Literature & SOTA Context: To properly contextualize the SOTA claims and position this work within the broader learning-for-planning landscape, please expand the related work and discussion to include recent SOTA GNN-based policy/heuristic learning methods—most notably GABAR (NeurIPS 2025, Graph Attention-Based Action Ranking for Relational Policy Learning)—alongside other recent 2025/2026 advancements in WL features (e.g., Hao et al., 2025) and LLM/GNN-generated heuristics on the IPC 2023 Learning Track.

Clarify why 1-WL is so much worse under Ridge than dot-product GPR (351 vs. 516), and state whether return moments use q=4 or q∈{0,…,4}.

Fix the mismatched citations in Section 3 (Chen et al., 2025 vs. LM4Plan; Chen et al., 2024a vs. Chen & Thiébaux, 2024) and minor typos ("˚ Return", "generation generation").

Reviewer_skjUOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes using the spectral feature of the graph representation of a classical planning domain / instance to learn a domain-dependent, instance-independent heuristic function. This is supposed to be complimentary to 1-WL feature that has been used in the previous work, as 1-WL is not injective and the spectral feature may be able to distinguish the graphs that return the same 1-WL feature.

Spectral feature itself is not injective either, so 1-WL could help spectral feature too. The source of non-injectiveness of spectral feature is twofold: sign of the eigenvector, and multidimentional eigenspace where there is no unique basis. The authors address the sign by using the squared input value. To avoid eigenspace ambiguity, the authors use the normal vector of the eigenspace, which is unique (as far as I understand. I imagine a 2D plane in a 3D space, where the plane has no unique orthogonal basis; any pair of non-parallel vectors on the plane can be the basis, while it has a unique unit normal vector.)

I thought that SignInv and SignBasis are the main contribution, but it turned out, this is a big mislead. The author then starts explaining various spectral features, including the heat kernel methods and return moments, which are the core contribution but is explained extremely poorly. The overall takeaway from this paper is that the authors kept throwing various spectral features at the walls until one of them sticks. It is a viable approach to research, but a bad way to represent your results.

As mentioned later, there is no interpretation of each feature, I failed to get a deeper understanding of the method. Note that I have also tried Graph Laplacian in a different context of classical planning (unpublished), where my approach did not work --- so a deeper insight and analysis is much desired to help others understand why your approach works better.

The experiments are also shallow. It turned out most of what the authors tried did not work, and indeed the one that is complementary to 1-WL is the return moments.

The paper does not have comparisons to symbolic classical planners like LAMA.

I suggest a few changes to the current manuscript:

  • Remove the failed approaches and move them entirely to the appendix.
  • Using the saved space, rewrite the graph laplacian section entirely, with more description and some figures.
  • Add deeper insights -- what each feature is supposed to encode?
  • Add deeper analysis -- What does the feature do in the domains that it worked well?
    • For example, show the spectral distribution in a representative instane in each domain.

In addition, while the authors claim that 1-WL and spectal features are complementary, they did not concatenate those features and train the single regressors to perform ablation analysis. Intuitively, these additional features would combine well, and may even have synergetic effects. Some regularization for feature selection may be necessary, and it is interesting to see whether it suppresses 1-WL or spectral features in domains that 1-WL or spectral features failed to perform by itself, respectively.

minor:

  • line 115: N(v)N(v) undefined --- neighbor?
  • line 118: "exactly when" --- maybe AI slop? Claude tends to use "exactly" a lot. I see many uses of "exactly" in this paper -- 5 times, to be exact.
  • line 123: "The released WL-GOOSE..." --- maybe AI slop?
  • line 127-129: "A dictionary ... learned weight." This one sentence does not seem to connect to the surrounding context. AI slop?
  • The spectral feature section, and its description, or more specifically of graph laplacians, must be re-written. The current text is not adequate for consumption and is not written pedagogically. It must be split into multiple paragraphs, and then combined with a more generic introduction of graph laplacians, with appropriate figures explaining the concept.
  • there are several missing citations on using graph laplacians in reinforcement learning context.
    • Machado, Marlos C., Marc G. Bellemare, and Michael Bowling. "A laplacian framework for option discovery in reinforcement learning." International conference on machine learning. PMLR, 2017.
    • Jinnai, Yuu, et al. "Finding options that minimize planning time." International Conference on Machine Learning. PMLR, 2019.
    • Jinnai, Yuu, et al. "Discovering options for exploration by minimizing cover time." International Conference on Machine Learning. PMLR, 2019.
    • not my papers, by the way!
  • Section 4.3 gets increasingly sloppy, The crucial information missing in this section is what each feature is supposed to represent. Since eigenvalues of graph laplacian
  • line 267-280: these two paragraph deserves a new subsection.
  • line 263: HKS mentioned before introduction.
  • line 427: I agree that 1-WL and spectral features are complementary, but attributing this to PSPACE-completeness is hand-wavy. In fact, PSPACE-completeness is a statement over the entire STRIPS domains, rather than a statement of each domain in separation --- some planning domains can be solved in polynomial time.
Critical strengths

This is a novel application of graph laplacian to classical planning.

Critical weaknesses

The writing quality and the depth of experiments / analysis, as mentioned in the summary.

Questions for authors

Why does the return moments help, compared to other spectral methods?

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

The paper studies several feature extraction methods for classical planning problems based on spectral graph features. Each state of the planning problem is encoded as an ILG, from which the features are extracted. A regressor, trained on small instances of a problem type, is then used without retraining on larger instances of the same domain. This setting allows for fast training and transfer to larger problems. The work compares the different representations presented with 1-WL features, keeping the same WL-GOOSE pipeline, on a set of problems from the IPC 2023 Learning Track suite. The results show performance broadly comparable to 1-WL for some specific features, with improvements in some domains and worse performance in others, suggesting a complementary relationship between the representations compared.

Critical strengths
  • The comparison is well designed. Keeping graph construction and search fixed focuses the experiments on revealing differences between the descriptors. Furthermore, considering coverage, expansions, time, and prediction error together allows for a comprehensive assessment across the various possible evaluation dimensions.
  • The research question is clear and interesting. The problem addressed is concrete, and studying alternatives to the features presented in previous work is a relevant direction, especially in the setting of generalization across problem sizes. The feature construction has a clear and valuable theoretical basis, which provides criteria for motivating the representation choices and understanding their limitations, making the method more interpretable.
Critical weaknesses
  • Reporting the best configuration of features, colour counts, and regressor found using the 900 test problems can lead to overly optimistic results. Although the regressor was trained and tested on separate data, the configuration itself was selected using test performance. Selecting the configuration on a validation set and evaluating it on an independent test set would address the risk of overfitting in configuration selection. Including this intention as future work does not resolve the issue.
  • In my view, the empirical contribution remains rather limited. The main result essentially centers on one family that achieves performance broadly comparable to the best 1-WL configuration, with advantages and disadvantages across different domains. The ablations and prediction-error analyses provide useful insights, but I would expect a deeper account of which problem characteristics explain these domain-dependent differences and how robust they are. Generalization to larger instances, which I consider the most interesting characteristic of the work, also receives limited empirical analysis. Figure 2 provides partial indications, but it considers only jointly solved problems and does not directly relate training and test ILG sizes. Reporting these sizes together with coverage across problem-size ranges would help assess how performance changes with scale.
Questions for authors
  • In Table 3 in the appendix, the best configuration for “Heat Transfer Raw” uses LSVR and achieves a coverage of 468, whereas Table 1 reports Ridge. This appears inconsistent with the stated criterion of selecting the best configuration for each family. Could you clarify the selection mechanism, including whether configurations were selected using coverage on the same 900 test problems reported in the evaluation? Was the same selection procedure applied to 1-WL, and how many configurations were considered for each feature family?
  • As the ILG formalization is presented, a predicate of arity greater than one applied to the same object in different positions is allowed and also makes sense. For example: connect(a, a). This yields a graph with two parallel edges connecting the atom node and the object node. This introduces ambiguity in the subsequent derivation of matrices and features. Could you clarify how this specific case is handled?
  • Persistent homology also provides graph descriptors suitable for learning, including persistence-image-based approaches such as Zhao and Wang (NeurIPS 2019). Could you briefly discuss how these approaches relate to the spectral feature families considered here?
Reviewer_8BG3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies learned heuristics for classical planning. It proposes spectral features derived from the state-variable graph of a planning task and uses them as fixed-dimensional inputs to simple regressors (linear support vector regression, Gaussian process regression, and ridge regression) trained to predict optimal costs. Four feature families are introduced: global spectral features, return moments, and two eigenvector-based families (SignInv and SignBasis). The features are evaluated on 900 tasks from the IPC 2023 Learning Track (10 domains, at easy, medium, and hard difficulty) using Fast Downward with greedy best-first search, and compared with 1-WL features and simpler baselines using the same regressors. The paper reports that spectral features win in several individual domains, notably with return moments, but the best spectral variant does not beat the best 1-WL variant on total coverage.

Critical strengths
  1. A genuinely new feature family for learned planning heuristics. The paper is, as far as the cited literature shows, the first systematic study of spectral features for this task, and it develops several distinct constructions (global spectral summaries, return moments, and sign-invariant eigenvector features) rather than a single ad hoc encoding. 2. A broad, like-for-like empirical comparison. The evaluation covers 900 IPC 2023 Learning Track tasks across 10 domains and three difficulty levels, uses the same simple regressors for spectral and 1-WL features, and reports per-domain coverage and cost, so the reader can see where spectral features help and where they do not. Return moments with Gaussian process regression reach 513 solved tasks, close to the best 1-WL result, and win in several domains such as Ferry, Rovers, Satellite, Spanner, and Transport.
Critical weaknesses
  1. The headline claim overstates the main result. The abstract states that spectral features outperform 1-WL in multiple domains, which is true per domain, but on total coverage in Table 1 the best 1-WL variant (Gaussian process regression, 516 tasks) still beats the best spectral variant (return moments with Gaussian process regression, 513 tasks). The paper does not report statistical significance or uncertainty for this small gap, so the overall comparison should be presented as essentially tied, with domain-dependent wins, not as a general improvement. 2. Scope and cost limitations are underplayed. The evaluation is limited to classical, unit-cost STRIPS tasks in the IPC 2023 Learning Track setting, with no unseen-domain transfer and no comparison to deep or graph-neural-network learned heuristics beyond the 1-WL feature baseline. Some spectral variants are also far more expensive to compute than 1-WL (for example, the reported heat-kernel cost of 0.65-0.94 ms per state versus 0.02-0.03 ms for 1-WL), and the appendix path-graph example shows that fixed spectral summaries can fail on larger path-like structures. These points weaken any claim that the approach is uniformly practical or state of the art.
Questions for authors
  1. Could the authors revise the abstract and conclusions to state precisely that spectral features win in several domains but do not improve total coverage over 1-WL (516 versus 513 tasks in Table 1), and add a significance or uncertainty analysis for the coverage differences? 2. What is the feature-computation time and total planning time for the recommended return-moments variant, per domain, relative to 1-WL, and how should a practitioner choose between spectral features and 1-WL when feature cost matters? 3. Do the authors have evidence, or a concrete plan, for transfer to unseen domains or to non-unit-cost, numeric, or temporal planning formalisms, rather than only larger instances of the same domains?

Comments on the paper

1 comment
Area_Chair_CgsMOpenReview ↗

Please engage in the discussion

Dear Reviewers,

As we enter the final stage of the author-reviewer discussion, I would like to encourage everyone to actively engage with the authors’ responses and any additional evidence they have provided.

Please take this opportunity to reconsider your initial assessments with an open mind, particularly where the authors have offered substantive clarifications, detailed arguments, or additional experimental results. The goal of the discussion is not to defend initial positions, but to reach the fairest and most informed evaluation of the submission.

I encourage you to engage directly with the authors on any remaining concerns, clearly distinguishing between issues that have been satisfactorily addressed and those that remain unresolved. Where appropriate, please update your reviews and scores accordingly, or explain why your original assessment still stands.

Your active and constructive participation in these final exchanges is essential to reaching a fair, evidence-based decision.

Your AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.