基于邻居向量的近似子图匹配

Approximate subgraph matching based on neighborhood vector

将近似子图匹配分成节点匹配和边匹配两个阶段。将数据图中所有节点的h-邻居节点表示成向量形式,采用一种启发式推理算法进行节点匹配得到节点对应关系,使用查询节点权重提高匹配相似度,使用节点过滤、索引技术和孤立候选节点提高运算效率;利用邻居向量索引得到匹配节点集合的扩展图,进行边匹配,得到匹配图。在真实数据上进行实验,实验结果表明,该算法效果较好,运算效率较高,可以应用于节点标签稀疏的情况和top-k近似匹配。

This approximate subgraph matching algorithm is composed of two stages： nodes matching and edges matching. First, the h-neighborhoods of each node in the data graph were represented with a neighborhood vector, and corresponding relations be- tween nodes were obtained by using a heuristic algorithm. Besides, weights of query nodes were used to improve the matching accuracy, and the nodes filtering, the index technique, and isolated candidates were used to improve the computing speed. Second, the index of neighborhood vector was applied to get the extended graph of matching nodes, and the matching subgraph was obtained after edges matching. The experiment results on real datasets show that the algorithm is effective and efficient in the context of data graph of sparse node label classes, and can be applied to top-k approximate matching.