Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching
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 perspective, by directly matching two sets of node embeddings without the need to use fixed-dimensional vectors to represent whole graphs for their similarity computation. The model, GraphSim, achieves the state-of-the-art performance on four real-world graph datasets under six out of eight settings (here we count a specific dataset and metric combination as one setting), compared to existing popular methods for approximate Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) computation.
Code (1)
Tasks
ClusteringCombinatorial OptimizationGraph ClassificationGraph ClusteringGraph MatchingGraph Similarityset matchingSimilar Papers 제목 키워드 기반
Convolutional Set Matching for Graph Similarity
We introduce GSimCNN (Graph Similarity Computation via Convolutional Neural Networks) for predicting the similarity score between two graphs. As the core operation of graph similarity search, pairwise graph similarity co…
Graph Similarityset matchingDeep Mesh Prior: Unsupervised Mesh Restoration using Graph Convolutional Networks
This paper addresses mesh restoration problems, i.e., denoising and completion, by learning self-similarity in an unsupervised manner. For this purpose, the proposed method, which we refer to as Deep Mesh Prior, uses a g…
DenoisingCoSimGNN: Towards Large-scale Graph Similarity Computation
The ability to compute similarity scores between graphs based on metrics such as Graph Edit Distance (GED) is important in many real-world applications. Computing exact GED values is typically an NP-hard problem and trad…
3D Action RecognitionAction RecognitionGraph SimilarityGraph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration
Graph similarity is critical in graph-related tasks such as graph retrieval, where metrics like maximum common subgraph (MCS) and graph edit distance (GED) are commonly used. However, exact computations of these metrics …
Graph SimilarityGraph EmbeddingDeep Image Clustering with Contrastive Learning and Multi-scale Graph Convolutional Networks
Deep clustering has shown its promising capability in joint representation learning and clustering via deep neural networks. Despite the significant progress, the existing deep clustering works mostly utilize some distri…
ClusteringContrastive LearningDeep ClusteringImage Clustering+1