arXiv：cs.LG· Soham Dan·· 4 小时前AI 评分36
无顶点对应的随机图双样本检验：样本复杂度与图统计量
Two-Sample Testing for Random Graphs without Vertex Correspondence
AI 导读
研究在顶点无对应关系时随机图双样本检验所需的样本量：对 Erdős–Rényi 零假设与保持各期望度不变的双块植入差异，当每图信噪比 t<1 时每组需 m≍t^{-3} 张图，带符号三角形计数可达到该速率；若顶点对齐则仅需 m≍t^{-1}，错位代价约为 t^{-2}。当三角形信号抵消时速率变为 t^{-4}，需改用 4-cycles；由树构建的统计量在两假设下期望相同，有限个此类检验渐近无功效。
正文
Abstract:Two populations of graphs often have to be compared without any correspondence between their vertices, for instance when networks come from different communities, or when a graph generative model is evaluated against held-out graphs. We study how many graphs such an unaligned two-sample test needs, and which graph statistics can detect which differences. For an Erdős--Rényi null and a planted two-block difference that leaves every expected degree unchanged, we show that $m\asymp t^{-3}$ graphs per group are necessary and sufficient when the per-graph signal-to-noise ratio is $t<1$. Signed triangle counts attain this rate, and the lower bound holds for every graph size. With aligned vertices $m\asymp t^{-1}$ graphs suffice, so misalignment costs a factor of order $t^{-2}$. When the triangle signal cancels, the rate becomes $t^{-4}$ and $4$-cycles are needed. Statistics built from trees have exactly the same expectation under both hypotheses, and tests based on finitely many of them have asymptotically no power. In the graphon limit, this class includes degree distributions and message-passing graph neural network features. For a non-constant null, a generic difference is visible at first order, and a simple motif test attains the aligned order of sample size, suggesting that misalignment is costly mainly for differences that are invisible at low orders. We also give an exactly valid test for one or two graphs per group, at a cost in power. In our simulations, the fitted exponents are close to the predicted ones, and degree-based and random-GNN evaluation metrics stay at their level in a setting where signed triangles need about $65$ graphs.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07503 [stat.ML] |
| (or arXiv:2610.07503v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07503 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Soham Dan [view email]
[v1]
Mon, 5 Oct 2026 23:09:29 UTC (325 KB)
来源：arXiv：cs.LG · arxiv.org