有向图流中势恢复的规范不变、参数不敏感正则化

# 有向图流中势恢复的规范无关、参数不敏感正则化 来源：https://arxiv.org/html/2607.13609 ###### 摘要 从有向图上的观测流中恢复潜在势（一个带狄利克雷边界的离散泊松问题）是不适定的，而标准的修复方法会适得其反：岭回归收缩到一个规范无意义的原点，导致恢复顺序坍塌并逆转（相对于植入的真实情况，秩相关从 +0.81 变为 −0.42）。规范无关的图狄利克雷能量消除了这一风险，并实现了*参数不敏感*：估计值在 λ 的四个数量级上保持稳定，而岭回归对每一个 λ>0 都会逆转顺序。我们证明了约化求解是 SPD 的，并且在岭回归使动态范围坍塌的地方精确保留了它；同时通过泊松残差仅从流中定位吸收边界。H^1 半范数是经典的；新的贡献在于规范诊断、由此带来的参数不敏感性，以及一个消融实验证明结果对提取方法具有鲁棒性。在三个公开点击流语料库上，规范无关的估计保留了 28–41% 的内部动态范围，而岭回归的保留量低至 0.2%。同样的规范不变性也延续到图神经网络中——每层中和常数模式可防止导致深度有向 GCN 坍塌的过平滑——将这一经典逆问题与图学习中的一个核心问题联系起来。

## 1 引言

在图上的不适定逆问题中引入正则化需要两个决定：选择何种惩罚以及多强的惩罚。它们通常被分开处理，前提是假设一个合理的惩罚会随着 λ 的变化而优雅地退化。本文关注一种这种情况失败的情形：传统的惩罚不仅不会优雅退化，反而会*逆转*解，使得 λ 变成了在可用答案和自信的错误答案之间的选择。该设定是从观测的有向流中恢复潜在的标量*势*——通过流量计数得到的交通网络、通过库存移动得到的供应链、通过转移频率得到的导航日志：这是从散度到势反向求解泊松方程的离散模拟。我们识别出何时会发生这种情况，解释原因，并展示一种不同的惩罚可以消除它，使得答案在 λ 的多个数量级上不敏感。

#### 设置与退化。

设 G=(V,E,W) 是一个带吸收边界 B⊂V 的加权有向无环图。一个势 φ 诱导出通量 q_{ij}=W_{ij}(φ_j−φ_i), (1) 这是欧姆定律和菲克定律的离散模拟，净散度为 b_i=∑_j q_{ji}−∑_j q_{ij}。代入得到有向离散泊松方程 Lφ=b，其中 L 是加权拉普拉斯矩阵。它从带噪声的经验 b 中恢复 φ，并受 B 上的狄利克雷值约束，但这是不适定的（L*1=0，低散度链，有限数据），因此正则化不可避免；标准选择是广义形式的 Tikhonov：argmin_φ ½∥Lφ−b∥₂²+λ∥Rφ∥₂²，默认的岭回归 R=I。

#### 规范不匹配。

势只能确定到一个加法常数，该常数在分配边界值时设定。岭回归向 0 收缩，但 0 在狄利克雷问题中并无特别——它只是边界放置原点的位置。在正边界图上，拉力是不对称的，将内部状态拖向废弃边界，无论其真实位置如何，从而压缩了范围，并且在超过一个小的 λ 后，逆转了顺序。在一个带有植入真实情况的可控仪器上（第 7 节），岭回归的秩相关从 λ=0 时的 +0.81 下降到 ≈−0.42，逆转了顺序，线性相关穿过零（图 1）；唯一安全的岭回归设置是 λ→0——即没有正则化。

#### 参数不敏感。

修复方法是让惩罚对规范不敏感，即取 R 为关联算子，则惩罚为图狄利克雷能量 φ⊤L_Gφ=∑_{(u,v)∈E} w_{uv}(φ_v−φ_u)²（图的 H^1 半范数）；我们将得到的估计器称为*图-索伯列夫正则化*。由于 L_G*1=0，它惩罚的是差值而非幅度，并且沿规范模式是平坦的。实际结果是：估计是原点无关且对 λ 稳定的，在 λ∈[10⁻³,10] 范围内秩相关保持在 +0.81，线性相关保持在 [+0.76,+0.85]，因此强度不会被错误设定。在岭回归迫使做出刀刃选择的地方，狄利克雷能量将其消除了。

#### 什么新，什么不新。

惩罚本身是旧的：H^1 半范数是恒等半范数（广义形式 vs. 标准形式 Tikhonov）的经典替代，φ⊤Lφ 是图信号处理和半监督学习中的标准光滑性泛函。新的贡献在于：(i) 这些先验插值的是*部分观测的*节点信号，而我们的则是一个*非齐次*逆问题，从散度反卷积势并带有狄利克雷边界，决定性性质是规范不变性而非光滑性；(ii) 岭回归不仅次优，而且*主动有害*，逆转了顺序，规范诊断解释了原因；(iii) 由此产生的参数不敏感性；(iv) 一个泊松残差边界诊断方法；以及 (v) 一个带有植入真实情况的行为流应用。保边界的规范无关惩罚（总变差，p-拉普拉斯）在第 2 节中讨论。

#### 贡献。

