SFE: 基于子图特征抽取的关系补全推理
SFE(subgraph feature extraction)是一种改进自 PRA(Path Ranking Algorithm)算法的知识图谱补全方法。其对子图进行特征提取并基于此进行知识图谱的关系推理和补全
PRA算法
传统的PRA算法可以分为两步。第一步为找到通路，即节点之间是否存在路径，找到节点对之间的潜在的路径类型作为统计的特征。第二步则是计算每个路径类型和节点对的Random Walk的概率
其中第二步的计算量非常大，需要的计算时间可以认为是正比于$m^n$，其中m是图的平均出度，n是计算出的特征矩阵中每个单元的路径长度。
对于PRA算法，可以构造一个特征矩阵。矩阵的行是每一对Source node和Target node。而矩阵的列则是在第一步中我们找到的path type。在第二步中，通过一Source node为起点进行多次Random Walk（或者BFS）来进行采样，算出矩阵中每一个cell对应的概率。
SFE算法
SFE算法只使用PRA算法的第一步。作者认为第二步计算量太大而且随机游走的概率没啥用，因而只采用了二值特征（那对于特征矩阵是否应当考虑采用稀疏矩阵？）。
Motivation：
基于如下几点，SFE的工作试图通过删除PRA算法的第二步来提高效率和表达能力
二值化特征
对PRA生成的特征矩阵进行二值化处理。去掉PRA的第二步中的带来的绝大多数信息增益对于链接预测任务是没有显著影响的，Random Walk概率相对于二进制特征而言并没有带来额外的信息，这表明PRA的第二步花费了大量的计算但在性能上却没有显著的提高。
增强特征集
文中提到的一些实验表明，在类似PRA的模型中，使用更大的特征集可以显著提升性能。这些实验都使用了二值化特征，虽然没有直接对二值化特征和Random Walk概率进行对比，但可以说明通过增大特征集的大小来使模型达到超过Random Walk概率的效果可能是可行的。同时，他们的实验还表明使用path bigram特征(将每条路径上的每对连续的边类型作为附加特征添加到模型中)可以使性能显著提高，这些特征在传统的PRA表述中是无法体现的。
取消rejection sampling
对于我们上面提到的path bigram，如果我们指定路径最后一条边的类型必须为$r$，rejection sampling的效率会非常低，因为大多数采样最终都会被拒绝（撇开未指定路径长度这一额外问题不谈）。相比之下，如果这些特征仅仅只是表现图中是否有某一类型的路径，而没有任何概率相关的信息，那么这一特征就会比较易于计算。
子图特征提取
这一步仅适用于于图中所有度数大于一的node。对与node n， 使用K个Random Walks构造一个以n为中心的子图，对于子图$G$中每条Random Walk路径，记录其类型为$\pi$，该路径最后一个到达的节点$i$为intermedia node。对于一个子图$G$而言，其所有的类型-intermedia node对$(\pi, i)$可以看做是其一种特征。对于一对source-target节点$(s_j,t_j)$，SFE可以获得两个子图$G_{s_j}, G_{t_j}$，并将这两个子图依据他们的intermedia node $i$进行合并。SFE会取对应于$i$的路径类型$\pi$并组合他们（从target出发的path将会被reverse）。为了构建特征向量，SFE将$(s_j,t_j)$的子图中的所有组合路径类型作为binary feature.
此外，还可以使用BFS来代替Random Walk来进行更加详尽的搜索，因为不带约束的Random Walk会导致不能得到这个node周围的点的完整信息。
在论文中，作者还提到了一些其他类型的feature
PRA-style features.
这一类特征是由子图$G_{s_j}, G_{t_j}$在intermedia node上相交而构成的。换句话说，但两个子图共享同一个intermedia node时，我们将从source节点和target节点到这个intermedia node的路径组合起来。
Path Bigram features
路径类型使用二元组进行表示，例如对于两个子图：
| Subgraph for /m/Barack Obama | |
|---|---|
| $\pi$ | $i$ |
| -ALIAS- | “Barack Obama” |
| -GENDER- | /m/Male |
| -ALIAS-“is married to”- | “Michelle Obama” |
| Subgraph for /m/Michelle Obama | |
|---|---|
| $\pi$ | $i$ |
| -ALIAS- | “Michelle Obama” |
| -GENDER- | /m/Female |
| -ALIAS-“is married to”$^{-1}$- | “Barack Obama” |
One-sided features
不像PRA那样必须从Source走到Target, 可以直接将Source或者Target的子图路径作为特征。例如上面的两个子图中，特征可以是“SOURCE:- GENDER-:male”, “TARGET:-GENDER-:female”, “SOURCE:-ALIAS-:Barack Obama”, and “SOURCE:-ALIAS-is married to-:Michelle Obama”.
One-sided features comparisons
使用在Source和Target节点生成出的子图$G_{s_j}, G_{t_j}$中具备相同特征的边作为特征。例如在上面的两个子图中，这一对节点生成的子图共有的路径类型有-ALIAS-和 -GENDER-，其中，对于-GENDER-类型可以抽出一个feature：“COMPARISON:-GENDER-:/m/Male:/m/Female”。
Vector space similarity features
将edge的类型使用向量来表示（看上去是embedding的亚子）。看原文的描述，是将一些关系，替换为语义相近的关系。例如“spouse of”和“is married to”语义相近，就上面两个子图，我们可以得到“VECSIM:-ALIAS-is married to- ALIAS-”, “VECSIM:-ALIAS-spouse of-ALIAS-”, “VECSIM:-ALIAS-@ANY REL@-ALIAS-”和 “VECSIM:-@ANY REL@-is married to-ALIAS-”等feature.
Any-Relation features
和上面的很像，但是直接认为所有边都是可替换的，将一些边用"ANY_REL"来表示。例如对于 “-ALIAS-is married to- ALIAS-”这样的path而言，可以抽取出“ANYREL:-@ANY REL@- is married to-ALIAS”, “ANYREL:-ALIAS- @ANY REL@-ALIAS”, “ANYREL:-ALIAS-is married to-@ANY REL@”这些feature。
构造负样本
文中提到两种方法，一种是PRA采用的传统方法，即封闭世界假设：原始图谱中不存在的样本（指$(s_j,t_j)$对）都作为负样本。在PRA的第二步时，从一个Source node开始random walk到一个Target node，但这个Target node不是该Source node的已知尾实体，则这一对$(s_j,t_j)$就是一个负样本。
第二种方法是一种基于PPR（Personalized Page Rank）的方法。对于所有已知的正样本，我们获取他们所有的Source node和Target node，并找出其他的和他们在同一类别中PPR相近的节点。然后我们在新找出的类似节点中，按PPR分数进行加权采样（可以同时对Target node和Source node进行采样），在训练和测试时，这些都将成为我们的负样本。
不过作者称这两种方式没有显著的统计学差异