异构网络挖掘 - 目录

本文内容基于 Prof. Jiawei Han 的 UIUC CS512: Data Mining: Principles and Algorithms (Spring 2017) 课程的Chapter 2。主要基于幻灯片内容做概要性介绍，以后有机会将对其中的若干特定算法另撰文章详细介绍。

异构网络挖掘 - 目录
简介
Part 1：异构网络上的聚类和排名
Part 2：异构网络上的分类和预测
Part 3：异构网络上的其他数据挖掘方法

简介

同构网络（homogeneous network）：节点和连边都只有一种
- 朋友关系网络（顶点为朋友，连边为关系）
- 万维网（顶点为网页，连边为链接）
异构网络（heterogeneous network）：多种节点和连边类型
- 医疗网络（顶点有医生、患者、病症、治疗方式等）
- 文献网络（顶点有文献、作者、会议、关键字）
同构网络往往由异构网络导出（合作网络由作者-论文的异构网络向作者投影得到）
异构网络携带更多信息
挖掘半结构化的异构网络
- 聚类（cluster）
- 排名（ranking）
- 分类（classification）
- 预测（prediction）
- 相似度搜索（similarity search）

Part 1：异构网络上的聚类和排名

聚类和排名

RankClus: 在两种节点类型（比如作者和会议）的异构网络上，聚类和排名同时进行并相互提高。
- Y. Sun, J. Han, P. Zhao, Z. Yin, H. Cheng, T. Wu, “RankClus: Integrating Clustering with Ranking for Heterogeneous Information Network Analysis”, EDBT’09
- 节点连边矩阵：$W = \begin{bmatrix} W_{XX} & W_{XY} \\ W_{YX} & W_{YY} \end{bmatrix}$，X是会议，Y是作者。
- 在聚类中不是每个节点都应该相同对待（重要的节点应该作用越大）
- 排名在聚类的条件之下（在某聚类内的排名）
- 排名方法：在不同类型的节点间传播排名数值（类似PageRank）
  1. 高排名的作者在很多高排名的会议发表论文：$r_Y(j) = \sum_{i=1}^{m}W_{YX}(j, i)r_X(i)$
  2. 高排名的会议吸引很多高排名作者的文章：$r_X(i) = \sum_{j=1}^{n}W_{XY}(i, j)r_Y(j)$
  3. 如果一个作者和很多高排名作者合著文章，那么排名将会增加：$r_Y(i) = \alpha \sum_{j=1}^{m}W_{YX}(i, j)r_X(j) + (1 - \alpha)\sum_{j=1}^{n}W_{YY}(i, j)r_Y(j)$ （在1的基础上增加了一项）
- 其他的排名函数（比如加入具体知识，期刊往往比会议排名高等等）
- 考虑聚类：从“条件排名分布”到EM框架
  - 对于每个聚类$C_k$，把条件排名分数$r_X \vert C_k$、$r_Y \vert C_k$看做X和Y的条件排名分布（把排名和概率建立关系，并且用这个条件排名分数作为聚类特征来做聚类）
  - 对于对象$o_i$和聚类k，$p(k \vert o_i) \propto p(o_i \vert k)p(k)$。即$o_i$在聚类k里的排名分数$p(o_i \vert k)$越高，则$o_i$在聚类k中的概率$p(k \vert o_i)$越高。
  - 使用EM算法估计参数
    - 根据现有参数$\theta$计算分布$p(z=k \vert y_j, x_i, \theta)$。
    - 根据现在的分布更新$\theta$。
- EM风格的算法
  - 初始化
  - Repeat
    - 排名：在聚类的子网络内对里面的对象进行排名
    - 对每个对象估计混合模型系数（mixture model coefficients）
    - 调整聚类
  - Until 改变小于阈值
- 使用Normalized Mutual Info（NMI）评价聚类表现
NetClus：在星型网络下的基于排名的聚类
- Y. Sun, Y. Yu, and J. Han, “Ranking-Based Clustering of Heterogeneous Information Networks with Star Network Schema”, KDD’09
- 与RankClus类似的EM风格算法

相似度搜索

相似度度量/搜索是聚类分析的基础
Meta-Path（元路径）：元级别的对两个对象之间路径的描述
- 在Network Schema上的路径，例如“作者-文章-作者”（合作元路径，该作者的学生或者亲密合作者）、“作者-文章-会议-文章-作者”（在类似领域的类似声誉的作者）
- 不同的Meta-Path有不同的语义信息
已有的较流行的网络上相似度度量
- Personalized PageRank
- SimRank
PathSim：异构网络上基于Meta-Path的相似度搜索
- Y. Sun, J. Han, X. Yan, P. S. Yu, and T. Wu, “PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks”, VLDB’11
- Peer：在给定meta-path上具有强相连性和相似的可见性（比如在类似领域的类似声誉的作者）
- 给定一条对称的Meta-Path $\mathcal{P}$，两个对象之间的SimPath定义为：$s(x, y) = \frac{2 \times \vert {p_{x \rightarrow y} : p_{x \rightarrow y} \in \mathcal{P}} \vert}{\vert {p_{x \rightarrow x} : p_{x \rightarrow x} \in \mathcal{P}} \vert + \vert {p_{y \rightarrow y} : p_{y \rightarrow y} \in \mathcal{P}} \vert}$
  - 分子：x和y的相连性
  - 分母：x和y的可见性

