【CS224W】(task2)传统图机器学习和特征工程（更新中）

一、前言

除了想获得训练数据中节点or边or图特征数据还有反应节点在网络中位置、局部网络local network structure等特征。

本讲不讲属性特征只讲连接特征。

二、Traditional Feature-based Methods: Node

2.1 节点的特征

• 半监督学习如下图的节点分类
• 特征抽取目标找到能够描述节点在网络中结构与位置的特征
• 节点的度数

2.2 node centrality

• node centrality考虑了节点的重要性
  
  1eigenvector centrality如果当前节点周围有很多重要的邻居节点则可以认为当前节点也是重要的即节点v的centrality是邻居centrality的加和$c_{\mathrm{v}}=\frac{1}{\lambda }{\sum }_{\mathrm{u}\in \mathrm{N}(\mathrm{v})}{\mathrm{c}}_{\mathrm{u}}$其中$\lambda$是某个正常数。
  • 该递归式的解法是转为矩阵形式$\lambda \mathbf{c}=\mathbf{Ac}$其中$A$是邻接矩阵c是centralty向量即特征向量。根据Perron-Frobenius Theorem知最大的特征值总为正且唯一对应的c为centrality向量

2betweenness centrality若该节点在很多节点对的最短路径上则认为该节点重要
3closeness centrality若该节点和其他节点的距离最短则认为该节点重要 如下图所示

2.3 clustering coefficient

衡量节点邻居的连接程度描述节点的局部结构信息。

$\left(\begin{array}{c}{\mathrm{k}}_{\mathrm{v}}\\ 2\end{array}\right)$是组合数的写法表示v邻居所构成的节点对即潜在的连接数衡量节点邻居的连接有多紧密如上图中ev=6/6。

2.4 graphlets 有根连通异构子图

2.5 小结

节点级别的特征

• importance-based features捕获节点在图中的重要性
  • 节点度数
  • 不同的节点centrality衡量方法

• struture-based features捕获节点附近的拓扑属性
  

三、Traditional Feature-based Methods: Link

四、Traditional Feature-based Methods: Graph

Reference

[1] 传统图机器学习的特征工程-节点【斯坦福CS224W】
[2] cs224w图机器学习2021冬季课程学习笔记2: Traditional Methods for ML on Graphs
[3] NetworkX入门教程
[4] https://github.com/TommyZihao/zihao_course/tree/main/CS224W
[5] 斯坦福官方课程https://web.stanford.edu/class/cs224w/