acceptodds
Under review as a conference paper at ICLR 2027

Sheaf–Haar Equivariant Architecture for Heterophilous Graph Learning from Topology–Feature Clustering

10 views

Abstract

Heterophilous graphs, in which linked nodes tend to have different labels or dissimilar features, are widespread in real-world applications. However, existing multi-scale spectral approaches face two structural obstacles: (i) their hierarchical clusterings are built by procedures that ignore node features and are not covered by the models’ permutation-equivariance guarantees, and (ii) spectral framelet bands inherit the sign and degeneracy ambiguities of eigendecompositions. To address both obstacles at once, we introduce a Sheaf–Haar Equivariant Architecture (SHEAR), a hierarchical sheaf framelet network whose entire multi-resolution structure, including the partition tree, the coarse graphs, and the framelet operators, is generated by a single permutation-invariant procedure, so that the end-to-end model is unconditionally permutation-equivariant. SHEAR first fuses a permutation-invariant core-degree structural partition with progressive multi-scale subgrouping using a combined topology–feature edge distance, producing strictly nested clusterings with controlled sizes by construction. It then derives binary Haar framelet operators in basis-free form directly from the assignment matrices. These operators consist of cluster-mean scaling projections and their orthogonal complements equipped with learnable band gains, so that no eigendecomposition is involved in the frequency decomposition at all. At each hierarchical level, multi-scale neural sheaf diffusion runs with Galerkin coarse sheaf Laplacians assembled in closed form from the original edges, and all restriction maps are generated end-to-end by a shared edge-wise network, without any pretrained encoder. Finally, the outputs of propagation, diffusion, synthesis, and global low- and high-pass channels are combined by an attention-based fusion. Experiments on sixteen standard homophilous and heterophilous node-classification benchmarks show that SHEAR achieves state-of-the-art performance on several heterophilous datasets, improving upon the best previously reported result by up to 13 on Roman-empire, while reducing variance across random data splits.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Sheaf neural networks, Haar framelets, Heterophilous graph learning, Permutation equivariance

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_MNXjOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2(+1)
Read review
Paper summary

The paper proposes a Sheaf–Haar Equivariant Architecture (SHEAR), which combines two approaches for heterophilous graph learning: hierarchical framelet methods and sheaf neural diffusion. A main contribution of this work is to construct the graph hierarchy through a permutation invariant clustering procedure, and thus extending the permutation-equivariance guarantee to the clustering stage itself. The hierarchy construction also incorporates both graph topology and node features, rather than relying solely on graph topology as in previous work such as PEGFAN. In addition, the authors formulate the Haar framelet operators as basis-free orthogonal projectors derived directly from the hierarchy, avoiding explicit basis choices and eigendecomposition. The paper further claims that the resulting hierarchical structure, combined with the sheaf diffusion, provides channel-level guarantees for mitigating oversquashing and oversmoothing. In experiments, SHEAR is evaluated on a range of node-classification benchmarks and achieves competitive performance on several heterophilous datasets.

Critical strengths

The paper extends the permutation-equivariance analysis to the hierarchy construction itself. Under the general-position assumption, the equivariance argument supporting Theorem 1 (page 7), formalized in Theorem 4 of Appendix A, appears to be sound.

Critical weaknesses
  1. There are several flaws in the theoretical guarantees, undermining the claims outside GP in Theorem 1 and the oversquashing guarantee in Theorem 2.
  • The paper’s claims outside the general-position assumption, i.e. the final part of Theorem 1, are not supported by the equivariance argument. Section 4.2(a) identifies fingerprint-identical nodes as “automorphic twins,” but equality of the two-round WL color, GPNN structural id, degree, and feature does not imply they are in the same automorphism orbit (you can consider, for example, the Frucht graph). Raw-index tie breaking can therefore distinguish non-automorphic nodes with identical fingerprints and make the hierarchy depend on node numbering. Moreover, even for genuine automorphic twins, the claim in Remark 3 of the Appendix that such tie breaking leaves predictions unchanged does not follow from downstream equivariance: the downstream model also receives the partition tree, which may already have broken the symmetry between these nodes. Equivariance under jointly permuting the graph, features, and partition does not imply invariance to changing the partition while keeping the graph and features fixed.
  • The proof of Theorem 6 in Appendix C.1 (page 22) appears to conflate a lower bound on the smallest singular value of the coarse diffusion Jacobian, J=I−τMJ=I-\tau M, with a lower bound on the cross-node influence ∣∣Jab∣∣2||J_{ab}||_2. Specifically, a positive σmin⁡(J)\sigma_{\min}(J) does not imply that the off-diagonal Jacobian block JabJ_{ab} between adjacent coarse nodes a≠ba\neq b is nonzero or bounded away from zero. Hence the existence of a coarse path, together with the bound on σmin⁡(J)\sigma_{\min}(J), does not establish the claimed pairwise sensitivity lower bound in Eq. (53).
  1. The overall presentation and organization of the manuscript are also below the standard expected for a top tier conference. The figures are generally of low presentation quality, with overly small text, overlapping labels, and insufficient visual clarity. The manuscript is organized in a rather cluttered manner, making the technical narrative unnecessarily difficult to follow. I also recommend that the authors spend more time polishing the manuscript to address existing issues like the duplicated AI Use Statement.
Questions for authors

Appendix F.2 (page 27) states that switching off sheaf diffusion (T0=Tc=0T_0=T_c=0) leaves the mean accuracy unchanged on Squirrel and Chameleon, but the corresponding numerical results do not appear in any table. Could the authors report the full results of this ablation and clarify the empirical contribution of the sheaf component? If its role is primarily structural, which theoretical guarantees depend essentially on the learned sheaf information? Furthermore, could the authors provide controlled ablations showing whether removing this sheaf information degrades predictive performance or the structural properties addressed by these guarantees?

