跳到正文
返回论文列表
stat.ML提交于 已译

潜在结构块模型中的有界阶非可识别性:闭式纤维

Bounded-Order Non-Identifiability in Latent Structure Block Models: The Fiber in Closed Form

Sie Hendrata Dharmawan · Peter Chin

中文摘要

图核(graphon)由所有同态密度决定,但基于模体(motif)的方法只使用有限多个。本文在一个自然族中精确计算了这种截断的代价:位置位于K条射线上的潜在结构块模型,等价于秩为二的度修正块模型。对于给定的径向律,在所有顶点数少于2K-1的图上一致的配置构成一个一维纤维,我们给出了其闭式表达式及显式端点;友谊图(friendship graph) F_{K-1} 是其唯一的边最小分离器,因此没有固定的模体阶数适用于所有K。分离信号被抑制了至多 m_1^{2(K-1)} 倍,其中 m_1 是均方斜率,在 K=4 时约为 10^{-4}:从模体计数中检测它需要单个图中约 10^{15} 个节点,无论边密度如何。信息仍然在图中;纤维属于统计量,而非模型。常见的谱方法流程不计数模体,在普通密度下仍沿纤维滑动超过其长度的三分之一,置信区域几乎从不包含真值,而相同嵌入的基于模型的拟合则不会。我们为实践者提供了四项检查:拟合是否有风险、应改用什么方法、为什么置信区间不会警告、以及剩余模糊性有多宽。

关键要点

  1. 01问题:模体方法使用有限阶同态密度,截断导致潜在结构块模型出现一维非可识别纤维。
  2. 02方法:对K射线潜在结构块模型,给出纤维的闭式表达式,并证明友谊图F_{K-1}是唯一边最小分离器。
  3. 03结果:分离信号被抑制至多m_1^{2(K-1)}倍,K=4时约10^{-4},检测需约10^{15}节点。
  4. 04局限:谱方法流程沿纤维滑动超过三分之一长度,置信区域几乎不包含真值。

解读

1. 问题与价值

这篇论文解决的具体问题是:在“用有限阶 motif 计数来概括网络”的方法中,截断到底会丢掉多少信息。论文不是泛泛讨论图表示学习,而是在一个可精确计算的模型族里给出答案:latent structure block model,简称 LSBM,等价于 rank-two degree-corrected stochastic block model,简称 DCSBM。这个模型族的 latent positions 落在从原点出发的 K 条射线上,社区决定射线斜率,节点半径决定沿射线的位置。

论文的核心结论是:对于固定的径向分布 R,如果只统计顶点数少于 2K−1 的所有图,即只统计阶数不超过 2K−2 的 motif,那么存在一整个一维连续集合,称为 fiber,其中所有配置在这些 motif 密度上完全相同。只有达到 2K−1 个顶点的特定图,尤其是 friendship graph F_{K−1},才能区分 fiber 上的不同点。由于这个阈值随 K 增长,不存在一个固定 motif 阶数能适用于所有 K。

为什么重要:motif counts、graphlet kernels、subgraph densities 长期被用作网络摘要;谱聚类管道也常被用来从网络估计社区比例、斜率、连接矩阵等参数。论文指出两类风险。第一,有限阶 motif 统计量本身有可精确刻画的盲区,不是“估计误差大一点”的问题,而是存在连续多解。第二,即使谱管道完全不数 motif,它们仍可能沿着同一个 fiber 滑动:估计很稳定,置信区间很窄,但参数落在错误位置。

受益者包括三类角色。研究团队可以获得一个可检验的非可识别性定理和闭式 fiber,用来判断自己的 motif 统计量是否足够。应用开发者可以把论文给出的四项检查嵌入网络分析工具,在输出社区比例或连接矩阵参数前判断是否处于高风险区域。普通用户如果依赖网络分析工具查看“社区大小”“节点重要性”“图结构摘要”,其收益是避免把统计噪声之外的系统性偏差误读成真实结构。

2. 已有工作的不足

