Exploring Oversmoothing with Householder Matrices

This paper introduces HouseGNN (Householder Graph Neural Network), a novel architecture designed to mitigate oversmoothing in deep graph neural networks. The central design principle is stated as: "The central design decision is to decouple 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."

The HouseGNN update at each layer consists of four steps:

1. Aggregate: Compute the mean neighbourhood message: mi(l) = Σj Pij hj(l) where P is the row-normalized mean-aggregation operator.

2. Project direction: Transform the message by an orthogonal weight matrix and normalize: vi(l) = W(l) mi(l) with (W(l))⊤ W(l) = Id, then ui(l) = vi(l) / ∥vi(l)∥2.

3. Reflect: Form the Householder reflector and apply it: Ri(l) = Id − 2 ui(l)(ui(l))⊤, then zi(l) = Ri(l) hi(l).

4. Nonlinearity: Apply GroupSort: hi(l+1) = GroupSort(zi(l)).

The paper notes: "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."

The paper proves three core properties:

Proposition 1 (Orthogonality and eigenvalues): For any unit vector u ∈ Rd, the Householder matrix R(u) = Id − 2uu⊤ satisfies R(u)⊤ R(u) = Id, R(u)⊤ = R(u). Its spectrum is −1 (multiplicity 1, eigenvector u) and +1 (multiplicity d − 1, eigenspace u⊥).

Proposition 2 (Norm preservation): Let hi(l+1) = GroupSort(Ri(l) hi(l)). Then ∥hi(l+1)∥2 = ∥hi(l)∥2 for every node i and every layer l. Consequently, ∥hi(l)∥2 = ∥hi(0)∥2 for all l ≥ 0.

Proposition 3 (Scale and sign invariance): Define R(v) = Id − 2 vv⊤/∥v∥∥v∥ for v ≠ 0. Then for every nonzero scalar c, R(cv) = R(v). The reflector depends only on span(v).

Theorem 1 (One-step pairwise distance bound): For any nodes i, j and any layer l, dij(l+1) − dij(l) ≤ ρ ∥Oi(l) − Oj(l)∥2. This shows that node-wise operator mismatch [is] the sole mechanism by which pairwise distances can change.

Proposition 5 (Exact reflector mismatch): For any nodes i, j and any layer l, ∥Ri(l) − Rj(l)∥2 = 2√(1 − (γij(l))2) where γij(l) is the absolute cosine similarity between message directions.

Corollary 1 (Same-GroupSort pairwise bound): If Πi(l) = Πj(l), then dij(l+1) − dij(l) ≤ 2ρ√(1 − (γij(l))2).

The paper emphasizes: "The standard oversmoothing mechanism—in which eigenvalues of S appear 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."

The paper reports: GCN collapses beyond two layers, while HouseGNN maintains stable accuracy across the full depth sweeps.

• Cora: GCN accuracy drops from 78.5% at 2 layers to around 21–30% at 8–64 layers. HouseGNN stays in the 75.5–76.8% range throughout.

• CiteSeer: GCN collapses from 66.2% at 2 layers to below 22% at 8–64 layers; HouseGNN varies between 55.9% to 62.7% throughout.

• Texas: Both models remain comparatively stable, consistent with the heterophilic structure of the dataset.

On Cora at L=64: GCN achieves 30.6%, GAT 28.4%, BatchNorm 35.3%, PairNorm 44.0%, Residual 27.9%, while HouseGNN achieves 76.8%. The paper notes: These normalisations slow the collapse but do not eliminate it.

On Wisconsin, HouseGNN attains its best test accuracy at 16 and 32 layers (62.1%). On Cornell, Best performance appears at 8 and 32 layers (55.9%).

Removing the orthogonal weight constraint on Cora at 64 and 80 layers: 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.

At 128 layers on Cora, GroupSort activation achieves only 6.4% test accuracy but maintains high effective rank (54.014) and high Dirichlet energy (3506.059). In contrast, ReLU achieves 71.9% accuracy with effective rank 25.148 and Dirichlet energy 658.764. The paper states: 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.

The paper concludes: 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.

Future work directions include investigat[ing] whether the proposed method can be extended beyond 128 layers and studying the method in combination with residual connections.

Improvement 1: Depth-Robust Representation Learning for Graph Transformers

I can build a graph neural network backbone that replaces standard message-passing updates with Householder reflections, enabling training at 64–128 layers without performance collapse. The improved system can process long-range dependencies in graphs (e.g., molecular property prediction, social network analysis) where shallow models fail, while preserving node-level feature norms to avoid vanishing/exploding gradients.

Improvement 2: Orthogonality-Constrained Sequence Models

I can integrate Householder-based state updates into recurrent or state-space models (e.g., for time-series or language modeling) to maintain stable hidden-state norms across thousands of steps. The improved system can learn long-term dependencies in sequences (e.g., video understanding, financial forecasting) without gradient decay, and its reflection-based updates provide a principled alternative to gating mechanisms.

Improvement 3: Adaptive Oversmoothing Detection and Mitigation

I can use the paper’s theoretical bound (pairwise distance change ≤ operator mismatch) to create a diagnostic tool that monitors cosine similarity between node-wise reflection directions during training. The improved system can automatically detect when oversmoothing begins (via γij dropping below a threshold) and switch to a more expressive activation (e.g., ReLU) or add residual connections, preventing representational collapse in deep architectures.

Improvement 4: Norm-Preserving Feature Encoders for Heterophilic Graphs

I can design a feature extractor that uses Householder reflections for node updates, which the paper shows remains stable on heterophilic datasets (e.g., Texas, Cornell). The improved system can classify nodes in graphs where neighbors are dissimilar (e.g., fraud detection, protein interaction networks) by maintaining distinct local representations even at depth, unlike GCNs that over-smooth.

Improvement 5: Efficient Spectral Control via Reflection Subspaces

I can exploit the theoretical result that Householder matrices have eigenvalues −1, +1 to construct layers with explicit spectral control. The improved system can be used for graph denoising or semi-supervised learning where one needs to preserve high-frequency signals (e.g., image segmentation on irregular grids) by choosing reflection directions that avoid collapsing the representation space.

Improvement 6: GroupSort-Activated Deep Residual Networks

I can replace ReLU with GroupSort in deep residual networks (not just GNNs) to maintain Lipschitz continuity and norm preservation. The improved system can train ultra-deep feedforward networks (e.g., 1000+ layers) for image generation or reinforcement learning policies without gradient explosion, while retaining the expressive power of piecewise linear activations.

Improvement 7: Theoretical Guarantees for Non-Diffusive Message Passing

I can use the paper’s framework to design new message-passing schemes where aggregation only defines a direction, not a magnitude. The improved system can provide provable bounds on feature diversity (via Dirichlet energy) for arbitrary depth, enabling safe deployment in safety-critical applications like autonomous driving perception or medical diagnosis where model reliability at scale is essential.