技术摘要：边增强随机游走的统计估计

1. 问题陈述

本文探讨了有限、连通无向图 $G = (V, E)$ 上**边增强随机游走（ERRWs）**的统计估计问题。与标准马尔可夫链不同，ERRW 表现出路径依赖的转移概率，即遍历某条边的可能性随其被访问次数的增加而增大。

具体目标是在给定 $K$ 条长度为 $T$ 的独立样本轨迹的情况下，恢复初始边权重（或初始局部时间）$A = (a_e)_{e \in E} \in \mathbb{R}^E_{++}$。作者通过基于比率的散度 $d(A, \hat{A})$ 定义估计误差，旨在实现逐元素的乘性近似。

论文早期提出的一个关键理论发现是单条轨迹的不足性。即使拥有无限长的轨迹，如果两个不同的初始权重向量 $A$ 和 $\tilde{A}$ 足够接近，也无法以高概率区分它们。这是因为诱导混合测度（随机环境）之间的 Kullback-Leibler (KL) 散度对于小扰动 $\epsilon$ 而言按 $O(\epsilon^2)$ 缩放，导致假设检验的误差被限制在远离零的范围内。因此，本文确立了**多条独立轨迹（$K \ge 1$）**对于参数恢复是严格必要的。

2. 方法论

所提出的方法利用了 ERRW 与**随机环境中的随机游走（RWRE）**之间的深刻联系，具体利用了刻画随机边电导混合测度的"魔法公式"。

2.1 理论框架：RWRE 与混合测度

作者将 ERRW 视为可逆马尔可夫链的混合体。随机环境 $W$（边电导）是从由初始权重 $A$ 导出的特定混合测度 $\mu_{v_0, A}$ 中抽取的。核心见解在于，轨迹 $X$ 中包含的关于 $A$ 的统计信息是通过随机环境 $W$ 进行中介的。因此，估计策略遵循两阶段逻辑：

1. 从轨迹中估计随机环境参数（电导的矩）。
2. 反演这些矩与初始权重 $A$ 之间的关系。

2.2 广义矩估计（GMM）估计量

作者没有最大化非凹的对数似然函数（这在计算上是不可行的），而是提出了基于混合测度导出的特定矩公式的广义矩估计量。

定义的关键统计量包括：

• 对于边 $e=\{i,j\}$，$U_e = P_{ij}P_{ji}$，其中 $P$ 是随机环境的转移矩阵。
• 矩，如 $\mathbb{E}[U_e]$、$\mathbb{E}[U_e U_{e'}]$，以及类协方差项 $\Delta_{e,e'} = \mathbb{E}[U_e]\mathbb{E}[U_{e'}] - \mathbb{E}[U_e U_{e'}]$。

论文推导了这些期望值关于初始权重 $A$ 和 Gamma 函数的显式闭式表达式。例如：
$$\mathbb{E}[U_e] = \frac{a_e(a_e+1)}{(a_i + 1 - \mathbb{I}_{i=v_0})(a_j + 1 - \mathbb{I}_{j=v_0})}$$
其中 $a_v = \sum_{e \ni v} a_e$。

2.3 算法过程

估计算法分两个阶段进行：

1. 矩估计（算法 2）： 从 $K$ 条轨迹中，利用局部访问计数构建转移概率的经验估计量。这些估计量用于计算 $U_e$ 和乘积 $U_e U_{e'}$ 的经验平均值。
2. 参数恢复（算法 1）： 将经验矩代入理论矩方程以解出初始权重。
   • 对于度数 $\ge 2$ 的顶点，利用二阶矩与一阶矩的比率（公式 20）求解权重 $o_j = a_j + 1 - \mathbb{I}_{j=v_0}$。
   • 对于度数为 1 的顶点，利用邻居递归恢复权重。
   • 最后，通过求解由 $U_e$ 的矩公式导出的二次方程来恢复边权重 $a_e$。

3. 主要贡献与结果

3.1 非渐近样本复杂度界

主要贡献是推导了非渐近界，即在置信度 $1-\delta$ 下，以乘性误差 $\epsilon$ 估计 $A$ 所需的样本复杂度。

为此，作者分析了 ERRW 的覆盖时间。他们利用了一个“提升”的魔法公式，将随机电导表示为独立 Gamma 场（$\beta$）和双曲高斯场（$\phi$）的函数。

• 尾部界： 他们在一般图上建立了双曲高斯场 $\phi$ 上确界的紧尾部界（定理 2.6，引理 2.12）。
• 覆盖时间界： 他们证明，以高概率，覆盖时间 $t_{cov}$ 被 $n^3 \log n \cdot (d_{max}/\delta)^{O(diam)}$ 所界定（定理 2.17）。该界对于确定确保充分探索图所需的轨迹长度 $T$ 至关重要。

3.2 主定理（定理 2.20）

本文提供了严格的保证，即如果满足以下条件，所提出的估计量可实现 $\epsilon$-乘性精度：

• 轨迹数量（$K$）： 按 $O\left( \frac{d_{max}^6}{\epsilon^2} \log \frac{n d_{max}}{\delta} \right)$ 缩放。
• 轨迹长度（$T$）： 按 $O\left( n^3 \log n \cdot \exp(O(diam)) \right)$ 缩放。
• 内部参数（$m$）： 每个状态所需的用于准确转移估计的样本数量随直径呈指数级缩放。

对于常数度图（其中 $d_{max} = O(1)$），所需的轨迹数量 $K$ 仅关于图大小 $n$ 呈对数级（$K = O(\log n)$）。然而，轨迹长度 $T$ 仍主要由覆盖时间主导，而覆盖时间取决于图直径的指数级。

3.3 单条轨迹的下界

本文严格证明，基于单条轨迹（即使是无限长度）的任何估计量都无法区分某些接近的初始权重配置。这是通过构造混合测度之间的 KL 散度为 $O(\epsilon^2)$ 的实例来展示的，这导致检验误差接近 $1/2$（随机猜测）。

4. 意义与主张

本文声称提供了首个具有理论保证的算法，用于估计边增强随机游走的参数。其意义在于：

1. 连接理论与估计： 它成功地将抽象的“魔法公式”和 RWRE 联系转化为具体、可计算的估计过程。
2. 多条轨迹的必要性： 它正式确立了由于混合测度的性质，单条轨迹学习对于 ERRW 从根本上是不可能的，这一结果与标准马尔可夫链估计形成对比。
3. 样本复杂度刻画： 它量化了独立样本数量（$K$）与每个样本长度（$T$）之间的权衡，强调对于有界度图，瓶颈是探索时间（覆盖时间）而非样本数量。

作者对其上界的紧致性保持谦逊，指出覆盖时间和样本复杂度的推导界可能通过更精细的算法得到改进，但当前结果为问题的可行性提供了坚实的理论基础。他们明确指出，正整数情况并不能从根本上缓解覆盖时间瓶颈，尽管它可能会减少所需的轨迹数量。