在它之前,最接近的已有做法有几类。

  1. 图极限理论已经说明:graphon 被所有有限图的 homomorphism densities 决定。Lovász 和 Szegedy、Borgs 等、Diaconis 和 Janson 的工作建立了这一基础。但这只是“全部密度足够”的存在性陈述,没有告诉使用者:如果只数到某个有限阶,具体会留下多大的非唯一集合。
  1. 逆计数引理给出了从低阶密度控制 cut distance 的速率,约为 O(1/√log k)。这说明低阶密度虽然理论上可以逼近,但条件很差。不足在于:它没有在一个自然模型族里给出精确 fiber,也没有给出最小 breaker motif 和信号抑制量级。
  1. Bickel、Chen 和 Levina 的矩方法使用 wheel densities 识别 SBM 参数,条件是 π, Fπ, …, F^{K−1}π 线性无关。这个条件排除了各块期望度数相等的情形。LSBM/DCSBM 的对称射线模型正好落在类似被排除的区域:wheel densities 只依赖径向分布,无法识别斜率方向。不足在于:它没有给出这一退化情形下 motif 截断的完整几何。
  1. 谱方法方面,SCORE、row-normalized spectral clustering、spherical coordinates with GMM 等 DCSBM 管道有社区标签一致性保证。不足在于:这些保证针对的是“把节点分到正确社区”,不是“从簇中读出的斜率、权重、连接矩阵参数是否准确”。论文关注的正是后者。
  1. Message-passing graph neural networks 的表达力受 1-WL 限制,Böker 等已说明图on 极限下消息传递等价于 tree densities。不足在于:已有表达力结果没有量化“在 LSBM/DCSBM 中,tree densities 对斜率完全失明”这一具体后果,也没有把这种失明与有限阶 motif census 的 fiber 联系起来。
  1. 矩问题工具是经典的,包括 truncated Stieltjes problem、Hankel 矩阵、Jacobi 矩阵、Gauss–Radau rules。不足在于:此前没有把 motif matching 精确归约为这个截断矩问题,并给出闭式 fiber、端点、breaker graph 和检测成本。

3. 重建作者的思考路径

从旧方法出发,可以这样推演。

第一步,旧方法是数 motif。既然 graphon 被所有有限图密度决定,那么实际方法只数小图,例如三角形、4-cycle、5-cycle、6-vertex graphlets。一个自然问题是:少数高阶 motif,到底会混淆哪些模型?如果只是“高阶项小”,那可以估计误差;但如果存在连续多解,问题就更严重。

第二步,进入一个足够简单的模型族。LSBM/DCSBM 的对称射线结构让 edge probability 写成 x_u x_v(1+s_u s_v)。如果斜率分布关于 0 对称,奇数斜率矩为零;如果所有社区共享同一个径向分布 R,半径部分会乘性分离。于是每个 motif 密度变成径向矩和斜率矩的多项式。此时 motif matching 不再是图论问题,而变成“哪些斜率分布共享若干阶矩”的问题。

第三步,尝试用已知识别工具。SBM 文献中 wheel densities 能识别参数,但需要某些线性无关条件。对称共享径向律的模型可能让所有 wheel densities 只依赖 R,因此 wheel 路线撞墙。矛盾是:模型参数明明不同,motif 密度却可能完全一样。下一步必须放弃“找几个特殊 motif 就够了”的想法,转而刻画整个等价类。

第四步,转向矩问题。给定 m_0,…,m_{K−2},可以构造 Hankel 矩阵。经典矩问题会给出 Jacobi 矩阵或三对角矩阵。此时可能出现一个关键分叉:如果数据只填到某个阶,矩矩阵的移位矩阵可能有一个自由角落。这个自由角落对应一个未匹配矩,例如 m_{K−1}。沿着这个自由参数变化,所有低阶矩不变,但高阶矩变化。这就自然导向一维 fiber。

第五步,检查 fiber 是否真的存在,而不是只是代数巧合。需要验证三点:不同自由参数是否给出不同配置;配置是否满足概率约束,例如权重为正、边概率在 [0,1];低阶 motif 是否真的全部匹配。这里会撞上 admissibility 端点问题:自由参数不能无限变化,否则斜率太大或权重变负。端点可能对应 Gauss–Radau 或 Gauss quadrature rules。

第六步,问“哪个最小图能打破盲区”。既然 fiber 上的点匹配 m_0,…,m_{K−2},需要找一个 motif 能读到 m_{K−1}。直觉上,图必须足够“深”,让某个顶点在偶子图中达到足够高的度数。于是 friendship graph F_{K−1} 出现:多个三角形共享一个中心,中心在偶子图中可以有很高偶度数。若只按顶点数看,它刚好在 2K−1 个顶点;若按最大度数看,低阶图全部失明。这里会出现一个修正:阻碍不是图的大小,而是某个 combinatorial slope index。

第七步,问“能不能检测这个差异”。虽然 m_{K−1} 差异可能很大,但 friendship density 的差异被低阶矩的幂次抑制。若 m_1 较小,信号会被压到极小。于是需要外推样本量。这里会撞上现实矛盾:单图节点数需要大到不现实,而稀疏化不一定帮助,因为相对分离可能随尺度不变。

