Splitter笔记
这篇论文的最大的亮点就是将一个结点基于自我网络的原则分解，每个表示编码节点在节点参与的不同本地社区中的角色。嵌入方法能否从真实图的重叠聚类结构中获益？
这里考虑的是无向图，\(G=(V,E)\)，\(G[U]=(U,E \and U \times U)\)为G的结点的子集的诱导图（这里的\(U \times U\)可以理解为有\(U \times U\)条边，当然这些边都得在原图中存在，所以取了个交集）。\(N_u=\left\{v;(u,v) \in E\right\}\)就是结点u的邻居集合，而它的ego-net就是在其邻居诱导出来的图\(G[N_u]\)，u的ego-net并不包含结点u本身。令\(\mathcal{A}\)作为输入的非重叠聚类算法，返回的就是将结点集合V划分为t个不相交的集合\(A(G)=(V_1,V_2,...,V_t)\)。
首先这个论文考虑了一个persona分解的东西。首先使用在一个节点的自我网络中（它的邻居和它们的诱导子图）中发现的集群作为基础来定义一个新的图，即人物图，\(G_P\)。将新的图里面的结点称为personas，将G中每个原始节点的交互划分为几个语义子组，这些子组捕获其网络行为的不同组件。
persona decomposition要做的就是将原始图G转换为persona graph \(G_P\)：
- 对于每个节点\(u \in V\),使用聚类算法\(\mathcal{A}(G[N_u])=\left\{N_u^1,N_u^2,...,N_u^{t_u}\right\}\)，其中\(t_u=np_{\mathcal A}(G[N_u])\)。
- 创建一个personas集合\(V'\)，在V中的每个节点\(v_0\)对应在\(V_P\)中的\(t_{v_0}\)个personas（也就是\(v_0\)的ego-net的分割数），表示为\(v_i\)，\(i=1,...,t_{v_0}\)。
- 为personas之间添加边。如果\((u,v)∈E,v∈N_u^i,v∈N_v^j\)，那么添加一个边\((u_i,v_j)\)到\(E_P\)中。
构造的persona graph具有以下的性质：
- 每个位于\(G_P\)中的结点都是来自原始网络中的结点，分割为一个或者多个personas。
- 原始图中的每个节点都可以映射到其相应的角色。但是\(G_P\)的社区结构和原始网络比起来很不一样。
上面创建的\(G_P\)确实可以给每个结点创建多个embeddings，但是存在的问题就是创建的\(G_P\)可能与原始网络非常的不一样，可能会存在许多不相连的组件，即使他们在原始网络中是相连的。
作者在这里提出了两个改进的策略：
（1）提出添加约束条件，persona表示不仅仅能预测在\(G_P\)中其周围的personas，也能够预测原始结点。给定一个persona \(v_i\)，作者提出要求它的表示包括对原始图G中的节点\(v_o\)的依赖性：\(Pr(v_0| \Phi_{G_P(v_i)})\)。
为了控制图正则化的强度，引入参数λ，那么就产生了下述的优化问题：
（2）作者提出来将v的personas表示\(\Phi_{G_P}(v)\)依赖于原始的表示\(\Phi_G(v)\)通过初始化作为一个先验知识。初始化所有的personas为\(R^d\)中的同一个位置，结合正则表达的形式，将角色嵌入约束，使其表现为单个实体的内聚部分。
最后整个的算法流程为：
首先创建persona graph，初始化\(\Phi_G\)，遍历所有结点\(v_0\)及其personas，初始化\(v_0\)的第j个persona。
persona graph的创建
这篇论文中提出的ego-net的分割方法也是Google research发表的在2017 KDD会议上的论文。文章架构分为两步：首先是局部的ego-net分析，然后是全局的网络划分。
这里说的是有三个重叠的区域：\(\left\{a,b,c\right\},\left\{c,d,e,f\right\},\left\{f,g,h\right\}\)。当我们要由c的邻居生成的图的时候，c的两个社区是很容易发现的，它们完全对应于这两个相互连接的组件\(\left\{a,b\right\}\)以及\(\left\{d,e,f\right\}\)。所以通过使用连接的组件，论文提出的方法能够检测出即使只有一个单节点c，但是c实际上有两个personas，并且这会将c拆分为两个不同的节点：\(c_1\)和\(c_2\)。注意到除了节点c和节点f，其他的结点是只有一个单独的社区。我们的算法保留这些结点在特定的persona，比方说\(d_1\)是在d的case中的。
经过第一个局部的步骤之后，在第二阶段的全局步骤中，连接组件算法可以轻松的检测到图的重叠社区结构，通过将persona graph划分为集群\(\left\{a_1,b_1,c_1\right\},\left\{c_2,d_1,e_1,f_1\right\},\left\{f_2,g_1,h_1\right\}\)，这些也就是在原始图中的重叠集群。
在重叠社区发现问题中，目标就设计算法\(R\)，输入的是无向的图\(G=(V,E)\)，并且输出一个集合\(S'=R(G)\)，是节点集合V的子集，我们称之为聚集，任意两个聚集之间不能相交。
在一个簇重建公式中，我们假设有一组节点的子集S，我们称之为ground-truth集群，算法的任务是恢复这样的簇。为了使检测问题有意义，S和G必须以一种能够从G中提取关于S的信息的方式相关联。
这篇论文设计了两种不同的场景评估算法。首先是标记的数据集，其中图带有元数据，识别已知的社区和我们想要检索的节点子集。第二种场景是生成模型，其中一个随机过程从一组集群中生成一个图，而算法需要恢复那些只能访问该图的集群。
聚类检测问题
给定一个ground truth集群\(C \in V\)以及重构的集群\(C' \in V\)，我们定义精度为\(P(C',C)=|C \and C'|/|C'|\),以及召回：\(R(C',C)=|C \and C'|/|C|\)，F-1 score定义为：
作者这里用两个标准评价集群检测：
F-1 score：给定一个ground-truth 集群S和一个发现的集群S'，F1评分如下：
归一化互信息(NMI)。
给定一幅图\(G=(V,E)\)以及节点子集\(U\)，我们定义诱导图为\(G[U]=(U,E \and U \times U)\)。对于一个结点\(u \in V\)，u的邻域由连接到它的结点组成\(N_u=\left\{v;(u,v) \in E\right\}\)，u的ego-net由在邻域上诱导的图组成\(G[N_u]\)。自我网表示来自图连接上的节点u的局部视图(注意，u的自我网不包括节点u)。
有两个非重叠的聚类算法：局部聚类算法\(A^l\)以及全局聚类算法\(A^g\)，ego-splitting算法处理一个输入图并且输出一个聚类的集合\(S'\)：
- 第一步：对于每个节点使用局部聚类算法来分割u的ego-net，令\(A^l(G[N_u])=\left\{N_u^1,N_u^2,...,N_u^{t_u}\right\}\)，其中\(t_u=np(A^l,G[N_u])\)
- 第二步：创建personas集合。每个节点u将会跟在personas集合\(V'\)中的\(t_u\)个personas关联，表示为\(u_i\)
- 第三步：在personas之间添加边。如果\((u,v)∈E,v∈N_u^i\)并且\(u∈N_v^j\)，那么就添加一条边\((u_j,v_i)\)到\(E'\)中。
- 第四步：在\(G'=(V',E')\)中使用全局的聚类算法，并且获得V'的分割S''。
- 第五步：对于集合\(C'∈S''\)，\(C(C')=\left\{u \in V | \exist i \ s.t. u_i \in C'\right\}\)
通俗的讲，以上几个步骤就是下面的：首先根据全局的网络遍历所有的节点得到其ego-net（说白了也就是一阶邻居，不包含节点本身），然后找到这些个一阶邻居的分割，分成了多少个就代表这个节点有多少个personas，在新的persona graph添加边首先节点u和节点v得在原始网络中存在边，其次v在u的第i个邻域中，u在v的第j个邻域中，那么就添加ui和vj的边。就比方说上图中的ef连边，他是为了保证原本的连通性不受影响。第四步是使用全局的聚类算法\(A^g\)到\(G'\)中，可以获得划分\(S''\)，
