图特征工程：从图结构到机器学习特征

在图机器学习与网络分析中，原始图数据（节点与边）无法直接被大多数模型使用。图特征工程的目标就是将图中的结构信息、节点属性以及连接模式转换成可供模型学习的数值型特征。本教程聚焦三大核心维度：节点中心度、节点嵌入与结构指标，帮助你系统地构建图特征体系。

1. 节点中心度：谁在图中更重要？

节点中心度衡量节点在图中的“重要性”，不同定义揭示不同的角色。以下是必备的几类中心度指标。

1.1 度中心度 (Degree Centrality)

• 定义：节点的直接邻居数（无向图为度，有向图分为入度与出度）。
• 解释：度越高，节点越“活跃”或“流行”。在社交网络中，高度节点往往是交际枢纽。
• 计算公式： [ C_D(v) = \deg(v) ] 归一化版本除以最大可能度：( C'_D(v) = \frac{\deg(v)}{n-1} )，其中 (n) 为节点总数。
• 注意事项：度中心度只考虑局部结构，容易忽略节点所处的位置深度。

1.2 接近中心度 (Closeness Centrality)

• 定义：节点到图中所有其他节点的平均最短路径距离的倒数。
• 解释：接近中心度高的节点能更快地（通过较短路径）到达整个网络，处于信息传播的优势位置。
• 计算公式： [ C_C(v) = \frac{n-1}{\sum_{u \neq v} d(v,u)} ] 其中 (d(v,u)) 是 (v) 到 (u) 的最短路径长度。
• 局限性：对图是否连通高度敏感。非连通图中可采用“调和中心度”，仅对可达节点求和后取倒数。

1.3 中介中心度 (Betweenness Centrality)

• 定义：节点位于其他节点对之间最短路径上的频次。
• 解释：高中介中心度的节点扮演“桥梁”角色，控制着网络中的信息流。如果移除这类节点，很多节点对之间的距离会增加。
• 计算公式： [ C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}} ] 其中 (\sigma_{st}) 是 (s) 到 (t) 的最短路径总数，(\sigma_{st}(v)) 是经过 (v) 的最短路径数。
• 工程优化：精确计算全图中介中心度复杂度高（O(n³) 或 O(nm)），大规模图可使用近似算法（如基于采样的方法）。

1.4 特征向量中心度 (Eigenvector Centrality)

• 定义：节点的重要性不仅取决于自身有多少邻居，还取决于邻居的重要性。
• 解释：与重要节点相连的节点也会变得重要。谷歌的 PageRank 是其变体。
• 核心思想：求解邻接矩阵最大特征值对应的特征向量： [ \lambda x = A x ] 节点 (v) 的中心度为 (x_v)。
• 变种：PageRank 引入随机跳转概率，解决了出度为0导致的悬空节点问题，更适合有向图。

1.5 实用小结

通常将上述多个中心度组合为一组特征，可全面刻画节点的结构地位。

2. 节点嵌入：学习图的低维表示

中心度是人工定义的特征，而节点嵌入通过无监督或半监督学习，将节点映射到稠密低维向量空间，并保持图的结构信息（如同质性或结构等价性）。嵌入向量可直接作为下游任务的输入。

2.1 基于随机游走的方法

DeepWalk

• 原理：在图上执行均匀随机游走生成节点序列，再借用 Word2Vec (Skip-gram) 学习节点共现关系。
• 核心思想：将图视为“语言”，节点序列视为“句子”，使频繁共同出现的节点获得相近向量。
• 关键参数：游走长度、每个节点的游走次数、窗口大小、嵌入维度。

node2vec

• 改进：设计有偏随机游走，通过返回参数 (p) 和进出参数 (q) 在 BFS（宽度优先） 与 DFS（深度优先） 之间取得平衡。
• 同质性 (DFS倾向)：相连节点嵌入相似。
• 结构等价性 (BFS倾向)：扮演相似局部角色的节点嵌入相似。
• 实际选择：若需捕捉功能或连接性，增大 (q)；若看重结构角色，减小 (q)。

2.2 谱域与空间域图神经网络嵌入

图卷积网络 (GCN)

