作为国民级的音乐APP， 网易云音乐很早之前就将定位从传统的音乐工具软件转换为音乐内容社区，连接好泛音乐产品与用户，做最懂用户的音乐APP。

而直播作为参与度较多的场景， 云音乐内部花费大量的功夫将合适的主播推荐给用户。

评论页直播推荐难点

###业务难点

如图，是评论页场景直播推荐，和经典的推荐架构，主要包括召回、粗排、精排，本次实践主要落地在召回，而在此场景，我们约到的核心问题在于阅读评论页的用户较大部分未产生过行为，因而采用传统的协同过滤类算法，由于数据极度稀疏，并不能产生较好的效果，为典型的用户冷启动问题。

###基建难点

目前云音乐的所有计算资源已完成容器化部署， 在成本考虑下， 不可能给各个业务团队，比如384G内存、8卡的计算资源来进行海量数据的图神经网络模型训练， 如何在有限的、分布式的资源调控策略下完成大规模的图神经网络的训练也是我们必须要考虑的

图神经网络如何协助落地

行为域知识迁移

所幸，并不是没有解决方法，新用户在直播场景下为新，但是在音乐、歌单、mlog，通常会有较多的行为，是否能考虑这部分的知识，来映射到直播域，提供足够的“行为”来推荐合适的主播呢？
这里我们考虑使用Graph的结构， 引入多种不同类型的实体，如歌曲、DJ、Query、RadioID等等，将用户与主播、用户与歌曲、Query与主播等等行为，统一建模在一张图中，通过经典的Graph Model如DeepWalk， Metapath2vec、GraphSAGE,学习足够强大的embedding表示，来建模各实体id，然后通过ANN召回，通过用户对歌曲、Query等等的行为迁移至主播域，召回合适的主播。

通用的分布式图神经网络解决方案

由于该场景整体数据规模较大，在经过某些规则裁剪之后， 整体数据规模约为百万级节点，亿级别边，而在很多开源方案中，这样的量级就已经开始成为瓶颈，或者使用极其昂贵的计算资源来解决， 这个对于我们现有的资源情况来说是不可能， 而在我们的规划中，这样的数据量级仅仅还只是开始，所以，我们在开始之初， 就考虑到数据规模的问题，相对于使用什么的模型，我们更关注其在工业界场景数据下是否能训练得出， 通过调研现有的开源方案，我们选择PGL作为我们基础的框架， PGL基于PaddlePaddle Fleet来支持Graph Learning中较为独特的Distributed Graph Storage、Distributed Sampling， 可以较为方便的通过上层python接口，来将graph中的存储比如Side Feature等存储在不同server上，也支持通用的分布式采样接口，将不同子图的采样分布式处理，在分布式的“瘦计算节点”上加速计算， 这对于我们是十分具有吸引力。

进展与未来规划

目前采用图计算的实验，在有效观看上提升将近6%， 在该场景下尤其是通过引入其他域数据上来解决新用户冷启动问题上，有明显提升，未来，在这块上，我们规划从以下三个方向上探索

1. 模型上：目前我们已经完成包括DeepWalk（带权重）、MetaPath2Vec（带权重）、GraphSAGE直播场景的落地，后续打算引入更复杂的模型如attention 机制是否能协助解决不同实体类型对最终实体建模的贡献能力；
2. 数据规模：通过不停挖掘更多行为数据、关联更多行为实体， 数据规模越来越大，从单机到分布式，PGL目前支持较为完好，后续我们打算减少数据阈值，引入更多合适的领域数据来探索是否能够进一步提升；
3. 平台化能力输出：目前PGL的分布式方案尽管已在云音乐内部的机器学习平台上运行，但并未整合到提供平台化能力输出， 用户暂时无法自助运行分布式的PGL模型训练，也需要更改部分源码来适配分布式训练，后期我们打算通过制作组件以及对PGL进行封装，支持PGL训练代码无需修改代码来分布式训练；

经典的机器学习框架主要支持包括Images和Text/Speech 这两种数据，主要设计用来解决sequence、grids问题， 而Graph 结构相对较为复杂：

• 无法产生特定顺序的节点序列，因而很难转换为普通序列问题；
• 图结构频繁变化，且通常需要建模多模态特征；

Basics of deep learning for graphs

假定存在图G，其中V表示节点集合，A是邻接矩阵，\(X \in R^{m*|V|}\)是节点的特征矩阵（a matrix of node features）。这里的节点特征，根据不同的网络有不同的定义——如在社交网络里面，节点特征就包括用户资料、用户年龄等；在生物网络里面，节点的特征就包括基因表达、基因序列等；如果节点没有特征，就可以用one-hot编码表示或者常数向量 1: [ 1 , 1 , … , 1 ] [1, 1, …, 1][1,1,…,1]来表示节点的特征。

Local Network neighborhoods

节点的邻居定义计算图， 能够有效地建模信息的传播；

如上图，根据节点邻居得到计算图， 然后根据计算图生成节点的向量表示，如下图，A的节点表示由其邻居节点{B,C,D}，而这些节点又由其邻居节点决定，形成如下图的计算图，其中方形框即为其聚合邻居节点的策略，可采用average操作：

由此，可将图中任意节点，根据其邻居节点，生成对应的计算图。

Stacking multiple layers

上一小节示意图中，使用节点的最高至二阶邻居点，即邻居的邻居来生成某节点的计算图，也可以使用任意深度的模型来表示，即图神经网络中层的概念：

• 任意节点在每一层均有对应的向量表示；
• layer-0的向量表示即模型的输入特征\(x_{u}\);
• layer-k的向量表示，即节点经过k层邻居之后的向量表示；
  因而，Graph Neural Network能够通过叠加layer建模更高阶信息。

