CS224w 图网络机器学习笔记

笔记:https://snap-stanford.github.io/cs224w-notes/
视频:https://www.bilibili.com/video/av90106649?p=2

CS224w 图网络机器学习课程

Measuring Networks and Random Graphs

四个要素

  1. Degree Distribution P(k)

$$
P(k) = N_k / N
$$

$N_k$ is the number of nodes with degree k and N is the number of nodes.

  1. Paths in a Graph

distance 是最短路径

diameter (直径)是所有最短路径中最长的

average path length
$$
\hat h = \frac{1}{2 E_{max}} \sum_{i, j \neq i} h_{ij}
$$
$E_{max}$ 是图的最多路径数 n(n−1)/2

  1. Clustering Coefficient

For node i with degree $k_i$,
$$
C_i = \frac{2 e_i}{k_i (k_i - 1)}
$$
where $e_i$ is the number of edges between the neighbors of node i

  1. Connectivity

    the size of the largest connected component

一些图模型

  1. ER 随机图

难点:For a random Gnp graph, $\log n > np > c$,
$$
\text{diam}(G_{np}) = O(\log n / \log (np))
$$

  1. The Small World Random Graph Model

两个局限性在于它的度分布与现实世界网络的幂律分布不匹配,并且不能在假设网络规模的情况下对网络增长进行建模

  1. The Kronecker Random Graph Model

定义一种乘积运算,不断重复自身来生成模型

Motifs and Structral Rules in Network

网络模块(Motif)是指反复出现的重要的连接模式

相比随机图,出现的频率更高。随机图生成:保持所有节点的度不变,将边重新随机连接

  • role是根据在network中相似的功能来决定:例如公司中作为测试工程师的每个人,因为做着相似的工作所以扮演相同的role,可是在公司这个network中,这些人不一定互相连接。即role取决于相似性而不是相互连接性
  • group/community则是互相连接的个体(节点),核心在于连接性

RoIX 算法来确定 roles,使用节点自身的 feature,和邻居的 feature

社区

Modularity 模块度,衡量社区分割的好坏

如何识别社区? Louvain 算法,O(nlgn)的贪心算法

  1. Partition,将每个结点移入使模块度增加最多的邻居社区
  2. Aggregate,将社区不断聚合,形成一颗树

如何处理 overlap 社区,使用生成模型F生成一张图与实际图G进行比较,用随机梯度下降来进行最大似然估计

谱聚类

谱聚类算法是利用矩阵的特征向量进行聚点的聚类算法。它的主要思想是把所有的数据看做空间中的点,这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低,而距离较近的两个点之间的边权重值较高,通过对所有数据点组成的图进行切图,让切图后不同的子图间边权重和尽可能的低,而子图内的边权重和尽可能的高,从而达到聚类的目的。

以边为切割 – 以 motif 为切割(以元路径、元结构为切割?用路径来缩减图的表示) motif 论文

  1. Preprocessing: construct a matrix representation of a graph, such as the adjacency matrix (but we will explore other options)
  2. Decomposition: compute the eigenvectors and eigenvalues of the matrix, and use these to create a low-dimensional representation space
  3. Grouping: assign points to clusters based on their representation in this space

消息传递和节点分类

分为三个步骤:

  1. Local Classifier,使用节点自身特征进行传统分类,不使用网络信息;
  2. Relational Classfier:使用节点邻居的标签/特征来标记一个节点的类别,使用了网络信息;
  3. Collective Inference(集体推理):传播关联性,迭代对每个节点进行第二步,直至邻居间的不一致性降到最低;

Relational Classfier:

Iterative Classfier:

每个节点一个向量,包含自身特征和邻居节点的类别的聚合

Looply belief propagation 置信度传播算法:

节点只能从邻居获得信息

  1. 转移矩阵:i 到 j 的联合概率分布;
  2. 根据节点 i 自身特征计算的概率;
  3. 邻居节点认为 i 属于某类别的概率;

最后判别每个节点属于哪个类别。

NetProbe论文:识别在线拍卖中的欺诈者,增加了一个共犯类,共犯专门为欺诈者刷分。

图表示学习

节点嵌入:

  1. 定义图中的相似度计算方式;
  2. 定义 Embedding 方法;图中相似的节点在 Embedding 之后距离较近

Random Walk:

P 定义的是结点和邻居的相似度,给定结点的嵌入表示,使得它和邻居的相似度更高,求解这个嵌入。

相关论文 :DeepWalk / 负采样(node2vec)

Node2Vec:

biased walk:结合 BFS(Local 信息)和DFS(全局信息)

图嵌入:

  1. 将每个节点的嵌入聚合(求和/平均);2016
  2. 创建子图的虚拟节点,将节点聚合;2016
  3. 匿名路径嵌入(Anonymous Walk Embeddings);2018

GNN

图网络相关笔记

图神经网络直播笔记

图表示学习:

node importance

transductive / inductive

wikipedia,使用关联来识别 fake 文章

投影矩阵将不同节点投影到一起

节点级别聚合和语义级别聚合

训练框架 Eular dgl pyg

Network Schema
Meta Path,抽取子结构

Constrained Meta Path(Node\Link Constrained)
Meta structure/graph

Challenges: complex structure / mine semantics

Network Embedding
节点的特征向量:连接矩阵(长、稀疏),如何压缩到低维度,保持结构信息。
Shallow Model 浅层模型:矩阵分解Laplacian eigenmaps、随机游走Deepwalk,node2vec;
Deep Model:Autoencoder(DNGR、SDNE),GNN(Average neighbor info、GCN)

HIN Embedding:
Challenges:handle heterogenity、fuse information、capture rich semantics
Shallow Model:
异质变同质,HERec,
Meta-Path based randow walk(同质中等概率随机游走,异质中沿着特定类型的边、不等概率)
类型限制+Filtering
Skip-Gram?
Embedding Fusion

MCRec
用户和物品的表示,加上meta-path的表示,+attention,
元路径具有可解释性;

RHINE
不同关系的结构特性不同,

HHNE
欧式空间,-》双曲空间(Power-Law,层次)和网络数据特性接近,

HeGAN
负样本,产生具有迷惑性高质量的负样本,(对抗学习)
产生关系一样的负样本(Relation-aware),

Deep Models:

NeuACF
浅层因子模型,矩阵分解一个矩阵仅考虑了一方面信息,增加多方面信息
设置不同元路径抽取不同路径,历史购买特征+品牌特征

HAN:
用邻居信息,GAT
设置不同路径得到不同邻居,先是对某一路径的不同邻居,再对不同路径进行聚合(Node-level,Semantic-level attention)

Applications:
Cash-out user detection
花呗套现:特征隐含在购买、交互行为记录中
AHIN、HACUD
基本用户特征+多路径邻居聚合Meta-path based neighbors aggregation
Feature Fusion
Hiera attention

Intent recommendation(MEIRec)
用户、物品、查询
数量多,动态变化-》word拼接而成的item和query,

短文本分类,HGAT
topic,doc,entity

Chanllenge:

more complex-》knowledge graph
more powerful-》beyond meta path
more bigger-》parallel computation

如何从非结构化文本中构造图
表示
动态网络

HIN一篇综述

元路径的选择-领域知识,构建图的时候所具备的领域知识(语义可解释)
使用短的元路径,

考虑时间信息,+session,动态网络

0%