研究工作笔记

1. embedding部分

1.1 splitter的embedding

首先这个embedding用到了一个非重叠的聚类算法，说白了就是划分子图，并将子图构成一幅新图。在EgoNetSplitter()类中进行了相关的一系列操作。


测试所用图

按照代码中的思路，这个流程可以分为以下几步：

（1）首先对每个节点，划分其ego-net。

ego-net也就是自我中心网络，网络结点由唯一的中心节点ego，以及这个节点的邻居alters组成，边只包括ego与alter之间以及alter与alter之间的边。

1
2
3
4
5
self.components = {}
self.personalities = {}
self.index = 0
for node in tqdm(self.graph.nodes()):
    self._create_egonet(node)
1
2
3
4
5
6
7
8
9
10
11
12
13
ego_net_minus_ego = self.graph.subgraph(self.graph.neighbors(node))#得到一阶邻居子图,构成了一幅图,不包含节点本身，邻居原先有边相连的保留
# 针对当下节点的ego-net的连通节点以idx:nodes_idx的形式存储，idx没有明显的跟节点相关的意义，这个只是局部变量
components = {i: n for i, n in enumerate(nx.connected_components(ego_net_minus_ego))}
# 对于components，如果是上图中的2节点就是{0: {1, 6, 7}, 1: {3}}
new_mapping = {}
personalities = []
for k, v in components.items():#遍历ego-net中的alters
    personalities.append(self.index)#添加全局变量index，也就是表示personas的index
    for other_node in v:#遍历连通的结点，一个连通的alters就是一个persona标号
        new_mapping[other_node] = self.index#将当前的结点映射到persona
        self.index = self.index+1#这个index是对于全局都会相加的
        self.components[node] = new_mapping#对于当前节点，node_idx -> idx的映射，是ego_net中的，对应于personalities中的映射,idx表示personas的序号，也就是原始图中的结点映射到new_mapping中，new_mapping装的是当前原始结点的一阶邻居结点到personas的映射
        self.personalities[node] = personalities#当前节点的personalities就是index，对于全局而言的，所以这个意思就是，我有多少个连通着的邻居，我就有多少个personalities

经过上述的操作之后，self.components的结构就是：

1
{0: {1: 0}, 1: {0: 1, 2: 2, 6: 2}, 2: {1: 3, 6: 3, 7: 3, 3: 4}, 3: {9: 5, 2: 6}, 10: {9: 7, 11: 8}, 11: {10: 9, 12: 10}, 12: {11: 11, 7: 12}, 6: {1: 13, 2: 13, 7: 13}, 7: {2: 14, 6: 14, 12: 15}, 8: {9: 16}, 9: {8: 17, 10: 18, 3: 19}}

怎么解释这个数据结构呢？就是{原始图中的结点：{原始图中结点的一阶邻居：persona结点}}，比方说1结点有0,2,6三个邻居，其中0属于persona1，而2和6都属于persona2。

而self.personalities是：

1
{0: [0], 1: [1, 2], 2: [3, 4], 3: [5, 6], 10: [7, 8], 11: [9, 10], 12: [11, 12], 6: [13], 7: [14, 15], 8: [16], 9: [17, 18, 19]}

这个数据结构为每个节点存储了一个列表，表示当前原始图中的结点被分为哪几个personas。

（2）接下来将personalities映射为新的结点：

1
2
3
4
5
def _map_personalities(self):
    """
    Mapping the personas to new nodes.
   	"""
    self.personality_map = {p: n for n in self.graph.nodes() for p in 			         self.personalities[n]}

最后得到的self.personality_map为：其实也就是persona_node->原始结点的映射。

1
{0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3, 6: 3, 7: 10, 8: 10, 9: 11, 10: 11, 11: 12, 12: 12, 13: 6, 14: 7, 15: 7, 16: 8, 17: 9, 18: 9, 19: 9}

（3）然后我们得在新得到的personas之间添加边