第八步,问“信息是否真的不存在”。如果整个图分布能识别,那么问题不在 graph,而在 statistic。模型拟合若保留完整噪声几何,应能沿 fiber 定位。此时谱管道成为意外对象:它们不数 motif,却仍可能沿 fiber 滑动。为什么会这样?因为 ASE 嵌入本身一致,但“把每个节点压缩成一个方向、再聚类、再读参数”的 summary 引入了二阶偏差。这个偏差在 fiber 方向没有阻力,因此被放大成 O(1) 位移。

第九步,检查置信区间是否会报警。传统区间估计方差,假设渐近无偏。如果误差主要是 bias,且 bias 沿 fiber 滑动,区间会非常窄却完全错过真值。于是需要给出 practitioner checks,而不是只给理论。

与论文实际路径的差异:上述推演把 wheel 密度失败作为重要分叉,并把谱管道位移视为后续发现;论文文本显示其主线更直接:先从对称 LSBM 的矩多项式性质出发,把 motif matching 归约为截断矩问题,再给出闭式 fiber 和 breaker graph,随后用实验展示谱管道沿 fiber 位移。论文还明确把 fiber 归为“模型与统计量的组合”,而不是模型本身不可识别。

4. 核心 intuition

可以用“有限角度影子”来理解。

想象一个三维物体,但观察者只能看少数几个固定方向的影子。如果影子数量足够多,理论上可以重建物体;如果只看低阶影子,就可能出现一整个连续物体族,它们的影子完全相同。这个物体族就是 fiber。

对应到论文:

  • 三维物体是 LSBM/DCSBM 配置,包括社区权重、斜率、径向分布。
  • 固定方向的影子是 motif densities。
  • 只看低阶影子,等价于只统计顶点数不超过 2K−2 的图。
  • fiber 是那些所有低阶影子都相同的连续配置族。
  • friendship graph F_{K−1} 是一个特殊观察角度,刚好能看出 fiber 上的差异。
  • 信号被 m_1 的幂次抑制,相当于这个特殊角度下的影子差异极小,肉眼几乎看不见。
  • 谱管道相当于先用模糊照片重建物体,再用一个有系统偏差的尺子量体积;照片本身可能很稳定,但量出的体积会沿着“影子相同”的物体族滑动。

这个类比能对上机制,因为论文的核心不是“数据太少”,而是“统计量太粗”。同一个图分布包含足够信息,但有限阶 motif 统计量把多个配置压到同一个摘要上。

5. 方法 pipeline 举例

用一个具体输入走一遍流程。输入选择 K=4,对称斜率,共享 uniform radial law R,并取论文 Table 1 中的 pair A 和 pair B。

  1. 构造两个配置 Θ_A 和 Θ_B。它们共享同一个径向分布 R。原文给出:
  • m_1 = 0.21744283
  • m_2 = 0.05862892
  • pair A 的 m_3 = 0.01632560
  • pair B 的 m_3 = 0.02369236
  • m_3 相对差为 45.1%
  1. 对这两个配置做阶数不超过 2K−2 = 6 的 motif census。因为 K=4,所以统计所有顶点数不超过 6 的图。根据定理,这些图的 slope index h(F) 最多为 K−2 = 2,只能看到 m_1 和 m_2,看不到 m_3。中间结果是:
  • Cen_6(Θ_A) = Cen_6(Θ_B)
  • 所有 6 个及更少顶点的 homomorphism densities 完全相同
  • 所有最大度数不超过 2K−3 = 5 的图密度也完全相同,无论顶点数多大
  1. 加入 friendship graph F_3。它有 2K−1 = 7 个顶点,是 3 个三角形共享一个中心。它的 slope index 是 3,因此能读到 m_3。中间结果是:
  • t(F_3; Θ_A) 与 t(F_3; Θ_B) 不同
  • 原文给出差异为 7.551×10^-7
  • 这个差异对应 m_3 相对差 45.1%,但被强抑制
  1. 如果从真实网络估计这个差异,需要多大样本?原文对 K=4 外推:
  • 每个配置合并 200 个图时,需要约 10^12–10^13 个节点
  • 每个配置只用一个图时,需要约 2×10^15 个节点
  • 这个障碍不随 edge density 改变而消失
  1. 换到谱管道示例。取 HI 配置,w_min = 0.0375,即少数社区占 3.75%。模拟 C=0.3、n=32000 的图,平均度数为 n C^2 / 4 = 32000×0.3^2/4 = 720。
  1. 对每个模拟图做二维 ASE,然后运行 P1-cluster:把每个节点压缩成斜率估计,做小半径过滤,再对绝对斜率做一维 2-means,读出两个原子和权重。中间结果是:
  • 200 个 replicate 都落在 fiber 附近,原文说每个 replicate 在 θ 坐标下距离真值 fiber 不超过 0.02,约为弧长的 1.9%
  • 但估计沿 fiber 位移 31.4% of arc
  • spread 为 4.67% of arc
  • displacement 是 spread 的约 6.7 倍,原文 Table 5 给出 ratio 6.7
  • 少数社区权重被放大,原文在 HI 处给出 fitted-to-true minority weight 约 4.4
  1. 对同一批 ASE 嵌入运行 RayEM。RayEM 不把节点简单压缩成方向后聚类,而是在 ASE 协方差下拟合射线混合模型。中间结果是:
  • 原文在 HI、mean degree 720 给出 RayEM 总误差 0.26% of arc
  • 同一嵌入、同一真值下,P1-cluster 沿 fiber 位移,RayEM 不位移
  • 这说明问题在 summary statistic,不在 embedding 本身