Graph Neural Network整体架构到这里其实基本上就讲完了，而不同的上述各种图中的方形框内部的计算逻辑。

一个有效的方法即GCN的思路是， 在入口对接收到的message平均化， 多阶的信息由邻居的邻居的信息传播来进行建模， 和常见的深度学习模型没啥差别：

模型训练

模型训练基本方式和常规的深度学习方式基本一致， 构建神经网络结构，通过构造loss函数，使用梯度下降方法，对模型参数进行更新，以最小化loss函数值：

非监督方式

基于图神经网络的非监督方式相对于传统的深度学习方式更加流行，其通常利用graph结构信息（其实也可以拼接slide info，slide未提），保证在graph中有相似的节点，有相似的特征表示。常见的模型包括：random walk系列（node2vec， DeepWalk， Struc2vec）， Graph Factorization， Node Proximity in the graph

有监督方式

有监督方式的loss函数，根据不同任务类型来定义，如在常见的节点分类任务，如互联网中判断某节点是否为薅羊毛党，其为二元分类问题，通常采用交叉熵来表征其loss函数：

模型设计回顾

定义邻居聚合函数与loss函数:

按邻居节点生成批计算图

生成图节点的向量表示

对于计算图中，同一layer中的节点采用共享的参数表示，其参数彼此共享，且针对新图或者图中的新出现节点，均同样适用。

Graph Convolutional Networks and GraphSAGE

基本介绍

如前文所述，在邻居节点聚合操作时，我们采用average操作，那么是否有更多通用的方式呢？GraphSAGE的思路是采用一个通用的aggregation函数来表示方形框的计算，并将其与本身的向量表示拼接起来，aggregation函数要保证可微分。

常见的Aggregation如下：

• Mean：
  

• Pool:

• LSTM:

回顾

如下图， 图神经网络通过建模邻居节点的方式来解决图节点向量化的难题，通过多层高阶graph layer来聚合不同阶邻居的信息，并构建Graph计算图，来训练得到节点向量化表示，其中GCN为最基础方式，其聚合函数采取平均策略，而GraphSAGE设计通用的邻居聚合函数，如mean、pool、LSTM等等。

关于GNN的一些论文：

Tutorials and overviews:
§ Relational inductive biases and graph networks (Battaglia et al., 2018)
§ Representation learning on graphs: Methods and applications (Hamilton et al., 2017)
Attention-based neighborhood aggregation:
§ Graph attention networks (Hoshen, 2017; Velickovic et al., 2018; Liu et al., 2018)
Embedding entire graphs:
§ Graph neural nets with edge embeddings (Battaglia et al., 2016; Gilmer et. al., 2017)
§ Embedding entire graphs (Duvenaud et al., 2015; Dai et al., 2016; Li et al., 2018) and graph pooling
(Ying et al., 2018, Zhang et al., 2018)
§ Graph generation and relational inference (You et al., 2018; Kipf et al., 2018)
§ How powerful are graph neural networks(Xu et al., 2017)
Embedding nodes:
§ Varying neighborhood: Jumping knowledge networks (Xu et al., 2018), GeniePath (Liu et al., 2018) § Position-aware GNN (You et al. 2019)
Spectral approaches to graph neural networks:
§ Spectral graph CNN & ChebNet (Bruna et al., 2015; Defferrard et al., 2016) § Geometric deep learning (Bronstein et al., 2017; Monti et al., 2017)
Other GNN techniques:
§ Pre-training Graph Neural Networks (Hu et al., 2019)
§ GNNExplainer: Generating Explanations for Graph Neural Networks (Ying et al., 2019)

Graph Attention Networks

GAT顾名思义，需要考虑邻居节点中，对最终结果的不同的影响，因而引入attention机制，attention在经典的深度学习网络中十分常见，如transformer的self-attention，

Attention Mechanism

如下图， \(e_{uv}\)可以通过两个节点之间的信息流得到, \(e_{vu}\)表示节点u的信息对节点v的重要性, 使用softmax进行归一化，以便在不同的节点间存在可比性，然后集成在模型聚合函数中来建模不同节点对当前节点信息的重要性。

其他另外过程和原先GCN、graphSAGE没什么差别，除了attention信息也会参与训练。

写在net embedding之前

一个标准的机器学习流程如下：

其中如何设计一套合理方式来高效地进行特征表示，是十分重要的，比如在cv与nlp任务中，我们会分别设计cnn模块与RNN模块来建模图像中像素点表征的信息、word表征的信息。

那么在graph中，如何进行特征表示呢 ？ Graph的特征表示极为复杂，主要表现在以下三个方面：

• 极其复杂的拓扑结构，很难简单地像图像中的感受野来提取有效信息；
• 无特定的节点顺序；
• 通常graph会是动态变化的， 且使用多模态特征；
  

今天我们就来了解下如何对graph进行特征学习；

Embedding Nodes

假设有图G，V表示节点集合，A为对应的邻接矩阵，embedding node是对图当中的节点进行有效地编码，保证相似的节点在编码也有类似的相似性，如下图：

节点的向量学习分为以下三个方面：

1. 定义编码器， 即ENC(v)，将图中的节点通过周边结构关系的学习，映射到低维的向量表示，如\(Z_{v}\)，在常见的任务中，通常就是一个embedding矩阵，通过lookup拿到对应节点的向量，然后反向进行embedding向量的更新，这个即成为学习；
2. 定义相似度函数sim(u,v)，即如何定义两个节点相似度的大小；
3. 通过数据的学习不断来优化编码器参数，保证\(sim(u,v) = Z_{v}^{T}Z_{u}\)；

Random Walk

