跳转至

RKHS-Based Latent Position Random Graph Correlation

作者: Xiaoyi Wen, Junhui Wang, Liping Zhu
来源: Journal of Computational and Graphical Statistics
主题: 数理统计 / 假设检验
相关性: 5/10
机构绿灯: Chinese University of Hong Kong(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是:如何度量两个随机图之间的依赖关系。具体而言,给定两个共享同一顶点集的随机图 G₁ 和 G₂,我们想要检验它们的生成机制是否独立。这一问题的统计困难在于:图的观测是高维邻接矩阵,而图的结构信息(潜在位置)是不可观测的。本文的切入点是潜在位置随机图(Latent Position Random Graph, LPRG)模型——每个顶点有一个潜在位置,边的出现概率由潜在位置之间的核函数决定。在此框架下,两个图的独立性等价于两组潜在位置的独立性,从而将"图的独立性检验"转化为"潜在变量的独立性检验"。该子方向当前处于发展阶段:已有工作分别处理了图的嵌入(embedding)和变量间的独立性检验,但将两者结合并给出完整理论保证的工作尚属少见。

发展脉络

奠基工作:距离相关与核独立性准则。 本文的两个理论基石是 Székely et al. (2007) 的距离相关(distance correlation)和 Gretton et al. (2005, 2007) 的希尔伯特-施密特独立性准则(HSIC)。前者通过欧氏距离的期望定义了度量相关性的标量,后者将这一思想推广到再生核希尔伯特空间(RKHS),用核函数的期望刻画独立性。这两条线的共同特点是:零值当且仅当独立(对特征函数或通用核而言),且都有 U-统计量形式的无偏估计。但它们的适用对象都是向量值随机变量,无法直接处理图数据。

主要进展:图的谱嵌入。 将图转化为向量表示的关键工具是邻接矩阵的谱分解。Tang et al. (2013) 建立了潜在位置随机图的邻接谱嵌入(Adjacency Spectral Embedding, ASE)的收敛性,证明嵌入向量能一致地估计潜在位置(在正交变换意义下)。这一结果使得"先用谱嵌入估计潜在位置、再对嵌入向量做独立性检验"成为一个自然的策略。Tang and Priebe (2018) 进一步将类似结论推广到归一化拉普拉斯矩阵的谱嵌入。与此同时,Lee et al. (2019) 提出了一个两步法:先用扩散映射(diffusion maps)嵌入图,再用距离相关检验嵌入向量之间的依赖。但该工作缺乏对两步误差传播的完整理论分析。

当前 frontier 与本文位置。 当前的前沿问题是如何在"嵌入误差"存在的情况下仍保证检验的有效性。本文声称的贡献正是在此:作者提出一个无需指定核函数的图相关度量(gCor),证明其样本版本(基于 ASE 嵌入)一致收敛到总体版本,并给出置换检验的有效性证明。作者在引言中明确写道:"我们证明,即使没有指定核函数,样本图协方差也能收敛到其总体版本"——这是对 Lee et al. (2019) 两步法缺乏理论保证的直接回应。本文的位置是:将 HSIC 的理论框架与 ASE 的收敛性结合,给出一个端到端的、有理论保证的图独立性检验。

子线索聚类

被引文献大致落在三条子线索上:

  1. 基于距离/核的独立性度量:Székely et al. (2007)、Gretton et al. (2005, 2007)、Sejdinovic et al. (2013)、Shen et al. (2022)。这条线提供检验统计量的定义和渐近理论,核心工具是特征函数、RKHS 嵌入和 U-统计量。
  2. 随机图的谱嵌入与极限理论:Tang et al. (2013)、Fishkind et al. (2013)、Tang and Priebe (2018)、Levin et al. (2021)、Oliveira (2009)。这条线提供从邻接矩阵到潜在位置估计的工具,核心结果是嵌入向量的收敛速率。
  3. 图依赖性的应用检验:Lee et al. (2019)、Xiong et al. (2019)、Lyzinski et al. (2014)。这条线直接处理"两个图是否相关"的问题,但多为方法驱动、理论保证不足。

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

  1. 如何定义图的依赖关系? 直接比较邻接矩阵的条目(如 Pearson 相关)忽略了图的结构信息;本文的答案是:依赖关系应定义在潜在位置上,而非观测边上。
  2. 嵌入误差如何影响检验? 谱嵌入是对潜在位置的估计,估计误差会传播到后续的独立性检验中。核心问题是:这种传播是否会导致检验失效?本文的定理 1 和 2 正是回答这一问题。
  3. 如何避免核函数的选择? 传统 HSIC 需要用户指定核函数,而图的生成核(即 LPRG 中的 K)通常是未知的。本文声称其方法"无需指定核函数",因为 ASE 嵌入本身隐含地估计了核诱导的特征映射。

⚠️ 作者的 framing

这是作者的说法:作者将本文定位为"首次在潜在位置随机图框架下,给出无需指定核函数的图相关度量,并证明其一致性和检验有效性"。作者在引言中强调,已有方法(如 Lee et al. 2019)缺乏理论保证,而本文填补了这一空白。作者还声称其方法对图的稀疏性有一定鲁棒性(通过引入 Assumption 3 和 4 放宽了 Assumption 2 的密度条件)。值得研究者注意:作者对 Lee et al. (2019) 的批评是否公允、其理论条件(如核的通用性、特征间隙)在实际中是否可验证,这些都需要读者自行判断。

张力

未见明显对立引用。但存在一个微妙的张力:Tang et al. (2013) 的 ASE 收敛性要求图是相对稠密的(Assumption 2),而实际网络数据往往是稀疏的。本文通过引入 Assumption 3 和 4 试图将结论推广到半稀疏情形,但这是否真正解决了稀疏性问题,还是仅仅将问题转移到了对谱范数界的假设上,值得研究者仔细推敲。


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

第一步:符号、模型、可观测数据

潜在位置随机图(LPRG)模型:

  • 潜在变量:\(X = (x_1, \ldots, x_n)^\top \in \mathbb{R}^{n \times p}\) 和 \(Y = (y_1, \ldots, y_n)^\top \in \mathbb{R}^{n \times q}\) 分别是两个图的潜在位置矩阵。\(x_i\) 和 \(y_i\) 是第 \(i\) 个顶点的潜在位置,不可观测。我们假设 \((x_i, y_i)\) 是来自联合分布 \(F_{XY}\) 的 i.i.d. 样本,边缘分布为 \(F_X\) 和 \(F_Y\)。
  • 可观测数据:\(G_1\) 和 \(G_2\) 是两个共享顶点集 \(\{1, \ldots, n\}\) 的无向图,其邻接矩阵分别为 \(A_1, A_2 \in \{0,1\}^{n \times n}\)。\(A_1\) 的上三角元素 \(A_{1,ij}\) 独立地服从 \(\text{Bernoulli}(K(x_i, x_j))\),其中 \(K: \mathcal{X} \times \mathcal{X} \to [0,1]\) 是图的生成核(link function)。类似地,\(A_{2,ij} \sim \text{Bernoulli}(L(y_i, y_j))\)。
  • 目标(estimand):检验 \(H_0: F_{XY} = F_X F_Y\)(即 \(X\) 与 \(Y\) 独立)对 \(H_1: F_{XY} \neq F_X F_Y\)。

关键点:\(X\) 和 \(Y\) 不可观测,我们只能通过 \(A_1\) 和 \(A_2\) 来推断 \(X\) 和 \(Y\) 是否独立。这就是"可观测"(邻接矩阵)与"想要但观测不到"(潜在位置)之间的鸿沟。

核与特征映射:

  • 设 \(K\) 是 \(\mathcal{X}\) 上的正定核,其对应的 RKHS 为 \(\mathcal{H}_K\),特征映射为 \(\phi(x) = (\sqrt{\lambda_j} \psi_j(x) : j = 1, 2, \ldots)\),其中 \(\{(\lambda_j, \psi_j)\}\) 是积分算子 \(T_K\) 的特征对。
  • 对 \(d \geq 1\),定义截断特征映射 \(\phi_d(x) = (\sqrt{\lambda_1} \psi_1(x), \ldots, \sqrt{\lambda_d} \psi_d(x))\)。

总体图协方差(Population Graph Covariance):

\[gCov(G_1, G_2) = E[K(x, x')L(y, y')] + E[K(x, x')]E[L(y, y')] - 2E[K(x, x')L(y, y'')]\]

其中 \((x,y), (x',y'), (x'',y'')\) 独立同分布。这是 HSIC 的直接移植:当且仅当 \(X\) 与 \(Y\) 独立时,\(gCov = 0\)(假设 \(K\) 和 \(L\) 是通用核)。

样本图协方差(Sample Graph Covariance):

\[gCov_n(G_1, G_2) = \frac{1}{n(n-3)} \sum_{i \neq j} \tilde{K}_{ij} \tilde{L}_{ij}\]

其中 \(\tilde{K} = (\tilde{K}_{ij})\) 是对估计的核矩阵 \(\hat{K} = \hat{\Phi}_{1,d} \hat{\Phi}_{1,d}^\top\) 做 U-中心化(U-centering)得到的矩阵,\(\hat{\Phi}_{1,d} = U_{1,d} S_{1,d}^{1/2}\) 是 \(A_1\) 的 \(d\) 维邻接谱嵌入(ASE)。类似地定义 \(\tilde{L}\)。

第二步:最小内核

最小内核:假设 \(p = q = 1\)(一维潜在位置),\(K\) 和 \(L\) 是高斯核 \(K(x, x') = \exp(-(x-x')^2)\),且 \(d = 1\)(只取最大的一个特征值对应的特征向量)。在这个最简情形下,本文的核心主张退化为:

主张:设 \(X = (x_1, \ldots, x_n)\) 和 \(Y = (y_1, \ldots, y_n)\) 是两组 i.i.d. 潜在位置。令 \(\hat{\phi}_1(x_i)\) 和 \(\hat{\phi}_2(y_i)\) 分别为 \(A_1\) 和 \(A_2\) 的 ASE 嵌入(一维)。则

\[\frac{1}{n(n-3)} \sum_{i \neq j} \tilde{K}_{ij} \tilde{L}_{ij} \xrightarrow{p} E[K(x, x')L(y, y')] + E[K(x, x')]E[L(y, y')] - 2E[K(x, x')L(y, y'')]\]
其中 \(\tilde{K}_{ij} = \hat{K}_{ij} - \frac{1}{n-2}\sum_k \hat{K}_{ik} - \frac{1}{n-2}\sum_k \hat{K}_{kj} + \frac{1}{(n-1)(n-2)}\sum_{k,l}\hat{K}_{kl}\)。

为什么这个主张非平凡:\(\hat{\phi}_1(x_i)\) 是对 \(\phi(x_i)\) 的估计,估计误差 \(\|\hat{\phi}_1(x_i) - \phi(x_i)\|\) 会传播到 \(\tilde{K}_{ij}\) 中。要证明 \(gCov_n \to gCov\),需要控制这个传播误差。本文的定理 1 给出的条件是:特征值衰减速率(多项式或指数)和嵌入维数 \(d\) 的选择范围。证明的核心困难在于:ASE 的收敛性(Tang et al. 2013)只给出了 \(\|\hat{\phi}_1(x_i) - \phi(x_i)\|\) 的逐点界,但 \(gCov_n\) 是 \(\tilde{K}_{ij}\tilde{L}_{ij}\) 的双重求和,需要将逐点界提升为对双重求和的整体控制。

为什么成立(直觉):当 \(n\) 增大时,ASE 嵌入 \(\hat{\phi}_1(x_i)\) 以高概率逼近 \(\phi(x_i)\)(在正交变换意义下)。由于 \(gCov\) 是核矩阵内积的连续函数,嵌入误差的累积效应可以通过选择适当的 \(d\)(截断维度)来控制:\(d\) 太小则截断误差大,\(d\) 太大则估计误差大。定理 1 给出的 \(d\) 的范围(如 \(d = n^{\theta/\alpha}\))正是平衡这两种误差的结果。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:在潜在位置随机图框架下,如何检验两个随机图之间的独立性,即检验 \(H_0: F_{XY} = F_X F_Y\)。
  2. 核心工具/方法:利用邻接矩阵的谱分解(ASE)估计潜在位置的特征映射,构造无需指定核函数的样本图协方差 \(gCov_n\),并基于置换检验进行推断。
  3. 主要结论:证明了 \(gCov_n\) 在多项式或指数特征值衰减条件下一致收敛到总体 \(gCov\);置换检验在 \(H_0\) 下渐近有效(第一类错误率受控),在 \(H_1\) 下一致有效(功效趋于 1)。

关键设定与假设

  • 模型:LPRG,即 \(A_{ij} \sim \text{Bernoulli}(K(x_i, x_j))\),\(K\) 是通用核(universal kernel)。
  • 假设 1(特征值简单性):积分算子 \(T_K\) 的特征值 \(\lambda_1 > \lambda_2 > \cdots > 0\) 是简单的(无重根)。这保证了特征向量的可识别性。
  • 假设 2(密度条件):\(\Delta = \max_i \sum_j K(x_i, x_j) > c_0 \log n\),即图足够稠密。这是 ASE 收敛性的标准条件(Tang et al. 2013)。
  • 假设 3 和 4(稀疏性推广):\(\rho_n\) 满足 \(n\rho_n = \omega((\log n)^{1/2+\epsilon})\),且 \(\|A - E(A)\| \leq (\log n)^{1/2}\) 以高概率成立。这允许图是半稀疏的(边概率随 \(n\) 衰减)。
  • 相比已有文献的放宽:相比 Lee et al. (2019) 的两步法,本文不要求用户指定核函数;相比标准 HSIC 理论,本文允许嵌入误差的存在。

主要结果

定理 1(一致性):在假设 1 和 2 下,若特征值多项式衰减(\(\lambda_i = O(i^{-\alpha})\),\(\alpha > 1\)),选择 \(d = n^{\theta/\alpha}\) 且 \(0 < \theta \leq \alpha\),则 \(gCov_n \xrightarrow{p} gCov\)。若特征值指数衰减(\(\lambda_i = O(e^{-\tau i})\)),选择 \(d = \frac{1}{\tau}\log(n^\theta)\),则同样成立。

定理 2(零-独立等价):\(gCov_n \to 0\) 当且仅当 \(X\) 与 \(Y\) 独立(在通用核假设下)。这保证了检验的合理性。

定理 3(置换检验的有效性):在 \(H_0\) 下,置换检验的渐近第一类错误率不超过 \(\alpha\);在 \(H_1\) 下,功效趋于 1。

定理 4(拉普拉斯推广):将 ASE 替换为归一化拉普拉斯谱嵌入(LSE),\(dCov_n\)(基于距离相关而非 HSIC)仍保持一致性和检验有效性。

定理 5(稀疏图推广):在假设 3 和 4 下,\(gCov_n\) 的一致性仍然成立,但 \(d\) 的选择范围变为 \(d \leq c_1(\log n)^{2\epsilon}\)。

证明路线与技术技巧

整体路线(以定理 1 为例):

  1. 分解误差:将 \(gCov_n - gCov\) 分解为三项:
  2. 嵌入误差:\(\hat{\phi}_d(x_i)\) 与 \(\phi_d(x_i)\) 的差异;
  3. 截断误差:\(\phi_d\) 与 \(\phi\) 的差异(\(d\) 维截断);
  4. 采样误差:样本均值与总体期望的差异。
  5. 控制嵌入误差:利用 Tang et al. (2013) 的 ASE 收敛性定理,得到 \(\|\hat{\phi}_d(x_i) - \phi_d(x_i)\| = O_p(\sqrt{\log n / n})\)(在适当的正交变换下)。关键技巧是行向量的逐点界与Frobenius 范数界的结合。
  6. 控制截断误差:利用特征值衰减条件。多项式衰减时,\(\sum_{j > d} \lambda_j = O(d^{1-\alpha})\);指数衰减时,\(\sum_{j > d} \lambda_j = O(e^{-\tau d})\)。选择 \(d\) 使得截断误差与嵌入误差同阶。
  7. 控制采样误差:利用 U-统计量的渐近理论(Hoeffding 分解),将 \(gCov_n\) 表示为 U-统计量加余项。
  8. 合并:选择 \(d\) 平衡三项误差,得到 \(gCov_n - gCov = o_p(1)\)。

关键技巧点名:

  • U-中心化:采用 Székely et al. (2014) 的 U-中心化方法构造 \(\tilde{K}\),使得样本协方差是 U-统计量,从而可以利用 U-统计量的渐近正态性。
  • 谱嵌入的旋转不变性:ASE 嵌入在正交变换下是唯一的,因此 \(gCov_n\) 对正交变换不变,无需担心嵌入的旋转模糊性。
  • 特征间隙条件:假设 1(特征值简单)保证了特征向量的可识别性,这是 ASE 收敛性证明的前提。
  • 稀疏性处理:在定理 5 中,通过假设 \(\|A - E(A)\| \leq (\log n)^{1/2}\) 来控制稀疏图带来的额外噪声,这比直接假设稠密图更灵活。

真实例子与应用

例子 1:3D 网格数据。使用 Sumner and Popović (2004) 的动物姿态数据集。对每个 3D 对象采样 \(n = 1000\) 个点,构建 \(k\)-NN 图(\(k = 20\))。比较同一动物的不同姿态(应高度相关)和不同动物的姿态(应低相关)。结果显示,gCorr 能有效区分同类和异类,且比 Dcorr 的区分度更高(同类相关系数更高,异类相关系数更低)。

例子 2:线虫神经连接组。使用 C. elegans 的神经元连接数据(Varshney et al., 2011),将神经元分为感觉、运动、中间神经元三类,检验三类子网络之间的依赖关系。结果显示,感觉-中间神经元子网络的相关性显著高于感觉-运动子网络,与生物学直觉一致。

例子想说明什么:gCorr 不仅能检测线性依赖,还能捕捉非线性依赖(如联合正态设置下的二次关系),且对嵌入维度的选择不敏感(在合理范围内)。

🔎 结论是否比证明窄

  • 定理 2 的"当且仅当":作者在证明中依赖核的通用性(universality),但正文中未明确给出通用核的具体条件(如高斯核的通用性证明引用自 Fukumizu et al., 2007)。读者需自行确认该条件是否在实际使用的核(高斯、拉普拉斯)上成立。
  • 定理 3 的置换检验:作者证明了置换检验的渐近有效性,但未给出有限样本下的 Berry-Esseen 型界。文中提到"置换检验的有限样本性质留待未来研究"(Discussion 部分),这意味着在实际应用中,\(n\) 较小时的检验水平可能偏离 \(\alpha\)。
  • 定理 4 的拉普拉斯推广:作者仅证明了 \(dCov_n\) 的一致性,但未给出检验功效的显式下界。此外,LSE 的收敛性依赖于归一化拉普拉斯矩阵的特征值条件,这些条件在文中未详细讨论。
  • 定理 5 的稀疏性:作者假设 \(\|A - E(A)\| \leq (\log n)^{1/2}\),但未说明这一假设在常见的稀疏图模型(如随机块模型)中是否成立。读者需自行验证。

四、开放问题

  1. 有限样本性质:置换检验在 \(n\) 较小时的第一类错误率控制如何?能否给出 Berry-Esseen 型界或 Edgeworth 展开?(扎根于定理 3 的证明,作者仅证明了渐近有效性。)
  2. 嵌入维度的选择:\(d\) 的选择在定理 1 中依赖于特征值衰减速率(\(\alpha\) 或 \(\tau\)),但实际中 \(\alpha\) 和 \(\tau\) 未知。是否存在数据驱动的 \(d\) 选择准则(如拐点法或交叉验证)?(扎根于定理 1 的 \(d\) 条件。)
  3. 非通用核的检验:如果 LPRG 的生成核 \(K\) 不是通用的(如线性核),\(gCov = 0\) 是否仍等价于独立性?若不等价,检验的零假设应如何修正?(扎根于定理 2 的通用核假设。)
  4. 稀疏图的极限:当 \(\rho_n = o(\log n / n)\) 时,ASE 的收敛性是否仍然成立?是否存在类似随机块模型中的相变现象?(扎根于定理 5 的假设 3。)
  5. 更一般的图模型:本文的框架能否推广到加权图、有向图或多层图?LPRG 模型假设边独立,若边之间存在依赖(如三角形结构),检验是否仍然有效?(扎根于 LPRG 模型的定义。)

提示:要确认上述问题是否为真 gap,建议去读近 5 年关于图独立性检验的文献(如 Journal of Machine Learning Research 和 Annals of Statistics 上的相关论文),看是否已有工作解决了这些问题。如果多篇文献都指向同一问题,那很可能是共识性的开放问题;如果各文献给出的答案互相矛盾,那可能是一个值得深挖的争议点。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论