4 comments

We are grateful for the exceptionally careful reading. Both theoretical objections were correct and have led to substantive repairs. This is also a major presentation revision. We have redrawn the hierarchical graph clustering diagram (Figure 1, p. 4) and the SHEAR architecture overview (Figure 2, p. 7), and placed both in the main text. The figures now explain the clustering construction and the complete architecture at the point where they are introduced. The entire manuscript has been reorganized and compressed for readability, so we strongly encourage the reviewer to re-read the revised full paper.

W1(a). Out-of-GP equivariance. We have removed the incorrect “automorphic twin” assertion and all out-of-GP guarantees. Theorem 1 (main text, p. 8) and Theorem 4 (Appendix A.6, p. 21) now hold only under GP, fixed parameters on a given dataset, evaluation mode, and exact arithmetic. GP requires injective full fingerprint tuples on VV, not merely a convenient hash or an automorphism assumption. Raw-id fallback is deterministic but not equivariant and is used only outside GP. Remark 3 (Appendix A.7, pp. 22–23) contains the Frucht-graph counterexample and explains why downstream equivariance cannot repair a numbering-dependent partition tree. Table 3 (Appendix A.7, p. 23) gives all fifteen clean/stress tests: tie rates at most 2.2% on 13/15 versions, minimum NMI 0.994, and NMI 1.0000 on 12/15 versions. Clean-feature GP holds on only 5/13 main-table columns, so the conditional nature of the theorem is explicit.