用户指导的基于Meta-Path的聚类

对于不同的聚类目标（不同的Meta-Path偏好），可能期望的结果也会不同
问题描述
- 输入
  - 聚类T的目标类型（即对哪种类型聚类，这里只对单一类型聚类）
  - 聚类数量k
  - 对于一些聚类给定种子：$L_1, \cdots, L_k$（用户指导）
  - 可选的meta-paths：$P_1, \cdots, P_M$
- 输出
  - 每个meta-path的权值：$w_1, \cdots, w_M$
  - 根据用户指导的聚类结果
PathSelClus：一个用户指导的基于Meta-Path的聚类概率模型
- Sun, Yizhou, et al. “Pathselclus: Integrating meta-path selection with user-guided object clustering in heterogeneous information networks.” ACM Transactions on Knowledge Discovery from Data (TKDD) 7.3 (2013): 11.

Part 2：异构网络上的分类和预测

分类

GNetMine
- 所有对象同等对待
RankClass：基于排名的分类
- M. Ji, M. Danilevsky, and J. Han, ”Ranking-Based Classification of Heterogeneous Information Networks”, KDD’11
- 高排名的对象在分类中更重要
- 排名和分类互相增强
- 问题描述
  - 给定异构网络$\mathcal{G}$和有分类标签$\mathcal{Y}$的子图$\mathcal{G}’$，预测没有标签的剩下部分$\mathcal{G} - \mathcal{G}’$的分类标签和每类中的排名分布$P(x \vert T(x), k), x \in \mathcal{V}, k = 1 \cdots K$
- 直觉想法：权威性的传播
  - 连接在一起的对象更可能共享类别k的相似排名分数

关系预测

同构网络的链接预测——异构网络的关系预测
PathPredict：基于Meta-Path的关系预测
- Y. Sun, R. Barber, M. Gupta, C. Aggarwal and J. Han, “Co-Author Relationship Prediction in Heterogeneous Bibliographic Networks”, ASONAM’11
- 用Meta-Path构成的拓扑特征来预测合作关系（谁会成为你的新的论文合作者）
  - 长度不大于4的Meta-Path（9条，也就是说9个特征）
  - A-P-V-P-A、A-P-A-P-A、A-P→P←P-A最显著
- 4种度量：路径数（通过某meta-path从作者a到作者b一共有多少路径）、归一化路径数、随机游走、对称随机游走
  - 以上四种混合效果最好
- 合作时间预测

网络嵌入

任务导向的（task-guided），路径增广的（path-augmented）异构网络嵌入
- T. Chen and Y. Sun, Task-guided and Path-augmented Heterogeneous Network Embedding for Author Identification, WSDM’17
- 问题描述
  - 给定一篇匿名文章（一般是双盲评审），包括会议、年份、关键词、引用列表
  - 预测作者
  - 传统方式：特征工程
  - 新方法：异构网络嵌入

Part 3：异构网络上的其他数据挖掘方法

进化和动力学

Y. Sun, et al., “Studying Co-Evolution of Multi-Typed Objects in Dynamic Heterogeneous Information Networks”, MLG’10

角色发现

DBLP中发掘导师-学生关系
- Chi Wang, Jiawei Han, Yuntao Jia, Jie Tang, Duo Zhang, Yintao Yu, and Jingyi Guo, “Mining Advisor-Advisee Relationships from Research Publication Networks “, KDD’10

图上的OLAP

Peixiang Zhao, Xiaolei Li, Dong Xin, and Jiawei Han, “Graph Cube: On Warehousing and OLAP Multidimensional Networks”, SIGMOD’11
Chen Chen, Xifeng Yan, Feida Zhu, Jiawei Han, and Philip S. Yu, “Graph OLAP: Towards Online Analytical Processing on Graphs”, ICDM 2008

数据清理：同名区分

基于链接分析的同名区分
- X. Yin, J. Han, and P. S. Yu, “Object Distinction: Distinguishing Objects with Identical Names by Link Analysis”, ICDE’07
- 度量引用之间的相似性
  - 基于链接的相似性：引用同一对象则更可能
  - 基于邻居的相似性：每个引用和其邻居互相相似
- 自动建立训练集（Self-boosting）
  - 一些很特别的名字一般没有重名

多关系数据库间的分类

CrossMine
- Xiaoxin Yin, Jiawei Han, Jiong Yang and Philip S. Yu, “Efficient Classification across Multiple Database Relations:A CrossMine Approach”, IEEE Trans. Knowledge and Data Engineering, 18(6): 770-783, 2006.

多元数据扩展

EgoSet
- Xin Rong, Zhe Chen, Qiaozhu Mei, Eytan Adar, “EgoSet: Exploiting Word Ego-Networks and User-Generated Ontology for Multifaceted Set Expansion”, WSDM’16

Note of Heterogeneous Network Mining

异构网络挖掘 - 目录

简介

Part 1：异构网络上的聚类和排名

聚类和排名

相似度搜索

用户指导的基于Meta-Path的聚类

Part 2：异构网络上的分类和预测

分类

关系预测

推荐

网络嵌入

Part 3：异构网络上的其他数据挖掘方法

进化和动力学

角色发现

图上的OLAP

数据清理：同名区分

多关系数据库间的分类

多元数据扩展