6. 核心数学推导

先解释符号。

  • Θ = ((w_1,…,w_K),(s_1,…,s_K),R) 是一个配置。
  • w_i 是社区权重,满足 w_i > 0、∑_i w_i = 1,并且对称:w_i = w_{K+1−i}。
  • s_i 是社区斜率,满足 s_i = −s_{K+1−i}。
  • R 是径向分布,在 (0,C) 上,矩为 ρ_d = E_R[x^d]。
  • 节点 u 先按 Pr[c_u = i ∣ Θ] = w_i 抽社区,再抽半径 x_{1,u} ∼ R。
  • latent vector 是 L_u = x_{1,u}(1, s_{c_u})。
  • edge probability 是 W(u,v) = ⟨L_u,L_v⟩ = x_{1,u} x_{1,v}(1 + s_{c_u} s_{c_v})。
  • t(F;Θ) 是图 F 在配置 Θ 下的 homomorphism density。
  • m_j = E[s^{2j}] 是平方斜率的矩。由于对称,奇数斜率矩为零。

核心公式是 motif density 的 factorization:

t(F;Θ) = ∏_{v∈V(F)} ρ_{deg_F(v)} · ∑_{S∈E(F)} ∏_{v∈V(F)} m_{deg_S(v)/2}

这里 E(F) 表示 F 的偶子图集合:S ⊆ E(F),且每个顶点在 (V(F),S) 中度数为偶数。

推导分四步。

第一步,把 edge probability 代入 homomorphism density。每条边贡献一个 x_u x_v 和一个 (1+s_u s_v)。半径部分相乘时,每个顶点 v 被它的度数 deg_F(v) 次使用,所以半径期望分解为 ∏_v ρ_{deg_F(v)}。

第二步,展开斜率部分。∏_{uv∈E(F)}(1+s_u s_v) 展开成对边子集 S 求和。一个 S 贡献 ∏_{uv∈S} s_u s_v = ∏_v s_v^{deg_S(v)}。

第三步,利用对称斜率分布。若某个顶点在 S 中度数为奇数,则期望包含 E[s^{odd}] = 0,整项消失。只有所有顶点在 S 中度数为偶数时保留。对偶数度数 deg_S(v)=2r,贡献 m_r。于是得到上面的偶子图展开。

第四步,定义 slope index:

h(F) = max_{S∈E(F)} max_{v∈V(F)} deg_S(v)/2

它表示图 F 的密度多项式最高能读到哪个斜率矩。若两个配置共享 R 且 m_1,…,m_j 相同,则所有 h(F) ≤ j 的图密度相同。若它们第一次在 m_j 上不同,则所有 h(F)=j 的图密度会按同一方向改变,因为展开系数非负,没有 cancellation。

接下来把 slope index 和顶点数联系起来。如果 h(F) ≥ j,则存在一个顶点在某个偶子图 S 中度数至少 2j。这个顶点必须有 2j 个不同邻居,再加上它自己,所以:

∣V(F)∣ ≥ 2j + 1

因此,如果 ∣V(F)∣ ≤ 2K−2,就不可能有 h(F) ≥ K−1。所以所有顶点数不超过 2K−2 的图只能看到 m_1,…,m_{K−2},看不到 m_{K−1}。

friendship graph F_{K−1} 有 2K−1 个顶点,中心连接所有其他顶点,外围形成 K−1 个三角形。它有一个偶子图让中心度数达到 2K−2,所以 h(F_{K−1}) = K−1。因此它是能读到 m_{K−1} 的最小 breaker 之一。原文还给出它是 2K−1 个顶点上边数最少的 unique separator。

关于信号抑制,原文 Proposition 5.1 的可辨认结论是:含 m_j 的项会被 m_1 的幂次压低,F_j 达到这个界。摘要和正文给出的数值结论是:K=4 时抑制因子约为 10^-4。原文此处公式提取有损坏,精确指数不自行补全。