W1(b). Original Theorem 6 removed and replaced. The original Theorem 6 and its residual-branch proof have been removed entirely. The corresponding main-text informal statement has also been narrowed to the same bounded coarse-diffusion-budget regime. The replacement Theorem 6 (Appendix C.1, pp. 27–28) is a bounded-coarse-distance, existence-type pathway certificate. Its proof differentiates the coarse cross-block directly. Let the full pre-activation at output block aa be $ Z_a=\sum_c(\Delta_{F^{(L)}})_{ac}W_1^{(L,t)}H_cW_2^{(L,t)} $ and set $ D_a^{tanh}=\mathrm{diag}(\mathrm{tanh}^{'}(\mathrm{vec}Z_a)), $

Define $ Y=(\Delta_{F^{(L)}})_{ab}W_1^{(L,t)}XW_2^{(L,t)}. $

With generated restriction maps held fixed, differentiation with respect to the input block X=HbX=H_b gives

Jab:X→−τL,tDa′⊙YJ_{ab}:X\to-\tau_{L,t}D^{'}_a\odot Y,

where Da′=diag(tanh′(Za)).D^{'}_a=\mathrm{diag}(\mathrm{tanh}^{'}(Z_a)).

Equivalently, in vectorized form, define $ K_{ab}=W_2^{(L,t)T}\otimes(\Delta_{F^{(L)}})_{ab}W_1^{(L,t)}. $

Then, $ \mathrm{vec}(J_{ab}(X))=-\tau_{L,t}D_a^{tanh}K_{ab}\mathrm{vec}(X). $

Consequently, with $ S_{ab}=(\Delta_{F^{(L)}})_{ab}, $

$ \sigma_{min}(J_{ab})\ge |\tau_{L,t}|\mathrm{sech}^2(M_{pre})\sigma_{min}(S_{ab})\sigma_{min}(W_1^{(L,t)})\sigma_{min}(W_2^{(L,t)}). $

Along a shortest coarse path CL(v)=a0,…,ar=CL(u)C_L(v)=a_0,\ldots,a_r=C_L(u), under the stated (ND) conditions and with $ g_L:=\tau_{min}\mathrm{sech}^2(M_{pre})g_\Delta g_{W_1}g_{W_2}>0, $

define $ A=\prod_{\ell=1}^{L}\frac{\theta_{\ell,lp}p_\ell}{s_\ell^{max}} $ , and $ B=\prod_{k=1}^{L}\eta_k^{-}b_k. $

The selected pathway composition JpathJ_{path} satisfies $ \sigma_{min}(J_{path})\ge \lambda_{lift} A B g_L^{,r}g_{diag}^{,T_c-r}. $

Unlike the earlier argument, this bound is derived for JabJ_{ab} itself rather than inferred from the smallest singular value of the full Jacobian. The diagonal factor is evaluated at the full pre-activation ZaZ_a, not only at the (a,b)(a,b) summand, and the sech2(Mpre)\mathrm{sech}^2(M_{pre}) factor is included in gLg_L. ND now explicitly covers the nonzero lift and step-size gains, full-rank coupling blocks and W1,W2W_1,W_2, positive projection and back-projection gains, bounded full pre-activations, and positive endpoint diagonal blocks, and is checkable a posteriori. The theorem remains a per-pathway, bounded-coarse-distance certificate with generated restriction maps held fixed for the stated derivative; it does not claim a total-Jacobian bound or exclude cancellation. The support condition shows that one coarse step advances at most one coarse hop.

W2. Presentation. The two redrawn figures use vector graphics at full text width, with non-overlapping labels. Main-text experiments now include the component-ablation table and a roadmap to the appendices. Proposition 1's proof is moved to Appendix A, p. 19, and long definitions are compressed without removing theorem conditions. The duplicated AI Use Statement has been removed; the single remaining statement appears after the Conclusion.

Q. Full ablation and sheaf dependence. Our earlier sheaf-neutral statement was based only on Squirrel and Chameleon. We have now recomputed all of the previous experiments on the benchmark datasets and found a clear change on Roman-empire: diffusion-off changes 79.80±0.8479.80\pm0.84 to 74.96±1.2274.96\pm1.22 (a decrease of 4.84 points), and scalar stalks give 70.94±0.5770.94\pm0.57 (a decrease of 8.86 points). For comparison, on Geom-GCN Squirrel/Chameleon, diffusion-off gives 69.30±2.28→69.26±1.9269.30\pm2.28\to69.26\pm1.92 and 77.00±1.35→76.38±1.1077.00\pm1.35\to76.38\pm1.10, changes of only 0.04 and 0.62. On filtered Squirrel/Chameleon, it gives 40.90±1.39→40.92±1.4840.90\pm1.39\to40.92\pm1.48 and 43.99±3.68→43.99±3.1643.99\pm3.68\to43.99\pm3.16, both flat to within 0.1. Thus the earlier sheaf-neutral result holds on Squirrel/Chameleon but does not generalize to Roman-empire. We also distinguish sheaf-independent guarantees (scaling sensitivity, exact framelet isometry, fixed budget) from learned-map-dependent ones (ND cross-block gains, learned kernel, and Galerkin equivariance), detailed in Appendix F.2 (pp. 33–34). Diffusion-off leaves the map-independent guarantees—Theorem 5, Corollary 2, Lemma 13, Corollary 3, and Theorem 7(i)–(ii)—unchanged; the ND cross-block and endpoint gains, learned-kernel statement, and Galerkin equivariance depend on generated restriction maps. The reported ablations quantify accuracy effects associated with these components; scalar stalks and frozen maps are component controls, not a complete removal of all sheaf information.

Clustering-only, diffusion-off, and sheaf-component ablations (paper Table 2, p. 10; mean ±\pm std over ten splits).

DataGBSCRef.ΔGBSC\Delta_{\mathrm{GBSC}}No diff.Δoff\Delta_{\mathrm{off}}d=1d{=}1d=2d{=}2d=4d{=}4m=4m{=}4m=32m{=}32
Minesweeper88.83±0.8688.83\pm0.8691.28±0.8191.28\pm0.81+2.45+2.4590.66±0.5390.66\pm0.53+0.62+0.6290.64±0.5590.64\pm0.5590.58±0.5390.58\pm0.5390.70±0.3790.70\pm0.3790.67±0.5790.67\pm0.5791.50±0.6491.50\pm0.64
Tolokers81.61±1.1081.61\pm1.1083.06±0.9083.06\pm0.90+1.45+1.4582.99±0.8382.99\pm0.83+0.07+0.0782.95±0.9782.95\pm0.9782.89±0.9782.89\pm0.9782.81±0.9682.81\pm0.9682.98±0.8482.98\pm0.8482.94±0.9382.94\pm0.93
Roman-empire76.82±1.1276.82\pm1.1279.80±0.8479.80\pm0.84+2.98+2.9874.96±1.2274.96\pm1.22+4.84+4.8470.94±0.5770.94\pm0.5771.49±0.7771.49\pm0.7773.58±1.3073.58\pm1.3077.36±0.8177.36\pm0.8179.90±0.4179.90\pm0.41
Amazon-ratings45.58±0.6745.58\pm0.6746.26±0.8646.26\pm0.86+0.68+0.6845.97±0.9045.97\pm0.90+0.29+0.2945.25±0.7145.25\pm0.7145.32±0.5045.32\pm0.5045.25±0.6845.25\pm0.6846.13±0.7046.13\pm0.7045.86±0.9745.86\pm0.97
Squirrel (filt.)36.88±2.4336.88\pm2.4340.90±1.3940.90\pm1.39+4.02+4.0240.92±1.4840.92\pm1.48−0.02-0.0240.92±1.5440.92\pm1.5440.27±1.6640.27\pm1.6640.52±2.0640.52\pm2.0640.70±1.2740.70\pm1.2738.81±1.6038.81\pm1.60
Chameleon (filt.)41.52±4.1241.52\pm4.1243.99±3.6843.99\pm3.68+2.47+2.4743.99±3.1643.99\pm3.160.000.0043.76±2.7843.76\pm2.7844.10±2.9944.10\pm2.9943.54±3.5743.54\pm3.5743.54±2.9243.54\pm2.9243.65±3.3443.65\pm3.34

Additional diffusion-off results on the remaining nine versions (paper Table 9, Appendix F.2, p. 34).

This appendix table completes the clustering-only and diffusion-off comparison on the other nine versions, so the sheaf-neutral Squirrel/Chameleon results and the Roman-empire decrease can be evaluated in one place.

DataGBSCRef.ΔGBSC\Delta_{\mathrm{GBSC}}No diff.Δoff\Delta_{\mathrm{off}}
Cora86.16±1.5186.16\pm1.5186.48±1.6886.48\pm1.68+0.32+0.3286.40±2.0586.40\pm2.05+0.08+0.08
Citeseer76.14±1.5876.14\pm1.5876.91±1.5476.91\pm1.54+0.77+0.7776.78±1.4076.78\pm1.40+0.13+0.13
Pubmed89.27±0.5489.27\pm0.5489.64±0.4789.64\pm0.47+0.37+0.3789.53±0.4789.53\pm0.47+0.11+0.11
Film35.43±1.2935.43\pm1.2935.51±1.1035.51\pm1.10+0.08+0.0835.57±1.2435.57\pm1.24−0.06-0.06
Texas85.68±5.1485.68\pm5.1486.22±5.9886.22\pm5.98+0.54+0.5487.03±4.9587.03\pm4.95−0.81-0.81
Cornell87.03±6.8287.03\pm6.8286.22±6.5686.22\pm6.56−0.81-0.8185.95±7.0385.95\pm7.03+0.27+0.27
Wisconsin87.65±3.5187.65\pm3.5187.65±3.6287.65\pm3.620.000.0087.06±3.8487.06\pm3.84+0.59+0.59
Squirrel (GG)49.68±3.1849.68\pm3.1869.30±2.2869.30\pm2.28+19.62+19.6269.26±1.9269.26\pm1.92+0.04+0.04
Chameleon (GG)71.47±1.4671.47\pm1.4677.00±1.3577.00\pm1.35+5.53+5.5376.38±1.1076.38\pm1.10+0.62+0.62

Notation used in the ablation tables. GBSC denotes the clustering-only variant with detail channels excluded and validation-selected (h,α)(h,\alpha); Ref. denotes the deployed reference model; No diff. denotes T0=Tc=0T_0=T_c=0 (sheaf diffusion disabled); ΔGBSC=Ref.−GBSC\Delta_{\mathrm{GBSC}}=\mathrm{Ref.}-\mathrm{GBSC} and Δoff=Ref.−No diff.\Delta_{\mathrm{off}}=\mathrm{Ref.}-\mathrm{No\ diff.}, so positive values favor Ref. In Table 2, dd is the stalk dimension and mm is the number of sheaf channels.

Additional experimental evidence and table locations. Further ablations are provided in Appendix F.2 (Table 9, p. 34) and Appendix F.3 (Table 11, p. 35).

We hope these clarifications and revisions address the Reviewer’s concerns. The major revisions are highlighted in blue in the revised manuscript.

Thank you for the great effort you have put into revising the manuscript. However, given the extent of the revisions, I cannot thoroughly reassess the almost rewritten paper within the limited discussion period. Based on the parts I have reviewed, some of my original concerns appear to have been addressed, at least in part. Accordingly, I have increased my overall score from 1 to 2 and my soundness score from 1 to 2.

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

The paper proposes SHEAR (Sheaf–Haar Equivariant Architecture), a multi-scale graph neural network for node classification on heterophilous graphs. Its primary motivation is to address a limitation of PEGFAN: although PEGFAN's framelet network is permutation equivariant given a fixed partition tree, its Ward-clustering procedure for constructing that tree does not guarantee permutation invariance and ignores node features. SHEAR introduces three main components: Topology–feature hierarchical clustering, Basis-free Haar framelets, and Multi-scale sheaf diffusion. The authors establish theoretical results concerning permutation equivariance and channel-level robustness to oversquashing and oversmoothing. Experiments cover 13 node-classification benchmarks, with SHEAR performing particularly well on several heterophilous datasets.

Critical strengths
  1. The paper identifies a meaningful gap in existing permutation-equivariant graph framelet methods. The observation that equivariance of a neural architecture does not automatically guarantee equivariance of its preprocessing and hierarchy-construction stages is important. Replacing Ward clustering with a deterministic topology–feature clustering procedure addresses this issue at the pipeline level rather than merely modifying the downstream GNN.
  2. The architecture integrates several complementary ideas into a coherent framework. Hierarchical coarsening provides multi-scale representations, framelets preserve within-cluster details, and sheaf diffusion offers a more expressive mechanism for transporting information across heterophilous edges than conventional scalar aggregation. Regenerating the restriction maps during each forward pass also avoids relying on a separately pretrained, frozen sheaf encoder.
  3. The paper provides substantial theoretical analysis and diagnostic experiments. The authors analyze equivariance through the clustering, coarsening, framelet, and diffusion stages. They also examine sensitivity to clustering hyperparameters, sheaf capacity, frozen versus trainable restriction maps, and the removal of diffusion. The discussion of the limitations of the oversquashing guarantees is relatively transparent.
Critical weaknesses
  1. The permutation-equivariance guarantee relies on a strong general-position assumption, and the treatment of fingerprint collisions is questionable. The authors argue that when fingerprint ties occur, the residual problem is confined to automorphic twins whose predictions are identical. However, identical two-round WL colors, structural identifiers, degrees, and feature hashes do not generally imply that two nodes are related by a graph automorphism. Two structurally different nodes can remain indistinguishable under these finite-round descriptors.
  2. The empirical contribution of the sheaf machinery appears limited, weakening the motivation for the full architecture. The authors explicitly acknowledge that the sheaf machinery is primarily responsible for structural properties and theoretical guarantees rather than accuracy improvements on these benchmarks. This raises an important question: is the additional complexity of end-to-end sheaf diffusion justified by its practical benefits? The results suggest that much of the observed performance can be achieved through the propagation bank, direct framelet-detail channels, and attention fusion, even without active diffusion.
  3. The oversquashing guarantees are weaker than the headline claims might suggest. Theorem 2 and 3 are legitimate theoretical properties, but they do not establish that the full network is robust to oversquashing and oversmoothing in a strong, end-to-end sense. The distinction between guarantees for individual channels and guarantees for the final prediction function should be made more prominent.
Questions for authors
  1. Can the authors prove that nodes sharing the same fingerprint are necessarily interchangeable under a graph automorphism? If not, how is permutation equivariance maintained when two non-automorphic nodes have identical WL colors, structural identifiers, degrees, and feature hashes? Can the authors provide empirical tests on graphs with duplicated or quantized features?
  2. Since removing diffusion does not change mean accuracy on Squirrel and Chameleon, and freezing the restriction maps causes negligible degradation, what specific empirical benefits justify the additional complexity of end-to-end sheaf diffusion? Can the authors provide broader ablations on datasets where heterophily is particularly challenging?
  3. Can the authors clarify whether the oversquashing results imply a meaningful lower bound on the Jacobian of the final prediction function, rather than only on intermediate channels? How does the guarantee behave when the coarse graph does not contract distances, or when the pathway gain becomes exponentially small?
4 comments

We thank the reviewer for the precise technical criticisms. This revision is a substantial rewrite. We have redrawn the hierarchical graph clustering diagram (Figure 1, p. 4) and the SHEAR architecture overview (Figure 2, p. 7), and placed both in the main text. Figure 1 explains the clustering construction visually, while Figure 2 maps the complete architecture and its per-forward-pass computation. The full paper has been reorganized and compressed, so we encourage the reviewer to re-read the revised full text rather than only the response below.

W1 / Q1. Fingerprint collisions and automorphisms.

Response to W1. The reviewer is correct: fingerprint-identical nodes need not be automorphic, and we have removed the earlier “automorphic twin” claim. Theorem 1 (main text, p. 8) and Theorem 4 (Appendix A.6, p. 21) now require GP, fixed parameters instantiated on the given dataset, evaluation mode, and exact arithmetic. GP requires distinct full fingerprint tuples on VV and, more generally, every branch-affecting comparison key—including CRC32-derived or rounded keys—to be tie-free. Remark 3 (Appendix A.7, pp. 22–23) gives the Frucht-graph counterexample and explains why downstream equivariance cannot repair a numbering-dependent partition tree. No probability-one assertion is made for float32/CRC32.

Direct answer to Q1. No. Nodes sharing the same WL colors, structural identifiers, degrees, and feature hashes are not necessarily interchangeable under a graph automorphism. If two non-automorphic nodes have identical full fingerprints, GP is violated; the raw-id fallback may then be deterministic, but it is not claimed to be equivariant. Thus we guarantee permutation equivariance under the explicitly stated GP condition; no equivariance guarantee is made in the general tie case. As requested, Table 3 (Appendix A.7, p. 23) reports hierarchy-relabeling tests on all fifteen versions, using clean features, 5%/20% copied feature rows, and four-bin quantization, with five random permutations per feature variant. On 13/15 versions, neither the clean tie rate nor the maximum over the three stress variants exceeds 2.2%. The exceptions are Amazon-ratings (clean 10.918%, stress maximum 11.073%) and unfiltered Chameleon (clean 8.213%, stress maximum 8.740%). The lowest tested NMI is 0.994, and 12/15 versions achieve NMI 1.0000 across all four feature variants and all five tested permutations. These NMI results quantify hierarchy stability only; they do not prove prediction-level equivariance outside GP. Clean-feature GP holds on 5 of the 13 main-table columns, not universally.

W2 / Q2. Empirical contribution of sheaf diffusion.

Response to W2. We accept that sheaf diffusion is not universally accuracy-improving and that the earlier Squirrel/Chameleon results alone did not justify the additional complexity on every benchmark. The revised manuscript therefore presents the practical benefit as dataset-dependent and distinguishes the sheaf machinery's structural and theoretical roles from its measured accuracy contribution.

Direct answer to Q2. We re-ran all of the previous experiments on the benchmark datasets to update and broaden the ablations. The three controls answer different questions. Diffusion-off tests the sheaf dynamics: on Roman-empire it changes 79.80±0.8479.80\pm0.84 to 74.96±1.2274.96\pm1.22 (a decrease of 4.84 points), whereas on all four Squirrel/Chameleon configurations it changes the mean by at most 0.7 points. Scalar stalks (d=1d=1) test the incremental contribution of higher-dimensional stalk representations; they do not remove sheaf diffusion altogether. On Roman-empire, they give 70.94±0.5770.94\pm0.57 (a decrease of 8.86 points). Thus these components are empirically load-bearing on Roman-empire, but we do not claim that their additional complexity is universally justified. Frozen maps instead test end-to-end training against pretrained fixed restriction maps. Their accuracy effects are mixed, so we do not claim uniform accuracy superiority for end-to-end training: on the nine versions in Table 8 (Appendix F.2, p. 34), frozen−Ref.\mathrm{frozen}-\mathrm{Ref.} ranges from −3.79-3.79 points on Texas to +0.24+0.24 on Squirrel (GG). The consistent practical advantage of end-to-end SheafMLP is that it removes the pretraining stage and split-dependent restriction-map caches while preserving conditional equivariance.

Sheaf ablation on the remaining nine versions (paper Table 8, Appendix F.2, p. 34; accuracy %\%, mean ±\pm std over ten splits).

DataRef.d=1d{=}1d=2d{=}2d=4d{=}4d=16d{=}16m=4m{=}4m=32m{=}32frozen
Cora86.48±1.6886.48\pm1.6886.08±1.9486.08\pm1.9486.68±1.6186.68\pm1.6186.54±1.4586.54\pm1.4586.10±1.7186.10\pm1.7186.46±1.7286.46\pm1.7286.40±1.7886.40\pm1.7886.14±1.1586.14\pm1.15
Citeseer76.91±1.5476.91\pm1.5476.89±1.4576.89\pm1.4576.78±1.5576.78\pm1.5576.80±1.7076.80\pm1.7076.34±1.7776.34\pm1.7776.91±1.5976.91\pm1.5976.77±1.7576.77\pm1.7576.30±1.7676.30\pm1.76
Pubmed89.64±0.4789.64\pm0.4789.59±0.4789.59\pm0.4789.50±0.4989.50\pm0.4989.61±0.4289.61\pm0.4289.42±0.4189.42\pm0.4189.49±0.4889.49\pm0.4889.48±0.4389.48\pm0.4389.54±0.4089.54\pm0.40
Film35.51±1.1035.51\pm1.1035.16±1.0735.16\pm1.0735.24±1.1035.24\pm1.1035.24±1.0535.24\pm1.0535.45±1.0635.45\pm1.0635.29±0.6635.29\pm0.6635.38±0.9935.38\pm0.9934.88±1.2434.88\pm1.24
Texas86.22±5.9886.22\pm5.9884.59±5.5584.59\pm5.5583.78±4.6883.78\pm4.6885.68±5.4185.68\pm5.4182.97±4.6982.97\pm4.6986.22±4.2686.22\pm4.2685.68±4.9985.68\pm4.9982.43±4.5682.43\pm4.56
Cornell86.22±6.5686.22\pm6.5684.59±6.2984.59\pm6.2986.76±6.9986.76\pm6.9986.22±4.0986.22\pm4.0985.14±6.3185.14\pm6.3186.49±5.6786.49\pm5.6786.49±5.8086.49\pm5.8085.68±6.4085.68\pm6.40
Wisconsin87.65±3.6287.65\pm3.6286.67±3.3786.67\pm3.3786.86±3.9386.86\pm3.9387.25±4.0487.25\pm4.0487.06±4.6687.06\pm4.6687.65±2.7887.65\pm2.7887.06±4.1387.06\pm4.1386.86±4.3086.86\pm4.30
Squirrel (GG)69.30±2.2869.30\pm2.2867.86±1.7167.86\pm1.7167.05±2.4067.05\pm2.4068.36±2.3568.36\pm2.3568.84±1.7468.84\pm1.7469.06±2.6469.06\pm2.6469.24±2.1869.24\pm2.1869.54±2.3269.54\pm2.32
Chameleon (GG)77.00±1.3577.00\pm1.3576.10±1.5676.10\pm1.5676.18±1.0876.18\pm1.0876.34±1.2876.34\pm1.2876.38±1.2976.38\pm1.2976.36±1.4076.36\pm1.4075.90±1.4575.90\pm1.4576.01±1.1676.01\pm1.16

Notation for the frozen-map table. Ref. is the deployed reference model; dd is the stalk dimension and mm is the number of sheaf channels; frozen denotes pretrained, fixed restriction maps rather than end-to-end regenerated maps.

Additional experimental evidence and table locations. Main-text Table 2 (p. 10) and Appendix F.2 Tables 8–9 (p. 34) together cover all fifteen dataset versions; Appendix F.3 Table 11 (p. 35) provides the additional frequency-resolution, direct-detail, attention, and tree-identity diagnostics.

W3 / Q3. Scope of oversquashing/oversmoothing guarantees.

Response to W3. We have narrowed the claims explicitly to channel- and pathway-level properties rather than robustness of the full prediction function in a strong end-to-end sense. The scaling-channel sensitivity bound is given by Theorem 5 and Corollary 2 (Appendix C.1, p. 26), and Remark 5 (p. 26) explicitly limits its fusion transfer to a channel-contribution bound. Theorem 6 (Appendix C.1, pp. 26–28) is now stated as a bounded-coarse-distance, existence-type pathway certificate under ND, with generated restriction maps held fixed for the stated cross-block derivative, not a guarantee of non-cancellation across pathways. Its repaired proof differentiates the cross-block directly using a diagonal tanh-derivative matrix evaluated at the full pre-activation and a Kronecker product, yielding a lower bound on σmin⁡(Jab)\sigma_{\min}(J_{ab}) under explicit full-rank, boundedness of the full pre-activations, and endpoint-positivity conditions. Concretely, if r:=dGL(CL(u),CL(v))≤Tcr:=d_{G_L}(C_L(u),C_L(v))\le T_c and (ND) holds, the selected forward-pass pathway of length 2L+Tc2L+T_c satisfies

\ge \lambda_{\mathrm{lift}} \left(\prod_{\ell=1}^{L}\frac{\theta_{\ell,\mathrm{lp}}p_\ell}{s_\ell^{\max}}\right) \left(\prod_{k=1}^{L}\eta_k^{-}b_k\right) g_L^{\,r}g_{\mathrm{diag}}^{\,T_c-r}, \qquad g_L:=\tau_{\min}\mathrm{sech}^2(M_{\mathrm{pre}})g_\Delta g_{W_1}g_{W_2}>0 .$$ Thus the certificate scales exponentially with $r$ through $g_L^r$; when $g_L<1$, it weakens exponentially, and no distance-uniform final-prediction Jacobian bound follows. The selected pathway composition additionally requires positive lower gains for the lift, projections, back-projections, and endpoint diagonal Jacobian blocks, as specified by ND. For oversmoothing, the exact energy identity is restricted to the single-tree detail sub-bank (Theorem 7, Appendix C.2, pp. 29–30; Lemma 13, p. 28); a concatenated multi-tree bank instead has energy $n_{\mathrm{tree}}\|x\|^2$. The fixed budget is only a scope restriction, not an independent anti-oversmoothing guarantee (Remark 8, p. 31). Theorem 8 (p. 30) gives conditional class-mean contrast bounds for the pre-ReLU, pre-normalization representation; Remark 7 (p. 30) further shows that transfer to the normalized readout requires a positive normalized-channel contrast. **Direct answer to Q3.** No. These results do not imply a meaningful lower bound on the Jacobian of the final prediction function; they bound sensitivity only for the specified intermediate channels or pathways. If the coarse graph does not contract the relevant distances, the coarse distance can remain proportional to the original-graph distance up to cluster-size compression, so the bounded-coarse-distance regime and avoidance of exponential distance decay are not guaranteed. If the pathway gain becomes exponentially small, the certified lower bound also becomes exponentially small and may no longer provide a useful guarantee; no distance-uniform positive lower bound follows. The scaling-channel lower bound likewise degrades with cluster size and $d_{\max}$. Fixed $L\le3$ therefore gives no general asymptotic claim as $d_G(u,v)\to\infty$; pairs outside the coarse diffusion budget must instead rely on the propagation bank and direct detail channels, and we do not claim a uniform lower bound on the final prediction Jacobian. We hope these clarifications and revisions address the Reviewer’s concerns. The major revisions are highlighted in blue in the revised manuscript.
Reviewer_FmfkOpenReview ↗

Reply

Thank the authors for the detailed reply. Due to the inherent issues with the original submission, I would like to maintain my score. Thanks!

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

This paper proposes SHEAR, a Sheaf–Haar Equivariant Architecture for heterophilous graph learning. The method introduces a topology–feature coupled granular-ball clustering strategy to construct a permutation-invariant hierarchical graph structure. Experiments on node-classification benchmarks demonstrate competitive performance.

Critical strengths
  1. The paper proposes a novel topology–feature clustering strategy that incorporates permutation invariance into hierarchical graph construction.

  2. The basis-free Haar framelet formulation avoids eigenvector sign and degeneracy ambiguities.

  3. The paper provides extensive theoretical analyses of permutation equivariance, oversquashing, and oversmoothing.

Critical weaknesses
  1. The overall architecture is highly complex, involving multiple clustering, framelet, and sheaf components, which makes the practical contribution difficult to isolate.

  2. The sheaf components provide only marginal performance improvements, and disabling diffusion does not reduce accuracy on the evaluated datasets.

  3. SHEAR does not consistently outperform existing methods, and its effectiveness across different graph regimes remains unclear.

  4. The font in Figure 1 is too small, making it difficult to read.

  5. The paper's space allocation is unbalanced. Too much space is devoted to theoretical analysis, while the experimental section is insufficient. The main paper contains only one figure and one table.

  6. The AI Use Statement should be placed after the conclusion.

Questions for authors

please see Weaknesses

3 comments

We thank the reviewer for identifying both the isolation and presentation problems. This revision is a substantial rewrite. We have redrawn the hierarchical graph clustering diagram (Figure 1, p. 4) and the SHEAR architecture overview (Figure 2, p. 7), and placed both in the main text. Figure 1 explains the clustering construction, and Figure 2 maps the complete architecture and per-forward-pass computation. The whole manuscript has been reorganized and compressed for readability. We respectfully encourage a fresh reading of the revised full paper.

W1. Complexity and contribution isolation. Table 2 now compares clustering-only GBSC with the full architecture on the six HMH-protocol datasets, and Table 9 extends the comparison to the other nine versions. The full model improves on 13/15 versions, ties on Wisconsin, and decreases only on Cornell. Table 11 (Appendix F.3, p. 35) provides cumulative diagnostics for frequency resolution, direct detail channels, and regularized attention, together with a matched-preset GBSC-versus-Ward tree swap. Thus clustering, framelet-detail channels, attention, and sheaf transport are no longer presented as an inseparable block.

Clustering-only, diffusion-off, and sheaf-component ablations (paper Table 2, p. 10; mean ±\pm std over ten splits).

DataGBSCRef.ΔGBSC\Delta_{\mathrm{GBSC}}No diff.Δoff\Delta_{\mathrm{off}}d=1d{=}1d=2d{=}2d=4d{=}4m=4m{=}4m=32m{=}32
Minesweeper88.83±0.8688.83\pm0.8691.28±0.8191.28\pm0.81+2.45+2.4590.66±0.5390.66\pm0.53+0.62+0.6290.64±0.5590.64\pm0.5590.58±0.5390.58\pm0.5390.70±0.3790.70\pm0.3790.67±0.5790.67\pm0.5791.50±0.6491.50\pm0.64
Tolokers81.61±1.1081.61\pm1.1083.06±0.9083.06\pm0.90+1.45+1.4582.99±0.8382.99\pm0.83+0.07+0.0782.95±0.9782.95\pm0.9782.89±0.9782.89\pm0.9782.81±0.9682.81\pm0.9682.98±0.8482.98\pm0.8482.94±0.9382.94\pm0.93
Roman-empire76.82±1.1276.82\pm1.1279.80±0.8479.80\pm0.84+2.98+2.9874.96±1.2274.96\pm1.22+4.84+4.8470.94±0.5770.94\pm0.5771.49±0.7771.49\pm0.7773.58±1.3073.58\pm1.3077.36±0.8177.36\pm0.8179.90±0.4179.90\pm0.41
Amazon-ratings45.58±0.6745.58\pm0.6746.26±0.8646.26\pm0.86+0.68+0.6845.97±0.9045.97\pm0.90+0.29+0.2945.25±0.7145.25\pm0.7145.32±0.5045.32\pm0.5045.25±0.6845.25\pm0.6846.13±0.7046.13\pm0.7045.86±0.9745.86\pm0.97
Squirrel (filt.)36.88±2.4336.88\pm2.4340.90±1.3940.90\pm1.39+4.02+4.0240.92±1.4840.92\pm1.48−0.02-0.0240.92±1.5440.92\pm1.5440.27±1.6640.27\pm1.6640.52±2.0640.52\pm2.0640.70±1.2740.70\pm1.2738.81±1.6038.81\pm1.60
Chameleon (filt.)41.52±4.1241.52\pm4.1243.99±3.6843.99\pm3.68+2.47+2.4743.99±3.1643.99\pm3.160.000.0043.76±2.7843.76\pm2.7844.10±2.9944.10\pm2.9943.54±3.5743.54\pm3.5743.54±2.9243.54\pm2.9243.65±3.3443.65\pm3.34

Additional diffusion-off results on the remaining nine versions (paper Table 9, Appendix F.2, p. 34).

This table separates clustering-only GBSC from the full model and from diffusion-off: the large GBSC gains on Geom-GCN Squirrel and Chameleon do not imply a large diffusion effect, since No diff. remains close to Ref. on those datasets.

DataGBSCRef.ΔGBSC\Delta_{\mathrm{GBSC}}No diff.Δoff\Delta_{\mathrm{off}}
Cora86.16±1.5186.16\pm1.5186.48±1.6886.48\pm1.68+0.32+0.3286.40±2.0586.40\pm2.05+0.08+0.08
Citeseer76.14±1.5876.14\pm1.5876.91±1.5476.91\pm1.54+0.77+0.7776.78±1.4076.78\pm1.40+0.13+0.13
Pubmed89.27±0.5489.27\pm0.5489.64±0.4789.64\pm0.47+0.37+0.3789.53±0.4789.53\pm0.47+0.11+0.11
Film35.43±1.2935.43\pm1.2935.51±1.1035.51\pm1.10+0.08+0.0835.57±1.2435.57\pm1.24−0.06-0.06
Texas85.68±5.1485.68\pm5.1486.22±5.9886.22\pm5.98+0.54+0.5487.03±4.9587.03\pm4.95−0.81-0.81
Cornell87.03±6.8287.03\pm6.8286.22±6.5686.22\pm6.56−0.81-0.8185.95±7.0385.95\pm7.03+0.27+0.27
Wisconsin87.65±3.5187.65\pm3.5187.65±3.6287.65\pm3.620.000.0087.06±3.8487.06\pm3.84+0.59+0.59
Squirrel (GG)49.68±3.1849.68\pm3.1869.30±2.2869.30\pm2.28+19.62+19.6269.26±1.9269.26\pm1.92+0.04+0.04
Chameleon (GG)71.47±1.4671.47\pm1.4677.00±1.3577.00\pm1.35+5.53+5.5376.38±1.1076.38\pm1.10+0.62+0.62

Notation used in the ablation tables. GBSC denotes the clustering-only variant with detail channels excluded and validation-selected (h,α)(h,\alpha); Ref. denotes the deployed reference model; No diff. denotes T0=Tc=0T_0=T_c=0 (sheaf diffusion disabled); ΔGBSC=Ref.−GBSC\Delta_{\mathrm{GBSC}}=\mathrm{Ref.}-\mathrm{GBSC} and Δoff=Ref.−No diff.\Delta_{\mathrm{off}}=\mathrm{Ref.}-\mathrm{No\ diff.}, so positive values favor Ref. In Table 2, dd is the stalk dimension and mm is the number of sheaf channels.

Diagnostics on unfiltered Geom-GCN graphs (paper Table 11, Appendix F.3, p. 35). These diagnostics examine cumulative frequency-resolution, direct-detail, and regularized-attention changes, and include a matched-preset tree-identity comparison. GBSC is compared with a Ward tree under matched presets; differences are descriptive where per-split standard deviations are unavailable. The Ward tree is slightly higher in this matched-preset diagnostic (69.52/76.75 versus 68.53/76.51); accordingly, GBSC is presented as an invariant and competitive alternative, not as an accuracy improvement over Ward.

Config.Squirrel (GG)Chameleon (GG)
Binary Haar bands (study baseline)49.3949.3971.2371.23
Three-band sheaflet spectral bands50.1850.1871.6971.69
Adaptively bisected Haar high band49.6749.6771.1871.18
+ direct detail channels52.2752.2771.4771.47
+ regularized channel attention69.3069.3076.1476.14
GBSC tree, matched fusion presets68.53±2.4468.53\pm2.4476.51±1.3176.51\pm1.31
Ward tree swap (diagnostic, not invariant)69.52±2.8269.52\pm2.8276.75±1.1976.75\pm1.19

Additional experimental evidence and table locations. Further ablations are provided in Appendix F.2 (Table 8, p. 34; Table 9, p. 34) and Appendix F.3 (Table 11, p. 35).

W2. Marginal sheaf improvements. We also re-ran all of the previous experiments on the benchmark datasets to update the experimental results. On all four Squirrel/Chameleon configurations, diffusion-off changes the mean by at most 0.7 points, whereas on Roman-empire it changes 79.80±0.8479.80\pm0.84 to 74.96±1.2274.96\pm1.22 (a decrease of 4.84 points), and scalar stalks change it to 70.94±0.5770.94\pm0.57 (a decrease of 8.86 points). Thus sheaf transport is dataset-dependent rather than universally necessary: learned transport is a major measured accuracy contributor on Roman-empire, while direct framelet and propagation channels dominate on Squirrel/Chameleon.

W3. Consistency across graph regimes. The ranking statement is now precise: SHEAR is best or second on five same-protocol columns and has the highest numerical means on two additional filtered columns under non-identical masks/protocols, without using the filtered reports for direct ranking. Deficits on Cora, Citeseer, and Pubmed are acknowledged explicitly.

W4. Figure readability. Both the hierarchical graph clustering diagram (Figure 1) and the SHEAR architecture overview (Figure 2) have been redrawn as vector graphics at full text width, with non-overlapping labels.

W5. Space allocation. We have rebalanced the main text from prose-heavy theory exposition to an architecture-led presentation. Figure 2 now decomposes the network into dataset-time Select/Reduce/Connect, per-forward-pass SheafMLP, analysis, synthesis, channel bank, and fusion, so the architecture can be understood structurally rather than through long textual descriptions. Main-text Table 1 reports benchmark results, and Table 2 directly compares clustering-only GBSC, the full model, diffusion-off, and scalar stalks. The main text also contains the architecture equations, channel definitions, and the component-ablation table, while detailed proofs and robustness derivations are consolidated in the appendices.

W6. AI Use Statement. The AI Use Statement remains after the Conclusion, as requested.

We believe these changes answer the isolation, consistency, and presentation concerns without hiding the remaining dataset-dependent limitations. We hope these clarifications and revisions address the Reviewer’s concerns. The major revisions are highlighted in blue in the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.