Multi-level Graph Convolutional Networks for Cross-platform

2022-08-12

用于跨平台锚定节点对齐的多层次图卷积神经网络

我们提出了一种新的框架，即统一考虑局部网络结构和超图结构上的多层图卷积。我们提出了一种双相空间协调机制，在基于网络划分的并行训练和不同社交网络的账户匹配中调整嵌入空间，以便其能适用于大规模社交网络。

与简单图相比，超图允许一条边（也就是同端边）同时连接两个以上的节点。这意味着图中节点之间的非成对关系可以很容易地组织起来并表示为超边。此外，超图是鲁棒的、灵活的，可以适应各种各样的社会网络，无论给定的网络是纯社会网络或具有各种类型的异质社会网络属性和链接。

提出了一个多层图卷积网络MGCN，联合学习在不同粒度w.r.t.级别上的网络顶点的嵌入灵活的GCN内核(即，简单的图GCN，超图GCN)。社交网络的简单图结构信息反映了用户之间的关系，超图就是反映了不同网络的语义信息。例如，基于N跳邻居的超图(用户的n跳邻居通过同一超边缘连接)在某种程度上代表了朋友圈。基于中心性的超图表示不同的社会水平（具有相似中心性价值观的用户可能具有相同的社会地位）。因此，通过定义各种超图并将其交互到网络嵌入学习中，将促进选择更好的用户表示。为了支持这一点，我们提出的MGCN框架是灵活的，并且可以合并各种超图定义，它可以将任何超图作为向量表示，使模型结构对各种超图定义不变。

通过扩展GCN来开发和整合超图背后的基本原理是，超图提供了一个更灵活的网络表示，可以包含额外的和更丰富的信息组合，针对局部网络拓扑上的单个图gcn。一般的GCN只有两层，所以只能获取一个结点的局部特性。

作者这里提出了一种新的训练方式，首先将大规模的社交网络划分为集群，并以完全分散的方式学习网络嵌入。为了对齐学习到的不同簇的嵌入空间，我们提出了一种新的两相空间和解机制。在第一阶段，我们对齐从同一网络中的每个簇中学习到的嵌入空间。除了同一网络中不同子网络之间的对齐外，第二阶段空间和解还通过少量的观测锚定节点对两个不同的网络进行对齐。

展开全文 >>

形式语言与自动机理论

2022-07-28

1. 基础

集合A的n次幂($n≥0$)递归地定义为： \[ \begin{equation} A^n= \begin{cases} \left\{\varepsilon\right\}& \text{ $ n=0 $ } \\ A^{n-1}A& \text{ $ n≥1 $ } \end{cases} \end{equation} \]

克林闭包：$\Sigma^*=U_{i=0}^{∞} \Sigma^i$
正闭包：$\Sigma^+=U_{i=1}^{∞} \Sigma^i$
$\Sigma^*=\Sigma^+ \or \left\{\varepsilon\right\}$

2. 有限状态机

确定的有穷状态机的模型如下：

确定的有穷自动机(DFA)定义为：A的五元组：$A=(Q,\Sigma,\delta,q_0,F)$。

Q：有穷状态集
$\Sigma$：有穷输入符号集或字母表
$\delta$：$Q\times \Sigma \to Q$，状态转移函数
$q_0 \in Q$：初始状态
$F \subseteq Q$：终结状态集或接收状态集

状态转移图如下：

扩展转移函数

扩展$\delta$到字符串，定义扩展转移函数$\hat \delta:Q \times \Sigma^* \to Q$为： \[ \begin{equation} \hat \delta(q,w)= \begin{cases} q& \text{ $ w=\varepsilon $ } \\ \delta(\hat \delta(q,x),a)& \text{ $ w=xa $ } \end{cases} \end{equation} \] 其中$a \in \Sigma, w,x \in \Sigma^*$，那么当$w=a_0a_1...a_n$，则有$\hat \delta(q,w)=\delta(\hat \delta(q,a_0a_1...a_{n-1}),a_n)...$就这样一直嵌套递归下去。

DFA的语言与正则语言

定义：若$D=(Q,\Sigma,\delta,q_0,F)$是一个DFA,则D接受的语言为：$L(D)=\left\{w \in \Sigma^*| \hat \delta(q_0,w) \in F\right\}$

定义：如果语言L是某个DFA D的语言，即$L=L(D)$，则称L是正则语言。

非确定有穷自动机

非确定有穷自动机（NFA）的形式定义：

$A=(Q,\Sigma,\delta,q_0,F)$