再解释 fiber 的闭式构造。对 K=4,令:

J(ξ) = [[m_1, b_1], [b_1, ξ]]

其中:

b_1^2 = m_2 − m_1^2

J(ξ) 的两个特征值为 τ_1 和 τ_2,对应平方斜率。配置由 θ = (τ_1, τ_2, α_1) 表示,其中:

α_1 = (τ_2 − m_1)/(τ_2 − τ_1)

自由参数 ξ 改变时,m_1 和 m_2 不变,但 m_3 改变。admissible 端点为:

ξ− = b_1^2 / m_1

ξ+ = T − b_1^2 / (T − m_1)

其中 T = min(1, C^{-2} − 1)。原文此处公式提取有损坏,但 K=4 的显式结构可读。

对一般 K,原文用 Hankel 矩阵:

M_k = (m_{a+b−2})_{a,b≤k}

通过 Cholesky 分解得到 Jacobi 系数,再构造三对角矩阵 J(ξ),其右下角是自由参数 ξ。不同 ξ 给出不同的 m_{K−1},但 m_0,…,m_{K−2} 相同。原文 K 偶数时权重公式在提取文本中显示为损坏形式,无法辨认精确系数;这里不自行补全。

一句话总结:核心公式在计算“一个 motif 最高能看到哪个斜率矩”,从而证明有限阶 motif census 会把一整个一维 fiber 压成同一个摘要。

7. 实验设计

实验分为理论验证、census 检测成本、谱管道位移、model-based fits 对照四部分。

数据集不是真实网络,而是模拟图。模型族是 LSBM/DCSBM 对称射线模型。径向分布主要使用 uniform law on (0,C)。平均度数由 n C^2 / 4 给出。实验覆盖 K=4、K=5、K=6 的定理与 census 成本;谱管道实验主要在 K=4,n 最大到 32000,C 取 0.75、0.5、0.3 等。

基线包括:

  • P1-cluster:二维 ASE,节点斜率估计,小半径过滤,一维 2-means。
  • P1-Prony:对 ASE 后的平方斜率矩做 Prony 方法。
  • SCORE:特征向量比值的谱聚类。
  • row-normalized spectral clustering:行归一化后聚类。
  • spherical coordinates with GMM:球坐标加 Gaussian mixture。
  • RayEM:在 ASE 协方差下拟合射线混合模型。
  • Bayesian LSBM sampler:LSBM 作者的贝叶斯采样器,曲线限制为过原点的直线。
  • census estimators P2、P2′、P2′′:从 motif densities 反推斜率矩或拟合 fiber。
  • held-out oracle log-loss:用真实 latent positions 投影到候选射线,检验图分布本身是否包含信息。

指标包括:

  • motif density 差异,例如 t(F_3;Θ_A) − t(F_3;Θ_B)。
  • 两样本 z-statistic 和外推样本量 n*。
  • 参数总误差,写成 % of arc,即相对 fiber 参考弧长 1.0571 的误差。
  • along-fiber displacement,即沿 fiber 的有符号位移。
  • across-fiber distance,即离开 fiber 的距离。
  • replicate spread,即重复估计的离散度。
  • fitted-to-true minority weight,即估计少数社区权重与真实权重的比。
  • nominal 95% confidence region coverage。

消融包括:

  • 密度变化:C=0.75、0.5、0.3。
  • 样本量变化:n=2000、8000、32000。
  • 少数社区权重变化:从 0.495 到 0.03。
  • 少数社区在 shallow ray 还是 steep ray。
  • 谱特征形式:ratio、angle、unit vector。
  • 聚类器:k-means、GMM。
  • 是否加小半径过滤。
  • Richardson correction 和 subsampling detector。
  • moment inversion 的无约束与约束变体。

实验能否支撑结论:对定理部分,支撑较强,因为数学证明给出闭式 fiber、端点、breaker graph 和矩匹配机制。对 census 检测成本,支撑是外推式的,不是直接观测到 10^15 节点;原文明确 n* 是 extrapolated。对谱管道位移,支撑来自大量模拟 cell,但主要限于 K=4、n≤32000、模拟图、一条 fiber。对 model-based fits 避免位移,支撑较强,但前提是给定 K 和射线族;当 K 或射线族错误时未测试。

缺少的证据包括:真实网络实验、K 选择实验、非对称斜率实验、每射线不同径向律实验、更高阶 bias correction 是否消除位移、独立实现复现、非 uniform radial law 的广泛敏感性。

