Beyond Degree: Rooted Motif Signatures for Latent Position Identifiability in Graphon Models¶

作者: Roland Boniface Sogan, Tabea Rebafka
主题: 非参数 / 半参数
相关性: 6/10
链接: https://arxiv.org/abs/2607.01358

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向要解决的根本问题是：在图模型（graphon） 中，如何从一张观测到的网络数据中唯一地识别出每个节点的潜在位置（latent position），从而得到一个可解释的、可估计的图模型代表元。图模型本身是非参数且非可识别的——任何保测变换都会产生等价的图模型。因此，研究者需要引入额外的结构假设来“固定”一个代表元。当前的主流做法是依赖度函数（degree function） 的严格单调性，但这在度函数为常数或非单射时完全失效。本文试图用高阶局部子图模式（rooted motif） 来替代度函数，从而在更弱的假设下实现潜在位置的可识别性。

发展脉络（history）¶

奠基工作：图模型与弱等价类（2006-2007）
- Lovász & Szegedy (2006) 和 Diaconis & Janson (2007) 建立了图模型作为稠密图序列极限对象的理论框架。他们证明了图模型只能被识别到弱等价类（weak equivalence），即两个图模型如果诱导出相同的随机图分布，则它们在割距离（cut distance） 下距离为0。这奠定了非可识别性的基础。
- Borgs et al. (2008) 进一步刻画了弱等价类，并引入了割距离的度量性质。
主要进展：度函数与排序-平滑估计（2013-2014）
- Wolfe & Olhede (2013) 和 Olhede & Wolfe (2014) 提出了非参数图模型估计的框架，并证明了在稀疏网络下的相合性。他们使用了随机块模型（SBM） 作为图模型的直方图近似。
- Chan & Airoldi (2014) 和 Yang et al. (2014) 提出了基于排序-平滑（sorting-and-smoothing） 的图模型估计器。这些方法的核心是：如果度函数严格单调，则可以根据经验度对节点排序，从而得到一个“规范”的图模型代表元。这是当前最主流的做法，但它的成功完全依赖于度函数的可识别性。
- Sogan & Rebafka (2026)（本文作者的前作）提出了一个低复杂度的多网络图模型估计器，同样依赖于度函数排序。
当前 Frontier：超越度函数（2016-2026）
- Benson et al. (2016) 在计算网络科学中提出了基于高阶模体（motif）的聚类框架，展示了局部子图模式能揭示度信息无法捕捉的网络组织结构。本文直接引用了这一工作，作为“高阶信息有用”的动机。
- Borgs et al. (2010) 研究了双变量函数的矩与图极限的唯一性，提出了通过连接轮廓（connectivity profile） 来识别潜在位置的方法，并引入了孪生（twin） 概念。本文将其作为理论起点，并试图用模体签名来“实现”这种识别。
- 本文（Sogan & Rebafka, 2026） 是第一个系统性地提出用根植模体签名（rooted motif signatures） 来替代度函数，以实现潜在位置可识别性的工作。它证明了在有限秩图模型下，合适的模体签名可以唯一确定连接轮廓，并给出了经验签名的集中界。

子线索聚类¶

图模型的理论基础与可识别性：Lovász & Szegedy (2006), Diaconis & Janson (2007), Borgs et al. (2008, 2010), Lovász (2012)。这一簇关注图模型的极限理论、弱等价类、割距离和孪生概念，为可识别性问题提供了严格的数学框架。
基于度函数的图模型估计：Chan & Airoldi (2014), Yang et al. (2014), Olhede & Wolfe (2014), Wolfe & Olhede (2013), Sogan & Rebafka (2026)。这一簇关注如何利用度函数的单调性来设计可计算的、相合的图模型估计器。这是本文试图超越的“主流”。
网络中的高阶结构：Milo et al. (2002), Alon (2007), Benson et al. (2016)。这一簇来自计算网络科学，关注模体（motif）作为网络的基本构建块，并展示了其在聚类、角色发现等任务中的价值。本文将其作为“高阶信息有用”的实证动机。
随机块模型与社区发现：Holland et al. (1983), Bickel & Chen (2009), Abbe (2018), Rohe et al. (2011), Lei & Rinaldo (2015)。这一簇是图模型的一个特例（分段常数图模型），也是本文数值实验的主要测试平台。

这个方向在追问的核心问题¶