Q：有穷状态集
$\Sigma$：有穷输入符号集或字母表
$\delta:Q\times \Sigma \to 2^Q$状态转移函数
$q_0 \in Q$：为初始状态
$F \subseteq Q$：为终结状态集或接受状态集

DFA和NFA的等价性

定理1：如果L被NFA接受，当且仅当L被DFA接受。

非确定性并没有增加有穷自动机的能力。

带有空转移的非确定有穷自动机

空转移指的是不消耗字符串就能够进行转移的，空串$\varepsilon$。

定义为如下：

$\varepsilon-NFA,NFA,DFA$之间的主要区别：

NFA,$\varepsilon-NFA$自动机在某状态读入某个字符时，可能有多个转移。
$\varepsilon-NFA,NFA,DFA$在读入某个字符时，可能没有状态转移
$\varepsilon-NFA$自动机在某状态，可能不读入字符就进行转移

状态的$\varepsilon-$闭包

状态q的$\varepsilon-$闭包记为$E_{CLOSE}(q)$，表示从q经过$\varepsilon \varepsilon ... \varepsilon$序列可达的全部状态集合，递归定义为：

$q \in E_{CLOSE}(q)$
$\forall p \in E_{CLOSE}(q)$，若$r \in \delta(p, \varepsilon)$，则$r \in E_{CLOSE}(q)$

3. 正则表达式

正则表达式的递归定义：

如果$\Sigma$为字母表，则$\Sigma$上的正则表达式递归定义为：

$\varPhi$是一个正则表达式，表示空语言
$\varepsilon$是一个正则表达式，表示语言$\left\{\varepsilon\right\}$
$\forall a \in \Sigma$，a是一个正则表达式，表示语言$\left\{a\right\}$
如果正则表达式$r$和$s$分别表示语言R和S，那么$r+s,rs,r^*,(r)$都是正则表达式，分别表示语言：$R \or S, R \cdot S,R^*,R$

正则表达式的优先级：

首先括号优先级最高
其次$r^*$
然后是连接运算$rs, r \cdot s$
最后加最低$r+s,r \or s$

正则表达式示例：

定理：若$L=L(A)$是某DFA A的语言，那么存在正则表达式R满足$L=L(R)$

展开全文 >>

Multi-level Graph Convolutional Networks for Cross-platform

2022-06-27

跨平台锚定链路预测的多层次图卷积网络

现有的方法要么严重依赖于高质量的用户已生成的内容（包含用户的配置文件），或者如果只关注网络拓扑，就会出现数据不足问题，使研究人员陷入不可解决的模型选择困境。为了解决这一问题，我们提出了一个新的框架，即统一考虑局部网络结构和超图结构上的多层次图卷积。该方法克服了现有工作中的数据不足问题，不一定依赖于用户人口统计信息。此外，为了使所提出的方法能够处理大规模的社交网络，我们提出了一种双相空间和解机制来对齐两个网络分区中的嵌入空间基于不同社交网络的并行训练和账户匹配。

展开全文 >>

多元信用评估系统

2022-06-20

1. 共享模式发现

训练时，首先针对每个社交媒体网络，根据用户社会多媒体行为建立每个用户的行为特征表示。然后利用大量的无人口统计属性标注的用户行为数据，通过多源自编码器来无监督的学习用户稳定的特征表示。在得到了用户稳定的特征表示后，将已知人口统计属性作为监督，利用常用的支持向量机等分类器进行用户人口统计属性推断模型的训练。

预测时，给定在不同社交媒体网络上的网络行为，先提取用户行为特征，然后根据多源自编码器获得用户的稳定特征表示后，利用训练得到的模型推断出用户的人口统计属性。

共享模式发现

当然我们这里没有三个网络，我们可以将微博转发和微博原创当做两个网络。

两个社交媒体网络上的稳定特征：

两个社交媒体网络上的行为特征$f^t,f^t$通过互相重构的方式，将同一用户的两个社交媒体网络上的行为特征，映射到用户的人口属性空间，在最小化重构误差过程中，获得的隐特征$h^{tg}$和$h^{gt}$即为用户人口属性空间的特征表示。

$h^{gt}=encoder^t(f^t):=\zeta(W_e^tf^t+b_e^t)$：将$f^t$编码

$\widetilde f^{gt}=decoder^g(h^{gt}):=W^g_dh^{gt}+b_d^g$：

$h^{tg}=encoder^g(f^g):=\zeta(W_e^gf^g+b_e^g)$

$\widetilde f^{tg} = decoder^t(h^{tg}):=W_d^{t}h^{tg}+b_d^t$

