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.
Neural score matching improves high-dimensional causal inference by using neural networks for balancing scores.
problem Impracticality of traditional matching methods in high-dimensional datasets due to the curse of dimensionality.
method Develops neural networks to create non-trivial, multivariate balancing scores for high-dimensional causal inference.
result Neural score matching outperforms other methods in treatment effect estimation and reducing imbalance on high-dimensional datasets.
Study dynamic matching in heterogeneous networks using ODE model.
problem Dynamic matching in heterogeneous networks with compatibility restrictions.
method Introduced an ODE model to evaluate matching algorithms.
result Demonstrated trade-off between quick matching and optimal matching.
Efficiently learns matching rewards in two-sided markets with matrix completion.
problem Learning high-dimensional matching rewards in matching markets with limited data.
method Utilizes matrix completion with a novel approach to handle matching interference.
result Near-optimal guarantees for reward learning under matching interference.
The strength of association between a pair of data vectors is represented by a nonnegative real number, called matching weight. For dimensionality reduction, we consider a linear transformation of data vectors, and define a matching error as the weighted sum of squared distances between transformed vectors with respect…
Proposes a dynamic matching algorithm for two-sided online markets.
problem Dynamic preferences in two-sided online matching platforms.
method Dynamic Matching Bandit Algorithm with statistical preference ranking estimation.
result Agent-optimal stable matching result with logarithmic regret bound.
A classical problem in causal inference is that of matching, where treatment units need to be matched to control units based on covariate information. In this work, we propose a method that computes high quality almost-exact matches for high-dimensional categorical datasets. This method, called FLAME (Fast Large-scale …
Proposes a non-adversarial method for distribution matching.
problem Stability and optimization challenges in adversarial matching methods.
method Non-adversarial VAE-based matching method with alignment upper bounds.
result Demonstrates applicability of non-adversarial matching methods without modifying original architectures.
The paper addresses statistical inference in matching markets with dependent missingness.
problem Statistical inference for two-sided matching markets with matching-induced dependence.
method Non-convex algorithm based on Grassmannian gradient descent, debiasing and projection framework.
result Near-optimal entrywise convergence rates for various matching mechanisms.
We aim to create the highest possible quality of treatment-control matches for categorical data in the potential outcomes framework. Matching methods are heavily used in the social sciences due to their interpretability, but most matching methods do not pass basic sanity checks: they fail when irrelevant variables are …
Paper tackles distribution matching by partially matching distributions, achieving robust results.
problem Robustly aligning two probability distributions.
method Developed a partial Wasserstein adversarial network (PWAN) to efficiently approximate the partial Wasserstein-1 (PW) discrepancy.
result The PWAN effectively produces highly robust matching results, outperforming state-of-the-art methods.
Partial soft-matching distance improves neural representation comparison by allowing some neurons to remain unmatched.
problem Neural representations are noisy and contain outliers, making traditional matching methods unreliable.
method Extends soft-matching distance to a partial optimal transport setting, allowing some neurons to remain unmatched.
result Partial soft-matching provides robust correspondences that are more reliable under noise and outliers.
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.
Score matching is a recently developed parameter learning method that is particularly effective to complicated high dimensional density models with intractable partition functions. In this paper, we study two issues that have not been completely resolved for score matching. First, we provide a formal link between maxim…
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.
Polynomial time algorithm matches correlated Gaussian matrices without vanishing correlation.
problem Matching vertices in two correlated Erdős-Rényi graphs.
method Iterative matching algorithm for correlated Gaussian Wigner matrices.
result First polynomial time algorithm for graph matching with arbitrarily small constant correlation.
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 …
Efficiently matches subgraphs in noisy data without node labels.
problem Subgraph isomorphism in noisy, real-valued graphs.
method Two-step approach: extract topology, then expand matches.
result Realistically sub-linear computational efficiency, robustness to noise.
The paper analyzes set-to-set matching with neural networks, focusing on theoretical generalization.
problem Theoretical analysis of set-to-set matching with neural networks.
method Generalization error analysis of set-to-set matching with neural networks.
result Theoretical insights into the behavior of set-to-set matching models.
Improved score matching methods for estimating score functions and Hessians without high dimensionality.
problem Estimating score functions and Hessians efficiently in high-dimensional data.
method Implicit score matching and denoising score matching, leveraging Gagliardo-Nirenberg inequalities.
result Achieves convergence rates similar to denoising score matching and estimates Hessians without dimensionality issues.
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.
Submodular functions have many applications. Matchings have many applications. The bitext word alignment problem can be modeled as the problem of maximizing a nonnegative, monotone, submodular function constrained to matchings in a complete bipartite graph where each vertex corresponds to a word in the two input senten…
In this paper, we introduce a novel, non-recursive, maximal matching algorithm for double auctions, which aims to maximize the amount of commodities to be traded. It differs from the usual equilibrium matching, which clears a market at the equilibrium price. We compare the two algorithms through experimental analyses, …
This work improves likelihood of score-based diffusion ODEs using high-order denoising score matching.
problem The gap between maximum likelihood and score matching objectives for score-based diffusion ODEs.
method High-order denoising score matching to maximize likelihood.
result Score-based diffusion ODEs achieve better likelihood on synthetic and CIFAR-10 data.
Given a matched pair of Lie groups, we show that the tangent bundle of the matched pair group is isomorphic to the matched pair of the tangent groups. We thus obtain the Euler-Lagrange equations on the trivialized matched pair of tangent groups, as well as the Euler-Poincaré equations on the matched pair of Lie algebra…
SDE Matching eliminates simulation for training Latent SDEs, achieving similar performance.
problem Training Latent SDEs with adjoint sensitivity methods is computationally expensive and limited.
method SDE Matching, inspired by Score- and Flow Matching, eliminates simulation for training Latent SDEs.
result SDE Matching achieves performance comparable to adjoint sensitivity methods while reducing computational complexity.
Topological Flow Matching: A Generative Modeling Framework for Structured Spaces
problem Handling structured spaces in generative modeling
method Introducing topological flow matching
result Captures the structure of the underlying domain while preserving desirable properties
We propose a unified data-driven framework based on inverse optimal transport that can learn adaptive, nonlinear interaction cost function from noisy and incomplete empirical matching matrix and predict new matching in various matching contexts. We emphasize that the discrete optimal transport plays the role of a varia…
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.
We consider partial matchings, which are finite graphs consisting of edges and vertices of degree zero or one. We consider transformations between two states of partial matchings. We introduce a method of presenting a transformation between partial matchings. We introduce the notion of the lattice presentation of a par…
Algorithm identifies optimal stable matching in uncertain two-sided markets.
problem Sequential learning in two-sided markets with unknown preferences.
method Pure exploration approach with elimination-based algorithms exploiting partial preference information.
result Identification of pervasive stable matching for optimal stable matching identification.
Matched Machine Learning combines machine learning and matching for causal inference.
problem Non-interpretable methods for causal inference.
method Combines machine learning and matching for interpretable causal inference.
result Performs as well as black-box machine learning methods and better than existing matching methods.
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…
Task loss matching misrepresents similarity between neural network layers.
problem Measuring similarity between neural network layers using task loss matching.
method Task loss matching vs. direct matching; comparison with CCA and CKA.
result Direct matching provides a better similarity index than task loss matching.
New method extracts joint and individual signals from multi-view data.
problem Extract joint and individual signals from multi-view data.
method Double-matched matrix decomposition with optimization and iterative algorithm.
result Superior signal estimation performance compared to single-matching methods.
We introduce the notion of matched pairs of Courant algebroids and give several examples arising naturally from complex manifolds, holomorphic Courant algebroids, and certain regular Courant algebroids. We consider the matched sum of two Dirac subbundles, one in each of two Courant algebroids forming a matched pair.
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…
Polynomial-time algorithm matches correlated random graphs with non-vanishing correlation.
problem Matching correlated random graphs with non-vanishing edge correlation.
method Iterative algorithm for polynomial-time recovery of latent matching.
result Algorithm succeeds in recovering latent matching as long as edge correlation is non-vanishing.
KD2M unifies feature matching in neural networks.
problem Matching neural network activations for knowledge transfer.
method Formalizes distribution matching strategy.
result New theoretical results for KD.
GOAT improves graph matching speed and accuracy using optimal transport.
problem Efficiently matching large graphs in various applications.
method Replaces linear assignment with optimal transport methods.
result GOAT provides improvements in speed and accuracy.
Flow matching KL divergence bound derived for smooth distributions.
problem Estimating smooth distributions efficiently.
method Deterministic upper bound on KL divergence derived from flow-matching loss.
result Flow matching achieves nearly minimax-optimal efficiency under TV distance.
Comparing and aligning large datasets is a pervasive problem occurring across many different knowledge domains. We introduce and study MREC, a recursive decomposition algorithm for computing matchings between data sets. The basic idea is to partition the data, match the partitions, and then recursively match the points…
The paper explores a new method for landmark matching using sub-Riemannian geometry and neural networks.
problem Finding a time-dependent vector field to warp points from an initial set to a target set.
method Sub-Riemannian geometry and residual neural networks.
result Demonstrates the importance of regularization in landmark matching.
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.
Study efficient iterative method for distribution matching using sliced optimal transport.
problem Efficiently match distributions using sliced optimal transport.
method Slice-matching scheme based on sliced optimal transport, with quantitative non-asymptotic rates derived.
result Derive quantitative non-asymptotic rates for convergence to target distribution.
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.
This paper develops a learning framework for optimal strategies in multi-stage decentralized matching markets.
problem Optimal strategies in multi-stage decentralized matching markets with uncertain preferences.
method Nonparametric statistical approach and variational analysis.
result Participants can be better off with multi-stage matching compared to single-stage matching.
Score matching is a popular method for estimating unnormalized statistical models. However, it has been so far limited to simple, shallow models or low-dimensional data, due to the difficulty of computing the Hessian of log-density functions. We show this difficulty can be mitigated by projecting the scores onto random…