摘要
在本文中，我们提出了一系列的算法（FINAL）来对齐属性网络。关键思想是利用节点/边缘属性信息来指导（基于拓扑的）对齐过程。我们基于对齐一致性原则从优化的角度来阐述这个问题，并开发有效和可扩展的算法来解决它。
许多的真实网络中往往伴随着边或者节点的属性，这可能为解决节点拓扑一致性假设违反提供了一个互补的解决方案。存在以下三个问题：
- 目前还不清楚如何将节点/边缘属性信息吸收到基于拓扑的网络对齐公式中。
- 基于拓扑的网络对齐背后的优化问题通常是非凸的，甚至是np困难的。
- 我们如何利用真实网络的一些内在属性（如低秩）来扩大属性网络对齐过程？
作者的贡献：
- 我们从优化的角度来制定属性网络对齐。该公式背后的关键思想是利用节点/边缘属性信息来指导基于对齐一致性原则的（基于拓扑的）对齐过程。
- 提出了FINAL算法来解决网络对齐问题
算法
文章的参数如下：
问题1：属性网络对齐
给定两个特征网络\(G_1=\left\{A_1,N_1,E_1\right\}\)以及\(G_2=\left\{A_2,N_2,E_2\right\}\)，分别有n1和n2个节点，一个先验对齐偏好H。
输出：\(n_2 \times n_1\)的对齐矩阵，其中\(S(x,a)\)表示\(G_1\)中的节点a以及\(G_2\)中的节点x的相似度。
在上面的定义中，我们有一个可选的输入，来编码成对对齐偏好H的先验知识，这是一个n2×n1矩阵。H中的一个条目反映了我们对在两个输入网络中对齐两个相应节点的可能性的先验知识。当没有这样的先验知识时，我们设H的所有项都相等。在不失一般性的前提下，我们假设a1和a2具有相同的大小。
有的时候我们可能想要得到一个特定的脸书用户中十大最相似的领英用户。我们可以首先解决问题1，然后在对齐矩阵S中返回相应的行或列，这可能在计算上太昂贵，也不必要。考虑到这一点，我们进一步定义了查询属性网络对齐问题如下：
ON-QUERY属性网络对齐
给定两个特征网络\(G_1=\left\{A_1,N_1,E_1\right\}\)以及\(G_2=\left\{A_2,N_2,E_2\right\}\)，分别有n1和n2个节点，一个先验对齐偏好H。以及一个在\(G_1\)中的查询节点a。
输出：一个n2×1向量sa，有效地测量G1中的查询节点-a和G2中的所有节点之间的相似性。
FINAL：Optimition Formulation
- 拓扑一致性：a和b是在网络G1中的邻居，那么x和y也是在G2中的邻居。
- 节点属性一致性：a和x有同样的节点属性，b和y也有相同的节点属性。
- 边属性一致性：边(a,b)以及(x,y)有同样的边属性值。
如果我们已经知道a和x是对齐的，那么他们紧密的具有相同的属性值的邻居应该有很高的可能性对齐，其中b和y是a和x的紧密的邻居，如果它们是由相同的边属性值连接的。这自然导致了以下目标函数，我们希望用对齐矩阵S来最小化：
其中f是一个节点对规范化函数：
\(f(x,a)\)描述了有多少个邻居对具有以下的性质：1.在他们之间具有相同的节点属性值（比如b和y），2.分别通过相同的边属性值连接到a和x。
\(1(.)\)函数反映了输入的边或者节点是否有相同的属性值，其分解如下：
带入可得：
对于具有相同属性值的节点：
接下来，我们给出了j1的一个等价矩阵形式，这更方便了以下算法的描述和理论证明。通过向量化对齐矩阵S，并且使用元素级别的乘法（两个矩阵的对应位置的元素相乘）以及Kronecker product，等式1可以被重写为：