8. take-aways

  1. 对 K≥3,顶点数不超过 2K−2 的 motif census 不能识别 LSBM/DCSBM 对称射线模型中的一维 fiber。只有 F_{K−1} 这类 2K−1 顶点图才能打破盲区。成立条件是共享径向分布和反射对称斜率。
  1. K=4 时,两个配置可以在 m_3 上相差 45.1%,但 friendship graph density t(F_3) 只差 7.551×10^-7。原文外推:合并 200 个图需要约 10^12–10^13 节点,单图需要约 2×10^15 节点。这个结论适用于 motif-count detection,不适用于全图模型拟合。
  1. 没有 node features 的 message-passing GNN 在这个模型族中看不到斜率。原因是所有 tree densities 只依赖径向分布 R。成立条件是图on 极限、order-normalized sum aggregation、mean readout,且不使用 spectral positional encodings。
  1. 谱管道可能“精确地错”。在 C=0.3、n=32000、HI 配置中,P1-cluster 的 200 个 replicate 都贴近 fiber,距离约 1.9% of arc,但沿 fiber 位移 31.4% of arc,spread 为 4.67% of arc。原文给出 nominal 95% regions 在 17 of 18 个组中错过真值,最佳覆盖率也只有 5.1%。
  1. 保留 embedding 噪声几何的模型拟合能避免位移。RayEM 在 HI、mean degree 720 的总误差为 0.26% of arc;Bayesian LSBM sampler 的 along-fiber RMSE 为 0.81% of arc。成立条件是给定 K 和射线族,并且使用 ASE 协方差或相应模型。

9. 最脆弱的假设

最脆弱的假设是“反射对称斜率 + 所有社区共享同一个径向分布 R”。

这个假设承担了三件事。第一,奇数斜率矩为零,使 motif density 展开只保留偶子图。第二,径向矩完全乘性分离,使 motif matching 归约为斜率矩 matching。第三,截断矩问题的 Hankel/Jacobi 构造才能给出闭式 fiber 和端点。

如果共享径向分布不成立,例如每条射线有自己的尺度,R 不再能从所有密度中干净地 factor out,tree densities 或低阶 motif 可能不再只依赖一个共同径向律。此时论文给出的精确 fiber、端点、F_{K−1} 的 unique edge-minimal separator 地位,以及 K=4 的显式公式,可能不再直接适用。

如果反射对称不成立,奇数斜率矩可能不为零,偶子图展开会失效,motif 密度会看到更多方向。论文第 9 节讨论到共享径向律是 load-bearing,并说 fiber 在更大模型类中仍可能保留,但闭式不再成立。这个判断来自论文的结构分析,不是真实数据证据。

实验证据也有限。谱实验主要在 K=4、模拟图、n≤32000、一条 fiber 上。model-based fits 虽然准确,但被给定 K 和射线族。若真实数据中 K 选错,或网络不是射线结构,RayEM 和 Bayesian LSBM 是否仍可靠,没有实验证据。

因此,一旦“共享径向分布 + 对称射线”这个前提在目标网络中明显不成立,论文的闭式 fiber 和 practitioner thresholds 就不能直接搬用。结论会退化为:低阶统计量仍可能有盲区,但盲区形状、大小和检测成本需要重新计算。

10. 一周最小复现

目标是在 1 张 24GB 消费级显卡和 1 周内复现最核心结论:低阶 motif census 存在 fiber,而谱 summary pipeline 会沿 fiber 位移,model-based fit 可以避免。

Day 1:实现 K=4 模型和 fiber 构造。

  • 使用 Table 1 的 m_1 = 0.21744283、m_2 = 0.05862892。
  • 计算 b_1^2 = m_2 − m_1^2。
  • 对 pair A 使用 m_3 = 0.01632560,对 pair B 使用 m_3 = 0.02369236。
  • 用数值搜索 ξ,使构造出的平方斜率分布匹配给定 m_3。
  • 验证 Cen_6 相同:不需要枚举所有 6-vertex graphs,可先验证所有 h(F) ≤ 2 的图;再单独计算 t(F_3)。
  • 预期结果:t(F_3) 差异约为 7.551×10^-7。

Day 2:实现 motif 计数。

  • 使用 n=8000、C=0.75。平均度数为 8000×0.75^2/4 = 1125。
  • 每个配置生成 200 个图。
  • 用整数算术计算 F_3 homomorphism counts,避免 float32 精度不足。
  • 对每个图计算 t(F_3) 估计,并做两样本 z-statistic。
  • 预期结果:有限样本很难直接显著,因为原文外推需要 10^12–10^13 节点合并 200 图。这里只复现“差异极小”,不复现显著检测。

