graph - 图形编码以使用图形内核进行计算机程序之间的相似性度量

Question

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

图摘自论文《Using Graph based program characterization for predicting modeling》

我打算使用 Graph 内核，为此我正在寻求帮助，了解如何使用包含特征向量（该特定基本块的特征）的每个节点（基本块）对这些图进行编码（格式），以便它们可以被馈送到内核来计算预先计算的矩阵。

Answer 1

为非数字对象（如字符串或图形）定义的内核函数主要是为了避免对这种结构进行编码。核心思想是直接在非数字空间的对象上计算内核值，就像在这个例子中一样 - 图形。您的特定示例是标记垂直图的实例（边缘没有标签），因此您可以简单地将图形内核用于此类结构。在Graph Kernels 论文中，它被介绍为边缘标记结构，但是从边缘标记到顶点标记的变化是非常自然的（并且已经在其他论文中完成）。所以剩下的就是计算特定顶点v_i和之间的相似性v_j。在原始论文中，我们只是有一个矩阵W（负责表达特定边缘标签的“相似性”）因此类似地，您可以计算顶点特征向量之间的某种相似性（有几十种可能性，并且特定的选择很大程度上取决于数据，您可以尝试余弦相似度，汉明距离，MSE等），但核心思想保持不变。您首先计算要在产品图中使用的顶点-顶点相似度矩阵，然后简单地将相应的图内核应用于您的数据。这不是简单的解决方案，但我认为不存在简单（好）的解决方案。图内核是非常年轻的对象（11 年前引入），可以处理非常复杂的对象（您的特定问题是非常复杂的分类对象的一个​​很好的例子）。你应该记住，在图形上使用内核方法的计算成本很高，因此使用一些更简单的模型（处理图形的一些简单特征而不是整个“原始”数据）可能是更好的主意。