Combinatorial Learning of Graph Edit Distance via Dynamic Embedding
This work provides a more efficient and adaptive method for computing Graph Edit Distance and recovering edit paths, which is valuable for researchers and practitioners working with graph similarity measurements.
This paper addresses the scalability issues of Graph Edit Distance (GED) computation, particularly the A* algorithm, by introducing a hybrid approach that combines search-based techniques with deep embedding models. The method dynamically reuses node-level embeddings and prunes suboptimal branches, significantly reducing the computational burden of A* while maintaining accuracy.
Graph Edit Distance (GED) is a popular similarity measurement for pairwise graphs and it also refers to the recovery of the edit path from the source graph to the target graph. Traditional A* algorithm suffers scalability issues due to its exhaustive nature, whose search heuristics heavily rely on human prior knowledge. This paper presents a hybrid approach by combing the interpretability of traditional search-based techniques for producing the edit path, as well as the efficiency and adaptivity of deep embedding models to achieve a cost-effective GED solver. Inspired by dynamic programming, node-level embedding is designated in a dynamic reuse fashion and suboptimal branches are encouraged to be pruned. To this end, our method can be readily integrated into A* procedure in a dynamic fashion, as well as significantly reduce the computational burden with a learned heuristic. Experimental results on different graph datasets show that our approach can remarkably ease the search process of A* without sacrificing much accuracy. To our best knowledge, this work is also the first deep learning-based GED method for recovering the edit path.