如何在不依赖度函数单调性的前提下，实现潜在位置的可识别性？ 这是本文直接回答的问题。
什么样的“高阶”统计量（如模体密度）能唯一确定一个节点的连接轮廓？ 本文对有限秩图模型给出了一个充分条件（根植路径密度）。
对于一般的、非有限秩的图模型，模体签名能否实现可识别性？ 本文给出了一个反例（对称图模型），表明不能，并留下了一个开放问题。
如何从单张观测图中可靠地估计这些高阶模体密度，并用于下游任务（如聚类、图模型估计）？ 本文给出了经验估计量和集中界，但未将其用于图模型估计本身。

⚠️ 作者的 framing¶

作者把缺口 frame 成什么？ 作者将“度函数严格单调”这一假设定位为过于严格（restrictive），并指出它在许多常见场景（如等度SBM、度函数有平台区）下失效。因此，本文的贡献是提供了一个更宽松的替代方案——根植模体签名。作者将本文定位为“显然的下一步”，即从一阶度信息推广到高阶局部模式。
哪些竞争路线被他淡化或回避了？ 作者在引言中提到了Borgs et al. (2010)的“连接轮廓”方法，但并未深入讨论如何从数据中估计这个轮廓。实际上，Borgs et al.的方法在理论上更一般（不依赖任何特定统计量），但可能更难实现。作者通过引入一个可计算的、基于模体的签名，实际上是在“理论优雅性”和“计算可行性”之间做了一个权衡，并选择了后者。作者也回避了讨论稀疏图模型（sparse graphon）下的可识别性问题，因为本文的集中界依赖于稠密图假设（模体计数是U-统计量，其方差在稀疏下会爆炸）。
什么明显该被引 / 该存在、却没出现在 intro 里？ 作者没有引用任何关于图模型估计的minimax最优速率的工作（如Gao et al., 2015, AoS; Klopp et al., 2017, AoS）。这些工作讨论了在Sobolev或Hölder光滑性假设下，图模型估计的最优收敛速率。本文的模体签名估计器是否达到了这些最优速率？这是一个明显的、未被讨论的问题。此外，作者也没有引用图神经网络（GNN） 中关于节点表示学习的工作，尽管模体签名本质上就是一种节点特征。

张力¶

未见明显对立引用。所有被引工作基本在同一个理论框架（图模型）下，只是关注点不同（理论 vs. 估计 vs. 应用）。唯一的潜在张力在于：Borgs et al. (2010)的“连接轮廓”方法在理论上更一般，而本文的“模体签名”方法在计算上更具体。但这并非矛盾，而是互补。

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

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

符号：
- W: 图模型（graphon），一个对称可测函数 W: [0,1]^2 -> [0,1]。这是参数（非参数意义上的）。
- U_i: 节点 i 的潜在位置（latent position），独立同分布于 Unif[0,1]。这是潜在变量，不可观测。
- A_ij: 邻接矩阵（adjacency matrix）的第 (i,j) 个元素。A_ij = 1 表示节点 i 和 j 之间有边。这是可观测数据。
- n: 节点数，即样本量。
- g(u): 度函数（degree function），g(u) = ∫_0^1 W(u,v) dv。这是一阶统计量。
- (F, r): 一个根植模体（rooted motif），F 是一个简单图，r 是其中的一个特殊节点（根）。
- t((F, r), W)(u): 根植模体密度（rooted motif density），即在潜在位置 u 处，根植模体 (F, r) 出现的期望概率。这是高阶统计量。
- Φ_W(u): 根植模体签名（rooted motif signature），即所有根植模体密度的集合。这是目标 estimand。
- bΦ^F_i: 经验根植模体签名（empirical rooted motif signature），基于观测到的邻接矩阵 A 对节点 i 的签名估计。这是估计量。
- Θ(u) = (φ_1(u), ..., φ_m(u)): 有限秩图模型的谱坐标（spectral coordinates）。这是连接轮廓的等价表示。
模型：
- 数据生成机制：U_i ~ i.i.d. Unif[0,1]，然后 A_ij | U_i, U_j ~ Bernoulli(W(U_i, U_j))，且 A_ij 在给定 U 下条件独立。
- 这是一个非参数模型，因为 W 可以是任何对称可测函数。
- 本文主要关注有限秩图模型（finite-rank graphon），即 W(u,v) = Σ_{j=1}^m λ_j φ_j(u) φ_j(v)，其中 λ_j 是特征值，φ_j 是特征函数。这是一个半参数模型，因为谱坐标 Θ(u) 是有限维的。
可观测数据：
- 研究者能观测到的是邻接矩阵 A，一个 n x n 的对称0-1矩阵。
- 研究者无法观测到潜在位置 U_i，也无法直接观测到图模型 W。
- 研究者想要但观测不到的是每个节点的连接轮廓 W(U_i, ·)，或者等价地，其谱坐标 Θ(U_i)。

