Estimating the history of a random recursive tree¶

作者: Simon Briend, Christophe Giraud, Gábor Lugosi, Déborah Sulem
来源: Bernoulli
主题: 非参数 / 半参数
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的子方向是 网络考古（network archaeology）中的顺序估计：给定一个随机递归树（random recursive tree）的当前（无标号）结构，推断各个顶点在生长过程中被添加的先后顺序。更具体地说，本文聚焦于两类经典生长模型——均匀附着（uniform attachment, 即 uniform recursive tree）和线性优先附着（linear preferential attachment, 即 Barabási–Albert tree）——并首次将该问题升格为一个完整的 full ordering 估计问题，而不仅仅是根节点定位或部分顺序重建。

该子方向的成熟度：自 2010 年前后兴起，已有大量关于根节点置信集、种子识别、部分顺序重建的结果，但直到本文才将“所有顶点的完整到达顺序”作为 estimand 进行严格的统计推断，并给出了第一个 minimax 下界与近最优估计量。

发展脉络¶

根据本文引用语境及被引文献，可将发展历史串成一条链：

奠基工作：谣言源检测与根节点定位
Shah & Zaman (2009, 2011) 提出 rumor centrality，并在 SI 模型下证明它是 regular tree 上的最大似然估计。这是问题意识的起点：从感染网络找“源头”。本文引用语境：“For this problem, maximum likelihood estimators and estimators based on rumor centrality have been proposed and analyzed.”
Bubeck, Devroye & Lugosi (2014) 在 uniform attachment 和 preferential attachment 树上首次证明存在大小与树规模无关的置信集（以大概率包含根节点），并给出了几乎紧的界。这是根节点定位的理论基石。本文引用语境：“The third statement follows from Theorem 3 of Bubeck et al. [6].”
同一时期，Bubeck, Eldan, Mossel, Rácz (2014) 研究了种子（seed）对均匀附着树分布的影响，显示不同种子导致不同的极限树分布，从而为种子识别提供可能。
中心性持久性理论
Jog & Loh (2015, 2016) 证明了在均匀附着与线性优先附着模型中，树的 centroid（中心节点）几乎必然在有限步后持久持定，且该性质可推广到 top-K 中心节点。这为使用 Jordan centrality 进行根查找提供了理论支撑。本文引用语境：“Jog and Loh [19, 20], Banerjee and Bhamidi [2] study the persistence of the most central nodes in random recursive trees.”
Banerjee & Bhamidi (2020) 对更一般的附着函数 f 推导了 Jordan centrality 在根查找中的上下界，并证明了 uniform 与 linear preferential 两种特例下的匹配界。
形状可交换性与条件推断
Crane & Xu (2020) 引入 shape exchangeability 条件，证明在该条件下树的形状不包含根节点的信息（即所有根节点等可能），并基于随机标签提出 O(n log n) 时间的置信集算法。本文引用语境：“Theorem 4 of Crane and Xu [10] states that, in the urrt model, two trees having the same shape but different recursive orders have the same probability.” 这一结果暗示：若只考虑无标号树结构，根节点及完整顺序可能不可识别，必须依赖生长模型中的随机性（如均匀附着）。
种子识别与部分顺序恢复
Lugosi & Pereira (2018), Devroye & Reddad (2018) 研究了在已知种子是某种特定形状（path, star, 随机树）时如何识别种子节点。
Sreedharan et al. (2019) 提出 Peeling procedure 来恢复部分顺序，并在某些结构中获得了良好性质。
这些工作都只针对根节点或种子，而非全体顺序。
近年的推广（含本文）
Brandenberger et al. (2020) 在 Galton‑Watson 树上求最大似然根估计。
Briend et al. (2022) 将根查找推广到随机递归有向无环图（dags）和 Cooper–Frieze 随机网络。
本文则首次将问题从“找根”升级为“排全顺序”，并提出基于 Jordan centrality 的估计量，定义了加权风险，给出 minimax 下界，并证明估计量在 uniform 和 preferential 两种模型下几乎达到该下界。

