未对齐图检验需m≍t⁻³个图，比对齐时多出t⁻²倍代价！
Two-Sample Testing for Random Graphs without Vertex Correspondence
📖 AI 总结
本文研究在顶点无对应关系条件下对两个随机图总体进行双样本检验的统计极限。作者针对Erdős–Rényi零假设与保持所有期望度不变的两块植入差异模型，证明当每图信噪比为t<1时，每组所需图数满足m≍t⁻³，且该速率对任意图规模均成立；带符号三角形计数可达到此速率。若顶点对齐，则仅需m≍t⁻¹，说明错位带来的代价约为t⁻²倍。当三角形信号相互抵消时，速率变为t⁻⁴，需借助四环统计量。基于树的统计量在两假设下期望完全相同，有限多个此类统计量渐近无检验功效，图极限下度分布与消息传递GNN特征均属该失效类。对非常数零假设，一般差异可在一阶显现，简单模体检验即可达到对齐样本量级。作者还给出每组仅一至两张图的精确有效检验，并报告模拟中拟合指数与理论预测接近，在带符号三角形约需65张图的设定下，基于度和随机GNN的评估指标仍停留在原水平。
🔑 关键词速览
| 未对齐两样本检验 | 在两组图的顶点之间没有对应关系的情况下，检验它们是否来自同一分布。 |
| Erdős–Rényi零假设 | 一种随机图模型，其中每对顶点之间独立地以相同概率相连。 |
| 植入两块差异 | 一种备择假设，其中图被分为两个块，块内和块间的连接概率不同，但整体期望度保持不变。 |
| 带符号三角形计数 | 一种图统计量，对三角形中的边赋予正负号后求和，用于检测特定结构差异。 |
| 图极限 | 描述大规模图序列极限行为的数学对象，常用于分析图统计量的渐近性质。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