Proposes methods to recover labels from shuffled networks using graph averages.
problem Recovering labels from a shuffled network using graph averages.
method Cluster networks into classes, then match the new graph to cluster-averages, minimizing the graph matching objective function.
result Higher fidelity matching performance when clustering networks into different classes.
NeuroMatch efficiently matches subgraphs in large graphs using neural networks.
problem Determining the presence and location of a query graph in a large target graph.
method NeuroMatch decomposes graphs into subgraphs, embeds them using graph neural networks, and matches them directly in the embedding space.
result NeuroMatch is 100x faster and 18% more accurate than existing methods.
New method for matching bipartite and unipartite graphs without collapsing.
problem Matching between bipartite and unipartite networks without losing information.
method Formulated as an undirected graphical model, aligns graphs without collapsing.
result Consistent method with conditions for exact recovery of matching solution.
Network learns graph matching directly from edge affinity matrices.
problem Graph matching optimization based on edge-to-edge affinity matrices.
method Embedding network for vertex classification, Sinkhorn normalization, cross-entropy loss, matching-aware constraints, dummy nodes.
result Competitive performance on synthetic and real-world graphs, faster than state-of-the-art.
Graph Matching Networks learn graph similarity using GNN embeddings.
problem Learning similarity between graph structured objects.
method Graph Matching Network model using cross-graph attention mechanism.
result Models outperform baseline systems in function similarity search.
SIGMA model improves graph matching across various applications.
problem Graph matching problem in different domains.
method Stochastic Iterative Graph Matching (SIGMA) model with multi-step refinement and dummy nodes.
result SIGMA produces significantly improved graph matching results compared to state-of-the-art models.
Graph matching with feature vectors is solved using a two-layer graph neural network.
problem Graph matching in the presence of sparse binary features.
method Two-layer graph neural network with graph structure.
result Graph neural network can recover correct mapping with high probability under certain conditions.
Improved graph matching algorithm robust to noise.
problem Finding a bijection between vertex sets of two graphs.
method Uses multistage signature vectors to match vertices.
result Recover matching exactly with high probability for α≤1/(loglogn)C. Improved graph matching using covariates for network data integration.
problem Matching networks without unique identifiers.
method Two novel covariate-assisted seeded graph matching methods.
result Improved alignment accuracy through covariate information.
Given a pair of graphs with the same number of vertices, the inexact graph matching problem consists in finding a correspondence between the vertices of these graphs that minimizes the total number of induced edge disagreements. We study this problem from a statistical framework in which one of the graphs is an errorfu…
Proposes MGMN for end-to-end graph similarity learning.
problem Lack of cross-level interactions in graph similarity learning.
method Multi-level graph matching network (MGMN) combining node-graph matching and siamese graph neural networks.
result MGMN outperforms state-of-the-art models on graph-graph classification and regression tasks.
The problem of finding the vertex correspondence between two noisy graphs with different number of vertices where the smaller graph is still large has many applications in social networks, neuroscience, and computer vision. We propose a solution to this problem via a graph matching matched filter: centering and padding…
Consider two networks on overlapping, non-identical vertex sets. Given vertices of interest in the first network, we seek to identify the corresponding vertices, if any exist, in the second network. While in moderately sized networks graph matching methods can be applied directly to recover the missing correspondences,…
A neural architecture learns and refines graph correspondences.
problem Learning structural correspondences between graphs.
method Two-stage neural architecture: node embeddings followed by message passing networks.
result Message passing scheme computes well-founded consensus for corresponding neighborhoods.
Neural execution solves complex graph problems like bipartite matching.
problem Solving complex graph algorithms like maximum bipartite matching.
method Reduces bipartite matching to a flow problem and uses Ford-Fulkerson for maximum flow.
result Neural network achieves optimal matching almost 100% of the time.
Framework generates causal probabilities from observational data.
problem Generating causal probabilities from observational data.
method Moment-matching graph-networks for causal inference.
result Automated sampling of latent space conditional probability distributions.
Graph matching in noisy environments with Markovian errors.
problem Graph matching under time-dependent Markovian noise.
method Introduced edgelighter error model and analyzed graph matching thresholds.
result Graph matching thresholds and mixing times are of order Θ(n2logn) for Erdős-Rényi graphs, and O(nαlogn) for Stochastic Block Model graphs. We study graph matching with correlated Gaussian features and find thresholds for exact recovery.
problem Graph matching with correlated Gaussian features.
method Information-theoretic thresholds and conditions for exact and almost exact recovery.
result Contextual information introduces a richer structure, with thresholds for exact and almost exact recovery no longer coinciding.
New MPNNs match 2-WL, faster distinguishing graphs.
problem Improving graph neural network expressiveness.
method Introducing ℓ-walk MPNNs and second-order GNNs. result Walk MPNNs match 2-WL and can distinguish graphs faster.
We propose an extension of Convolutional Neural Networks (CNNs) to graph-structured data, including strided convolutions and data augmentation on graphs. Our method matches the accuracy of state-of-the-art CNNs when applied on images, without any prior about their 2D regular structure. On fMRI data, we obtain a signifi…
Efficient algorithm for matching graphs with community structure.
problem Graph matching between correlated stochastic block models with constant correlation.
method Partition trees rooted from each vertex, comparing edge statistics to different communities.
result First low-order polynomial-time algorithm achieving exact matching with high probability in dense graphs.
UM-GNN improves GNN robustness against poisoning attacks.
problem Vulnerability of GNNs to poisoning attacks.
method UM-GNN uses epistemic uncertainties from message passing to build a surrogate predictor.
result UM-GNN achieves significantly improved robustness against poisoning attacks.
Graphs model human mobility patterns, reducing errors in data matching.
problem Lack of high-quality data and computational resources for graph-based mobility analysis.
method Embedding graphs into a continuous space to address matching, modeling, and visualization challenges.
result Approx 40% decrease in error on average in matched graphs vs unmatched ones.
MatchGNet detects malware by learning program behavior graphs.
problem Malware evasion through obfuscation and high false positives in traditional detection methods.
method Heterogeneous Graph Matching Network model that learns graph representation and similarity metrics.
result MatchGNet reduces false positives by 50% while maintaining zero false negatives.
Enhances community detection in correlated networks with node attributes.
problem Community detection in multiple networks with correlated node attributes and edges.
method Introduced the correlated Contextual Stochastic Block Model (CSBM), developed a two-step matching procedure.
result Algorithm recovers exact node correspondence, enabling enhanced community detection.
Two approaches use TDA and graph theory for tennis match prediction.
problem Predicting tennis match outcomes using network features.
method Lower-star filtration on player competitive networks, Random Forest model, modified Katz similarity index.
result TDA features alone can achieve above-chance prediction in tennis match outcomes.
We introduce a new cohomology theory for planar trivalent graphs with perfect matchings. The graded Euler characteristic of the cohomology is a one variable polynomial called the 2-factor polynomial that, if nonzero when evaluated at one, implies that the perfect matching is even and therefore the graph is 4-face color…
Graph matching is a challenging problem with very important applications in a wide range of fields, from image and video analysis to biological and biomedical problems. We propose a robust graph matching algorithm inspired in sparsity-related techniques. We cast the problem, resembling group or collaborative sparsity f…
Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasible, iterative moment matched approximations to the spectra and kernel smoothing are typically used. …
OmniMatch algorithm perfectly matches graphs without edge correlation.
problem Graph matching in the absence of edge correlation.
method OmniMatch algorithm for seeded multiple graph matching.
result OmniMatch aligns O(sα) unseeded vertices across multiple networks efficiently and perfectly. Adding random features to GNNs improves their performance.
problem Limitations of GNNs in distinguishing graphs and learning efficient algorithms.
method Adding random features to each node in GNNs.
result Random features enable GNNs to learn optimal algorithms for graph problems.
Improved graph generation model for small organic molecules.
problem Graph generation models struggle with matching training distributions and require expensive graph matching.
method Introduced a message passing neural network into the GVAE's encoder and decoder.
result Demonstrated improved graph generation for small organic molecules.
Paper solves graph matching for correlated Erdős--Rényi graphs.
problem Matching vertices of correlated Erdős--Rényi graphs.
method Polynomial-time algorithm based on comparison of partition trees.
result Exact matching achieved with high probability.
A novel Gromov-Wasserstein learning framework is proposed to jointly match (align) graphs and learn embedding vectors for the associated graph nodes. Using Gromov-Wasserstein discrepancy, we measure the dissimilarity between two graphs and find their correspondence, according to the learned optimal transport. The node …
A new graph generator uses heat diffusion on graph Laplacians to create new graph structures.
problem Creating realistic and diverse graph structures for various applications.
method Adapting the Generator Matching paradigm to graph data, using graph Laplacian and heat kernel for diffusion.
result The method effectively generates graphs with structural properties of real and synthetic graphs.
Method finds multiple noisy graph templates in large graphs.
problem Finding multiple graph templates in noisy large graphs.
method Iteratively penalizes node-pair similarity matrix in matched filter algorithm.
result Method can sequentially discover multiple templates under mild model conditions.
Paper proposes a new method for population-wise matching of sulcal graphs.
problem Challenges in matching cortical fold variations across individuals.
method Population-wise multi-graph matching of sulcal graphs.
result Effectiveness of multi-graph matching in obtaining consistent labeling of sulcal basins.
GraphMoE generates random graphs using neural networks and graphlets.
problem Learning generative models for random graphs.
method GraphMoE uses a neural network trained with graphlets and subgraph counts to match the distribution of random graphs.
result GraphMoE can generate graphs that mimic various real-world datasets and fool graph classifiers.
A test for comparing networks using stochastic block models.
problem Determining if two network datasets come from the same model.
method Adopting stochastic block models, the study introduces an efficient algorithm to match estimated network parameters and develops a powerful test.
result The test is consistent and asymptotically follows a chi-squared distribution.
Riemannian metric matching learns the geometry of high-dimensional datasets using neural networks.
problem Estimating the geometry of high-dimensional datasets from samples
method Riemannian metric matching using neural networks
result Riemannian metric matching rivals or improves k-NN-based diffusion geometry estimators GNNRank uses neural networks to learn global rankings from competition match data.
problem Learning global rankings from pairwise comparisons in directed graphs.
method Proposes GNNRank, a trainable GNN-based framework with digraph embedding and new objectives.
result GNNRank achieves competitive and superior performance compared to baselines.
Given two graphs, the graph matching problem is to align the two vertex sets so as to minimize the number of adjacency disagreements between the two graphs. The seeded graph matching problem is the graph matching problem when we are first given a partial alignment that we are tasked with completing. In this paper, we m…
We present a parallelized bijective graph matching algorithm that leverages seeds and is designed to match very large graphs. Our algorithm combines spectral graph embedding with existing state-of-the-art seeded graph matching procedures. We justify our approach by proving that modestly correlated, large stochastic blo…
We present a novel approximate graph matching algorithm that incorporates seeded data into the graph matching paradigm. Our Joint Optimization of Fidelity and Commensurability (JOFC) algorithm embeds two graphs into a common Euclidean space where the matching inference task can be performed. Through real and simulated …
LGGAN generates labeled graphs from graph data.
problem Training generative models for graph-structured data with labels.
method LGGAN, a GAN approach, trains deep models for graph data with node labels.
result LGGAN generates diverse labeled graphs that match training data and outperforms alternatives.
Study sharpens threshold for matching correlated graphs without labels.
problem Matching latent vertex correspondences in correlated random graphs.
method Analyzes information-theoretic limits for correct vertex matching in sub-sampled graphs.
result Establishes a sharp information-theoretic threshold for vertex matching recovery.
Paper tackles shape graph registration using neural networks.
problem Constrained registration of shape graphs with varying nodes and edges.
method Shape-Graph Matching Network (SGM-net) with an elastic shape metric loss function.
result State-of-the-art matching performance and reduced computational cost.
GraphDETR detects subgraphs in large graphs using deep learning.
problem Detecting subgraphs in large graphs efficiently and accurately.
method Formulates subgraph detection as a set prediction problem using GraphDETR, a deep learning framework.
result GraphDETR can detect diverse patterns in large graphs, achieving strong performance on molecular functional group detection.