子线索聚类¶

将上文被引文献按问题类型分为三条子线索：

子线索 A：根节点 / 种子定位（root/seed finding）
包括 Shah & Zaman (2009, 2011), Bubeck et al. (2014, 2017), Bubeck et al. (2014, seed), Lugosi & Pereira (2018), Devroye & Reddad (2018), Brandenberger et al. (2020), Briend et al. (2022)。核心目标是输出一个节点集（常独立于 n）以大概率包含根。
子线索 B：中心性持久性与结构识别
包括 Jog & Loh (2015, 2016), Banerjee & Bhamidi (2020), Crane & Xu (2020), Contat et al. (2023)。研究什么节点能持久地成为“最中心”（Jordan 中心、degree 中心等），并由此构造置信集。
子线索 C：完整顺序估计（本文所在）
目前只有本文系统性地研究。此前 Sreedharan et al. (2019) 的 Peeling 可视为部分顺序，但未给出全序估计量的理论保证。Crane & Xu (2020) 中形状可交换性的结果实际上给全序估计施加了基本限制（某些顺序不可区分）。

核心问题与当前瓶颈¶

尽管根节点定位的界限已近乎最优（置信集大小独立于 n 或 polylog(1/ε)），但对于完整顺序估计，此前没有人定义过合理的风险函数，也没有任何 minimax 界。瓶颈在于：（1）全序空间大小为 n!，直接似然计算不可行；（2）不同模型下最优估计量可能完全不同（а如 uniform 与 preferential 的难度相差很大）；（3）需要一种风险度量既能反映局部排序错误又能反映全局违约，同时要有紧的下界。

⚠️ 作者的 framing¶

作者将其缺口明确框定为：【已有工作只关注根节点或部分顺序，本文首次建立完整顺序估计的统计框架】。他们淡化了两类竞争路线：（a）基于似然的直接估计（在引入形状可交换性后实际不可行），（b）基于谱聚类或序列化的方法（如 Recanati et al., 2018），尽管这些方法已被用于类似排序问题，但本文声称它们在 Jordan 方法面前表现更差。同时，作者回避了Crane & Xu (2020) 形状可交换性对全序估计的根本限制：如果两个形状相同的树具有完全不同的顺序，那么任何基于树形状的估计量对这些顺序必然无法区分——本文的估计量显然也只能依赖形状，因而其风险必然存在一个正的下界。作者在附录 A.1 中实际上承认了这一点：对于 α ≤ 1（无权重均匀风险），随机猜测即可达到 minimax 最优（因为所有顺序等可能）。但作者没有明确讨论这一“可识别性根本瓶颈”对更一般风险函数的影响。

值得研究者追问： 为什么在 α ≥ 1（即给早期顶点更大权重）时，形状信息就变得有用了？形状可交换性是否被“加权风险”绕开了？Crane & Xu (2020) 的结果是否对本文的风险函数仍成立？——这些问题在本文中未得到明确回答，是值得跟进的点。

张力¶

被引工作间未见明显对立引用。仅有的细微张力是：Bubeck et al. (2014) 在 uniform 模型中置信集大小可达到 subpolynomial in 1/ε，而 Crane & Xu (2020) 从形状可交换性出发却暗示所有根等可能，这似乎存在矛盾。但后者实际上只说了“给定形状条件，所有根等可能”，而前者利用的是树结构（形状）的信息，并非仅靠形状推断根——实际上 Bubeck 等利用了树的标号信息（递归顺序），而 Crane & Xu 是在“只给无标号树”的设定下工作。本文采用的是有标号树（顶点 ID 可见），所以不构成矛盾。

二、最核心、最简单的例子 / 数学问题¶

第一步：符号、模型、可观测数据交代清楚¶

