Exploring Oversmoothing with Householder Matrices

# Exploring Oversmoothing with Householder Matrices
Source: [https://arxiv.org/html/2608.12514](https://arxiv.org/html/2608.12514)
###### Abstract

Deep graph neural networks \(GNNs\) suffer from oversmoothing—a progressive collapse of node representations toward a low\-information subspace as network depth increases—because the normalized graph propagation operator is repeatedly applied directly to the hidden representations\. In this work we studyHouseholder Graph Neural Network \(HouseGNN\)\. Rather than updating the hidden state like standard GCN, HouseGNN uses the aggregated neighbourhood message solely to estimate a reflection direction; the node embedding is then updated by a Householder reflector followed by GroupSort, yielding a*piecewise orthogonal*layer that preserves Euclidean norm at every node and at every depth\. We prove three core properties: \(i\) every internal layer preserves the node\-wise Euclidean norm; \(ii\) the Householder reflector is scale and sign\-invariant in the message; and \(iii\) pairwise distances between nodes can change through mismatch between node\-wise orthogonal operators\.

###### Index Terms:

Graph Neural Networks, Oversmoothing, Householder Reflection, Orthogonal Networks, GroupSort\.

## IIntroduction

Graph neural networks \(GNNs\)\[[1](https://arxiv.org/html/2608.12514#bib.bib1),[2](https://arxiv.org/html/2608.12514#bib.bib2),[3](https://arxiv.org/html/2608.12514#bib.bib3)\]have become the dominant area for learning on graph\-structured data, achieving strong empirical performance in node classification\[[5](https://arxiv.org/html/2608.12514#bib.bib5)\], link prediction, and molecular property prediction\[[7](https://arxiv.org/html/2608.12514#bib.bib7)\]\. The majority of effective architectures follow the*message\-passing*framework\[[6](https://arxiv.org/html/2608.12514#bib.bib6)\]: at each layer, every node aggregates features from its neighbours and updates its representation via a learnable transformation\.

Despite strong shallow performance, deep GNNs are well\-known to suffer from*oversmoothing*\[[8](https://arxiv.org/html/2608.12514#bib.bib8),[9](https://arxiv.org/html/2608.12514#bib.bib9)\]\. As depth grows, repeated application of the graph propagation operator suppresses high\-frequency spectral components, progressively reducing discriminative variation across nodes and driving the representation toward a low\-dimensional subspace determined by the leading eigenspace of the propagation operator\[[9](https://arxiv.org/html/2608.12514#bib.bib9)\]\. In node classification, this loss of variation can make node representations increasingly difficult to separate\.

A variety of strategies have been proposed to combat oversmoothing, including PairNorm\[[12](https://arxiv.org/html/2608.12514#bib.bib12)\], GCNII\[[13](https://arxiv.org/html/2608.12514#bib.bib13)\], DropEdge\[[14](https://arxiv.org/html/2608.12514#bib.bib14)\], residual connections\[[25](https://arxiv.org/html/2608.12514#bib.bib25)\], and batch normalisation\[[26](https://arxiv.org/html/2608.12514#bib.bib26)\]\.

In this work, we study oversmoothing using Householder matrices\. Instead of directly updating the hidden states, we change*how the hidden state is updated*\. The key idea is to use the neighbourhood message only to define a*reflection direction*, then update the node state by a Householder reflection\[[23](https://arxiv.org/html/2608.12514#bib.bib23)\]across the hyperplane normal to that direction, followed by GroupSort\[[22](https://arxiv.org/html/2608.12514#bib.bib22)\], a norm\-preserving nonlinearity\.

## IIRelated Work

### II\-AOversmoothing in GNNs

The oversmoothing phenomenon was first identified by Li et al\.\[[8](https://arxiv.org/html/2608.12514#bib.bib8)\], who observed empirically that GCN performance degrades with depth\. Oono and Suzuki\[[9](https://arxiv.org/html/2608.12514#bib.bib9)\]later proved that GCN representations converge to a subspace at an exponential rate\. Wu et al\.\[[10](https://arxiv.org/html/2608.12514#bib.bib10)\]provided a non\-asymptotic analysis showing that oversmoothing can appear even in shallow models under specific random graph conditions\. Oversmoothing in attention\-based GNNs was studied by Wu et al\.\[[11](https://arxiv.org/html/2608.12514#bib.bib11)\]\.

### II\-BMitigation Strategies

A number of architectural modifications reduce oversmoothing\. Zhao and Akoglu\[[12](https://arxiv.org/html/2608.12514#bib.bib12)\]propose PairNorm, which rescales representations to maintain a fixed total pairwise distance\. Chen et al\.\[[13](https://arxiv.org/html/2608.12514#bib.bib13)\]introduce GCNII, which combines initial residual connections with identity mappings at each layer\. Rong et al\.\[[14](https://arxiv.org/html/2608.12514#bib.bib14)\]randomly drop edges during training to limit graph smoothing\. Residual GCN\[[25](https://arxiv.org/html/2608.12514#bib.bib25)\]and APPNP\[[15](https://arxiv.org/html/2608.12514#bib.bib15)\]retain initial\-feature information through skip connections\. Jumping Knowledge Networks\[[4](https://arxiv.org/html/2608.12514#bib.bib4)\]aggregate representations from all intermediate layers\. Scholkemper et al\.\[[17](https://arxiv.org/html/2608.12514#bib.bib17)\]prove that residual connections and normalisation can provably prevent oversmoothing under certain conditions\.

### II\-COrthogonal Parameterisations in GNNs

Several recent works use orthogonality constraints in GNNs\. Guo et al\.\[[19](https://arxiv.org/html/2608.12514#bib.bib19)\]propose OOGNN with orthogonal weight matrices to prevent oversmoothing\. Kiani et al\.\[[20](https://arxiv.org/html/2608.12514#bib.bib20)\]study unitary convolutions by modifying the Adjacency matrix\.

### II\-DHouseholder Transformations

Householder reflectors\[[23](https://arxiv.org/html/2608.12514#bib.bib23)\]are used for orthogonal matrix factorisation \(QR decomposition\) and eigenvalue computation\. Their use as learnable parameterisations in neural networks was explored by Mhammedi et al\.\[[24](https://arxiv.org/html/2608.12514#bib.bib24)\]in the context of recurrent networks requiring fast orthogonal transformations\. In this work, Householder reflectors serve a different purpose: rather than parameterising a global weight matrix, each reflector is*conditioned dynamically*on the node’s neighbourhood, making it a local, graph\-dependent, per\-node transformation\.

## IIIBackground

TABLE I:Notation used in the work\.### III\-AGraph Neural Networks and Notation

Let𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)be an undirected graph withn=\|𝒱\|n=\|\\mathcal\{V\}\|nodes\. Each nodei∈𝒱i\\in\\mathcal\{V\}carries an input feature vector𝐱i∈ℝdin\\mathbf\{x\}\_\{i\}\\in\\mathbb\{R\}^\{d\_\{\\mathrm\{in\}\}\}\.

We use column\-vector notation for per\-node states throughout the work\. Thus,𝐡i\(ℓ\)∈ℝd\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\\in\\mathbb\{R\}^\{d\}and𝐦i\(ℓ\)∈ℝd\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\}\\in\\mathbb\{R\}^\{d\}are column vectors\. When the stacked matrixH\(ℓ\)∈ℝn×dH^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{n\\times d\}is used, itsii\-th row is\(𝐡i\(ℓ\)\)⊤\(\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\)^\{\\top\}\.

LetA∈ℝn×nA\\in\\mathbb\{R\}^\{n\\times n\}denote the adjacency matrix of the graph, and let

A~=A\+In\\widetilde\{A\}=A\+I\_\{n\}denote the adjacency matrix with self\-loops\. Its degree matrix is

D~i​i=∑j=1nA~i​j\.\\widetilde\{D\}\_\{ii\}=\\sum\_\{j=1\}^\{n\}\\widetilde\{A\}\_\{ij\}\.
Two normalized graph operators are used in this work\. The first is the row\-normalized adjacency

P=D~−1​A~,P=\\widetilde\{D\}^\{\-1\}\\widetilde\{A\},\(1\)which is the random\-walk or mean\-aggregation operator\. Itsii\-th row sums to one, so it explicitly averages over the neighbourhood including the node itself\.

The second is the symmetric normalized adjacency

S=D~−1/2A~D~−1/2,S=\\widetilde\{D\}^\{\-1/2\}\\widetilde\{A\}\\widetilde\{D\}^\{\-1/2\},\(2\)which is the propagation matrix used in the standard GCN layer\. For undirected graphs,SSis symmetric, whereasPPis generally not symmetric unless the graph is regular\.

These two are closely related\. SinceD~\\widetilde\{D\}is a positive diagonal matrix after adding self\-loops,

S=D~1/2PD~−1/2\.S=\\widetilde\{D\}^\{1/2\}P\\widetilde\{D\}^\{\-1/2\}\.\(3\)ThusPPandSSare similar matrices and therefore have the same eigenvalues\. They are not the same operator on node features, but they have the same spectral convergence factors\. This distinction is important for oversmoothing: both operators have the same asymptotic smoothing rate on an undirected graph, while their limiting representations differ by degree\-dependent scaling\.

### III\-BStandard Graph Convolutional Network

The GCN update\[[1](https://arxiv.org/html/2608.12514#bib.bib1)\]at layerℓ\\ellis

H\(ℓ\+1\)=σ⁡\(S​H\(ℓ\)​W\(ℓ\)\),H^\{\(\\ell\+1\)\}=\\sigma\\\!\\left\(S\\,H^\{\(\\ell\)\}\\,W^\{\(\\ell\)\}\\right\),\(4\)whereW\(ℓ\)∈ℝdℓ×dℓ\+1W^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{d\_\{\\ell\}\\times d\_\{\\ell\+1\}\}is a learnable weight matrix andσ\\sigmais a nonlinearity\.

### III\-CSpectral View of Oversmoothing

Oversmoothing refers to the loss of node\-wise discriminative variation caused by repeatedly applying a graph propagation operator\. In the linearized setting, where nonlinearities and weight matrices are ignored, a GCN layer has this form

H\(ℓ\+1\)≈M​H\(ℓ\),H\(L\)≈ML​H\(0\),H^\{\(\\ell\+1\)\}\\approx MH^\{\(\\ell\)\},\\qquad H^\{\(L\)\}\\approx M^\{L\}H^\{\(0\)\},\(5\)for a propagation operatorMM\. Oversmoothing occurs when the powersMLM^\{L\}suppress all spectral components except those associated with the dominant eigenspace\. For the row\-normalized operatorP=D~−1​A~P=\\widetilde\{D\}^\{\-1\}\\widetilde\{A\}, each row sums to one, hence

P​𝟏=𝟏\.P\\mathbf\{1\}=\\mathbf\{1\}\.\(6\)Thus11is an eigenvalue ofPP\. If the graph is undirected and connected, and self\-loops are included throughA~=A\+In\\widetilde\{A\}=A\+I\_\{n\}, thenPPis an irreducible and aperiodic stochastic matrix\. By the Perron–Frobenius theorem, one of the eigenvalue ofPPis11and every other eigenvalue satisfies

\|λk​\(P\)\|<1,k≥2\.\|\\lambda\_\{k\}\(P\)\|<1,\\qquad k\\geq 2\.\(7\)Consequently,

PL⟶𝟏​π⊤,πi=D~i​i∑j=1nD~j​j,P^\{L\}\\longrightarrow\\mathbf\{1\}\\pi^\{\\top\},\\qquad\\pi\_\{i\}=\\frac\{\\widetilde\{D\}\_\{ii\}\}\{\\sum\_\{j=1\}^\{n\}\\widetilde\{D\}\_\{jj\}\},\(8\)and therefore

PL​H\(0\)⟶𝟏​π⊤​H\(0\)\.P^\{L\}H^\{\(0\)\}\\longrightarrow\\mathbf\{1\}\\pi^\{\\top\}H^\{\(0\)\}\.\(9\)In this row\-normalized case, all node representations converge to the same vector\.

For the symmetric GCN operator

S=D~−1/2A~D~−1/2,S=\\widetilde\{D\}^\{\-1/2\}\\widetilde\{A\}\\widetilde\{D\}^\{\-1/2\},\(10\)the same eigenvalue conclusion holds becauseSSis similar toPP:

S=D~1/2PD~−1/2\.S=\\widetilde\{D\}^\{1/2\}P\\widetilde\{D\}^\{\-1/2\}\.\(11\)Similar matrices have the same eigenvalues, soSSalso has only one eigenvalue equals to11and all other eigenvalues have modulus strictly less than11under the same connected, self\-looped, undirected\-graph assumption\. SinceSSis symmetric, it admits an orthogonal eigendecomposition

S=Q​Λ​Q⊤,S=Q\\Lambda Q^\{\\top\},\(12\)and the linearized GCN propagation satisfies

H\(L\)≈SL​H\(0\)=Q​ΛL​Q⊤​H\(0\)\.H^\{\(L\)\}\\approx S^\{L\}H^\{\(0\)\}=Q\\Lambda^\{L\}Q^\{\\top\}H^\{\(0\)\}\.\(13\)Every component with\|λk\|<1\|\\lambda\_\{k\}\|<1is multiplied byλkL\\lambda\_\{k\}^\{L\}and decays\. The surviving eigenvector is proportional toD~1/2​𝟏\\widetilde\{D\}^\{1/2\}\\mathbf\{1\}, so

SL⟶u1​u1⊤,u1=D~1/2​𝟏𝟏⊤​D~​𝟏\.S^\{L\}\\longrightarrow u\_\{1\}u\_\{1\}^\{\\top\},\\qquad u\_\{1\}=\\frac\{\\widetilde\{D\}^\{1/2\}\\mathbf\{1\}\}\{\\sqrt\{\\mathbf\{1\}^\{\\top\}\\widetilde\{D\}\\mathbf\{1\}\}\}\.\(14\)ThusSL​H\(0\)S^\{L\}H^\{\(0\)\}converges to degree\-scaled copies of a common feature vector: node embeddings become parallel, although not necessarily identical\.

HencePPandSSdescribe the same spectral oversmoothing mechanism: they have the same eigenvalues and therefore the same asymptotic spectral convergence\. The difference is in the limiting form\. The row\-normalized operatorPPmakes the node embeddings identical, while the symmetric operatorSSmakes them align in the same direction with degree\-dependent magnitudes\. In both cases, repeated direct application of the graph operator to the hidden state causes oversmoothing\[[9](https://arxiv.org/html/2608.12514#bib.bib9)\]\.

### III\-DDirichlet Energy

For a hidden\-state matrixH∈ℝn×dH\\in\\mathbb\{R\}^\{n\\times d\}with rowiiequal to\(𝐡i\)⊤\(\\mathbf\{h\}\_\{i\}\)^\{\\top\}, define

ℰDir​\(H\)=∑\(i,j\)∈ℰu‖𝐡i−𝐡j‖22,\\mathcal\{E\}\_\{\\mathrm\{Dir\}\}\(H\)=\\sum\_\{\(i,j\)\\in\\mathcal\{E\}\_\{u\}\}\\left\\\|\\mathbf\{h\}\_\{i\}\-\\mathbf\{h\}\_\{j\}\\right\\\|\_\{2\}^\{2\},\(15\)whereℰu\\mathcal\{E\}\_\{u\}denotes the set of unique undirected edges\. Dirichlet energy measures how much neighboring node representations vary across the graph\. Smaller values correspond to smoother representations over edges, meaning that adjacent node representations tend to be more similar, whereas larger values indicate greater variation between adjacent nodes\. In particular, on a connected graph,ℰDir​\(H\)=0\\mathcal\{E\}\_\{\\mathrm\{Dir\}\}\(H\)=0if and only if all node representations are identical\.

## IVHouseholder Graph Neural Network

### IV\-ADesign Principle

The central design decision is todecouple neighbourhood aggregation from state update\. The neighbourhood message is used only to define a*reflection direction*; the current node state is then reflected across the hyperplane normal to that direction\. Formally, for nodeiiat layerℓ\\ell, the update is defined as follows\.

Step 1 — Aggregate\.Compute the mean neighbourhood message:

𝐦i\(ℓ\)=∑j=1nPi​j​𝐡j\(ℓ\),\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\}=\\sum\_\{j=1\}^\{n\}P\_\{ij\}\\,\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\},\(16\)whereP∈ℝn×nP\\in\\mathbb\{R\}^\{n\\times n\}is the row\-normalized mean\-aggregation operator induced by the graph\.

P=D~−1​A~P=\\widetilde\{D\}^\{\-1\}\\widetilde\{A\}\(17\)Thus, \([16](https://arxiv.org/html/2608.12514#S4.E16)\) can equivalently be written as

𝐦i\(ℓ\)=1\|𝒩~​\(i\)\|​∑j∈𝒩~​\(i\)𝐡j\(ℓ\),\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\}=\\frac\{1\}\{\|\\widetilde\{\\mathcal\{N\}\}\(i\)\|\}\\sum\_\{j\\in\\widetilde\{\\mathcal\{N\}\}\(i\)\}\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\},\(18\)where𝒩~​\(i\)=𝒩​\(i\)∪\{i\}\\widetilde\{\\mathcal\{N\}\}\(i\)=\\mathcal\{N\}\(i\)\\cup\\\{i\\\}denotes the neighbourhood of nodeiiincluding itself\.

Step 2 — Project direction\.Transform the message by an orthogonal weight matrix and normalize:

𝐯i\(ℓ\)=W\(ℓ\)​𝐦i\(ℓ\),\(W\(ℓ\)\)⊤​W\(ℓ\)=Id\.\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}=W^\{\(\\ell\)\}\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\},\\qquad\(W^\{\(\\ell\)\}\)^\{\\top\}W^\{\(\\ell\)\}=I\_\{d\}\.\(19\)For𝐯i\(ℓ\)≠𝟎\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\\neq\\mathbf\{0\}, define the unit reflection direction as

𝐮i\(ℓ\)=𝐯i\(ℓ\)‖𝐯i\(ℓ\)‖2\.\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}=\\frac\{\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\}\{\\\|\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\\\|\_\{2\}\}\.\(20\)
Step 3 — Reflect\.Form the Householder reflector and apply it to the current state:

Ri\(ℓ\)=Id−2​𝐮i\(ℓ\)​\(𝐮i\(ℓ\)\)⊤,R^\{\(\\ell\)\}\_\{i\}=I\_\{d\}\-2\\,\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}\(\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}\)^\{\\top\},\(21\)𝐳i\(ℓ\)=Ri\(ℓ\)​𝐡i\(ℓ\)\.\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}=R^\{\(\\ell\)\}\_\{i\}\\,\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\.\(22\)
Step 4 — Nonlinearity\.Apply GroupSort:

𝐡i\(ℓ\+1\)=GroupSort⁡\(𝐳i\(ℓ\)\)\.\\mathbf\{h\}^\{\(\\ell\+1\)\}\_\{i\}=\\mathrm\{GroupSort\}\\\!\\left\(\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\\right\)\.\(23\)
GroupSort\[[22](https://arxiv.org/html/2608.12514#bib.bib22)\]is a norm\-preserving nonlinearity\. Let the group size begg, and assume thatddis divisible bygg\. For a vector𝐳∈ℝd\\mathbf\{z\}\\in\\mathbb\{R\}^\{d\}, write

𝐳=\[𝐳\(1\);𝐳\(2\);…;𝐳\(d/g\)\],\\mathbf\{z\}=\\big\[\\mathbf\{z\}^\{\(1\)\};\\mathbf\{z\}^\{\(2\)\};\\ldots;\\mathbf\{z\}^\{\(d/g\)\}\\big\],where each block𝐳\(k\)∈ℝg\\mathbf\{z\}^\{\(k\)\}\\in\\mathbb\{R\}^\{g\}containsggconsecutive coordinates\. GroupSort sorts the entries inside each block in ascending order and then concatenates the sorted blocks\.

In our experiments, we used group sizeg=2g=2\. For example, if

𝐳=\[3−12544\],\\mathbf\{z\}=\\begin\{bmatrix\}3\\\\ \-1\\\\ 2\\\\ 5\\\\ 4\\\\ 4\\end\{bmatrix\},then

GroupSort⁡\(𝐳\)=\[−132544\]\.\\mathrm\{GroupSort\}\(\\mathbf\{z\}\)=\\begin\{bmatrix\}\-1\\\\ 3\\\\ 2\\\\ 5\\\\ 4\\\\ 4\\end\{bmatrix\}\.

### IV\-BContrast with Standard GCN

TABLE II:Structural comparison between GCN and HouseGNN\.The structural difference is that in GCN the graph operator acts*directly*on the hidden state, whereas in HouseGNN it uses a direction vector\{𝐮i\(ℓ\)\}\\\{\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}\\\}that governs local reflections\. Since message magnitude is discarded in \([20](https://arxiv.org/html/2608.12514#S4.E20)\), adjacency eigenvalues can no longer appear as repeated multiplicative shrinkage of the state\.

### IV\-CGeometric Interpretation

For any unit vector𝐮∈ℝd\\mathbf\{u\}\\in\\mathbb\{R\}^\{d\}, decompose a state𝐡∈ℝd\\mathbf\{h\}\\in\\mathbb\{R\}^\{d\}as

𝐡=⟨𝐮,𝐡⟩​𝐮⏟along​𝐮\+\(𝐡−⟨𝐮,𝐡⟩​𝐮\)⏟⟂𝐮\.\\mathbf\{h\}=\\underbrace\{\\langle\\mathbf\{u\},\\,\\mathbf\{h\}\\rangle\\,\\mathbf\{u\}\}\_\{\\text\{along \}\\mathbf\{u\}\}\+\\underbrace\{\(\\mathbf\{h\}\-\\langle\\mathbf\{u\},\\,\\mathbf\{h\}\\rangle\\,\\mathbf\{u\}\)\}\_\{\\perp\\,\\mathbf\{u\}\}\.ThenR⁡\(𝐮\)​𝐡=−⟨𝐮,𝐡⟩​𝐮\+\(𝐡−⟨𝐮,𝐡⟩​𝐮\)R\(\\mathbf\{u\}\)\\mathbf\{h\}=\-\\langle\\mathbf\{u\},\\,\\mathbf\{h\}\\rangle\\,\\mathbf\{u\}\+\(\\mathbf\{h\}\-\\langle\\mathbf\{u\},\\,\\mathbf\{h\}\\rangle\\,\\mathbf\{u\}\), i\.e\. the reflector flips exactly the component along𝐮\\mathbf\{u\}and leaves the orthogonal complement unchanged\. In HouseGNN,𝐮\\mathbf\{u\}is not fixed; it is estimated from the node’s neighbourhood\. The method therefore says*“reflect your current state across the hyperplane whose normal is estimated from your neighbourhood”*, not*“become the neighbourhood average”*\.

## VTheoretical Analysis

All proofs are fully detailed in Section[VI](https://arxiv.org/html/2608.12514#S6)\.

### V\-AOrthogonality and Spectral Structure

###### Proposition 1\(Orthogonality and eigenvalues\)\.

For any unit vector𝐮∈ℝd\\mathbf\{u\}\\in\\mathbb\{R\}^\{d\}, the Householder matrixR⁡\(𝐮\)=𝐈d−2​𝐮𝐮⊤R\(\\mathbf\{u\}\)=\\mathbf\{I\}\_\{d\}\-2\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}satisfies

R​\(𝐮\)⊤​R​\(𝐮\)=𝐈d,R​\(𝐮\)⊤=R⁡\(𝐮\)\.R\(\\mathbf\{u\}\)^\{\\top\}R\(\\mathbf\{u\}\)=\\mathbf\{I\}\_\{d\},\\qquad R\(\\mathbf\{u\}\)^\{\\top\}=R\(\\mathbf\{u\}\)\.Its spectrum is\{−1\}\\\{\-1\\\}\(multiplicity 1, eigenvector𝐮\\mathbf\{u\}\) and\{\+1\}\\\{\+1\\\}\(multiplicityd−1d\-1, eigenspace𝐮⟂\\mathbf\{u\}^\{\\perp\}\)\.

Proposition[1](https://arxiv.org/html/2608.12514#Thmproposition1)establishes that the reflector is both orthogonal and an involution \(R2=𝐈R^\{2\}=\\mathbf\{I\}\): it flips precisely one learned direction and preserves all orthogonal directions\.

### V\-BLayerwise Norm Preservation

###### Proposition 2\(Norm preservation\)\.

Let𝐡i\(ℓ\+1\)=GroupSort⁡\(Ri\(ℓ\)​𝐡i\(ℓ\)\)\\mathbf\{h\}^\{\(\\ell\+1\)\}\_\{i\}=\\mathrm\{GroupSort\}\(R^\{\(\\ell\)\}\_\{i\}\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\)\. Then‖𝐡i\(ℓ\+1\)‖=‖𝐡i\(ℓ\)‖\\left\\\|\\mathbf\{h\}^\{\(\\ell\+1\)\}\_\{i\}\\right\\\|=\\left\\\|\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\\right\\\|for every nodeiiand every layerℓ\\ell\. Consequently,‖𝐡i\(ℓ\)‖=‖𝐡i\(0\)‖\\left\\\|\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\\right\\\|=\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{i\}\\right\\\|for allℓ≥0\\ell\\geq 0\.

### V\-CDirection\-Only Dependence

###### Proposition 3\(Scale and sign invariance\)\.

DefineR⁡\(𝐯\)=𝐈d−2​𝐯‖𝐯‖​𝐯⊤‖𝐯‖R\(\\mathbf\{v\}\)=\\mathbf\{I\}\_\{d\}\-2\\frac\{\\mathbf\{v\}\}\{\\left\\\|\\mathbf\{v\}\\right\\\|\}\\frac\{\\mathbf\{v\}^\{\\top\}\}\{\\left\\\|\\mathbf\{v\}\\right\\\|\}for𝐯≠𝟎\\mathbf\{v\}\\neq\\mathbf\{0\}\. Then for every nonzero scalarcc,

R⁡\(c​𝐯\)=R⁡\(𝐯\)\.R\(c\\mathbf\{v\}\)=R\(\\mathbf\{v\}\)\.

The reflector depends only onspan⁡\(𝐯\)\\mathrm\{span\}\(\\mathbf\{v\}\)\. In vanilla GCN, adjacency eigenvalues directly multiply the state repeatedly\. In HouseGNN, the same propagation operator shapes the message𝐦i\(ℓ\)\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\}, but message magnitude is discarded in \([20](https://arxiv.org/html/2608.12514#S4.E20)\) before any state update occurs\.

###### Definition 1\(Pairwise collapse\)\.

Two nodesiiandjjare said to collapse at depthLLif

𝐡i\(L\)=𝐡j\(L\)\.\\mathbf\{h\}\_\{i\}^\{\(L\)\}=\\mathbf\{h\}\_\{j\}^\{\(L\)\}\.More generally, a deep graph model is said to exhibit oversmoothing if, as depth increases, hidden representations lose discriminative variation across many nodes and become increasingly difficult to separate for node classification\.

### V\-DObstruction to Pairwise Collapse

###### Proposition 4\(Equal\-radius requirement for collapse\)\.

Suppose there exists a layerLLsuch that𝐡i\(L\)=𝐡j\(L\)\\mathbf\{h\}^\{\(L\)\}\_\{i\}=\\mathbf\{h\}^\{\(L\)\}\_\{j\}\. Then necessarily‖𝐡i\(0\)‖=‖𝐡j\(0\)‖\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{i\}\\right\\\|=\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{j\}\\right\\\|\.

### V\-EPairwise Distance Evolution

For each nodeiiand layerℓ\\ell, define the combined layer operator

Oi\(ℓ\):=Πi\(ℓ\)​Ri\(ℓ\),O^\{\(\\ell\)\}\_\{i\}:=\\Pi^\{\(\\ell\)\}\_\{i\}R^\{\(\\ell\)\}\_\{i\},whereΠi\(ℓ\)\\Pi^\{\(\\ell\)\}\_\{i\}is the local GroupSort permutation at nodeii\. Then𝐡i\(ℓ\+1\)=Oi\(ℓ\)​𝐡i\(ℓ\)\\mathbf\{h\}^\{\(\\ell\+1\)\}\_\{i\}=O^\{\(\\ell\)\}\_\{i\}\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}and\(Oi\(ℓ\)\)⊤​Oi\(ℓ\)=𝐈d\(O^\{\(\\ell\)\}\_\{i\}\)^\{\\top\}O^\{\(\\ell\)\}\_\{i\}=\\mathbf\{I\}\_\{d\}\. Define

Δi​j\(ℓ\):=𝐡i\(ℓ\)−𝐡j\(ℓ\),di​j\(ℓ\):=‖Δi​j\(ℓ\)‖,ρ:=maxk⁡‖𝐡k\(0\)‖\.\\Delta^\{\(\\ell\)\}\_\{ij\}:=\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\-\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\},\\quad d^\{\(\\ell\)\}\_\{ij\}:=\\left\\\|\\Delta^\{\(\\ell\)\}\_\{ij\}\\right\\\|,\\quad\\rho:=\\max\_\{k\}\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{k\}\\right\\\|\.
###### Theorem 1\(One\-step pairwise distance bound\)\.

For any nodesi,ji,jand any layerℓ\\ell,

\|di​j\(ℓ\+1\)−di​j\(ℓ\)\|≤ρ​‖Oi\(ℓ\)−Oj\(ℓ\)‖2\.\\left\|d^\{\(\\ell\+1\)\}\_\{ij\}\-d^\{\(\\ell\)\}\_\{ij\}\\right\|\\;\\leq\\;\\rho\\,\\left\\\|O^\{\(\\ell\)\}\_\{i\}\-O^\{\(\\ell\)\}\_\{j\}\\right\\\|\_\{2\}\.

Theorem[1](https://arxiv.org/html/2608.12514#Thmtheorem1)identifies node\-wise*operator mismatch*as the*sole*mechanism by which pairwise distances can change\. The hidden state is not averaged into a neighbourhood mean; if all nodes experience the same orthogonal operator at layerℓ\\ell, then all pairwise distances are preserved exactly at that layer\.

### V\-FThe Same\-GroupSort Special Case

Define the absolute cosine similarity between message directions:

γi​j\(ℓ\):=\|⟨𝐦i\(ℓ\),𝐦j\(ℓ\)⟩\|‖𝐦i\(ℓ\)‖​‖𝐦j\(ℓ\)‖∈\[0,1\]\.\\gamma^\{\(\\ell\)\}\_\{ij\}:=\\frac\{\|\\langle\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\},\\,\\mathbf\{m\}^\{\(\\ell\)\}\_\{j\}\\rangle\|\}\{\\left\\\|\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\}\\right\\\|\\,\\left\\\|\\mathbf\{m\}^\{\(\\ell\)\}\_\{j\}\\right\\\|\}\\in\[0,1\]\.\(24\)BecauseW\(ℓ\)W^\{\(\\ell\)\}is orthogonal,γi​j\(ℓ\)\\gamma^\{\(\\ell\)\}\_\{ij\}equals the absolute cosine similarity between the learned directions𝐮i\(ℓ\)\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}and𝐮j\(ℓ\)\\mathbf\{u\}^\{\(\\ell\)\}\_\{j\}\.

###### Proposition 5\(Exact reflector mismatch\)\.

For any nodesi,ji,jand any layerℓ\\ell,

‖Ri\(ℓ\)−Rj\(ℓ\)‖2=2​1−\(γi​j\(ℓ\)\)2\.\\left\\\|R^\{\(\\ell\)\}\_\{i\}\-R^\{\(\\ell\)\}\_\{j\}\\right\\\|\_\{2\}=2\\sqrt\{1\-\(\\gamma^\{\(\\ell\)\}\_\{ij\}\)^\{2\}\}\.

###### Corollary 1\(Same\-GroupSort pairwise bound\)\.

IfΠi\(ℓ\)=Πj\(ℓ\)\\Pi^\{\(\\ell\)\}\_\{i\}=\\Pi^\{\(\\ell\)\}\_\{j\}, then

\|di​j\(ℓ\+1\)−di​j\(ℓ\)\|≤2​ρ​1−\(γi​j\(ℓ\)\)2\.\\left\|d^\{\(\\ell\+1\)\}\_\{ij\}\-d^\{\(\\ell\)\}\_\{ij\}\\right\|\\;\\leq\\;2\\rho\\sqrt\{1\-\(\\gamma^\{\(\\ell\)\}\_\{ij\}\)^\{2\}\}\.Summing over layers:

di​j\(L\)≥di​j\(0\)−2​ρ​∑ℓ=0L−11−\(γi​j\(ℓ\)\)2\.d^\{\(L\)\}\_\{ij\}\\;\\geq\\;d^\{\(0\)\}\_\{ij\}\-2\\rho\\sum\_\{\\ell=0\}^\{L\-1\}\\sqrt\{1\-\(\\gamma^\{\(\\ell\)\}\_\{ij\}\)^\{2\}\}\.

### V\-GRole of the Adjacency Spectrum

The adjacency operatorPPstill shapes the messages𝐦i\(ℓ\)\\mathbf\{m\}^\{\(\\ell\)\}\_\{i\}in \([16](https://arxiv.org/html/2608.12514#S4.E16)\)—its eigenvalues influence the direction field\{𝐮i\(ℓ\)\}\\\{\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}\\\}\. What Proposition[3](https://arxiv.org/html/2608.12514#Thmproposition3)proves is that*message magnitude*is discarded before the state update\. The standard oversmoothing mechanism—in which eigenvalues ofSSappear as repeated multiplicative factors on the hidden state—is absent\. Oversmoothing in HouseGNN, if it occurs, must occur through accumulated node\-wise operator mismatches that gradually rotate or reflect representations toward one another\. If all nodes experience the same local orthogonal operator, pairwise distances are preserved rather than smoothed\.

## VIProofs

### VI\-AProof of Proposition[1](https://arxiv.org/html/2608.12514#Thmproposition1)

Let𝐮∈ℝd\\mathbf\{u\}\\in\\mathbb\{R\}^\{d\}satisfy‖𝐮‖2=1\\left\\\|\\mathbf\{u\}\\right\\\|\_\{2\}=1, and define

R=𝐈−2​𝐮𝐮⊤\.R=\\mathbf\{I\}\-2\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}\.\(25\)
Symmetry\.Taking the transpose gives

R⊤=\(𝐈−2​𝐮𝐮⊤\)⊤=𝐈−2​𝐮𝐮⊤=R\.R^\{\\top\}=\\left\(\\mathbf\{I\}\-2\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}\\right\)^\{\\top\}=\\mathbf\{I\}\-2\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}=R\.\(26\)Hence,RRis symmetric\.

Orthogonality\.We compute

R2\\displaystyle R^\{2\}=\(𝐈−2​𝐮𝐮⊤\)2\\displaystyle=\\left\(\\mathbf\{I\}\-2\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}\\right\)^\{2\}=𝐈−4​𝐮𝐮⊤\+4​𝐮​\(𝐮⊤​𝐮\)​𝐮⊤\.\\displaystyle=\\mathbf\{I\}\-4\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}\+4\\mathbf\{u\}\\left\(\\mathbf\{u\}^\{\\top\}\\mathbf\{u\}\\right\)\\mathbf\{u\}^\{\\top\}\.\(27\)Since𝐮⊤​𝐮=1\\mathbf\{u\}^\{\\top\}\\mathbf\{u\}=1, this reduces to

R2=𝐈\.R^\{2\}=\\mathbf\{I\}\.\(28\)BecauseRRis symmetric, we have

R⊤​R=R2=𝐈\.R^\{\\top\}R=R^\{2\}=\\mathbf\{I\}\.\(29\)Therefore,RRis orthogonal\.

Eigenvalues\.First,

R​𝐮=𝐮−2​𝐮​\(𝐮⊤​𝐮\)=−𝐮\.R\\mathbf\{u\}=\\mathbf\{u\}\-2\\mathbf\{u\}\\left\(\\mathbf\{u\}^\{\\top\}\\mathbf\{u\}\\right\)=\-\\mathbf\{u\}\.\(30\)Thus,𝐮\\mathbf\{u\}is an eigenvector with eigenvalue−1\-1\.

Now let𝐰⟂𝐮\\mathbf\{w\}\\perp\\mathbf\{u\}\. Then𝐮⊤​𝐰=0\\mathbf\{u\}^\{\\top\}\\mathbf\{w\}=0, and hence

R​𝐰=𝐰−2​𝐮​\(𝐮⊤​𝐰\)=𝐰\.R\\mathbf\{w\}=\\mathbf\{w\}\-2\\mathbf\{u\}\\left\(\\mathbf\{u\}^\{\\top\}\\mathbf\{w\}\\right\)=\\mathbf\{w\}\.\(31\)Therefore, every vector that satisfies𝐮⊤​𝐰=0\\mathbf\{u\}^\{\\top\}\\mathbf\{w\}=0is an eigenvector with eigenvalue\+1\+1\. This proves the proposition\.□\\square

### VI\-BProof of Proposition[2](https://arxiv.org/html/2608.12514#Thmproposition2)

Let

𝐳i\(ℓ\)=Ri\(ℓ\)​𝐡i\(ℓ\)\.\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}=R\_\{i\}^\{\(\\ell\)\}\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\.\(32\)By Proposition[1](https://arxiv.org/html/2608.12514#Thmproposition1),Ri\(ℓ\)R\_\{i\}^\{\(\\ell\)\}is orthogonal\. Therefore,

‖𝐳i\(ℓ\)‖2=‖𝐡i\(ℓ\)‖2\.\\left\\\|\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\\right\\\|\_\{2\}\.\(33\)
GroupSort only permutes coordinates within each group\. Since coordinate permutations preserve the Euclidean norm,

‖GroupSort⁡\(𝐳i\(ℓ\)\)‖2=‖𝐳i\(ℓ\)‖2\.\\left\\\|\\mathrm\{GroupSort\}\\left\(\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\\right\)\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\\right\\\|\_\{2\}\.\(34\)Using the update rule

𝐡i\(ℓ\+1\)=GroupSort⁡\(𝐳i\(ℓ\)\),\\mathbf\{h\}^\{\(\\ell\+1\)\}\_\{i\}=\\mathrm\{GroupSort\}\\left\(\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\\right\),we obtain

‖𝐡i\(ℓ\+1\)‖2=‖𝐡i\(ℓ\)‖2\.\\left\\\|\\mathbf\{h\}^\{\(\\ell\+1\)\}\_\{i\}\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\\right\\\|\_\{2\}\.\(35\)Applying this equality recursively gives

‖𝐡i\(ℓ\)‖2=‖𝐡i\(0\)‖2,ℓ≥0\.\\left\\\|\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{i\}\\right\\\|\_\{2\},\\qquad\\ell\\geq 0\.\(36\)This proves the proposition\.□\\square

### VI\-CProof of Proposition[3](https://arxiv.org/html/2608.12514#Thmproposition3)

Let𝐯≠𝟎\\mathbf\{v\}\\neq\\mathbf\{0\}and letc≠0c\\neq 0\. Then

c​𝐯‖c​𝐯‖2=c\|c\|​𝐯‖𝐯‖2=sgn⁡\(c\)​𝐯‖𝐯‖2\.\\frac\{c\\mathbf\{v\}\}\{\\left\\\|c\\mathbf\{v\}\\right\\\|\_\{2\}\}=\\frac\{c\}\{\|c\|\}\\frac\{\\mathbf\{v\}\}\{\\left\\\|\\mathbf\{v\}\\right\\\|\_\{2\}\}=\\mathrm\{sgn\}\(c\)\\frac\{\\mathbf\{v\}\}\{\\left\\\|\\mathbf\{v\}\\right\\\|\_\{2\}\}\.\(37\)The scalar factor disappears in the outer product, sincesgn​\(c\)2=1\\mathrm\{sgn\}\(c\)^\{2\}=1\. Hence,

R⁡\(c​𝐯\)\\displaystyle R\(c\\mathbf\{v\}\)=𝐈−2​\(c​𝐯‖c​𝐯‖2\)​\(c​𝐯‖c​𝐯‖2\)⊤\\displaystyle=\\mathbf\{I\}\-2\\left\(\\frac\{c\\mathbf\{v\}\}\{\\left\\\|c\\mathbf\{v\}\\right\\\|\_\{2\}\}\\right\)\\left\(\\frac\{c\\mathbf\{v\}\}\{\\left\\\|c\\mathbf\{v\}\\right\\\|\_\{2\}\}\\right\)^\{\\top\}=𝐈−2​𝐯‖𝐯‖2​𝐯⊤‖𝐯‖2=R⁡\(𝐯\)\.\\displaystyle=\\mathbf\{I\}\-2\\frac\{\\mathbf\{v\}\}\{\\left\\\|\\mathbf\{v\}\\right\\\|\_\{2\}\}\\frac\{\\mathbf\{v\}^\{\\top\}\}\{\\left\\\|\\mathbf\{v\}\\right\\\|\_\{2\}\}=R\(\\mathbf\{v\}\)\.\(38\)This proves scale and sign invariance\.□\\square

### VI\-DProof of Proposition[4](https://arxiv.org/html/2608.12514#Thmproposition4)

Suppose

𝐡i\(L\)=𝐡j\(L\)\.\\mathbf\{h\}^\{\(L\)\}\_\{i\}=\\mathbf\{h\}^\{\(L\)\}\_\{j\}\.\(39\)Then their Euclidean norms are equal:

‖𝐡i\(L\)‖2=‖𝐡j\(L\)‖2\.\\left\\\|\\mathbf\{h\}^\{\(L\)\}\_\{i\}\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{h\}^\{\(L\)\}\_\{j\}\\right\\\|\_\{2\}\.\(40\)By Proposition[2](https://arxiv.org/html/2608.12514#Thmproposition2),

‖𝐡k\(L\)‖2=‖𝐡k\(0\)‖2,k∈\{i,j\}\.\\left\\\|\\mathbf\{h\}^\{\(L\)\}\_\{k\}\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{k\}\\right\\\|\_\{2\},\\qquad k\\in\\\{i,j\\\}\.\(41\)Therefore,

‖𝐡i\(0\)‖2=‖𝐡j\(0\)‖2\.\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{i\}\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{j\}\\right\\\|\_\{2\}\.\(42\)This proves the proposition\.□\\square

### VI\-EProof of Theorem[1](https://arxiv.org/html/2608.12514#Thmtheorem1)

SinceOi\(ℓ\)O\_\{i\}^\{\(\\ell\)\}andOj\(ℓ\)O\_\{j\}^\{\(\\ell\)\}are orthogonal, we have

Δi​j\(ℓ\+1\)\\displaystyle\\Delta\_\{ij\}^\{\(\\ell\+1\)\}=Oi\(ℓ\)​𝐡i\(ℓ\)−Oj\(ℓ\)​𝐡j\(ℓ\)\\displaystyle=O\_\{i\}^\{\(\\ell\)\}\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\-O\_\{j\}^\{\(\\ell\)\}\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\}=Oi\(ℓ\)​\(𝐡i\(ℓ\)−𝐡j\(ℓ\)\)\+\(Oi\(ℓ\)−Oj\(ℓ\)\)​𝐡j\(ℓ\)\.\\displaystyle=O\_\{i\}^\{\(\\ell\)\}\\left\(\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\-\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\}\\right\)\+\\left\(O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\)\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\}\.\(43\)Taking norms and applying the triangle inequality gives

di​j\(ℓ\+1\)\\displaystyle d\_\{ij\}^\{\(\\ell\+1\)\}≤‖Oi\(ℓ\)​Δi​j\(ℓ\)‖2\+‖\(Oi\(ℓ\)−Oj\(ℓ\)\)​𝐡j\(ℓ\)‖2\\displaystyle\\leq\\left\\\|O\_\{i\}^\{\(\\ell\)\}\\Delta\_\{ij\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\+\\left\\\|\\left\(O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\)\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\}\\right\\\|\_\{2\}≤‖Δi​j\(ℓ\)‖2\+‖Oi\(ℓ\)−Oj\(ℓ\)‖2​‖𝐡j\(ℓ\)‖2\.\\displaystyle\\leq\\left\\\|\\Delta\_\{ij\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\+\\left\\\|O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\\left\\\|\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\}\\right\\\|\_\{2\}\.\(44\)BecauseOi\(ℓ\)O\_\{i\}^\{\(\\ell\)\}is orthogonal,

‖Oi\(ℓ\)​Δi​j\(ℓ\)‖2=‖Δi​j\(ℓ\)‖2=di​j\(ℓ\)\.\\left\\\|O\_\{i\}^\{\(\\ell\)\}\\Delta\_\{ij\}^\{\(\\ell\)\}\\right\\\|\_\{2\}=\\left\\\|\\Delta\_\{ij\}^\{\(\\ell\)\}\\right\\\|\_\{2\}=d\_\{ij\}^\{\(\\ell\)\}\.Moreover, by Proposition[2](https://arxiv.org/html/2608.12514#Thmproposition2),

‖𝐡j\(ℓ\)‖2=‖𝐡j\(0\)‖2≤ρ\.\\left\\\|\\mathbf\{h\}^\{\(\\ell\)\}\_\{j\}\\right\\\|\_\{2\}=\\left\\\|\\mathbf\{h\}^\{\(0\)\}\_\{j\}\\right\\\|\_\{2\}\\leq\\rho\.\(45\)Therefore,

di​j\(ℓ\+1\)≤di​j\(ℓ\)\+ρ​‖Oi\(ℓ\)−Oj\(ℓ\)‖2\.d\_\{ij\}^\{\(\\ell\+1\)\}\\leq d\_\{ij\}^\{\(\\ell\)\}\+\\rho\\left\\\|O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\.\(46\)Equivalently,

di​j\(ℓ\+1\)−di​j\(ℓ\)≤ρ​‖Oi\(ℓ\)−Oj\(ℓ\)‖2\.d\_\{ij\}^\{\(\\ell\+1\)\}\-d\_\{ij\}^\{\(\\ell\)\}\\leq\\rho\\left\\\|O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\.\(47\)
For the lower bound, apply the reverse triangle inequality to the same decomposition:

‖Δi​j\(ℓ\+1\)‖2\\displaystyle\\left\\\|\\Delta\_\{ij\}^\{\(\\ell\+1\)\}\\right\\\|\_\{2\}≥‖Oi\(ℓ\)​Δi​j\(ℓ\)‖2−‖\(Oi\(ℓ\)−Oj\(ℓ\)\)​𝐡j\(ℓ\)‖2\.\\displaystyle\\geq\\left\\\|O\_\{i\}^\{\(\\ell\)\}\\Delta\_\{ij\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\-\\left\\\|\\left\(O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\)\\mathbf\{h\}\_\{j\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\.\(48\)Using the same estimates,

di​j\(ℓ\+1\)≥di​j\(ℓ\)−ρ​‖Oi\(ℓ\)−Oj\(ℓ\)‖2\.d\_\{ij\}^\{\(\\ell\+1\)\}\\geq d\_\{ij\}^\{\(\\ell\)\}\-\\rho\\left\\\|O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\.\(49\)Combining the upper and lower bounds yields

\|di​j\(ℓ\+1\)−di​j\(ℓ\)\|≤ρ​‖Oi\(ℓ\)−Oj\(ℓ\)‖2\.\\left\|d\_\{ij\}^\{\(\\ell\+1\)\}\-d\_\{ij\}^\{\(\\ell\)\}\\right\|\\leq\\rho\\left\\\|O\_\{i\}^\{\(\\ell\)\}\-O\_\{j\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\.\(50\)This proves the theorem\.□\\square

### VI\-FProof of Proposition[5](https://arxiv.org/html/2608.12514#Thmproposition5)

Let𝐮,𝐰∈ℝd\\mathbf\{u\},\\mathbf\{w\}\\in\\mathbb\{R\}^\{d\}be unit vectors and define

c=𝐮⊤​𝐰\.c=\\mathbf\{u\}^\{\\top\}\\mathbf\{w\}\.\(51\)Ifc=1c=1, then𝐮=𝐰\\mathbf\{u\}=\\mathbf\{w\}\. Ifc=−1c=\-1, then𝐰=−𝐮\\mathbf\{w\}=\-\\mathbf\{u\}\. In both cases,

𝐰𝐰⊤=𝐮𝐮⊤,\\mathbf\{w\}\\mathbf\{w\}^\{\\top\}=\\mathbf\{u\}\\mathbf\{u\}^\{\\top\},soR⁡\(𝐮\)=R⁡\(𝐰\)R\(\\mathbf\{u\}\)=R\(\\mathbf\{w\}\)and the result is immediate\.

Now assume\|c\|<1\|c\|<1\. We have

R⁡\(𝐮\)−R⁡\(𝐰\)=2​\(𝐰𝐰⊤−𝐮𝐮⊤\)\.R\(\\mathbf\{u\}\)\-R\(\\mathbf\{w\}\)=2\\left\(\\mathbf\{w\}\\mathbf\{w\}^\{\\top\}\-\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}\\right\)\.\(52\)Define

𝐬=𝐰−c​𝐮1−c2\.\\mathbf\{s\}=\\frac\{\\mathbf\{w\}\-c\\mathbf\{u\}\}\{\\sqrt\{1\-c^\{2\}\}\}\.\(53\)Then\{𝐮,𝐬\}\\\{\\mathbf\{u\},\\mathbf\{s\}\\\}is an orthonormal set, and

𝐰=c​𝐮\+1−c2​𝐬\.\\mathbf\{w\}=c\\mathbf\{u\}\+\\sqrt\{1\-c^\{2\}\}\\,\\mathbf\{s\}\.\(54\)In the basis\{𝐮,𝐬\}\\\{\\mathbf\{u\},\\mathbf\{s\}\\\}, the matrix𝐰𝐰⊤−𝐮𝐮⊤\\mathbf\{w\}\\mathbf\{w\}^\{\\top\}\-\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}has representation

\(−\(1−c2\)c​1−c2c​1−c21−c2\)\.\\begin\{pmatrix\}\-\(1\-c^\{2\}\)&c\\sqrt\{1\-c^\{2\}\}\\\\ c\\sqrt\{1\-c^\{2\}\}&1\-c^\{2\}\\end\{pmatrix\}\.\(55\)This symmetric matrix has trace zero and determinant−\(1−c2\)\-\(1\-c^\{2\}\)\. Hence, its eigenvalues are

±1−c2\.\\pm\\sqrt\{1\-c^\{2\}\}\.\(56\)Therefore,

‖𝐰𝐰⊤−𝐮𝐮⊤‖2=1−c2\.\\left\\\|\\mathbf\{w\}\\mathbf\{w\}^\{\\top\}\-\\mathbf\{u\}\\mathbf\{u\}^\{\\top\}\\right\\\|\_\{2\}=\\sqrt\{1\-c^\{2\}\}\.\(57\)It follows that

‖R⁡\(𝐮\)−R⁡\(𝐰\)‖2=2​1−c2\.\\left\\\|R\(\\mathbf\{u\}\)\-R\(\\mathbf\{w\}\)\\right\\\|\_\{2\}=2\\sqrt\{1\-c^\{2\}\}\.\(58\)Sinceγi​j\(ℓ\)=\|c\|\\gamma\_\{ij\}^\{\(\\ell\)\}=\|c\|, we havec2=\(γi​j\(ℓ\)\)2c^\{2\}=\(\\gamma\_\{ij\}^\{\(\\ell\)\}\)^\{2\}\. Thus,

‖Ri\(ℓ\)−Rj\(ℓ\)‖2=2​1−\(γi​j\(ℓ\)\)2\.\\left\\\|R\_\{i\}^\{\(\\ell\)\}\-R\_\{j\}^\{\(\\ell\)\}\\right\\\|\_\{2\}=2\\sqrt\{1\-\(\\gamma\_\{ij\}^\{\(\\ell\)\}\)^\{2\}\}\.\(59\)This proves the proposition\.□\\square

## VIIExperimental Evaluation

### VII\-AExperimental Protocol

Datasets\.We evaluate on six standard node\-classification benchmarks\. The citation graphs Cora\[[27](https://arxiv.org/html/2608.12514#bib.bib27)\], CiteSeer\[[28](https://arxiv.org/html/2608.12514#bib.bib28)\], and PubMed\[[29](https://arxiv.org/html/2608.12514#bib.bib29)\]are homophilic \(edge homophily≥0\.74\\geq 0\.74\)\. Texas, Wisconsin, and Cornell from the WebKB collection are heterophilic \(edge homophily≤0\.30\\leq 0\.30\)\. Dataset statistics are provided in Table[III](https://arxiv.org/html/2608.12514#S7.T3)\.

TABLE III:Dataset statistics\.H⁡\(𝒢\)H\(\\mathcal\{G\}\)denotes edge homophily\.Baselines\.We compare against \(i\) a standard GCN\[[1](https://arxiv.org/html/2608.12514#bib.bib1)\], \(ii\) GAT\[[2](https://arxiv.org/html/2608.12514#bib.bib2)\], \(iii\) BatchNorm\-GCN\[[26](https://arxiv.org/html/2608.12514#bib.bib26)\], \(iv\) PairNorm\-GCN\[[12](https://arxiv.org/html/2608.12514#bib.bib12)\], and \(v\) Residual\-GCN\. Baseline results for GCN, GAT, BatchNorm, PairNorm, and Residual on Cora, CiteSeer, and PubMed are taken from Wang et al\.\[[18](https://arxiv.org/html/2608.12514#bib.bib18)\]\.

HouseGNN setup\.Hidden dimension: 64; GroupSort group size: 2; aggregation: mean; optimiser: Adam with learning rate5×10−45\\times 10^\{\-4\}and weight decay10−310^\{\-3\}; training: up to 400 epochs with gradient clipping\. All HouseGNN results are reported as the mean and standard deviation over 5 random seeds\.

Depth sweep\.The main benchmark usesL∈\{2,8,16,32,64\}L\\in\\\{2,8,16,32,64\\\}layers\. In addition, we include a Cora\-only geometric diagnostic across the same depth range and an extreme\-depth study atL=128L=128comparing GroupSort and ReLU under the same orthogonal Householder backbone\.

### VII\-BCore Benchmark: Cora, CiteSeer, and Texas

Figure[1](https://arxiv.org/html/2608.12514#S7.F1)shows the test accuracy curves as the depth varies\. This shows: GCN collapses beyond two layers, while HouseGNN maintains stable accuracy across the full depth sweeps\.

![Refer to caption](https://arxiv.org/html/2608.12514v1/grid_test_accuracy_cora__1_.png)\(a\)Cora
![Refer to caption](https://arxiv.org/html/2608.12514v1/grid_test_accuracy_citeseer__1_.png)\(b\)CiteSeer
![Refer to caption](https://arxiv.org/html/2608.12514v1/grid_test_accuracy_texas__1_.png)\(c\)Texas

Fig\. 1:Test accuracy vs\. depth for GCN \(blue\) and HouseGNN \(orange\) on Cora, CiteSeer, and Texas\.Table[IV](https://arxiv.org/html/2608.12514#S7.T4)contains numerical results\.Cora: GCN accuracy drops from78\.5%78\.5\\%at 2 layers to around2121–30%30\\%at88–6464layers\. HouseGNN stays in the75\.575\.5–76\.8%76\.8\\%range throughout\.CiteSeer: GCN collapses from66\.2%66\.2\\%at 2 layers to below22%22\\%at88–6464layers; HouseGNN varies between55\.9%55\.9\\%to62\.7%62\.7\\%throughout\.Texas: Both models remain comparatively stable, consistent with the heterophilic structure of the dataset\.

TABLE IV:Core benchmark: Test accuracy vs layers on Cora, CiteSeer, and Texas\.
### VII\-CComparison with Multiple Baselines

Table[V](https://arxiv.org/html/2608.12514#S7.T5)provides a broad comparison on Cora, CiteSeer, and PubMed, including GCN, GAT, BatchNorm, PairNorm, and Residual\. Baseline results are taken from\[[18](https://arxiv.org/html/2608.12514#bib.bib18)\]\.

GAT\.On Cora, GAT accuracy falls from81\.5%81\.5\\%atL=2L=2to28\.4%28\.4\\%atL=64L=64\. On CiteSeer, GAT drops from69\.9%69\.9\\%to26\.0%26\.0\\%\.

Partial mitigation by BatchNorm and PairNorm\.These normalisations slow the collapse but do not eliminate it\. AtL=64L=64on Cora, BatchNorm achieves only35\.3%35\.3\\%and PairNorm44\.0%44\.0\\%\. On PubMed, both methods are more effective \(69\.3%69\.3\\%and71\.2%71\.2\\%atL=64L=64respectively\), but still degrade notably from their peak values\.

Residual connectionsprovide limited depth\-robustness: on Cora, accuracy drops from80\.7%80\.7\\%atL=2L=2to27\.9%27\.9\\%atL=64L=64; on CiteSeer it collapses from67\.5%67\.5\\%atL=2L=2to19\.7%19\.7\\%atL=64L=64\.

HouseGNNshows the most stable depth trend among the reported methods\. On Cora, it maintains75\.575\.5–76\.8%76\.8\\%across all tested depths\. On CiteSeer, it ranges between55\.9%55\.9\\%and62\.7%62\.7\\%\. On PubMed, performance reaches77\.0%77\.0\\%atL=64L=64\.

TABLE V:Test accuracy \(%\) vs depth on Cora, CiteSeer, and PubMed\. Baseline results \( GAT, BatchNorm, PairNorm, Residual\) are from Wang et al\.\[[18](https://arxiv.org/html/2608.12514#bib.bib18)\]\.
### VII\-DExtended Experiments: Wisconsin and Cornell

Table[VI](https://arxiv.org/html/2608.12514#S7.T6)reports HouseGNN on Wisconsin and Cornell\.

TABLE VI:Result on Wisconsin and Cornell Dataset for HouseGNN\.Wisconsin\.The model is stable across depth, attaining its best test accuracy at 16 and 32 layers \(62\.1%62\.1\\%\)\.Cornell\.Best performance appears at 8 and 32 layers \(55\.9%55\.9\\%\)\.

### VII\-ERemoving the Orthogonal Weights

To isolate the contribution of orthogonal weights, we evaluate HouseGNN on Cora at 64 and 80 layers where the matrixW\(ℓ\)W^\{\(\\ell\)\}in \([19](https://arxiv.org/html/2608.12514#S4.E19)\) is unconstrained \(not required to have orthogonal weights\)\. The Householder reflection and GroupSort remain intact\. Table[VII](https://arxiv.org/html/2608.12514#S7.T7)reports the results for this\.

TABLE VII:Result on Cora after removing the orthogonal weights constraint on HouseGNN\.These results suggest that the model does not collapse at large depth when the orthogonality constraint is removed, suggesting that the Householder plus GroupSort activation itself carries meaningful learning capacity\.

### VII\-FDirichlet Energy and effective rank on Cora

Figure[2](https://arxiv.org/html/2608.12514#S7.F2)shows that GCN rapidly loses Dirichlet energy as depth increases, and its effective rank also remains very low\. In contrast, HouseGNN maintains a much larger effective rank throughout the sweep and does not show the same collapse of Dirichlet energy\. Dirichlet energy is used as a metric for oversmoothing; therefore, for GCN, as the number of layers increases, both accuracy and Dirichlet energy decrease\.

![Refer to caption](https://arxiv.org/html/2608.12514v1/depth_sweep_effective_rank.png)
![Refer to caption](https://arxiv.org/html/2608.12514v1/depth_sweep_dirichlet_energy.png)

Fig\. 2:Effective rank and Dirichlet energy vs \. depth on Cora
### VII\-GResult at 128\-Layers

Table[VIII](https://arxiv.org/html/2608.12514#S7.T8)reports the Cora results on 128 layers with two activation functions\.

TABLE VIII:Result on Cora at 128\-layers on HouseGNN\.As suggested by the results in Table[VIII](https://arxiv.org/html/2608.12514#S7.T8)the contrast is important\. At 128 layers, HouseGNN with GroupSort activation falls to very low test accuracy, but its effective rank remains high and its Dirichlet energy also remains large \(ReLU:658\.764±43\.253658\.764\\pm 43\.253; GroupSort:3506\.059±152\.9053506\.059\\pm 152\.905\)\. This indicates that the 128\-layer failure is not well described as classical GCN\-style oversmoothing, where one would expect representational collapse and a large decrease in Dirichlet energy\. One possible interpretation is that the orthogonal Householder\+GroupSort dynamics can enter a non\-collapsed but poorly class\-discriminative regime at extreme depth\.

Another possible explanation is that, at 128 layers, repeated reflections combined with GroupSort may make the representations overly dispersed or poorly aligned for classification\. Since GroupSort permutes the elements of each vector while preserving its norm, the representations may remain non\-collapsed but become poorly organized in direction\. This interpretation is supported by the high effective rank, which suggests that the representations occupy many directions in the feature space\.

This is also consistent with the large Dirichlet energy, which suggests that node representations do not collapse but instead remain highly separated in the representation space\. In this regime, more different activation may help organize the representations into a more class\-discriminative structure\. The 128\-layers result of the ReLU variant supports this interpretation, although it should be viewed as suggestive rather than conclusive\.

### VII\-HSummary of Empirical Findings

Conclusions from the experiments:

1. 1\.Depth stability\.HouseGNN maintains relatively stable accuracy as depth increases, whereas GCN shows a substantial drop at larger depths\.
2. 2\.Behaviour across datasets\.The results on PubMed, Wisconsin, and Cornell suggest that the proposed update remains stable across both homophilic and heterophilic graphs\.
3. 3\.Effect of the orthogonality constraint\.The Cora ablation shows that removing the orthogonal constraint does not lead to collapse, suggesting that the reflection\-based update itself plays an important role in depth stability\.

## VIIIConclusion and Future Work

This work studied Householder Graph Neural Network \(HouseGNN\) as a possible way to mitigate oversmoothing in deep GNNs\. The main idea is to use graph aggregation to estimate a direction, rather than directly using the aggregated message as the new hidden state\. The node state is updated by a Householder reflection followed by GroupSort, so each internal layer is piecewise orthogonal and preserves the Euclidean norm\. The theoretical analysis shows HouseGNN layer preserves node\-wise norms at every depth and pairwise distances can change only through mismatch between local orthogonal operators\. These results do not prove that all forms of oversmoothing are impossible, but they show that the standard diffusion\-based mechanism of GCN oversmoothing is removed\.

The experiments support the theory\. HouseGNN remains stable across many layers on Cora and CiteSeer, while GCN collapses after only a few layers\. On Texas, Wisconsin, and Cornell, HouseGNN shows mixed behaviour, which suggests that heterophilic graphs need additional modelling choices\. On PubMed, the model shows promising behaviour at larger depth\. The additional diagnostics on Cora further indicate that HouseGNN does not follow the usual low\-rank, low\-energy oversmoothing pattern of GCN across the depth sweep\.

At the same time, the 128\-layer result shows the model can fail but failure can be migigated by changing the activation function\. The GroupSort version can become non\-discriminative without showing collapse in effective rank and dirichlet energy, whereas the ReLU version remains stable\.

Future work should investigate whether the proposed method can be extended beyond 128 layers\. During our experiments, we tested a 150\-layer model with ReLU activations and observed accuracy comparable to that of the 128\-layer ReLU model, suggesting that deeper architectures may be feasible\. Another promising direction is to study the method in combination with residual connections\. Since HouseGNN does not rely on additional stabilization combining it with hyperparameters and residual connections may further improve stability and could potentially lead to significantly higher accuracy\.

## Appendix AAlgorithm Summary

Algorithm[1](https://arxiv.org/html/2608.12514#alg1)summarizes the HouseGNN forward pass\.

Algorithm 1HouseGNN Forward Pass0:Graph

𝒢\\mathcal\{G\}with edge set

ℰ\\mathcal\{E\}, features

X∈ℝn×dinX\\in\\mathbb\{R\}^\{n\\times d\_\{\\mathrm\{in\}\}\}, parameters

\{W\(ℓ\)\}ℓ=0L−1\\\{W^\{\(\\ell\)\}\\\}\_\{\\ell=0\}^\{L\-1\},

WencW\_\{\\mathrm\{enc\}\},

WclsW\_\{\\mathrm\{cls\}\}
0:Class logits

\{ℓi\}i=1n\\\{\\ell\_\{i\}\\\}\_\{i=1\}^\{n\}
1:

H\(0\)←X​Wenc⊤\+𝟏​𝐛enc⊤H^\{\(0\)\}\\leftarrow XW\_\{\\mathrm\{enc\}\}^\{\\top\}\+\\mathbf\{1\}\\mathbf\{b\}\_\{\\mathrm\{enc\}\}^\{\\top\}\{Encoder\}

2:for

ℓ=0\\ell=0to

L−1L\-1do

3:

M\(ℓ\)←MeanAggr​\(H\(ℓ\),ℰ\)M^\{\(\\ell\)\}\\leftarrow\\text\{MeanAggr\}\(H^\{\(\\ell\)\},\\mathcal\{E\}\)\{\([16](https://arxiv.org/html/2608.12514#S4.E16)\)\}

4:

V\(ℓ\)←M\(ℓ\)​\(W\(ℓ\)\)⊤V^\{\(\\ell\)\}\\leftarrow M^\{\(\\ell\)\}\(W^\{\(\\ell\)\}\)^\{\\top\}
5:foreach node

iido

6:if

‖𝐯i\(ℓ\)‖2=0\\\|\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\\\|\_\{2\}=0then

7:

𝐳i\(ℓ\)←𝐡i\(ℓ\)\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\\leftarrow\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}
8:else

9:

𝐮i\(ℓ\)←𝐯i\(ℓ\)/‖𝐯i\(ℓ\)‖2\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}\\leftarrow\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}/\\\|\\mathbf\{v\}^\{\(\\ell\)\}\_\{i\}\\\|\_\{2\}\{Node\-wise normalisation; \([20](https://arxiv.org/html/2608.12514#S4.E20)\)\}

10:

𝐳i\(ℓ\)←𝐡i\(ℓ\)−2​𝐮i\(ℓ\)​\(𝐮i\(ℓ\)⊤​𝐡i\(ℓ\)\)\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\\leftarrow\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\-2\\,\\mathbf\{u\}^\{\(\\ell\)\}\_\{i\}\(\\mathbf\{u\}^\{\(\\ell\)\\top\}\_\{i\}\\mathbf\{h\}^\{\(\\ell\)\}\_\{i\}\)\{Householder reflection; \([22](https://arxiv.org/html/2608.12514#S4.E22)\)\}

11:endif

12:

𝐡i\(ℓ\+1\)←GroupSort​\(𝐳i\(ℓ\)\)\\mathbf\{h\}^\{\(\\ell\+1\)\}\_\{i\}\\leftarrow\\text\{GroupSort\}\(\\mathbf\{z\}^\{\(\\ell\)\}\_\{i\}\)\{\([23](https://arxiv.org/html/2608.12514#S4.E23)\)\}

13:endfor

14:endfor

15:foreach node

iido

16:

ℓi←𝐡i\(L\)​Wcls⊤\+𝐛cls\\ell\_\{i\}\\leftarrow\\mathbf\{h\}^\{\(L\)\}\_\{i\}W\_\{\\mathrm\{cls\}\}^\{\\top\}\+\\mathbf\{b\}\_\{\\mathrm\{cls\}\}\{Classifier\}

17:endfor

18:return

\{ℓi\}i=1n\\\{\\ell\_\{i\}\\\}\_\{i=1\}^\{n\}

## References

- \[1\]T\. N\. Kipf and M\. Welling, “Semi\-supervised classification with graph convolutional networks,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2017\.
- \[2\]P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. Bengio, “Graph attention networks,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2018\.
- \[3\]K\. Xu, W\. Hu, J\. Leskovec, and S\. Jegelka, “How powerful are graph neural networks?” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2019\.
- \[4\]K\. Xu, C\. Li, Y\. Tian, T\. Sonobe, K\. Kawarabayashi, and S\. Jegelka, “Representation learning on graphs with jumping knowledge networks,” inProc\. Int\. Conf\. Machine Learning \(ICML\), 2018\.
- \[5\]F\. Wu, A\. Souza, T\. Zhang, C\. Fifty, T\. Yu, and K\. Weinberger, “Simplifying graph convolutional networks,” inProc\. Int\. Conf\. Machine Learning \(ICML\), 2019\.
- \[6\]J\. Gilmer, S\. S\. Schoenholz, P\. F\. Riley, O\. Vinyals, and G\. E\. Dahl, “Neural message passing for quantum chemistry,” in Proc\. Int\. Conf\. Machine Learning \(ICML\), 2017\.
- \[7\]D\. K\. Duvenaudet al\., “Convolutional networks on graphs for learning molecular fingerprints,” inProc\. Neural Inf\. Process\. Syst\. \(NeurIPS\), 2015\.
- \[8\]Q\. Li, Z\. Han, and X\.\-M\. Wu, “Deeper insights into graph convolutional networks for semi\-supervised learning,” inProc\. AAAI Conf\. Artif\. Intell\., 2018\.
- \[9\]K\. Oono and T\. Suzuki, “Graph neural networks exponentially lose expressive power for node classification,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2020\.
- \[10\]X\. Wu, Z\. Chen, W\. Wang, and A\. Jadbabaie, “A non\-asymptotic analysis of oversmoothing in graph neural networks,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2023\.
- \[11\]X\. Wu, A\. Ajorlou, Z\. Wu, and A\. Jadbabaie, “Demystifying oversmoothing in attention\-based graph neural networks,” inProc\. Neural Inf\. Process\. Syst\. \(NeurIPS\), 2023\.
- \[12\]L\. Zhao and L\. Akoglu, “PairNorm: Tackling oversmoothing in GNNs,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2020\.
- \[13\]M\. Chen, Z\. Wei, Z\. Huang, B\. Ding, and Y\. Li, “Simple and deep graph convolutional networks,” inProc\. Int\. Conf\. Machine Learning \(ICML\), 2020\.
- \[14\]Y\. Rong, W\. Huang, T\. Xu, and J\. Huang, “Dropedge: Towards deep graph convolutional networks on node classification,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2020\.
- \[15\]J\. Gasteiger, A\. Bojchevski, and S\. Günnemann, “Predict then propagate: Graph neural networks meet personalized PageRank,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2019\.
- \[16\]M\. Liu, H\. Gao, and S\. Ji, “Towards deeper graph neural networks,” inProc\. ACM SIGKDD Int\. Conf\. Knowledge Discovery and Data Mining, 2020\.
- \[17\]M\. Scholkemper, X\. Wu, A\. Jadbabaie, and M\. T\. Schaub, “Residual connections and normalization can provably prevent oversmoothing in GNNs,” inProc\. Int\. Conf\. Learning Representations \(ICLR\), 2025\.
- \[18\]J\. Wang, X\. Wu, J\. Cheng, and Y\. Wang, “A signed graph approach to understanding and mitigating oversmoothing in GNNs,”arXiv:2502\.11394, 2025\.
- \[19\]K\. Guo, K\. Zhou, X\. Hu, Y\. Li, Y\. Chang, and X\. Wang, “Orthogonal graph neural networks,”arXiv:2109\.11338, 2021\.
- \[20\]\[20\] B\. T\. Kiani, L\. Fesser, and M\. Weber, “Unitary convolutions for learning on graphs and groups,” arXiv:2410\.05499, 2024\.
- \[21\]H\. Qiu, Y\. Bian, and Q\. Yao, “Graph unitary message passing,”arXiv:2403\.11199, 2024\.
- \[22\]C\. Anil, J\. Lucas, and R\. Grosse, “Sorting out Lipschitz function approximation,” inProc\. Int\. Conf\. Machine Learning \(ICML\), 2019\.
- \[23\]A\. S\. Householder, “Unitary triangularization of a nonsymmetric matrix,”J\. ACM, vol\. 5, no\. 4, pp\. 339–342, 1958\.
- \[24\]Z\. Mhammedi, A\. Hellicar, A\. Rahman, and J\. Bailey, “Efficient orthogonal parametrisation of recurrent neural networks using Householder reflections,” inProc\. Int\. Conf\. Machine Learning \(ICML\), 2017\.
- \[25\]K\. He, X\. Zhang, S\. Ren, and J\. Sun, “Deep residual learning for image recognition,” inProc\. IEEE Conf\. Comput\. Vis\. Pattern Recognit\. \(CVPR\), 2016\.
- \[26\]S\. Ioffe and C\. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” inProc\. Int\. Conf\. Machine Learning \(ICML\), 2015\.
- \[27\]A\. K\. McCallum, K\. Nigam, J\. Rennie, and K\. Seymore, “Automating the construction of internet portals with machine learning,”Inf\. Retrieval, vol\. 3, no\. 2, pp\. 127–163, 2000\.
- \[28\]C\. L\. Giles, K\. D\. Bollacker, and S\. Lawrence, “CiteSeer: An automatic citation indexing system,” inProc\. 3rd ACM Conf\. Digital Libraries, 1998\.
- \[29\]G\. Namata, B\. London, L\. Getoor, and B\. Huang, “Query\-driven active surveying for collective classification,” inWorkshop Mining and Learning with Graphs \(MLG\), 2012\.
- \[30\]M\. Eliasof, E\. Haber, and E\. Treister, “PDE\-GCN: Novel architectures for graph neural networks motivated by partial differential equations,” inProc\. Neural Inf\. Process\. Syst\. \(NeurIPS\), 2021\.
- \[31\]T\. K\. Rusch, M\. M\. Bronstein, and S\. Mishra, “A survey on oversmoothing in graph neural networks,”arXiv:2303\.10993, 2023\.
- \[32\]G\. Shi, C\. Altafini, and J\. S\. Baras, “Dynamics over signed networks,”SIAM Review, vol\. 61, no\. 2, pp\. 229–257, 2019\.
- \[33\]O\. Platonov, D\. Kuznedelev, M\. Diskin, A\. Babenko, and L\. Prokhorenkova, “A critical look at the evaluation of GNNs under heterophily: Are we really making progress?”arXiv:2302\.11640, 2023\.