A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Paper tackles graph matching with partially correct seeds, improving performance guarantees.
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 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 …
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…
PPM improves graph matching for correlated Gaussian Wigner models with high probability.
OmniMatch algorithm perfectly matches graphs without edge correlation.
Improved graph matching using covariates for network data integration.
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,…
We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated Erdős-Rényi random graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. For seeded problems, our result pr…
Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdős-Rényi graphs. However, very little is known about the existence of e…
Study finds many Lagrangian fillings for certain Legendrian links.
We propose a consistent polynomial-time method for the unseeded node matching problem for networks with smooth underlying structures. Despite widely conjectured by the research community that the structured graph matching problem to be significantly easier than its worst case counterpart, well-known to be NP-hard, the …
The paper shows how shared random seeds can reduce variance in machine learning evaluations.
Discrete knot theory models use lattice-filtered graphs to detect merging knot components.
New Karger-like algorithms solve graph cuts, useful for image segmentation.
TOO optimizes stochastic epidemiological models by finding both parameter settings and random seeds.
Proposes a new optimization method for local graph clustering.
The paper provides statistical theory and intuition for personalized PageRank (called "PPR"): a popular technique that samples a small community from a massive network. We study a setting where the entire network is expensive to obtain thoroughly or to maintain, but we can start from a seed node of interest and "crawl"…
Image partitioning, or segmentation without semantics, is the task of decomposing an image into distinct segments, or equivalently to detect closed contours. Most prior work either requires seeds, one per segment; or a threshold; or formulates the task as multicut / correlation clustering, an NP-hard problem. Here, we …
Local graph clustering methods aim to find small clusters in very large graphs. These methods take as input a graph and a seed node, and they return as output a good cluster in a running time that depends on the size of the output cluster but that is independent of the size of the input graph. In this paper, we adopt a…
In this work we propose a simple and easily parallelizable algorithm for multiway graph partitioning. The algorithm alternates between three basic components: diffusing seed vertices over the graph, thresholding the diffused seeds, and then randomly reseeding the thresholded clusters. We demonstrate experimentally that…
The paper defines and studies discrete p-density and compression-radius profiles of lattice knots.
Graph data widely exist in many high-impact applications. Inspired by the success of deep learning in grid-structured data, graph neural network models have been proposed to learn powerful node-level or graph-level representation. However, most of the existing graph neural networks suffer from the following limitations…
The study finds many Lagrangian fillings for Legendrian links of specific types.
New method speeds up k-means clustering for large k by improving nearest-neighbor search.
SIGMA model improves graph matching across various applications.
IIC decouples causal identification into two phases, significantly reducing the HTC gap in linear SEMs.
We establish the following theorem of Bernstein type for the first Heisenberg group: Let S be a C^2 connected H-minimal surface which is a graph over some plane P, then S is either a non-characteristic vertical plane, or its generalized seed curve satisfies a type of constant curvature condition.
Method finds multiple noisy graph templates in large graphs.
Paper proposes a new method for population-wise matching of sulcal graphs.
Local network community detection is the task of finding a single community of nodes concentrated around few given seed nodes in a localized way. Conductance is a popular objective function used in many algorithms for local community detection. This paper studies a continuous relaxation of conductance. We show that con…
Network Lasso clusters sparse graph clusters efficiently.
NeuroMatch efficiently matches subgraphs in large graphs using neural networks.
Proposes methods to recover labels from shuffled networks using graph averages.
New method stabilizes machine learning predictions across random seeds.
Study sharpens threshold for matching correlated graphs without labels.
Fairness audits fail under missing protected labels, especially at zero access.
GOAT improves graph matching speed and accuracy using optimal transport.
Improved graph matching algorithm robust to noise.
Efficient algorithm for matching graphs with community structure.
Graphs provide an efficient tool for object representation in various computer vision applications. Once graph-based representations are constructed, an important question is how to compare graphs. This problem is often formulated as a graph matching problem where one seeks a mapping between vertices of two graphs whic…
New method fills cluster seeds with exact Lagrangian structures.
Many methods for automated software test generation, including some that explicitly use machine learning (and some that use ML more broadly conceived) derive new tests from existing tests (often referred to as seeds). Often, the seed tests from which new tests are derived are manually constructed, or at least simpler t…
End-to-end trainable graph matching using improved combinatorial solvers.
Efficiently matches random graphs with inhomogeneous edge probabilities.
We propose a new approach to graph compression by appeal to optimal transport. The transport problem is seeded with prior information about node importance, attributes, and edges in the graph. The transport formulation can be setup for either directed or undirected graphs, and its dual characterization is cast in terms…
Graph matching involves combinatorial optimization based on edge-to-edge affinity matrix, which can be generally formulated as Lawler's Quadratic Assignment Problem (QAP). This paper presents a QAP network directly learning with the affinity matrix (equivalently the association graph) whereby the matching problem is tr…
We recently proposed a new ensemble clustering algorithm for graphs (ECG) based on the concept of consensus clustering. We validated our approach by replicating a study comparing graph clustering algorithms over benchmark graphs, showing that ECG outperforms the leading algorithms. In this paper, we extend our comparis…