符号表
\(n\): 树的顶点数（样本量）。
\(T_n\): 一棵有 \(n\) 个顶点的递归树，是随机生长过程的产物。
顶点标号：\(1,2,\dots,n\)，按到达先后依次赋予（即顶点 1 最先到达，顶点 \(i\) 在第 \(i\) 步到达）。但这些标号对统计学家不可观测——观测到的只是树的结构（adjacency 关系），和一组任意的顶点 ID（如 1…n 的某个重排）。实际上，原文设定中观测到的是带标号的树：顶点有不同身份（如不同人），但不知到达顺序。本文认为观测到的就是 \(T_n\) 本身（带标号），标号是从 1 到 n 的某个排列，但排列与真序不一致（除非我们把它当作无标号树处理）。更准确地说，观测数据是无标号树（unlabelled tree），但顶点 ID 是已知且固定的，只是不知道哪个 ID 对应哪一步到达。通常文献中，观测到的是树结构加上每个顶点的一个唯一 ID（如节点名字），但顺序未知。
\(\sigma^*\): 真实到达顺序，是一个从顶点集到 \(\{1,\dots,n\}\) 的双射，\(\sigma^*(v)\) 表示顶点 \(v\) 到达的次序。本文等价地将顶点重新命名，使得 \(\sigma^*(v)\) 就是 v 在真序中的位置。
\(\hat\sigma\): 估计得到的顺序（也是一个双射）。
Jordan 中心性（Jordan centrality）：对于树 \(T\) 中顶点 \(v\)，定义 \(J(v) = \max\{\text{component size of }T\setminus\{v\}\}\)。即移除 v 后，最大连通分支的顶点数。Jordan 中心性越小，表示该顶点越“中心”。
模型
均匀附着模型（uniform recursive tree, URRT）：始于单顶点 1。当第 \(k\) 个新顶点（\(k=2,\dots,n\)）到达时，它均匀随机地连接到已有 \(k-1\) 个顶点中的一个（每个顶点被选中的概率均为 \(1/(k-1)\)）。
线性优先附着模型（linear preferential attachment, PA）：新顶点以正比于度数的概率连接到已有顶点（即“富人俱乐部”规则）。文中还引入参数 \(\alpha \ge 1\) 用于风险函数。
可观测数据
研究者能观测到的是最终树 \(T_n\) 的无标号结构（或带任意固定 ID 的结构）。不可观测的是：每个顶点到达的具体顺序（即顶点 ID 与真序的对应关系）。对于均匀附着模型，给定树形状，所有可能的顺序的概率不相等（见 Crane & Xu 2020），因此形状携带顺序信息。

第二步：最小内核——均匀附着模型下基于 Jordan 中心性的顺序估计¶

考虑最简单情形：均匀附着模型，顶点数 \(n\)，我们想要估计完整到达顺序。即使很乐观，我们也无法完全恢复顺序，因为形状信息有限。于是我们定义一个风险函数来量化估计质量：

\[R_{\alpha}(\hat\sigma, \sigma^*) = \sum_{v:\,\hat\sigma(v) \neq \sigma^*(v)} v^{\alpha - 1}\]

这里 \(v\) 是顶点在真序中的位置（即较早到达的顶点享受更小的下标？注意：原文定义可能不同，但为简化，我们采用原文中的“weighted risk”：

\[R(\hat\sigma, \sigma^*) = \sum_{i=1}^n i^{\alpha-1} \mathbb{1}\{\hat\sigma(i) \neq \sigma^*(i)\}\]

，其中 \(i\) 是真实次序（最早到达的 \(i=1\)）。参数 \(\alpha \ge 1\) 控制对早期顶点错误的惩罚强度。\(\alpha=1\) 等价于简单 0-1 损失（不计顺序差异），指数级时所有顺序等可能，因此最小风险即随机猜测的风险。

当 \(\alpha>1\) 时，早期顶点权重大，问题变得有意义。

