An inverse problem for fractional random walks on finite graphs

这是一份关于论文《有限图上分数随机游走的逆问题》（AN INVERSE PROBLEM FOR FRACTIONAL RANDOM WALKS ON FINITE GRAPHS）的详细技术总结。

1. 研究背景与问题定义

背景：
本文受分数阶 Calderón 问题（Fractional Calderón problem）在黎曼流形背景下研究的启发，旨在将这一连续域中的逆问题离散化到有限图上。传统的图逆问题（如电阻网络）通常假设图的结构（边集）已知，仅恢复权重（电导率）。然而，本文挑战了更困难的设定：在仅观测到部分顶点上的随机游走数据的情况下，同时恢复图的拓扑结构（顶点数、边集）和电导率分布。

核心问题：
给定一个有限连通图 $G=(X, E)$ 和定义在顶点上的电导率函数 $\gamma: X \to (0, \infty)$。

• 随机游走模型：定义了一个“分数电导率随机游走” $H^x_0$。其转移概率 $P(x, y)$ 不仅依赖于电导率 $\gamma$，还允许长距离跳跃（非局部性）。转移概率公式为：
  $$P(x, y) := \frac{1}{m(x)} \frac{\gamma^{1/2}(x)\gamma^{1/2}(y)}{d_G(x, y)^\alpha}$$
  其中 $d_G(x, y)$ 是图上的距离，$\alpha > 0$ 是已知分数阶参数，$m(x)$ 是归一化常数。
• 观测数据：数据是“部分”的。观测者只能在一个固定的可观测子集 $B \subseteq X$ 上观测随机游走者的位置。
• 逆问题目标：仅利用可观测顶点 $B$ 上的随机游走数据（即从 $B$ 出发并在 $B$ 中结束的转移概率序列），恢复：
  1. 图的总顶点数 $|X|$。
  2. 图的边集 $E$。
  3. 电导率 $\gamma$（在正比例因子意义下）。

2. 方法论与数学工具

文章采用线性代数、图论和非局部向量微积分相结合的方法，主要步骤如下：

2.1 数据表示与分块矩阵

将转移矩阵 $P$ 根据可观测集 $B$（大小为 $N$）和不可观测集 $X \setminus B$（大小为 $M$）进行分块：
$$P = \begin{pmatrix} P_{11} & P_{12} \\ P_{21} & P_{22} \end{pmatrix}$$
观测数据定义为序列 $\Lambda_\omega(P) = \{(P^k)_{11}\}_{k \in \mathbb{N}}$，即 $k$ 步内从 $B$ 到 $B$ 的转移概率子矩阵。

2.2 规范类（Gauge Class）的刻画

利用矩阵的满秩分解（Full rank factorization）和 Moore-Penrose 伪逆，作者证明了观测数据 $\Lambda_3(P)$（仅需前 3 步数据）足以确定转移矩阵 $P$ 所属的一个规范类。

• 关键发现：如果两个矩阵 $P$ 和 $\tilde{P}$ 满足 $\Lambda_3(P) = \Lambda_3(\tilde{P})$，则存在一个可逆矩阵 $A$ 使得：
  $$P = (I_N \oplus A) \tilde{P} (I_N \oplus A^{-1})$$
  这表明观测数据无法唯一确定 $P$，只能确定其在群作用下的轨道。
• 冗余性：令人惊讶的是，超过 3 步的观测数据（$k > 3$）对于确定该规范类是冗余的。这是分数阶随机游走非局部性质的体现，与经典随机游走（需要无限步才能探测远距离节点）形成鲜明对比。

2.3 物理约束与规范约化

并非所有满足上述代数关系的矩阵都是合法的转移矩阵。合法的转移矩阵必须满足：

1. 行随机性（Row-stochastic）。
2. 由正对称矩阵（相互作用矩阵 $C$）经行归一化得到。
   通过分析这些约束，作者进一步缩小了解的范围，证明了在特定条件下（如 $P=\tilde{P}$），电导率 $\gamma$ 和边集 $E$ 可以被恢复。

2.4 边集与电导率的恢复算法

在已知转移矩阵 $P$（或其规范类代表）后，利用图论性质恢复结构：