第二步：讲最小内核¶

本文的核心思路可以用一个最简特例来理解：一个2-块的随机块模型（SBM），且两个块有相同的期望度（equal-degree）。

设定：假设有 Q=2 个块，块比例 π = (0.5, 0.5)。连接概率矩阵为：
```
B = [[p, q],
     [q, p]]
```
其中 p ≠ q，但 p + q 是常数。这意味着块1和块2的期望度相同：g(1) = 0.5*p + 0.5*q = g(2)。
问题：在这个模型下，度函数 g(u) 是常数（对所有节点都一样）。因此，基于度函数的排序方法完全失效——它无法区分来自块1和块2的节点。然而，这两个块的连接轮廓是不同的：块1的节点更倾向于与块1的节点连接（概率 p），而块2的节点更倾向于与块2的节点连接（概率 p）。
核心想法：使用根植三角形密度（rooted triangle density）g_△(u) 来区分它们。
- 对于块1中的一个节点 u，其根植三角形密度为： g_△(1) = P(节点u与两个其他节点v, w都相连，且v和w也相连) = P(v∈块1, w∈块1) * p^3 + P(v∈块1, w∈块2) * p*q*q + P(v∈块2, w∈块1) * q*p*q + P(v∈块2, w∈块2) * q^3 = 0.25 * p^3 + 0.25 * p*q^2 + 0.25 * q*p*q + 0.25 * q^3 = 0.25 * (p^3 + 2p*q^2 + q^3)
- 对于块2中的一个节点 v，其根植三角形密度为： g_△(2) = 0.25 * (q^3 + 2q*p^2 + p^3)
- 由于 p ≠ q，g_△(1) ≠ g_△(2)。因此，根植三角形密度可以区分这两个块，而度函数不能。
推广：这个例子揭示了本文的核心数学困难：如何找到一个有限维的统计量（模体签名），使得当两个节点的度函数相同时，该统计量仍然能唯一地确定它们的连接轮廓？ 对于有限秩图模型，本文证明了一组特定的根植路径密度（rooted path densities）可以做到这一点，其证明依赖于一个Vandermonde矩阵的可逆性（见第三节证明路线）。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：本文研究了在图模型（graphon）中，如何利用根植模体签名（rooted motif signatures） 来替代传统的度函数，实现在度函数非单射（如等度SBM）情况下的潜在位置可识别性。
核心工具/方法：本文提出了根植模体签名作为节点级的高阶表示，并证明了对于有限秩图模型，一组特定的根植路径密度可以唯一确定节点的谱坐标（即连接轮廓）。在统计方面，定义了基于单张观测图的经验根植模体签名，并证明了其均匀集中界。
主要结论：对于一般的有限秩图模型，在特征值互异且特征函数与常数函数不正交的假设下，根植路径密度（P_2^•, ..., P_{m+1}^•）足以确定连接轮廓。对于任意图模型，由于对称性，该性质不成立。经验签名以 O_P(√(log n / n)) 的速率一致收敛于其总体对应量。

关键设定与假设¶

图模型：W: [0,1]^2 -> [0,1]，对称可测。这是标准设定。
有限秩图模型：W(u,v) = Σ_{j=1}^m λ_j φ_j(u) φ_j(v)，其中 λ_j 是特征值，φ_j 是 L^2[0,1] 中的标准正交基。这是本文理论结果的核心设定。
Proposition 3.5 的假设：
1. λ_i ≠ λ_j 对于所有 i ≠ j（特征值互异）。这是为了保证Vandermonde矩阵可逆。
2. ⟨1, φ_j⟩ ≠ 0 对于所有 j（特征函数与常数函数不正交）。这是为了保证对角矩阵 diag(c_1, ..., c_m) 可逆。
Theorem 4.1 的假设：
1. F 是一个固定的有限根植模体族。
2. n ≥ s_max，其中 s_max 是 F 中最大模体的顶点数。这是为了保证经验签名有定义。
3. 图模型是稠密的（W 取值在 [0,1] 之间，没有稀疏化）。这是集中界成立的关键，因为模体计数本质上是U-统计量，其方差在稠密图下是 O(1/n)。

