introduction
内在网络属性信息对对齐结果的直接影响在很大程度上仍然是未知的。针对该挑战，提出了一个主动网络对齐方法(ATTENT)确定要查询的最佳节点.该方法的关键思想是利用定义在对齐解决方案上的有效和高效的影响函数来评估可供查询的候选节点的有效性。提出的方法具有以下优点：（1）有效性：能够准确地量化候选节点对对齐结果的影响；（2）高效性：线性扩展与15 17×加速比直接实现没有任何质量损失；（3）普适性：不断提高各种网络对齐算法的对齐性能。
一开始的时候网络对齐是困难的，因为节点2可能与节点e或者节点b对齐。通过查询节点1和4并且获得他妈的正确的对齐节点a和d，所有的其他节点都会被正确的对齐由于拓扑一致性。但是，如果我们随机的查询节点2和节点5，剩余的1346节点的正确对齐仍无法获得。例如我们无法知道1是和a还是c对齐。
但是现在对于如何主动获取高质量的anchor links以进一步提高网络的对齐精度还没有被很好的研究过。现有的查询机制可能存在以下几个问题：首先，查询对对齐的直接影响没有被很好的研究，因为查询节点的选择本身就依赖于对齐的采样结果；其次，网络属性信息如何改进主动网络对齐中的查询策略，目前还没有深入研究；最后，它可能会根据特定的采样策略而具有较高的计算复杂度。
本文中处理这些问题，并且提出了一个基于影响函数的查询策略（ATTENT）针对特征网络对齐，根据查询结果对网络对齐结果的影响情况向人工标注器建议最佳的查询来标记正确的对齐。该查询方法的关键思想是利用定义在网络对齐结果上的影响函数来评估要查询的候选节点的有效性。具体来说，给定了来自属性网络对齐算法的对齐解向量，我们将查询的信息量化为我们提出的关于与查询相关的对齐结果的效用函数的变化率。我们进一步提出了有效的算法来加速和扩大计算规模。
我们的贡献如下：
- problem formulation。我们正式定义了主动归属网络对齐问题
- algorithms and analysis。我们提出了一类基于影响函数的查询算法(Attent)来解决主动归属网络对齐问题，它适用于多种网络对齐算法。我们进一步提出了有效的算法来加速和扩大计算，具有线性复杂度。
- empirical evaluations。我们对真实数据集进行了广泛的实验评估，以测试我们提出的方法的有效性。
算法
文章的参数如下：
Attributed network alignment。关键点在于三个原则：拓扑一致性、节点属性一致性、边属性一致性。从优化的角度来说，属性网络对齐旨在找到一个解方程\(X∈R^{n_t \times n_s}\)表示跨网络节点相似度，最小化前三个方面的不一致并且向量化的阶矩阵也就是\(x=vec(X)\)是通过求解以下方程得到的：
其中，\(h=mat(H,n_t,n_s)\)，\(H∈R^{n_t \times n_s}\)是对齐偏好矩阵表示两个输入网络之间的首选节点相似度（也就是先验知识），\(α∈(0,1)\)是正则化参数，它确定对齐结果向量x与偏好向量h的接近程度，\(\widetilde W\)编码拓扑结构、节点属性和边属性的一致性的矩阵,并且\(\widetilde W=D^{-1/2}WD^{-1/2}\)是归一化的\(W=N_X(E_X \odot A_X)N_X\)，对角矩阵D是用来归一化W，被定义为\(\mathbf{D}=\mathbf{N}_{\times} \operatorname{diag}\left(\sum_{i=1}^{K} \sum_{j=1}^{L}\left[\left(\mathbf{E}_{s}^{j} \odot \mathbf{A}_{s}\right) \mathbf{N}_{s}^{i}\right] \otimes\left[\left(\mathbf{E}_{t}^{j} \odot \mathbf{A}_{t}\right) \mathbf{N}_{t}^{i}\right]\right)\)。由于Kronecker product的特性（\((C^T \otimes A)vec(B)\)）解向量x可以通过一种有效的迭代方法来计算，使用以下方程:
Q是\(q=N_XD^{-1/2}\)以列的顺序改变形状后的结果。如果没有节点和边的属性信息，公式1退化为\(x=αD_n^{-1/2}A_XD_n^{-1/2}x+(1-α)h\)，其中\(D_n=diag([A_s1] \otimes [A_t1])\)其中1是全1向量。
对齐偏好矩阵H包含这两个输入网络中的两个节点有多相似的先验知识。在属性网络对齐的主动学习设置中，引入了一个人工注释器来提供一些正确对齐的先验信息，并用于更新偏好垫 以最大限度地提高网络对齐算法的性能。
问题定义
一般来说，主动学习的目标是通过标记从整个训练数据中尽可能少的样本来最大限度地提高学习性能。在主动特征网络对齐中，我们假设算法可以与一个Oracle（比方说一个人类注释器）相互作用，可以想要信息的反馈也就是两个网络之间的正确的对齐。在本文中，我们主要考虑到人类注释者可以回答以下问题：给定一个源网络\(G_s\)中的节点\(a_s\)，以及一系列的候选链接\(C_{a_s}\)，在目标网络\(G_t\)中，哪个在\(C_{a_s}\)节点\(a_t\)是\(a_s\)的正确对齐。
给定表示网络对齐解的向量x，我们正式定义了主动属性网络对齐问题如下：
问题1：主动属性网络对齐
给定：（1）一对属性源网络和目标网络\(G_s= \left\{ A_s,N_s,E_s\right\}\)和\(G_t= \left\{ A_t,N_t,E_t\right\}\)，（2）一个初始对齐偏好矩阵\(H_0\)，（3）一个整数查询预算k，（4）一个Oracle，（5）由eq2计算得到的对齐结果向量x，（6）一个效用函数\(f(.)\)
找出：在\(G_s\)中的对\(f(x)\)影响最大的k个节点，使人工注释者在目标网络Gt中标记正确的匹配，从而最大限度地提高Gs中剩余节点的对齐精度。
我们提出了一种定量的方法来评估节点的信息量，基于节点的影响，以产生对齐解的结果。
候选对象查询的信息量
在主动学习中，一种常用的策略是选择在训练机器学习模型时信息更丰富的数据点，比方说利用不确定性来评估查询的信息性，并选择不确定性最大的数据点。主动属性网络对齐的主要目标是找到一种有效的查询策略来标记另一个网络中匹配的节点，从而使剩余节点的网络对齐精度可以最大限度地改进。为了实现有效的网络对齐查询，需要选择查询反馈会对对齐结果产生显著影响的节点，也就是在公式1中的x。表2中列出了我们用来量化对齐解向量的效用函数f（·）的选择，为了说明推导，我们主要使用平方L2范数效用函数。
在本文中，我们提出利用影响函数，这个影响函数与解向量x相关，利用这个影响函数来量化查询的信息量。让我们从不同查询类型对网络对齐结果的影响的两个定义开始。
- definition 1：node pair query对属性网络对齐的影响。给定一个覆盖在对齐解向量上的选定的效用函数，也就是\(f(x)\)。node pair query的影响，表示为\(q_{ij}\)其中节点i在\(G_t\)中，节点j在\(G_s\)中关于f(x)被定义为f(x)对于对齐这对节点的偏好的导数（也就是\(H(i,j)\)）。节点对查询的影响正式的被定义为\(\mathcal{I}\left(q_{i j}\right)=\frac{\partial f(\mathbf{x})}{\partial \mathbf{H}(i, j)}\)
- definition 2：节点查询对属性网络对齐的影响。对于单个节点查询，表示为\(q_j\)其中节点j在源网络\(G_s\)中，这个影响定义为\(G_s\)中节点j与节点pairs之间的影响的聚合，并且所有的节点都在\(G_t\)中，也就是\(\mathcal{I}\left(q_{j}\right)=\sum_{i=1}^{n_{t}} \mathcal{I}\left(q_{i j}\right)\)
接下来，我们将详细介绍如何计算这两种类型的查询w.r.t.的影响给定了一个效用函数f（·）的对齐结果。
A. 节点对查询影响
首先在引理1中计算节点对查询对网络对齐的影响。
引理1：（在属性网络对齐中的节点对影响）对于一个在对齐解向量上选定的效用函数，也就是f(x)，与f(x)相关的某个特定节点对(i,j)的影响可以被如下计算：
其中\(\mathbf{P}=(1-\alpha)(\mathbf{I}-\alpha \tilde{\mathbf{W}})^{-1}\)，并且P是对称的，\(I∈R^{n_sn_t \times n_sn_t}\)是单位矩阵，\(k=(j-1) \cdot n_t+i\)是\(H(i,j)\)的新索引（在我们按列的顺序向量化H之后），对数运算符被明智地应用于元素，而1是一个全1的向量。
证明（1）：我们首先证明使用L2范数的平方作为效用函数的情况，也就是\(f(x)=|||x|^2_2\)。根据公式（1），给出了网络对准的封闭形式解为：
\(\mathbf{x}=(1-\alpha)(\mathbf{I}-\alpha \tilde{\mathbf{W}})^{-1} \mathbf{h}\)
根据定义1，我们使用链式法则并且求与特定的节点对（也就是H(i,j））相关的f(x)的偏导
\(\mathcal{I}\left(q_{i j}\right)=\frac{\partial f(\mathbf{x})}{\partial \mathbf{H}(i, j)}=\left[\frac{\partial f(\mathbf{x})}{\partial \mathbf{x}}\right]^{\prime} \frac{\partial \mathbf{x}}{\partial \mathbf{H}(i, j)}\)
这里，对于第一个求导，\(\frac{\partial f(x)}{\partial x}=2x\)，我们同样向量化表现矩阵H并且表示H(i,j)新的在h中的索引为\(k=(j-1) \cdot n_t+i\)，其中\(n_t\)是\(G_t\)的大小。通过令\(P=(1-α)(I-α \widetilde{W})^{-1}\)，对于第二个偏导数，我们进一步有：
\(\frac{\partial \mathbf{x}}{\partial \mathbf{h}_{k}}=\frac{\partial(\mathbf{P h})}{\partial \mathbf{h}_{k}}=\mathbf{P e}_{k}=\mathbf{P}(:, k)\)
其中\(e_k\)是一个只有一个位置k为1的向量，总共的长度为\(n_s \times n_t\)，第二个偏导返回的是矩阵P的第k行。因为P是对称的，通过合并一切，我们得到了与网络对齐解向量的平方l2范数节点对\((i,j)\)的影响如下：
\(\mathcal{I}\left(q_{i j}\right)=2 \mathbf{P}(:, k)^{\prime} \mathbf{x}=2 \mathbf{P}(k,:) \mathbf{x}\)
证明（2）：对于entropy效用函数的情况，很显然的是，解矩阵的熵是X中的每列的entropy之和，也就是：
\(f(\mathbf{X})=\sum_{s=1}^{n_{s}} f(\mathbf{X}(:, s))\)
我们从计算X中一个列的熵的偏导数开始(如\(s^{th}\)列在\(X(:,s)\))与\(H(i,j)\)相关，由于在表2中的定义，我们有：
相似的，我们表示向量化的X和H中对应项的新索引为\(l=(s-1) \cdot n_t+t,k=(j-1) \cdot n_t+i\)。公式（9）中的偏导为：
\(\frac{\partial \mathbf{X}(t, s)}{\partial \mathbf{H}(i, j)}=\frac{\partial \mathbf{x}_{l}}{\partial \mathbf{h}_{k}}=\frac{\partial \mathbf{P}(l,:) \mathbf{h}}{\partial \mathbf{h}_{k}}=\mathbf{P}(l,:) \mathbf{e}_{k}=\mathbf{P}(l, k)\)
我们进一步有：
\(\frac{\partial f(\mathbf{X}(:, s))}{\partial \mathbf{H}(i, j)}=-\sum_{l=(s-1) \cdot n_{t}+1}^{s n_{t}} \mathbf{P}(l, k)\left(\log \mathbf{x}_{l}+1\right)\)
根据公式（8），通过将所有整合到一起，我们计算节点对的影响与对齐解向量的熵相关的为：
\(\begin{aligned} \mathcal{I}\left(q_{i j}\right) &=-\sum_{s=1}^{n_{s}} \sum_{l=(s-1) \cdot n_{t}+1}^{s n_{t}} \mathrm{P}(l, k)\left(\log \mathbf{x}_{l}+1\right) \\ &=-\mathrm{P}(k,:)(\log (\mathbf{x})+1) \end{aligned}\)
也就得证了。
B. 节点查询的影响
根据引理1和定义2中的节点对查询影响，我们可以直接计算节点查询的影响，这是总结在下面的引理中。
引理2：（节点查询对属性网络对齐的影响）给定一个对齐解向量上的效用函数，也就是\(f(x)\)，特定的节点查询的影响（例如在\(G_S\)中的节点j）表示为\(q_j\)，可以被下面的公式计算：
其中，\(k_{1}=(j-1) \cdot n_{t}+1, k_{2}=j \cdot n_{t}, \mathbf{P}=(1-\alpha)(\mathbf{I}-\alpha \widetilde{\mathbf{W}})^{-1}\)，1是全1向量，\(||\cdot||_1\)表示L1范数。
证明：（1）对于使用L2范数为效用函数的情况，根据定义2，节点查询的影响是在\(G_s\)中的节点j与在\(G_t\)中所有节点对的影响的总和，基于公式（7），对于节点对查询的影响，我们有：
\(\mathcal{I}\left(q_{j}\right)=\sum_{i=1}^{n_{t}} \mathcal{I}\left(q_{i j}\right)=2 \sum_{k=(j-1) n_{t}+1}^{j n_{t}} \mathbf{P}(k,:) \mathbf{x}\)
这表示了通过选择P中从\(((j-1)n_t+1)^{th}\)行到\((jn_t)^{th}\)的子矩阵（如\(P(k_1:k_2,:)\)）并且聚合结果向量的条目（即在\(P(k_1:k_2,:)x\)使用L1范数）我们得到了计算节点查询影响的公式如下：
\(\mathcal{I}\left(q_{j}\right)=2\left\|\mathrm{P}\left(k_{1}: k_{2},:\right) \mathbf{x}\right\|_{1}\)
证明：（2）熵情况的证明类似于(i)通过在相同的索引上选择相同的行的P子矩阵，然后在结果向量上应用l1范数（也就是\(P(k_1:k_2,:)x\)）。因此，与熵相关的节点查询影响是\(\mathcal{I}\left(q_{j}\right)=\left\|\mathrm{P}\left(k_{1}: k_{2},:\right)(\log (\mathrm{x})+1)\right\|_{1}\)
公式（13）需要显式的计算矩阵\(P=(1-α)(I-α \widetilde W)^{-1}\)，这在计算上十分复杂，为了解决这个问题，我们首先定义新的向量\(y=Px\)（以l2范数的平方作为效用函数的情况），其中x是对齐的解向量。为了求解y，我们有：
\(\mathbf{y}=(1-\alpha)(\mathbf{I}-\alpha \widetilde{\mathbf{W}})^{-1} \mathbf{x}\)， \(\Leftrightarrow \mathbf{y}=\alpha \widetilde{\mathbf{W}} \mathbf{y}+(1-\alpha) \mathbf{x}\)
这意味着y可以用迭代幂法来计算出来，因此可以避免对逆矩阵的直接计算。对于熵的情况，我们有以下几点，
\(\mathbf{y}=\alpha \widetilde{\mathbf{W}} \mathbf{y}+(\alpha-1)(\log (\mathbf{x})+\mathbf{1})\)
我们进一步观察到，查询对节点j的影响可以通过以下等效方程来计算，
\(\mathcal{I}\left(q_{j}\right)=\left\|\mathbf{y}_{k_{1}: k_{2}}\right\|_{1}\)
其中，\(k_1=(j-1) \cdot n_t + 1,k_2=j \cdot n_t\)，这意味着我们可以通过聚合y中相应的条目来计算\(I(q_j)\)
提出的算法
A. 针对主动归属网络对齐的一种通用算法
基于引理1和引理2。我们提出了算法1来选择信息最丰富的节点进行查询，以提高网络对齐算法的性能。该算法的关键思想是迭代选择我们提出的定量方法计算出的影响最大的节点（19）（第7步，第10步），查询Oracle的正确对齐（步骤13），更新对齐偏好矩阵，即等式中的H（1）相应地（步骤-14），重新计算对齐结果（步骤15）和其余候选查询节点的影响。（如何利用查询结果来更新网络对齐将在第5.1节的实验设置中介绍。）在算法1中，对齐偏好向量被初始化为均匀单位向量，也就是\(h=1 \times 1/(n_t \times n_s)\)，这意味着我们对对齐结果没有任何先验知识。为了更新H，如果查询结果表明在\(G_s\)中的节点j与在\(G_t\)中的节点i对齐，我们设置\(H(i,j)=1\)并且保持剩余的值不变（即\(H(i,k)|_{k≠j} \ and \ H(k,j)|_{k≠i}\)）。
请注意，算法1提供了一系列基于所选实用程序函数的主动网络对齐查询策略\(f(\cdot)\)，我们使用不同的后缀来区分效用函数，分别用于ATTENT-L2和ATTENT-Entropy。