2-传统图机器学习和特征工程

节点

连接

全图

子豪兄参考

同济子豪兄 2023-1-10

同济子豪兄中文精讲视频：

• 节点特征工程：https://www.bilibili.com/video/BV1HK411175s

• 连接特征工程：https://www.bilibili.com/video/BV1r3411m7sD

• 全图特征工程：https://www.bilibili.com/video/BV14W4y1V7gg

• 斯坦福原版视频：

  • https://www.youtube.com/watch?v=3IS7UhNMQ3U&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=4

  • https://www.youtube.com/watch?v=4dVwlE9jYxY&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=5

  • https://www.youtube.com/watch?v=buzsHTa4Hgs&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=6

节点

扩展阅读

• Eigenvector Centrality (Centrality Measure) - GeeksforGeeks

• Centrality-Measures.pdf

• Network Centrality Measures and Their Visualization

• 上海地铁线路图：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

思考题

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

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

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

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

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

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

7. 简述不同的Node Centrality计算方法

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

9. Eigenvector centrality和PageRank有什么异同？

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

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

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

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

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

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

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

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

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

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

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

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

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

连接

扩展阅读

NetworkX相关文档

• https://networkx.org/documentation/stable/reference/generated/networkx.classes.function.common_neighbors.html

• https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_prediction.jaccard_coefficient.html

• https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_prediction.adamic_adar_index.html

• https://stackoverflow.com/questions/62069781/how-to-find-the-similarity-between-pair-of-vertices-using-katz-index-in-python

思考题

1. 连接层面，存在哪些数据挖掘任务，有何应用场景？

2. 连接层面可以构造哪些特征？这些特征可以归为哪三类？

3. 简述Link Prediction的基本流程

4. A和B都知道梅西，C和D都知道同济子豪兄，请问哪对人物更容易产生社交连接。可以用哪个特征解释？

5. 两个节点没有共同好友时，可以用什么特征，将连接编码为D维向量？

6. 简述Katz Index的算法原理

7. 如何计算节点U和节点V之间，长度为K的路径个数

8. 为什么不直接把link两端节点的向量特征concat到一起，作为link的向量特征

全图

扩展阅读

weisfeiler_lehman_graph_hash

思考题

1. 全图层面，存在哪些数据挖掘任务，有何应用场景？

2. 全图层面可以构造哪些特征？

3. 全图层面的Graphlet，和节点层面的Graphlet，有什么区别？

4. 子图匹配，算法复杂度如何计算？

5. 简述Weisfeiler-Lehman Kernel的算法原理

6. Weisfeiler-Lehman Kernel的词汇表（颜色表）是如何构建的？

7. Weisfeiler-Lehman Kernel，算法复杂度是多少？

8. Weisfeiler-Lehman Kernel和图神经网络（GNN）有什么关系？

9. 简述Kernel Methods基本原理

10. 为什么在Graph-level任务中，使用Kernel Methods

11. 除了Graphlet Kernel和Weisfeiler-Lehman Kernel之外，还有哪些Kernel

12. 传统图机器学习和特征工程中，哪些特征用到了邻接矩阵Adjacency Matrix？

13. 如何把无向图节点、连接、全图的特征，推广到有向图？

14. 如何用代码实现Weisfeiler-Lehman Kernel？