(1) 参数不敏感性：规范无关惩罚使得恢复的势在 λ 的四数量级范围内稳定（第 5 节）；(2) 岭回归逆转及其规范诊断（秩相关 +0.81→−0.42）；(3) 离散保证——规范不变性（命题 5），一个可通过共轭梯度法扩展到 10⁴ 个节点的 SPD 约化系统（定理 1），以及链上的精确范围保留（定理 2）；(4) 一个可复现的流程（代码：https://github.com/MohammadForouhesh/gauge-flow-recovery），包含泊松残差边界诊断（第 6 节）、提取消融实验、真实语料验证，以及一个下游任务，其中规范无关势是一个可用的节点特征而岭回归的则不是（第 7 和 8 节）。我们明确范围：惩罚保证保留而非信号——数据所支持的任何顺序都跨越 λ 被保留，而不是被破坏。

## 2 相关工作

#### 图上的逆问题和流。

从观测流中恢复势是椭圆型逆问题的离散对应。电阻网络类比是经典的：具有指定边界势的电阻网络服从一个离散拉普拉斯方程，其调和函数编码了相关游走的吸收概率。与我们的设定最接近的是，Jia 等人 (2019) 通过基于 Hodge 的半监督学习恢复边流，而 Schaub 和 Segarra (2018) 通过投影到 Hodge 梯度/旋度子空间对边流去噪。我们的不同之处在于通过带有狄利克雷边界的有向前向算子恢复*节点势*，并诊断由恒等半范数引起的规范诱导的*逆转*，这是一种关于正则化器而非表示形式的失败模式。

#### 正则化与图信号处理。

Tikhonov 正则化是不适定系统的默认稳定器，半范数矩阵编码先验结构；总变差和图趋势滤波惩罚则以尖锐过渡换取二次光滑性。惩罚半范数是否消灭前向算子的零空间决定了估计器的偏差。这一点已知，但我们将其具体化并使其对带有向狄利克雷问题具有后果：恒等半范数不消灭规范模式，导致的偏差不是分辨率损失，而是顺序的逆转。相同的二次型 φ⊤L_Gφ 是图信号处理和拉普拉斯半监督学习中的标准光滑性泛函，是层和联络拉普拉斯推广的“平凡”结构选择——但在那里是针对节点上*部分观测的*信号，而不是像这里一样，规范不变性具有决定性作用的非齐次逆问题。

#### 有向图与 Hodge 分解。

有向图神经网络将方向编码到复厄米（磁）拉普拉斯算子或方向感知消息传递中，而有向图信号处理研究边方向性；这些目标在于节点/边表示学习，而我们保持一个*实的*有向拉普拉斯作为前向算子并对其逆进行正则化。亥姆霍兹-霍奇分解将边流分解为梯度、旋度和调和部分；我们仅使用梯度将流定向到无环支撑上，第 7 节和 7.1 节表明这并非至关重要。图总变差、趋势滤波和 p-拉普拉斯是规范无关的替代方案；岭病理的分界线是规范不变性，它们共享此性质而恒等半范数没有，而不是指数。

#### 与图表示学习的联系。

操作上，规范无关势是一个有向图*节点特征*，在下游任务中有用，而岭回归势则不行（第 8.4 节）。其坍塌是*过平滑*的一个实例——重复传播将节点表示驱动到常数模式，正如幅度惩罚压缩势的范围；我们验证了这一点（表 6），一个普通有向 GCN 的转换 AUC 从 0.86（2 层）下降到 0.81（32 层），同时其节点能量坍塌。相同的规范不变性解决了这个问题：每层中和常数模式——即 L_G*1=0 的逐层模拟——使 AUC 保持平坦（32 层时为 0.85），从单一原理恢复了 PairNorm 和狄利克雷能量约束网络：沿规范模式的平坦性既稳定了逆问题又防止了过平滑。在磁拉普拉斯和层拉普拉斯网络学习嵌入的地方，我们通过一个显式前向算子为每个节点恢复一个可解释的标量。

## 3 从原始流到无环支撑

逆问题是在有向无环图上提出的，但原始流既不是无环的也不纯粹是梯度：它包含往返流量、瞬态环以及没有任何势可以解释的螺线管分量。提取是上游机制；第 7.1 节表明本文的主张*不变*于其实现方式，因此我们保持描述简短，将机制推迟到附录 A。

#### 流与优势。

会话是状态序列；折叠连续重复并计数转移得到经验流 F_{uv}，用作电导 W_{uv}=F_{uv}。往返流量通过一个*优势*测试过滤：对于 ρ≥1，如果 F_{uv}≥ρF_{vu}，则对 (u,v) 是优势的。

#### 定向。

无环支撑需要对优势边进行定向。当会话顺序可用时，默认是一个廉价的*拓扑排序*：按平均访问位置（或净流入）对状态排序，保留尊重该顺序的优势边。这不需要线性求解，第 7.1 节显示它至少与替代方法一样好地恢复势。当只有聚合流矩阵可用时（没有可排序的会话顺序），我们改为通过离散亥姆霍兹-霍奇投影进行定向：梯度势 φ₀ 求解 G⊤G φ₀ = G⊤ω，其中 ω_{uv}=F_{uv}−F_{vu} 是偏斜流，边按 φ₀ 递增定向。它只需要流，但消融实验发现它并不比拓扑排序更准确且更慢；我们仅为了无需顺序的环境而保留它。两者的保留规则在附录 A 中。

#### 无环性与泊松右端项。

###### 命题 1（无环性）。任一朝向诱导出保留支撑 Gδ=(V,Eδ) 的一个拓扑顺序；因此 Gδ 是无环的。令 A 为 Gδ 上的次随机转移算子（出边权重归一化，吸收行在汇点）。由于 Gδ 是一个 DAG，A 是幂零的。

###### 命题 2（幂零性）。如果最长有向路径