Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation

# Supplemental Items
Source: [https://arxiv.org/html/2605.10975](https://arxiv.org/html/2605.10975)
###### Abstract

Graphs with heterophily, where adjacent nodes carry different labels, are prevalent in real\-world applications, from social networks to molecular interactions\. However, existing spectral Graph Neural Network \(GNN\) approaches tailored for heterophilous graph classification suffer from hub\-dominated \(node with large degree\) aggregation and oversmoothing, as their suboptimal polynomial filters introduce approximation errors and blend distant signals\. To address the degree\-biased aggregation and suboptimal polynomial filtering, we introduce a Hierarchical Multi‐view HAAR \(HMH\), a novel spectral graph‐learning framework that scales in near‑linear time \. HMH first learns feature\- and structure\-aware*signed*affinities via a heterophily\-aware encoder, then constructs a soft graph hierarchy guided by these embeddings\. At each hierarchical level, HMH constructs a sparse, orthonormal, and locality\-aware Haar basis to apply learnable spectral filters in the frequency domain\. Finally, skip\-connection unpooling layers combine outputs from all hierarchical levels back into the original graph, effectively preventing hub domination and long\-range signal bottleneck \(over\-squashing\)\. Experimentation shows that HMH outperforms state‑of‑the‑art spectral baselines, achieving up to a3%3\\%improvement on node classification and7%7\\%points on graph classification datasets, all while maintaining linear scalability\.

Graph Neural Networks, Heterophily, Wavelets, Coarsening, Oversquashing

## 1Introduction

Real\-world graphs are rarely uniform: some regions are relatively homogeneous with nearby nodes sharing similar features and connectivity, while others are heterophilous, where neighbors differ sharply in both attributes and structure\. In graph learning, homogeneous areas typically benefit from smoothing/averaging \(low\-pass filtering\), whereas heterophellous regions require contrast amplification \(high\-pass filtering\)\(Chien et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib5)\)\. Spectral Graph Neural Networks \(GNNs\) aim to capture such signals by projecting onto a global eigenbasis of the graph Laplacian or its polynomial approximation\(Zhu & Koniusz,,[2021](https://arxiv.org/html/2605.10975#bib.bib39)\)\. Using a global basis, whether it is explicitly precomputed\(He et al\.,,[2022](https://arxiv.org/html/2605.10975#bib.bib15)\)or implicitly approximated using high\-order polynomials\(Huang et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib17)\), often sacrifices graph locality\. The induced filters can spread energy across many hops and mix signals from semantically unrelated regions, which may blur fine\-grained structural distinctions among small clusters that are especially important under heterophily\(He et al\.,,[2022](https://arxiv.org/html/2605.10975#bib.bib15)\)\.

In addition, conventional polynomial bases \(e\.g\., Chebyshev\) are limited by the conditioning of polynomial parameterizations on graphs\. In the theoretical setting, Chebyshev polynomials are orthogonal on\[−1,1\]\[\-1,1\]under a*continuous*weight function \(w​\(x\)=1/1−x2w\(x\)=1/\\sqrt\{1\-x^\{2\}\}\)\. Although graph filters rescale the Laplacian spectrum to\[−1,1\]\[\-1,1\], a real graph does not provide this continuous weighting since it is governed by a*discrete*spectral measure \(the rescaled eigenvalues and their multiplicities\), leading to leakage across frequency channels and reduced effective expressivity of the filter bank\(Guo & Wei,,[2023](https://arxiv.org/html/2605.10975#bib.bib13)\)\. Moreover, high\-order polynomial approximations can be prone to error and the resulting bases are typically*static*and not adaptive to local feature/structure heterophily\(Huang et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib17); Zheng,,[2024](https://arxiv.org/html/2605.10975#bib.bib38)\)\.

On the other hand, spatial GNNs filter graph signals directly by employing neighborhood aggregation and often exhibit an inherent low\-pass bias\(Zhu & Koniusz,,[2021](https://arxiv.org/html/2605.10975#bib.bib39)\)\. To address this, recently proposed signed message\-passing methods \(SMPs\) incorporate edge signs to learn the contrast between the node signals\. SMP based models suffer from sign cancellation across depth \(e\.g\., every two layers\), progressively erasing heterophilous contrasts\(Liang et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib22)\)\. To prevent signal\-signed flipping, several spatial models employ Chunked Message Passing \(CMP\) approaches, which bucketize neighbors by similarity and subsequently consolidate all chunks/buckets via a global aggregation step\(Pei et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib27)\)\. Both approaches mix signals across graph regions\. This mixing is particularly detrimental in degree\-imbalanced graphs: densely connected, high\-degree hub nodes can dominate message passing, eroding the signals of small \(spoke\) heterophilous clusters, leading to indistinguishable features \(hub domination\) and ultimately exacerbating signal oversmoothing\(Keriven,,[2022](https://arxiv.org/html/2605.10975#bib.bib18)\)\. These limitations motivate a filter that is \(i\) spectrally well\-conditioned to prevent leakage across frequency channels, \(ii\) localized to avoid long\-range contamination, and \(iii\) learns high\-pass and low\-pass filters without sign cancellation pathology\.

![Refer to caption](https://arxiv.org/html/2605.10975v1/x1.png)Figure 1:Overview of the proposed HMH framework\. The process begins with the input graph and node features, followed by adaptive heterophilous encoding and hierarchical graph coarsening\. At each level, class\-aware Haar bases are constructed, and diagonal spectral filtering is performed\. Finally, multi\-scale skip\-connected fusion aggregates information from all levels\.To address the existing limitations, we propose a novel model, referred to as HMH\. The HMH first introduces an adaptive heterophilous encoder that assigns positive weights to homophilous edges and persistent negative weights to heterophilous edges\. The encoder is also designed to serve as an adaptive high\-pass and low\-pass filter, thereby preserving the high‑frequency contrasts that conventional static methods typically fail\. The encoder also incorporates structural similarity and feature affinities to generate per\-node scores that facilitate hierarchical clustering \(coarsening\)\. At each hierarchical level, the encoder is used to construct the Haar basis, which forms a sparse, orthonormal eigenbasis explicitly capable of capturing localized low\-frequency \(within\-cluster\) and high\-frequency \(between\-cluster\) variations\. Diagonal spectral filtering in this basis selectively amplifies heterophilous channels and attenuates hub\-dominated signals\. Skip\-connected unpooling is employed to reintegrate filtered signals from each level into the original nodes, enriching them with multi\-scale context\. The coarsening hierarchy reduces effective path lengths logarithmically, allowing gradients and information to propagate without the exponential decay caused by oversquashing\(Di Giovanni et al\.,,[2023](https://arxiv.org/html/2605.10975#bib.bib7)\)\. Finally, we leverage the hierarchical tree to perform graph pooling for graph classification, reducing the pooling overhead from quadraticO​\(n2\)O\(n^\{2\}\)in prior methods to near\-linearO​\(n\)O\(n\)time\(Li et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib21)\)\.

The contributions of the paper are: \(i\) We introduce a label\-free adaptive signed affinity that prevents sign cancellation\. \(ii\) We introduce the first framework that constructs an orthonormal, multi\-scale, sparse spectral basis in near\-linear time, scaling effortlessly to large graphs; \(iii\) We rigorously prove and empirically confirm that conventional GNNs suffer fromhub domination,oversmoothing, andoversquashing, whereas our proposedHMHovercomes these pathologies; and \(iv\) we demonstrate that HMH achieves state‑of‑the‑art \(SOTA\) accuracy on both node and graph classification tasks while maintaining linear scalability\.

## 2Related works

Spectral Filtering:Early models, like ChebNet\(He et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib14)\), used truncated Chebyshev polynomials to approximate the eigenbasis\. Conversely, Generalized Page Rank GNN \(GPR\-GNN\)\(Chien et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib5)\)utilizes generalized PageRank weights with monomial bases for approximations\. In contrast, BernNet\(He et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib14)\)and JacobiConv\(Wang & Zhang,,[2022](https://arxiv.org/html/2605.10975#bib.bib33)\)provide Bernstein and Jacobi polynomials, respectively, to enhance the interpretability and adaptability of the bases\. ChebNetII\(He et al\.,,[2022](https://arxiv.org/html/2605.10975#bib.bib15)\)addressed the issue of Chebyshev polynomials overfitting by employing interpolation, whereas OptBasisGNN\(Guo & Wei,,[2023](https://arxiv.org/html/2605.10975#bib.bib13)\)aimed to make basis polynomials orthogonal to accelerate convergence\. The above methodologies continue to employ dense, fixed graph\-wide bases that prevent global message mixing\. Hierarchical Graph Learning:Learnable pooling methods, such as DiffPool\(Ying et al\.,,[2018](https://arxiv.org/html/2605.10975#bib.bib37)\), SAGPool\(Lee et al\.,,[2019](https://arxiv.org/html/2605.10975#bib.bib19)\), TopKPool\(Diehl,,[2019](https://arxiv.org/html/2605.10975#bib.bib8)\), utilize node\-scoring to coarsen homophilous graphs at a singular resolution incurringO​\(n2\)O\(n^\{2\}\)computational cost\(Li et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib21)\)\. EigenPool\(Ma et al\.,,[2019](https://arxiv.org/html/2605.10975#bib.bib25)\)and Haar\-based pooling employ an expensive eigendecomposition to coarsen the graph, incurring anO​\(n3\)O\(n^\{3\}\)computational cost, which constrains scalability and overlooks local heterophily\(Wang et al\.,,[2020](https://arxiv.org/html/2605.10975#bib.bib32)\)\.

## 3Preliminaries

LetG=\(V,E\)G=\(V,E\)be a simple, undirected graph, whereVVdenotes the set of vertices andEEdenotes the set of edges\. Its adjacency matrixA∈ℝn×nA\\in\\mathbb\{R\}^\{n\\times n\}has entriesAi​j=1A\_\{ij\}=1ifi,j∈E\{i,j\}\\in Eand0otherwise, andD=diag​\(A​1\)D=\\mathrm\{diag\}\(A\\textbf\{1\}\)is the degree matrix, where1is the all\-ones vector\. Given node featuresX∈ℝm×dX\\in\\mathbb\{R\}^\{m\\times d\}and normalized Laplacianℒ=U​Λ​U⊤\\mathcal\{L\}=U\\Lambda U^\{\\top\}, a spectral layer rescales graph Fourier components byg​\(ℒ\)​X=U​g​\(Λ\)​U⊤​X,g\(\\mathcal\{L\}\)X=U\\,g\(\\Lambda\)\\,U^\{\\top\}X,whereggis spectral filter\. The polynomiaspectral methods implementsggwith a polynomial,g​\(L\)≈∑r=0Rθr​Lrg\(L\)\\;\\approx\\;\\sum\_\{r=0\}^\{R\}\\theta\_\{r\}\\,L^\{r\}, whereR∈ℕR\\in\\mathbb\{N\}is the polynomial order\. Withkklayer message–passing, a GNN learns the graph signal as a polynomial through a propagation operatorPP, which essentially induces the global eigenbasis of the propagation operatorPPgiven by

H\(k\)≈∑r=0kΘr​Pr​X=gP​\(P\)​X=UP​gP​\(ΛP\)​UP⊤​X,H^\{\(k\)\}\\approx\\sum\_\{r=0\}^\{k\}\\Theta\_\{r\}\\,P^\{r\}\\,X=g\_\{P\}\(P\)\\,X\\;=U\_\{P\}\\,g\_\{P\}\(\\Lambda\_\{P\}\)\\,U\_\{P\}^\{\\top\}X,\(1\)whereUP​ΛP​UP⊤U\_\{P\}\\Lambda\_\{P\}U\_\{P\}^\{\\top\}is the eigendecomposition ofPPandΘr\\Theta\_\{r\}are learnable linear parameters Real‐world graphs often exhibit different levels of homophily in different regions of the graph\. We quantify*homophily*asHlab=1\|E\|​∑\(u,v\)∈E\[yu=yv\],H\_\{\\mathrm\{lab\}\}=\\frac\{1\}\{\|E\|\}\\sum\_\{\(u,v\)\\in E\}\[y\_\{u\}=y\_\{v\}\],whereyyis the node label\. To address the discrepancy between nodes homophily, thesign\- based message passing \(SMP\)\(Liang et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib22); Chien et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib5)\)algorithms introduced signed adjacency matrix,SS, defined asSu​v=\+1S\_\{uv\}=\+1if\(u,v\)∈E\(u,v\)\\in Eandyu=yvy\_\{u\}=y\_\{v\},Su​v=−1S\_\{uv\}=\-1if\(u,v\)∈E\(u,v\)\\in Eandyu≠yvy\_\{u\}\\neq y\_\{v\}\. So the feature of each layer is updated as,H\(k\+1\)=σ​\(S​H\(k\)​W\(k\)\),H\(0\)=X,H^\{\(k\+1\)\}=\\sigma\\\!\\big\(S\\,H^\{\(k\)\}W^\{\(k\)\}\\big\),\\quad H^\{\(0\)\}=X,whereSSworks as a propagation operator andWWis weight matrix\. Using \([1](https://arxiv.org/html/2605.10975#S3.E1)\), thekk\-layer SMP can be expressed as a spectral filter in the global basis ofSS\. To solve the sign flipping of SMP,chunked multi\-track aggregation \(CMA\)\-based methods\(Pei et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib27)\)propose to split each node’s neighbors intotttracks \(e\.g\., homo/hetero\) with learned attentionsi​j,ts\_\{ij,t\}and aggregate messagesmi,tm\_\{i,t\}per tracktt\. Vanilla GCNs are known to exhibit two depth\-related pathologies\.\(i\) Oversmoothingoccurs as the number of layers grows and all node embeddings converge to their class means\(Epping et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib10)\)\.\(ii\) Oversquashing\(Topping et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib31)\), which occurs when gradients \(or messages\) from distant nodes decay exponentially with graph distance, preventing long\-range information flow\. While many heterophilous GNNs aim to address these issues, their limitations under hub\-dominated graphs and suboptimal bases remain, as discussed next\.

## 4Limitations of Existing Models

We highlight two failure modes in existing graph learning models that together explain the poor performance on hub\-dominated graphs\(Luan et al\.,,[2022](https://arxiv.org/html/2605.10975#bib.bib24); Guo & Wei,,[2023](https://arxiv.org/html/2605.10975#bib.bib13)\)\. Limitation 1: Hub Domination\.Consider two small clustersAAandBBdensely connected to a dominant Hub regionH′H^\{\\prime\}\(either a single high\-degree node or a homophilous cluster of high\-degree nodes\)\. Due toH′H^\{\\prime\}’s significantly higher degree relative to the spokes \(small cluster of low degree nodes\), the resulting higher signal contribution statistically overwhelms the local features ofAAandBBduring message passing\. DespiteAAandBBhaving distinct class labels, this “Hub Domination” causes the embeddings to drift toward a common hub\-induced representation, erasing the decision boundary between them\. The following theorem establishes the theoretical basis of hub domination, and empirical results and analyses are presented later in Table[3](https://arxiv.org/html/2605.10975#S6.T3)\.

![Refer to caption](https://arxiv.org/html/2605.10975v1/x2.png)Figure 2:Hub aliasing phenomenon in cluster \(AA,BB,H′H^\{\\prime\}\)\.###### Theorem 4\.1\.

The representational distance between any node inAAand any node inBBdecays exponentially after multiple layers of SMP or CMA\. \(Proof in Appendix[A](https://arxiv.org/html/2605.10975#A1)\)

Limitation 2: Suboptimal basis\.Fixed polynomial bases \(e\.g\., Jacobi, Chebyshev\) assume continuous orthogonality, which does not hold on the discrete spectrum of irregular graphs\. Consequently, polynomial basis become correlated, hindering the model’s ability to decouple frequency components and adapt to local graph structures\.

## 5Methodology

In this section, we present the proposed HMH spectral graph\-learning framework\. HMH performs multi\-resolution analysis of graph signals, capturing both local interactions and global structural trends, as shown in Fig\.[1](https://arxiv.org/html/2605.10975#S1.F1)\. The pipeline begins with a heterophily\-aware encoder that computes node scores from local features and structural cues\. These scores guide a clustering step that forms the supernodes for the next level\. We apply the same encoder–clustering procedure recursively at every level to construct the full hierarchy\. At each level, we build a level\-specific spectral basisU\(ℓ\)U^\{\(\\ell\)\}, enabling diagonal filtering in the transformed domain and multi\-scale fusion back to the original graph\. We detail each component below\.

### 5\.1Heterophilous Encoder

The goal is to introduce an adaptive encoder that generates node scores based on feature and structural similarity, guiding the graph coarsening process\. In addition, the encoder should act as a learnable high\-pass and low\-pass filter by integrating the feature affinities and structural patterns to determine node similarity\. We follow a two\-step process: \(i\) Adaptive Similarity Computation\.At layerkk, let the node embeddings beH\(k\)∈ℝn×dkH^\{\(k\)\}\\in\\mathbb\{R\}^\{n\\times d\_\{k\}\}andhih\_\{i\}is theiith node embedding\. For each neighborj∈𝒩​\(i\)j\\in\\mathcal\{N\}\(i\), we compute \(I\)feature affinitySatt\(k\)​\(i,j\)=σ​\(𝐰att⊤​\[hi\(k\)∥hj\(k\)\]\)S\_\{\\mathrm\{att\}\}^\{\(k\)\}\(i,j\)=\\sigma\\\!\\bigl\(\\mathbf\{w\}\_\{\\mathrm\{att\}\}^\{\\top\}\[h\_\{i\}^\{\(k\)\}\\\|h\_\{j\}^\{\(k\)\}\]\\bigr\), where𝐰att\\mathbf\{w\}\_\{\\mathrm\{att\}\}is learnable weights and ; and \(II\)structural similaritySstruct\(k\)​\(i,j\)=\|𝒩2​\(i\)∩𝒩2​\(j\)\|\|𝒩2​\(i\)∪𝒩2​\(j\)\|S\_\{\\mathrm\{struct\}\}^\{\(k\)\}\(i,j\)=\\frac\{\|\\mathcal\{N\}\_\{2\}\(i\)\\cap\\mathcal\{N\}\_\{2\}\(j\)\|\}\{\|\\mathcal\{N\}\_\{2\}\(i\)\\cup\\mathcal\{N\}\_\{2\}\(j\)\|\}, where we use two\-hop neighbors𝒩2\\mathcal\{N\_\{2\}\}to find similarity using shared neighbors beyond direct adjacency\. We integrate scores to form a normalized similarity matrixS~\(k\)\\widetilde\{S\}^\{\(k\)\}, where each

S~i​j\(k\)=softmaxj∈𝒩​\(i\)​\(Satt\(k\)​\(i,j\)\+Sstruct\(k\)​\(i,j\)\)\.\\widetilde\{S\}^\{\(k\)\}\_\{ij\}=\\mathrm\{softmax\}\_\{j\\in\\mathcal\{N\}\(i\)\}\\\!\\left\(S\_\{\\mathrm\{att\}\}^\{\(k\)\}\(i,j\)\+S\_\{\\mathrm\{struct\}\}^\{\(k\)\}\(i,j\)\\right\)\.\(2\)
\(ii\) Adaptive Signed Adjacency & Propagation\.To capture both homophily and heterophily, we transform the binary adjacencyAAinto a signed, continuous matrixAadp\(k\)A\_\{\\mathrm\{adp\}\}^\{\(k\)\}\. We assign positive weights to similar nodes and negative weights to dissimilar ones by computing

Aadp\(k\)=\(2​S~\(k\)−𝟏𝟏⊤\)⊙A\(k\)=\(2​S~\(k\)−1\)⊙A\(k\)\.A\_\{\\mathrm\{adp\}\}^\{\(k\)\}\\;=\\;\\bigl\(2\\widetilde\{S\}^\{\(k\)\}\-\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\bigr\)\\odot A^\{\(k\)\}\\;=\\;\(2\\widetilde\{S\}^\{\(k\)\}\-1\)\\odot A^\{\(k\)\}\.\(3\)
where⊙\\odotis element\-wise product\. Alternatively, we set\(Aadp\(k\)\)i,j=2​S~i​j\(k\)−1\(A\_\{\\mathrm\{adp\}\}^\{\(k\)\}\)\_\{i,j\}=2\\widetilde\{S\}\_\{ij\}^\{\(k\)\}\-1ifAi​j=1A\_\{ij\}=1, and0otherwise\. This creates a dynamic filtering mechanism\. That is, when two nodes are highly similar \(e\.g\.,S~≈0\.9\\widetilde\{S\}\\\!\\approx\\\!0\.9\), the resulting edge weight is positive \(about0\.90\.9\) and message passing behaves like a low\-pass operator by averaging neighbor features\. In contrast, low similarity \(e\.g\.,S~≈0\.4\\widetilde\{S\}\\\!\\approx\\\!0\.4\) yields a negative weight, which emphasizes differences between neighbors and thus behaves like a high\-pass \(sharpening\) operator\. Using this graph\-agnostic weighting, the encoder updates the feature as

Z\(k\+1\)=σ​\(Aadp\(k\)​Z\(k\)​W\(k\)\)\.Z^\{\(k\+1\)\}=\\sigma\\big\(A\_\{\\mathrm\{adp\}\}^\{\(k\)\}Z^\{\(k\)\}W^\{\(k\)\}\\big\)\.\(4\)For every layerkk, we recalculate theS~\(k\)\\widetilde\{S\}^\{\(k\)\}, thereby updatingAadp\(k\)A\_\{\\mathrm\{adp\}\}^\{\(k\)\}according to \([3](https://arxiv.org/html/2605.10975#S5.E3)\), which mitigates the sign flipping and serves as an adaptive filter demonstrated in the following theorems\.

###### Theorem 5\.1\.

UpdatingAa​d​a​pA\_\{adap\}using \([3](https://arxiv.org/html/2605.10975#S5.E3)\) with \([2](https://arxiv.org/html/2605.10975#S5.E2)\) at every propagation layerkkmitigates the periodic sign\-flipping limitation of SMP\. \(Proof in Appendix[B](https://arxiv.org/html/2605.10975#A2)\)

###### Theorem 5\.2\.

At every layerℓ\\ellof message passing, theAa​d​pA\_\{adp\}acts as an adaptive combination of low\-pass and high\-pass filter\. \(Proof in Appendix[C](https://arxiv.org/html/2605.10975#A3)\)

### 5\.2Haar\-Tree Formulation

To construct the hierarchy, we utilize the encoder embeddingsZ\(ℓ\)=Encoder​\(X\(ℓ\),Aadp\(ℓ\)\)Z^\{\(\\ell\)\}=\\mathrm\{Encoder\}\(X^\{\(\\ell\)\},A\_\{\\mathrm\{adp\}\}^\{\(\\ell\)\}\)as node scores\. These scores guide the partitioning of nodes into clusters and the subsequent aggregation of features and edges for the formed cluster via three specific steps:

\(i\) Cluster Prototype:To coarsen the tree at a predefined ratioRR, we set the target number of nodes for the coarsened trees asKℓ=max⁡\(1,⌊\|V\(ℓ\)\|⋅R⌋\)K\_\{\\ell\}=\\max\\left\(1,\\,\\left\\lfloor\|V^\{\(\\ell\)\}\|\\cdot R\\right\\rfloor\\right\)\. We employkk\-means\+\+\(Bahmani et al\.,,[2012](https://arxiv.org/html/2605.10975#bib.bib1)\)onZ\(ℓ\)Z^\{\(\\ell\)\}to obtainKℓK\_\{\\ell\}the number of centroids\{pk\(ℓ\)\}k=1Kℓ⊂ℝd′\\\{p\_\{k\}^\{\(\\ell\)\}\\\}\_\{k=1\}^\{K\_\{\\ell\}\}\\subset\\mathbb\{R\}^\{d^\{\\prime\}\}, which serves as prototypes of cluster\{Ck\(ℓ\)\}k=1Kℓ\\\{C\_\{k\}^\{\(\\ell\)\}\\\}\_\{k=1\}^\{K\_\{\\ell\}\}\.

\(ii\) Weighted Soft Assignment:Rather than assigning each node to a single cluster, we use a probabilistic \(soft\) membership over all prototypes\. For each nodei∈V\(ℓ\)i\\in V^\{\(\\ell\)\}and prototypepk\(ℓ\)p\_\{k\}^\{\(\\ell\)\}, we compute an affinity scoreΩi​k\(ℓ\)=⟨Zi\(ℓ\),pk\(ℓ\)⟩,\\Omega\_\{ik\}^\{\(\\ell\)\}=\\langle Z\_\{i\}^\{\(\\ell\)\},\\,p\_\{k\}^\{\(\\ell\)\}\\rangle,wherek=1,…,Kℓk=1,\\dots,K\_\{\\ell\}, where⟨\.,\.⟩\\langle\.,\.\\rangledenotes inner product\. To control the sharpness of the decision boundaries, we compute the row\-stochastic assignment matrix as\(As\(ℓ\)\)i​k=softmaxk​\(Ωi​kτ\),\(A\_\{s\}^\{\(\\ell\)\}\)\_\{ik\}=\\mathrm\{softmax\}\_\{k\}\\left\(\\frac\{\\Omega\_\{ik\}\}\{\\tau\}\\right\),whereτ\>0\\tau\>0is a temperature parameter that controls the sharpness\.

\(iii\) Feature and Edge Aggregation:Given the node‑featureX\(ℓ\)∈ℝ\|V\(ℓ\)\|×dℓX^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{\\,\|V^\{\(\\ell\)\}\|\\times d\_\{\\ell\}\}and the adjacencyA\(ℓ\)∈\{0,1\}\|V\(ℓ\)\|×\|V\(ℓ\)\|A^\{\(\\ell\)\}\\in\\\{0,1\\\}^\{\\,\|V^\{\(\\ell\)\}\|\\times\|V^\{\(\\ell\)\}\|\}at levelℓ\\ell, we obtain the next‑level \(ℓ\+1\\ell\+1\) coarsened graph and its adjacency as

X\(ℓ\+1\)\\displaystyle X^\{\(\\ell\+1\)\}=\(As\(ℓ\)\)⊤​X\(ℓ\)∈ℝKℓ×dℓ,\\displaystyle=\\bigl\(A\_\{s\}^\{\(\\ell\)\}\\bigr\)^\{\\top\}X^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{\\,K\_\{\\ell\}\\times d\_\{\\ell\}\},\(5\)Ak​k′\(ℓ\+1\)\\displaystyle A^\{\(\\ell\+1\)\}\_\{kk^\{\\prime\}\}=∑t∈Ck\(ℓ\)∑q∈Ck′\(ℓ\)\(A\)t​q\(ℓ\)∈ℝKℓ×Kℓ,\\displaystyle=\\sum\_\{t\\in C\_\{k\}^\{\(\\ell\)\}\}\\sum\_\{q\\in C\_\{k^\{\\prime\}\}^\{\(\\ell\)\}\}\(A\)\_\{tq\}^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{\\,K\_\{\\ell\}\\times K\_\{\\ell\}\},\(6\)where, at levelℓ\\ell, letk,k′∈\{1,…,Kℓ\}k,k^\{\\prime\}\\in\\\{1,\\dots,K\_\{\\ell\}\\\}index the coarse \(cluster\) nodes, whilet,q∈V\(ℓ\)t,q\\in V^\{\(\\ell\)\}index the fine nodes\. Thus, each coarse node’s feature is the probability\-weighted sum of its children’s features, and two coarse nodes are adjacent whenever at least one edge exists between their constituent nodes at levelℓ\\ell\. Non\-zero entries\(As\(ℓ\)\)i​k\>0\(A\_\{s\}^\{\(\\ell\)\}\)\_\{ik\}\>0means that a fine nodeiicontributes to a coarse nodekkat levelℓ\+1\\ell\+1\. Collecting these indices across levels yields the parent–child links of the Haar tree\. The coarsening loop repeats until\|V\(L\)\|≤ht\|V^\{\(L\)\}\|\\leq h\_\{t\}, wherehth\_\{t\}is a user‑specified threshold\. Next, we discuss the algorithms to compute the class\-aware Haar basisUℓU^\{\\ell\}from the Haar tree\.

### 5\.3Class\-aware Haar Bases

The coarsening builds a hierarchy\{G\(ℓ\)\}ℓ=0L\\\{G^\{\(\\ell\)\}\\\}\_\{\\ell=0\}^\{L\}by iteratively merging nodes from the input graph \(L=0L=0\) to the coarsest levelLLutilizing the encoder, which may collapse into a single supernode depending on the ratioRR\. At each level L, supernodes represent clusters from the previous level\. We construct a spectral basisU\(ℓ\)U^\{\(\\ell\)\}that decomposes signals into inter\-cluster contrasts and intra\-cluster details, enabling level\-specific low\-/high\-pass filtering\. The bases are built bottom\-up: we construct the coarsest basis \(intra\-cluster only ifKL=1K\_\{L\}=1\) and recursively lift it to finer levels to preserve global structure while adding localized detail\.

Coarsest level \(ℓ=L\\ell=L\)\.Let the coarsest graphG\(L\)G^\{\(L\)\}consist ofKL=\|V\(L\)\|K\_\{L\}=\|V^\{\(L\)\}\|supernodes\. We constructU\(L\)∈ℝKL×KLU^\{\(L\)\}\\in\\mathbb\{R\}^\{K\_\{L\}\\times K\_\{L\}\}from a global scaling vector andKL−1K\_\{L\}\-1inter\-supernode wavelets \(ifKL\>1K\_\{L\}\>1\)\.

\(1\) Global scaling vector\.To capture the global low\-frequency \(mean\) component, we can define the basis as

usc\(L\)=1KL​\[1,1,…,1\]⊤\.u\_\{\\mathrm\{sc\}\}^\{\(L\)\}=\\frac\{1\}\{\\sqrt\{K\_\{L\}\}\}\[1,1,\\ldots,1\]^\{\\top\}\.

\(2\) Inter\-supernode \(cluster\) wavelets \(coarse contrasts\)\.IfKL\>1K\_\{L\}\>1, we need basis vectors to capture the differences*between*these supernodes\. We constructKL−1K\_\{L\}\-1orthogonal wavelets using a standard recursive difference method\. Forq=1,…,KL−1q=1,\\dots,K\_\{L\}\-1, theqq\-th wavelet contrasts theqq\-th supernode against the average of all subsequent supernodes:

wcoarse;q\(L\)=KL−q\+1KL−q​\(eq−1KL−q​∑t=q\+1KLet\),w\_\{\\mathrm\{coarse\};\\,q\}^\{\(L\)\}=\\sqrt\{\\frac\{K\_\{L\}\-q\+1\}\{K\_\{L\}\-q\}\}\\left\(e\_\{q\}\-\\frac\{1\}\{K\_\{L\}\-q\}\\sum\_\{t=q\+1\}^\{K\_\{L\}\}e\_\{t\}\\right\),\(7\)whereeqe\_\{q\}is the standard basis vector at indexqq\(a one\-hot vector with\(eq\)q=1\(e\_\{q\}\)\_\{q\}=1and zeros elsewhere\)\. These vectors have zero mean, unit norm, and are mutually orthogonal\. HenceU\(L\)=\[usc\(L\)​∣⋯∣​wcoarse;KL−1\(L\)\]U^\{\(L\)\}=\[u\_\{\\mathrm\{sc\}\}^\{\(L\)\}\\mid\\cdots\\mid w\_\{\\mathrm\{coarse\};K\_\{L\}\-1\}^\{\(L\)\}\]is orthonormal\.

Recursive lifting to finer levels \(ℓ=L−1,…,0\\ell=L\-1,\\dots,0\)\.At levelℓ\\ell, fine nodesV\(ℓ\)V^\{\(\\ell\)\}are softly assigned toKℓ\+1=\|V\(ℓ\+1\)\|K\_\{\\ell\+1\}=\|V^\{\(\\ell\+1\)\}\|clusters throughAs\(ℓ\)∈ℝ\|V\(ℓ\)\|×Kℓ\+1A\_\{s\}^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{\|V^\{\(\\ell\)\}\|\\times K\_\{\\ell\+1\}\}\. For Haar basis construction, we hardenAs\(ℓ\)A\_\{s\}^\{\(\\ell\)\}by keeping only the maximum entry per row asA~s\(ℓ\)\(i,k\)=𝟏\[k=argmaxt\(As\(ℓ\)\)i​t\]\\tilde\{A\}\_\{s\}^\{\(\\ell\)\}\(i,k\)=\\mathbf\{1\}\\\!\\left\[k=\\arg\\max\_\{t\}\(A\_\{s\}^\{\(\\ell\)\}\)\_\{it\}\\right\]\. We then constructU\(ℓ\)U^\{\(\\ell\)\}in three parts\.

\(1\) Lift the global scaling vector\.To ensure that each node inherits the coarse\-level average of its parent cluster, givenusc\(ℓ\+1\)∈ℝKℓ\+1u\_\{\\mathrm\{sc\}\}^\{\(\\ell\+1\)\}\\in\\mathbb\{R\}^\{K\_\{\\ell\+1\}\}, we lift the mean to the finer graph as

usc\(ℓ\)=A~s\(ℓ\)​usc\(ℓ\+1\)∈ℝ\|V\(ℓ\)\|\.u\_\{\\mathrm\{sc\}\}^\{\(\\ell\)\}=\\tilde\{A\}\_\{s\}^\{\(\\ell\)\}u\_\{\\mathrm\{sc\}\}^\{\(\\ell\+1\)\}\\in\\mathbb\{R\}^\{\|V^\{\(\\ell\)\}\|\}\.\(8\)
\(2\) Inter\-cluster wavelets \(between clusters\)\.Treating theKℓK\_\{\\ell\}clusters as “supernodes,” we constructKℓ−1K\_\{\\ell\}\-1orthogonal wavelets that capture differences*between*clusters using the same procedure as in \([7](https://arxiv.org/html/2605.10975#S5.E7)\)\.

\(3\) Intra\-cluster wavelets \(within a cluster\)\.Consider a clusterCk\(ℓ\)C\_\{k\}^\{\(\\ell\)\}withnkn\_\{k\}nodes\. We constructnk−1n\_\{k\}\-1strictly local wavelets to capture variations within this cluster\. We iterate through the cluster’s nodes and define “split points\.” For a split at indexrr, we define a waveletwintra;k,r\(ℓ\)w\_\{\\mathrm\{intra\};k,r\}^\{\(\\ell\)\}that contrasts the firstrrnodes \(Left \(c\) group \) against the remainingnk−rn\_\{k\}\-rnodes \(Right \(e\) group\) as

wintra;k,r\(ℓ\)​\(i\)=\{βk,rαk,r​\(αk,r\+βk,r\)​\(As\(ℓ\)\)i,k,i∈c,−αk,rβk,r​\(αk,r\+βk,r\)​\(As\(ℓ\)\)i,k,i∈e\.w\_\{\\mathrm\{intra\};k,r\}^\{\(\\ell\)\}\(i\)=\\begin\{cases\}\\;\\;\\;\\;\\sqrt\{\\dfrac\{\\beta\_\{k,r\}\}\{\\alpha\_\{k,r\}\\bigl\(\\alpha\_\{k,r\}\+\\beta\_\{k,r\}\\bigr\)\}\}\\,\(A\_\{s\}^\{\(\\ell\)\}\)\_\{i,k\},&i\\in\\text\{c\},\\\\\[1\.0pt\] \-\\sqrt\{\\dfrac\{\\alpha\_\{k,r\}\}\{\\beta\_\{k,r\}\\bigl\(\\alpha\_\{k,r\}\+\\beta\_\{k,r\}\\bigr\)\}\}\\,\(A\_\{s\}^\{\(\\ell\)\}\)\_\{i,k\},&i\\in\\text\{e\}\.\\end\{cases\}\(9\)withwintra;k,r\(ℓ\)​\(i\)=0w\_\{\\mathrm\{intra\};k,r\}^\{\(\\ell\)\}\(i\)=0fori∉Ck\(ℓ\)i\\notin C\_\{k\}^\{\(\\ell\)\}, whereαk,r\(ℓ\)=∑j=1r\(As\(ℓ\)\)i,k\\alpha\_\{k,r\}^\{\(\\ell\)\}=\\sum\_\{j=1\}^\{r\}\(A\_\{s\}^\{\(\\ell\)\}\)\_\{i,k\}andβk,r\(ℓ\)=∑j=r\+1nk\(As\(ℓ\)\)i,k\\beta\_\{k,r\}^\{\(\\ell\)\}=\\sum\_\{j=r\+1\}^\{n\_\{k\}\}\(A\_\{s\}^\{\(\\ell\)\}\)\_\{i,k\}are the total membership masses of the Left and Right groups, respectively\. Assembly and filtering\.Finally, we concatenate the scaling vector, inter\-cluster wavelets, and intra\-cluster wavelets to form the Haar basis as

U\(ℓ\)=\[usc\(ℓ\)​\|Winter\(ℓ\)\|​Wintra\(ℓ\)\]∈ℝ\|V\(ℓ\)\|×\|V\(ℓ\)\|\.U^\{\(\\ell\)\}=\\Bigl\[u\_\{\\mathrm\{sc\}\}^\{\(\\ell\)\}\\;\\Big\|\\;W\_\{\\mathrm\{inter\}\}^\{\(\\ell\)\}\\;\\Big\|\\;W\_\{\\mathrm\{intra\}\}^\{\(\\ell\)\}\\Bigr\]\\in\\mathbb\{R\}^\{\|V^\{\(\\ell\)\}\|\\times\|V^\{\(\\ell\)\}\|\}\.The structure of the Haar basis is shown in Fig\.[3](https://arxiv.org/html/2605.10975#S5.F3)\. We filter features at levelℓ\\ellas

H\(ℓ\)=U\(ℓ\)​Λ\(ℓ\)​U\(ℓ\)⊤​X\(ℓ\),H^\{\(\\ell\)\}=U^\{\(\\ell\)\}\\Lambda^\{\(\\ell\)\}U^\{\(\\ell\)\\top\}X^\{\(\\ell\)\},\(10\)whereΛ\(ℓ\)\\Lambda^\{\(\\ell\)\}is a learnable diagonal gain matrix controlling low\-/high\-frequency channels\. BecauseU\(ℓ\)U^\{\(\\ell\)\}is sparse and locally supported, both basis construction and filtering can be implemented in near\-linear time on sparse graphs\.

### 5\.4Prediction Task

For node‑level tasks, we compute each node’s final embedding by additive unpoolingH^j=Hj\(0\)\+∑ℓ=1L∑i:j∈Ci\(ℓ\)Hi\(ℓ\)\\widehat\{H\}\_\{j\}=H\_\{j\}^\{\(0\)\}\+\\sum\_\{\\ell=1\}^\{L\}\\sum\_\{i:j\\in C\_\{i\}^\{\(\\ell\)\}\}H\_\{i\}^\{\(\\ell\)\}\\,so that every node carries its base feature plus the pooled summaries of all clusters across different scales it belongs to\. For graph‑level tasks, we coarsen until the number of nodes is\|V\(L\)\|=1\\lvert V^\{\(L\)\}\\rvert=1\. We then use the embedding of this final supernode for graph classification\. The total loss is defined asLtotal=LCE−λdiv​Ldiv,L\_\{\\mathrm\{total\}\}=L\_\{\\mathrm\{CE\}\}\-\\lambda\_\{\\mathrm\{div\}\}\\,L\_\{\\mathrm\{div\}\},whereLCEL\_\{\\mathrm\{CE\}\}is the standard cross‑entropy and

Ldiv=−∑ℓ=0L−11\|V\(ℓ\)\|​∑i=1\|V\(ℓ\)\|∑k=1KℓAs,i​k\(ℓ\)​log⁡As,i​k\(ℓ\),L\_\{\\mathrm\{div\}\}=\-\\sum\_\{\\ell=0\}^\{L\-1\}\\frac\{1\}\{\\lvert V^\{\(\\ell\)\}\\rvert\}\\sum\_\{i=1\}^\{\\lvert V^\{\(\\ell\)\}\\rvert\}\\sum\_\{k=1\}^\{K\_\{\\ell\}\}A\_\{s,ik\}^\{\(\\ell\)\}\\log A\_\{s,ik\}^\{\(\\ell\)\},that maximizes the entropy of each node’s soft assignment\(As\(ℓ\)\)i:\(A\_\{s\}^\{\(\\ell\)\}\)\_\{i:\}\. Hyperparametersλdiv\\lambda\_\{\\mathrm\{div\}\}andλrec\\lambda\_\{\\mathrm\{rec\}\}balance the auxiliary terms\.

### 5\.5Theoretical Perspective

![Refer to caption](https://arxiv.org/html/2605.10975v1/Haar_matrix.png)Figure 3:Structure of the Haar basis matrixU\(ℓ\)U^\{\(\\ell\)\}\. Columns are nodes ordered by assumed clusters\(C1,C2,C3\)\(C\_\{1\},C\_\{2\},C\_\{3\}\)Figure[3](https://arxiv.org/html/2605.10975#S5.F3)illustrates the distinct structure of the Haar basis matrixU\(ℓ\)U^\{\(\\ell\)\}using a simplified example with three clusters \(C1,C2,C3C\_\{1\},C\_\{2\},C\_\{3\}\)\.The rows exhibit a hierarchical progression\. The first row is a dense scaling vector that captures the global trend\. The second and third rows correspond to inter\-cluster wavelets, which are block\-constant and encode contrasts between clusters\. The remaining rows form intra\-cluster wavelets, which are sparse \(block\-diagonal\) and capture strictly local variations within each cluster\.

This structure offers a decisive advantage over global polynomial bases, whose basis are dense and spread energy diffusely across distant nodes\. By strictly confining the support of each wavelet, Haar filtering prevents information leakage between unrelated parts of the graph\. Our localized basis preserves these high\-frequency components without allowing the hub’s dominant signal to overwhelm them, thereby mitigating hub domination\. Furthermore, the strict orthogonality between the scaling and wavelet subspaces prevents frequency leakage and uncontrolled low\-pass drift, reducing oversmoothing\. The hierarchical nature of the construction logarithmically shortens communication paths to alleviate oversquashing\. We formalize these theoretical guarantees in the following theorems\.

Table 1:Node classification performance \(%\)\. “—” indicates not reported under the corresponding suite/protocol\.###### Theorem 5\.3\.

A spectral filter based on orthonormal and local basis holds any region\-specific signal pattern confined under filtering\. \(Proof in Appendix[D](https://arxiv.org/html/2605.10975#A4)\)

###### Theorem 5\.4\.

LetA,B,H′A,B,H^\{\\prime\}post‑filter centroids areμA,μB,μH′\\mu\_\{A\},\\mu\_\{B\},\\mu\_\{H\}^\{\\prime\}and setΔA​B=‖μA−μB‖,ΔA​H′=‖μA−μH′‖\\Delta\_\{AB\}=\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|,\\Delta\_\{AH^\{\\prime\}\}=\\\|\\mu\_\{A\}\-\\mu\_\{H\}^\{\\prime\}\\\|, thenΔA​BΔA​H′≥Ma\+b​\(1−2M\)\>1\.\\frac\{\\Delta\_\{AB\}\}\{\\Delta\_\{AH^\{\\prime\}\}\}\\;\\geq\\;\\sqrt\{\\frac\{M\}\{a\+b\}\}\\Bigl\(1\-\\tfrac\{2\}\{\\sqrt\{M\}\}\\Bigr\)\\;\>\\;1\.Thus enlarging the hubHHcan never shrink the spoke–spoke separation below the spoke–hub separation, avoiding hub domination\. \(Proof is in Appendix[E](https://arxiv.org/html/2605.10975#A5)\)

###### Theorem 5\.5\.

Regardless of the number of layers in the proposed HMH , it overcomes the problems of oversmoothing and oversquashing\. \(Proof is in Appendix[F](https://arxiv.org/html/2605.10975#A6)\)

## 6Experiments

Node ClassificationWe evaluate HMH on standard node\-classification benchmarks spanning*homophilous*citation graphs \(Cora, Citeseer, Pubmed, Coauthor\-CS/Physics\) and*heterophilous*graphs \(Chameleon, Squirrel, Texas,Roman\-empire,Amazon\-ratings,Questions,Minesweeper,Tolokers, etc\.\)\(Platonov et al\.,,[2023](https://arxiv.org/html/2605.10975#bib.bib30)\)\. Dataset statistics \(nodes/edges, classes, homophily\) are provided in Appendix G\.1\. For smaller datasets, we use a60/20/2060/20/20train/val/test split and report*inductive*performance, where test nodes are not used for supervision during training\. For larger graphs, we follow the standard*transductive*protocol with validation tuning and early stopping, and report mean test performance over1010splits \(mean±\\pm95% CI\)\. For the heterophily suite ofPlatonov et al\., \([2023](https://arxiv.org/html/2605.10975#bib.bib30)\), we use the official splits and metrics \(ROC\-AUC forMinesweeper/Tolokers/Questions; accuracy otherwise\)\. Full training and tuning details are in Appendix[G](https://arxiv.org/html/2605.10975#A7)\. Baselines\.We compare against representative methods from \(i\)polynomial filtering, \(ii\) heterophilly\-specalized message passing, and \(iii\) spectral/transformer models: SIGN\(Frasca et al\.,,[2020](https://arxiv.org/html/2605.10975#bib.bib11)\), EvenNet\(Lei et al\.,,[2022](https://arxiv.org/html/2605.10975#bib.bib20)\), ChebNet II\(He et al\.,,[2022](https://arxiv.org/html/2605.10975#bib.bib15)\), BernNet\(He et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib14)\), JacobiConv\(Wang & Zhang,,[2022](https://arxiv.org/html/2605.10975#bib.bib33)\), ARMA, UniFilter\(Huang et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib17)\), SLOG\(Xu et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib36)\), LINKX\(Lim et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib23)\), FAGCN\(Bo et al\.,,[2021](https://arxiv.org/html/2605.10975#bib.bib4)\), MTGCN\(Reuter et al\.,,[2025](https://arxiv.org/html/2605.10975#bib.bib28)\), M2M\-GNN\(Liang et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib22)\), and PolyFormer\(Ma et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib26)\), TFE\-GNN\(Huang et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib9)\)\. Results and discussion\.Table[1](https://arxiv.org/html/2605.10975#S5.T1)summarizes node classification accuracy\. Overall,HMH achieves strong and consistent performanceon homophilic graphs, withclear gains on challenging heterophilic benchmarksandcompetitive results at large scale\. Onhomophilicdatasets \(e\.g\., CS and Citeseer\), where labels are dominated by smooth signals, the encoder learns mostly positive affinities enabling stable low\-pass propagation, while Haar\-domain diagonal gains suppress non\-informative high\-frequency components, improving denoising without oversmoothing\. Onheterophilicdatasets \(e\.g\., Minesweeper, Roman\-empire, Squirrel/Chameleon, and Amazon\-ratings\), HMH improves over standard GNN baselines and remains competitive with specialized heterophily methods by learning*signed, adaptive affinities*and selectively preserving contrastive \(high\-frequency\) Haar components, which reduces destructive neighbor mixing and better maintains class boundaries\. HMH also performs strongly on the large\-scaleOGBN\-Arxivdataset \(169,343 nodes; 1,166,243 edges\), indicating that hierarchical Haar filtering remains effective beyond small benchmarks\. Additionally, the results from large\-scale datasets are presented in Appendix[G\.1](https://arxiv.org/html/2605.10975#A7.SS1)\.

Table 2:Graph\-classification accuracy \(%\) comparison on TU datasets\. Mean is±\\pm95% CI and ‘–’ means no result found\.### 6\.1Hub Domination, Oversmoothing and Oversquashing Analysis

Since degree\-dependent aggregation drives hub domination, a degree\-stratified evaluation provides a direct stress test: it isolates performance on low\-degree nodes \( weaker aggregation influence\) versus high\-degree nodes \(stronger aggregation influence\)\. We divide the test nodes into three groups based on node degree: ”Spokes” \(low\-degree\), ”Medium” \(mid\-degree\), and ”Hubs” \(high\-degree\), as shown in Table[3](https://arxiv.org/html/2605.10975#S6.T3)\. GCN and BernNet are significantly more accurate on*Hubs*than on*Spokes*, suggesting hub\-dominated aggregation\. This disparity is even more pronounced in large\-scale graphs \(Penn94, Amazon\-Ratings\): Spoke accuracy can be up to 19% lower than Hub accuracy\. Proposed HMH reduces hub dominance by multiscale Haar filtering, increasing Spokes on Penn94 by\+10\.8%\\mathbf\{\+10\.8\\%\}and minimizing the degree gap compared to baseline\. The pattern continues on highly heterogeneous graphs, such as Squirrel \(non\-filtered\), where HMH improves all cohorts \(e\.g\.,\+9\.1%\\mathbf\{\+9\.1\\%\}on Spokes\) by preventing oversmoothing of conflicting signals\. On the other hand,Tolokersexhibits*reverse*hub domination \(the baselines perform worse on high\-degree nodes, likely due to noisy superusers/bots\)\. Instead of blindly boosting the hub accuracy, HMH improves all cohorts by\+1\.6%\\mathbf\{\+1\.6\\%\}over baseline, signaling strong adaptation to the graph structure\. Overall, HMH prevents amplification of hubs while filtering degree\-induced structural noise\.

Table 3:Stratified Accuracy \(%\) Analysis on Hub Domination\. We report performance across node degree \(dd\) cohorts:Spokes\(Low\),Medium, andHubs\(High\)\. The number of nodes \(NN\) and degree range is indicated in the header\.![Refer to caption](https://arxiv.org/html/2605.10975v1/x3.png)Figure 4:Oversmoothing \(a, b, and c\) and Oversquashing \(d\) Analysis\.We empirically show that the proposed HMH mitigates two depth\-related GNN pathologies:oversmoothingandoversquashing\.Oversmoothingresults are in Fig\.[4](https://arxiv.org/html/2605.10975#S6.F4)\(a–c\)\. We can see that as depth grows, standard GCNs ’ accuracy rapidly degrades \(below 20% onPenn94andArxivat 64 layers\), consistent with feature homogenization\. Even, depth\-stabilized baselines \(GCNII, EvenNet\) still drop by55–10%10\\%\. In contrast, HMH remains stable and improves with depth, peaking onPenn94at 32–64 layers \(up to85\.1%85\.1\\%\), indicating better preservation of discriminative signals\. Foroversquashing, we useTree\-NeighborsMatch\(Fig\.[4](https://arxiv.org/html/2605.10975#S6.F4)\(d\)\) benchmark\(Pei et al\.,,[2024](https://arxiv.org/html/2605.10975#bib.bib27)\), where correct leaf predictions require information from distant ancestors\. As tree depth increases, the required information must travel farther, creating a strong bottleneck in the information flow from distant neighbors\. InFig\.[4](https://arxiv.org/html/2605.10975#S6.F4)\(d\), we can see baseline models such as GIN and ChebNet quickly lose long\-range context and drop to random guess accuracy \(50%50\\%\) by depth 8\. In contrast, HMH maintains reliable long\-range propagation and strong accuracy \(\>98%\>98\\%\) even at depth 10\. This signals HMH’s effective long\-range information\-propagation capability\. Dirichlet energy results are provided in Appendix[J](https://arxiv.org/html/2605.10975#A10)\.

### 6\.2Graph Classification via Spectral Pooling

HMH is ideal for graph classification because its hierarchical coarsening explicitly implements pooling: at each level, nodes are aggregated into supernodes, and the final \(coarsest\) level provides a compact graph\-level embedding\. Experimental Setup\.We evaluate HMH on 7 benchmarks covering molecular \(e\.g\., MUTAG, NCI1\) and social networks \(IMDB, REDDIT\)\. We compare against strong pooling baselines DiffPool\(Ying et al\.,,[2018](https://arxiv.org/html/2605.10975#bib.bib37)\), SAGPool\(Lee et al\.,,[2019](https://arxiv.org/html/2605.10975#bib.bib19)\), TopKPool\(Diehl,,[2019](https://arxiv.org/html/2605.10975#bib.bib8)\)and graph classifiers DGCNN\(Phan et al\.,,[2018](https://arxiv.org/html/2605.10975#bib.bib29)\), SEP\(Wu et al\.,,[2022](https://arxiv.org/html/2605.10975#bib.bib35)\)\. Hyperparameters, including loss weights \(λdiv,λrec\\lambda\_\{\\mathrm\{div\}\},\\lambda\_\{\\mathrm\{rec\}\}\) and coarsening depthℓ\\ellare detailed in Appendix[H](https://arxiv.org/html/2605.10975#A8)\. Graph Classification Results\.Table[2](https://arxiv.org/html/2605.10975#S6.T2)reports graph classification accuracy across bioinformatics and social benchmarks\. HMH achieves strong gains on structure\-heavy bioinformatics graphs, reaching94\.5%onMUTAGand consistently improving onPROTEINSandNCI1, suggesting that high\-frequency Haar components capture fine\-grained molecular signals that are often oversmoothed by purely low\-pass pooling\. On hub\-heavy social graphs \(e\.g\.,IMDB\-M,REDDIT\-12K\), HMH remains highly competitive, indicating that the learned orthogonal basis can disentangle community structure while avoiding signal mixing\. Full experimental settings and dataset details are provided in the Appendix[H](https://arxiv.org/html/2605.10975#A8)\. Ablation Study and Runtime Analysis\.We ablate three components of HMH under the same protocol as the full model\. 1\)Fixed adjacencyreplaces the adaptive signed affinity with the originalAA\. 2\)No hierarchyperforms Haar filtering only atℓ=0\\ell\{=\}0\(no coarsening / no multiscale fusion\)\. 3\)Fixed basisreplaces the learned localized Haar basis with a Chebyshev global surrogate\. Table[4](https://arxiv.org/html/2605.10975#S6.T4)shows consistent drops, with the largest degradations on heterophilous graphs \(Actor/Chameleon/Squirrel\), supporting the roles of adaptive signing, hierarchy, and localized orthonormal bases\. Additional ablations are in Appendix[K](https://arxiv.org/html/2605.10975#A11)\. Moreover, HMH runs in near\-linear time on sparse graphs since bothAadpA\_\{\\mathrm\{adp\}\}and we report wall\-clock time and peak memory onRedditin Appendix[I](https://arxiv.org/html/2605.10975#A9)\. LimitationsOur current formulation assumes a static graph\. Extending HMH to dynamic settings with frequently changing edges would require updating the hierarchy over time\. Also, extending HMH to multi\-relational/directed graphs is an important direction for broader graph learning\.

Table 4:Ablation on HMH \(mean±\\pmstd, %\)\. We used the non\-filtered version of the squirrel and chameleon datasets for ablation\.

## 7Conclusion

We presented HMH, a sign\-aware, multi\-resolution framework designed for heterophilous graphs\. Using an adaptive encoder that integrated structural and feature affinities into a unified node score, HMH enabled systematic hierarchical coarsening and constructed sparse, orthonormal Haar bases at each level in almost linear time\. These locality\-preserving orthogonal bases confine energy strictly to two\-hop neighbourhoods, allowing the framework to distinguish low\-frequency \(homophilous\) from high\-frequency \(heterophilous\) signals across clusters of varying sizes without relying on costly eigen\-decomposition\. Through this design, HMH mitigated hub\-aliasing and basis\-suboptimality, achieved state\-of\-the\-art performance on diverse node\- and graph\-classification benchmarks, and significantly reduced preprocessing overhead\. Analytical results, rigorous proofs, and experimental validation confirmed the proposed approach, showing that HMH consistently outperformed state\-of\-the\-art spectral baselines – achieving up to a 3% improvement in node\-classification accuracy on heterophilous datasets and a 2% gain on graph\-classification tasks, while maintaining linear scalability\.

## References

- Bahmani et al\., \(2012\)Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii\.Scalable K\-Means\+\+\.*Proc\. VLDB Endow\.*, 2012\.
- Abate & Bianchi, \(2024\)Carlo Abate and Filippo Maria Bianchi\.MaxCutPool: Differentiable feature\-aware Maxcut for pooling in graph neural networks\.*arXiv preprint arXiv:2409\.05100*, 2024\.
- Bianchi et al\., \(2019\)Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi\.Mincut pooling in Graph Neural Networks\.*ArXiv*, 2019\.
- Bo et al\., \(2021\)Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen\.Beyond Low\-frequency Information in Graph Convolutional Networks\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 2021\.
- Chien et al\., \(2021\)Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic\.Adaptive Universal Generalized PageRank Graph Neural Network\.*Proceedings of International Conference on Learning Representations*, 2021\.
- Chung, \(1997\)Fan RK Chung\.Spectral graph theory\.1997\.
- Di Giovanni et al\., \(2023\)Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein\.On over\-squashing in message passing neural networks: The impact of width, depth, and topology\.*Proceedings of International conference on machine learning*, 2023\.
- Diehl, \(2019\)Frederik Diehl\.Edge contraction pooling for graph neural networks\.*arXiv preprint arXiv:1905\.10990*, 2019\.
- Huang et al\., \(2024\)Keke Huang, Yu Guang Wang, Ming Li, and Pietro Liò\.Unifying Homophily and Heterophily for Spectral Graph Neural Networks via Triple Filter Ensembles\.*Proceedings of Advances in Neural Information Processing Systems \(NeurIPS\)*, 2024\.
- Epping et al\., \(2024\)Bastian Epping, Alexandre René, Moritz Helias, and Michael T Schaub\.Graph neural networks do not always oversmooth\.*Proceedings of Advances in Neural Information Processing Systems*, 2024\.
- Frasca et al\., \(2020\)Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti\.Sign: Scalable inception graph neural networks\.*arXiv preprint arXiv:2004\.11198*, 2020\.
- Giraldo et al\., \(2023\)Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros\.On the trade\-off between over\-smoothing and over\-squashing in deep graph neural networks\.*Proceedings of the 32nd ACM international conference on information and knowledge management*, 2023\.
- Guo & Wei, \(2023\)Yuhe Guo and Zhewei Wei\.Graph neural networks with learnable and optimal polynomial bases\.*Proceedings of International conference on machine learning*, 2023\.
- He et al\., \(2021\)Mingguo He, Zhewei Wei, Hongteng Xu, and others\.Bernnet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation\.*Proceedings of Advances in neural information processing systems*, 2021\.
- He et al\., \(2022\)Mingguo He, Zhewei Wei, and Ji\-Rong Wen\.Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited\.*Proceedings of Advances in neural information processing systems*, 2022\.
- Horn & Johnson, \(2012\)Roger A Horn and Charles R Johnson\.Matrix analysis\.2012\.
- Huang et al\., \(2024\)Keke Huang, Yu Guang Wang, Ming Li, and others\.How universal polynomial bases enhance spectral graph neural networks: Heterophily, over\-smoothing, and over\-squashing\.*arXiv preprint arXiv:2405\.12474*, 2024\.
- Keriven, \(2022\)Nicolas Keriven\.Not too little, not too much: A theoretical analysis of graph \(over\) smoothing\.*Proceedings of Advances in Neural Information Processing Systems*, 2022\.
- Lee et al\., \(2019\)Junhyun Lee, Inyeop Lee, and Jaewoo Kang\.Self\-attention graph pooling\.*Proceedings of International conference on machine learning*, 2019\.
- Lei et al\., \(2022\)Runlin Lei, Zhen Wang, Yaliang Li, Bolin Ding, and Zhewei Wei\.EvenNet: Ignoring odd\-hop neighbors improves robustness of graph neural networks\.*Proceedings of Advances in neural information processing systems*, 2022\.
- Li et al\., \(2024\)Zhi\-Peng Li, Si\-Guo Wang, Qin\-Hu Zhang, Yi\-Jie Pan, Nai\-An Xiao, Jia\-Yang Guo, Chang\-An Yuan, Wen\-Jian Liu, and De\-Shuang Huang\.Graph pooling for graph\-level representation learning: a survey\.*Artificial Intelligence Review*, 2024\.
- Liang et al\., \(2024\)Langzhang Liang, Sunwoo Kim, Kijung Shin, Zenglin Xu, Shirui Pan, and Yuan Qi\.Sign is not a remedy: Multiset\-to\-multiset message passing for learning on heterophilic graphs\.*arXiv preprint arXiv:2405\.20652*, 2024\.
- Lim et al\., \(2021\)Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser\-Nam Lim\.Large Scale Learning on Non\-Homophilous Graphs: New Benchmarks and Strong Simple Methods\.*Proceedings of Advances in Neural Information Processing Systems \(NeurIPS\)*, 2021\.
- Luan et al\., \(2022\)Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao\-Wen Chang, and Doina Precup\.Revisiting heterophily for graph neural networks\.*Proceedings of Advances in neural information processing systems*, 2022\.
- Ma et al\., \(2019\)Yao Ma, Suhang Wang, Charu C Aggarwal, and Jiliang Tang\.Graph convolutional networks with eigenpooling\.*Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining*, 2019\.
- Ma et al\., \(2024\)Jiahong Ma, Mingguo He, and Zhewei Wei\.PolyFormer: Scalable Node\-wise Filters via Polynomial Graph Transformer\.*Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining \(KDD\)*, 2024\.
- Pei et al\., \(2024\)Hongbin Pei, Yu Li, Huiqi Deng, Jingxin Hai, Pinghui Wang, Jie Ma, Jing Tao, Yuheng Xiong, and Xiaohong Guan\.Multi\-track message passing: Tackling oversmoothing and oversquashing in graph learning via preventing heterophily mixing\.*Proceedings of Forty\-first International Conference on Machine Learning*, 2024\.
- Reuter et al\., \(2025\)L\. Reuter, G\. De Pietro, S\. Stefkova, T\. Ferber, V\. Bertacchi, G\. Casarosa, L\. Corona, P\. Ecker, A\. Glazov, Y\. Han, M\. Laurenza, T\. Lueck, L\. Massaccesi, S\. Mondal, B\. Scavino, S\. Spataro, C\. Wessel, and L\. Zani\.End\-to\-End Multi\-Track Reconstruction using Graph Neural Networks at Belle II\.*Computing and Software for Big Science*, 2025\.
- Phan et al\., \(2018\)Anh Viet Phan, Minh Le Nguyen, Yen Lam Hoang Nguyen, and Lam Thu Bui\.DGCNN: A convolutional neural network over large\-scale labeled graphs\.*Neural Networks*, 2018\.
- Platonov et al\., \(2023\)Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova\.A critical look at the evaluation of GNNs under heterophily: Are we really making progress?\.*arXiv preprint arXiv:2302\.11640*, 2023\.
- Topping et al\., \(2021\)Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein\.Understanding over\-squashing and bottlenecks on graphs via curvature\.*arXiv preprint arXiv:2111\.14522*, 2021\.
- Wang et al\., \(2020\)Yu Guang Wang, Ming Li, Zheng Ma, Guido Montufar, Xiaosheng Zhuang, and Yanan Fan\.Haar graph pooling\.*Proceedings of International conference on machine learning*, 2020\.
- Wang & Zhang, \(2022\)Xiyuan Wang and Muhan Zhang\.How powerful are spectral graph neural networks\.*Proceedings of International conference on machine learning*, 2022\.
- Wang et al\., \(2024\)Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang\.Understanding heterophily for graph neural networks\.*arXiv preprint arXiv:2401\.09125*, 2024\.
- Wu et al\., \(2022\)Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li\.Structural entropy guided graph hierarchical pooling\.*Proceedings of International conference on machine learning*, 2022\.
- Xu et al\., \(2024\)Haobo Xu, Yuchen Yan, Dingsu Wang, Zhe Xu, Zhichen Zeng, Tarek F Abdelzaher, Jiawei Han, and Hanghang Tong\.SLOG: An Inductive Spectral Graph Neural Network Beyond Polynomial Filter\.*Proceedings of the 41st International Conference on Machine Learning \(ICML\)*, 2024\.
- Ying et al\., \(2018\)Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec\.Hierarchical graph representation learning with differentiable pooling\.*Proceedings of Advances in neural information processing systems*, 2018\.
- Zheng, \(2024\)Zheng\.What is missing in homophily? Disentangling graph homophily for graph neural networks\.*arXiv preprint arXiv:2406\.18854*, 2024\.
- Zhu & Koniusz, \(2021\)Hao Zhu and Piotr Koniusz\.Simple spectral graph convolution\.*Proceedings of International conference on learning representations*, 2021\.

## Appendix AProof of Theorem 4\.1

Consider three clustersAA,BB, andH′H^\{\\prime\}\. The tiny clusters or spokesAAandBBof sizea=\|A\|a=\|A\|andb=\|B\|b=\|B\|\) are attached to a common hubH′H^\{\\prime\}of sizeM=\|H′\|M=\|H^\{\\prime\}\|withM≫a,bM\\gg a,b\. Let the cluster mean features given byμA∈ℝd\\mu\_\{A\}\\in\\mathbb\{R\}^\{d\},μB∈ℝd\\mu\_\{B\}\\in\\mathbb\{R\}^\{d\},μH′∈ℝd\\mu\_\{H^\{\\prime\}\}\\in\\mathbb\{R\}^\{d\}, respectively forAA,BB, andH′H^\{\\prime\}\. Defineδ=‖μA−μB‖\\delta=\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|that measures the separationAA–BBandΔ=‖μH−μA\+μB2‖\\Delta=\\Big\\\|\\mu\_\{H\}\-\\tfrac\{\\mu\_\{A\}\+\\mu\_\{B\}\}\{2\}\\Big\\\|that measures the hub offset relative to the midpoint ofAAandBB

To analyze hub aliasing coherently, we will use the following standard assumptions:

#### Assumption 1

\(i\) The hub’s mean feature is*significantly different*from spokesAAandBBfeatures, i\.e\.,Δ≥κ​δfor some margin​κ\>1\\Delta\\geq\\kappa\\delta\\quad\\text\{for some margin \}\\kappa\>1\.

\(ii\) The hub’s sizeMMis sufficiently larger than the combined size with the weighed geometric factor, i\.e\.,Δ/δ\\Delta/\\delta,i\.e\.,M≥\(a\+b\)​Δδ​\(1\+ε\)for some​ε\>0\.M\\geq\\frac\{\(a\+b\)\\,\\Delta\}\{\\delta\}\\,\(1\+\\varepsilon\)\\quad\\text\{for some \}\\varepsilon\>0\.

We will consider the CMA and SMP algorithms in two cases to demonstrate that hub aliasing occurs in both the cases\.

Case I: Hub\-aliasing in CMA:For theCMA layer mechanics, the projection of the initial embedding is given by

zi=Hi\(ℓ−1\)​W∈ℝd′\.z\_\{i\}=H\_\{i\}^\{\(\\ell\-1\)\}W\\in\\mathbb\{R\}^\{d^\{\\prime\}\}\.
The pre\-softmax scores \(per edge and per chunk\) is given by

g​\(zi,zj\)=τ−1​r​e​l​u​\(α​zi\+zj\)​Watt∈ℝC\.g\(z\_\{i\},z\_\{j\}\)\\;=\\;\\tau^\{\-1\}\\,relu\(\\alpha z\_\{i\}\+z\_\{j\}\)\\,W\_\{\\text\{att\}\}\\in\\mathbb\{R\}^\{C\}\.\(11\)
The soft labels \(chunk weights\) is given by

si​j=softmax​\(g​\(zi,zj\)\)∈ΔC−1\.s\_\{ij\}=\\text\{softmax\}\\\!\\big\(g\(z\_\{i\},z\_\{j\}\)\\big\)\\in\\Delta^\{C\-1\}\.\(12\)
The chunked aggregation is given byCi,t=∑j∈𝒩​\(i\)si​j,t​zjC\_\{i,t\}=\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}s\_\{ij,t\}\\,z\_\{j\}, and

mi=∥t=1CCi,t\.m\_\{i\}=\\big\\\|\_\{t=1\}^\{C\}C\_\{i,t\}\.\(13\)The CMA update rule is expressed by

Hi\(ℓ\)=r​e​l​u​\(\(1−β\)​Hi\(0\)\+β​mi\)H\_\{i\}^\{\(\\ell\)\}=relu\\\!\\big\(\(1\-\\beta\)H\_\{i\}^\{\(0\)\}\+\\beta\\,m\_\{i\}\\big\)\(14\)
The projection embedding iszh≈μH​Wz\_\{h\}\\approx\\mu\_\{H\}Wforh∈H′h\\in H^\{\\prime\},zu≈μA​Wz\_\{u\}\\approx\\mu\_\{A\}Wforu∈Au\\in A,zv≈μB​Wz\_\{v\}\\approx\\mu\_\{B\}Wforv∈Bv\\in B\.

Now using Lipschitz and strong monotonicity, we get the following: ReLU is11\-Lipschitz\. So,the mapx↦x​Wattx\\mapsto xW\_\{\\text\{att\}\}is‖Watt‖2\\\|W\_\{\\text\{att\}\}\\\|\_\{2\}\-Lipschitz\. Scaling byτ−1\\tau^\{\-1\}isτ−1\\tau^\{\-1\}\-Lipschitz\. Hence, for the score mapggusing \([11](https://arxiv.org/html/2605.10975#A1.E11)\) we get,

‖g​\(α​zi\+zh\)−g​\(α​zj\+zh\)‖\\displaystyle\\\|g\(\\alpha z\_\{i\}\+z\_\{h\}\)\-g\(\\alpha z\_\{j\}\+z\_\{h\}\)\\\|≤‖Watt‖2τ​α​‖W‖2​‖zi−zj‖\.\\displaystyle\\leq\\frac\{\\\|W\_\{\\text\{att\}\}\\\|\_\{2\}\}\{\\tau\}\\,\\alpha\\,\\\|W\\\|\_\{2\}\\,\\\|z\_\{i\}\-z\_\{j\}\\\|\.\(15\)Softmax isLσL\_\{\\sigma\}\-Lipschitz withLσ≤1L\_\{\\sigma\}\\leq 1and on the subspace orthogonal to𝟏\\mathbf\{1\}it isκσ\\kappa\_\{\\sigma\}\-strongly monotone, given by

‖softmax​\(u\)−softmax​\(v\)‖\\displaystyle\\\|\\text\{softmax\}\(u\)\-\\text\{softmax\}\(v\)\\\|≥κσ​‖u−v‖\.\\displaystyle\\geq\\kappa\_\{\\sigma\}\\,\\\|u\-v\\\|\.\(16\)whereκσ:=pmin​\(1−pmin\)\\kappa\_\{\\sigma\}:=p\_\{\\min\}\(1\-p\_\{\\min\}\)withpmin\>0p\_\{\\min\}\>0is the minimum probability of softmax output, and we assume no collapse ofWWalong\(μA−μH\)\(\\mu\_\{A\}\-\\mu\_\{H\}\)\.

For spoke to hub edges\(u,h\)\(u,h\)versus\(v,h\)\(v,h\), we can calculate the difference of the soft label using \([12](https://arxiv.org/html/2605.10975#A1.E12)\) as

‖su​h−sv​h‖\\displaystyle\\\|s\_\{uh\}\-s\_\{vh\}\\\|≤Lσ​‖Watt‖2τ​α​‖W‖2​‖zu−zv‖≤catt​δ\.\\displaystyle\\leq L\_\{\\sigma\}\\,\\frac\{\\\|W\_\{\\text\{att\}\}\\\|\_\{2\}\}\{\\tau\}\\,\\alpha\\,\\\|W\\\|\_\{2\}\\,\\\|z\_\{u\}\-z\_\{v\}\\\|\\leq c\_\{\\text\{att\}\}\\,\\delta\.\(17\)Similarly, for spoke versus hub edges\(u,w\)\(u,w\)and\(h,w\)\(h,w\)withw∈H′w\\in H^\{\\prime\}, we can calculate the difference of the soft label using \([12](https://arxiv.org/html/2605.10975#A1.E12)\) as

‖su​w−sh​w‖\\displaystyle\\\|s\_\{uw\}\-s\_\{hw\}\\\|≥κσ​‖Watt‖2τ​α​‖W‖2​‖zu−zh‖≥catt′​Δ,\\displaystyle\\geq\\kappa\_\{\\sigma\}\\,\\frac\{\\\|W\_\{\\text\{att\}\}\\\|\_\{2\}\}\{\\tau\}\\,\\alpha\\,\\\|W\\\|\_\{2\}\\,\\\|z\_\{u\}\-z\_\{h\}\\\|\\geq c^\{\\prime\}\_\{\\text\{att\}\}\\,\\Delta,\(18\)wherecatt=Lσ​‖Watt‖2τ​α​‖W‖2c\_\{\\text\{att\}\}=L\_\{\\sigma\}\\,\\frac\{\\\|W\_\{\\text\{att\}\}\\\|\_\{2\}\}\{\\tau\}\\,\\alpha\\,\\\|W\\\|\_\{2\}andcatt′=κσ​‖Watt‖2τ​α​‖W‖2c^\{\\prime\}\_\{\\text\{att\}\}=\\kappa\_\{\\sigma\}\\,\\frac\{\\\|W\_\{\\text\{att\}\}\\\|\_\{2\}\}\{\\tau\}\\,\\alpha\\,\\\|W\\\|\_\{2\}\. By partitioning the message update for the node into hub and spoke components as per \([13](https://arxiv.org/html/2605.10975#A1.E13)\) and aggregating over neighbors, we obtain

‖mu−mv‖\\displaystyle\\\|m\_\{u\}\-m\_\{v\}\\\|≤M​catt​δ​‖zH‖\+\(a\+b\)​‖W‖2​δ=Kz​δ,\\displaystyle\\leq M\\,c\_\{\\text\{att\}\}\\,\\delta\\,\\\|z\_\{H\}\\\|\+\(a\+b\)\\,\\\|W\\\|\_\{2\}\\,\\delta=K\_\{z\}\\,\\delta,\(19\)‖mu−mh‖\\displaystyle\\\|m\_\{u\}\-m\_\{h\}\\\|≥M​catt′​Δ​‖zH‖=Kh​Δ,\\displaystyle\\geq M\\,c^\{\\prime\}\_\{\\text\{att\}\}\\,\\Delta\\,\\\|z\_\{H\}\\\|=K\_\{h\}\\,\\Delta,\(20\)whereKz=M​catt​‖zH‖\+\(a\+b\)​‖W‖2K\_\{z\}=M\\,c\_\{\\text\{att\}\}\\,\\\|z\_\{H\}\\\|\+\(a\+b\)\\,\\\|W\\\|\_\{2\}andKh=M​catt′​‖zH‖K\_\{h\}=M\\,c^\{\\prime\}\_\{\\text\{att\}\}\\,\\\|z\_\{H\}\\\|\.

Recalling the CMA hub update from \([14](https://arxiv.org/html/2605.10975#A1.E14)\) we get,

‖Hu\(1\)−Hv\(1\)‖\\displaystyle\\\|H\_\{u\}^\{\(1\)\}\-H\_\{v\}^\{\(1\)\}\\\|≤\(1−β\)​δ\+β​Kz​δ,\\displaystyle\\leq\(1\-\\beta\)\\,\\delta\+\\beta\\,K\_\{z\}\\,\\delta,\(21\)‖Hu\(1\)−Hh\(1\)‖\\displaystyle\\\|H\_\{u\}^\{\(1\)\}\-H\_\{h\}^\{\(1\)\}\\\|≥β​Kh​Δ−\(1−β\)​Δ\.\\displaystyle\\geq\\beta\\,K\_\{h\}\\,\\Delta\-\(1\-\\beta\)\\,\\Delta\.\(22\)Therefore dividing \([21](https://arxiv.org/html/2605.10975#A1.E21)\) by \([22](https://arxiv.org/html/2605.10975#A1.E22)\) we get

‖Hu\(1\)−Hv\(1\)‖‖Hu\(1\)−Hh\(1\)‖\\displaystyle\\frac\{\\\|H\_\{u\}^\{\(1\)\}\-H\_\{v\}^\{\(1\)\}\\\|\}\{\\\|H\_\{u\}^\{\(1\)\}\-H\_\{h\}^\{\(1\)\}\\\|\}≤\(1−β\)\+β​Kzβ​Kh−\(1−β\)​δΔ\.\\displaystyle\\leq\\frac\{\(1\-\\beta\)\+\\beta K\_\{z\}\}\{\\beta K\_\{h\}\-\(1\-\\beta\)\}\\,\\frac\{\\delta\}\{\\Delta\}\.\(23\)SubstitutingKz=M​catt​‖zH‖\+\(a\+b\)​‖W‖2K\_\{z\}=M\\,c\_\{\\text\{att\}\}\\,\\\|z\_\{H\}\\\|\+\(a\+b\)\\,\\\|W\\\|\_\{2\},Kh=M​catt′​‖zH‖K\_\{h\}=M\\,c^\{\\prime\}\_\{\\text\{att\}\}\\,\\\|z\_\{H\}\\\|, and grouping the hub size terms, it holds that

\(1−β\)\+β​Kzβ​Kh−\(1−β\)\\displaystyle\\frac\{\(1\-\\beta\)\+\\beta K\_\{z\}\}\{\\beta K\_\{h\}\-\(1\-\\beta\)\}≤1−ββ​Kh\+cattcatt′\+a\+bM​‖W‖2catt′​‖zH‖\\displaystyle\\leq\\frac\{1\-\\beta\}\{\\beta K\_\{h\}\}\+\\frac\{c\_\{\\text\{att\}\}\}\{c^\{\\prime\}\_\{\\text\{att\}\}\}\+\\frac\{a\+b\}\{M\}\\,\\frac\{\\\|W\\\|\_\{2\}\}\{c^\{\\prime\}\_\{\\text\{att\}\}\\\|z\_\{H\}\\\|\}\(24\)=θ0\+κ\+ρ​θ1,\\displaystyle=\\theta\_\{0\}\+\\kappa\+\\rho\\,\\theta\_\{1\},\(25\)whereθ0=1−ββ​Kh\\theta\_\{0\}=\\frac\{1\-\\beta\}\{\\beta K\_\{h\}\},κ=cattcatt′\\kappa=\\frac\{c\_\{\\text\{att\}\}\}\{c^\{\\prime\}\_\{\\text\{att\}\}\}andθ1=‖W‖2catt′​‖zH‖\\theta\_\{1\}=\\frac\{\\\|W\\\|\_\{2\}\}\{c^\{\\prime\}\_\{\\text\{att\}\}\\\|z\_\{H\}\\\|\}\. For largeMM,θ0\\theta\_\{0\}is negligible\.

Defineη:=κ\+ρ​θ1\\eta:=\\kappa\+\\rho\\,\\theta\_\{1\}\. From the definitioncatt<catt′c\_\{\\text\{att\}\}<c^\{\\prime\}\_\{\\text\{att\}\}andρ<1\\rho<1, and soη<1\\eta<1\. Combining \([23](https://arxiv.org/html/2605.10975#A1.E23)\) and \([25](https://arxiv.org/html/2605.10975#A1.E25)\) yields

‖Hu\(1\)−Hv\(1\)‖‖Hu\(1\)−Hh\(1\)‖\\displaystyle\\frac\{\\\|H\_\{u\}^\{\(1\)\}\-H\_\{v\}^\{\(1\)\}\\\|\}\{\\\|H\_\{u\}^\{\(1\)\}\-H\_\{h\}^\{\(1\)\}\\\|\}≤η​δΔ\.\\displaystyle\\leq\\eta\\,\\frac\{\\delta\}\{\\Delta\}\.\(26\)
Repeating the same argument at each layer forLLlayers with the same constants or their upper envelopes, we obtain

‖Hu\(L\)−Hv\(L\)‖‖Hu\(L\)−Hh\(L\)‖\\displaystyle\\frac\{\\\|H\_\{u\}^\{\(L\)\}\-H\_\{v\}^\{\(L\)\}\\\|\}\{\\\|H\_\{u\}^\{\(L\)\}\-H\_\{h\}^\{\(L\)\}\\\|\}≤\(η​δΔ\)L,\\displaystyle\\leq\(\\eta\\,\\frac\{\\delta\}\{\\Delta\}\)^\{L\},\(27\)with0<δΔ<10<\\frac\{\\delta\}\{\\Delta\}<1\. From \([27](https://arxiv.org/html/2605.10975#A1.E27)\), we can state that the spoke–spoke separation decays exponentially relative to the spoke–hub separation across layers\. Therefore, CMA concentrates information toward the hub\.

Case II: Hub\-aliasing in SMP:Let the signed adjacencySu​v=\+1S\_\{uv\}=\+1if\(u,v\)∈E\(u,v\)\\in Eandyu=yvy\_\{u\}=y\_\{v\}, andSu​v=−1S\_\{uv\}=\-1ifyu≠yvy\_\{u\}\\neq y\_\{v\}\. The SMP update \(omitting bias and ReLU for upper bound\) is given by

H\(k\+1\)=S​H\(k\)​W\(k\),‖W\(k\)‖2=1,H\(0\)=X\.H^\{\(k\+1\)\}=SH^\{\(k\)\}W^\{\(k\)\},\\quad\\\|W^\{\(k\)\}\\\|\_\{2\}=1,\\quad H^\{\(0\)\}=X\.\(28\)So we can express

‖S​H\(k\)​W\(k\)‖2≤‖S​H\(k\)‖2\.\\bigl\\\|S\\,H^\{\(k\)\}W^\{\(k\)\}\\bigr\\\|\_\{2\}\\;\\leq\\;\\bigl\\\|S\\,H^\{\(k\)\}\\bigr\\\|\_\{2\}\.
In addition, two consecutive steps of the SMP can be expressed as

H\(k\+2\)=S​\(S​H\(k\)​W\(k\)\)​W\(k\+1\)≈S2​H\(k\)\.H^\{\(k\+2\)\}=S\\bigl\(S\\,H^\{\(k\)\}W^\{\(k\)\}\\bigr\)W^\{\(k\+1\)\}\\;\\approx\\;S^\{2\}\\,H^\{\(k\)\}\.
Now, there are no edges betweenAAandBBS, so a walk from a node inAAto another region must pass throughH′H^\{\\prime\}\. Similarly, a walk from a node inBBto another region must pass throughH′H^\{\\prime\}\. Hence foru∈Au\\in A,v∈Bv\\in B, and anyh∈H′h\\in H^\{\\prime\}the second layer embedding can be given by

hu\(2\)=\(S2​X\)u=∑w∈H∑z∈N​\(w\)∩AXz\+∑z∈N​\(u\)∩A∑w∈N​\(z\)∩HXw≈M​μH\+\(a−1\)​μA,\\begin\{split\}h\_\{u\}^\{\(2\)\}&=\(S^\{2\}X\)\_\{u\}=\\sum\_\{w\\in H\}\\sum\_\{z\\in N\(w\)\\,\\cap\\,A\}X\_\{z\}\\\\ &\\quad\+\\sum\_\{z\\in N\(u\)\\,\\cap\\,A\}\\sum\_\{w\\in N\(z\)\\,\\cap\\,H\}X\_\{w\}\\;\\approx\\;M\\,\\mu\_\{H\}\+\(a\-1\)\\,\\mu\_\{A\},\\end\{split\}\(29\)Similarly, for nodevvandhhwe have

hv\(2\)≈M​μH′\+\(b−1\)​μB,h\_\{v\}^\{\(2\)\}\\approx M\\,\\mu\_\{H\}^\{\\prime\}\+\(b\-1\)\\,\\mu\_\{B\},\(30\)
hh\(2\)≈M​μH′\+\(a−1\)​μA\+\(b−1\)​μB\.h\_\{h\}^\{\(2\)\}\\approx M\\,\\mu\_\{H\}^\{\\prime\}\+\(a\-1\)\\,\\mu\_\{A\}\+\(b\-1\)\\,\\mu\_\{B\}\.\(31\)
By subtracting and calculating the norm of \([29](https://arxiv.org/html/2605.10975#A1.E29)\) and \([30](https://arxiv.org/html/2605.10975#A1.E30)\) we get

‖hu\(2\)−hv\(2\)‖2≤‖\(a−1\)​μA−\(b−1\)​μB‖2≤\(a\+b\)∥μA−μB∥2=:\(a\+b\)δ\.\\begin\{split\}\\\|h\_\{u\}^\{\(2\)\}\-h\_\{v\}^\{\(2\)\}\\\|\_\{2\}&\\leq\\\|\(a\-1\)\\,\\mu\_\{A\}\-\(b\-1\)\\,\\mu\_\{B\}\\\|\_\{2\}\\\\ &\\leq\(a\+b\)\\,\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|\_\{2\}=:\(a\+b\)\\,\\delta\.\\end\{split\}\(32\)
By subtracting and calculating the norm of \([29](https://arxiv.org/html/2605.10975#A1.E29)\) and \([31](https://arxiv.org/html/2605.10975#A1.E31)\) we have

‖hu\(2\)−hh\(2\)‖2≥‖M​μH−\(\(a−1\)​μA\+\(b−1\)​μB\)‖2−\(a\+b\)​δ≥M​Δ−\(a\+b\)​δ,\\begin\{split\}\\\|h\_\{u\}^\{\(2\)\}\-h\_\{h\}^\{\(2\)\}\\\|\_\{2\}&\\geq\\left\\\|M\\,\\mu\_\{H\}\-\\bigl\(\(a\-1\)\\mu\_\{A\}\+\(b\-1\)\\mu\_\{B\}\\bigr\)\\right\\\|\_\{2\}\-\(a\+b\)\\,\\delta\\geq M\\,\\Delta\-\(a\+b\)\\,\\delta,\\end\{split\}\(33\)
Dividing \([32](https://arxiv.org/html/2605.10975#A1.E32)\) by \([33](https://arxiv.org/html/2605.10975#A1.E33)\) gives

‖hu\(2\)−hv\(2\)‖2‖hu\(2\)−hh\(2\)‖2≤\(a\+b\)​δM​Δ−\(a\+b\)​δ≤ρ1\+ϵ,ρ=a\+bM\.\\frac\{\\\|h\_\{u\}^\{\(2\)\}\-h\_\{v\}^\{\(2\)\}\\\|\_\{2\}\}\{\\\|h\_\{u\}^\{\(2\)\}\-h\_\{h\}^\{\(2\)\}\\\|\_\{2\}\}\\;\\leq\\;\\frac\{\(a\+b\)\\,\\delta\}\{M\\,\\Delta\-\(a\+b\)\\,\\delta\}\\;\\leq\\;\\frac\{\\rho\}\{1\+\\epsilon\},\\quad\\rho=\\frac\{a\+b\}\{M\}\.\(34\)So that afterL=2​kL=2klayers \([34](https://arxiv.org/html/2605.10975#A1.E34)\) becomes,

‖hu\(L\)−hv\(L\)‖2‖hu\(L\)−hh\(L\)‖2≤\(ρ1\+ϵ\)k=\(ρ1\+ϵ\)⌈L/2⌉,\\frac\{\\\|h\_\{u\}^\{\(L\)\}\-h\_\{v\}^\{\(L\)\}\\\|\_\{2\}\}\{\\\|h\_\{u\}^\{\(L\)\}\-h\_\{h\}^\{\(L\)\}\\\|\_\{2\}\}\\;\\leq\\;\\Bigl\(\\frac\{\\rho\}\{1\+\\epsilon\}\\Bigr\)^\{k\}\\;=\\;\\Bigl\(\\frac\{\\rho\}\{1\+\\epsilon\}\\Bigr\)^\{\\lceil L/2\\rceil\},\(35\)whereρ1\+ϵ<1\\frac\{\\rho\}\{1\+\\epsilon\}<1\. Therefore, spoke\-spoke separation diminishes exponentially in relation to the spoke\-hub separation across the layer of SMP\. This completes the proof\.■\\blacksquare

## Appendix BProof of Theorem 5\.1

Signed Message Passing \(SMP\) with a fixed signed adjacency matrixSScalculates the embedding of each layer as

H\(ℓ\+1\)=S​H\(ℓ\)\.H^\{\(\\ell\+1\)\}=SH^\{\(\\ell\)\}\.Then for theℓ\+2\\ell\+2layer, we can write

H\(ℓ\+2\)=S2​H\(ℓ\)=H\(ℓ\)\.H^\{\(\\ell\+2\)\}=S^\{2\}H^\{\(\\ell\)\}=H^\{\(\\ell\)\}\.Since =S2=IS^\{2\}=Ithe sign flips in matrix S for the layerℓ\+2\\ell\+2\. Morover, ifSScarries a global sign \(e\.g\.,S=−IS=\-Ion some subspace\), one can getH\(ℓ\+2\)=−H\(ℓ\)H^\{\(\\ell\+2\)\}=\-H^\{\(\\ell\)\}, i\.e\., an alternating\(−1\)ℓ\(\-1\)^\{\\ell\}pattern\. We will prove that our HMH model avoids sign flipping\.

In HMH encoder, the signed \(adaptive\) adjacency is recomputed per layer as

Aadp\(ℓ\)=2⋅softmaxj∈𝒩​\(i\)⁡\[Satt\(ℓ\)​\(i,j\)\+Sstruct\(ℓ\)​\(i,j\)\]−1,A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}=2\\cdot\\operatorname\{softmax\}\_\{j\\in\\mathcal\{N\}\(i\)\}\\\!\\bigl\[S^\{\(\\ell\)\}\_\{\\mathrm\{att\}\}\(i,j\)\+S^\{\(\\ell\)\}\_\{\\mathrm\{struct\}\}\(i,j\)\\bigr\]\-1,soAadp\(ℓ\)A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}depends onH\(ℓ\)H^\{\(\\ell\)\}and in generalAadp\(ℓ\+1\)≠Aadp\(ℓ\)A^\{\(\\ell\+1\)\}\_\{\\mathrm\{adp\}\}\\neq A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}\. The layer\-wise update is given by

H\(ℓ\+1\)=Aadp\(ℓ\)​H\(ℓ\)\.H^\{\(\\ell\+1\)\}=A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}H^\{\(\\ell\)\}\.Therefore, atℓ\+2\\ell\+2steps, we have

H\(ℓ\+2\)=Aadp\(ℓ\+1\)​Aadp\(ℓ\)​H\(ℓ\)\.H^\{\(\\ell\+2\)\}=A^\{\(\\ell\+1\)\}\_\{\\mathrm\{adp\}\}A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}H^\{\(\\ell\)\}\.For a deterministic\(−1\)2\(\-1\)^\{2\}sign flip \(or any fixed sign oscillation\) to persist one would need a fixed scalar relationship like

Aadp\(ℓ\+1\)​Aadp\(ℓ\)≈−IA^\{\(\\ell\+1\)\}\_\{\\mathrm\{adp\}\}A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}\\approx\-Iuniformly across layers, which is impossible when eachAadp\(ℓ\)A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}is a nonlinear function of the embedding at that particular levelℓ\\ell\. Equivalently, there is no constant scalarσ∈\{−1,1\}\\sigma\\in\\\{\-1,1\\\}such thatH\(ℓ\+2\)=σ​H\(ℓ\)H^\{\(\\ell\+2\)\}=\\sigma H^\{\(\\ell\)\}for allℓ\\ell, because that would require

Aadp\(ℓ\+1\)​Aadp\(ℓ\)=σ​IA^\{\(\\ell\+1\)\}\_\{\\mathrm\{adp\}\}A^\{\(\\ell\)\}\_\{\\mathrm\{adp\}\}=\\sigma Iwithσ\\sigmaindependent ofℓ\\ell, contradicting the adaptive \(data\-dependent\) recalculation\. Therefore, the HMH model avoid the rigid two\-step sign oscillation of the fixed SMP\. This completes the proof\.

## Appendix CProof of Theorem 5\.2

We analyze the eigenpairs of the original \(pre\-encoder\) LaplacianLL, denoted as\{\(λk,uk\)\}k=1n\\\{\(\\lambda\_\{k\},u\_\{k\}\)\\\}\_\{k=1\}^\{n\}withλ1≤⋯≤λn\\lambda\_\{1\}\\leq\\cdots\\leq\\lambda\_\{n\}\. To examine the spectral impact of the adaptive Laplacian, we divide the spectrum at indexτ\\tauinto the low\-frequency subspaceUlow=span⁡\{u1,…,uτ\}U\_\{\\mathrm\{low\}\}=\\operatorname\{span\}\\\{u\_\{1\},\\ldots,u\_\{\\tau\}\\\}and its orthogonal complementUhigh=span⁡\{uτ\+1,…,un\}U\_\{\\mathrm\{high\}\}=\\operatorname\{span\}\\\{u\_\{\\tau\+1\},\\ldots,u\_\{n\}\\\}\. We partition the edge set intoEsame=\{\(i,j\)∈E:yi=yj\}E\_\{\\mathrm\{same\}\}=\\\{\(i,j\)\\in E:y\_\{i\}=y\_\{j\}\\\}homophilous edges andEdiff=E∖EsameE\_\{\\mathrm\{diff\}\}=E\\setminus E\_\{\\mathrm\{same\}\}hetereophilous edges\. We now define the bounds for the similarity score as

ϵℓ=1−min\(i,j\)∈Esame⁡Si​j\(ℓ\),\\displaystyle\\epsilon\_\{\\ell\}\\;=\\;1\\;\-\\;\\min\_\{\(i,j\)\\in E\_\{\\mathrm\{same\}\}\}S\_\{ij\}^\{\(\\ell\)\},αℓ=1−max\(i,j\)∈Ediff⁡Si​j\(ℓ\),\\displaystyle\\alpha\_\{\\ell\}\\;=\\;1\\;\-\\;\\max\_\{\(i,j\)\\in E\_\{\\mathrm\{diff\}\}\}S\_\{ij\}^\{\(\\ell\)\},\(36\)whereϵℓ\\displaystyle\\epsilon\_\{\\ell\}indicates how much we can lower the weight of the ”most similar” same\-label edge andαℓ\\displaystyle\\alpha\_\{\\ell\}tells us how much the ”least similar” edge with a different label can still drive the signal toward homophily\. For layerℓ\\ell, letSi​j\(ℓ\)∈\[0,1\]S\_\{ij\}^\{\(\\ell\)\}\\in\[0,1\]be the encoder similarity and define the adaptive Laplacian

Ladp\(ℓ\):=L\+Δ\(ℓ\),L\_\{\\mathrm\{adp\}\}^\{\(\\ell\)\}\\;:=\\;L\+\\Delta^\{\(\\ell\)\},where the perturbation is specified*entrywise*by

Δi​j\(ℓ\)=\{−\(1−Si​j\(ℓ\)\),\(i,j\)∈Esame,\(1−Si​j\(ℓ\)\),\(i,j\)∈Ediff,0,i=j​or​\(i,j\)∉E\.\\Delta\_\{ij\}^\{\(\\ell\)\}\\;=\\;\\begin\{cases\}\-\\bigl\(1\-S\_\{ij\}^\{\(\\ell\)\}\\bigr\),&\(i,j\)\\in E\_\{\\mathrm\{same\}\},\\\\\[2\.0pt\] \\phantom\{\-\}\\bigl\(1\-S\_\{ij\}^\{\(\\ell\)\}\\bigr\),&\(i,j\)\\in E\_\{\\mathrm\{diff\}\},\\\\\[2\.0pt\] 0,&i=j\\ \\text\{or\}\\ \(i,j\)\\notin E\.\\end\{cases\}\(37\)For any\(i,j\)∈Esame\(i,j\)\\in E\_\{\\mathrm\{same\}\}, by definitionSi​j\(ℓ\)≥minEsame⁡Sp​q\(ℓ\)S\_\{ij\}^\{\(\\ell\)\}\\geq\\min\_\{E\_\{\\mathrm\{same\}\}\}S\_\{pq\}^\{\(\\ell\)\}, which implies1−Si​j\(ℓ\)≤1−minEsame⁡Sp​q\(ℓ\)=εℓ1\-S\_\{ij\}^\{\(\\ell\)\}\\leq 1\-\\min\_\{E\_\{\\mathrm\{same\}\}\}S\_\{pq\}^\{\(\\ell\)\}=\\varepsilon\_\{\\ell\}\.

For the caseΔi​j\(ℓ\)=−\(1−Si​j\(ℓ\)\)\\Delta\_\{ij\}^\{\(\\ell\)\}=\-\(1\-S\_\{ij\}^\{\(\\ell\)\}\)∀\(i,j\)∈Esame\\forall\(i,j\)\\in E\_\{\\mathrm\{same\}\}according to \([37](https://arxiv.org/html/2605.10975#A3.E37)\), it follows that−εℓ≤Δi​j\(ℓ\)≤0\-\\varepsilon\_\{\\ell\}\\leq\\Delta\_\{ij\}^\{\(\\ell\)\}\\leq 0\. Again for\(i,j\)∈Ediff\(i,j\)\\in E\_\{\\mathrm\{diff\}\}, by definitionSi​j\(ℓ\)≤maxEdiff⁡Sp​q\(ℓ\)S\_\{ij\}^\{\(\\ell\)\}\\leq\\max\_\{E\_\{\\mathrm\{diff\}\}\}S\_\{pq\}^\{\(\\ell\)\}\. So1−Si​j\(ℓ\)≥1−maxEdiff⁡Sp​q\(ℓ\)=αℓ1\-S\_\{ij\}^\{\(\\ell\)\}\\geq 1\-\\max\_\{E\_\{\\mathrm\{diff\}\}\}S\_\{pq\}^\{\(\\ell\)\}=\\alpha\_\{\\ell\}and also1−Si​j\(ℓ\)≤εℓ1\-S\_\{ij\}^\{\(\\ell\)\}\\leq\\varepsilon\_\{\\ell\}\.

For the caseΔi​j\(ℓ\)=\+\(1−Si​j\(ℓ\)\)\\Delta\_\{ij\}^\{\(\\ell\)\}=\+\(1\-S\_\{ij\}^\{\(\\ell\)\}\)∀\(i,j\)∈Ediff\\forall\(i,j\)\\in E\_\{\\mathrm\{diff\}\}according to \([37](https://arxiv.org/html/2605.10975#A3.E37)\), we obtain

αℓ≤Δi​j\(ℓ\)≤εℓ\.\\alpha\_\{\\ell\}\\leq\\Delta\_\{ij\}^\{\(\\ell\)\}\\leq\\varepsilon\_\{\\ell\}\.\(38\)Lets denote\{μk\(ℓ\)\}k=1n\\\{\\mu\_\{k\}^\{\(\\ell\)\}\\\}\_\{k=1\}^\{n\}be the eigenvalues ofLadp\(ℓ\)=L\+Δ\(ℓ\)L\_\{\\mathrm\{adp\}\}^\{\(\\ell\)\}=L\+\\Delta^\{\(\\ell\)\}\. To prove that Adaptive Adjacency works as high high\-pass and low\-pass filter, we will show the following:

\(i\) Low\-frequency \(smooth\) modes shift asμk\(ℓ\)≤λk\+εℓ​λτfor​k≤τ\.\\mu\_\{k\}^\{\(\\ell\)\}\\leq\\lambda\_\{k\}\+\\varepsilon\_\{\\ell\}\\lambda\_\{\\tau\}\\quad\\text\{for \}k\\leq\\tau\.So the low\-pass band remains essentially intact\.

\(ii\) High\-frequency modes receive a uniform positive lift as,μk\(ℓ\)≥λk\+βℓ​λτ\+1,\\mu\_\{k\}^\{\(\\ell\)\}\\geq\\lambda\_\{k\}\+\\beta\_\{\\ell\}\\lambda\_\{\\tau\+1\},, whereβ\>0\\beta\>0, thereby sharpening high\-pass separation and enhancing heterophilous contrast\.

According to the graph spectral theory\(Chung,,[1997](https://arxiv.org/html/2605.10975#bib.bib6)\), for anyx∈ℝnx\\in\\mathbb\{R\}^\{n\}, we expand

x⊤​Δ\(ℓ\)​x=12​∑\(i,j\)∈EΔi​j\(ℓ\)​\(xi−xj\)2\.x^\{\\top\}\\Delta^\{\(\\ell\)\}x=\\tfrac\{1\}\{2\}\\sum\_\{\(i,j\)\\in E\}\\Delta\_\{ij\}^\{\(\\ell\)\}\\,\(x\_\{i\}\-x\_\{j\}\)^\{2\}\.\(39\)
According to the \([37](https://arxiv.org/html/2605.10975#A3.E37)\) the edge‐wise boundΔi​j\(ℓ\)≥−εℓ\\Delta\_\{ij\}^\{\(\\ell\)\}\\geq\-\\varepsilon\_\{\\ell\}onEsameE\_\{\\mathrm\{same\}\}andΔi​j\(ℓ\)≤εℓ\\Delta\_\{ij\}^\{\(\\ell\)\}\\leq\\varepsilon\_\{\\ell\}onEdiffE\_\{\\mathrm\{diff\}\}, it follows that

x⊤​Δ\(ℓ\)​x\\displaystyle x^\{\\top\}\\Delta^\{\(\\ell\)\}x≤−εℓ2​∑\(i,j\)∈Esame\(xi−xj\)2\\displaystyle\\leq\-\\tfrac\{\\varepsilon\_\{\\ell\}\}\{2\}\\sum\_\{\(i,j\)\\in E\_\{\\mathrm\{same\}\}\}\(x\_\{i\}\-x\_\{j\}\)^\{2\}\(40\)\+εℓ2​∑\(i,j\)∈Ediff\(xi−xj\)2\.\\displaystyle\+\\;\\tfrac\{\\varepsilon\_\{\\ell\}\}\{2\}\\sum\_\{\(i,j\)\\in E\_\{\\mathrm\{diff\}\}\}\(x\_\{i\}\-x\_\{j\}\)^\{2\}\.
For anyx∈ℝnx\\in\\mathbb\{R\}^\{n\}and the total energy isQ=Qsame\+QdiffQ=Q\_\{\\text\{same\}\}\+Q\_\{\\text\{diff\}\}\(Chung,,[1997](https://arxiv.org/html/2605.10975#bib.bib6)\), we can define the edge energy splits as

Qsame​\(x\)\\displaystyle Q\_\{\\mathrm\{same\}\}\(x\)=∑\(i,j\)∈Esame\(xi−xj\)2,\\displaystyle=\\sum\_\{\(i,j\)\\in E\_\{\\mathrm\{same\}\}\}\(x\_\{i\}\-x\_\{j\}\)^\{2\},\(41\)Qdiff​\(x\)\\displaystyle Q\_\{\\mathrm\{diff\}\}\(x\)=∑\(i,j\)∈Ediff\(xi−xj\)2\.\\displaystyle=\\sum\_\{\(i,j\)\\in E\_\{\\mathrm\{diff\}\}\}\(x\_\{i\}\-x\_\{j\}\)^\{2\}\.\(42\)So using \([39](https://arxiv.org/html/2605.10975#A3.E39)\) and substituting \([42](https://arxiv.org/html/2605.10975#A3.E42)\), the total energy is

Q​\(x\)=Qsame​\(x\)\+Qdiff​\(x\)=2​x⊤​L​x\.Q\(x\)=Q\_\{\\mathrm\{same\}\}\(x\)\+Q\_\{\\mathrm\{diff\}\}\(x\)=2x^\{\\top\}Lx\.\(43\)
Letx∈Ulow∖\{0\}x\\in U\_\{\\mathrm\{low\}\}\\setminus\\\{0\\\}\. By the Rayleigh quotient\(Chung,,[1997](https://arxiv.org/html/2605.10975#bib.bib6)\),

x⊤​L​x‖x‖2≤λτ\.\\frac\{x^\{\\top\}Lx\}\{\\\|x\\\|^\{2\}\}\\;\\leq\\;\\lambda\_\{\\tau\}\.\(44\)Substituting the value ofQ​\(x\)Q\(x\)from \([43](https://arxiv.org/html/2605.10975#A3.E43)\) into \([44](https://arxiv.org/html/2605.10975#A3.E44)\) we get, \([44](https://arxiv.org/html/2605.10975#A3.E44)\) implies

Q​\(x\)≤2​λτ​‖x‖2\.Q\(x\)\\;\\leq\\;2\\,\\lambda\_\{\\tau\}\\,\\\|x\\\|^\{2\}\.\(45\)
Let defineρ:=\|Esame\|/\|E\|∈\(0,1\)\\rho:=\|E\_\{\\mathrm\{same\}\}\|/\|E\|\\in\(0,1\)the homophily ratio \(for a heterophilous graph,0<ρ<120<\\rho<\\tfrac\{1\}\{2\}\)\. By edge counting theory\(Chung,,[1997](https://arxiv.org/html/2605.10975#bib.bib6)\),

Qdiff​\(x\)Q​\(x\)≤1−ρ⟹Qdiff​\(x\)≤\(1−ρ\)​Q​\(x\)\.\\frac\{Q\_\{\\mathrm\{diff\}\}\(x\)\}\{Q\(x\)\}\\;\\leq\\;1\-\\rho\\;\\;\\Longrightarrow\\;\\;Q\_\{\\mathrm\{diff\}\}\(x\)\\;\\leq\\;\(1\-\\rho\)\\,Q\(x\)\.\(46\)Combining \([46](https://arxiv.org/html/2605.10975#A3.E46)\) with \([45](https://arxiv.org/html/2605.10975#A3.E45)\) yields

Qdiff​\(x\)≤2​\(1−ρ\)​λτ​‖x‖2,Q\_\{\\mathrm\{diff\}\}\(x\)\\;\\leq\\;2\(1\-\\rho\)\\,\\lambda\_\{\\tau\}\\,\\\|x\\\|^\{2\},\(47\)i\.e\.,

∑\(i,j\)∈Ediff\(xi−xj\)2≤2​\(1−ρ\)​λτ​‖x‖2\.\\sum\_\{\(i,j\)\\in E\_\{\\mathrm\{diff\}\}\}\\\!\\\!\(x\_\{i\}\-x\_\{j\}\)^\{2\}\\;\\leq\\;2\(1\-\\rho\)\\,\\lambda\_\{\\tau\}\\,\\\|x\\\|^\{2\}\.\(48\)
Similarly, fromQsame​\(x\)=Q​\(x\)−Qdiff​\(x\)Q\_\{\\mathrm\{same\}\}\(x\)=Q\(x\)\-Q\_\{\\mathrm\{diff\}\}\(x\)and \([46](https://arxiv.org/html/2605.10975#A3.E46)\),

Qsame​\(x\)≥ρ​Q​\(x\)≥\([45](https://arxiv.org/html/2605.10975#A3.E45)\)2​ρ​λτ​‖x‖2,Q\_\{\\mathrm\{same\}\}\(x\)\\;\\geq\\;\\rho\\,Q\(x\)\\;\\stackrel\{\{\\scriptstyle\\eqref\{eq:Q\-bound\}\}\}\{\{\\geq\}\}\\;2\\rho\\,\\lambda\_\{\\tau\}\\,\\\|x\\\|^\{2\},\(49\)i\.e\.,

∑\(i,j\)∈Esame\(xi−xj\)2≥2​ρ​λτ​‖x‖2\.\\sum\_\{\(i,j\)\\in E\_\{\\mathrm\{same\}\}\}\\\!\\\!\(x\_\{i\}\-x\_\{j\}\)^\{2\}\\;\\geq\\;2\\rho\\,\\lambda\_\{\\tau\}\\,\\\|x\\\|^\{2\}\.\(50\)
Substituting the bounds \([50](https://arxiv.org/html/2605.10975#A3.E50)\) and \([48](https://arxiv.org/html/2605.10975#A3.E48)\) into the quadratic form bound \([40](https://arxiv.org/html/2605.10975#A3.E40)\), we have

x⊤​Δ\(ℓ\)​x\\displaystyle x^\{\\top\}\\Delta^\{\(\\ell\)\}x≤−εℓ2⋅2​ρ​λτ​‖x‖2\+εℓ2⋅2​\(1−ρ\)​λτ​‖x‖2\\displaystyle\\leq\-\\tfrac\{\\varepsilon\_\{\\ell\}\}\{2\}\\cdot 2\\rho\\lambda\_\{\\tau\}\\\|x\\\|^\{2\}\+\\tfrac\{\\varepsilon\_\{\\ell\}\}\{2\}\\cdot 2\(1\-\\rho\)\\lambda\_\{\\tau\}\\\|x\\\|^\{2\}=εℓ​\(1−ρ−ρ\)​λτ​‖x‖2\\displaystyle=\\varepsilon\_\{\\ell\}\\bigl\(1\-\\rho\-\\rho\\bigr\)\\lambda\_\{\\tau\}\\\|x\\\|^\{2\}=εℓ​\(1−2​ρ\)​λτ​‖x‖2\.\\displaystyle=\\varepsilon\_\{\\ell\}\(1\-2\\rho\)\\lambda\_\{\\tau\}\\\|x\\\|^\{2\}\.\(51\)Alternatively, we have

x⊤​Δ\(ℓ\)​x‖x‖2≤εℓ​λτ,\\frac\{x^\{\\top\}\\Delta^\{\(\\ell\)\}x\}\{\\\|x\\\|^\{2\}\}\\leq\\varepsilon\_\{\\ell\}\\lambda\_\{\\tau\},\(52\)
Applying the Courant\-Fischer min\-max principle\(Chung,,[1997](https://arxiv.org/html/2605.10975#bib.bib6)\)forLa​d​pℓL\_\{adp\}^\{\\ell\}, for any eigen valueμk\\mu\_\{k\}we get,

μk\(ℓ\)=mindimS=k⁡max0≠x∈S⁡x⊤​\(L\+Δ\(ℓ\)\)​x‖x‖2\.\\displaystyle\\mu\_\{k\}^\{\(\\ell\)\}=\\min\_\{\\dim S=k\}\\max\_\{0\\neq x\\in S\}\\frac\{x^\{\\top\}\(L\+\\Delta^\{\(\\ell\)\}\)x\}\{\\\|x\\\|^\{2\}\}\.\(53\)
Case I: Low pass filter:LetS=Ulow=span​\{u1,…,uτ\}S=U\_\{\\mathrm\{low\}\}=\\mathrm\{span\}\\\{u\_\{1\},\\dots,u\_\{\\tau\}\\\}, sodimS≥k\\dim S\\geq k\. Applying \([53](https://arxiv.org/html/2605.10975#A3.E53)\) toLa​d​pL\_\{adp\}for anyx∈Ulow∖\{0\}x\\in U\_\{\\mathrm\{low\}\}\\setminus\\\{0\\\}and substituting from \([52](https://arxiv.org/html/2605.10975#A3.E52)\) we get,

x⊤​\(L\+Δ\(ℓ\)\)​x‖x‖2≤x⊤​L​x‖x‖2\+x⊤​Δ\(ℓ\)​x‖x‖2≤λk\+εℓ​λτ\.\\frac\{x^\{\\top\}\(L\+\\Delta^\{\(\\ell\)\}\)x\}\{\\\|x\\\|^\{2\}\}\\leq\\frac\{x^\{\\top\}Lx\}\{\\\|x\\\|^\{2\}\}\+\\frac\{x^\{\\top\}\\Delta^\{\(\\ell\)\}x\}\{\\\|x\\\|^\{2\}\}\\leq\\lambda\_\{k\}\+\\varepsilon\_\{\\ell\}\\lambda\_\{\\tau\}\.Taking the minimum over all suchSS, according to \([53](https://arxiv.org/html/2605.10975#A3.E53)\) yields,

μk\(ℓ\)≤λk\+εℓ​λτ,k≤τ\.\\mu\_\{k\}^\{\(\\ell\)\}\\leq\\lambda\_\{k\}\+\\varepsilon\_\{\\ell\}\\lambda\_\{\\tau\},\\qquad k\\leq\\tau\.\(54\)
#### Case II: High pass filter:

According to \([37](https://arxiv.org/html/2605.10975#A3.E37)\) for anyx∈ℝnx\\in\\mathbb\{R\}^\{n\}we can express

x⊤​Δ\(ℓ\)​x\\displaystyle x^\{\\top\}\\Delta^\{\(\\ell\)\}x≥−εℓ2​Qsame​\(x\)\+αℓ2​Qdiff​\(x\)\.\\displaystyle\\geq\\;\-\\frac\{\\varepsilon\_\{\\ell\}\}\{2\}\\,Q\_\{\\mathrm\{same\}\}\(x\)\\;\+\\;\\frac\{\\alpha\_\{\\ell\}\}\{2\}\\,Q\_\{\\mathrm\{diff\}\}\(x\)\.\(55\)
UsingQdiff​\(x\)=Q​\(x\)−Qsame​\(x\)Q\_\{\\mathrm\{diff\}\}\(x\)=Q\(x\)\-Q\_\{\\mathrm\{same\}\}\(x\)in \([55](https://arxiv.org/html/2605.10975#A3.E55)\) gives

x⊤​Δ\(ℓ\)​x\\displaystyle x^\{\\top\}\\Delta^\{\(\\ell\)\}x≥−εℓ2​Qsame​\(x\)\+αℓ2​\[Q​\(x\)−Qsame​\(x\)\]\\displaystyle\\geq\-\\frac\{\\varepsilon\_\{\\ell\}\}\{2\}\\,Q\_\{\\mathrm\{same\}\}\(x\)\+\\frac\{\\alpha\_\{\\ell\}\}\{2\}\\,\\bigl\[Q\(x\)\-Q\_\{\\mathrm\{same\}\}\(x\)\\bigr\]=12​\[αℓ​Q​\(x\)−\(αℓ\+εℓ\)​Qsame​\(x\)\]\\displaystyle=\\frac\{1\}\{2\}\\Bigl\[\\alpha\_\{\\ell\}\\,Q\(x\)\\;\-\\;\\bigl\(\\alpha\_\{\\ell\}\+\\varepsilon\_\{\\ell\}\\bigr\)\\,Q\_\{\\mathrm\{same\}\}\(x\)\\Bigr\]\(56\)≥12​\[αℓ​\(1−ρ\)−εℓ​ρ\]​Q​\(x\)\\displaystyle\\geq\\frac\{1\}\{2\}\\Bigl\[\\alpha\_\{\\ell\}\(1\-\\rho\)\-\\varepsilon\_\{\\ell\}\\rho\\Bigr\]\\,Q\(x\)\(57\)≥\[αℓ​\(1−ρ\)−εℓ​ρ\]​λτ\+1​‖x‖2\.\\displaystyle\\geq\\;\\bigl\[\\alpha\_\{\\ell\}\(1\-\\rho\)\-\\varepsilon\_\{\\ell\}\\rho\\bigr\]\\,\\lambda\_\{\\tau\+1\}\\,\\\|x\\\|^\{2\}\.\(58\)Applying \([53](https://arxiv.org/html/2605.10975#A3.E53)\) toLa​d​pL\_\{adp\}for anyx∈Ulow∖\{0\}x\\in U\_\{\\mathrm\{low\}\}\\setminus\\\{0\\\}and substituting from \([58](https://arxiv.org/html/2605.10975#A3.E58)\) we get,

x⊤​\(L\+Δ\(ℓ\)\)​x\\displaystyle x^\{\\top\}\\bigl\(L\+\\Delta^\{\(\\ell\)\}\\bigr\)x≥λτ\+1​‖x‖2\+\[αℓ​\(1−ρ\)−εℓ​ρ\]\\displaystyle\\geq\\lambda\_\{\\tau\+1\}\\,\\\|x\\\|^\{2\}\+\\bigl\[\\alpha\_\{\\ell\}\(1\-\\rho\)\-\\varepsilon\_\{\\ell\}\\rho\\bigr\]\\,λτ\+1​‖x‖2\\displaystyle~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\lambda\_\{\\tau\+1\}\\,\\\|x\\\|^\{2\}=\[1\+αℓ​\(1−ρ\)−εℓ​ρ\]​λτ\+1​‖x‖2\.\\displaystyle=\\bigl\[\\,1\+\\alpha\_\{\\ell\}\(1\-\\rho\)\-\\varepsilon\_\{\\ell\}\\rho\\,\\bigr\]\\,\\lambda\_\{\\tau\+1\}\\,\\\|x\\\|^\{2\}\.\(59\)Therefore, from \([C](https://arxiv.org/html/2605.10975#A3.Ex19)\) we have

x⊤​\(L\+Δ\(ℓ\)\)​x‖x‖2≥x⊤​L​x‖x‖2\+x⊤​Δ\(ℓ\)​x‖x‖2≥λk\+αℓ​\(1−ρ\)​λτ\+1\.\\frac\{x^\{\\top\}\(L\+\\Delta^\{\(\\ell\)\}\)x\}\{\\\|x\\\|^\{2\}\}\\geq\\frac\{x^\{\\top\}Lx\}\{\\\|x\\\|^\{2\}\}\+\\frac\{x^\{\\top\}\\Delta^\{\(\\ell\)\}x\}\{\\\|x\\\|^\{2\}\}\\geq\\lambda\_\{k\}\+\\alpha\_\{\\ell\}\(1\-\\rho\)\\lambda\_\{\\tau\+1\}\.Applying the Courant\-Fischer theorem fork\>τk\>\\tauwe get,μk\(ℓ\)≥λk\+αℓ​\(1−ρ\)​λτ\+1,k\>τ\.\\mu\_\{k\}^\{\(\\ell\)\}\\geq\\lambda\_\{k\}\+\\alpha\_\{\\ell\}\(1\-\\rho\)\\lambda\_\{\\tau\+1\},\\qquad k\>\\tau\.

Thus, for both cases,

\{μk\(ℓ\)≤λk\+εℓ​λτ,k≤τ,μk\(ℓ\)≥λk\+αℓ​\(1−ρ\)​λτ\+1,k\>τ\.\\left\\\{\\begin\{aligned\} &\\mu\_\{k\}^\{\(\\ell\)\}\\leq\\lambda\_\{k\}\+\\varepsilon\_\{\\ell\}\\lambda\_\{\\tau\},&&k\\leq\\tau,\\\\ &\\mu\_\{k\}^\{\(\\ell\)\}\\geq\\lambda\_\{k\}\+\\alpha\_\{\\ell\}\(1\-\\rho\)\\lambda\_\{\\tau\+1\},&&k\>\\tau\.\\end\{aligned\}\\right\.\(60\)Therefore, each low pass frequency is changed only very smaller amountεℓ<<1\\varepsilon\_\{\\ell\}<<1and each high\-frequency eigenvalue ofLa​d​aL\_\{ada\}\(k\>τk\>\\tau\) is*raised*by at least\[αℓ​\(1−ρ\)−εℓ​ρ\]​λτ\+1\>0\.\\bigl\[\\alpha\_\{\\ell\}\(1\-\\rho\)\-\\varepsilon\_\{\\ell\}\\rho\\bigr\]\\,\\lambda\_\{\\tau\+1\}\>0\.This means that the adaptive Laplacian makes those modes harder to smooth away and boosts the eigenvalue associated with high frequency mode\. This completes the proof\.■\\blacksquare

## Appendix DProof of Theorem 5\.3

Consider two disjoint small clustersA,B⊂VA,B\\subset V, and a large hub regionH′⊂VH^\{\\prime\}\\subset V, such thatA∩B=∅,A∩H′=∅,B∩H′=∅\.A\\cap B=\\varnothing,\\qquad A\\cap H^\{\\prime\}=\\varnothing,\\qquad B\\cap H^\{\\prime\}=\\varnothing\.LetxA,xB∈ℝ\|V\|x\_\{A\},x\_\{B\}\\in\\mathbb\{R\}^\{\|V\|\}be denoted as unit\-norm normalized indicator signal vectors that are supported on clustersAAandBB\. It means that\(xA\)i=0\(x\_\{A\}\)\_\{i\}=0for every nodei∉Ai\\notin A\.

Now consider a single linear filter defined asℱ:ℝ\|V\|→ℝ\|V\|\\mathcal\{F\}:\\mathbb\{R\}^\{\|V\|\}\\to\\mathbb\{R\}^\{\|V\|\}\. A stack ofLLlayers of Filter is defined asℱ\(L\)=ℱL​⋯​ℱ1\\mathcal\{F\}^\{\(L\)\}=\\mathcal\{F\}\_\{L\}\\cdots\\mathcal\{F\}\_\{1\}, where eachℱℓ\\mathcal\{F\}\_\{\\ell\}is a linear filter\. We define the separation ratio of two cluster signals afterLLfiltering layers to pre filter embeddings as

r​\(L\)=‖ℱ\(L\)​xA−ℱ\(L\)​xB‖2‖xA−xB‖2,r\(L\)=\\frac\{\\left\\\|\\mathcal\{F\}^\{\(L\)\}x\_\{A\}\-\\mathcal\{F\}^\{\(L\)\}x\_\{B\}\\right\\\|\_\{2\}\}\{\\left\\\|x\_\{A\}\-x\_\{B\}\\right\\\|\_\{2\}\},whereℱ\(L\)​xA\\mathcal\{F\}^\{\(L\)\}x\_\{A\}is the filter acting on region A andℱ\(L\)​xB\\mathcal\{F\}^\{\(L\)\}x\_\{B\}acting on region B\. The filterF\(L\)F^\{\(L\)\}is diagonal in the localized orthonormal basis, so it rescales each coordinate by gainsgkg\_\{k\}\. We will show that⟨F\(L\)​xA,F\(L\)​xB⟩=0,\\langle F^\{\(L\)\}x\_\{A\},\\,F^\{\(L\)\}x\_\{B\}\\rangle=0,i\.e\., no cross\-region leakage\. We will also demonstrate that the separation between the two signals after filtering is preserved up to a scaling factor, i\.e\.,gmin≤r​\(L\)≤gmaxg\_\{\\min\}\\leq r\(L\)\\leq g\_\{\\max\}\. This means filter restricts regional patterns and preserves their contrast, altering only their magnitude by diagonal gains\.

LetB′=\[b1′,…,bn′\]∈ℝn×nB^\{\\prime\}=\[b^\{\\prime\}\_\{1\},\\dots,b^\{\\prime\}\_\{n\}\]\\in\\mathbb\{R\}^\{n\\times n\}be an*orthogonal, spatially localized*basis \(B′⁣⊤​B′=B′​B′⁣⊤=IB^\{\\prime\\\!\\top\}B^\{\\prime\}=B^\{\\prime\}B^\{\\prime\\\!\\top\}=I\) such that each columnbk′b^\{\\prime\}\_\{k\}is supported entirely in exactly one ofAA,BB, orHH\. Define disjoint index sets asΩA:=\{k:supp⁡\(bk′\)⊆A\},ΩB:=\{k:supp⁡\(bk′\)⊆B\},ΩH:=\{1,…,n\}∖\(ΩA∪ΩB\)\.\\Omega\_\{A\}:=\\\{k:\\operatorname\{supp\}\(b^\{\\prime\}\_\{k\}\)\\subseteq A\\\},\\quad\\Omega\_\{B\}:=\\\{k:\\operatorname\{supp\}\(b^\{\\prime\}\_\{k\}\)\\subseteq B\\\},\\quad\\Omega\_\{H\}:=\\\{1,\\dots,n\\\}\\setminus\(\\Omega\_\{A\}\\cup\\Omega\_\{B\}\)\.Assume each layerFℓF\_\{\\ell\}is diagonal inB′B^\{\\prime\}:

Fℓ=B′​diag​\(h\(ℓ\)\)​B′⁣⊤,ℓ=1,…,L\.F\_\{\\ell\}\\;=\\;B^\{\\prime\}\\,\\mathrm\{diag\}\\\!\\big\(h^\{\(\\ell\)\}\\big\)\\,B^\{\\prime\\\!\\top\},\\qquad\\ell=1,\\dots,L\.Hence the stack

F\(L\):=FL​⋯​F1=B′​diag​\(g\)​B′⁣⊤,gk:=∏ℓ=1Lhk\(ℓ\)\.F^\{\(L\)\}:=F\_\{L\}\\cdots F\_\{1\}=B^\{\\prime\}\\,\\mathrm\{diag\}\(g\)\\,B^\{\\prime\\\!\\top\},\\qquad g\_\{k\}:=\\prod\_\{\\ell=1\}^\{L\}h^\{\(\\ell\)\}\_\{k\}\.Any signalX∈ℝ\|V\|X\\in\\mathbb\{R\}^\{\|V\|\}can be represented asX=B′​cX=B^\{\\prime\}c, with the coefficients defined byc=B′⁣⊤​xc=B^\{\\prime\\top\}x\. Due to localization we can write,

xA\\displaystyle x\_\{A\}=B′​cAwhere\(cA\)k=0​∀k∉ΩA,\\displaystyle=B^\{\\prime\}c\_\{A\}\\quad\\text\{where\}\\quad\(c\_\{A\}\)\_\{k\}=0\\;\\;\\forall k\\notin\\Omega\_\{A\},xB\\displaystyle x\_\{B\}=B′​cBwhere\(cB\)k=0​∀k∉ΩB\.\\displaystyle=B^\{\\prime\}c\_\{B\}\\quad\\text\{where\}\\quad\(c\_\{B\}\)\_\{k\}=0\\;\\;\\forall k\\notin\\Omega\_\{B\}\.Moreover, the signals are orthogonal, resulting in the inner product⟨xA,xB⟩=cA⊤​cB=0\\langle x\_\{A\},x\_\{B\}\\rangle=c\_\{A\}^\{\\top\}c\_\{B\}=0\(orthonormality\)\. Then the inner product of the filter is

⟨F\(L\)​xA,F\(L\)​xB⟩=\(diag​\(g\)​cA\)⊤​\(diag​\(g\)​cB\)=∑kgk2​\(cA\)k​\(cB\)k=0,\\begin\{split\}\\langle F^\{\(L\)\}x\_\{A\},\\,F^\{\(L\)\}x\_\{B\}\\rangle&=\\bigl\(\\mathrm\{diag\}\(g\)\\,c\_\{A\}\\bigr\)^\{\\top\}\\bigl\(\\mathrm\{diag\}\(g\)\\,c\_\{B\}\\bigr\)\\\\ &=\\sum\_\{k\}g\_\{k\}^\{2\}\\,\(c\_\{A\}\)\_\{k\}\\,\(c\_\{B\}\)\_\{k\}=0,\\end\{split\}\(61\)since for every indexkk, at least one of\(cA\)k\(c\_\{A\}\)\_\{k\}or\(cB\)k\(c\_\{B\}\)\_\{k\}is zero\. Orthogonality implies‖x‖2=‖B′⁣⊤​x‖2\\\|x\\\|\_\{2\}=\\\|B^\{\\prime\\\!\\top\}x\\\|\_\{2\}\. BecausecAc\_\{A\}andcBc\_\{B\}have disjoint supports,

‖xA−xB‖22=‖cA‖22\+‖cB‖22\.\\\|x\_\{A\}\-x\_\{B\}\\\|\_\{2\}^\{2\}=\\\|c\_\{A\}\\\|\_\{2\}^\{2\}\+\\\|c\_\{B\}\\\|\_\{2\}^\{2\}\.\(62\)Also, for the filtering, we can write,

‖F\(L\)​xA−F\(L\)​xB‖22=‖diag​\(g\)​cA‖22\+‖diag​\(g\)​cB‖22=∑kgk2​\(\(cA\)k2\+\(cB\)k2\)\.\\begin\{split\}\\\|F^\{\(L\)\}x\_\{A\}\-F^\{\(L\)\}x\_\{B\}\\\|\_\{2\}^\{2\}&=\\\|\\mathrm\{diag\}\(g\)\\,c\_\{A\}\\\|\_\{2\}^\{2\}\+\\\|\\mathrm\{diag\}\(g\)\\,c\_\{B\}\\\|\_\{2\}^\{2\}\\\\ &=\\sum\_\{k\}g\_\{k\}^\{2\}\\\!\\left\(\(c\_\{A\}\)\_\{k\}^\{2\}\+\(c\_\{B\}\)\_\{k\}^\{2\}\\right\)\.\\end\{split\}\(63\)Letgmin=mink⁡\|gk\|g\_\{\\min\}=\\min\_\{k\}\|g\_\{k\}\|andgmax=maxk⁡\|gk\|g\_\{\\max\}=\\max\_\{k\}\|g\_\{k\}\|\. Then using \([62](https://arxiv.org/html/2605.10975#A4.E62)\) and \([63](https://arxiv.org/html/2605.10975#A4.E63)\), we can get a bound as

gmin2​\(‖cA‖22\+‖cB‖22\)≤‖F\(L\)​xA−F\(L\)​xB‖22≤gmax2​\(‖cA‖22\+‖cB‖22\)\.\\begin\{split\}g\_\{\\min\}^\{2\}\\\!\\left\(\\\|c\_\{A\}\\\|\_\{2\}^\{2\}\+\\\|c\_\{B\}\\\|\_\{2\}^\{2\}\\right\)&\\leq\\\|F^\{\(L\)\}x\_\{A\}\-F^\{\(L\)\}x\_\{B\}\\\|\_\{2\}^\{2\}\\\\ &\\leq g\_\{\\max\}^\{2\}\\\!\\left\(\\\|c\_\{A\}\\\|\_\{2\}^\{2\}\+\\\|c\_\{B\}\\\|\_\{2\}^\{2\}\\right\)\.\\end\{split\}\(64\)Taking square roots and using \([62](https://arxiv.org/html/2605.10975#A4.E62)\) yieldsgmin≤r​\(L\)≤gmax\.g\_\{\\min\}\\leq r\(L\)\\leq g\_\{\\max\}\.

Thus, the separation ratio afterLLlayers is squeezed between the smallest and largest gains over all basis coordinates\. This completes the proof\.■\\blacksquare

## Appendix EProof of Theorem 5\.4

At Level 2 of the hierarchy, we are applying the HMH algorithm\. Let’s denote the clusters as A, B, and H’, whereA=\|a\|A=\|a\|,B=\|b\|B=\|b\|,H′=\|M\|H^\{\\prime\}=\|M\|anda,b<<Ma,b<<M\. Now we assume their means feature byμH,μA,μB\\mu\_\{H\},\\mu\_\{A\},\\mu\_\{B\}withμA≠μB\\mu\_\{A\}\\neq\\mu\_\{B\}\. Also, since we assumed the encoder outputXXis constant on each cluster, its inner product with any such wavelet \(inter\-class wavelets\) vanishes because of the orthogonal property\.

Define the global scaling and cluster\-contrast basis vectors as

s\\displaystyle s:=1M\+a\+b​1,\\displaystyle=\\;\\tfrac\{1\}\{M\+a\+b\}\\mathbf\{1\},\(65\)wA,H′\\displaystyle w\_\{A,H^\{\\prime\}\}:=a​\(M\+a\)M​1A−M​\(M\+a\)a​1H′,\\displaystyle=\\;\\sqrt\{\\tfrac\{a\(M\+a\)\}\{M\}\}\\mathbf\{1\}\_\{A\}\\;\-\\;\\sqrt\{\\tfrac\{M\(M\+a\)\}\{a\}\}\\mathbf\{1\}\_\{H^\{\\prime\}\},wB,H′\\displaystyle w\_\{B,H^\{\\prime\}\}:=b​\(M\+b\)M​1B−M​\(M\+b\)b​1H′\.\\displaystyle=\\;\\sqrt\{\\tfrac\{b\(M\+b\)\}\{M\}\}\\mathbf\{1\}\_\{B\}\\;\-\\;\\sqrt\{\\tfrac\{M\(M\+b\)\}\{b\}\}\\mathbf\{1\}\_\{H^\{\\prime\}\}\.where𝟏A\\mathbf\{1\}\_\{A\},𝟏B\\mathbf\{1\}\_\{B\}and𝟏H′\\mathbf\{1\}\_\{H^\{\\prime\}\}are indicator vectors for clustersAABB, andH′H^\{\\prime\}respectively\. These are the only basis vectors with nonzero projection on constant\-per\-cluster signals\.

Now define the projector of this basis as

P:=s​s⊤,W:=wA,H′​wA,H′⊤\+wB,H′​wB,H′⊤\.P:=ss^\{\\top\},\\qquad W:=w\_\{A,H^\{\\prime\}\}w\_\{A,H^\{\\prime\}\}^\{\\top\}\+w\_\{B,H^\{\\prime\}\}w\_\{B,H^\{\\prime\}\}^\{\\top\}\.The Haar filter is defined as

Φ:=λsc​P\+λwav​W,0<λsc≤λwav\.\\Phi:=\\lambda\_\{\\mathrm\{sc\}\}P\+\\lambda\_\{\\mathrm\{wav\}\}W,\\qquad 0<\\lambda\_\{\\mathrm\{sc\}\}\\leq\\lambda\_\{\\mathrm\{wav\}\}\.\(66\)According to the encoder design, it follows thatP\+W=IP\+W=Ion that subspace; every such vectorxxdecomposes uniquely asx=P​x\+W​x,x=Px\+Wx,whereP​xPxis the hub\-dominated mean component andW​xWxencodes the spoke–hub contrasts\. The filter then suppresses the former and amplifies the latter as,

Φ​x=λsc​P​x\+λwav​W​x,λwavλsc=λgain≫1\.\\Phi x=\\lambda\_\{\\mathrm\{sc\}\}Px\+\\lambda\_\{\\mathrm\{wav\}\}Wx,\\qquad\\frac\{\\lambda\_\{\\mathrm\{wav\}\}\}\{\\lambda\_\{\\mathrm\{sc\}\}\}=\\lambda\_\{\\mathrm\{gain\}\}\\gg 1\.
Let’s denote the post\-filter value of the node ishh\. For any clusterT∈\{A,B,H\}T\\in\\\{A,B,H\\\}, denoteh¯T=1\|T\|​∑i∈Thi\\bar\{h\}\_\{T\}=\\frac\{1\}\{\|T\|\}\\sum\_\{i\\in T\}h\_\{i\}as the mean of embeddinghhoverTT\. The mean embeddings forAA,BBandHHcan be defined as

h¯A\\displaystyle\\bar\{h\}\_\{A\}=λsc​x¯\+λwav​cAa,\\displaystyle=\\lambda\_\{\\mathrm\{sc\}\}\\bar\{x\}\+\\lambda\_\{\\mathrm\{wav\}\}\\frac\{c\_\{A\}\}\{a\},\(67\)h¯B\\displaystyle\\bar\{h\}\_\{B\}=λsc​x¯\+λwav​cBb,\\displaystyle=\\lambda\_\{\\mathrm\{sc\}\}\\bar\{x\}\+\\lambda\_\{\\mathrm\{wav\}\}\\frac\{c\_\{B\}\}\{b\},h¯H′\\displaystyle\\bar\{h\}\_\{H^\{\\prime\}\}=λsc​x¯−λwav​\(Ma​cA\+Mb​cB\)\.\\displaystyle=\\lambda\_\{\\mathrm\{sc\}\}\\bar\{x\}\-\\lambda\_\{\\mathrm\{wav\}\}\\\!\\left\(\\frac\{M\}\{a\}c\_\{A\}\+\\frac\{M\}\{b\}c\_\{B\}\\right\)\.wherex¯=M​μH′\+a​μA\+b​μBM\+a\+b\\bar\{x\}=\\frac\{M\\mu\_\{H^\{\\prime\}\}\+a\\mu\_\{A\}\+b\\mu\_\{B\}\}\{M\+a\+b\}andcA=a​MM\+a​\(μA−μH′\),cB=b​MM\+b​\(μB−μH′\)\.c\_\{A\}=\\frac\{aM\}\{M\+a\}\(\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\),\\qquad c\_\{B\}=\\frac\{bM\}\{M\+b\}\(\\mu\_\{B\}\-\\mu\_\{H^\{\\prime\}\}\)\.

To assess the separation between clustersAAandBBafter filtering, subtract their means and square the means using \([67](https://arxiv.org/html/2605.10975#A5.E67)\), we get

‖h¯A−h¯B‖2=λwav2​Ma\+b​‖μA−μB‖2\.\\\|\\bar\{h\}\_\{A\}\-\\bar\{h\}\_\{B\}\\\|^\{2\}=\\lambda\_\{\\mathrm\{wav\}\}^\{2\}\\frac\{M\}\{a\+b\}\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|^\{2\}\.\(68\)Similarly, for the difference between clusterAAand the hubHHusing \([67](https://arxiv.org/html/2605.10975#A5.E67)\), we get

h¯A−h¯H′\\displaystyle\\bar\{h\}\_\{A\}\-\\bar\{h\}\_\{H^\{\\prime\}\}=\(λsc​x¯\+λwav​cAa\)−\(λsc​x¯−λwav​cA\+cBM\)\\displaystyle=\\left\(\\lambda\_\{\\mathrm\{sc\}\}\\,\\bar\{x\}\+\\lambda\_\{\\mathrm\{wav\}\}\\,\\frac\{c\_\{A\}\}\{a\}\\right\)\-\\left\(\\lambda\_\{\\mathrm\{sc\}\}\\,\\bar\{x\}\-\\lambda\_\{\\mathrm\{wav\}\}\\,\\frac\{c\_\{A\}\+c\_\{B\}\}\{M\}\\right\)=λwav​\(cAa\+cA\+cBM\)\.\\displaystyle=\\lambda\_\{\\mathrm\{wav\}\}\\left\(\\frac\{c\_\{A\}\}\{a\}\+\\frac\{c\_\{A\}\+c\_\{B\}\}\{M\}\\right\)\.\(69\)
‖h¯A−h¯H′‖2≲λwav2​aM​‖μA−μH′‖2\.\\\|\\bar\{h\}\_\{A\}\-\\bar\{h\}\_\{H^\{\\prime\}\}\\\|^\{2\}\\lesssim\\lambda\_\{\\mathrm\{wav\}\}^\{2\}\\frac\{a\}\{M\}\\\|\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\\\|^\{2\}\.\(70\)Let’s define the two key distances after filtering as

ΔA​B:=‖h¯A−h¯B‖,ΔA​H′:=‖h¯A−h¯H′‖,\\Delta\_\{AB\}:=\\\|\\bar\{h\}\_\{A\}\-\\bar\{h\}\_\{B\}\\\|,\\quad\\Delta\_\{AH^\{\\prime\}\}:=\\\|\\bar\{h\}\_\{A\}\-\\bar\{h\}\_\{H^\{\\prime\}\}\\\|,\(71\)whereh¯A\\bar\{h\}\_\{A\},h¯B\\bar\{h\}\_\{B\}, andh¯H′\\bar\{h\}\_\{H^\{\\prime\}\}are the cluster means of the filtered features onAA,BB, andHHrespectively\.

Substituting \([71](https://arxiv.org/html/2605.10975#A5.E71)\) into \([68](https://arxiv.org/html/2605.10975#A5.E68)\) we get

ΔA​B2=λwav2​Ma\+b​‖μA−μB‖2,\\Delta\_\{AB\}^\{2\}=\\lambda\_\{\\mathrm\{wav\}\}^\{2\}\\frac\{M\}\{a\+b\}\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|^\{2\},\(72\)and again substituting \([71](https://arxiv.org/html/2605.10975#A5.E71)\) into \([70](https://arxiv.org/html/2605.10975#A5.E70)\), we have

ΔA​H′2≤λwav2​aM​‖μA−μH′‖2\.\\Delta\_\{AH^\{\\prime\}\}^\{2\}\\leq\\lambda\_\{\\mathrm\{wav\}\}^\{2\}\\frac\{a\}\{M\}\\\|\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\\\|^\{2\}\.\(73\)
Dividing \([72](https://arxiv.org/html/2605.10975#A5.E72)\) by \([73](https://arxiv.org/html/2605.10975#A5.E73)\), we obtain

ΔA​BΔA​H′\\displaystyle\\frac\{\\Delta\_\{AB\}\}\{\\Delta\_\{AH^\{\\prime\}\}\}≳λwav2​Ma\+b​‖μA−μB‖2λwav2​aM​‖μA−μH′‖2\\displaystyle\\gtrsim\\frac\{\\sqrt\{\\lambda\_\{\\mathrm\{wav\}\}^\{2\}\\frac\{M\}\{a\+b\}\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|^\{2\}\}\}\{\\sqrt\{\\lambda\_\{\\mathrm\{wav\}\}^\{2\}\\frac\{a\}\{M\}\\\|\\mu\_\{A\}\-\\mu\_\{H\}^\{\\prime\}\\\|^\{2\}\}\}\(74\)=M/\(a\+b\)a/M⋅‖μA−μB‖‖μA−μH′‖\\displaystyle=\\frac\{\\sqrt\{M/\(a\+b\)\}\}\{\\sqrt\{a/M\}\}\\cdot\\frac\{\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|\}\{\\\|\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\\\|\}\(75\)=Ma\+b⋅‖μA−μB‖‖μA−μH′‖\.\\displaystyle=\\frac\{M\}\{a\+b\}\\cdot\\frac\{\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|\}\{\\\|\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\\\|\}\.\(76\)Now, before applying the basis, we applied the heterophyllous encoder, which gave us the mean embeddings of the cluster\.

Define a*unit*vectorxu∈ℝdx\_\{u\}\\in\\mathbb\{R\}^\{d\}as the heterophilous encoder output of nodeuu\. Assume encoder outputs are unit vectors with signed marginκ\>0\\kappa\>0:⟨xu,xv⟩≥κ\\langle x\_\{u\},x\_\{v\}\\rangle\\geq\\kappaifyu=yvy\_\{u\}=y\_\{v\}and≤−κ\\leq\-\\kappaotherwise\. And also‖μA‖=‖μB‖=1\\\|\\mu\_\{A\}\\\|=\\\|\\mu\_\{B\}\\\|=1\(layer normalization\)\.

For every heterophilous edge\(u,h\)\(u,h\)withu∈A∪Bu\\in A\\cup B,h′∈H′h^\{\\prime\}\\in H^\{\\prime\}, we can write‖xu‖=‖xh′‖=1\\\|x\_\{u\}\\\|=\\\|x\_\{h\}^\{\\prime\}\\\|=1\. Hence‖xu−xh′‖2=2−2​⟨xu,xh⟩≥2\+2​κ\\\|x\_\{u\}\-x\_\{h\}^\{\\prime\}\\\|^\{2\}=2\-2\\langle x\_\{u\},x\_\{h\}\\rangle\\geq 2\+2\\kappa\. So we can express

‖xu−xh′‖≥2​\(1\+κ\)\.\\\|x\_\{u\}\-x\_\{h\}^\{\\prime\}\\\|\\;\\geq\\;\\sqrt\{\\,2\\bigl\(1\+\\kappa\\bigr\)\}\.\(77\)
AveragingMMunit vectors shrinks the deviations of features of nodes in hubH′H^\{\\prime\}as

‖xh′−μH′‖≤1M,∀h∈H′\.\\\|x\_\{h\}^\{\\prime\}\-\\mu\_\{H^\{\\prime\}\}\\\|\\;\\leq\\;\\frac\{1\}\{\\sqrt\{M\}\},\\qquad\\forall h\\in H^\{\\prime\}\.\(78\)Taking the difference to theμA\\mu\_\{A\}andμh\\mu\_\{h\}and applying triangle inequality gives us,

‖μA−μH′‖\\displaystyle\\\|\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\\\|≤‖μA−xh′‖\+‖xh′−μH′‖\.\\displaystyle\\leq\\\|\\mu\_\{A\}\-x\_\{h\}^\{\\prime\}\\\|\+\\\|x\_\{h\}^\{\\prime\}\-\\mu\_\{H^\{\\prime\}\}\\\|\.\(79\)Using the \([77](https://arxiv.org/html/2605.10975#A5.E77)\) and \([78](https://arxiv.org/html/2605.10975#A5.E78)\) we can write

‖μA−μH′‖≤2​2​\(1\+κ\)M\.\\;\\\|\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\\\|\\;\\leq\\;\\frac\{2\\sqrt\{2\(1\+\\kappa\)\}\}\{\\sqrt\{M\}\}\.\(80\)Applying the similar reasoning toμB\\mu\_\{B\}andμH\\mu\_\{H\}gives

‖μB−μH′‖≤2​2​\(1\+κ\)M\.\\;\\\|\\mu\_\{B\}\-\\mu\_\{H^\{\\prime\}\}\\\|\\;\\leq\\;\\frac\{2\\sqrt\{2\(1\+\\kappa\)\}\}\{\\sqrt\{M\}\}\.\(81\)Again, using the triangle inequality, we can write for the mean feature of A and B as follows,

‖μA−μB‖\\displaystyle\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|≥‖μA−xh‖−‖μB−xh‖\.\\displaystyle\\geq\\\|\\mu\_\{A\}\-x\_\{h\}\\\|\-\\\|\\mu\_\{B\}\-x\_\{h\}\\\|\.\(triangle\)Using \([77](https://arxiv.org/html/2605.10975#A5.E77)\) and \([78](https://arxiv.org/html/2605.10975#A5.E78)\), we get,

‖μA−μB‖≥2​\(1\+κ\)​\(1−2M\)\.\\;\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|\\;\\geq\\;\\sqrt\{2\(1\+\\kappa\)\}\\Bigl\(1\-\\tfrac\{2\}\{\\sqrt\{M\}\}\\Bigr\)\.\(82\)With \([82](https://arxiv.org/html/2605.10975#A5.E82)\) in the numerator and \([80](https://arxiv.org/html/2605.10975#A5.E80)\) in the denominator,

‖μA−μB‖‖μA−μH′‖≥2​\(1\+κ\)​\(1−2M\)2​2​\(1\+κ\)/M\\displaystyle\\frac\{\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|\}\{\\\|\\mu\_\{A\}\-\\mu\_\{H^\{\\prime\}\}\\\|\}\\;\\geq\\;\\frac\{\\sqrt\{2\(1\+\\kappa\)\}\\,\\bigl\(1\-\\tfrac\{2\}\{\\sqrt\{M\}\}\\bigr\)\}\{2\\sqrt\{2\(1\+\\kappa\)\}/\\sqrt\{M\}\}\(83\)=M​\(1−2M\)\>1\.\\displaystyle=\\sqrt\{M\}\\,\\Bigl\(1\-\\tfrac\{2\}\{\\sqrt\{M\}\}\\Bigr\)\>1\.\(84\)By symmetry the same bound holds for‖μA−μB‖/‖μB−μH′‖\\\|\\mu\_\{A\}\-\\mu\_\{B\}\\\|/\\\|\\mu\_\{B\}\-\\mu\_\{H^\{\\prime\}\}\\\|\. Now substituting in \([76](https://arxiv.org/html/2605.10975#A5.E76)\) we get ,

ΔA​BΔA​H′≥M​\(1−2M\)\>1\.\\frac\{\\Delta\_\{AB\}\}\{\\Delta\_\{AH^\{\\prime\}\}\}\\geq\\sqrt\{M\}\\,\\Bigl\(1\-\\tfrac\{2\}\{\\sqrt\{M\}\}\\Bigr\)\>1\.\(85\)No matter how large the hubHHbecomes, the post\-filter gap between the two tiny spokesAAandBBremains at least a fixed fraction of their separation fromHH\. Thus enlarging the hubHHcan never shrink the spoke–spoke separation below the spoke–hub separation, avoiding hub aliasing\. This completes the proof\.

## Appendix FProof of Theorem 5\.5

Case I: Oversquashing:Oversquashing occurs when gradients \(or messages\) from distant nodes decay exponentially with graph distance, preventing long\-range information flow\(Giraldo et al\.,,[2023](https://arxiv.org/html/2605.10975#bib.bib12)\)\. GivenJu​v\(L\)=∂Hu\(L\)∂XvJ\_\{uv\}^\{\(L\)\}=\\tfrac\{\\partial H\_\{u\}^\{\(L\)\}\}\{\\partial X\_\{v\}\}be the Jacobian of theLL\-layer embedding of nodeuuwith respect to the input of nodevv, anddG​\(u,v\)d\_\{G\}\(u,v\)denotes their shortest\-path distance\. Over Squashing occurs if there exist constants0<σ<10<\\sigma<1andD∗≥1D^\{\\ast\}\\\!\\geq 1such that‖Ju​v\(L\)‖2≤σdG​\(u,v\),∀L,∀u,v​with​dG​\(u,v\)≥D∗\.\\bigl\\\|J\_\{uv\}^\{\(L\)\}\\bigr\\\|\_\{2\}\\;\\leq\\;\\sigma^\{\\,d\_\{G\}\(u,v\)\},\\quad\\forall L,\\;\\forall u,v\\text\{ with \}d\_\{G\}\(u,v\)\\geq D^\{\\ast\}\.

Let the fine\-level input features beH\(0\)=X∈ℝN0×d0H^\{\(0\)\}=X\\in\\mathbb\{R\}^\{N\_\{0\}\\times d\_\{0\}\}withHi\(0\)=xiH^\{\(0\)\}\_\{i\}=x\_\{i\},i∈V\(0\)i\\in V^\{\(0\)\}\. For each macro\-layerℓ=0,…,L−1\\ell=0,\\ldots,L\-1:

Coarsen:H~\(ℓ\+1\)=P\(ℓ\+1\)​H\(ℓ\)∈ℝNℓ\+1×dℓ\\displaystyle\\tilde\{H\}^\{\(\\ell\+1\)\}=P^\{\(\\ell\+1\)\}H^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{N\_\{\\ell\+1\}\\times d\_\{\\ell\}\}Signed encoding:H^\(ℓ\+1\)=E\(ℓ\)​H~\(ℓ\+1\)\\displaystyle\\hat\{H\}^\{\(\\ell\+1\)\}=E^\{\(\\ell\)\}\\tilde\{H\}^\{\(\\ell\+1\)\}Haar filter:H¯\(ℓ\+1\)=Φ\(ℓ\)​H^\(ℓ\+1\)\\displaystyle\\bar\{H\}^\{\(\\ell\+1\)\}=\\Phi^\{\(\\ell\)\}\\hat\{H\}^\{\(\\ell\+1\)\}Unpool:H\(ℓ\+1\)=P\(0\)​H¯\(ℓ\+1\),\\displaystyle H^\{\(\\ell\+1\)\}=P^\{\(0\)\}\\bar\{H\}^\{\(\\ell\+1\)\},where atP\(ℓ\+1\)∈ℝNℓ\+1×NℓP^\{\(\\ell\+1\)\}\\\!\\in\\\!\\mathbb\{R\}^\{N\_\{\\ell\+1\}\\times N\_\{\\ell\}\}coarsens the graph,Φ\(ℓ\)=U\(ℓ\)​d​i​a​g​\(λsc\(ℓ\),Λwav\(ℓ\)\)​U\(ℓ\)⊤\\Phi^\{\(\\ell\)\}=U^\{\(\\ell\)\}\\;\\\!diag\\;\\\!\\big\(\\lambda\_\{\\mathrm\{sc\}\}^\{\(\\ell\)\},\\Lambda\_\{\\mathrm\{wav\}\}^\{\(\\ell\)\}\\big\)U^\{\(\\ell\)\\top\}is the Haar filter,E\(ℓ\)E^\{\(\\ell\)\}is the signed encoder andP\(0\)∈ℝN0×Nℓ\+1P^\{\(0\)\}\\\!\\in\\\!\\mathbb\{R\}^\{N\_\{0\}\\times N\_\{\\ell\+1\}\}up\-samples back to the original nodes \. Composed all of the above givesh\(ℓ\+1\)=P\(0\)​Φ\(ℓ\)​E\(ℓ\)​P\(ℓ\+1\)​H\(ℓ\)h^\{\(\\ell\+1\)\}=P^\{\(0\)\}\\Phi^\{\(\\ell\)\}E^\{\(\\ell\)\}P^\{\(\\ell\+1\)\}H^\{\(\\ell\)\}\. Defining the linear macro\-layer map asM′⁣\(ℓ\)=P\(0\)​Φ\(ℓ\)​E\(ℓ\)​P\(ℓ\+1\)M^\{\\prime\(\\ell\)\}=P^\{\(0\)\}\\Phi^\{\(\\ell\)\}E^\{\(\\ell\)\}P^\{\(\\ell\+1\)\}, whereM′⁣\(ℓ\):ℝNℓ×dℓ→ℝN0×dℓ\+1M^\{\\prime\(\\ell\)\}:\\mathbb\{R\}^\{N\_\{\\ell\}\\times d\_\{\\ell\}\}\\to\\mathbb\{R\}^\{N\_\{0\}\\times d\_\{\\ell\+1\}\}, we can express

H\(ℓ\+1\)=M\(ℓ\)​H\(ℓ\),ℓ=0,…,L−1,H\(0\)=X\.H^\{\(\\ell\+1\)\}=M^\{\(\\ell\)\}\\,H^\{\(\\ell\)\},\\qquad\\ell=0,\\dots,L\-1,\\qquad H^\{\(0\)\}=X\.\(86\)By unrolling the layers we get,

H\(1\)\\displaystyle H^\{\(1\)\}=M′⁣\(0\)​X,\\displaystyle=M^\{\\prime\(0\)\}X,\(87\)H\(2\)\\displaystyle H^\{\(2\)\}=M′⁣\(1\)​M\(0\)​X,\\displaystyle=M^\{\\prime\(1\)\}M^\{\(0\)\}X,⋮\\displaystyle\\vdotsH\(L\)\\displaystyle H^\{\(L\)\}=M′⁣\(L−1\)\.\.M\(0\)X\.\\displaystyle=M^\{\\prime\(L\-1\)\}\.\.M^\{\(0\)\}X\.Since eachM′⁣\(ℓ\)M^\{\\prime\(\\ell\)\}is linear, we apply the chain rule recursively as

∂H\(L\)∂X=M′⁣\(L−1\)​∂H\(L−1\)∂X=M′⁣\(L−1\)​M′⁣\(L−2\)​∂H\(L−2\)∂X⋮=M′⁣\(L−1\)​M′⁣\(L−2\)​⋯​M′⁣\(0\)\.\\begin\{split\}\\frac\{\\partial H^\{\(L\)\}\}\{\\partial X\}&=M^\{\\prime\(L\-1\)\}\\,\\frac\{\\partial H^\{\(L\-1\)\}\}\{\\partial X\}\\\\ &=M^\{\\prime\(L\-1\)\}M^\{\\prime\(L\-2\)\}\\,\\frac\{\\partial H^\{\(L\-2\)\}\}\{\\partial X\}\\\\ &\\quad\\,\\vdots\\\\ &=M^\{\\prime\(L\-1\)\}M^\{\\prime\(L\-2\)\}\\cdots M^\{\\prime\(0\)\}\.\\end\{split\}\(88\)
Letδ​Xv\\delta X\_\{v\}be a perturbation at nodev∈Gv\\in Gandδ​Hu\(L\)\\delta H\_\{u\}^\{\(L\)\}the change in the output at nodeu∈Gu\\in G\. The message Jacobian,Ju​v\(L\)=∂Hu\(L\)∂XvJ\_\{uv\}^\{\(L\)\}=\\frac\{\\partial H\_\{u\}^\{\(L\)\}\}\{\\partial X\_\{v\}\}, from inputXXto final outputH\(L\)H^\{\(L\)\}, using \([88](https://arxiv.org/html/2605.10975#A6.E88)\) can calculated as

Ju​v\(L\)=\[M′⁣\(L−1\)\]u,:\.​\[M′⁣\(L−2\)\]\.,\.​⋯​\[M′⁣\(0\)\]:,v,J\_\{uv\}^\{\(L\)\}=\[M^\{\\prime\(L\-1\)\}\]\_\{u,:\.\}\[M^\{\\prime\(L\-2\)\}\]\_\{\.,\.\}\\cdots\[M^\{\\prime\(0\)\}\]\_\{:,v\},or, equivalently,

Ju​v\(L\)=\[P\(0\)​Φ\(L−1\)​E\(L−1\)​P\(L\)\]​⋯​\[P\(0\)​Φ\(0\)​E\(0\)​P\(1\)\]\.J\_\{uv\}^\{\(L\)\}=\[P^\{\(0\)\}\\Phi^\{\(L\-1\)\}E^\{\(L\-1\)\}P^\{\(L\)\}\]\\cdots\[P^\{\(0\)\}\\Phi^\{\(0\)\}E^\{\(0\)\}P^\{\(1\)\}\]\.\(89\)Alternatively, we can write, by the chain rule, the message Jacobian is

Ju​v\(L\)=\[∏ℓ=0L−1M′⁣\(ℓ\)\]u,v\.J\_\{uv\}^\{\(L\)\}=\\bigl\[\\prod\_\{\\ell=0\}^\{L\-1\}M^\{\\prime\(\\ell\)\}\\bigr\]\_\{u,v\}\.\(90\)Letd=dG​\(u,v\)d=d\_\{G\}\(u,v\)is the distance between the nodeuuandvv\. Afterℓ\\ellcoarsening according to the coarsening algorithm, theu→vu\\\!\\to\\\!vpath has lengthk​\(ℓ\)≤⌈d/rℓ⌉k\(\\ell\)\\leq\\lceil d/r^\{\\ell\}\\rceil\(since the coarseing ratio is r and the tree length isll\) for some contractionr\>1r\>1\. Assume, afterℓ\\elllevels of coarsening,uuandvvare mapped to super\-nodes connected by a path of lengthk​\(ℓ\)k\(\\ell\)\. Now denote the sequence of coarse nodes on that path byi1,…,ik​\(ℓ\)⊆V\(ℓ\)i\_\{1\},\\dots,i\_\{k\(\\ell\)\}\\subseteq V^\{\(\\ell\)\}\. The path\-tube subspace at levelℓ\\ellisT\(ℓ\)=span​\{ei1,…,eik​\(ℓ\)\}⊂ℝNℓT^\{\(\\ell\)\}=\\mathrm\{span\}\\\{e\_\{i\_\{1\}\},\\dots,e\_\{i\_\{k\(\\ell\)\}\}\\\}\\subset\\mathbb\{R\}^\{N\_\{\\ell\}\}andS\(ℓ\):=P\(ℓ\+1\)​T\(ℓ\)S^\{\(\\ell\):=P^\{\(\\ell\+1\)\}T^\{\(\\ell\)\}\}its image under pooling in the layerℓ\+1\\ell\+1\. Then by definition of the restricted operator norm\(Horn & Johnson,,[2012](https://arxiv.org/html/2605.10975#bib.bib16)\),

‖M′⁣\(ℓ\)‖2,T\(ℓ\)=supX∈T\(ℓ\)‖X‖=1‖P\(0\)​Φ\(ℓ\)​E\(ℓ\)​P\(ℓ\+1\)​X‖\.\\\|M^\{\\prime\(\\ell\)\}\\\|\_\{2,\\,T^\{\(\\ell\)\}\}=\\sup\_\{\\begin\{subarray\}\{c\}X\\in T^\{\(\\ell\)\}\\\\ \\\|X\\\|=1\\end\{subarray\}\}\\\|P^\{\(0\)\}\\Phi^\{\(\\ell\)\}E^\{\(\\ell\)\}P^\{\(\\ell\+1\)\}X\\\|\.For any unitz∈S\(ℓ\)z\\in S^\{\(\\ell\)\}there existsX∈T\(ℓ\)X\\in T^\{\(\\ell\)\}withP\(ℓ\+1\)​X=zP^\{\(\\ell\+1\)\}X=z, so using‖P\(0\)‖2=1\\\|P^\{\(0\)\}\\\|\_\{2\}=1,

‖M′⁣\(ℓ\)‖2,T\(ℓ\)≥supz∈S\(ℓ\)‖z‖=1‖Φ\(ℓ\)​E\(ℓ\)​z‖=‖Φ\(ℓ\)​E\(ℓ\)‖2,S\(ℓ\)\.\\\|M^\{\\prime\(\\ell\)\}\\\|\_\{2,\\,T^\{\(\\ell\)\}\}\\geq\\sup\_\{\\begin\{subarray\}\{c\}z\\in S^\{\(\\ell\)\}\\\\ \\\|z\\\|=1\\end\{subarray\}\}\\\|\\Phi^\{\(\\ell\)\}E^\{\(\\ell\)\}z\\\|=\\\|\\Phi^\{\(\\ell\)\}E^\{\(\\ell\)\}\\\|\_\{2,\\,S^\{\(\\ell\)\}\}\.Hence, we can write

‖M′⁣\(ℓ\)‖2,T\(ℓ\)≥‖Φ\(ℓ\)​E\(ℓ\)‖2,S\(ℓ\)\.\\\|M^\{\\prime\(\\ell\)\}\\\|\_\{2,\\,T^\{\(\\ell\)\}\}\\geq\\\|\\Phi^\{\(\\ell\)\}E^\{\(\\ell\)\}\\\|\_\{2,\\,S^\{\(\\ell\)\}\}\.\(91\)
Now we can bound the encoder and haar filter output as follows: \(i\) EncoderOn thek​\(ℓ\)k\(\\ell\)\-edge path, the signed\-Laplacian encoderE\(ℓ\)=I−Ladp\(ℓ\)E^\{\(\\ell\)\}=I\-L\_\{\\mathrm\{adp\}\}^\{\(\\ell\)\}amplifies each “heterophilous” edge by at leastγ¯\>1\\underline\{\\gamma\}\>1, so

‖E\(ℓ\)‖2,k​\(ℓ\)≥\(γ¯\)k​\(ℓ\)\.\\\|E^\{\(\\ell\)\}\\\|\_\{2,\\,k\(\\ell\)\}\\geq\(\\underline\{\\gamma\}\)^\{k\(\\ell\)\}\.\(92\)\(ii\) Haar\-Filter Contribution\.The Haar filter shrinks the low mode byλsc<1\\lambda\_\{\\mathrm\{sc\}\}<1, but stretches each high\-frequency mode byλwav\>1\\lambda\_\{\\mathrm\{wav\}\}\>1\(in analysis and synthesis\), so on the detail subspace,

‖Φ\(ℓ\)‖2,k​\(ℓ\)≥\(λwav\(ℓ\)\)2≥\(λ¯wav\)2,λ¯wav\>1\.\\\|\\Phi^\{\(\\ell\)\}\\\|\_\{2,\\,k\(\\ell\)\}\\geq\(\\lambda\_\{\\mathrm\{wav\}\}^\{\(\\ell\)\}\)^\{2\}\\geq\(\\underline\{\\lambda\}\_\{\\mathrm\{wav\}\}\)^\{2\},\\quad\\underline\{\\lambda\}\_\{\\mathrm\{wav\}\}\>1\.\(93\)Using the inequality \([92](https://arxiv.org/html/2605.10975#A6.E92)\) and \([93](https://arxiv.org/html/2605.10975#A6.E93)\) and substituting back to \([91](https://arxiv.org/html/2605.10975#A6.E91)\) we get,

‖M′⁣\(ℓ\)‖2,k​\(ℓ\)\\displaystyle\\\|M^\{\\prime\(\\ell\)\}\\\|\_\{2,\\,k\(\\ell\)\}≥\(λ¯wav\)2​\(γ¯\)k​\(ℓ\)\.\\displaystyle\\geq\(\\underline\{\\lambda\}\_\{\\mathrm\{wav\}\}\)^\{2\}\(\\underline\{\\gamma\}\)^\{k\(\\ell\)\}\.\(94\)Thus substituting \([94](https://arxiv.org/html/2605.10975#A6.E94)\) into \([90](https://arxiv.org/html/2605.10975#A6.E90)\) we get,

‖Ju​v​\(L\)‖2≥∏ℓ=0L−1\[\(λ¯wav\)2​γ¯k​\(ℓ\)\]=\(λ¯wav\)2​L​γ¯∑ℓk​\(ℓ\)\.\\\|J\_\{uv\}\(L\)\\\|\_\{2\}\\geq\\prod\_\{\\ell=0\}^\{L\-1\}\\left\[\(\\underline\{\\lambda\}\_\{\\mathrm\{wav\}\}\)^\{2\}\\underline\{\\gamma\}^\{k\(\\ell\)\}\\right\]=\(\\underline\{\\lambda\}\_\{\\mathrm\{wav\}\}\)^\{2L\}\\underline\{\\gamma\}^\{\\sum\_\{\\ell\}k\(\\ell\)\}\.\(95\)Afterℓ\\ellrounds of coarsening, these nodes map to super\-nodes connected by a path of lengthk​\(ℓ\)≤⌈d/rℓ⌉k\(\\ell\)\\leq\\lceil d/r^\{\\ell\}\\rceil, for some contraction factorr\>1r\>1\. So we can write

∑ℓ=0L−1k​\(ℓ\)≤∑ℓ=0∞⌈drℓ⌉=O​\(d\)\.\\sum\_\{\\ell=0\}^\{L\-1\}k\(\\ell\)\\leq\\sum\_\{\\ell=0\}^\{\\infty\}\\left\\lceil\\frac\{d\}\{r^\{\\ell\}\}\\right\\rceil=O\(d\)\.\(96\)Therefore, the bound \([95](https://arxiv.org/html/2605.10975#A6.E95)\) becomes

‖Ju​v​\(L\)‖2≥\(λ¯wav\)2​L​dc\\\|J\_\{uv\}\(L\)\\\|\_\{2\}\\geq\(\\underline\{\\lambda\}\_\{\\mathrm\{wav\}\}\)^\{2L\}\\,d^\{c\}\(97\)for somec\>0c\>0\. In contrast, over\-squashing would require‖Ju​v​\(L\)‖2≤σd\\\|J\_\{uv\}\(L\)\\\|\_\{2\}\\leq\\sigma^\{d\}for someσ<1\\sigma<1\. Thus, this polynomial lower bound precludes exponential decay and proves the absence of over\-squashing\.

Case II: Oversmoothing:Oversmoothing means different class means collapse for distinct classes \(e\.g\., spokes\)A,BA,B,‖μA\(L\)−μB\(L\)‖→0\\\|\\mu\_\{A\}^\{\(L\)\}\-\\mu\_\{B\}^\{\(L\)\}\\\|\\to 0as depthLLgrows\. In Theorem 5\.4, we have proved,

‖μA\(L\)−μB\(L\)‖‖μA\(L\)−μH′\(L\)‖≥M​\(1−2M\)\>1,\\frac\{\\\|\\mu\_\{A\}^\{\(L\)\}\-\\mu\_\{B\}^\{\(L\)\}\\\|\}\{\\\|\\mu\_\{A\}^\{\(L\)\}\-\\mu\_\{H^\{\\prime\}\}^\{\(L\)\}\\\|\}\\geq\\sqrt\{M\}\\Bigl\(1\-\\frac\{2\}\{\\sqrt\{M\}\}\\Bigr\)\>1,\(98\)so‖μA\(L\)−μB\(L\)‖\>‖μA\(L\)−μH′\(L\)‖\\\|\\mu\_\{A\}^\{\(L\)\}\-\\mu\_\{B\}^\{\(L\)\}\\\|\>\\\|\\mu\_\{A\}^\{\(L\)\}\-\\mu\_\{H^\{\\prime\}\}^\{\(L\)\}\\\|\. Thus, any decay of the spoke–spoke gap forces at least as fast \(indeed faster\) decay of the spoke–hub gap\. Now, we can assume the spoke consists of nodes of the same class, and hubs are the neighbors of the spokes\. Equation \([98](https://arxiv.org/html/2605.10975#A6.E98)\) still holds for the assumption\. So we can say if over any class means it is separated from the other class, node means irrespective of the neighbor node influence\. This ensures thatlimL→∞‖μA\(L\)−μB\(L\)‖≠0,\\lim\_\{L\\to\\infty\}\\\|\\mu\_\{A\}^\{\(L\)\}\-\\mu\_\{B\}^\{\(L\)\}\\\|\\;\\neq\\;0,avoiding over\-smoothing\. This completes the proof\.■\\blacksquare

## Appendix GDatasets and Experiment Settings

Table 5:Ablation study \(node classification accuracy, %\)\. Mean±\\pmstd over 10 runs\.#### Dataset descriptions\.

- •CoraandCiteseerare citation networks \(nodes = publications, edges = citations\) characterized by bag\-of\-words characteristics and subject\-category labels\. Cora has 7 labels, while Citeseer has 6\. We use the usual semi\-supervised splits\. For Cora, there are 140 training nodes \(20 per class\), 500 for validation, and 1000 for testing\. For Citeseer, there are 120 training nodes \(20 for each class\), 500 for validation, and 1000 for testing\.
- •Actoris a Wikipedia co\-occurrence network where nodes denotes actors and edges represent the occurrence of two actors appearing on the same page\. It also has keyword\-based characteristics and categorization labels\. It has five classes and minimal homophily\. We use the standard split: 100 training nodes \(20 per class\), 500 for validation, and 1000 for testing\.
- •ChameleonandSquirrelare Wikipedia page\-to\-page graphs with nodes \(pages\) and edges \(mutual links\)\. They have keyword\-based features and labels depending on traffic\. There are five classes in each\. We use the ”filtered” versions \(with duplicates removed\) and the ”dense” splits that were publicly provided in earlier work: 60%\\%for training, 20%\\%for validation, and 20%\\%for testing\.
- •Texas,Wisconsin, andCornellare WebKB graphs with bag\-of\-words features and five different types of page\-type labels\. The nodes are CS department pages, and the edges are hyperlinks\. We employ the typical semi\-supervised protocol, which involves using 20 labeled nodes per class for training, 30 per class for validation, and the remaining nodes for testing\.

#### Dataset statistics and homophily\.

To measure local neighborhood label consistency, we calculate edge homophily \(the fraction of edges connecting same\-label nodes\) for each graph\. Low edge homophily suggests a heterophilous structure with distinct labels for nearby nodes, worsening hub\-aliasing\. Previous research found that Cora and Citeseer are homophilous, but Actor, Chameleon, Squirrel, Texas, Wisconsin, and Cornell are heterophilous and require a particular heterophilous algorithm\. For datasets such as Cora, Citeseer, Chameleon, Squirrel, DBLP, Coauthor\-CS, and Coauthor\-Physics, we use the implementations provided in PyTorch Geometric\. For Chameleon\-filtered, Squirrel\-filtered, Minesweeper, Tolokers, Amazon\-ratings, and Questions, we use the raw data released byPlatonov et al\., \([2023](https://arxiv.org/html/2605.10975#bib.bib30)\)\. Forogbn\-arxiv, we use the Open Graph Benchmark\. Dataset statistics are reported in Table[6](https://arxiv.org/html/2605.10975#A7.T6)\.

Table 6:Dataset statistics\.
#### Running Environment

All experiments were performed on a with dual NVIDIA RTX 4090 GPUs \(each possessing 16 GB of VRAM\) and 32 GB of system memory\.

#### Hyperparameter Settings for HMH

Hyperparameters were selected by maximizing validation accuracy using Optuna with 10 trials per dataset\. Below are the key components and their settings:

- •Encoder embedding dimension\(d′d^\{\\prime\}\): 64 / 128 / 256 \(dataset\-dependent\)\.
- •Clustering & CoarseningReduction ratioRR: 0\.5 \(default\), tuned in \{0\.3, 0\.5, 0\.7\} for depth trade\-off\.
- •Haar Basis & Spectral Filtering Scaling gainλsc\(ℓ\)\\lambda\_\{\\mathrm\{sc\}\}^\{\(\\ell\)\}: initialized<1<1, learned subject to constraint0<λsc\(ℓ\)<10<\\lambda\_\{\\mathrm\{sc\}\}^\{\(\\ell\)\}<1\. And Wavelet gainλwav\(ℓ\)\\lambda\_\{\\mathrm\{wav\}\}^\{\(\\ell\)\}: initialized\>1\>1, learned with lower bound\>1\>1\.
- •Loss weights:λdiv\\lambda\_\{\\mathrm\{div\}\}andλrec\\lambda\_\{\\mathrm\{rec\}\}tuned in \{0\.1, 0\.5, 1\.0\}; default 0\.5\.
- •Optimizer: AdamW with weight decay in\[1​e−5,1​e−3\]\[1\\mathrm\{e\}\{\-5\},1\\mathrm\{e\}\{\-3\}\]\.
- •Learning rate: tuned in\[1​e−4,5​e−3\]\[1\\mathrm\{e\}\{\-4\},5\\mathrm\{e\}\{\-3\}\]; typical value1​e−31\\mathrm\{e\}\{\-3\}\.
- •Batch size: We set the batch size to 32 for graph classification and 1 for node classification\.
- •Dropout: 0\.3\.
- •Training epochs: 200 with early stopping on validation loss \(patience 50\)\.

Table 7:HMH hyperparameters: \(a\) search ranges; \(b\) selected values for node classification\.\(a\) Key hyperparameters and search ranges\.

\(b\) Selected hyperparameters \(node classification\)\.

### G\.1Experiment on Additional Datasets

Penn94 is a social network graph of university users, characterized by profile attributes and class labels indicating graduation year or affiliation\. Genius is a content/co\-occurrence graph that features textual and metadata attributes, along with categorical labels\. Ogbnarxiv is a citation network of computer science papers that includes paper content embeddings and subject\-area labels\. For Penn94 and Genius, we employ fully supervised random class\-wise splits derived from previous heterophily evaluations:60,20,2060,20,20\. For OGBN\-ArXiv, we use its conventional temporal partitioning: training nodes consist of papers published through 2017, validation nodes cover 2018, and test nodes include 2019 and subsequent publications\. The result is reported in Table[8](https://arxiv.org/html/2605.10975#A7.T8)\.

Table 8:Node classification accuracy \(%\) on Penn94, Genius, and OGBN\-ArXiv\.

## Appendix HExperiment Settings for Graph Classification

The batch size used for the Graph classification datasets with the epoch number needed before stopping is reported in Table[9](https://arxiv.org/html/2605.10975#A8.T9)\.

Table 9:Training hyperparameters, reduction ratio, and loss weights per dataset\.
## Appendix IScalability

HMH scales linearly with graph size\. Each forward or backward pass takes𝒪​\(m​d\+n​d\)\\mathcal\{O\}\(md\+nd\)time covering sparse encoding, coarsening, Haar basis construction, spectral filtering, and unpooling\. Memory is𝒪​\(n\+m\)\\mathcal\{O\}\(n\+m\), storing only sparse adjacencies, assignment matrices, and wavelets\. Table[10](https://arxiv.org/html/2605.10975#A9.T10)reports the per\-epoch wall\-clock time and peak memory usage on a small graph \(SBM\-1k;n=103n=10^\{3\},m=5×103m=5\\times 10^\{3\}\) and a large graph \(REDDIT\-12K;n≈2\.4×106n\\approx 2\.4\\times 10^\{6\},m≈1\.2×107m\\approx 1\.2\\times 10^\{7\}\), wherennis the number of nodes andmmis the number of edges\. To compare across different sizes of graphs, we normalize training time by the number of edges usingms/Medge​\(milliseconds per million edges\)=1000​Tepoch/\(m/106\)\\text\{ms/Medge\}\(\\text\{milliseconds per million edges\}\)=1000\\,T\_\{\\mathrm\{epoch\}\}/\(m/10^\{6\}\)\. On SBM\-1k, HMH takes0\.040\.04s per epoch \(7,0007\{,\}000ms/Medge\) compared to0\.200\.20s \(40,00040\{,\}000ms/Medge\) of eigendecomposition methods, giving roughly a5×5\\timesspeedup and3\.3×3\.3\\timeslower peak memory \(0\.120\.12GB vs\.0\.400\.40GB\)\. On REDDIT\-12K, HMH achieves6464s per epoch \(5,3335\{,\}333ms/Medge\) versus520520s \(43,33343\{,\}333ms/Medge\) for the baseline, an8\.1×8\.1\\timesspeedup with3\.9×3\.9\\timesless memory \(9\.89\.8GB vs\.3838GB\)\. We also include the comparison of mid\-sized synthetic heterophilous graphs named Synthetic\-1M \(n=104n=10^\{4\},m=106m=10^\{6\}\) and Synthetic\-3M \(n=104n=10^\{4\},m=3×106m=3\\times 10^\{6\}\) in Table[10](https://arxiv.org/html/2605.10975#A9.T10)to illustrate the time\-complexity trend at intermediate scales\. The nearly constant ms/Medge across graph sizes shows that HMH scales linearly with the number of edges per epoch\.

Table 10:Per\-epoch efficiency \(mean, indicative\)\.ms/Medge=1000​Tepoch/\(m/106\)\\mathrm\{ms/Medge\}=1000\\,T\_\{\\text\{epoch\}\}/\(m/10^\{6\}\)\. Lower is better\.![Refer to caption](https://arxiv.org/html/2605.10975v1/Haar_vs_eigen_heatmaps.png)Figure 5:\(a\)Signed Haar basis: The basis is computed for a graph with 28 nodes, where each column represents a sparse, highly localized wavelet, with nonzero coefficients concentrated inside a limited cluster of nodes\. Red entries indicate negative weights, blue entries signify positive weights, and saturation represents magnitude\. \(b\)Eigen Vector Basis: This is a sparse and global eigenbasis for the same Graph\. \(c\)Haar locality \(hop\-energy\):For each Haar basis vectorhkh\_\{k\}, we compute its normalized per node energyei=hk​\(i\)2∑jhk​\(j\)2e\_\{i\}\\;=\\;\\frac\{h\_\{k\}\(i\)^\{2\}\}\{\\sum\_\{j\}h\_\{k\}\(j\)^\{2\}\}and then aggregate these energy contributions by graph\-distance \(number of hops\) from the vector’s largest\-magnitude entry\. The heatmap plots, for hop shells0,1,2,…,40,1,2,\\dots,4, the fraction of each vector’s total energy within that shell\. Over85%85\\%of energy falls within two hops, demonstrating tight spatial confinement\. \(c\) Haar locality \(hop\-energy\): for each Haar basis vector, we plot the fraction of its total energy within successive hop distances from its strongest node\. Over80%80\\%of energy lies within its hops, confirming tight spatial confinement\. \(d\)Eigenvector Basis:Distribute their energy almost uniformly across the first four hops, indicating poor localization and explaining their tendency to mix distant cluster signals \(hub\-aliasing\)\. More comparisons with different polynomials are presented in Appendix F\.1\.
## Appendix JOversmoothing Analysis

In Figure[4](https://arxiv.org/html/2605.10975#S6.F4),d we established that HMH demonstrates greater resistance to oversmoothing compared to standard baselines\. This section presents a rigorous quantification of this effect using Dirichlet Energy across four diverse benchmarks: Tolokers, Roman\-empire, Ogbn\-arxiv, and Amazon\-Ratings\.

Metric Definition\. The Dirichlet energyE​\(𝐇\(ℓ\)\)E\(\\mathbf\{H\}^\{\(\\ell\)\}\)of node embeddings at layerℓ\\ellmeasures the average distance between connected nodes in the feature space:

E​\(𝐇\(ℓ\)\)=1N​trace​\(\(𝐇\(ℓ\)\)⊤​ℒ​𝐇\(ℓ\)\),E\(\\mathbf\{H\}^\{\(\\ell\)\}\)=\\frac\{1\}\{N\}\\text\{trace\}\\left\(\(\\mathbf\{H\}^\{\(\\ell\)\}\)^\{\\top\}\\mathcal\{L\}\\mathbf\{H\}^\{\(\\ell\)\}\\right\),\(99\)whereℒ\\mathcal\{L\}denotes the normalized Laplacian\. An energy valueE≈0E\\approx 0indicates oversmoothing, in which node features converge to a stationary distribution and become indistinguishable\.

Results\.Figure[6](https://arxiv.org/html/2605.10975#A10.F6)presents the energy decay as model depth increases from 0 to 32 layers\.

- •GCN \(Red\): Experiences catastrophic collapse, with energy decreasing by several orders of magnitude \(for example,1\.0→0\.00051\.0\\to 0\.0005on Tolokers\) within only 4 layers\. This result demonstrates its inability to capture long\-range dependencies while preserving local information\.
- •ChebNet \(Orange\): Reduces energy decay to a limited extent through polynomial filters but ultimately exhibits oversmoothing at depths greater than 8\.
- •HMH \(Green\): Consistently maintains a robust energy floor \(E\>0\.4E\>0\.4\) across all datasets\. These results indicate that the multi\-scale Haar basis effectively separates high\-frequency details from low\-frequency trends, thereby preserving structural diversity even in deep architectures\.

sszs

![Refer to caption](https://arxiv.org/html/2605.10975v1/dricehelt.png)Figure 6:Dirichlet Energy Decay Analysis\.We measure the mean Dirichlet energy of node features at varying depths \(Log Scale\)\. While standard GCNs \(red\) and ChebNets \(orange\) suffer from exponential energy decay—indicating feature collapse—HMH \(green\) preserves significant structural energy at deep layers, validating its resistance to oversmoothing\.
## Appendix KAdditional Abalation Study

We use the following ablation of our model:

– Fixed Encoder\.It ensures the heterophily\-aware encoder remains stationary, allowing only the downstream parts to be trained\.

– No Hier\.It turns off hierarchical coarsening, thereby simplifying the model by converting it to a single\-scale version\.

– No Unpool\.It removes the level\-1 \(initial\) lift and uses level\-wise outputs to perform classification without propagating features back to their original resolution\.

– Feat\-only\.It gets rid of the structure\-similarity channel and only uses feature\-based attention\.

– Struct\-only\.It gets rid of feature attention and only keeps the similarity scores that come from structure\. In this case,λdiv=0∗\\lambda\_\{\\text\{div\}\}\{=\}0^\{\\ast\}means that the diversity loss is not included in the goal\. Table[5](https://arxiv.org/html/2605.10975#A7.T5)shows the result of the ablation method\.

The entire HMH consistently performs better than its ablations across datasets, with the biggest reductions being from “Struct\-only/Feat\-only” \(removing one channel damages complementary cues\) and “No Hier” \(losing multiscale separation\)\. Lifting multi\-level information back to level\-0 is crucial for final discrimination\. “No Unpool” also reduces accuracy\. The advantage of layer\-wise adaptive adjacency is demonstrated by the “Fixed Enc” results, which perform worse than the entire model\.

Setting𝝀div=𝟎∗\\boldsymbol\{\\lambda\_\{\\text\{div\}\}\{=\}0\}\\\!^\{\\ast\}caused clustering to become unstable\. The entropy regularizer prevents mode collapse in soft assignments\. Without it, assignment rows focus on one centroid, and several centroids move toward the same area\. This makes the number of clusters less effective \(typically one\)\. As a result, coarsening failed in a few runs\. There weren’t enough unique clusters to make the Haar basis at that level, which caused the spectral block to fail \(basis creation needs at least two nontrivial clusters\)\. In short, the loss of diversity is necessary to maintain a spread of assignments, enable meaningful coarsening, and provide a valid Haar basis\. The ablation study result is reported on[5](https://arxiv.org/html/2605.10975#A7.T5)\(main paper\)

## F\. Basis Approximations with polynomials

In this experiment, we estimated the graph’s basis, which has 30 nodes\. We used Chebyshev polynomials of the fourth order to approximate the basis\. The support of these basis vectors is orthonormalized\. The majority of entries in the Chebyshev\-derived basis are non\-negligible even at moderate thresholds, demonstrating the high density in the node domain and the global distribution of information by localized polynomials\. The dense approximated basis is illustrated in Figure[7](https://arxiv.org/html/2605.10975#Ax1.F7)\.

![Refer to caption](https://arxiv.org/html/2605.10975v1/chebyshev_basis_heatmap_times_roman_with_nodes.png)Figure 7:The heatmap shows the exact values of the first 10 order\-4 Chebyshev\-derived basis vectors at one anchor node\. The fact that there are 95%\\%nonzero entries means that the Chebyshev basis is dense in the spatial domain\. This is because localized spectral basis functions spread their effect across most nodes while capturing approximations to the main spectral components\.