图表示学习 Graph Representation Learning chapter2 背景知识和传统方法

2.1 图统计和核方法

2.1.1 节点层次的统计和特征

节点的度

$$d_u=\sum _{v\in \mathcal{V}}A(u,v)\text{\hspace{1em}(2.1)}$$

需要说明的是，在有向和加权图中，度可以区分为不同的概念。例如入度和出度之类的。不管怎么说，这个特征在传统机器学习中都是十分重要的。

节点中心度

$$e_u=\frac{1}{\lambda }\sum _{v\in \mathcal{V}}A(u,v)e_v,\forall u\in \mathcal{V}\text{\hspace{1em}(2.2)}$$

一种常见的方式是利用特征向量中心度，我们定义每个节点的中心度为周围所有中心度的均值，其中$\lambda$是一个常数。

求解这一过程，可以写作如下形式：$$\lambda e=Ae\text{\hspace{1em}(2.3)}$$
如果我们期望所有的中心度都是正的，我们可以应用Perron-Frobenius Theorem，即对A求解特征向量。
此外我们也可以通过迭代法如下：$$e^{(t+1)}=A{e}^{(t)}\text{\hspace{1em}(2.4)}$$

如果我们设$e^0=(1,1,...,1{)}^T$那么每次迭代后的结果是截至T步时，经过的次数，由此可以得到重要性。

聚类系数

用于衡量节点局部邻域封闭三角形的比例。

$$c_u=\frac{|(v_1,v_2)\in \mathcal{E}:v_1,v_2\in \mathcal{N}(u)|}{C_{d_u}^2}\text{\hspace{1em}(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：计算不同子图结构出现次数。具体方式为，枚举所有可能的子图结构，然后统计出现的次数。

基于路径，则是统计类似于最短路之类的。

邻域重叠检测

未完待续。