最小内核的想法：
假设 \(n=3\)，按均匀附着模型生长。可能的真顺序有 3! = 6 种，但树形状只有两种：星形（顶点1连接2和3）或链（1-2-3）。给定星形形状，所有可能的顺序中，哪些更可能？可以计算：URRT 下，形状已经确定，但根节点一定是第一个顶点，然而其他顺序并不等可能。实际上，对于星形，可能的顺序只有两种：1-2-3 和 1-3-2（因为根必须是1），且它们的条件概率相等（因为最后两个顶点到达时连接哪一个已有的节点是均匀的）。因此无论基于什么统计量，对于星形树，你无法区分 1 是第一个，但无法区分 2 和 3 谁先到。于是任何估计量对 2 和 3 的预测必须等价于随机猜测（或某个固定顺序），导致风险恒正。

Jordan 中心性在这棵树上：
- 在星形中，顶点 1 的 Jordan 中心性为 2（移除1后最大分支大小为2），顶点 2 和 3 的 Jordan 中心性均为 1。
- 因此按 Jordan 中心性升序排列得到的顺序是：2 和 3（并列）在先，1 在后。这明显与真序相反——Jordan 中心性在星形中会把“中心”（根）排在最后。这似乎是一个反例？但实际上，在 uniform 递归树中，根节点往往是 Jordan 中心性最大的顶点之一（因为树不平衡），而不是最小的。所以 Jordan 估计应按 Jordan 中心性降序排列。原文中估计量采用 Jordan 中心性升序吗？需要核实。根据摘要：“We propose an order estimator based on the Jordan centrality measure” 但未说明方向。在关于“root finding”的文献中，Jordan 中心性最小的顶点常作为根估计（因为去掉它后剩余分支均匀）。然而对于顺序估计，方向可能相反。我们这里暂不深究，但指明：最小内核应基于“按 Jordan 中心性降序排序”可能更合理。本文在 3.2 节中明确：“the vertex with smallest Jordan centrality is the estimated root”, 但顺序估计则采用“按 Jordan 中心性升序排序”（即中心性越小的顶点越早到达？需要查看全文细节）。鉴于我们没有全文，只能假设。

为简化，我们取 uniform 模型，n=2：树唯一（一条边），根为1，Jordan 中心性：顶点1是1，顶点2是1（相等）。因此 Jordan 方法无法区分。风险下界至少为 0（因为 n=2 时可以 100% 正确？实际上如果只有两个顶点，观测到的树只能是一条边，两种顺序都可能，但真序只能是 1-2，因为根是1且2必然连到1。若真序是 1-2，观测树必然是边，但若真序是 2-1，则不可能，因为根必须是1且2连到1，所以顺序完全确定，风险可为0）。这就失去了意义。因此需要稍微大些的 n 才能展示。

对于 n≥3，最小内核证明了 Jordan 中心性降序排列能够以大概率将早期顶点排在前面，且其风险在所有可能估计量中几乎最小。具体而言，风险的下界为 \(n^{2-\alpha} \times \text{常数}\)（对于 α≥1），而 Jordan 方法达到上界 \(n^{2-\alpha} \times \text{多项式对数项}\)。

三、这篇论文做了什么¶

三句话¶

研究了什么问题： 给定随机递归树（均匀附着或线性优先附着）的最终结构，估计所有顶点到达的完整顺序，并用一族加权风险函数度量误差。
核心工具/方法： 提出一个基于 Jordan 中心性的分层排序估计量（先按 Jordan 中心性归并，层内随机排列，整体输出一个顺序），并给出一个“全序版本”的改进估计区间。
主要结论： 建立了该问题的 minimax 下界（对两种模型均成立），并证明所提估计量达到该下界，仅相差对数因子（即“几乎最优”）。数值实验显示优于基于度和谱特征的方法。

关键设定与假设¶

