【强基固本】传统图机器学习特征提取方法 -- 基于节点水平的特征（Node-level）

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

来源：知乎—葱鸭Fighting

地址：https://zhuanlan.zhihu.com/p/413568865

在传统机器学习方法的pipeline中，我们需要手动地抽取一系列特征组合成特征向量    ，并将该特征向量    与标签    作为输入来训练机器学习模型，如随机森林、SVM、前馈神经网络等等。图网络数据作为一种特殊的数据结构，其既包含了节点自身的信息，又包含了网络拓扑结构信息，那么，针对图网络结构的数据有哪些传统有效的特征提取方法？本文将结合斯坦福大学CS224W课程第四讲内容，介绍传统的基于节点水平（Node-level）的图网络数据特征提取方法。

官方油管课程视频链接：

https://youtu.be/3IS7UhNMQ3U

01

基于节点水平的特征（Node-Level Features）

传统的节点水平的图网络特征可大致分为两类：
（1）基于节点重要性的特征，衡量了某节点在网络中的重要程度，如：节点度，节点中心性度量；
（2）基于结构的特征，能够捕捉节点周围领域的拓扑属性，如：节点度，聚类系数，图元度向量（GDV，graphlet degree vector）

接下来我们对节点度，中心性，聚类系数，以及GDV等概念进行详细介绍。

1. 节点度（Node Degree）

节点度，即对节点邻居个数的计数，或是与节点连接的边的条数。当图为有向图时，节点度又可分为入度（in-degree）与出度（out-degree）。值得注意的是，节点度捕捉到的信息默认了每一个邻居节点信息都是平等的。

2. 节点中心性（Node Centrality）

节点的中心性指标有多种，它们从不同角度衡量了节点在网络中的重要程度，其中最常用的几个中心性指标分别是：特征向量中心性，中介中心性，接近中心性。

特征向量中心性（eigenvector centrality）

特征向量中心性背后的思想是：若一个节点的邻居节点的重要性高，那么它的重要性也越高。特征向量中心性计算公式    可表示为：

经过一系列的变形，以上计算方法实际上等价于如下定义：设    为网络    的邻接矩阵，通过求解特征方程    我们可以得到特征向量   ，当    为最大特征值时，第    个节点的特征向量中心性即为向量    的第    个元素。

中介中心性（betweenness centrality）

中介中心性又称为最短路径中心性（shortest-path centrality），其思想是：若一个节点在各节点对之间的最短路径上出现次数越多，则其在网络中的重要性越高。用公式可表示为：

接近中心性（closeness centrality）

接近中心性背后的思想是：若一个节点到其他所有节点的最短路径长度越小，那么它在网络中的重要性越高，以公式可表示为：

3. 聚类系数（Clustering Coefficients）

聚类系数衡量了节点的邻居节点之间的连接性高低，若它的邻居节点之间相互连接的越多，则聚类系数越大。设聚类系数为    ，计算公式表示为：

下图以带有5个节点的网络为例，展示了三种不同网络结构下节点  的聚类系数：

聚类系数示例图（图源自CS224W课程）

4. 图元度向量（Graphlet Degree Vector）

图元度向量对事先指定的图元（graphlet）结构进行了计数统计，从而反映了网络的结构特征。在理解图元度向量之前，我们首先要理解图元的概念。

什么是图元？官方给出的图元定义为“有根连通的非同构子图”。简单来说，图元就是若干个节点构成的所有可能的连通图结构，我们以课程中的示例图来进行解释。在下图中我们可以看到，当仅有两个节点时，可能的图元结构只有一种；当有三个节点时，图元结构有两种，可能是线型连接的，或是构成一个三角形（这里值得注意的是，当以不同的节点为根节点时，图元是不同的，例如    结构由于节点连接顺序不同代表了三种图元表示）；以此类推，当考虑4个或5个节点时，构成的图元结构将会更多样。

图元示例图（图源自CS224W课程）

什么是图元度向量？指定图元，图元度向量统计了网络中以给定节点为根的图元个数。以下图为例，网络    中的    是我们要观察的根节点，a-d指定了4种不同的图元结构，以    为根节点对网络G中四种指定的图元结构进行计数统计，各图元出现的次数分别为2,1,0,2，由此我们可以得到节点    的图元度向量为    。

图元度向量示例（图源自CS224W课程）

02

代码实践

Python的第三方库networkx是一个非常实用的网络操作与分析工具，本部分将基于该库进行代码的实践。官方文档指路：

https://networkx.org/documentation/stable/index.html

导入第三方库

# 导入第三方网络分析库 networkx
# 导入绘图库
import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd

导入示例数据集

# 导入networkx自带的网络数据集 karate club 作为示例测试代码
G = nx.karate_club_graph()

# 打印查看网络的基本信息以及可视化
print(nx.info(G))
nx.draw(G, pos=nx.spring_layout(G), with_labels=True)

节点度函数 G.degree(v)

# 打印查看节点度信息
print("Node Degree")
for v in G:
    print(f"{v:4} {G.degree(v):6}")

节点中心性函数

特征向量中心性函数：nx.eigenvector_centrality(G)

中介中心性函数：nx.betweenness_centrality(G)

接近中心性函数：nx.closeness_centrality(G)

# 打印查看各种节点中心性数值
# 各个中心性函数返回的是字典类型数据，key为节点index，value为中心性数值
print("Node centraility")
eigen_dict = nx.eigenvector_centrality(G)
betw_dict = nx.betweenness_centrality(G)
close_dict = nx.closeness_centrality(G)
centrality_df = pd.DataFrame(
    {
     'eigenvector_centrality': [eigen_dict[v] for v in G],
     'betweenness_centrality': [betw_dict[v] for v in G],
     'closeness_centrality': [close_dict[v] for v in G],
    }
)
centrality_df

节点聚类系数函数 nx.clustering(G)

# 打印查看各种节点聚类系数
# 聚类系数函数nx.clustering(G)返回的是字典类型数据，key为节点index，value为聚类系数数值
print("Node Clustering Coefficients")
nx.clustering(G)

运行代码会发现index为7的节点聚类系数为1，表明它的邻居节点应该呈两两之间全部相连接的状态，因此我们可以将7号节点的自我中心网络（ego-network）可视化检查看看是否符合：

ego = nx.ego_graph(G, 7)
nx.draw(ego, pos=nx.spring_layout(ego), with_labels=True)

注：图元度向量（GDV）暂未找到Python代码实现，故本文内容暂不对其进行代码展示

完整代码

见google colab notebook链接：

https://colab.research.google.com/drive/1fpINHRhJmKNCJW7hVKbTZ_o1GR46Kxfq?usp=sharing

03

小结

从本节的内容我们学习到了如何从网络中手动提取节点水平的特征，包含了节点度、中心性、聚类系数，以及图元度向量等概念。试想一下，如果仅考虑节点水平的特征，我们将遗漏掉网络中重要的链接信息，因此，在下一篇文章中，我们将学习网络中基于链接水平的特征提取方法。

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！