目录
- 一.Review
- 二.Traditional Feature-based Methods: Node
- 三、Traditional Feature-based Methods: Link
- 四、Traditional Feature-based Methods: Graph
- 五、本章小结
一.Review
- 图预测：节点预测、边预测和图预测
- 传统机器学习pipeline：设计并获取所有训练数据上节点/边/图的特征→训练机器学习模型→应用模型
- 图数据本身就会有特征，但是我们还想获得说明其在网络中的位置、其局部网络结构local network structure之类的特征（这些额外的特征描述了网络的拓扑结构，能使预测更加准确）
- 共有两种特征：数据的结构关联特征structural feature以及其本身的节点属性特征attributes and properities
- 传统机器学习的步骤
- 获取数据点、节点、连接等，且他们具有特征向量，对其应用典型机器学习模型（分类器classifier、模型moodel如随机森林random forest、支持向量机support vector machine、前馈神经网络a feed-forword neural network）
- 将数据应用于模型产生新的节点、链表、图等，根据新的节点的特征，可以对其进行预测
- 本节课目标—— 功能设计feature design
- 单个节点用于节点预测
- 一对节点用于连边预测
- 节点之间的结构用于图预测
本节课讨论的内容都是基于无向图，课程目标：
二.Traditional Feature-based Methods: Node
1. 半监督学习任务semi-supervised
预测未知点颜色的着色：
1. 设置规则：绿色节点至少有两个邻边，红色节点有一个邻边；
2. 将节点度作为结构特征，让机器学习
2. 节点特征overview
描述节点在网络中结构与位置的特征，具体分为以下四类：
1.节点度node degree：一个节点的连边有多少
2.节点中心性node centrality：说明一个节点在图中的重要性
3.聚类系数clustering coefficient：衡量节点邻居的连接程度，表征网络结构，如节点数量、节点间结构
4.异构连通子图graphlets：给定节点下全部子图的构型
3. 节点度node degree
计算一个节点的连边是多少，因此机器无法区分如C和D，因为他们具有相同的节点度，所以节点度的概念不能够完全说明节点的特征，因此需要引入节点中心度的概念
4. 节点中心度node centrality
进行节点中心度计算的几种方法：
1.engienvector centrality特征向量中心性：节点的邻居数量的总和就是节点的重要性的程度，可以用特征值和特征向量来表示，最大特征值正定且唯一，前置向量leading eigenvector就是节点中心度的向量
2.betweenness centrality：节点连接的最短路径越多就越重要，类似于交通要道。
如A到B、D、E的最短路径都要经过节点C，所以节点C的节点中心度为3。规定边缘节点A、B、E的节点中心度为0。
3.closeness centrality：节点越居中，与其他节点的路径越短越重要
如A到各个节点的距离分别为2,1,2,3，而D到各个节点的距离为2,1,1,1，所以D的节点中心度比A的大
5. 聚类系数clustering coefficient
节点的邻居之间的连接程度，节点邻居实际连接的边和潜在所有连边的比值
如图1中邻居和其他所有邻居相连，聚类系数为1，图二一个邻居和两个邻居相连，而四个邻居之间潜在连边是6，所以聚类系数是0.5，图三邻居之间没有连边，聚类系数是0.
6. 异构连通子图Graphlets
节点和他的邻居之间可以构成很多三角形组，这样那些没有构成连边的节点对在将来也有可能构成连边，这个特征就被成为graphlets。
当节点的数量不同时，各个节点之间构成的关系子图结构就不同，节点的特征也不同
三种节点属性的区别：
1.节点度：表示和该节点相连接的节点的数量
2.聚类系数：表示节点的邻居与其他邻居连接的程度
3.异构连通子图的度向量GDV：表示数量相同的节点，因为结构不同而产生的不同的图结构。
如上图，当我们研究v时，异构连通子图的节点可为2,3，实例graphlet instances的个数即为GDV。
当节点为2时，有2种实例，
当节点为3时，有两种异构连通子图，
第一种情况下三个节点等价，有1种实例
第二种情况下节点不等价，分c,d两种节点，c节点有1种实例，d节点有2中实例。
综上，GDV表示为[2,1,0,2]
考虑2-5个节点的graphlets，可以得到一个长度为73个坐标coordinate（就前图所示一共73种graphlet）的GDV，描述该点的局部拓扑结构topology of node’s neighborhood，可以捕获距离为4 hops的互联性interconnectivities。
相比节点度或聚类系数，GDV能够更详细的(细粒度fine-grained)描述两个节点之间的局部拓扑结构相似性local topological similarity。
7. 小结summary
关于节点的特征可以分为两类：
1.捕获节点在图中的重要性：节点度、节点中心度
2.捕获节点附近的拓扑结构：节点度、聚类系数、异构连通子图
三、Traditional Feature-based Methods: Link
1. 边预测任务
基于已知的连边，预测新的连边。在预测模型时，将每一对无连接的节点对进行排序，取存在连接概率最高的k个节点对作为预测结果。
但是太多次的预测会导致两个节点间的信息丢失，因此，更加认为边预测任务是双向的link prediction task is two-way.
2. 边节点预测的类型
1.随机失踪边：随机删除一些边，通过机器学习预测再将其连接上，适用于静态网络
2.随时间演化边：适用于随时间推移而发展的网络
3.基于相似性预测边
计算每一对节点对(x,y)的得分c，将分数进行排序，最高分的节点对将作为新连接，通过比较预测值和实际值来说明我们方法的好坏。
3. 边特征overview
1.最短路径distance-baesd feature
2.节点的共有邻居数local neighborhood overlap
3.global neighborhood overlap
4. distance-baesd feature
基于路径的特征可以计算两个节点之间的最短路径，但是不能判断节点之间连接的紧密程度，因此引入本地邻域重叠local neighborhood overlap的概念，通过判断两个节点之间共同邻居的个数来判断其连接的紧密程度。
5. local neighborhood overlap
1. 共同邻居的个数——使用交集来表示
2. 规范化使用Jaccard's coefficient
3. Adamic-Adar index在实践中表现得好。在社交网络上表现好的原因：有一堆度数低的共同好友比有一堆高度联系的名人共同好友的得分更高。
6. global neighborhood overlap
提供一对节点的得分和Katz索引计数
当两个节点没有共同邻居时，局部邻居数返回为0，但实际两个节点将来仍可能连接在一起，因此需要考虑全局邻居。
Katz索引Katz index：计算节点对之间所有长度路径的条数
1.计算给定两节点间给定长度的路径数——图邻接矩阵graph adjacency matrix求幂
2.计算\(P^{(k)}_{uv}\)
\(P^{(2)}_{12}=A^{(2)}_{12}=2\)表示节点1,2之间存在一条路径长度为2的路径。基于此，可以延伸到无穷长度。
β 是权重衰减因子，路径与长度成指数关系。为了保证数列的收敛性，其取值需小于邻接矩阵A最大特征值的倒数。该方法权重衰减因子的最优值只能通过大量的实验验证获得，因此具有一定的局限性。
计算所得\(S\)即为两个节点之间边的分数
7. 小结summary
四、Traditional Feature-based Methods: Graph
图级别特征构建目标：找到能够描述全图结构的特征
1. 背景知识
1.Kernel Methods——被广泛用于图级别的预测
2.方法：设计内核而不是特征向量
3.对Kernel的简要介绍
- \(K(G,G')\)用来描述计算数据间的相似性
- Kernel矩阵则是测量所有节点对的相似性，且核矩阵\(u\)必须是半正定positive semi-definite(有正特征值)且对称symmetric
- 内核有特征表示feature representation\(\phi\)，大概意思是图的特征可以用一个向量表示，内核的特征表示就是两个图的特征向量点乘。
- 优点：不需要显式创建就可以计算，且定义好内核后有现成的机器学习模型svm(kernel support vector machines)
2. 图特征overview
测量图相似度的不同内核：
1.graphlet kernel
2.weisfeiler-lehman kernel
3.其他: random-walk kernel ; shortest-path kernel
内核背后的关键思想：定义特征向量\(\phi(G)\)
如文档的特征可以用里面的单次来表示，基于此思想，将图的特征用里面的节点来表示，但这样具有同样节点数的不同图结构就有相同的特征向量，因此，提出了度内核node degree
如第一个图，四个节点的度分别为1,2,2,3，所以特征向量为[1,2,1] (分别表示节点的度为1,2,3的个数)
3. graphlet features
将图表示为图中异构连通子图数量的计数，但其与节点异构连通子图有以下两点不同：
1.节点级异构连通子图不需要全部连通，即可以存在孤立节点
2.节点级异构连通子图没有内核
graphlet count vector中的每个元素是图中对应graphlet的数量，该向量记为\(f_{G}\)
存在问题：两个图的大小可能不相同
解决办法：将特征向量规范化
graphlet计数占用空间巨大，非常耗时，为了提高效率，提出了weisfeiler-lehman kernel
4. weisfeiler-lehman kernel
目标：高效计算图的特征向量
办法：用节点邻居结构迭代地来扩充节点信息
算法：Weisfeiler-Lehman graph isomorphism test同构检验，也叫色彩优化color refinement
先给每个节点设置相同的初始颜色，根据节点的连边个数收集颜色，基于HASH函数，对节点的颜色进行更新。
举例：
再进行第二次迭代
通过这样不断的迭代，可以对颜色进行细化
在经过k次迭代后，内核就可以通过给定颜色的节点数来进行计数，解决了前面计数运算量大的问题。
WL kernel的优势在于它非常高效，因为其运算是线性的，不像graphlet呈指数型增加。
5. 小结summary
五、本章小结