Day 3:实现 ASE 和 P1-cluster。

  • 使用 HI 配置,w_min = 0.0375。
  • 为适配 24GB 显存,选择 C=0.5、n=8000。平均度数为 8000×0.5^2/4 = 500。
  • 生成稀疏邻接矩阵,边数约为 8000×500/2 = 2000000。
  • 用稀疏二维特征分解得到 ASE。
  • 实现 P1-cluster:节点斜率 x_2/x_1,小半径过滤,对绝对斜率做 2-means,读出 τ_1,τ_2,α_1。
  • 预期结果:原文 Table 11 在 C=0.5、n=8000、HI 给出 displacement 44.6% of arc、spread 3.79% of arc。若实现一致,应看到估计贴近 fiber 但沿 fiber 大幅位移。

Day 4:实现 intrinsic fiber coordinates。

  • 用 θ = (τ_1, τ_2, α_1) 表示配置。
  • 以原文参考弧长 1.0571 归一化。
  • 计算每个估计到 fiber 的最近点,得到 along-fiber displacement 和 across-fiber distance。
  • 预期结果:displacement 明显大于 spread,说明误差是 bias,不是随机噪声。

Day 5:实现 RayEM 或简化 model-based fit。

  • 在 ASE 行上使用高斯噪声模型,射线约束为 r_i(1, ±s)。
  • 用 EM 拟合权重、半径和斜率。
  • 如果完整 ASE covariance 实现困难,可先用经验协方差近似,再检查是否仍显著优于 P1-cluster。
  • 预期结果:原文给出 RayEM 在 tested cells 总误差低于 1% of arc;在 HI、mean degree 720 为 0.26% of arc。最小复现中若低于几个百分点,即支持核心对照。

Day 6:检验置信区间是否沉默。

  • 对 P1-cluster 做 bootstrap 或 jackknife,构造 nominal 95% region。
  • 检查真值是否落入。
  • 预期结果:原文给出 17 of 18 个组中 nominal 95% regions 错过真值,最佳覆盖率 5.1%。小规模复现中应看到覆盖率远低于 95%,即使 replicate spread 很小。

Day 7:检验 ambiguity width。

  • 对 P1-cluster 的 m_1、m_2 估计,构造 K=4 fiber。
  • 读取 fiber 上少数社区权重范围。
  • 预期结果:原文给出一个 fitted minority weight 0.17 可能对应真实权重从 0.03 到 0.50 的 fiber。复现中若看到类似宽区间,说明低阶摘要留下的歧义很大。

最小成功判据:

  1. pair A/B 的 Cen_6 相同,但 t(F_3) 不同。
  2. P1-cluster 在 HI 配置中沿 fiber displacement 明显,且 displacement 大于 spread。
  3. RayEM 或同类 model-based fit 在同一嵌入上误差显著低于 P1-cluster。
  4. bootstrap 95% region 对 P1-cluster 不覆盖真值。

11. 反例设计

设计一个直接攻击核心定理的实验。

对象:K=4,pair A 和 pair B,来自 Table 1。它们共享 R,匹配 m_1 和 m_2,但 m_3 不同。

任务:检验“顶点数不超过 6 的 motif census 完全相同”以及“F_3 是 7 顶点上边数最少的 unique separator”。

步骤:

  1. 枚举所有 unlabeled graphs F,满足 ∣V(F)∣ ≤ 6。
  2. 对每个 F,用 50 位精度或精确有理数计算 t(F;Θ_A) 和 t(F;Θ_B)。
  3. 检查是否所有差值严格为零。
  4. 枚举所有 unlabeled graphs F,满足 ∣V(F)∣ = 7 且边数少于 F_3 的边数。F_3 边数为 3×(4−1)=9。
  5. 对每个这样的 7-vertex graph,计算 t(F;Θ_A) 和 t(F;Θ_B)。
  6. 检查是否存在边数少于 9 的图能区分 pair A 和 pair B。
  7. 检查是否存在与 F_3 不同构的 9-edge graph 也能区分 pair A 和 pair B。

判据:

  • 如果找到一个 ∣V(F)∣ ≤ 6 的图,使 t(F;Θ_A) ≠ t(F;Θ_B),则“Cen_6 不能区分 fiber”的核心定理被推翻。
  • 如果找到一个 7-vertex graph,边数少于 9,且能区分 pair A 和 pair B,则“F_3 是 unique edge-minimal separator”被推翻。
  • 如果找到另一个 9-edge graph 也能区分,则 uniqueness 被推翻,但 threshold order 仍可能成立。

这个反例不依赖模拟噪声,因为定理是 population density 层面的。若精确计算发现非零差异,论文关于 bounded-order motif census 的核心主张直接崩塌。

12. 落地判断

