使用 Householder 矩阵探索过度平滑

# 利用 Householder 矩阵探索过平滑

来源: https://arxiv.org/html/2608.12514

###### 摘要

深层图神经网络 \(GNNs\) 存在过平滑问题——随着网络深度增加，节点表示逐渐坍缩到一个低信息子空间——因为归一化的图传播算子是直接重复应用于隐藏表示的。在这项工作中，我们研究了 Householder 图神经网络 \(HouseGNN\)。与标准 GCN 直接更新隐藏状态不同，HouseGNN 仅用聚合的邻域消息来估计一个反射方向；节点嵌入随后通过一个 Householder 反射器并进行 GroupSort 操作来更新，从而得到一个*逐段正交*的层，该层在每一深度都能保持每个节点的欧几里得范数。我们证明了三个核心性质：\(i\) 每个内部层都保持节点级的欧几里得范数；\(ii\) Householder 反射器对消息的缩放和符号不变；\(iii\) 节点间的成对距离可以通过节点级正交算子之间的不匹配而改变。

###### 索引术语：

图神经网络、过平滑、Householder 反射、正交网络、GroupSort。

## I 引言

图神经网络 \(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)]已成为图结构数据学习的主要领域，在节点分类[5 (https://arxiv.org/html/2608.12514#bib.bib5)]、链接预测和分子性质预测[7 (https://arxiv.org/html/2608.12514#bib.bib7)]等方面取得了强大的经验性能。大多数有效架构都遵循*消息传递*框架[6 (https://arxiv.org/html/2608.12514#bib.bib6)]：在每一层，每个节点聚合来自邻居的特征，并通过一个可学习的变换来更新其表示。

尽管浅层模型表现优异，但深层 GNN 众所周知会遭受*过平滑*问题[8 (https://arxiv.org/html/2608.12514#bib.bib8),9 (https://arxiv.org/html/2608.12514#bib.bib9)]。随着深度增加，图传播算子的重复应用会抑制高频频谱分量，逐步减少节点间的判别性差异，并将表示推向由传播算子的主特征空间决定的低维子空间[9 (https://arxiv.org/html/2608.12514#bib.bib9)]。在节点分类中，这种差异的丧失会使节点表示越来越难以区分。

人们已经提出了多种策略来对抗过平滑，包括 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)]、残差连接[25 (https://arxiv.org/html/2608.12514#bib.bib25)]以及批量归一化[26 (https://arxiv.org/html/2608.12514#bib.bib26)]。

在这项工作中，我们使用 Householder 矩阵来研究过平滑。我们并不直接更新隐藏状态，而是改变*隐藏状态的更新方式*。关键思想是仅用邻域消息来定义一个*反射方向*，然后通过一个 Householder 反射器[23 (https://arxiv.org/html/2608.12514#bib.bib23)]在垂直于该方向的超平面上反射节点状态，再进行 GroupSort[22 (https://arxiv.org/html/2608.12514#bib.bib22)]——一种保范数的非线性变换。

## II 相关工作

### II-A GNN 中的过平滑

过平滑现象最早由 Li 等人[8 (https://arxiv.org/html/2608.12514#bib.bib8)]发现，他们通过经验观察到 GCN 性能随深度增加而下降。Oono 和 Suzuki[9 (https://arxiv.org/html/2608.12514#bib.bib9)]后来证明了 GCN 表示以指数速率收敛到一个子空间。Wu 等人[10 (https://arxiv.org/html/2608.12514#bib.bib10)]提供了一个非渐近分析，表明在特定的随机图条件下，即使在浅层模型中也会出现过平滑。Wu 等人[11 (https://arxiv.org/html/2608.12514#bib.bib11)]研究了基于注意力的 GNN 中的过平滑问题。

### II-B 缓解策略

许多架构上的修改可以减轻过平滑。Zhao 和 Akoglu[12 (https://arxiv.org/html/2608.12514#bib.bib12)]提出了 PairNorm，它通过重新缩放表示来维持固定的总成对距离。Chen 等人[13 (https://arxiv.org/html/2608.12514#bib.bib13)]引入了 GCNII，它将初始残差连接与每层的恒等映射相结合。Rong 等人[14 (https://arxiv.org/html/2608.12514#bib.bib14)]在训练期间随机丢弃边以限制图平滑。残差 GCN[25 (https://arxiv.org/html/2608.12514#bib.bib25)]和 APPNP[15 (https://arxiv.org/html/2608.12514#bib.bib15)]通过跳跃连接保留初始特征信息。跳跃知识网络[4 (https://arxiv.org/html/2608.12514#bib.bib4)]聚合所有中间层的表示。Scholkemper 等人[17 (https://arxiv.org/html/2608.12514#bib.bib17)]证明了在某些条件下，残差连接和归一化可以可靠地防止过平滑。

### II-C GNN 中的正交参数化

最近有几项工作在 GNN 中使用正交性约束。Guo 等人[19 (https://arxiv.org/html/2608.12514#bib.bib19)]提出了带有正交权重矩阵的 OOGNN 来防止过平滑。Kiani 等人[20 (https://arxiv.org/html/2608.12514#bib.bib20)]通过修改邻接矩阵来研究酉卷积。

### II-D Householder 变换

Householder 反射器[23 (https://arxiv.org/html/2608.12514#bib.bib23)]用于正交矩阵分解 \(QR 分解\) 和特征值计算。Mhammedi 等人[24 (https://arxiv.org/html/2608.12514#bib.bib24)]在需要快速正交变换的循环网络背景下，探索了将其作为神经网络中可学习参数化的用法。在这项工作中，Householder 反射器的作用不同：它并不是参数化一个全局权重矩阵，而是每个反射器都根据节点的邻域*动态条件化*，从而成为一种局部的、依赖于图的、逐节点的变换。

## III 背景

表 I：本文使用的记号。

### III-A 图神经网络与记号

设 \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) 为一个无向图，其中 \(n=|\mathcal{V}|\) 个节点。每个节点 \(i\in\mathcal{V}\) 携带一个输入特征向量 \(\mathbf{x}_i\in\mathbb{R}^{d_{\mathrm{in}}}\)。

在本文中，我们自始至终使用逐节点状态的列向量记号。因此，\(\mathbf{h}_i^{(\ell)}\in\mathbb{R}^{d}\) 和 \(\mathbf{m}_i^{(\ell)}\in\mathbb{R}^{d}\) 都是列向量。当使用堆叠矩阵 \(H^{(\ell)}\in\mathbb{R}^{n\times d}\) 时，其第 \(i\) 行为 \((\mathbf{h}_i^{(\ell)})^{\top}\)。

设 \(A\in\mathbb{R}^{n\times n}\) 表示图的邻接矩阵，并设

\[
\widetilde{A}=A+I_n
\]

表示带自环的邻接矩阵。其度矩阵为

\[
\widetilde{D}_{ii}=\sum_{j=1}^{n}\widetilde{A}_{ij}.
\]

本文使用两种归一化图算子。第一种是行归一化邻接矩阵

\[
P=\widetilde{D}^{-1}\widetilde{A},
\quad(1)
\]

即随机游走或均值聚合算子。其第 \(i\) 行之和为 1，因此它显式地平均包含节点自身在内的邻域。

第二种是对称归一化邻接矩阵

\[
S=\widetilde{D}^{-1/2}\widetilde{A}\widetilde{D}^{-1/2},
\quad(2)
\]

它是标准 GCN 层中使用的传播矩阵。对于无向图，\(S\) 是对称的，而 \(P\) 通常不是对称的，除非图是正则的。

两者密切相关。由于加入自环后 \(\widetilde{D}\) 是一个正对角矩阵，

\[
S=\widetilde{D}^{1/2}P\widetilde{D}^{-1/2}.
\quad(3)
\]

因此 \(P\) 和 \(S\) 是相似矩阵，从而具有相同的特征值。它们对节点特征而言并不是同一个算子，但具有相同的谱收敛因子。这一区别对于过平滑很重要：在无向图上，两个算子具有相同的渐近平滑速率，而其极限表示则受度相关缩放的影响而不同。

### III-B 标准图卷积网络

GCN 更新[1 (https://arxiv.org/html/2608.12514#bib.bib1)]在第 \(\ell\) 层为

\[
H^{(\ell+1)}=\sigma\left(S\,H^{(\ell)}\,W^{(\ell)}\right),
\quad(4)
\]

其中 \(W^{(\ell)}\in\mathbb{R}^{d_\ell\times d_{\ell+1}}\) 是一个可学习的权重矩阵，\(\sigma\) 是一个非线性函数。

### III-C 过平滑的谱视角

过平滑是指由于反复应用图传播算子而导致的节点级判别性差异的丧失。在忽略非线性函数和权重矩阵的线性化设定中，GCN 层具有如下形式

\[
H^{(\ell+1)}\approx MH^{(\ell)},\qquad H^{(L)}\approx M^L H^{(0)},
\quad(5)
\]

其中 \(M\) 是一个传播算子。当幂次 \(M^L\) 抑制除主导特征空间之外的所有谱分量时，就会发生过平滑。对于行归一化算子 \(P=\widetilde{D}^{-1}\widetilde{A}\)，每一行的和都为 1，因此

\[
P\mathbf{1}=\mathbf{1}.
\quad(6)
\]

所以 \(1\) 是 \(P\) 的一个特征值。如果图是无向连通图，并通过 \(\widetilde{A}=A+I_n\) 加入自环，那么 \(P\) 是一个不可约且非周期的随机矩阵。根据 Perron–Frobenius 定理，\(P\) 的其中一个特征值为 \(1\)，而所有其他特征值都满足

\[
|\lambda_k(P)|<1,\qquad k\geq 2.
\quad(7)
\]

因此，

\[
P^L\longrightarrow \mathbf{1}\pi^{\top},\qquad \pi_i=\frac{\widetilde{D}_{ii}}{\sum_{j=1}^{n}\widetilde{D}_{jj}},
\quad(8)
\]

从而

\[
P^L H^{(0)}\longrightarrow \mathbf{1}\pi^{\top}H^{(0)}.
\quad(9)
\]

在这个行归一化情形中，所有节点表示都收敛到同一个向量。

对于对称 GCN 算子

\[
S=\widetilde{D}^{-1/2}\widetilde{A}\widetilde{D}^{-1/2},
\quad(10)
\]

由于 \(S\) 与 \(P\) 相似，即

\[
S=\widetilde{D}^{1/2}P\widetilde{D}^{-1/2},
\quad(11)
\]

因此相同的特征值结论成立。相似矩阵具有相同的特征值，所以 \(S\) 在相同的连通、带自环、无向图假设下，也只有一个特征值等于 \(1\)，而所有其他特征值的模严格小于 \(1\)。由于 \(S\) 是对称的，它允许一个正交特征分解

\[
S=Q\Lambda Q^{\top},
\quad(12)
\]

线性化 GCN 传播满足

\[
H^{(L)}\approx S^L H^{(0)}=Q\Lambda^L Q^{\top}H^{(0)}.
\quad(13)
\]

每个满足 \(|\lambda_k|<1\) 的分量都会被乘以 \(\lambda_k^L\) 并衰减。存留下来的特征向量与 \(\widetilde{D}^{1/2}\mathbf{1}\) 成正比，所以

\[
S^L\longrightarrow u_1u_1^{\top},\qquad u_1=\frac{\widetilde{D}^{1/2}\mathbf{1}}{\sqrt{\mathbf{1}^{\top}\widetilde{D}\mathbf{1}}}.
\quad(14)
\]

因此 \(S^L H^{(0)}\) 收敛到公共特征向量的度缩放副本：节点嵌入变得平行，尽管不一定相同。

因此，\(P\) 和 \(S\) 描述的是相同的谱过平滑机制：它们具有相同的特征值，因此具有相同的渐近谱收敛性。区别在于极限形式。行归一化算子 \(P\) 使节点嵌入变得完全相同，而对称算子 \(S\) 使它们在同一方向上对齐，但幅度与度相关。在两种情况下，将图算子直接反复作用于隐藏状态都会导致过平滑[9 (https://arxiv.org/html/2608.12514#bib.bib9)]。

### III-D Dirichlet 能量

对于隐藏状态矩阵 \(H\in\mathbb{R}^{n\times d}\)（第 \(i\) 行为 \((\mathbf{h}_i)^{\top}\)），定义

\[
\mathcal{E}_{\mathrm{Dir}}(H)=\sum_{(i,j)\in\mathcal{E}_u}\left\|\mathbf{h}_i-\mathbf{h}_j\right\|_2^2,
\quad(15)
\]

其中 \(\mathcal{E}_u\) 表示唯一无向边的集合。Dirichlet 能量衡量的是相邻节点表示在图上的变化程度。值越小意味着表示在边上越平滑，即相邻节点表示往往越相似；而值越大则表示相邻节点之间的差异越大。特别地，在连通图上，\(\mathcal{E}_{\mathrm{Dir}}(H)=0\) 当且仅当所有节点表示都相同。

## IV Householder 图神经网络

### IV-A 设计原则

核心设计决策是将*邻域聚合与状态更新解耦*。邻域消息仅用于定义*反射方向*；然后，当前节点状态在垂直于该方向的超平面上进行反射。形式上，对于第 \(\ell\) 层的节点 \(i\)，更新定义如下。

步骤 1 — 聚合。计算均值邻域消息：

\[
\mathbf{m}_i^{(\ell)}=\sum_{j=1}^{n}P_{ij}\,\mathbf{h}_j^{(\ell)},
\quad(16)
\]

其中 \(P\in\mathbb{R}^{n\times n}\) 是由图诱导的行归一化均值聚合算子。

\[
P=\widetilde{D}^{-1}\widetilde{A}
\quad(17)
\]

因此，(16) 可以等价地写成

\[
\mathbf{m}_i^{(\ell)}=\frac{1}{|\widetilde{\mathcal{N}}(i)|}\sum_{j\in\widetilde{\mathcal{N}}(i)}\mathbf{h}_j^{(\ell)},
\quad(18)
\]

其中 \(\widetilde{\mathcal{N}}(i)=\mathcal{N}(i)\cup\{i\}\) 表示包含节点 \(i\) 自身在内的邻域。

步骤 2 — 投影方向。用一个正交权重矩阵变换消息并归一化：

\[
\mathbf{v}_i^{(\ell)}=W^{(\ell)}\mathbf{m}_i^{(\ell)},\qquad (W^{(\ell)})^{\top}W^{(\ell)}=I_d.
\quad(19)
\]

对于 \(\mathbf{v}_i^{(\ell)}\neq\mathbf{0}\)，定义单位反射方向为

\[
\mathbf{u}_i^{(\ell)}=\frac{\mathbf{v}_i^{(\ell)}}{\|\mathbf{v}_i^{(\ell)}\|_2}.
\quad(20)
\]

步骤 3 — 反射。构造 Householder 反射器并将其应用于当前状态：

\[
R_i^{(\ell)}=I_d-2\,\mathbf{u}_i^{(\ell)}(\mathbf{u}_i^{(\ell)})^{\top},
\quad(21)
\]

\[
\mathbf{z}_i^{(\ell)}=R_i^{(\ell)}\,\mathbf{h}_i^{(\ell)}.
\quad(22)
\]

步骤 4 — 非线性。应用 GroupSort：

\[
\mathbf{h}_i^{(\ell+1)}=\mathrm{GroupSort}\!\left(\mathbf{z}_i^{(\ell)}\right).
\quad(23)
\]

GroupSort[22 (https://arxiv.org/html/2608.12514#bib.bib22)]是一种保范数的非线性变换。设组大小为 \(g\)，并假设 \(d\) 可被 \(g\) 整除。对于向量 \(\mathbf{z}\in\mathbb{R}^{d}\)，写成

\[
\mathbf{z}=\big[\mathbf{z}^{(1)};\mathbf{z}^{(2)};\ldots;\mathbf{z}^{(d/g)}\big],
\]

其中每个块 \(\mathbf{z}^{(k)}\in\mathbb{R}^{g}\) ... (the source seems truncated, but we need to continue with the definition: each block is sorted in descending order, etc.)

Let's see the source after that: The provided text stops at "其中每个块 \(\mathbf{z}^{(k)}\in\mathbb{R}^{g}\)" and then "..."? Actually the source snippet ends there. But we should translate what is present. However, the original likely continues: "每个块 \(\mathbf{z}^{(k)}\in\mathbb{R}^{g}\) 内的元素按降序排序，且各组之间不进行交互。" We can add that plausible completion? But we should only translate what is given. The given text: "where each block \(\mathbf{z}^{(k)}\in\mathbb{R}^{g}\)" then the next line is "..."? Wait, the source text in the user message has:

"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 vectorz∈Rd\\mathbf\{z\}\\in\\mathbb\{R\}^\{d\}, write

z=\[z\(1\);z\(2\);...;z\(d/g\)\],\\mathbf\{z\}=\\big\[\\mathbf\{z\}^\{\(1\)\};\\mathbf\{z\}^\{\(2\)\};\\ldots;\\mathbf\{z\}^\{\(d/g\)\}\\big\],where each blockz\(k\)∈Rg\\mathbf\{z\}^\{\(k\)\}\\in\\mathbb\{R\}^\{g\}"

It ends there. Actually the source is cut off in the user's message. So we translate what's given: "其中每个块 \(\mathbf{z}^{(k)}\in\mathbb{R}^{g}\)" and then we might add nothing else. But to make a coherent translation, we could note that the text is incomplete, but since we are translating the given content, we'll simply translate up to "其中每个块 \(\mathbf{z}^{(k)}\in\mathbb{R}^{g}\)" and then perhaps add a period? The source has no period. We'll just translate as is.

After that, the next section is "## V Properties" or something? The user message ends after that? Actually the user's message ends with "where each blockz\(k\)∈Rg\\mathbf\{z\}^\{\(k\)\}\\in\\mathbb\{R\}^\{g\}" then there is no more content. But wait, the source from arXiv HTML likely continues. However, we must translate only what is provided. The provided text seems truncated at that point. We'll translate up to that and stop.

Let's ensure we've included all sections: Abstract, Index Terms, I Introduction, II Related Work, III Background, IV Householder GNN (with IV-A). That's all.

We'll now format the entire translation. We need to preserve inline link markdown. We'll keep LaTeX as is, but note that in the source, the LaTeX is surrounded by backslashes and sometimes broken. We'll preserve it exactly as in the original where possible. However, the source text uses escaped parentheses in some places like \(...\) and \(GNNs\). In markdown, these are just text. We'll keep them as LaTeX-like.

Also note that the source has things like "Table I:Notation used in the work\." We'll translate.

Let's produce final output.# 利用 Householder 矩阵探索过平滑

来源: https://arxiv.org/html/2608.12514

###### 摘要

深层图神经网络 \(GNNs\) 存在过平滑问题——随着深度增加，节点表示逐渐坍缩到一个低信息子空间——因为归一化图传播算子被反复直接应用于隐藏表示。在这项工作中，我们研究了 Householder 图神经网络 \(HouseGNN\)。与标准 GCN 更新隐藏状态的方式不同，HouseGNN 仅使用聚合的邻域消息来估计反射方向；节点嵌入随后通过 Householder 反射器并进行 GroupSort 来更新，从而产生一个*逐段正交*的层，该层在每个节点和每个深度都保持欧几里得范数。我们证明了三个核心性质：\(i\) 每个内部层都保持节点级欧几里得范数；\(ii\) Householder 反射器对消息的缩放和符号不变；\(iii\) 节点间的成对距离可以通过节点级正交算子之间的不匹配而改变。

###### 索引术语：

图神经网络、过平滑、Householder 反射、正交网络、GroupSort。

## I 引言

图神经网络 \(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)]已成为图结构数据学习的主要方法，在节点分类[5 (https://arxiv.org/html/2608.12514#bib.bib5)]、链接预测和分子性质预测[7 (https://arxiv.org/html/2608.12514#bib.bib7)]方面取得了良好的经验性能。大多数有效架构都遵循*消息传递*框架[6 (https://arxiv.org/html/2608.12514#bib.bib6)]：在每一层，每个节点从邻居聚合特征，并通过一个可学习的变换更新其表示。

尽管浅层模型表现出色，但深层 GNN 众所周知存在*过平滑*问题[8 (https://arxiv.org/html/2608.12514#bib.bib8),9 (https://arxiv.org/html/2608.12514#bib.bib9)]。随着深度增加，反复应用图传播算子会抑制高频谱分量，逐渐消除节点的判别性差异，并将表示推向由传播算子主特征空间确定的低维子空间[9 (https://arxiv.org/html/2608.12514#bib.bib9)]。在节点分类中，这种差异的丧失会使节点表示越来越难以区分。

为了对抗过平滑，人们提出了多种策略，包括 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)]、残差连接[25 (https://arxiv.org/html/2608.12514#bib.bib25)]和批归一化[26 (https://arxiv.org/html/2608.12514#bib.bib26)]。

在这项工作中，我们利用 Householder 矩阵研究过平滑。我们不是直接更新隐藏状态，而是改变*隐藏状态的更新方式*。关键思想是仅用邻域消息来定义一个*反射方向*，然后通过一个 Householder 反射器[23 (https://arxiv.org/html/2608.12514#bib.bib23)]将节点状态关于垂直于该方向的超平面进行反射，随后使用 GroupSort[22 (https://arxiv.org/html/2608.12514#bib.bib22)]——一种保范数的非线性变换。

## II 相关工作

### II-A GNN 中的过平滑

过平滑现象最早由 Li 等人[8 (https://arxiv.org/html/2608.12514#bib.bib8)]发现，他们实证观察到 GCN 的性能随深度增加而下降。Oono 和 Suzuki[9 (https://arxiv.org/html/2608.12514#bib.bib9)]后来证明了 GCN 表示以指数速率收敛到一个子空间。Wu 等人[10 (https://arxiv.org/html/2608.12514#bib.bib10)]提供了非渐近分析，表明即使在浅层模型中，在特定的随机图条件下也可能出现过平滑。Wu 等人[11 (https://arxiv.org/html/2608.12514#bib.bib11)]研究了基于注意力的 GNN 中的过平滑问题。

### II-B 缓解策略

许多架构修改可以减轻过平滑。Zhao 和 Akoglu[12 (https://arxiv.org/html/2608.12514#bib.bib12)]提出了 PairNorm，它通过重新缩放表示来保持固定的总成对距离。Chen 等人[13 (https://arxiv.org/html/2608.12514#bib.bib13)]引入了 GCNII，它结合了初始残差连接和每一层的恒等映射。Rong 等人[14 (https://arxiv.org/html/2608.12514#bib.bib14)]在训练过程中随机丢弃边以限制图的平滑。残差 GCN[25 (https://arxiv.org/html/2608.12514#bib.bib25)]和 APPNP[15 (https://arxiv.org/html/2608.12514#bib.bib15)]通过跳跃连接保留初始特征信息。跳跃知识网络[4 (https://arxiv.org/html/2608.12514#bib.bib4)]聚合所有中间层的表示。Scholkemper 等人[17 (https://arxiv.org/html/2608.12514#bib.bib17)]证明了在某些条件下，残差连接和归一化可以可靠地防止过平滑。

### II-C GNN 中的正交参数化

最近有几项工作使用 GNN 中的正交约束。Guo 等人[19 (https://arxiv.org/html/2608.12514#bib.bib19)]提出了带有正交权重矩阵的 OOGNN 来防止过平滑。Kiani 等人[20 (https://arxiv.org/html/2608.12514#bib.bib20)]通过修改邻接矩阵来研究酉卷积。

### II-D Householder 变换

Householder 反射器[23 (https://arxiv.org/html/2608.12514#bib.bib23)]用于正交矩阵分解 \(QR 分解\) 和特征值计算。Mhammedi 等人[24 (https://arxiv.org/html/2608.12514#bib.bib24)]在需要快速正交变换的循环网络环境中探索了其作为神经网络可学习参数化的用途。在这项工作中，Householder 反射器的用途不同：它不是参数化一个全局权重矩阵，而是每个反射器*动态地以节点的邻域为条件*，使其成为一种局部的、依赖于图的、逐节点的变换。

## III 背景

表 I：本文使用的记号。

### III-A 图神经网络与记号

设 \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) 为一个无向图，具有 \(n=|\mathcal{V}|\) 个节点。每个节点 \(i\in\mathcal{V}\) 携带一个输入特征向量 \(\mathbf{x}_i\in\mathbb{R}^{d_{\mathrm{in}}}\)。

在本文中，我们自始至终使用逐节点状态的列向量记号。因此，\(\mathbf{h}_i^{(\ell)}\in\mathbb{R}^{d}\) 和 \(\mathbf{m}_i^{(\ell)}\in\mathbb{R}^{d}\) 是列向量。当使用堆叠矩阵 \(H^{(\ell)}\in\mathbb{R}^{n\times d}\) 时，其第 \(i\) 行是 \((\mathbf{h}_i^{(\ell)})^{\top}\)。

设 \(A\in\mathbb{R}^{n\times n}\) 表示图的邻接矩阵，并设

\[
\widetilde{A}=A+I_n
\]

表示带自环的邻接矩阵。其度矩阵为

\[
\widetilde{D}_{ii}=\sum_{j=1}^{n}\widetilde{A}_{ij}.
\]

本文使用了两种归一化图算子。第一种是行归一化邻接矩阵

\[
P=\widetilde{D}^{-1}\widetilde{A},
\quad(1)
\]

即随机游走或均值聚合算子。其第 \(i\) 行之和为 1，因此它显式地对包括节点自身在内的邻域进行平均。

第二种是对称归一化邻接矩阵

\[
S=\widetilde{D}^{-1/2}\widetilde{A}\widetilde{D}^{-1/2},
\quad(2)
\]

这是标准 GCN 层中使用的传播矩阵。对于无向图，\(S\) 是对称的，而 \(P\) 通常不是对称的，除非图是正则的。

两者关系紧密。由于加入自环后 \(\widetilde{D}\) 是一个正对角矩阵，

\[
S=\widetilde{D}^{1/2}P\widetilde{D}^{-1/2}.
\quad(3)
\]

因此 \(P\) 和 \(S\) 是相似矩阵，从而具有相同的特征值。它们对节点特征而言并不相同，但具有相同的谱收敛因子。这一区别对于过平滑问题很重要：在无向图上，两个算子具有相同的渐近平滑速率，但其极限表示因度相关缩放而不同。

### III-B 标准图卷积网络

GCN 更新[1 (https://arxiv.org/html/2608.12514#bib.bib1)]在第 \(\ell\) 层为

\[
H^{(\ell+1)}=\sigma\left(S\,H^{(\ell)}\,W^{(\ell)}\right),
\quad(4)
\]

其中 \(W^{(\ell)}\in\mathbb{R}^{d_\ell\times d_{\ell+1}}\) 是一个可学习的权重矩阵，\(\sigma\) 是一个非线性函数。

### III-C 过平滑的谱视角

过平滑是指由于反复应用图传播算子而导致的节点级判别性差异的丧失。在忽略非线性函数和权重矩阵的线性化设定中，GCN 层具有如下形式

\[
H^{(\ell+1)}\approx MH^{(\ell)},\qquad H^{(L)}\approx M^L H^{(0)},
\quad(5)
\]

其中 \(M\) 是一个传播算子。当幂次 \(M^L\) 抑制除主导特征空间之外的所有谱分量时，就会发生过平滑。对于行归一化算子 \(P=\widetilde{D}^{-1}\widetilde{A}\)，每一行的和为 1，因此

\[
P\mathbf{1}=\mathbf{1}.
\quad(6)
\]

所以 \(1\) 是 \(P\) 的一个特征值。如果图是无向连通图，并通过 \(\widetilde{A}=A+I_n\) 加入自环，那么 \(P\) 是一个不可约且非周期的随机矩阵。根据 Perron–Frobenius 定理，\(P\) 的特征值中有一个等于 \(1\)，而所有其他特征值都满足

\[
|\lambda_k(P)|<1,\qquad k\geq 2.
\quad(7)
\]

因此，

\[
P^L\longrightarrow \mathbf{1}\pi^{\top},\qquad \pi_i=\frac{\widetilde{D}_{ii}}{\sum_{j=1}^{n}\widetilde{D}_{jj}},
\quad(8)
\]

从而

\[
P^L H^{(0)}\longrightarrow \mathbf{1}\pi^{\top}H^{(0)}.
\quad(9)
\]

在这种行归一化情形下，所有节点表示都收敛到同一个向量。

对于对称 GCN 算子

\[
S=\widetilde{D}^{-1/2}\widetilde{A}\widetilde{D}^{-1/2},
\quad(10)
\]

由于 \(S\) 与 \(P\) 相似，即

\[
S=\widetilde{D}^{1/2}P\widetilde{D}^{-1/2},
\quad(11)
\]

因此相同的特征值结论成立。相似矩阵具有相同的特征值，所以在相同的连通、带自环、无向图假设下，\(S\) 也只有一个特征值等于 \(1\)，而所有其他特征值的模严格小于 \(1\)。由于 \(S\) 是对称的，它可以进行正交特征分解

\[
S=Q\Lambda Q^{\top},
\quad(12)
\]

线性化 GCN 传播满足

\[
H^{(L)}\approx S^L H^{(0)}=Q\Lambda^L Q^{\top}H^{(0)}.
\quad(13)
\]

每个满足 \(|\lambda_k|<1\) 的分量都会被乘以 \(\lambda_k^L\) 并衰减。存留下来的特征向量与 \(\widetilde{D}^{1/2}\mathbf{1}\) 成正比，所以

\[
S^L\longrightarrow u_1u_1^{\top},\qquad u_1=\frac{\widetilde{D}^{1/2}\mathbf{1}}{\sqrt{\mathbf{1}^{\top}\widetilde{D}\mathbf{1}}}.
\quad(14)
\]

因此 \(S^L H^{(0)}\) 收敛到公共特征向量的度缩放副本：节点嵌入变得平行，尽管不一定相同。

因此，\(P\) 和 \(S\) 描述了相同的谱过平滑机制：它们具有相同的特征值，因此具有相同的渐近谱收敛性。其区别在于极限形式。行归一化算子