【CS224W】(task2)传统图机器学习和特征工程

2023-02-12 12:48 345人阅读评论(0)

note

Traditional ML Pipeline
- Hand-crafted feature + ML model
Hand-crafted features for graph data
- Node-level:
  - Node degree, centrality, clustering coefficient, graphlets
- Link-level:
  - Distance-based feature
  - local/global neighborhood overlap
- Graph-level:
  - Graphlet kernel, WL kernel

一、前言

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

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

二、Traditional Feature-based Methods: Node

2.1 节点的特征

半监督学习：如上图的节点分类，预测灰色点时属于红色点还是绿色点。
特征抽取目标：找到能够描述节点在网络中结构与位置的特征
节点的度数：缺点是节点的所有邻居节点的重要程度都相同

2.2 node centrality

node centrality：考虑了节点的重要性

（1）eigenvector 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{A} \mathbf{c}$ ，其中 $A$ 是邻接矩阵，c是centralty向量，即特征向量。根据Perron-Frobenius Theorem知最大的特征值总为正且唯一，对应的c为centrality向量

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

2.3 clustering coefficient

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

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

2.4 graphlets 有根连通异构子图

Graphlet Degree Vector (GDV): Graphlet-base features for nodes
GDV与其他两种描述节点结构的特征的区别：
Degree counts #(edges) that a node touches
Clustering coefficient counts #(triangles) that a node touches.
GDV counts #(graphlets) that a node touches
Graphlet Degree Vector (GDV): A count vector of graphslets rooted at a given node.

2.5 思考题

（1）扩展阅读

https://www.geeksforgeeks.org/eigenvector-centrality-centrality-measure

https://www.jsums.edu/nmeghanathan/files/2015/08/CSC641-Fall2015-Module-2-Centrality-Measures.pdf?x61976

https://aksakalli.github.io/2017/07/17/network-centrality-measures-and-their-visualization.html

上海地铁线路图：http://www.shmetro.com

上海地铁时刻表：http://service.shmetro.com/hcskb/index.htm

北京地铁线路图：https://map.bjsubway.com

北京地铁时刻表：https://www.bjsubway.com/station/smcsj

https://hal.archives-ouvertes.fr/hal-01764253v2/document

NetworkX-常用图数据挖掘算法：https://networkx.org/documentation/stable/reference/algorithms/index.html

NetworkX-节点重要度算法：https://networkx.org/documentation/stable/reference/algorithms/centrality.html

NetworkX-Clustering算法：https://networkx.org/documentation/stable/reference/algorithms/clustering.html

NetworkX-最短路径算法：https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html

（2）思考题

节点层面，存在哪些数据挖掘任务，有何应用场景？

“传统图机器学习方法”传统在何处？

特征工程在数据挖掘中有什么作用？

在传统图机器学习中，为什么要对节点、连接、全图做特征工程？

传统图机器学习方法相比图神经网络（深度学习），有什么优点和缺点？

节点层面可以构造哪些特征？这些特征可以归为哪两类？

简述不同的Node Centrality计算方法

只用Node Degree作为节点重要度，会有什么缺点？

Eigenvector centrality和PageRank有什么异同？

Betweenness Centrality和Closeness Centrality有什么区别？分别揭示了节点是什么特征？

你认为所有海峡中，哪个海峡的Betweenness Centrality最高？

你认为中国所有城市中，哪个城市的Closeness Centrality最高？

湖北到中国任何一个省级行政区，最多跨两个省，说明哪个特征高？

你认为你所在城市的地铁站中，哪个地铁站的Closeness Centrality最高？哪个地铁站的Clutering Coefficient最高？

地铁线路连接关系，应该如何表示？（邻接矩阵、连接列表、邻接列表）

你认为你的人脉圈中，谁的Clutering Coefficient最高？为什么？

什么是Ego-Network（自我中心网络）？

Graphlet和Wavelet（小波分析）有什么异同？

由四个节点组成的图，存在多少种Graphlet？

五个节点构造的所有Graphlet中，存在多少种不同角色的节点？

节点的哪些特征，可以衡量该节点是否为中心枢纽节点？桥接节点？边缘孤立节点？

除了课程中讲的Centrality之外，还有哪些Centrality指标？（PageRank、Katz Centrality、HITS Hubs and Authorities）

（3）小结

节点级别的特征：

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

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

三、Traditional Feature-based Methods: Link

3.1 链接预测任务

任务：基于已知边，预测新边的类别。测试模型时：将每一对没有连接的节点对进行排序，取存在连接概率最高的topK个节点对，作为预测的结果。

两种类型：随机缺失边、随时间演化边
- 第一种：比如研究发现蛋白质之间的交互作用
- 第二种：社交网络，随时间迁移，认识更多人

3.2 捕获节点的共同邻居数

common neighbors的问题在于度数高的点对就会有更高的结果；
Jaccard’s coefficient是其归一化后的结果。