在解决大规模图划分时，读过了很多论文，无非是在目标方程中做出一些策略上的改动，并没有什么创新的地方，最严肃的问题是，可能收敛不了。而深度学习发展的今天，获取可以考虑用DeepLearning的形式来改善大规模图划分。读了些许的论文，只有这篇是沾点边的，遂精读并做笔记，这篇论文八成是日后的对比对象了。
在论文中，最重要的一点是如何使用网络处理图数据，并定义损失函数，即如何将图划分问题迁移到NN中。
问题背景
- 大规模图划分，显然要划分的图的规模是很大的，节点在百万、千万、亿级别，并不是
cora数据集这样只有两千多个节点。将大规模的图划分为多个子图； - 此外，大规模图图划分涉及生物、化学和社交网络等多个领域，在图划分结束后，将划分结果提交到分布式平台用于计算，因此图划分仅仅是数据处理阶段，仅给使用者提供划分服务，但也是很重要的一环；
- 边割率：将大规模划分为多个子图后，子图之间的联系应该尽可能的少，因为子图之间的边是沟通信息的桥梁，为方便计算，子图间的通信应尽可能少；定义为：
\begin{equation}
\text{edge_cut}=\frac{E_{\text{cut}}}{|E|}
\end{equation}
其中，$E_{\text{cut}}$是切割边的边数，$|E|$是总边数。 - 负载均衡：多个子图的规模应该尽可能相似，不然一个子图的规模很大，其他子图的规模很小，在分布式计算平台会严重影响计算速度，即常见的短板效应。定义为：
\begin{equation}
\text{load_balance}=\frac{\text{ver}_{\text{max}}g}{|V|}
\end{equation}
其中，$\text{ver}_{\text{max}}$表示子图中最大的节点数，$g$为最终划分子图的数量，$|V|$是图节点数。
边割率损失定义
假设此时要切割$g$个子图，以$S_k,(k=1,2,\cdots, g)$表示子图的集合。那么$cut(S_k,\bar{S_k})$表示切割出子图$S_k$时要切割的边数，为了防止节点度过大和过小导致的不平衡切割，所以提出了标准化切割$Ncut$：
\begin{equation}
Ncut(S_1,S_2,\cdots,S_g)=\sum_{i=1}^g\frac{cut(S_k,\bar{S_k})}{vol(S_k,V)}
\label{Ncut}
\end{equation}
其中，$vol(S_k,V)$是子图$k$内的节点度数。
使用网络学习边割率
之后的任务就简单了，用神经网络学习出公式 \eqref{Ncut} 的分子和分母即可。假设网络的最后一层的输出是计算当前节点属于子图的概率，那么当划分子图数量为$g$时，输出维度也应该是$g$。$Y\in \mathbb{R}^{n\times g}$，图数据中有$n$个节点，最后的矩阵$Y$的维度就是$n \times g$了，$Y_{ik}$表示第$i$个图节点属于第$k$个子图的概率。
此时计算切分子图$k$的期望：
\begin{equation}
\mathbb{E}[cut(S_k,\bar{S_k})]=\sum _{v_i \in S_k, v_j\in N(v_i)} \sum_{z=1}^g Y_{iz}(1-Y_{jz})
\end{equation}
其中，$N(v_i)$是节点$v_i$的邻居节点，$1-Y_{jz}$表示节点$v_j$不属于子图$z$的概率。两者相乘，表示切割出子图$S_k(k=1,2,\cdots,g)$的期望，而邻接节点很容易通过邻接矩阵$A$获取，至此，分子计算完毕。
之后考虑分母的计算，假设矩阵$D\in \mathbb{R}^{n\times 1}$表示节点的度的矩阵，那么计算一个子图内节点的度的期望就很容易了：
\begin{equation}
\Gamma = Y^T D，\mathbb{E}[vol(S_k,V)]=\Gamma_k
\end{equation}
此时，便很容易得到边割率的损失$\mathcal{L}_1=\mathbb{E}[cut]/\mathbb{E}[vol]$。
负载均衡损失定义
考虑边割率的同时，也要考虑到子图之间的负载均衡，即各个子图的规模大小应尽可能的相似。当图节点为$n$，切分为$g$个子图时，每个子图内的节点的数量应该和$n/g$相近。所以负载均衡的损失$\mathcal{L}_2$计算方式为：
\begin{equation}
\mathcal{L}_2 =\sum_{j=1}^g\Big( \sum_{i=1}^nY_{ij}-\frac{n}{g}\Big)^2
\end{equation}
综上，损失函数为$\mathcal{L}_1+\mathcal{L}_2$。
节点的嵌入学习
在论文中，最重要的一点是如何使用网络处理图数据，并定义损失函数，即如何将图划分问题迁移到NN中。
所以对图嵌入模块，只想忽略的介绍。在图划分模块之前还有图嵌入模块，即使用 GNN 来学习节点的嵌入表示，随着层数的加深不断的更新节点的表示。文中使用的网络为 GraphSAGE 和 maxpool 策略，在图划分的过程中不断的学习节点的嵌入表示，两者同时进行。
此外需要注意的是，损失函数是要对$Y$求偏导并计算梯度的，$Y$在反向传播回$x$的嵌入表示并调整。
本文并不想在这里展开 GNN 的介绍，如果想简单理解可以参考 bilibili 李宏毅最新的机器学习课程，里面讲的很详细。在图规模不断扩大时，基于谱方法的 GNN 之类不再适用，如 GCN，因为这种网络需要传入邻接矩阵这样大规模的参数。
代码
有人用 pytorch 复现了一份 ：
https://github.com/saurabhdash/GCN_Partitioning
代码我看过了，并做了一定的修改，上面的代码很多地方不够规范（懂得都懂）。额外添加了详细的中文注释以及$\mathcal{L}_2$的损失函数和梯度下降，待目前工作结束后开源。
