Learning-based Efficient Graph Similarity Computation Via Multi-scale Convolutional Set Matching

Abstract

Graph similarity computation is one of the core operations in many graph-based applications, such as graph similarity search, graph database analysis, graph clustering, etc. Since computing the exact distance/similarity between two graphs is typically NP-hard, a series of approximate methods have been proposed with a trade-off between accuracy and speed. Recently, several data-driven approaches based on neural networks have been proposed, most of which model the graph-graph similarity as the inner product of their graph-level representations, with different techniques proposed for generating one embedding per graph. However, using one fixed-dimensional embedding per graph may fail to fully capture graphs in varying sizes and link structures, a limitation that is especially problematic for the task of graph similarity computation, where the goal is to find the fine-grained difference between two graphs. In this paper, we address the problem of graph similarity computation from another p

Stats

• citations64
• S2 citations—
• github stars0
• HF likes0
• heat score13.60
• arxiv keybai2018learning

Related papers

• Hierarchical Graph Matching Network For Graph Similarity Computation (2020)0.00
• Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
• All Graphs Lead To Rome: Learning Geometric And Cycle-consistent Representations With Graph Convolutional Networks (2019)0.00
• Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration (2025)0.00
• Deep Graph Similarity Learning: A Survey (2019)13.97
• SEGMN: A Structure-enhanced Graph Matching Network For Graph Similarity Learning (2024)2.26
• Multi-scale Convolutions For Learning Context Aware Feature Representations (2019)0.00
• Learning Graph Edit Distance By Graph Neural Networks (2020)10.85