使用图核进行计算机程序间相似性度量的图编码

Question

我打算使用Graph Kernel来执行不同计算机程序之间的相似性度量。在计算机程序的编译过程中，它们被表示为某种形式的图形，如图中所示的控制流。

​

​

该图摘自论文"Using Graph based program characterization for predictive modeling“

我打算使用Graph内核，为此，我正在寻求帮助，了解如何使用包含特征向量(特定基本块的特征)的每个节点(基本块)对这些图形进行编码(格式化)，以便将它们提供给内核来计算预计算矩阵。

Answer 1

为字符串或图形等非数值对象定义的内核函数主要是为了避免对这种结构的进行编码而引入的。核心思想是直接在非数值空间中的对象上计算核值，就像本例中的图一样。您的特定示例是一个带标签的垂直图的实例(边上没有标签)，因此您可以简单地将图内核用于此类结构。在Graph Kernels paper中，它是作为一个边标记结构引入的，但是从边标记到顶点标记的改变是非常自然的(和already done in other papers)。所以剩下的就是计算特定顶点v_i和v_j之间的相似度。在权威论文中，我们只有一个矩阵W (负责表示特定边缘标签的“相似性”)，所以类似地，你可以计算顶点特征向量之间的某种相似性(有几十种可能性，选择特定的一个严重依赖于数据，你可以尝试余弦相似性，海明距离，均方误差等)，但核心思想保持不变。首先计算要在产品图中使用的顶点-顶点相似度矩阵，然后在数据上简单地应用相应的图内核。这不是简单的解决方案，但我不认为存在简单(好)的解决方案。图形内核是非常年轻的对象( 11年前引入)，用于处理真正复杂的对象(您的特定问题是非常复杂的分类对象的一个很好的例子)。您应该记住，在图形上使用内核方法在计算上可能非常昂贵()，因此使用一些更简单的模型可能是更好的想法(处理图形的一些简单特性，而不是整个“原始”数据)。