主要结果¶

Proposition 3.5（理论核心）：对于有限秩图模型，在特征值互异且特征函数与常数函数不正交的假设下，根植路径密度 t(P_{k+1}^•, W)(u) 对于 k=1,...,m 可以唯一确定谱坐标 Θ(u) = (φ_1(u), ..., φ_m(u))。
- 直觉：t(P_{k+1}^•, W)(u) = (T_W^k 1)(u)，其中 T_W 是图模型积分算子。将 T_W 的谱分解代入，得到 t(P_{k+1}^•, W)(u) = Σ_{j=1}^m λ_j^k ⟨1, φ_j⟩ φ_j(u)。这构成了一个关于 φ_j(u) 的线性方程组，其系数矩阵是一个Vandermonde矩阵乘以一个对角矩阵。在假设下，该矩阵可逆，因此可以解出 φ_j(u)。
- 必要条件：特征值互异和 ⟨1, φ_j⟩ ≠ 0 是技术性的，但作者指出这是“generic”（一般的）条件，即不满足这些条件的图模型是“退化”的。
- 解决的技术难点：将根植路径密度与积分算子的幂联系起来，并利用谱分解将其转化为一个可解的线性系统。
Theorem 4.1（统计核心）：对于固定的有限根植模体族 F，经验根植模体签名 bΦ^F_i 以 O_P(√(log n / n)) 的速率一致收敛于其总体对应量 Φ^F_W(U_i)。
- 证明路线：将误差分解为边采样误差（edge-sampling error）和潜在采样误差（latent-sampling error）。边采样误差通过McDiarmid不等式控制，潜在采样误差通过U-统计量的集中不等式控制。最后通过Boole不等式得到一致界。
- 技术技巧：McDiarmid不等式（有界差分法）和U-统计量的Hoeffding/Arcones型不等式。

证明路线与技术技巧¶

Proposition 3.5 的证明路线：
1. 建立联系：证明根植路径密度 t(P_{k+1}^•, W)(u) 等于积分算子 T_W 的 k 次幂作用于常数函数1后在 u 处的值：(T_W^k 1)(u)。
2. 谱分解：利用有限秩图模型的谱分解 T_W f = Σ λ_j ⟨f, φ_j⟩ φ_j，迭代得到 T_W^k 1 = Σ λ_j^k ⟨1, φ_j⟩ φ_j。
3. 形成线性系统：将 k=1,...,m 的 m 个方程写成一个矩阵形式： [t(P_2^•), ..., t(P_{m+1}^•)]^T = V * diag(c_1, ..., c_m) * [φ_1, ..., φ_m]^T，其中 V 是特征值 λ_j 的Vandermonde矩阵，c_j = ⟨1, φ_j⟩。
4. 证明可逆性：由于特征值互异，Vandermonde矩阵 V 可逆。由于 c_j ≠ 0，对角矩阵可逆。因此整个系数矩阵可逆，从而可以从根植路径密度唯一解出谱坐标 φ_j(u)。
Theorem 4.1 的证明路线：
1. 分解误差：|bΦ^F_i - Φ^F_W(U_i)| ≤ |bΦ^F_i - E[bΦ^F_i | U]| + |E[bΦ^F_i | U] - Φ^F_W(U_i)|。
2. 控制边采样误差：|bΦ^F_i - E[bΦ^F_i | U]| 是在给定潜在位置 U 下，由邻接矩阵的随机性引起的。使用McDiarmid不等式，证明改变一条边对 bΦ^F_i 的影响是 O(1/n)，从而得到指数型集中界。
3. 控制潜在采样误差：|E[bΦ^F_i | U] - Φ^F_W(U_i)| 是由潜在位置 U_j (j≠i) 的随机性引起的。E[bΦ^F_i | U] 是一个以 U_i 为条件的U-统计量。使用U-统计量的集中不等式（如Hoeffding或Arcones），得到指数型集中界。
4. 联合界：对每个节点 i 和每个模体 (F_k, r_k) 应用集中界，然后通过Boole不等式得到一致界。

真实例子与应用¶