$\Phi_t=\sum_{u\in U}||f^t-\widetilde f^{tg}||^2_2$

$\Phi_g=\sum_{u\in U}||f^g-\widetilde f^{gt}||^2_2$

2. 基于多源信用数据信用评估

基本的思路就是：首先基于多源数据关联和共享模式发现方法获得同一个自然人的由多源行为数据到稳定用户属性之间的映射，然后基于用户属性预测信用等级情况。

在集成学习框架的第一层，首先分别从微博和网易云音乐两个中文社交媒体网络上的动态信息中提取用户的行为特征。然后根据层次自编码器，寻找行为特征之间的共享模式。

最后，分别使用SVM，决策树和逻辑回归，根据一致和稳定的用户特征表示得到用户属于各个信用等级的概率大小，将其作为第一层提取出的高层次特征和第二层的输入特征。

在集成学习框架的第二层，将第一层得到的高层次特征和用户在微博上除了动态信息外的12种信息串联起来，使用GDBT作为分类器，对用户信用进行评估。第二层输入特征只有17维，既有连续值，又有离散值。使用的是GDBT算法进行分类。

展开全文 >>

研究工作笔记

2022-06-19

1. embedding部分

1.1 splitter的embedding

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

测试所用图

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

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

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

self.components = {}
self.personalities = {}
self.index = 0
for node in tqdm(self.graph.nodes()):
    self._create_egonet(node)

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的结构就是：

{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映射为新的结点：

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对应的顶点添加连边。

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问题的。

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^*$

代码如下：

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$，这个是啥意思了？

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

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^*$。

展开全文 >>

操作系统

2022-06-17

0. 操作系统笔记

more >>

展开全文 >>

Boosting Graph Alignment Algorithms笔记

2022-06-15

1. 简介

作者研究了我们研究了两种最先进的图形对齐算法，利用节点表示，CONE-Align以及GRASP算法，并以一个总体的模块化框架来描述它们。

网络对齐任务一般包含以下：

embed：为每个节点创建embedding
align：对齐两个图的嵌入空间，使相似的节点在公共空间中彼此接近。
assign：通过一些线性分配算法来匹配变换后的嵌入数。

作者研究了三种模块的对齐算法REGAL，CONE-Align以及GRASP，并对CONE-Align以及GRASP提出了改进。

一些参数：

graph alignment：给定两个无向图：$G_1=(V_1,E_1)$和$G_2=(V_2,E_2)$，图对齐就是将两个网络中的结点互相对齐。

node embedding：嵌入函数$f(v) \in R^k$是节点v的表示。

graph laplacian：$\mathcal{L}=I-D^{-1/2}AD^{-1/2}$,其中A是G的邻接矩阵，D是度矩阵$D_{ii}=\sum_{j=1}^nA_{ij}$。这个矩阵的特征分解是$\mathcal{L}= \Phi \Lambda \Phi^T$，其中$\Lambda$是特征值的对角矩阵。其对角线，$\left\{\lambda_1,...,\lambda_n\right\}$是L的谱，$\Phi_{\mathcal{L}}=[\phi_1 \phi_2...\phi_n]$是特征向量矩阵。特征向量可以解释为为每个节点分配一个实值的函数。

展开全文 >>

Splitter笔记

2022-06-06

Splitter笔记

more >>

展开全文 >>

Towards Improving Embedding Based Models of

2022-06-02

利用伪锚定改进基于嵌入的社会网络对齐模型

more >>

展开全文 >>

Chris Peng

Multi-level Graph Convolutional Networks for Cross-platform

用于跨平台锚定节点对齐的多层次图卷积神经网络

形式语言与自动机理论

1. 基础

2. 有限状态机

扩展转移函数

DFA的语言与正则语言

非确定有穷自动机

DFA和NFA的等价性

带有空转移的非确定有穷自动机

状态的\(\varepsilon-\)闭包

3. 正则表达式

Multi-level Graph Convolutional Networks for Cross-platform

跨平台锚定链路预测的多层次图卷积网络

多元信用评估系统

1. 共享模式发现

2. 基于多源信用数据信用评估

研究工作笔记

1. embedding部分

1.1 splitter的embedding

2. 对齐部分

2.1 wasserstein距离的应用

2.2 CONE-Align的具体做法

操作系统

0. 操作系统笔记

Boosting Graph Alignment Algorithms笔记

1. 简介

Splitter笔记

Splitter笔记

Towards Improving Embedding Based Models of

利用伪锚定改进基于嵌入的社会网络对齐模型