acceptodds
Withdrawn from ICLR 2027

HIERARCHICAL SPECTRAL LEARNING: LOCALITY BEFORE FREQUENCY FOR GRAPH NEURAL NET- WORKS

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Graph neural networks on heterophilous graphs face two coupled challenges: neighborhood aggregation can mix semantically incompatible nodes, and a single latent geometry may fail to capture the coexistence of hierarchical, flat, and cyclic graph structure. Existing methods typically address only one of them: geometric GNNs improve representation fidelity in curved spaces but still rely on smoothing-based aggregation, while heterophily-aware spectral methods improve signal separation yet ignore the geometric mismatch between node representations that live in different tangent spaces. We propose a Curvature-Transport Spectral Network (CTS-Net) that resolves these limitations by combining mixed-curvature representation learning with transport-aware and track-specific propagation. CTS-Net embeds nodes in a mixed-curvature product manifold to model heterogeneous graph geometry, parallel-transports neighbor messages to the receiver tangent space to align cross-node representations before aggregation, routes the aligned messages into smooth and contrastive tracks through a learned orthogonal operator to separate compatible from incompatible interactions, and applies track-specific polynomial diffusion to learn distinct spectral responses for the two types of signals. Our analysis shows that orthogonal routing preserves inter-track separation and that transport avoids additional distortion during aggregation. Across ten heterophilous node-classification benchmarks, CTS-Net achieves the best average performance among the compared baselines while remaining efficient in memory and runtime.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Transformer

Reviews

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

This paper proposes Hierarchical Spectral Learning (HSL), a locality-first multiresolution spectral framework. HSL combines graph topology and feature similarity to construct a multi-view geometry, refines the fused geometry using diffusion coherence, recursively constructs a diffusion-coherent hierarchy through spectral partitioning, and derives degree-aware Haar scaling and contrast components. It then learns frequency- and resolution-dependent responses over the resulting localized multiresolution components. The paper provides theoretical results for successive linear spatial operators under a fixed hierarchy. It evaluates HSL on node classification, graph classification, and community detection, and further studies oversmoothing, oversquashing, hub-degree bias, and scalability.

Critical strengths
  1. The principle of locality before frequency is clear and technically interesting.
  2. The empirical study covers node classification, graph classification, and community detection, together with depth-wise contrast preservation, degree-stratified analysis, hierarchy and filter ablations, and scalability studies.
Critical weaknesses
  1. The entire hierarchy tree is precomputed in a one-off manner prior to training and remains fixed throughout the training process. This strategy lacks adaptivity across different types of graphs. Moreover, errors in hierarchical partitioning will perpetually propagate downstream, with no mechanism to correct mispartitioning during training.
  2. The relationship between theoretical guarantees and underlying assumptions is not clearly established. All theorems are derived for linear spatial operators and neglect the MLP non-linearities and skip connections within the network. Furthermore, the diffusion-coherent hierarchy relies on spectral clustering with k-means, which introduces randomness. Corresponding theoretical analysis is missing.
Questions for authors
  1. The near-linear hierarchy-construction claim in line 470 needs further justification. At each level, the method applies k-means with K_l clusters to a q_l-dimensional spectral embedding, while K_l = max⁡{1,⌊r n_l ⌋} scales with n_l. The complexity analysis does not explicitly account for this clustering step, feature k-nearest-neighbor construction, or the clustering variant and iteration budget.
  2. Section 2.3 explicitly limits its theoretical results to successive linear spatial operators under a fixed hierarchy, excluding the learned feature transformations and nonlinearities in Eq. (4).
  3. In line 165, D_coh may have a zero diagonal entry if diffusion gating removes all incident candidate edges, making the normalized Laplacian undefined. The later correction μ_i = d_i^coh + δ does not resolve this earlier normalization issue. Please clarify how zero-degree nodes are handled.
  4. Why is the effective frequency defined with L_mix in line 242 when the hierarchy is constructed from L_coh? Please clarify why these two geometries are used for different stages.
  5. The hierarchy is constructed using the randomized heat embedding Y_t = p_(K_d ) (L_mix)R, but the paper does not assess how different draws of R, the projection dimension q_d, or the polynomial order K_d affect the resulting hierarchy. How stable is the hierarchy across these approximation settings?
  6. Table 4 reports only task accuracy as evidence of oversquashing mitigation. Can the authors report the source-target sensitivity ‖∂h_v^((l))/∂x_u ‖ introduced in Section 1.1 to directly verify that the gains arise from hierarchy-mediated communication rather than predictive performance alone?
  7. Figure 1 weights the root scaling term as γ_0 P_0 X, whereas line 248 defines it as P_0 X without γ_0; it also uses S_topo rather than S_top. Figure 2 uses k - 1 and states |C| - 1 contrast directions, whereas lines 226–230 specify m - 1 for a region with m children. These annotations should be reconciled with Section 2.
  8. Table 1 is not fully documented: the symbols † and ‡ are undefined.
  9. In Figures 3 and 4, the proposed method is labeled “HMH (Ours)” in the legends rather than “HSL (Ours).” Why this inconsistency?
Reviewer_AEYxOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