何谓"随机游走"？给定一个graph和一个起点，随机选择其一个邻居，并移动到这个邻居，然后继续随机选择这个点的邻居，产生随机的点序列，而点和点之间出现的概率即为\(Z_{v}^{T}Z_{u}\)

Random Walk有两个特点：

• 极具表达性： 节点相似计算的定义、随机，且包含了局部（邻居）以及高阶邻居的信息；
• 效率级高：训练时不需要穷举所有的节点对，只需要考虑随机游走中同时的对；

非监督特征学习

给定图G=（V， E）， 学习一种映射\(z: u->R^{d}\)，目标函数：

其中，\(N_{R}(u)\)表明以策略R得到的节点u的邻居：

优化

1. 使用某种策略R，从图上的每个节点开始进行固定长度的较短的random walks；
2. 对于每个节点u，得到其的邻居\(N_{R}(u)\);
3. 根据上图中似然函数，对embedding进行优化；

这里，将目标函数，修改为以下，其中\(p(v|z_{u})\)可通过softmax得到：

但是一旦使用softmax，其复杂度变得极大，你必须计算graph当中所有的节点，其复杂度达到了\(O(|V|^2)\)，和大家十分熟悉的word2vec，我们采用Negative Sampling来近似计算：

Negative Sampling

Negative Sampling仅仅随机选择k个负样本进行归一化操作，其中\(P_V\)是所有节点的随机分布，其中k属于超参，通常有以下经验：

• k越大，预估有更强的鲁棒性；
• k越大，负样本偏差会越大；
• k通常使用5-20；

Node2vec

Node2vec解决的和random类似的额问题， Node2vec扩展节点u的邻居\(N_{R}(u)\)的定义，来丰富embedding的建模信息；

Biased Walk
DeepWalk选取随机游走序列中下一个节点的方式是均匀随机分布的，而node2vec通过引入两个参数p和q，其中p为返回到上一个节点的概率， q表示生成策略选择DFS或者BFS的概率， 将宽度优先搜索和深度优先搜索引入随机游走序列的生成过程。宽度优先搜索(BFS)注重临近的节点，并刻画了相对局部的一种网络表示，宽度优先中的节点一般会出现很多次，从而降低刻画中心节点的邻居节点的方差；深度优先搜索(BFS)反应了更高层面上的节点间的同质性。（即BFS能够探究图中的结构性质，而DFS则能够探究出内容上的相似性（相邻节点之间的相似性）。其中结构相似性不一定要相连接，甚至可能相距很远。

得到Walks之后， Node2vec算法和DeepWalk基本类似，整体流程如下：

• 计算随机游走的概率；
• 模型从每个节点u开始的步长为l的r次随机游走；
• 利用优化方法优化目标函数；

如何使用节点的embedding？

训练好的节点向量可用于很多场景：

• 比如专栏前面文章提到的聚类、社区检测；
• 节点分类，比如根据节点embedding预测节点是否属于薅羊毛人群，新闻实体是否为fake news；
• 关系预测，比如预测用于是否与对应实体可能产生连接关系，即是否可能产生行为关系；

总结

本章课程，主要介绍了在graph中做node embedding的基本概念，以及常见的方法如Random Walk、Node2vec，并简要介绍了embedding的用途，视频教程中还有基于KG的Translating Embedding的应用，因为讲的过于简单，仅仅介绍TranE的三元组关系，感觉并不能理清楚其实际落地细节，所以本文不做描述，这部分相关工作建议直接阅读TranE的相关文档，比如药物中蛋白质分子的应用的等等，其实本文将是接下来各种复杂GNN的入门课程，大概所有的深度学习模型其实都在学习一种有效地特征表示，如本章内容而言，仅是入门，还有很多有意思的工作，比如是否能建模graph的dynamic的信息，行为是动态更新的，dynamic在某些场景下更能表征节点的社交行为结构化信息，另外还有包括side information的引入，都是在graph下的embedding node下很重要的工作。

• Graph Partitioning
  • Criterion
    • Minimum-cut
    • Conductance
• Spectral Graph Partitioning
  • Matrix Representations
  • Find Optimal Cut
• Spectral Clustering Algorithm
  • 基础方法
  • k-Way Spectral Clustering
• Motif-Based SPectral Clustering
  • Motif Conductance
• Summary

Graph Partitioning

何谓graph partitioning, 如下图，给定无向图\(G(V,E)\)， 将这些节点分为两个组：

逻辑很简单，但是难点在于：

1. 如何定义一个尺度，来保证图的切分是合理的：
   1. 组内成员连接尽可能多；
   2. 组与组之间连接尽可能少；
2. 如何高效地识别这些分区；

Criterion

Cut(A,B): 如下图，图当中，两个点分别在两个分组的边的数量；

Minimum-cut

最小化图分组间的连接（如果有权重，则考虑权重）：

\[arg min_{A, B}\ Cut(A,B) \]

这样会存问题：

• 仅仅考虑图当中分组的外部连接；
• 未考虑图中分组的内部连接；
  因此，在下面图中，会出现，假如是minimum cut不是optimal cut
  

Conductance

与Minimum-cut逻辑不一样， Conductance不仅仅考虑分组间的连接， 也考虑了分割组内的“体积块”， 保证分割后得到的块更均衡，Conductance指标如下：

\[ \phi(A, B)=\frac{cut(A,B)}{min(vol(A), vol(B))} \]

其中\(vol(A)\)指分组块A内节点所有的权重度之和；
但是，得到最好的Conductance是一个np难题。

Spectral Graph Partitioning

假定A为无连接图G的链接矩阵表示，如(i,j)中存在边，则\(A_{ij}=1\)，否则为0；
假定x是维度为n的向量\((x_1, ..., x_n)\)，我们认为他是图当中每个节点的一种标签；
那么\(A*x\)的意义是， 如下图， \(y_i\)表示i的邻居节点与对应标签和：