• 叶节点识别：利用距离函数的极值性质，通过计算特定比率 $R_{ab}$ 来识别图的叶节点（Leaf nodes）及其邻居。
• 距离恢复：一旦识别出叶节点，利用观测数据中的距离比率关系，可以逐步恢复所有顶点对之间的图距离 $d_G(x, y)$。
• 边集确定：图距离的完全恢复直接导出了边集 $E$ 的确定。
• 电导率恢复：在已知 $E$ 和 $d_G$ 的情况下，利用 $P$ 与 $\gamma$ 的关系式，可以恢复 $\gamma$ 至多一个正比例因子。

3. 主要结果

3.1 唯一性与重构定理 (Theorem 1.2)

对于满足“可容许性”条件（Admissible graph）的图 $G$：

• 顶点数确定：仅凭 $\Lambda_3(P)$ 即可确定顶点总数 $|X|$。
• 规范类确定：数据确定了 $P$ 所属的规范类（由群作用 $g(A, \tilde{P})$ 定义）。
• 完全重构：如果已知转移矩阵 $P$ 本身（即消除了规范模糊性），则可以唯一恢复边集 $E$ 和电导率 $\gamma$（$\gamma$ 仅差一个正比例因子）。

3.2 数据特征化定理 (Theorem 1.3)

• 充分性：$\Lambda_3(P) = \Lambda_3(\tilde{P})$ 等价于 $\Lambda_\omega(P) = \Lambda_\omega(\tilde{P})$。
• 必要性：少于 3 步的数据（$\Lambda_2$ 或 $\Lambda_1$）不足以恢复 $P$ 的规范类，因为它们不包含关于不可观测节点间距离的足够信息。
• 非局部性质：这一结果揭示了分数阶随机游走的强非局部性，即短时间的观测即可“感知”整个图的结构。

3.3 可容许性条件

论文定义了图的可容许性条件（A1 和 A2），确保转移矩阵的特定子块具有满秩，从而保证上述代数推导成立。例如，图不能是星型图，且必须包含至少两个叶节点，叶节点的偏心率需大于 3。

4. 关键贡献与创新点

1. 非局部逆问题的离散化：首次将分数阶 Calderón 问题的思想系统地应用于有限图上的随机游走逆问题，建立了离散非局部算子与连续分数阶算子之间的联系。
2. 3 步数据的充分性：发现并证明了仅需观测随机游走的前 3 步数据即可完全确定转移矩阵的规范类。这在经典随机游走（局部）中是不可能的，是分数阶非局部性的直接体现。
3. 同时恢复结构与参数：突破了传统图逆问题假设图结构已知的限制，证明了在部分观测下，可以同时恢复未知的图拓扑结构（边集）和物理参数（电导率）。
4. 规范类分析：深入分析了由观测数据引起的规范模糊性（Gauge ambiguity），并给出了该规范类的代数结构描述。

5. 意义与展望

• 理论意义：该工作为理解分数阶算子的唯一延拓性质（Unique Continuation Property, UCP）提供了新的离散视角。分数阶随机游走的“短步长即知全局”特性与连续情形下的 UCP 有着深刻的内在联系。
• 应用潜力：为网络拓扑发现、光学层析成像（Optical Tomography）和神经科学中的网络重构提供了新的数学工具和理论依据，特别是在只能进行部分观测且存在长程相互作用（非局部扩散）的场景中。
• 未来方向：
  • 稳定性分析：研究观测数据中的微小误差对重构结果（特别是边集）的影响，预期存在临界情况导致拓扑结构的突变。
  • 黎曼流形推广：计划将此离散方法推广到黎曼流形上的分数阶电导率逆问题，通过图逼近流形来构建连续算子。
  • 条件必要性：目前可容许性条件（A1, A2）是充分条件，未来需探讨其是否也是唯一性成立的必要条件。

总结

这篇文章通过精妙的线性代数构造和图论分析，解决了有限图上分数随机游走的逆问题。它不仅证明了在部分观测下恢复图结构和物理参数的可行性，还揭示了非局部随机游走中“少量数据蕴含全局信息”这一反直觉的数学现象，为分数阶逆问题的研究开辟了新的离散化路径。