We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are similar in the supremum norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and universal, meaning that it pr…
On-device research index
arXiv research
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Graph Edit Distance”
Edit distance, also known as Levenshtein distance, is an essential way to compare two strings that proved to be particularly useful in the analysis of genetic sequences and natural language processing. However, edit distance is a discrete function that is known to be hard to optimize. This fact hampers the use of this …
We introduce GSimCNN (Graph Similarity Computation via Convolutional Neural Networks) for predicting the similarity score between two graphs. As the core operation of graph similarity search, pairwise graph similarity computation is a challenging problem due to the NP-hard nature of computing many graph distance/simila…
funcGNN uses graph neural networks to estimate program similarity efficiently.
problem Estimating accurate program similarity for software engineering tasks.
method funcGNN trains on labeled CFG pairs to predict GED between unseen programs using effective embedding vectors.
result funcGNN achieves lower error rate (0.00194) and is 23 times faster than traditional methods.
New metric learning approach for tree data reduces computation cost.
problem Efficiently computing distances between ordered labeled trees.
method Introduced pq-grams and a differentiable weighted pq-gram distance, combined with LMNN for optimization.
result Significantly reduces computation time for tree classification problems.
RS-Del provides robustness for sequence classifiers against edit distance attacks.
problem Certifying robustness of discrete sequence classifiers against edit distance attacks.
method Randomized deletion (RS-Del) for discrete sequence classifiers, focusing on edit distance-bounded adversaries.
result Achieved a certified accuracy of 91% at an edit distance radius of 128 bytes on malware detection.
Neural network for subgraph similarity computation with pruning.
problem Computing subgraph similarity between a target and query graph.
method Convert pruning to node relabeling, relax to differentiable problem, design neural network for SED computation.
result Establishes new state-of-the-art results across multiple benchmark datasets.
CoSimGNN improves graph similarity computation for large graphs.
problem Efficiently computing graph similarity scores for large graphs.
method Embedding-coarsening-matching framework with adaptive pooling and fine-grained interactions.
result CoSimGNN achieves best performance in graph similarity computation.
Metric learning has the aim to improve classification accuracy by learning a distance measure which brings data points from the same class closer together and pushes data points from different classes further apart. Recent research has demonstrated that metric learning approaches can also be applied to trees, such as m…
PSimGNN partitions graphs into subgraphs for efficient graph similarity computation.
problem Efficiently compute graph similarity scores for large graphs.
method Graph partitioning followed by subgraph-level and node-level comparisons using a graph neural network.
result PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks.
MEGAN models chemical reactions as graph edits, improving synthesis planning.
problem Generating and predicting chemical reactions under constraints.
method End-to-end encoder-decoder neural model inspired by arrow pushing formalism.
result State-of-the-art accuracy in standard benchmarks for retrosynthesis prediction.
Tree Edit Distance Learning via Adaptive Symbol Embeddings: Supplementary Materials and Resultscs.LG
Metric learning has the aim to improve classification accuracy by learning a distance measure which brings data points from the same class closer together and pushes data points from different classes further apart. Recent research has demonstrated that metric learning approaches can also be applied to trees, such as m…
Causal KL improves on existing metrics for evaluating causal models.
problem Insufficient discrimination between causal models using edit-distance and KL divergence.
method Introducing Causal KL, an augmented KL divergence that considers causal relationships.
result Causal KL variants effectively distinguish between observationally equivalent models.
Finding an optimal assignment between two sets of objects is a fundamental problem arising in many applications, including the matching of `bag-of-words' representations in natural language processing and computer vision. Solving the assignment problem typically requires cubic time and its pairwise computation is expen…
We compute an approximate Fréchet mean for sets of sparse graphs.
problem Characterizing the location of a set of graphs in a metric space.
method We use the pseudometric defined by the ℓ₂ norm of eigenvalues of adjacency matrices.
result We describe an algorithm to approximate the Fréchet mean of a set of graphs.
Differentially private data structures for estimating distances between strings.
problem Estimating distances between query strings and database strings while ensuring privacy.
method Proposes differentially private data structures for Hamming and edit distances using randomized response technique.
result Efficient data structures that provide accurate distance estimates with strong privacy guarantees.
The paper computes an approximation to the sample Frechet mean of graph sets using spectral information.
problem Characterizing the location of a set of graphs in a metric space.
method The Frechet mean is computed for sets of large graphs using the pseudometric defined by the norm between eigenvalues of adjacency matrices.
result An algorithm to approximate the sample Frechet mean of undirected unweighted graphs is described.
Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matchingcs.LG
Graph similarity computation is one of the core operations in many graph-based applications, such as graph similarity search, graph database analysis, graph clustering, etc. Since computing the exact distance/similarity between two graphs is typically NP-hard, a series of approximate methods have been proposed with a t…
Many machine learning models can be attacked with adversarial examples, i.e. inputs close to correctly classified examples that are classified incorrectly. However, most research on adversarial attacks to date is limited to vectorial data, in particular image data. In this contribution, we extend the field by introduci…
We present Optimal Completion Distillation (OCD), a training procedure for optimizing sequence to sequence models based on edit distance. OCD is efficient, has no hyper-parameters of its own, and does not require pretraining or joint optimization with conditional log-likelihood. Given a partial sequence generated by th…
We introduce agents that use object-oriented reasoning to consider alternate states of the world in order to more quickly find solutions to problems. Specifically, a hierarchical controller directs a low-level agent to behave as if objects in the scene were added, deleted, or modified. The actions taken by the controll…
New method for finding function correspondences in binary programs.
problem Finding a correspondence between functions of two binary programs.
method Formulated as a network alignment problem and solved using belief propagation.
result QBinDiff prototype outperforms state-of-the-art diffing tools.
Biological and cellular systems are often modeled as graphs in which vertices represent objects of interest (genes, proteins, drugs) and edges represent relational ties among these objects (binds-to, interacts-with, regulates). This approach has been highly successful owing to the theory, methodology and software that …
We introduce the problem of learning distributed representations of edits. By combining a "neural editor" with an "edit encoder", our models learn to represent the salient information of an edit and can be used to apply edits to new inputs. We experiment on natural language and source code edit data. Our evaluation yie…
ED-NeRF efficiently edits 3D scenes using latent space NeRF and improved loss functions.
problem Slow training speeds and inadequate editing loss functions in existing NeRF editing techniques.
method Embedding real-world scenes into latent space of LDM, using a unique refinement layer and an improved loss function.
result ED-NeRF achieves faster editing speed and improved output quality compared to state-of-the-art models.
The crucial importance of metrics in machine learning algorithms has led to an increasing interest in optimizing distance and similarity functions, an area of research known as metric learning. When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance. Less work has been …
Edit wars in Wikipediastat.ML
We present a new, efficient method for automatically detecting severe conflicts `edit wars' in Wikipedia and evaluate this method on six different language WPs. We discuss how the number of edits, reverts, the length of discussions, the burstiness of edits and reverts deviate in such pages from those following the gene…
As the number of contributors to online peer-production systems grows, it becomes increasingly important to predict whether the edits that users make will eventually be beneficial to the project. Existing solutions either rely on a user reputation system or consist of a highly specialized predictor that is tailored to …
Graph similarity search is among the most important graph-based applications, e.g. finding the chemical compounds that are most similar to a query compound. Graph similarity computation, such as Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), is the core operation of graph similarity search and many other …
Ground-A-Video edits videos without training, preserving intended changes.
problem Complex multi-attribute video editing with omitted or wrong changes.
method Grounding-guided video-to-video translation with Cross-Frame Gated Attention.
result Zero-shot multi-attribute video editing with improved accuracy and frame consistency.
Principled Fine-tuning of LLMs from User-Edits: A Medley of Preference, Supervision, and Rewardcs.LG
Paper fine-tunes LLMs using user edits, unifying preference, supervision, and reward feedback.
problem Adapting LLMs to user preferences and feedback types.
method Derives bounds for learning algorithms from user edits, proposes an ensembling procedure.
result Ensembling procedure outperforms individual feedback methods and robustly adapts to different user-edit distributions.
Programming languages are emerging as a challenging and interesting domain for machine learning. A core task, which has received significant attention in recent years, is building generative models of source code. However, to our knowledge, previous generative models have always been framed in terms of generating stati…
We propose a new generative model of sentences that first samples a prototype sentence from the training corpus and then edits it into a new sentence. Compared to traditional models that generate from scratch either left-to-right or by first sampling a latent sentence vector, our prototype-then-edit model improves perp…
Improves generative models by optimizing rewards and sample editing.
problem Efficiently generating high-reward samples with structural constraints.
method Introduces MDM-VGB, a discrete diffusion sampler that augments unmasking generation with reward-guided remasking.
result MDM-VGB achieves quadratic complexity and robustness to noise, outperforming heuristics like best-of-.
We define a pseudo-inverse for line graphs using linear integer programming.
problem Not all graphs have a corresponding root graph, making the line graph operation non-invertible.
method Propose a linear integer program to edit the smallest number of edges in the line graph to recover a root graph.
result The pseudo-inverse operation is well-behaved and works in practice as shown by empirical experiments.
New method uses coupled SDEs to edit images with high fidelity and consistency.
problem Challenges in editing image content with text-to-image models.
method Using coupled stochastic differential equations to guide generative model sampling.
result Achieves high prompt fidelity and near-pixel-level consistency.
Paper proposes efficient image inversion and editing using rectified stochastic differential equations.
problem Inversion and editing of real images using generative models.
method Proposes RF inversion using dynamic optimal control and a linear quadratic regulator, extending to stochastic sampler for Flux.
result Allows state-of-the-art performance in zero-shot inversion and editing, outperforming prior works.
New method detects watermarks in LLM-generated text with human edits.
problem Dilution of watermark signals by human edits on LLM-generated text.
method Truncated goodness-of-fit test (Tr-GoF) for robust detection.
result Tr-GoF achieves optimality in robust detection of Gumbel-max watermark.
A technique to quickly fix mistakes in neural networks.
problem Fixing model errors in neural networks quickly and without affecting other samples.
method Editable Training, a model-agnostic training technique.
result Effectiveness demonstrated on large-scale image classification and machine translation tasks.
A review of nearest neighbour classifiers, focusing on similarity measures and computational efficiency.
problem Improving the performance of nearest neighbour classifiers.
method Explains mechanisms for assessing similarity (distance), identifying nearest neighbours, and reducing data dimensionality.
result Added new sections on time-series similarity measures, retrieval speed-up, and intrinsic dimensionality.
For the task of generating complex outputs such as source code, editing existing outputs can be easier than generating complex outputs from scratch. With this motivation, we propose an approach that first retrieves a training example based on the input (e.g., natural language description) and then edits it to the desir…
Differentiable language model attacks improve adversarial examples for categorical sequence classifiers.
problem Challenges in adversarial attacks for categorical sequence models due to non-differentiability.
method Fine-tuning a language model as a generator of adversarial examples, using a differentiable loss function that combines a surrogate classifier score and approximate edit distance.
result Semantically better and more resistant adversarial examples.
Machine learning experiments show IID assumption is flawed for bathymetry editing.
problem Flawed IID assumption in machine learning for bathymetry editing.
method Real-world computer-assisted labeling task, IID assumption analysis.
result Common random split leads to poor performance in machine learning.
New robustness measure accounts for task-specific symmetries.
problem Traditional robustness measures fail for tasks with inherent symmetries.
method Sound notion of adversarial robustness for equivariant tasks, using randomized smoothing and graph edit distance certificates.
result Provable robustness can be achieved for various tasks with inherent symmetries.
Graph distance metric learning serves as the foundation for many graph learning problems, e.g., graph clustering, graph classification and graph matching. Existing research works on graph distance metric (or graph kernels) learning fail to maintain the basic properties of such metrics, e.g., non-negative, identity of i…
GMED edits stored examples to improve continual learning.
problem Catastrophic forgetting in task-free continual learning.
method Gradient-based memory editing of stored examples.
result GMED-edited examples help prevent forgetting.
Facial attribute editing aims to manipulate single or multiple attributes of a face image, i.e., to generate a new face with desired attributes while preserving other details. Recently, generative adversarial net (GAN) and encoder-decoder architecture are usually incorporated to handle this task with promising results.…
In recent years, the importance of deep learning has significantly increased in pattern recognition, computer vision, and artificial intelligence research, as well as in industry. However, despite the existence of multiple deep learning frameworks, there is a lack of comprehensible and easy-to-use high-level tools for …