1.3

图的基本表示

• Objects：nodes（节点）、vertices（顶点）表示为NN

• Interactions（关系）：links、edges表示为EE

• System：network、graph表示为G(N,E)G(N,E)

设计本体图

• 如何设计本体图，取决于将来想解决什么样的问题

• 有些时候，本体图是唯一的、无歧义的

图的类型

• 无向图：连接是无方向的

• 有向图：连接是有方向的

• 异质图：节点和连接都存在不同的类型

• 二分图（Bipartite Graph）

• 节点只有两类

• 展开二分图：将连接了另一类的节点进行分别连接

节点连接数

• 无向图：平均度为

• 有向图：平均度为

邻接矩阵Adjacency Matrix

• 无向图：

• 邻接矩阵是对称阵

• ，主对角线为0，A_{ii} = 0Aii=0

• 连接总数：

• 沿行或列求和均可：

• 有向图

• 邻接矩阵是非对称矩阵，

• 连接总数：

2.6 连接列表、邻接列表

• 连接列表：只记录存在连接的节点对

• 邻接列表：只记录相关连接的节点，每个节点占用一行

2.1总结：

2.1

图数据挖掘任务分类：

• 节点层面：信用卡欺诈用户的挖掘

• 连接层面：Facebook预测可能认识的人，预测某两个节点之间是否有连接以及连接的种类；

• 全图层面：与非一个蛋白质分子的功能

传统机器学习（人工特征+机器学习）

节点属性特征；

连接特征，节点和其他节点之间连接的特征；结构信息

本节主要讨论无向图；

特征非常重要，

Eigenvector centrality：

，这是一个递归的求解；等价于

，A是邻接矩阵，c 是A的eigenvectors；

Betweenness centrality：

Closeness centrality：

u和v之间最短路径长度累加；

Node Feature: Clustering Coefficient：

Graphlet Degree Vector (GDV)：

A count vector of graphlets rooted at a given node;（因为是u节点邻域的信息，不包括u节点）

2.2总结

2.2 连接层面的特征工程

the task is to predict new links based on the existing links；

at test time, node pairs (with no existing links) are ranked, and top K pairs are predicted.

the key is to design features for a pair of nodes.

方法：

• For each pair of nodes (x, y) compute score c(x ,y) (例如 x 和 y 的共有邻居)；

Link-Level Features: Overview

• Distance-based feature

• Shortest-path distance between two nodes; 但是这样忽略了例如多条路径的信息

• Local neighborhood overlap

• Common neighbors （共同好友个数）

• jaccard's coefficient:

• （交互比）;

• Adamic-Adar index:

• （共同好友是不是社牛）

• 缺点：如果两个节点没有共同节点

• Global neighborhood overlap

• Katz index: count the number of walks of all lengths between a given pair of nodes. 节点u和节点v之间长度为K的路径个数

• 两节点之间 walks 计算方法：计算 adjacency matrix (邻接矩阵) 的幂；

2.3 总结

2.3 全图层面的特征工程

把整张图变成d维向量，能反映全图的结构特点；

Goal: design graph feature vector

Key idea:

• Bag-of-Words (BoW) for a graph

• Bag of node degrees; Bag-of-*

• Count the number of different graphlets in a graph

• 这里不是针对 rooted 的图，而是针对全图视角的，区别于节点工程中的针对邻域的graphlet

• Graphlet Kernel:

• ，如果

• 和

• size不同，那么用归一化的方式进行处理

• 子图匹配非常消耗算力，枚举；

• 可用于各种 kernel；

• Weisfeiler-Lehman Kernel：

• Goal: Design an efficient graph feature descriptor

• ，color reinforcement