CoSimGNN: Towards Large-scale Graph Similarity Computation
- URL: http://arxiv.org/abs/2005.07115v7
- Date: Wed, 17 Aug 2022 02:20:15 GMT
- Title: CoSimGNN: Towards Large-scale Graph Similarity Computation
- Authors: Haoyan Xu, Runjian Chen, Yueyang Wang, Ziheng Duan, Jie Feng
- Abstract summary: Graph Neural Networks (GNNs) provide a data-driven solution for this task.
Existing GNN-based methods, which either respectively embeds two graphs or deploy cross-graph interactions for whole graph pairs, are still not able to achieve competitive results.
We propose the "embedding-coarsening-matching" framework CoSimGNN, which first embeds and coarsens large graphs with adaptive pooling operation and then deploys fine-grained interactions on the coarsened graphs for final similarity scores.
- Score: 5.17905821006887
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 traditional
algorithms usually achieve an unsatisfactory trade-off between accuracy and
efficiency. Recently, Graph Neural Networks (GNNs) provide a data-driven
solution for this task, which is more efficient while maintaining prediction
accuracy in small graph (around 10 nodes per graph) similarity computation.
Existing GNN-based methods, which either respectively embeds two graphs (lack
of low-level cross-graph interactions) or deploy cross-graph interactions for
whole graph pairs (redundant and time-consuming), are still not able to achieve
competitive results when the number of nodes in graphs increases. In this
paper, we focus on similarity computation for large-scale graphs and propose
the "embedding-coarsening-matching" framework CoSimGNN, which first embeds and
coarsens large graphs with adaptive pooling operation and then deploys
fine-grained interactions on the coarsened graphs for final similarity scores.
Furthermore, we create several synthetic datasets which provide new benchmarks
for graph similarity computation. Detailed experiments on both synthetic and
real-world datasets have been conducted and CoSimGNN achieves the best
performance while the inference time is at most 1/3 of that of previous
state-of-the-art.
Related papers
- Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs)
This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings.
Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
arXiv Detail & Related papers (2024-05-27T17:52:12Z) - Graph Coarsening via Convolution Matching for Scalable Graph Neural
Network Training [22.411609128594982]
We propose the Coarsening Via Convolution Matching (CONVMATCH) algorithm and a highly scalable variant, A-CONVMATCH, for creating summarized graphs.
We evaluate CONVMATCH on six real-world link prediction and node classification graph datasets.
arXiv Detail & Related papers (2023-12-24T16:07:14Z) - Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs.
Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors.
We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
arXiv Detail & Related papers (2023-10-23T01:25:44Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining.
Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
arXiv Detail & Related papers (2023-10-05T02:58:29Z) - Co-attention Graph Pooling for Efficient Pairwise Graph Interaction
Learning [19.58671020943416]
Graph Neural Networks (GNNs) have proven to be effective in processing and learning from graph-structured data.
We propose a novel and efficient graph-level approach for extracting interaction representations using co-attention in graph pooling.
Our method, Co-Attention Graph Pooling (CAGPool), exhibits competitive performance relative to existing methods in both classification and regression tasks.
arXiv Detail & Related papers (2023-07-28T07:53:34Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data.
We present a novel Graph Matching based GNN Pre-Training framework, called GMPT.
The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
arXiv Detail & Related papers (2022-03-03T09:53:53Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data.
Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks.
In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities.
arXiv Detail & Related papers (2020-11-19T06:03:35Z) - Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects.
To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks.
Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
arXiv Detail & Related papers (2020-07-08T19:48:19Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs.
In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings.
We show that training PPRGo and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph.
arXiv Detail & Related papers (2020-07-03T09:30:07Z) - Graph Partitioning and Graph Neural Network based Hierarchical Graph
Matching for Graph Similarity Computation [5.710312846460821]
Graph similarity aims to predict a similarity score between one pair of graphs to facilitate downstream applications.
We propose a graph partitioning and graph neural network-based model, called PSimGNN, to effectively resolve this issue.
PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks using approximate Graph Edit Distance (GED) as the graph similarity metric.
arXiv Detail & Related papers (2020-05-16T15:01:58Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.