双曲空间嵌入（Hyperbolic Embedding）的原理与优化求解过程
题目描述
双曲空间是一种具有恒定负曲率的非欧几里得几何空间。与常见的欧几里得空间（如我们日常感知的平面或三维空间）相比，双曲空间具有一个关键性质：随着半径的增长，其周长和面积呈指数级增长。这意味着在双曲空间中，距离中心越远，可容纳的“空间”就越大。许多现实世界的复杂网络（如社交网络、知识图谱、生物网络）具有类似的树状或层次结构，它们在欧几里得空间中难以高效表示（需要极高的维度），而在双曲空间中可以用低维嵌入更自然地保持其结构和距离关系。
本题将详细讲解如何将离散的图数据（如树状结构）嵌入到双曲空间中，包括：
- 双曲空间的数学表示：重点介绍庞加莱圆盘模型。
- 双曲距离的定义与性质：解释为何它能有效建模层次结构。
- 嵌入的优化目标：如何定义损失函数来衡量嵌入质量。
- 优化求解过程：如何在双曲流形上进行梯度下降。
解题过程
第一步：理解双曲空间的几何表示——庞加莱圆盘模型
由于双曲空间不能像欧几里得空间那样直观地在平面上绘制，我们通常使用一个模型来在欧几里得空间中表示它。最常用的是庞加莱圆盘模型。
- 模型范围：它将整个双曲平面映射到一个单位圆盘内（半径为1的圆）。
- 边界意义：圆盘的边界代表“无穷远”。在双曲空间中的无限远处，对应到圆盘模型的边界。
- 点的表示：双曲空间中的一个点，用圆盘内的一个二维（或更高维）欧几里得坐标 u 来表示。
- 关键特点：在圆盘中心附近，几何性质近似欧几里得；越靠近边界，距离的“拉伸”效应越强，这与双曲空间的指数增长特性相对应。
第二步：定义双曲空间中的距离
在庞加莱圆盘模型中，给定两个点 u 和 v（都在单位圆盘内），它们之间的双曲距离计算公式为：
\[d_H(\mathbf{u}, \mathbf{v}) = \text{arcosh} \left( 1 + 2 \frac{\|\mathbf{u} - \mathbf{v}\|^2}{(1 - \|\mathbf{u}\|^2)(1 - \|\mathbf{v}\|^2)} \right) \]
其中：
- \(\| \cdot \|\) 表示标准的欧几里得范数（L2范数）。
- \(\text{arcosh}(x) = \ln(x + \sqrt{x^2 - 1})\) 是反双曲余弦函数。
- 公式解读：
- 分子 \(\|\mathbf{u} - \mathbf{v}\|^2\) 衡量了欧几里得空间中的直接“直线”距离。
- 分母 \((1 - \|\mathbf{u}\|^2)\) 和 \((1 - \|\mathbf{v}\|^2)\) 称为共形因子。一个点越靠近边界（\(\|\mathbf{u}\|\) 越接近1），这个分母越接近0，整个分数值会变得非常大。
- 这导致了一个重要性质：即使两个点在欧几里得视角下离得很近（靠近边界），只要它们本身非常靠近边界，它们的双曲距离 \(d_H\) 仍然可以非常大。这完美模拟了树状结构中，两个底层叶子节点可能“看起来”在末端相近，但追溯到根节点的路径却很长。
第三步：定义嵌入的优化目标（损失函数）
我们的目标是将一个图 \(G=(V, E)\) 的节点嵌入到庞加莱圆盘中。我们希望：
- 相连的节点（有边） 在双曲空间中距离较近。
- 不相连的节点（无边） 在双曲空间中距离较远。
一种常见的方法是使用基于距离的损失函数，如带负采样的最大间隔损失或似然损失。
这里介绍一种基于双曲距离的对比损失（例如使用Softmax形式的负采样）：
对于图中每条边 \((u, v) \in E\)：
- 正样本：节点对 \((u, v)\)。
- 负样本：为节点 \(u\) 随机采样一组不与它直接相连的节点 \(\{ n_1, n_2, ..., n_k \}\)。
我们希望最小化以下损失函数：
\[\mathcal{L} = -\log \frac{\exp(-d_H(\mathbf{u}, \mathbf{v}))}{\exp(-d_H(\mathbf{u}, \mathbf{v})) + \sum_{i=1}^{k} \exp(-d_H(\mathbf{u}, \mathbf{n}_i))} \]
直观理解：这个损失函数是交叉熵的一种形式。分子鼓励正样本对（相连节点）的双曲距离 \(d_H\) 小（即 \(-d_H\) 大），分母同时惩罚正样本对和所有负样本对。优化过程就是让相连节点的嵌入向量在双曲空间中相互“吸引”，让不相连节点的嵌入向量相互“排斥”。
第四步：在双曲流形上进行优化求解（黎曼优化）
难点在于：我们不能像在欧几里得空间中那样直接对嵌入向量 u 进行普通的梯度下降。因为更新后的新坐标可能跳出单位圆盘（即 \(\|\mathbf{u}\| \geq 1\)），这不再是有效的双曲空间点。
解决方案是使用黎曼优化。核心思想是：在双曲流形（庞加莱圆盘）的每一点上，都有一个与之相切的切空间（这是一个欧几里得空间）。优化步骤如下：
-
计算欧几里得梯度：首先，像在普通空间中一样，计算损失函数 \(\mathcal{L}\) 关于嵌入向量 u 的梯度 \(\nabla_{\text{Euc}} \mathcal{L}\)。这个梯度存在于外围的欧几里得空间中。
-
投影到黎曼梯度：将这个欧几里得梯度投影到当前点 u 所在的切空间上，得到在流形上正确的下降方向，称为黎曼梯度 \(\nabla_{\text{R}} \mathcal{L}\)。对于庞加莱圆盘模型，这个投影操作是：
\[ \nabla_{\text{R}} \mathcal{L} = (1 - \|\mathbf{u}\|^2)^2 \nabla_{\text{Euc}} \mathcal{L} / 4 \]
注意这里除以4是约定俗成的缩放因子。可以看到，**共形因子** $ (1 - \|\mathbf{u}\|^2)^2 $ 再次出现。当点靠近边界时，这个因子会急剧缩小梯度，防止更新步长过大导致点“飞出”圆盘。
- 指数映射（更新参数）：我们不能简单地将 \(\mathbf{u} - \eta \nabla_{\text{R}} \mathcal{L}\) 作为新点，因为这种线性减法是在切空间中进行的。我们需要使用指数映射操作，将切空间中的向量（即更新方向 \(-\eta \nabla_{\text{R}} \mathcal{L}\) ）映射回双曲流形上，得到新的嵌入点 \(\mathbf{u}_{\text{new}}\)。
庞加莱圆盘模型的指数映射有一个闭合形式解。假设当前点为 u，切向量为 v（即 \(-\eta \nabla_{\text{R}} \mathcal{L}\) ），则更新公式为：
\[ \mathbf{u}_{\text{new}} = \mathbf{u} \oplus \left( \tanh(\lambda_{\mathbf{u}} \frac{\| \mathbf{v} \|}{2}) \frac{\mathbf{v}}{\| \mathbf{v} \|} \right) \]
其中 $ \oplus $ 是庞加莱圆盘中的**莫比乌斯加法**（一种非线性的“加法”），$ \lambda_{\mathbf{u}} = 2/(1 - \|\mathbf{u}\|^2) $ 是**利普希茨因子**。这个复杂的公式确保了无论更新步长多大，新点 $ \mathbf{u}_{\text{new}} $ 始终停留在单位圆盘内。
- 迭代：重复步骤1-3，直到损失函数收敛或达到预设的迭代次数。
总结过程
- 初始化：将图中所有节点的嵌入向量随机初始化为庞加莱单位圆盘内的小值（例如从均匀分布中采样并缩放）。
- 构造批数据：从图中采样一批边作为正样本，并为每条边采样多个负样本节点。
- 前向传播：对于这批数据，利用公式计算所有相关节点对的双曲距离 \(d_H\)。
- 计算损失：根据定义的距离对比损失函数计算当前批的损失值。
- 反向传播与黎曼优化：
- 计算欧几里得梯度。
- 将其投影为黎曼梯度。
- 通过指数映射更新所有节点的嵌入向量。
- 循环：回到第2步，直到模型收敛。
最终，我们得到每个节点在庞加莱圆盘中的一个低维向量表示。在嵌入空间中，具有相似祖先或处于同一子树中的节点会聚集在一起，而高层级（靠近根节点）的节点会更靠近圆盘中心，低层级（叶子节点）的节点则分布在圆盘外围。这种嵌入能够以极高的效率（用二维或三维）捕捉和可视化复杂的层次结构信息。