- 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
- 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, , with a lower bound on the cross-node influence . Specifically, a positive does not imply that the off-diagonal Jacobian block between adjacent coarse nodes is nonzero or bounded away from zero. Hence the existence of a coarse path, together with the bound on , does not establish the claimed pairwise sensitivity lower bound in Eq. (53).
- 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 () 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
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 to (a decrease of 4.84 points), and scalar stalks give (a decrease of 8.86 points). For comparison, on Geom-GCN Squirrel/Chameleon, diffusion-off gives and , changes of only 0.04 and 0.62. On filtered Squirrel/Chameleon, it gives and , 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 std over ten splits).
| Data | GBSC | Ref. | No diff. | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Minesweeper | ||||||||||
| Tolokers | ||||||||||
| Roman-empire | ||||||||||
| Amazon-ratings | ||||||||||
| Squirrel (filt.) | ||||||||||
| Chameleon (filt.) |
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.
| Data | GBSC | Ref. | No diff. | ||
|---|---|---|---|---|---|
| Cora | |||||
| Citeseer | |||||
| Pubmed | |||||
| Film | |||||
| Texas | |||||
| Cornell | |||||
| Wisconsin | |||||
| Squirrel (GG) | |||||
| Chameleon (GG) |
Notation used in the ablation tables. GBSC denotes the clustering-only variant with detail channels excluded and validation-selected ; Ref. denotes the deployed reference model; No diff. denotes (sheaf diffusion disabled); and , so positive values favor Ref. In Table 2, is the stalk dimension and 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.
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 V, 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 a 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=Hb gives
Jab:X→−τL,tDa′⊙Y,
where Da′=diag(tanh′(Za)).
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), 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 Jpath 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 Jab itself rather than inferred from the smallest singular value of the full Jacobian. The diagonal factor is evaluated at the full pre-activation Za, not only at the (a,b) summand, and the sech2(Mpre) factor is included in gL. ND now explicitly covers the nonzero lift and step-size gains, full-rank coupling blocks and W1,W2, 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.