本文包含模拟实验，没有真实数据例子。

实验1：随机块模型（SBM）：
- 数据：生成了6种不同的SBM，包括等度块（equal-degree-3）、角色块（role-3）等，这些模型是度函数无法区分的。
- 方法：对每个节点计算经验根植模体签名（包括度、三角形、4-环、钻石、K4、爪、蝴蝶、5-环、K5、路径等），然后进行PCA降维到2维进行可视化。
- 结果：在度函数表示下，不同块的节点严重重叠。而在模体签名的PCA投影下，不同块的节点形成了清晰可分的簇。这验证了模体签名能捕捉度函数无法捕捉的块结构差异。
- 想说明什么：验证了本文的核心论点——高阶模体信息可以揭示度信息无法揭示的潜在结构。
实验2：连续图模型（Continuous graphon）：
- 数据：设计了一个有限秩图模型 W_1，其度函数在中间区域有一个“平台区”（plateau），即度函数变化很小。
- 方法：计算了该图模型下各种根植模体密度的总体曲线。
- 结果：在度函数的平台区内，许多高阶模体密度（如三角形、4-环、钻石等）仍然有显著的变化。这表明，即使度函数无法区分这些潜在位置，高阶模体签名仍然可以。
- 想说明什么：验证了模体签名在连续图模型场景下也能提供超越度函数的信息。

🔎 结论是否比证明窄¶

Proposition 3.5 的结论是“根植路径密度确定谱坐标”，但作者在Remark 3.6中明确指出：“This result should not be interpreted as saying that rooted paths are the only informative motifs.” 这是一个诚实的限定。然而，在数值实验中，作者使用的模体族 F 远不止路径，还包括三角形、环、团等。因此，论文的实证部分（实验1和2）的结论比理论证明的结论更宽泛——理论只保证了路径的有效性，但实验表明其他模体也有效。作者没有证明为什么这些其他模体也有效，也没有给出一个选择最优模体族的理论指导。
Theorem 4.1 的结论是经验签名以 O_P(√(log n / n)) 的速率一致收敛。这个速率是次优的。对于稠密图模型，度函数（即 K_2^• 的签名）的估计速率是 O_P(1/√n)（因为它是样本均值的标准差）。而本文的速率多了一个 √(log n) 因子，这是由一致界（max over i）带来的。对于更高阶的模体，其U-统计量的方差可能更大，但本文的集中界只依赖于模体的顶点数，没有给出更精细的方差分析。因此，这个速率可能不是最优的，且没有考虑不同模体之间的相关性。

四、开放问题¶

一般图模型下的可识别性：本文证明了对于有限秩图模型，模体签名可以确定连接轮廓。但对于一般图模型，存在对称性导致签名无法区分。作者在Section 3.2末尾留下了一个开放问题：如果 Φ_W(u) = Φ_W(v)，是否意味着 u 和 v 可以通过一个保持 W 不变的保测变换联系起来？（扎根于论文第18页：“We leave this question open.”）
模体族的选择与权重学习：本文的数值实验使用了一个手工挑选的模体族 F。如何根据数据自适应地选择最“有信息量”的模体族？如何学习不同模体的权重 w_k 以最大化下游任务（如聚类、图模型估计）的性能？（扎根于论文第19页：“an important practical question is how to select the motif family and possibly learn motif weights”）
模体签名在图模型估计中的应用：本文只将模体签名用于可视化（PCA），没有将其用于图模型估计本身。一个直接的问题是：能否用模体签名诱导的距离 d_{F,w} 来设计一个基于邻域平滑（neighborhood smoothing） 或最近邻（nearest-neighbor） 的图模型估计器？这个估计器的收敛速率是多少？是否优于基于度函数的估计器？（扎根于论文第19页：“Another is to use motif-induced distances in graphon estimation procedures based on smoothing, nearest-neighbor averaging, or local aggregation.”）
稀疏图模型下的表现：本文的所有理论（集中界）都依赖于稠密图假设（W 取值在 [0,1]）。在稀疏图模型（W 乘以一个稀疏因子 ρ_n → 0）下，模体计数的方差会爆炸。如何将本文的框架推广到稀疏图？是否存在一个“稀疏模体签名”的概念？（这是一个明显的、未被本文讨论的延伸，但可以从“稀疏图模型”的文献中找到动机。）

Maintained by 陈星宇 · Homepage · Source on GitHub