图表示学习 Graph Representation Learning chapter2 背景知识和传统方法
图表示学习 Graph Representation Learning chapter2 背景知识和传统方法
- 2.1 图统计和核方法
- 2.1.1 节点层次的统计和特征
- 节点的度
- 节点中心度
- 聚类系数
- Closed Triangles, Ego Graphs, and Motifs
- 图层次的特征和图的核
- 节点袋
- Weisfieler–Lehman核
- Graphlets和基于路径的方法
- 邻域重叠检测
2.1 图统计和核方法
2.1.1 节点层次的统计和特征
节点的度
d u = ∑ v ∈ V A ( u , v ) (2.1) d_u = \sum_{v\in \mathcal{V}} A(u, v)\tag{2.1} du=v∈V∑A(u,v)(2.1)
需要说明的是，在有向和加权图中，度可以区分为不同的概念。例如入度和出度之类的。不管怎么说，这个特征在传统机器学习中都是十分重要的。
节点中心度
e u = 1 λ ∑ v ∈ V A ( u , v ) e v , ∀ u ∈ V (2.2) e_u = \frac{1}{\lambda}\sum_{v\in \mathcal{V}}A(u, v)e_v, \forall u\in \mathcal{V}\tag{2.2} eu=λ1v∈V∑A(u,v)ev,∀u∈V(2.2)
一种常见的方式是利用特征向量中心度，我们定义每个节点的中心度为周围所有中心度的均值，其中 λ \lambda λ是一个常数。
求解这一过程，可以写作如下形式： λ e = A e (2.3) \lambda e = Ae\tag{2.3} λe=Ae(2.3)
如果我们期望所有的中心度都是正的，我们可以应用Perron-Frobenius Theorem，即对A求解特征向量。
此外我们也可以通过迭代法如下： e ( t + 1 ) = A e ( t ) (2.4) e^{(t+1)}=Ae^{(t)}\tag{2.4} e(t+1)=Ae(t)(2.4)
如果我们设 e 0 = ( 1 , 1 , . . . , 1 ) T e^0=(1,1,...,1)^T e0=(1,1,...,1)T那么每次迭代后的结果是截至T步时，经过的次数，由此可以得到重要性。
聚类系数
用于衡量节点局部邻域封闭三角形的比例。
c u = ∣ ( v 1 , v 2 ) ∈ E : v 1 , v 2 ∈ N ( u ) ∣ C d u 2 (2.5) c_u=\frac{|(v_1,v_2)\in \mathcal{E}:v_1,v_2\in \mathcal{N}(u)|}{C_{d_u}^2}\tag{2.5} cu=Cdu2∣(v1,v2)∈E:v1,v2∈N(u)∣(2.5)
其中 N ( u ) = { v ∈ V : ( u , v ) ∈ E } \mathcal{N}(u)=\{v\in \mathcal{V}:(u,v)\in \mathcal{E}\} N(u)={v∈V:(u,v)∈E}也就是所有的相邻节点构成的集合。
这一特征描述了节点附近结构的紧密程度。
Closed Triangles, Ego Graphs, and Motifs
略
图层次的特征和图的核
节点袋
单纯综合节点的特征。
Weisfieler–Lehman核
一种迭代邻域聚合方法。
Graphlets和基于路径的方法
Graphlets：计算不同子图结构出现次数。具体方式为，枚举所有可能的子图结构，然后统计出现的次数。
基于路径，则是统计类似于最短路之类的。
邻域重叠检测
未完待续。