Stochastic Iterative Graph Matching
- URL: http://arxiv.org/abs/2106.02206v1
- Date: Fri, 4 Jun 2021 02:05:35 GMT
- Title: Stochastic Iterative Graph Matching
- Authors: Linfeng Liu, Michael C. Hughes, Soha Hassoun, Li-Ping Liu
- Abstract summary: We propose a new model, Iterative Graph MAtching, to address the graph matching problem.
Our model defines a distribution of matchings for a graph pair so the model can explore a wide range of possible matchings.
We conduct extensive experiments across synthetic graph datasets as well as biochemistry and computer vision applications.
- Score: 11.128153575173213
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent works leveraging Graph Neural Networks to approach graph matching
tasks have shown promising results. Recent progress in learning discrete
distributions poses new opportunities for learning graph matching models. In
this work, we propose a new model, Stochastic Iterative Graph MAtching (SIGMA),
to address the graph matching problem. Our model defines a distribution of
matchings for a graph pair so the model can explore a wide range of possible
matchings. We further introduce a novel multi-step matching procedure, which
learns how to refine a graph pair's matching results incrementally. The model
also includes dummy nodes so that the model does not have to find matchings for
nodes without correspondence. We fit this model to data via scalable stochastic
optimization. We conduct extensive experiments across synthetic graph datasets
as well as biochemistry and computer vision applications. Across all tasks, our
results show that SIGMA can produce significantly improved graph matching
results compared to state-of-the-art models. Ablation studies verify that each
of our components (stochastic training, iterative matching, and dummy nodes)
offers noticeable improvement.
Related papers
- Permutation Equivariant Graph Framelets for Heterophilous Graph Learning [6.679929638714752]
We develop a new way to implement multi-scale extraction via constructing Haar-type graph framelets.
We show that our model can achieve the best performance on certain datasets of heterophilous graphs.
arXiv Detail & Related papers (2023-06-07T09:05:56Z) - Similarity-aware Positive Instance Sampling for Graph Contrastive
Pre-training [82.68805025636165]
We propose to select positive graph instances directly from existing graphs in the training set.
Our selection is based on certain domain-specific pair-wise similarity measurements.
Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
arXiv Detail & Related papers (2022-06-23T20:12:51Z) - MetaGL: Evaluation-Free Selection of Graph Learning Models via
Meta-Learning [17.70842402755857]
We develop the first meta-learning approach for evaluation-free graph learning model selection, called MetaGL.
To quantify similarities across a wide variety of graphs, we introduce specialized meta-graph features.
Then we design G-M network, which represents the relations among graphs and models, and develop a graph-based meta-learner.
arXiv Detail & Related papers (2022-06-18T20:43:38Z) - A Graph-Enhanced Click Model for Web Search [67.27218481132185]
We propose a novel graph-enhanced click model (GraphCM) for web search.
We exploit both intra-session and inter-session information for the sparsity and cold-start problems.
arXiv Detail & Related papers (2022-06-17T08:32:43Z) - Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching.
The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k)
It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
arXiv Detail & Related papers (2021-09-01T08:24:02Z) - 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) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology.
Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
arXiv Detail & Related papers (2020-06-19T13:09:44Z) - Permutation Invariant Graph Generation via Score-Based Generative
Modeling [114.12935776726606]
We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling.
In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph.
For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
arXiv Detail & Related papers (2020-03-02T03:06:14Z)
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.