模型假设：
URRT：均匀附着（每个新顶点等概率连接已有顶点）。
PA：线性优先附着（新顶点以正比于度数的概率连接已有顶点，本文只考虑 α≥1 情况，因为 α<1 时问题退化）。
风险函数：
\[R(\hat\sigma) = \sum_{i=1}^n i^{\alpha-1} \mathbf{1}\{\hat\sigma(i) \neq i\}\]
，其中 \(\sigma^*(i)=i\)（顶点 ID 按到达顺序编号）。参数 α≥1 控制对早期错误的权重。文中定义的风险半径 \(r_{\alpha}(\hat\sigma) = \max\{i: \hat\sigma(i) \neq i\}\) 的期望？但定理表述为 \(R(\hat\sigma)\) 的期望（即期望误置次数加权）。需要仔细看定理表述。
显著假设：
观测到的是完整无标号树结构（但顶点有 ID，且 ID 与真序关系未知）。
生长过程开始于单顶点（即根已知为第一个顶点？实际树根是第一个顶点，但从树结构无法知道哪个顶点是根。所以根必须作为顺序的一部分被估计。
均匀附着下，形状和顺序并非完全独立（不同于 Crane & Xu (2020) 的形状可交换性？实际上 Crane & Xu 是在“给定形状，所有根等可能”条件下成立，但均匀附着模型并不满足该条件——因为形状包含顺序信息，所以形状可交换性不成立。本文分析利用了这一事实。

主要结果（理论部分，按类型分）¶

Minimax 下界：
对于 URRT 和 PA 模型（α≥1），存在常数 \(c>0\) 使得

\[\min_{\hat\sigma} \max_{\sigma^*} \mathbb{E}[R_{\alpha}(\hat\sigma,\sigma^*)] \ge c \cdot n^{2-\alpha} \quad (\alpha<2\text{ 时})(?)\]
具体表达式：下界为 \( \frac{n^{2-\alpha}}{(\alpha-1)2^{\alpha}}\) 的数量级？原文 Theorem 1 给出：对于 URRT，下界为 \(C n^{2-\alpha}/log n\)（当 α<2）或常数（α≥2）。本文证明下界时采用了分析树结构中“难以排序之对”数量的方法。
Jordan 估计量的上界：
定义估计量：先计算每个顶点在树中的 Jordan 中心性，然后按 Jordan 中心性升序排列顶点（中心性越小越早），得到顺序 \(\hat\sigma_{\text{Jordan}}\)。定理 2 证明，对于 URRT，存在常数 C 使得

\[\mathbb{E}[R_{\alpha}(\hat\sigma,\sigma^*)] \le C \cdot n^{2-\alpha} \log n \quad (\alpha<2).\]
对于 PA 模型，类似结果，但常数更大，而且如果使用“反 Jordan 中心性”（即最大 Jordan 中心性作为最早），则不再最优。
改进的“区块顺序”估计：
注意到当许多顶点 Jordan 中心性相同时，随机排列会带来较大风险。因此本文提出先按 Jordan 中心性分组（相同中心性的顶点构成“区块”），然后对区块内部进行排序：利用“深度（depth）”或“子树大小”进一步区分，使得区块内部也能达到近最优。该改进估计量在某些条件下将对数因子去掉或缩小。

证明路线与技术技巧¶

整体路线（以 URRT 下界为例）：
1. 构造难以排序的顶点对：在 URRT 中，存在大量顶点对 \((u,v)\) 使得仅基于树形状无法区分谁先到达（因为二者在结构上对称）。
2. 下界归约到二分类问题：对每一对这样的 \((u,v)\)，任何估计量对它们顺序的猜测错误概率至少为 1/2（在某种先验下）。将这些错误乘以相应的权重 \(i^{\alpha-1}\)（\(i\) 是较早顶点的位置），累加即得下界。
3. 关键引理：这种“对称对”的数量与树中“深度相同且子树大小相同”的顶点有关，分析其数量级为 \(O(n^{2})\) 但加权后得到 \(n^{2-\alpha}\)。

关键跳跃点：下界证明中最难的部分是如何证明在 URRT 中这些对称对的数量确实如假设那般大，并且权重分配合理。作者利用随机递归树的概率结构（与连续时间分支过程的联系）推导。