普通用户:目前不能直接使用。论文不是现成软件,也不是真实网络上的即插即用估计器。普通用户能拿到的是认知层面的收益:如果一个网络分析工具只依赖小 motif 计数或谱聚类后直接报社区比例,那么它可能在某些 latent block 结构中给出非常稳定但系统偏错的参数。普通用户无法自行验证是否处于风险区,除非工具内置检查。

应用开发者:可以部分落地。最直接的集成方式是实现论文的四项检查。第一,检查拟合是否处于 displacement regime:看 mean degree、fitted minority weight、少数社区在 steep ray 还是 shallow ray。原文给出的阈值是:在 mean degree 2000 及以上,displacement 可低于 5%;当少数社区在 steep ray 时,fitted weight 至少 0.095 才在 mean degree 1125 下安全,至少 0.37 在 mean degree 720 下安全,至少 0.42 在 mean degree 500 下安全。第二,若处于风险区,不要只报 motif counts 或 summary spectral parameters,改跑保留 embedding 噪声几何的模型拟合。第三,不要依赖 bootstrap 或 jackknife 95% interval 报警,因为误差是 bias。第四,报告 fiber ambiguity width,而不是只报告点估计。

研究团队:可以较快使用定理和实验设计。可带走的研究问题包括:如何自动选择 K;如何在不知道射线族时做 model selection;如何把 fiber width 变成可计算的 uncertainty quantification;如何设计能高效读取 m_{K−1} 的 motif estimator;如何在非对称、非共享径向律、稀疏图、动态图中扩展。论文给出的 K=4 闭式 fiber 是强基线,适合用来测试新 estimator 是否真的突破 bounded-order 盲区。

距离可用还差几步:

  1. 数据规模:定理本身不需要数据;实际估计需要足够节点数。K=4 的 motif detection 外推到单图约 2×10^15 节点,这在真实网络中几乎不可用。谱位移实验最大 n=32000,真实网络是否同样表现未验证。
  1. 算力门槛:最小复现可在单张 24GB 消费级显卡上用 n=8000、C=0.5、200 replicates 做。完整论文实验规模更大,原文给出 64 CPUs 和 6×RTX 6000 Ada,前七次约 10 wall-hours,第八次更多。因此完整复现不是普通笔记本一天能完成。
  1. 工程集成:需要实现 ASE、稀疏特征分解、偶子图或 friendship graph 计数、fiber 参数化、intrinsic coordinates、RayEM 或贝叶斯 LSBM。对非 K=4 情形,闭式 fiber 和端点计算更复杂。
  1. 独立验证:需要在真实网络、非对称斜率、每射线不同径向律、K 未知、节点特征存在、position encoding 存在等条件下测试。论文自己把 spectral experiments 限制在 K=4、n≤32000、模拟图、一条 fiber,且 model-based fits 给定 K 和射线族。

成本量级:如果只做核心复现,一个熟悉概率图模型和谱聚类的开发者用 1 周、单张 24GB 消费级显卡是可行的。如果做完整论文实验,需要多核 CPU 或多 GPU 集群,以及大量 motif 计数和 MCMC 链。最大坑是误把“估计稳定”当成“参数正确”。P1-cluster 的 replicate spread 可以很小,但点估计沿 fiber 位移 31.4% of arc;bootstrap 95% region 可以很窄,但原文给出它在 17 of 18 个组中错过真值。

内容由 AI 生成,仅供参考。如发现错误,欢迎反馈。

原始英文摘要

arXiv:2611.23547v1 Announce Type: new Abstract: A graphon is determined by all of its homomorphism densities, but motif-based methods use finitely many. We compute exactly what that truncation costs in a natural family: latent structure block models whose positions lie on $K$ rays, equivalently degree-corrected block models of rank two. For a given radial law, the configurations that agree on every graph with fewer than $2K-1$ vertices form a one-dimensional fiber, which we give in closed form with explicit endpoints; the friendship graph $F_{K-1}$ is its unique edge-minimal separator, so no fixed motif order serves every $K$. The separating signal is suppressed by a factor of at most $m_1^{2(K-1)}$, where $m_1$ is the mean squared slope, about $10^{-4}$ at $K=4$: detecting it from motif counts would take about $10^{15}$ nodes in a single graph, at any edge density. The information is nonetheless in the graph; the fiber belongs to the statistic, not the model. Common spectral pipelines, which count no motifs, still slide along the fiber by more than a third of its length at ordinary densities, with confidence regions that almost never contain the truth, while model-based fits of the same embedding do not. We give practitioners four checks: whether a fit is at risk, what to run instead, why a confidence interval will not warn, and how wide the remaining ambiguity is.

同方向论文 · stat.ML

查看全部 →