Deep Graph Matching Consensus (2020-01-27T00:00:00.000000Z)

TL;DR

This work presents a two-stage neural architecture for learning and refining structural correspondences between graphs that scales well to large, real-world inputs while still being able to recover global correspondences consistently.

Abstract

This work presents a two-stage neural architecture for learning and refining structural correspondences between graphs. First, we use localized node embeddings computed by a graph neural network to obtain an initial ranking of soft correspondences between nodes. Secondly, we employ synchronous message passing networks to iteratively re-rank the soft correspondences to reach a matching consensus in local neighborhoods between graphs. We show, theoretically and empirically, that our message passing scheme computes a well-founded measure of consensus for corresponding neighborhoods, which is then used to guide the iterative re-ranking process. Our purely local and sparsity-aware architecture scales well to large, real-world inputs while still being able to recover global correspondences consistently. We demonstrate the practical effectiveness of our method on real-world tasks from the fields of computer vision and entity alignment between knowledge graphs, on which we improve upon the current state-of-the-art.

Authors

Matthias Fey

5 papers

Christopher Morris

4 papers

Nils M. Kriege

4 papers

TL;DR

Abstract

Authors

References117 items

KerGM: Kernelized Graph Matching

Deep Graphical Feature Learning for the Feature Matching Problem

Neighborhood-Aware Attentional Representation for Multilingual Knowledge Graphs

Multi-Channel Graph Neural Network for Entity Alignment

Learning edit cost estimation models for graph edit distance

Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching

Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs

Deep Closest Point: Learning Representations for Point Cloud Registration

Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network

Graph Matching Networks for Learning the Similarity of Graph Structured Objects

Learning Combinatorial Embedding Networks for Deep Graph Matching

Relational Pooling for Graph Representations

Graph Neural Networks for User Identity Linkage

Fast Graph Representation Learning with PyTorch Geometric

Deep Adversarial Network Alignment

Computing Optimal Assignments in Linear Time for Approximate Graph Matching

Gromov-Wasserstein Learning for Graph Matching and Node Embedding

A Functional Representation for Graph Matching

An efficient algorithm for graph edit distance computation

Self-supervised Learning of Dense Shape Correspondence

Neighbourhood Consensus Networks

Convolutional Set Matching for Graph Similarity

Random Graphs

Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

How Powerful are Graph Neural Networks?

Learning Representations of Sets through Optimized Permutations

SimGNN: A Neural Network Approach to Fast Graph Similarity Computation

Bootstrapping Entity Alignment with Knowledge Graph Embedding

Representation Learning on Graphs with Jumping Knowledge Networks

Relational inductive biases, deep learning, and graph networks

Deep Learning of Graph Matching

REGAL: Representation Learning-based Graph Alignment

Graph Similarity and Approximate Isomorphism

A Family of Tractable Graph Distances

New binary linear programming formulation to compute the graph edit distance

SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels

Graph Attention Networks

Automatic differentiation in PyTorch

Word Translation Without Parallel Data

Representation Learning on Graphs: Methods and Applications

Cross-Lingual Entity Alignment via Joint Attribute-Preserving Embedding

A Survey on Applications of Bipartite Graph Edit Distance

Graph Embedding Techniques, Applications, and Performance: A Survey

Deep Functional Maps: Structured Prediction for Dense Shape Correspondence

Neural Message Passing for Quantum Chemistry

Unpaired Image-to-Image Translation Using Cycle-Consistent Adversarial Networks

Proposal Flow: Semantic Correspondences from Object Proposals

Modeling Relational Data with Graph Convolutional Networks

Graph edit distance as a quadratic assignment problem

A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching

Geometric Deep Learning: Going beyond Euclidean data

Semi-Supervised Classification with Graph Convolutional Networks

Factorized Graph Matching

FINAL: Fast Attributed Network Alignment

Enriching Word Vectors with Subword Information

node2vec: Scalable Feature Learning for Networks

Gromov-Wasserstein Averaging of Kernel and Distance Matrices

Universal Correspondence Network

A Short Survey of Recent Advances in Graph Matching

CSI_GED: An efficient approach for graph edit similarity computation

Multiple Anonymized Social Networks Alignment

On the Power of Color Refinement

Greedy Graph Edit Distance

Partial Functional Correspondence

Approximation of Graph Edit Distance in Quadratic Time

On convex relaxation of graph isomorphism

Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

Adam: A Method for Stochastic Optimization

Very Deep Convolutional Networks for Large-Scale Image Recognition

Power Iterated Color Refinement

Graph Matching: Relax at Your Own Risk

Learning Graphs to Match

Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

Network Similarity Decomposition (NSD): A Fast and Scalable Approach to Network Alignment

Functional maps

Deep Sparse Rectifier Neural Networks