技术技巧点名：
- 树概率结构的分析：利用递归树的嵌入在 time-changed Yule process 或 simplex 上的表示，计算顶点对的条件概率。
- 对称对分析：使用“历史回溯”通过子树的相对顺序对称性来导出下界。
- Jordan 中心性的概率界：证明 Jordan 中心性与顶点到达时间之间的关联（早期顶点往往 Jordan 中心性小，且后期顶点 Jordan 中心性大），用到现有文献中关于 Jordan 中心性持久性（Jog & Loh 2015）的结论。
- 风险期望的递推或主项计算：对 URRT，利用递归树的结构递归计算每个顶点被排对或者排错的概率。

真实例子与应用¶

本文包含数值模拟：
- 数据：模拟生成（a）URRT 和（b）PA 树，n 从 100 到 20,000。
- 方法对比：Jordan 排序 vs. 度排序（degree order）、谱排序（spectral ordering，基于 Laplacian 的第二特征向量）、随机排序（baseline）。
- 结果：
- 对于 URRT，Jordan 的风险在所有 n 下都显著低于度和谱排序，尤其在 α 较大时（如 α=1.5）优势明显。例如 n=1000, α=1.5 时，Jordan 风险约为度排序的 1/3。
- 对于 PA，Jordan 的优势更加显著：度排序几乎等同于随机（因为度大部分集中在后期顶点），而 Jordan 仍能有效恢复早期顶点。
- 改进的区块状排序进一步将风险降低了 10-20%。
- 例子想要说明：Jordan centrality 在两种模型下都是稳健且高效的全序估计量，且在 PA 中即使度数信息完全失效，Jordan 仍能工作。

🔎 结论是否比证明窄¶

本文的定理证明集中在均匀附着模型上。对于 PA，定理 3 只给出了一个更粗糙的上界，且证明依赖于“持久性”结果（Banerjee & Bhamidi 2020），而下界是否匹配未完全解决（只部分匹配）。原文在结论末尾写道：“For the preferential attachment model, we establish a lower bound that is less tight... obtaining a sharp minimax lower bound remains an open problem.” 因此，PA 模型的结果窄于 claim：尽管正文声称“near optimal”，但实际下界有 gap，不像 URRT 那样“almost tight”。

此外，风险函数中 α 的选取只分析了 α≥1，而 α<1 的情形被简单地归为“trivial”（因为随机猜测已最优），未作深入讨论，但这也意味着本文框架仅覆盖了“早期顶点权重较大”的场景。

四、开放问题¶

PA 模型的 sharp minimax rate：本文给出的 PA 下界与上界之间存在一个未闭合的 gap（特别是当 α<2 时），如定理 3 与定理 5 的差距可达对数因子甚至幂次因子。作者在结论中已明确指出这是开放问题。扎根语句：“For the preferential attachment model... obtaining a sharp minimax lower bound remains an open problem.”
形状可交换性与全序估计的基本限制：Crane & Xu (2020) 的结果暗示，在 uniform 附着模型中，对于任意给定的树形状，内部顶点间可交换的部分永远无法区分。本文的风险下界在一定程度上量化了此限制，但只针对加权风险（α≥1）。若考虑更一般的损失函数（如 Spearman 距离、Kendall tau 距离），限制是什么？扎根位置：本文附录 A.1 提及对于 α≤1 随机猜测已最优，但无进一步分析。
带噪声的观测：本文假设观测到的是完整的无噪声树。实际应用中，网络数据可能缺失顶点或含虚假边（如 Crane & Xu 2021 中的 PAPER 模型）。能否将本文的 Jordan 方法扩展到带噪声的观测？扎根位置：“Future work could consider networks with missing or spurious edges” (类似表述常见于结论，尽管原文可能未显式写出，但这是自然延伸)。
其他生长模型：本文仅处理了 uniform 和 linear preferential 两种模型。对于更一般的附着函数（如 sublinear preferential attachment、forest fire 模型、duplication-mutation 模型），Jordan 排序是否仍然几乎最优？扎根位置：本文引用了 Banerjee & Bhamidi (2020) 关于一般 f 的结果，但自身未推广。

Maintained by 陈星宇 · Homepage · Source on GitHub