图嵌入 图嵌入是将图结构数据（节点和边）映射到低维向量空间的方法，同时尽可能保留图的拓扑属性、节点关系或其他特征。其核心思想是为每个节点学习一个低维向量表示，使得在原始图中相似的节点在嵌入空间中的向量也相似。 1. 图嵌入的基本动机 图数据广泛存在于社交网络、分子结构、知识图谱等领域，但图本身是非欧几里得结构，难以直接用传统机器学习算法（如神经网络、聚类算法）处理。 图嵌入通过将节点转换为连续向量，使得节点关系可被量化计算（如向量距离或内积），从而支持节点分类、链接预测、图聚类等任务。 2. 关键问题与设计目标 保留何种信息 ：嵌入需权衡保留图的局部结构（如一阶邻近性，即直接相连的节点应靠近）或全局结构（如高阶邻近性，即具有相似邻居的节点应靠近）。 ** scalability** ：算法需适应大规模图（如百万级节点）。 嵌入维度 ：向量维度需足够低以节省计算资源，同时足够高以保留必要信息。 3. 经典方法：基于矩阵分解 思想：将图的结构信息（如邻接矩阵、拉普拉斯矩阵）分解为低维向量表示。 示例： 拉普拉斯特征映射（Laplacian Eigenmaps） 步骤： 构建图的拉普拉斯矩阵 \( L = D - A \)，其中 \( A \) 为邻接矩阵，\( D \) 为度矩阵。 求解广义特征值问题 \( L \mathbf{x} = \lambda D \mathbf{x} \)。 取最小的 \( k \) 个非零特征值对应的特征向量，构成节点的 \( k \) 维嵌入。 原理：最小化相邻节点嵌入的平方距离，保留局部相似性。 4. 基于随机游走的方法 思想：通过模拟图中随机游走生成节点序列，将序列视为"句子"，用自然语言处理中的词嵌入技术（如Word2Vec）学习节点向量。 示例： DeepWalk 步骤： 从每个节点出发进行多次固定长度的随机游走。 将游走得到的节点序列作为语料库。 使用Skip-gram模型学习节点向量，最大化序列中共现节点的概率。 优势：捕获高阶邻近性，适应稀疏图。 5. 基于神经网络的方法 思想：利用图卷积网络（GCN）等深度学习模型聚合邻居信息，生成节点嵌入。 示例： GraphSAGE 步骤： 对每个节点采样固定数量的邻居。 通过聚合函数（如均值、LSTM）融合邻居特征。 多层聚合后输出节点嵌入。 特点：支持归纳学习（可处理未见过的新节点）。 6. 应用与评估 常见任务： 节点分类 ：用嵌入向量预测节点标签。 链接预测 ：计算节点向量相似度预测缺失边。 可视化 ：将嵌入降维至2D/3D空间展示图结构。 评估指标：使用分类准确率、AUC-ROC等，与任务相关。 7. 挑战与前沿 动态图嵌入：处理随时间变化的图结构。 异构图嵌入：处理含多种节点/边类型的图。 可解释性：理解嵌入向量的实际含义。