数学推导与算法

一、贝蒂数的秩公式

$k$ 维链群 $C_k$ 是以 $k$-单纯形为基的向量空间（维数 $n_k$），边界算子 $\partial_k:C_k\to C_{k-1}$ 的矩阵即 $B_k$。由 $\partial_{k}\partial_{k+1}=0$，有 $\mathrm{im}\,\partial_{k+1}\subseteq\ker\partial_k$，同调群 $H_k=\ker\partial_k/\mathrm{im}\,\partial_{k+1}$，其维数

$$\beta_k=\dim\ker B_k-\operatorname{rank}B_{k+1}=(n_k-\operatorname{rank}B_k)-\operatorname{rank}B_{k+1}.$$

霍奇分解：$C_k=\mathrm{im}\,B_{k+1}\oplus\mathrm{im}\,B_k^{\top}\oplus\ker L_k$，三部分两两正交。由于 $L_k=B_k^{\top}B_k+B_{k+1}B_{k+1}^{\top}$ 是两个半正定矩阵之和，$L_kx=0$ 当且仅当 $B_kx=0$ 且 $B_{k+1}^{\top}x=0$，因此 $\dim\ker L_k=\beta_k$。对 $k=1$，$\ker L_1$ 中的向量是边上的“调和流”：既无源汇（$B_1x=0$，散度为零），也不能写成三角形的边界（$B_2^{\top}x=0$，旋度为零），它们恰好绕着“洞”流动。

计算复杂度：基于矩阵秩的方法在单纯形数目 $n$ 上为 $O(n^3)$；持续同调的标准算法是对按过滤顺序排列的边界矩阵做列约简，最坏情况同为立方复杂度，实践中通常接近线性。团复形中三角形数目可达 $O(N^3)$，这是 TDA 只适用于中小规模网络或需要稀疏化的原因。

二、超拉普拉斯矩阵的两个极限

多重网络上节点–层 $(i,\alpha)$ 的状态 $x_{i\alpha}$ 满足

$$\dot{x}_{i\alpha}=\sum_j A^{[\alpha]}_{ij}(x_{j\alpha}-x_{i\alpha})+D_x\sum_{\beta\ne\alpha}(x_{i\beta}-x_{i\alpha}),$$

即 $\dot{x}=-\mathcal{L}x$，$\mathcal{L}=\bigoplus_\alpha L^{[\alpha]}+D_x\,(L_{\text{layer}}\otimes I_N)$，两层时 $L_{\text{layer}}=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$。

• 小 $D_x$：取 $x=(\mathbf{1}_N,-\mathbf{1}_N)$。由于 $L^{[\alpha]}\mathbf 1=0$，直接计算得 $\mathcal{L}x=(2D_x\mathbf 1_N,-2D_x\mathbf 1_N)=2D_x\,x$，所以 $2D_x$ 总是 $\mathcal{L}$ 的一个特征值，且该特征向量与 $\mathbf 1_{2N}$ 正交，故 $\lambda_2\le2D_x$。用瑞利商同样可得：层内项为 0，层间项为 $D_x\sum_i(1-(-1))^2=4ND_x$，除以 $x^{\top}x=2N$ 得 $2D_x$。当 $D_x$ 足够小时 $\lambda_2=2D_x$（Gómez 等，2013）。
• 大 $D_x$：层间耦合迫使 $x_{i1}\approx x_{i2}$，令 $x_{i1}=x_{i2}=y_i$，限制在这个子空间上的瑞利商为 $\frac{y^{\top}(L^{[1]}+L^{[2]})y}{2y^{\top}y}$，因此 $\lambda_2\to\lambda_2\big((L^{[1]}+L^{[2]})/2\big)$。由于 $\lambda_2$ 是凹函数（瑞利商最小值），$\lambda_2\big(\tfrac{L^{[1]}+L^{[2]}}{2}\big)\ge\tfrac12\big(\lambda_2(L^{[1]})+\lambda_2(L^{[2]})\big)$，可以超过任一单层。

三、时间一致可达性的扫描算法

把接触按时间排序，维护布尔矩阵 $R$（$R_{ij}=1$ 表示从 $i$ 出发的信息已能到达 $j$），初始 $R=I$。每遇到一次无向接触 $(u,v,t)$：

$$R_{\cdot u}\leftarrow R_{\cdot u}\lor R_{\cdot v},\qquad R_{\cdot v}\leftarrow R_{\cdot u}\lor R_{\cdot v}.$$