根据论文中所讲的，如果\((u,v) \in E,v \in N_u^i \and u \in N_v^j\)那么就添加一条边\((u_j,v_i)\)到\(E'\)中。什么意思呢？就是说如果在原始图中u和v是有边的，那么显然他们互为一阶邻居，如果v是在u的邻居的第i个连通分量中，而u是在v的第j个连通分量中，那么就在新的persona中的i，j对应的顶点添加连边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def _create_persona_graph(self):
    """
    Create a persona graph using the egonet components.
    这个对应论文中的第四步：在persona graph中使用全局的聚类算法得到一个分类S''
    """
    print("Creating the persona graph.")
    self.persona_graph_edges = [self._get_new_edge_ids(e) for e in tqdm(self.graph.edges())]
    self.persona_graph = nx.from_edgelist(self.persona_graph_edges)

def _get_new_edge_ids(self, edge):
    """
    Getting the new edge identifiers.
    Args:
        edge: Edge being mapped to the new identifiers.
    往新的图中添加边，所谓的新的图就是有多少个personas就有多少个结点
    self.components针对{node_idx:{当下节点的ego-net的连通节点以idx:nodes_idx的形式存储}}
    测试中为{0: {1: 0}, 1: {0: 1, 2: 2, 6: 2}, 2: {1: 3, 6: 3, 7: 3, 3: 4}, 3: {9: 5, 2: 6}, 10: {9: 7, 11: 8},
    11: {10: 9, 12: 10}, 12: {11: 11, 7: 12}, 6: {1: 13, 2: 13, 7: 13}, 7: {2: 14, 6: 14, 12: 15},
    8: {9: 16}, 9: {8: 17, 10: 18, 3: 19}}

    原始图中的边为：[(0, 1), (1, 2), (1, 6), (2, 3), (2, 7), (2, 6), (3, 9), (10, 11),
    (10, 9), (11, 12), (12, 7), (6, 7), (8, 9)]

    测试的输出的边为：[(0, 1), (2, 3), (2, 13), (4, 6), (3, 14), (3, 13), (5, 19),
    (8, 9), (7, 18), (10, 11), (12, 15), (13, 14), (16, 17)]
    函数输入的是原始图中的边，输出的是应该添加到新的图中的边
    那么如何添加呢？

    输入边(1,2)，函数返回的是(self.components[1][2], self.components[2][1])
    也就是(2, 3)
    为啥要这样？
    self.components[1][2]定位的是1结点的2这个一阶邻居结点在新图中对应的persona
    self.components[2][1]定位的是2结点的1这个一阶邻居节点在新图中对应的persona
    因为在原始图中这两个分出来的persona是相连接的，所以我们必须给他连一条边

    这里必须有的概念是：
    同一个节点在不同的节点的一阶邻居中的persona是不一样的，因为persona都是在自增的，如果说有边的话
    这样做的目的就是为了把节点从拓扑上分割开来，让节点充当有不同的角色，注意这个是单纯考虑拓扑结构的。
    """
    return (self.components[edge[0]][edge[1]], self.components[edge[1]][edge[0]])

首先进行的是构建新的连边函数_get_new_edge_ids()，输入边(1,2)，函数返回的是\((self.components[1][2], self.components[2][1])\)，也就是(2, 3)，为啥要这样？ \(self.components[1][2]\)定位的是1结点的2这个一阶邻居结点在新图中对应的persona \(self.components[2][1]\)定位的是2结点的1这个一阶邻居节点在新图中对应的persona 因为在原始图中这两个节点是相连接的，那么分出来的persona也应该是相连接的，所以在新构建的图中我们必须给他连一条边。 最后根据这些连边的关系，构建出一幅新的图，注意：新图可能是并不全连通的，而且新图中的边的数量等于原图中的边的数量。

在得到新图之后，断开的组件可能给图表示学习造成很多困扰，所以提出两点来解决这个问题。

  • 首先，我们建议添加一个约束条件，即角色表示除了能够预测GP中它周围的角色外，还能够预测它们的原始节点。给定一个persona \(v_i\)，我们提出求出其embedding包括对原始图G中的节点vo的依赖性：

    \(Pr(v_0| \Phi_{G_P(v_i)})\)

    为了控制图正则化的强度，我们引入了参数λ,结合了deepwalk的优化方程就会产生以下的优化问题：

    \(minimize_{\Phi_{G_P}} -logPr({v_{i-w},...,v_{i+w}/ v_i}| \Phi_{G_P}(v_i)- \lambda logPr(v_0| \Phi_{G_P}(v_i)))\)

    说白了这个就是用原来的图去监督现在的persona的图表示学习，不要让它偏离的过分。

  • 其次，还使用原始的结点表示\(\Phi_G(v)\)初始化结点v的persona图的结点表示，将这个作为先验。

这个地方还得研究的是：1. 首先优化函数loss要如何能酷炫点？魔改一下，为了让其适用于网络对齐任务。2. 试试看别的模型，比方说deepwalk，node2vec还有GCN对整体的影响。3. 是否可以加上用户的属性信息作为监督，怎么加呢？直接concat？还是弄个神经网络计算loss。4. 如何让网络对齐任务和embedding部分融合的更好。

2. 对齐部分

上面我们所做的是得到了一个图，将原本可能全连通的图变成了一个非全连通的图。

2.1 wasserstein距离的应用

paper：

这个论文解决的问题是：未能达到匹配的邻居一致性：在一个图中接近的节点通常与在另一个图中接近的节点不匹配。出于这个考虑，作者使用的是proximity-preserving node embedding methods。

在这里作者解决了两个问题，分别如下：

  • procrustes问题：\(min_{Q \in O^d}||Y_1Q-Y_2||^2_2\)，这个问题就是正交普鲁克问题，可以直接给出最优解的。

    这个问题的求解等价于求\(Q^*=UV^T\)，其中\(U \Sigma V^T\)是\(XY^T\)的SVD分解，Q是正交的矩阵。

  • wasserstein问题：\(min_{P \in P^n}||Y_1-PY_2||\)

首先这个论文要解决的就是一个凸初始化的问题，\(min_{P \in B^n}||(A_1P-PA_2)||_2^2\)，其中的\(B^n\)是\(P^n\)的凸包，可以使用frank-wolfe算法得到\(P^*\)，这个可以通过\(n_0\)次的迭代以及正则化参数\(\lambda_0\)来实现，使用\(Y_1\)和\(P^*Y_2\)，初始化的\(Q\)可以被正交的procrustes方法来生成。

首先介绍sinkhorn算法，细节不去深究，直接上代码，这个就是为了求解optimal transport问题的。

1
2
3
4
5
6
7
8
9
10
11
12
13
ot.bregman.sinkhorn(a, b, M, reg, method='sinkhorn', numItermax=1000, stopThr=1e-09, verbose=False, log=False, warn=True, **kwargs)
'''
a: shape(dim_a)对源网络的权重的采样
b: shape(dim_b)对目标网络的权重的采样
M: 代价函数
reg: 正则化项, >0
stopThr: 迭代终止的loss


return: 
		gamma(shape(dim_a, dim_b)): 最优传输矩阵
		log: 仅当参数中的log==True时，日志字典才会返回
'''

解决的是熵正则化的最优传输问题，并且返回最优传输矩阵。最优化的问题如下：

\(\gamma^* = arg\ min_y \ <\gamma, M>_F+reg * \Omega( \gamma)\)

约束条件为：

\(s.t. \ \gamma \vec 1 = \vec a\)

\(\gamma ^T \vec 1\)=\(\vec b\)

\(\gamma = \geq 0\)

其中：

  • M是代价函数：\((dima_a, dim_b)\)
  • \(\Omega\)是熵正则化，\(\Omega(\gamma)= \Sigma_{i,j} \gamma_{i,j}log(\gamma_{i,j})\)
  • \(\vec a, \vec b\)是源和目标权重，两者求和都是1

利用frank-wolfe算法和sinkhorn来求解可以得到一个最优的初始化的\(P^*\)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
for it in range(1, niter + 1): # 10轮次的迭代？
    if it % 10 == 0: print(it)
    '''G就是初始化要用的min ||(A_1P - PA_2)||'''
    G = P.dot(K2_X) + K2_Y.dot(P) - 2 * K_Y.dot(P.dot(K_X))
    # G = G.todense() #TODO how to get around this??
    # TODO 为啥会出现matrix类型呢？
    if (type(G) == np.matrix): # G有可能出现的是matrix类型，转换了
        G = G.A
    q = ot.sinkhorn(np.ones(n), np.ones(n), G, reg, stopThr=1e-3) # 得到了最优传输矩阵
    q = sparse.csr_matrix(q) # 压缩稀疏矩阵
    #print q.shape
    alpha = 2.0 / float(2.0 + it)
    P = alpha * q + (1.0 - alpha) * P # P是最先初始化的, frank-wolfe算法更新方向

然后求解\(min_{Q \in O^d}||Y_1Q-PY_2||\)可以得到一个初始化的\(Q_0\)，显然这个是个正交procrustes问题，可以通过\(P^*YX^T\)的SVD得到。

2.2 CONE-Align的具体做法

  • 首先要进行初始化的步骤：

\(P^*=argmin_{P∈B^n}||(A_1P-PA_2)||_2^2\)，这个是啥意思了？

这里相当于引入两个图的邻接矩阵，用两个图的邻接矩阵来进行初始化的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n, d = X.shape
if apply_sqrt:
    X, Y = sqrt_eig(X), sqrt_eig(Y)
if K_X is None:
	K_X = np.dot(X, X.T)
if K_Y is None:
    K_Y = np.dot(Y, Y.T)
K_Y *= sparse.linalg.norm(K_X) / sparse.linalg.norm(K_Y)
K2_X, K2_Y = K_X.dot(K_X), K_Y.dot(K_Y)
#print K_X, K_Y, K2_X, K2_Y
K_X, K_Y, K2_X, K2_Y = K_X.toarray(), K_Y.toarray(), K2_X.toarray(), K2_Y.toarray()
P = np.ones([n, n]) / float(n)
for it in range(1, niter + 1):
    if it % 10 == 0: print(it)
    G = P.dot(K2_X) + K2_Y.dot(P) - 2 * K_Y.dot(P.dot(K_X))
    #G = G.todense() #TODO how to get around this??
    if (type(G) == np.matrix): # G有可能出现的是matrix类型，转换了
        G = G.A
    q = ot.sinkhorn(np.ones(n), np.ones(n), G, reg, stopThr=1e-3)
    q = sparse.csr_matrix(q)
    #print q.shape
    alpha = 2.0 / float(2.0 + it)
    P = alpha * q + (1.0 - alpha) * P
obj = np.linalg.norm( P.dot(K_X) - K_Y.dot(P) )
print(obj)
return utils.procrustes(P.dot(X), Y).T, P

首先：\(K_X=X*X^T,K_Y=Y*Y^T\)

然后计算得到：\(K_Y=K_Y*||K_X|| \div ||K_Y||\)

\(K2_X=K_X*K_X=X*X^T*X*X^T\)

\(K2_Y=K_Y*K_Y\)

这个函数就是用frank-Wolfe算法来求解这个\(P^*\)。

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

永远保持对技术的那颗追求的心。