• 方法：通过聚合邻居特征的层叠操作学习节点表示。
• 典型层传播规则： [ H^{(l+1)} = \sigma\left( \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)} \right) ] 其中 (\tilde{A} = A + I)，(\tilde{D}) 为对应的度矩阵。
• 适用场景：节点分类、链接预测等半监督任务。

GraphSAGE

• 亮点：归纳式学习，可泛化到未见过的节点。通过采样邻居并聚合（均值、池化、LSTM等方式）生成嵌入。
• 技术优势：避免全图计算，适合超大图。

2.3 选择嵌入方法的判断清单

• 数据规模：小型图（<1M节点）可用 node2vec；极大规模图优先考虑 GraphSAGE 等采样方法。
• 任务监督信号：若标签较少，先采用无监督随机游走嵌入；若标签充分，端到端 GCN 可能更优。
• 图属性变化：动态图需增量嵌入 (如 DyGNN)；异构图需使用元路径感知模型 (如 metapath2vec)。

3. 结构指标：精细调节的局部与全局特征

除了中心度和嵌入，还有大量可直接计算的结构特征，对异常检测、角色发现等场景价值极高。

3.1 局部结构特征

聚类系数 (Clustering Coefficient)

• 定义：节点的邻居之间实际存在的边数与可能最大边数之比。
• 公式（无向图）： [ CC(v) = \frac{2 \cdot t(v)}{\deg(v)(\deg(v)-1)} ] 其中 (t(v)) 是 (v) 邻居间的闭合三元组数量。
• 意义：高聚类系数说明节点处于紧密的小团体中。整个图的平均聚类系数常作为全局特征。

三角参与与模体 (Motifs)

• 思路：统计节点参与特定子图模式（如三角形、星型、有向反馈环）的频率。
• 应用：构成节点的高阶特征向量，用于分类功能性角色。

3.2 全局/图级别特征

图密度与平均路径长度

• 密度：( \frac{2m}{n(n-1)} )，反映图的疏密程度。
• 平均路径长度：所有节点对最短路径的平均值，衡量网络的小世界特性。

模块度 (Modularity)

• 定义：衡量社区划分质量的指标，亦可生成单个节点对其所属社区的贡献程度作为特征。
• 用途：比较不同分区下节点的模块度值，分析节点的社区内聚倾向。

3.3 结构特征组合思路

4. 特征工程实战策略

4.1 避免特征冗余

中心度之间往往高度相关。在添加新特征前，计算皮尔逊相关系数矩阵，使用主成分分析 (PCA) 或根据下游任务的重要性 (如基于树模型的特征重要性) 进行筛选。

4.2 特征归一化

中心度指标取值量级差异大（如度可能为1~1000，中介中心度可能极小）。务必对连续特征做标准化 (z-score) 或 min-max 缩放，尤其当使用基于距离的模型（KNN、SVM）时。

4.3 与嵌入向量融合

可将手工中心度特征与学习到的嵌入向量拼接使用。例如，对每个节点构建特征向量： [ \text{features}(v) = [\deg(v), C_B(v), CC(v), \text{emb}_1, \text{emb}_2, ..., \text{emb}_d] ] 但需注意，嵌入可能已隐式编码部分中心度信息，融合时最好采用加权或注意力机制。

4.4 时序图特征

图随时间变化时，需考虑时间切片特征：瞬时度、滑窗聚合的节点交互次数、中心度的变化率等。嵌入方面可选用时间随机游走或动态图神经网络。

5. 常用工具与库

• NetworkX (Python)：丰富的中心度与结构指标计算，适合中小规模图。
• igraph (R/Python/C)：性能优异，支持大型图的高效计算。
• PyTorch Geometric (PyG) / DGL：实现 GCN、GraphSAGE、node2vec 等深度学习嵌入。
• Platypus 或 Karate Club：涵盖图嵌入算法集合，API简洁。

总结

图特征工程不是单一公式，而是一个从图结构提炼信息的系统流程：

• 中心度给出显式、可解释的重要性得分。
• 嵌入提供稠密的、可训练的表示，适合复杂模式挖掘。
• 结构指标补充局部团簇和全局拓扑特征。

根据任务需求，合理组合这三类特征，并持续通过验证评估其效果，是构建高质量图机器学习模型的关键。