扫描结束时 $R$ 即为可达矩阵。复杂度 $O(N\cdot M)$（$M$ 为接触数）。同一时刻的多次接触需要约定处理顺序（或限制每个时间步只传一步），这一约定会影响结果，应在方法中写明。

四、拉普拉斯特征映射

目标 $\sum_{ij}W_{ij}\|y_i-y_j\|^2=2\,\mathrm{tr}(Y^{\top}LY)$。在约束 $Y^{\top}DY=I$ 下引入拉格朗日乘子，驻点条件为 $LY=DY\Lambda$，即广义特征值问题 $Ly=\lambda Dy$。令 $u=D^{1/2}y$，等价于对称归一化拉普拉斯 $\mathcal{L}_{\text{sym}}=D^{-1/2}LD^{-1/2}$ 的普通特征值问题 $\mathcal{L}_{\text{sym}}u=\lambda u$。最小特征值 0 对应常向量 $y=\mathbf 1$（平凡解），取接下来的 $d$ 个特征向量作为 $d$ 维嵌入。代码示例使用 $\mathcal{L}_{\text{sym}}$ 的特征向量 $u$；如需严格对应上式，可再左乘 $D^{-1/2}$。

五、从谱图卷积到 GCN

谱图卷积把信号 $x$ 变换到拉普拉斯 $\mathcal{L}_{\text{sym}}=U\Lambda U^{\top}$ 的特征基上滤波：$g_\theta\star x=Ug_\theta(\Lambda)U^{\top}x$。为避免特征分解，用切比雪夫多项式近似 $g_\theta$；Kipf 与 Welling（2017）取一阶近似并设 $\lambda_{\max}\approx2$：

$$g_\theta\star x\approx\theta_0x+\theta_1(\mathcal{L}_{\text{sym}}-I)x=\theta_0x-\theta_1D^{-1/2}AD^{-1/2}x .$$

再令 $\theta=\theta_0=-\theta_1$ 减少参数，得到 $\theta(I+D^{-1/2}AD^{-1/2})x$。矩阵 $I+D^{-1/2}AD^{-1/2}$ 的特征值在 $[0,2]$ 内，多层堆叠时可能导致数值不稳定，于是采用重归一化技巧，以 $\tilde{A}=A+I$、$\tilde{D}_{ii}=\sum_j\tilde{A}_{ij}$ 代替，得到 $\hat{A}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$，其特征值在 $(-1,1]$ 内。多通道输入与输出时即 $H^{(l+1)}=\sigma(\hat{A}H^{(l)}W^{(l)})$。

过平滑的谱解释：$\hat{A}$ 是对称矩阵，最大特征值为 1，对应特征向量 $u_1\propto\tilde{D}^{1/2}\mathbf 1$；若图连通且非二部，其余特征值 $|\mu_i|<1$。于是 $\hat{A}^kX=u_1u_1^{\top}X+\sum_{i\ge2}\mu_i^k u_iu_i^{\top}X$，第二项按 $|\mu_2|^k$ 衰减。代码示例中 $|\mu_2|\approx0.76$，32 层后剩余部分约为 $0.756^{32}\approx1.3\times10^{-4}$，与数值结果（$2\times10^{-4}$）量级一致。

六、GCN 训练的梯度（两层、交叉熵）

记 $Z_1=\hat{A}XW_1$，$H_1=\mathrm{ReLU}(Z_1)$，$Z_2=\hat{A}H_1W_2$，$P=\mathrm{softmax}(Z_2)$，损失只在已标注节点集合 $\mathcal{Y}_L$ 上计算：$\mathcal{J}=-\frac{1}{|\mathcal{Y}_L|}\sum_{v\in\mathcal{Y}_L}\log P_{v,y_v}$。则

$$\frac{\partial\mathcal{J}}{\partial Z_2}=\frac{M(P-Y)}{|\mathcal{Y}_L|},\quad \frac{\partial\mathcal{J}}{\partial W_2}=(\hat{A}H_1)^{\top}\frac{\partial\mathcal{J}}{\partial Z_2},\quad \frac{\partial\mathcal{J}}{\partial W_1}=(\hat{A}X)^{\top}\Big[\Big(\hat{A}^{\top}\frac{\partial\mathcal{J}}{\partial Z_2}W_2^{\top}\Big)\odot\mathbf{1}(Z_1>0)\Big],$$

其中 $M$ 是只保留已标注行的对角掩码矩阵。注意未标注节点虽然不贡献损失，却通过 $\hat{A}$ 参与前向传播——这正是“半监督”的含义，也是图上的数据泄漏容易发生的地方：测试节点的特征在训练时已被邻居“看到”。