令\(Ax=\lambda x\)，可以得到特征值：\(\lambda_i\), 和对应的特征向量\(x_i\)。对于图G， spectral(谱)定义为对应特征值\({\lambda_1, \lambda_2, ..., \lambda_n}\)，其\(\lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n\) 对应的特征向量组\({x_i, x_2, ..., x_n}\)；

** d-Regular Graph 举例 **

假定图当中每个节点的度均为\(d\)，且G是连通的，即称为\(d-Regular Graph\)。
假定\(x = (1,1,...,1)\)，那么\(Ax = (d, d, ..., d) = \lambda x\)， 故会有对应的特征对：

\[x=(1,1,...,1), \lambda =d \]

且d是A最大的特征值（证明课程未讲）

d-Regular Graph on 2 Components

假定G有两个部分， 每个部分均为d-Regular Graph，
那么必然存在：

\(x^{'}=(1,...,1,0,...,0)^T\)， \(A x^{'}=(d,...,d,0,...,0)^T\)
\(x^{''}=(0,...,0,1,...,1)^T\)， \(A x^{'}=(0,...,0,d,...,d)^T\)

所以必然存在两个特征值\(\lambda_{n} = \lambda_{n-1}\)， 推广起来，如果图G中两个部分互相连通，如下图， 则最大的特征值很近似：

推广， 这里有点没有太理解：

Matrix Representations

邻接矩阵A

• 对称矩阵；
• n个实数特征值；
• 特征向量均为实数向量且正交:
  

度矩阵

• 对角矩阵；
• \(D=[d_{ii}]\), \(d_{ii}\) 表示节点i的度；
  

Laplacian matrix

Laplacian matrix 有以下特点：

• 令x=(1,...,1)则\(L*x=0\)， 故\(\lambda=\lambda_{1}=0\)；
• L的特征值均为非负实数；
• L的特征向量均为实数向量，且正交；
• 对于所有x，\(x^{T}Lx=\sum_{ij} L_{ij}x_{i}x_{j} \geq 0\)；
• L能够表示为\(L = N^{T} N\)

Find Optimal Cut

分组表示(A,B)为一个向量，其中

问题转换为寻找最小化各部分间连接：

相关证明间slide，这里老师没有做过多解读；

Spectral Clustering Algorithm

基础方法

如下图：主要包括三个步骤：

• 预处理：构造图的表示， 包括Laplacian Matrix；
• 矩阵分解：
  • 计算Laplacian Matrix的所有的特征值与特征向量；
  • 将节点使用特征向量表示（对应\(\lambda_2\)的特征向量\(x_2\)）；
    
• 聚类， 将节点的特征表示，排序， 按大于0与小于来进行拆分：
  

以下是多个实例， 看起来使用\(\lambda_{2}\)对应的特征向量\(x_2\)来切分是比较合适的：

k-Way Spectral Clustering

如何将图切分为k个聚类呢？

• 递归利用二分算法，将图进行划分。但是递归方法效率比较低，且比较不稳定；
• 使用降维方法，将节点表示为低维度的向量表示，然后利用k-mean类似的方法对节点进行聚类；

那么如何选择合适的k呢，如下图，计算连续的特征值之间的差值，选择差异最大的即为应该选择的k？

Motif-Based SPectral Clustering

是否能够通过专有的pattern 来进行聚类呢？上一篇文章有提到motif， 如下图：

给定motif，是否能够得到相应地聚类结果：

答案当然是可以的， 而且也是复用前面的逻辑

Motif Conductance

和上文中， 按边来切分逻辑不通， conductance指标，应该表征为motif的相关指标，如下：

这里给出一个计算的例子， 如下图， 该出模式分子为切分经过的该模式数量， 分母为该模式覆盖的所有节点数量：

所以motif的谱聚类就变成了给定图G与Motif结构来找到\(\phi_{M}(S)最小的\)， 很不幸， 找到最小化motif conductance也是一个np问题；
同样地，也专门提出了解决motif 谱聚类的方法：

1. 给定图G和motif M；
2. 按M和给定的G，生成新的权重图\(W_{(M)}\);
3. 在新的图上应用spectral clustering方法；
4. 输出对应的类簇；

大致过程如下图所示：

具体过程如下：

1. 给定图G与motif M， 计算权重图\(W^(M)\)：
   

2. 应用谱聚类， 计算其Laplacian Matrix的特征值与特征向量，得到第二小的特征向量，：
   

3. 按升序对第二小特征值的对应的特征向量进行排序（对应的节点ID需要保存以计算motif conductance）， 以\(S_r = {x_1, ...,x_r}\)计算motif conductance值，选择最小地的值即为划分点， 如下图，1,2,3,4,5为一个类：
   

Summary

本章我们学习了谱聚类相关的工作， 首先，讲了关于表征切分图的指标cut(A,B)以及conductance，如何切分图以及为什么切分图是一个np难题，然后提出了利用谱聚类的方法来解决该问题，从而学习到了degree matrix, Laplacian matrix等概念； 而后提出是否有按motif来进行图聚类的方法， 并基于谱聚类的方法来解决来转换原图为带权重的图来解决；

Granovetter's theory

马克·格兰诺维特（Mark Granovetter，1943年10月20日－），美国社会学家，斯坦福大学教授。格兰诺维特是论文被引用最多的学者之一，根据 Web of Science 的数据，社会学论文被引数排名第一和第三的文章皆出自格兰诺维特之手。格兰诺维特因为对社会网络和经济社会学的研究而成名。其最著名成就是1974年提出的弱连接理论：与自己频繁接触的亲朋好友之间是一种“强连接”，通过这种连接获取到的往往是同质性的信息；但社会上更为广泛的是一种并不深入的人际关系，这种弱关系能够使个体获得通过强关系无法获取到的信息，从而在工作和事业上、在信息的扩散上起到决定作用。

格兰诺维特的研究认为如果两个人之间有共同的朋友，那他们成为朋友的可能性较大。

格兰诺维特的研究也在真实的数据上得到了验证

Edge Overlap

简单解释下，Edge Overlap表示两个节点的邻居节点的重合程度（本身节点不在计算范围内），下图中右边部分右上图， \(N(i)=4, N(j)=4\)， 去除本身i, j 所以\(N(i) \cup N(j) = 6\), \(N(i) \cap N(j) = 2\)， 所以\(O_{ij}=1/3\)

Edge Overlap被用来当做节点间链接的强弱的一种度量，通过在实际数据集（欧洲通话网络数据集得到验证）， 在实际数据中，具有高边重叠的边，确实是有着强连接关系的， 这里的强连接关系即用节点间通话次数来表示关系强弱；

社区内强连接，社区间弱连接

上面的研究表明，在图中确实会存在紧密连接的社群概念，社群内的链接基本是强连接， 而社群间的连接是弱连接，强链接偏向将信息流锁紧在社群内部，而边缘连接由于涉及到多个社群之间，在信息传播上更有优势

网络社群的基本概念

网络中的社群的基础定义：紧密连接的节点集合，这些节点间有较多的内部连接，而相对较少的外部连接；

Zachary空手道俱乐部一个在图这块入门级的数据集，用来展示图网络中基本的问题如节点分类、社区发现等等；

如下图， 仅靠图的结构化关系，可以比较合理地将俱乐部进行切分，即规划至各自的社群：

另一个例子是NCAA FootBall Network：

如何寻找网络中的社群？

Modularity Q用来衡量网络中社群划分的指标， 其基础含义如下：

\[Q \Rightarrow \sum_{s \in S}[(\#\ edges\ within\ group\ s) - (expected\ \#\ edges\ with\ in\ group\ s) ] \]

其中\((expected\ \#\ edges\ with\ in\ group\ s)\)需要构建null model（之前的学习笔记有提到过Configuration Model， 忘记了的小伙伴可以翻一下）， 保证相同的degree distribution且连接概率为均匀随机， 假定两个节点i、j，其度分别为\(k_i, k_j\)，那么节点间边的期望为\(p(i,j)= \frac{k_{i}k_{j}}{2m}\)，所以这个图里面所有边的期望为：

\[E_{edge}=0.5 \sum_{i \in N} \sum_{j \in N} \frac{k_{i}k_{j}}{2m}= 0.5 * \frac{1}{2m}\sum_{i \in N}k_{i}(\sum_{j \in N} k_{j})=\frac{1}{4m}* 2m*2m = m \]

所以Modularity Q从：

\[Q \Rightarrow \sum_{s \in S}[(\#\ edges\ within\ group\ s) - (expected\ \#\ edges\ with\ in\ group\ s) ] \]

表示为：

\[Q(G, S) = \frac{1}{2m}\sum_{s \in S}\sum_{i \in s}\sum_{j \in s}(A_{ij}-\frac{k_{i}k_{j}}{2m}) = \frac{1}{2m}\sum_{ij}[A_{ij}-\frac{k_{i}k_{j}}{2m}]\delta(c_i, c_j) \]

其\(A_{ij}\ =\ 1\ if\ i->j\ 0\ otherwise, \delta(c_i, c_j)=1\ if\ c_i = c_j\ 0\ otherwise\)

Q值域为[-1, 1], 正值表示社群内的边多于期望， 当Q为0.3-0.7之间表明有显著的社群结构；

Louvain Algorithm

Louvain Algorithm是一个最大化Modularity Q的贪心算法，主要由两步构成：

过程1：Partitioning

1. 初始化的时候给所有节点分配一个单独的社区；
2. 针对每一个节点i，进行以下步骤：
   1. 计算改几点被划分到其邻居节点j所在的社群，并且计算该社群的modularity delta；
   2. 将节点i移入至最好modularity delta的社群；
3. 迭代，直到modularity delta不再增加；

其中modularity delta \(\Delta Q\)， 应该包括\(\Delta (i->C)\)(将节点i移入community C增加的Q值)与\(\Delta(D->i)\)（将节点i溢出Community D）， 因为\(\\Delta(D->i)\)， 在步骤1中都一样， 所以\(\Delta Q\)公式主要依赖于\(\Delta (i->C)\)， 如下：

\[\Delta Q(i ->C)[\frac{\sum_{in} { k_{i, in}}}{2m} - (\frac{\sum_{tot}+k_i}{2m})^2] - [\frac{\sum_{in}}{2m} - (\frac{\sum_{tot}}{2m})^2 - (\frac{k_i}{2m})^2] \]

其中：
\(\sum_{in}\) 表示社群内节点之间的边权重和（社群内边）；
\(\sum_{tot}\) 表示社群中节点所有的边的边权重和（社群内边与社群外边均考虑）；
\(k_{i, in}\) 表示社群中节点i与其他节点的边权重和；
\(k_i\) 表示节点i连接的所有边的权重和；

过程2： Restructuring

经过第一步之后， 会出现很多超级节点，这些超级节点间所在的社群间如果有任意的边连接，那么我们要连接超级节点， 超级节点间的边的权重等于他们相应地社群间所有边权重的和；

具体的伪代码如图，逻辑还是相对比较简单的：

回顾与真实数据展示

每一个pass 包含：partitioning和restructuring 两个部分， 如下，迭代直到收敛：

真实数据集上的一个例子：

检测有重叠的社群算法：BigCLAM

何谓有重叠的社群？

无重叠的社群与有重叠的社群

很多实际数据集中，存在有重叠的社群：
facebook的Ego-Network

PPI

BigCLAM

BigCLAM主要步骤如下：

1. 基于节点所属的社群，构造一个图生成模型，构造方法为AGM(Community Affiliation Graph Model)；
2. 根据我们实际的图G，假设它是用AGM生成的。寻找一个最优的AGM，能产生我们实际的图G， 通过这个AGM，确定每个节点所属的社区

Community Affiliation Graph Model

如下图， 左边部分主要包括节点V， 社群C， 从属关系，其中每一个社群的概率为\(p_c\)：

1. 社群c内的节点，彼此连接形成边的概率是\(p_c\);
2. 对于从属与多个社群的节点，如果其在一个社群内没有连接， 其边在另外社群的连接也是可能存在的；

AGM可以生成多种不同的社群结构，如Non-overlapping, Overlapping, Nested：

Detecting Communities with AGM

使用AGM来做社群发现就转换成一个给定graph G， 如何反推AGM的各个参数F：Affiliation Graph M， 社群个数C，以及社群内连接概率\(p_c\)

给定G和F， 计算器似然函数:

\[P(G|F)=\prod_{(u,v) \in G}P(u, v)\prod_{(u,v) \not \in G}(1-p(u,v)) \]

上式中前一个连乘表示图当中所有的边的似然函数，后一个表示不在该graph边集合的似然。
考虑到每个节点属于各个社区的权重是不同的， 向量\(F_u\)表示节点u属于各个社群的权重，加上log转换， 所以log似然函数为：

\[l(F) = \sum_{(u,v) \in E} log(1-exp(-F_{u}F_{u}^{T})) - \sum_{(u,v) \not \in E}F_{u}F_{v}^T \]

这里和lr的梯度下降很类似，其实就是一样，只需要用梯度下降公司待进去自然就可以算出收敛是的F的参数；

有了F之后， 我们的节点从属社群关系就极其明显了。

总结

今天，课程上主要讲解的是graph中社群的概念，通过Granovetter's theory和真实数据的对比，验证了图当中的强弱连接，从而引出社群概念，然后介绍了一种简单的社群发现算法Louvain Algorithm，通过最大化Modularity Q来保证节点与社群的从属， 最后提供可重叠的社群发现，提出BigCLAM算法，通过最大化log似然函数优化AGM生成对应真实Graph，来得到AGM， 从而得到包括社群从属关系在内的各个参数，从而识别节点从属；

• Subgraphs
  • Motif: Induced Subgraphs
  • Motifs: Recurrence
  • Motif： Significance
  • Configuration Model
  • Alternative for Spokes: Switching
  • 本节总结
• Graphlets: Node Feature Vectors
• Finding Motifs and Graphlets
  • Exact Subgraph Enumeration###
  • Graph Isomorphism
• Structural roles in networks
  • Discovering Structural Roles in Networks
    • RoIX: AutoMatic Discovery of nodes' structural roles in network

Subgraphs

何谓motif？ 图中反复出现的相互连接的模式，有以下三个特点：

• Pattern：小的能导出的子图；
• Recurring：频繁出现；
• Significant：模式的出现明显高于预期，如类似的random genderated networks中的模式；

Motif: Induced Subgraphs

Induced Subgraph如下图所示，图中红色框虽然也是3个节点构成的子图，但是该子图与待匹配的子图不匹配（连接不一致），而蓝色的三角框中的子图与待匹配的子图匹配， 匹配的意思是指必须是出现在待匹配子图里所有节点的边，如果不是待匹配节点之间的边，则不匹配；

Motifs: Recurrence

如下图，右侧图中出现了4个待匹配的motif，motif之间可以相互重叠；

Motif： Significance

如下图， 该motif在真实的网络中出现的频率要对类似的随机网络出现的频率要高的多， 我们成为其显著性明显；

显著性通常是和随机性网络做对比，通常使用\(Z_i\)来描述motif i的显著性， 其中\(N_{i}^{real}\)表示真实网络中motif i的数量， \(N_{i}^{rand}\)表示在随机网络中motif i的数量：

\[Z_i = \frac{(N_{i}^{real}-N_{avg\ i}^{rand})}{std(N_{i}^{rand})} \]

上面的计算会随着网络规模的不同而有数值的变化，而大的网络会倾向于有更大的Z-score， 归一化处理之后，使用Net significance profile来表示，motif i的SP计算公式如下：

\[SP_{i}= \frac{Z_{i}}{\sqrt{\sum_{j}{Z_{j}^{2}}}} \]

Configuration Model

配置一个和真实网络相同的度序列的随机图可以分为三步：

1. 按节点的度序列生成Node spokes；
2. 随机从nodes spokes中挑选两个连接起来；
3. 根据源节点和目标节点，将步骤2中聚合起来，即形成和真实网络相同度序列的随机网络；

Alternative for Spokes: Switching

另一个产生于源图类似的图的方法就是随机做边交换，具体步骤如下：

1. 从源图中随机找出边如，A->B, C->D，随机交换边的终点产生边A->D, C->B， 如果交换导致自己指向自己，则不交换；
2. 重复1中，Q次， 当Q足够大时，即可生成随机图；

本节总结

经过上面的定义与解释之后，我们就可以定义如何检测一个motif：

1. 在真实图中，统计induced subgraph的个数；
2. 统计生成的随机网络中的induced subgraph的个数， 这里随机生成的网络，可以生成多个做对比；
3. 计算Z-score， 那些高的Z-score就是我们需要的motif；

motif也有相应的变种， 如不同的频率概念、不同的显著性计算标准、null model的不同约束等等，但基本上都是万变不离其宗；

Graphlets: Node Feature Vectors

Graphlet是基础的由节点构成的基础子图单位，由两个节点开始，下图是2-5个节点的graphlet示例图：

那么，如何由graphlet来改造节点的特征呢？
之前我们提到的度，是指每个节点能够接触到的边数，这里我们扩展Graphlet degress vector，用来表示节点v能够接触到的graphlet的数量， 如下图，graphlet有a, b, c, d, 注意这里d和c画在一张图上, 这样我就可以用2, 1, 0, 2来表示节点V：

Graphlet degree vector的意义在与它提供了对于一个节点的本地网络拓扑的度量，这样可以比较两个节点的GDV来度量它们的相似度。由于Graphlet的数量随着节点的增加可以很快变得非常大，所以一般会选择2-5个节点的Graphlet来标识一个节点的GDV。

Finding Motifs and Graphlets

在一个图里识别出一种特定大小的motifs和graphlet，并计算它的数量是非常难的一个问题。识别是否是同构子图本身就是一个NP-hard的问题：计算量也会随着节点数的增加而呈指数增长，因此， 一般只识别节点数较小如3-8的motif或者graphlet。

Exact Subgraph Enumeration###

ESU从一个节点\(v\)开始，算法分为两个集合：\(V_{subgraph}\):表示当前构造的子图，\(V_{extension}\)：表示能够扩展motif的候选节点， 将满足以下两个条件的节点\(u\)加入到\(V_{extension}\)：

1. \(u\)的节点id要大于v的id；
2. \(u\)只能是新加入加点\(w\)的邻居，而不能是\(V_{subgraph}\)里的节点邻居；

伪代码逻辑如下：

如下图就很容易理解了， 从不同的点出发， 比如node 1， node 1的邻居只有3， 所以开始extendsion为3， node2， 其邻居只有3， 所以extension为3， node 3， 其邻居有1、2、4、5，为保证id要大于node 3， 所以extension为4、5， node 4， 邻居有3、5， 保证id大于4所以extension为5， 第二层将exetension加入到subgraph， 且此时exetension要是新加入节点，如最左边分支，新加入节点为3，exetension要讲node 3的邻居加入，且保证大于node1 ， 即exetension变为2，4，5；左起第二个， 将exetension 中node 3加入， node3的邻居节点有1、2、4、5， 其中只有4、5大于原先subgraph中的2， 所有exetension为4、5， 以此类推即可，最终所有大小为3的子图即可遍历出来；

到目前为止， 我们就可以遍历出所有大小为的子图， 接下来我们只需要统计下这些图即可， 如下图所示， 需要判断是否为同构图，即拓扑结构完全一致：

Graph Isomorphism

如何判定两个图是同构？
如果图\(G\)和\(H\)是同构的，那么必定存在一个双向映射\(f: V_{(G}->H_{(H)}\)保证任意两个节点u和v在图G里面是相邻的，则\(f ( u )\) 和\(f ( v )\)在图H里也是相邻的, 检查图是否重构是一个NP难题

Structural roles in networks

Role: 角色， 是对节点在网络中功能的描述， 是有相同结构特征的点，相同角色的节点并不一定直接相连，而Group/Communities(社群)， 是彼此相互密集连接的节点群；

视频中举了个例子，假定一个计算机系构建一个社交网络，其中：

• 角色指： 教职、职员、学生；
• 社群指： AILab、Info Lab、 Theory Lab等；

如果节点u和节点v和所有其他节点有相同的关系，则说明节点u和节点v在结构上等同， 如下图中u和v完全相同；

Discovering Structural Roles in Networks

为什么要研究图当中的role ？如下图：

RoIX: AutoMatic Discovery of nodes' structural roles in network

RoIX特点如下：

• 非监督学习方法；
• 无需先验知识；
• 支持多种角色分类；
• 按边数线性扩展；

RoIX过程如下图， 其中最重要的Recursive Feature Extraction.

Recursive Feature Extraction是基于图的结构详细，从某一节点出发，聚合该节点的特征，如有向图中，该特征未出度、入度、度等等，其次基于该node的邻居、包含该节点的可导出子图，这称之为Egonet，也会提取Egonet中节点的特征。以此类推，用这种方法提取到的特征，是指数级增长，后续会使用裁剪技术将部分特征裁剪掉；

最终，每一个节点会由如下图的向量表示， 然后采用non negative matrix factorization（KL离散度距离来评估似然度） 即可完成流程图中node * role matrix与role * feature matrix的生成：

如何描述一个网络

Degree Distribution

P(k): 随机选择的节点， 度为k的的概率分布， 使用直方图来描述

其中\(N_k\)表示度为k的节点数， 比如上图中，度为1的节点数有6， 所有节点数为10， 所以\(P(6)=0.6\)

Path Length

Path: path是指每个节点连接下一个节点的序列，其中，一个path能够重复多次相同的边， 如下图： ACBDCDEG

Distance: 连接节点对最少数量的边，称为两个节点间的distance，如下图，其中\(h_{B,D}=2, h_{A,X}=\infty\)， 若图中两节点无连接，或中间连接断开，则distance为无穷，在有向图中，distance的计算应该考虑两个节点间的方向，如下图\(h_{B,C}=1, h{C,B}=2\)，不是对称的：

Diameter在graph中，所有节点对当中最长distance；
Average path length针对graph来说， average path length计算公式如下：

\[h_{average}=\frac{\sum_{i,j!=i h_{ij}}}{2E_{max}} \]

其中\(h_{ij}\)是node i到node j的distance, \(E_{max}\)是指图最多可存在的边数：\(\frac{n(n-1)}{2}\)

Cluster coefficient

cluster coefficient 对于无向图，用来描述节点i与他的邻居的链接情况， 其中节点i的度为\(k_{i}\)，clustering coefficient计算公式如下：

\[C_{i}=\frac{2e_{i}}{k_{i}(k_{i}-1)} \]

如下图， 图的node i的cluster coefficient计算如下：\(C_{i}=\frac{2*6}{4*(4-1)}=1, C_{i}=\frac{(2*3)}{4*(4-1)}=0.5, C_{i}=\frac{2*0}{4*(4-1)}=0\)
Average clustering coefficient: \(C=\frac{1}{N}\sum_{i}^{N}C_{i}\)

\(K_{A}=1, e_{A}=0, C_{A}=0\)
\(k_{B}=2, e_{B}=1, C_{B}=1\)
\(k_{C}=4, e_{C}=2, C_{C}=1/3\)
\(k_{D}=4, e_{D}=2, C_{D}=1/3\)
\(k_{E}=3, e_{E}=0, C_{E}=0\)
\(k_{F}=1, e_{F}=0, C_{F}=0\)
\(k_{G}=1, e_{G}=0, C_{G}=0\)
\(k_{H}=2, e_{H}=1, C_{H}=1\)
avg. clustering: C= (1+1/3+1/3+1)/8=1/3

Connected components

Connectivity
图当中最大的可连接的component：能够通过path链接的任意两个几点的最大的集合；
如何找到图当中的connect components，从图中随机节点开始，按广度优先策略遍历，标记遍历过的节点，如果，所有的节点均被遍历，那么这个未connected component， 否则从未遍历的节点中随机开始，重复广度优先策略遍历；

描述实际中的图：MSN Messenger

msn一个月的相关的数据，如下：

Degree Distribution

x坐标log之后：

可见大部分的节点degress在个位数。

Clustering

将所有的节点的k与c绘制在如下图中，整个graph的avg culstering coefficient约为0.1140

Connected Components

Diameter

msn的graph中平均path length为6.6， 90% 的节点能够触及在8个链接后触及到另一节点；

图的核心属性如何使用？

这些graph的属性是意外的还是在我们本身预料之中？

PPI Network

Random Graph Model

Simplest Model of Graph

ER Random Graphs
两个变种：

1. \(G_{np}\)： n个节点的无向图，其中每一条边是概率为p的独立同分布；
2. \(G_{nm}\): n个节点的无向图，其中m个边均匀随机生成；

需要说明的是，n, p 无法唯一地的决定graph，如下图，相同的n,p下， 我们有不同的图：

Degree Distribution of \(G_{np}\)

假定\(P{(k)}\)表示度为k在所有节点中的占比， 则

\[P_{(k)}= C_{n-1}^{k} p^{k}(1-p)^{n-1-k} \]

很明显的binomial distribution, 所以均值、方差为：

\[k_mean = p(n-1) \] \[\sigma^2 = p(1-p)(n-1) \]

标准差率为：\(\frac{\sigma}{k_mean} \approx \frac{1}{(n-1)^{0.5}}\)，当图无限大的时候，则标准差为0， 所有的节点都为\(k_mean\)。

Clustering Coefficient of \(G_{np}\)

已知\(C_{i}=\frac{2e_{i}}{k_{i}(k_{i}-1)}\), 在\(G_{np}\)，边为概率为p的独立同步分， 其中\(E[e_{i}] = p\frac{k_{i}(k_{i}-1)}{2}\), 故\(E[C_i] = \frac{pk_i(k_i - 1)}{k_i(k_i -1)} = p = \frac{k_{avg}}{n-1} \approx \frac{k_{avg}}{n}\)

Expansion

定义\(\alpha\): 如果一个graph的任意的子集S,子集中边的条数大于alpha乘以子集或者graph去除子集之后的节点数量， Expansion通常用来衡量图的lu'bang'xing：

\[\alpha = \mathop{\min}_{S \subseteqq}{\frac{\# edges\ leaving\ S} {min(|s|, |V \ S|)}} \]

这张ppt没理解清楚，

在\(G_{np}\)中，n*p为常数，所以avg deg k也为常数：

Connected Components

\(G_{np}，其中n = 100000, k=p(n-1)=0.5...3\)，Largest CC中节点占图中所有节点的比例

Random Graph Model vs. MSN

在Random Graph Model 和实际的MNS的4个核心属性对比：

真实网络和Random Graph类似吗 ？

• Giant Connected component: yes
• Average path length: yes
• Clustering Coefficient: No
• Degree Distribution: No

The Small-World Model--能同时保证high clustering且短path的图吗？

回顾下前面MSN network，clustering coef为0.11， 而\(G_{np}的clustering coef为8*10^{-8}\)。
另外一个例子， IMDB数据集、Electrical power grid, Network of nerons中：

其中h：average shortest path length， C: avg clustering coefficient， random，是保证相同avg degree，相同节点下的图的情况。

下图左边：高clustering coefficient： 朋友的朋友是我的朋友；

Small-World同时保证high cluster and low diameter；
如下图，从high clustering/high diameter, 到low clustering/low diameter， 增加随机性（p变大）: 即随机的将一条边的另一个端点连接到任意较远的节点上，这样可以保持high clustering，low diameter；

下图中的p区域保证保证high clustering 和low path length：

Kronecker Graph Model: Generating large realistic graphs

递归的graph的生成: Self-similarity

Kronecker Produce是一种生成self-similar矩阵的方法：

Kronecker Product 定义如下：

举个例子：

• 构建一个\(N_1 * N_1\)的初始概率矩阵；
• 计算k阶Kronecker 矩阵；
• 遍历k阶矩阵，按\(p_{uv}\)构建edge(u, v)链接
  
  如上图最后， 需要模拟\(n^2\)次，耗时太高， 是否有更高效方法(利用其递归结构)？

真实网络与Kronecker网络很相似， 右上角为其初始矩阵：