HSL combines topology and feature affinities, refines edges using heat-diffusion distances, and builds a hierarchy through spectral embeddings and k-means. Degree-aware Haar projectors define localized contrast components. Each layer rescales these components using effective frequency and hierarchy resolution, with a depth-normalized gain. The paper evaluates node classification, graph classification, community detection, and controlled long-range tasks.

Critical strengths
  1. Explicit preservation of multiscale detail. Retaining localized contrast components avoids discarding fine information through coarse averaging alone. Combining this representation with diffusion-guided structure is a worthwhile direction.
  2. A controlled linear filtering design. The depth-normalized gain provides a valid contrast-energy bound for successive linear filters on a fixed hierarchy. Recursive analysis and reconstruction avoid dense projector matrices.
Critical weaknesses
  1. Central theoretical and experimental claims are not established. Theorem 4 shows nonzero interaction for an individual γCPC, but components can cancel in the full operator. Setting every γC=1\gamma_C=1 is allowed and gives F=P0+∑CPC=IF=P_0+\sum_CP_C=I, with no cross-node influence. The contrast-energy bound also explicitly excludes feature transforms and nonlinearities. Separately, Section 2.2 and hsl/community.py use preprocessing assignments for community outputs, yet Table 24 changes PolBlog NMI from 84.7 to 81.3 under Fixed response. With an unchanged hierarchy and random state, changing only a downstream response cannot change those outputs. These gaps undermine the claimed communication guarantee and component attribution.
  2. Novelty relative to graph framelet methods is unclear. The paper omits PEGFAN, introduced in Permutation Equivariant Graph Framelets for Heterophilous Graph Learning (Li, Zheng, Feng, Li, and Zhuang, TNNLS 2024). Section III and Proposition 1 give a complementary-subspace construction BTB=I−ppTB^TB=I-pp^T. With p=aCp=a_C, this corresponds to the local contrast projector used by HSL. This does not make the complete networks identical, but requires a direct discussion and comparison. Shared-hierarchy and shared-backend experiments are needed to establish the incremental value of diffusion-guided partitions and adaptive responses.
Questions for authors
  1. Clarification: Why do Fixed response and Uniform Haar change community scores when the stated outputs are the finest preprocessing assignments? What other settings or inference steps changed?
  2. Clarification: Can the authors establish communication for the full operator despite cancellation, or narrow the claim to individual components?
  3. Decisive comparison: What remains of the improvement against PEGFAN under a common hierarchy, and against other hierarchy builders under a common backend?
  4. Clarification: Please include kNN search, k-means with KK proportional to nn, soft assignments, and CPU memory in the preprocessing analysis and explain the actual implementation behind the million-node results.
Reviewer_ywj1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

Most existing GNNs use one graph wide propagation operator, which can mix different local signal patterns and cause oversmoothing and oversquashing. To address this, the paper proposes Hierarchical Spectral Learning model, which fuses topology and feature similarity, builds a diffusion coherent hierarchy, and uses a Haar decomposition to get localized multiresolution components. HSL then learns a gain for each component from a frequency and a hierarchy level. Theoretical analysis as well as extensive experiments cover node classification, graph classification, and community detection are provided in the paper.

Critical strengths
  1. The research problem of the paper is important, which looks into different limitations of existing GNN models.
  2. Although combining different components, the overall designs of the proposed HSL is straightforward. Theoretical analysis is also provided for some detailed explanations.
  3. Extensive analysis is conducted on multiple different tasks and datasets.
Critical weaknesses
  1. The overall performance of proposed HSL seems to rely on the extracted hierarchy structure, which can also be seen from the ablation study and appendix. However, the quality and robustness of the hierarchy as well as generation algorithm is not evaluated. The appendix shows sensitivity analysis on different hierarchy structures, but it does not evaluate how errors in partitioning, assignment and graph coarsening would affect model performance. Some analysis such as perturbation in graphs and features would impact the hierarchy quality as well as overall performance.

  2. It seems the proposed HSL shares a lot of similarity with the HMH method, which is also cited in the paper and used as baseline. The paper does not provide enough explanation on the design choices compared to HMH. Besides there are some experiment details need more explanations which make the experiments much less convincing:

    a. There are multiple same values (both mean and std) shared by HSL in this paper and the HMH model from its original paper: Filtered Squirrel and Chameleon (Table 1). MUTAG (Table 2). Citeseer, Coauthor-CS, Coauthor-Physics, Questions, and Amazon-ratings (Table 10).

    b. Meanwhile, some other numbers of HMH for datasets such as Minesweeper and Tolokers seem to be directly copied from the paper. The paper should clearly explain if the experiment settings are exactly the same compared to the original HMH paper, and provide details such as detailed setup.

    c. In Figure 4, the best performing group is marked as HMH instead of HSL. Can authors provide more explanation on this?

  3. The motivation of the paper seems to be valid but never being validated directly. The paper should include experiments that measure where a global spectral filter fails compared to HSL. For instance, if HSL performed better on low-homophily nodes compared to global filters based models, this would support the motivation directly.

Questions for authors

How does the proposed hierarchy preserve meaningful local graph structures, especially when a graph contains both homophilous and heterophilous regions? Can the authors provide quantitative evidence of the quality of the learned regions? How are k-means clustering and soft assignments implemented efficiently when the number of clusters grows with graph size?

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

Related papers

Discussion (0)

Sign in to comment.