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…
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,657 papers · 148 categories
Trend · papers per month
48 results for “graph distances”
New curvature concept preserves graph distances under operations.
problem Preserving graph distances under graph operations.
method Characterization of distance matrix and its null space.
result Linear system may not have a solution.
Enhances graph comparison by incorporating edge features using Fused Gromov-Wasserstein distance.
problem Graph distances overlook edge attributes, limiting their effectiveness.
method Introduced Fused Gromov-Wasserstein distance for graph comparison with edge features. Proposed algorithms for distance and barycenter computation.
result Empirically validated the effectiveness of the novel distance in graph learning tasks.
The paper tightens bounds on distances between Reeb graphs.
problem Certifying quasi-universality of distances between Reeb graphs.
method Establishes tight bi-Lipschitz bounds for various distances.
result Proves strict universality of the functional contortion distance for contour trees and coincides with interleaving distance for merge trees.
Using existing technology, we prove a Masur-Minsky style distance formula for flip- graph distance between two triangulations, expressed as a sum of the distances of the projections of these triangulations into arc graphs of the suitable subsurfaces of S.
New bounds for average graph distance using curvature and centrality.
problem Finding bounds for average graph distance.
method Using weighted average Ollivier curvature with edge betweenness centrality.
result Equality in bounds achieved for specific reflective graphs.
New distances for causal graphs improve evaluation of learned structures.
problem Difficulty in evaluating graphs learned by causal discovery algorithms.
method Developed a framework for causal distances, including new reachability algorithms.
result Improved distances are faster and more scalable than existing methods.
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…
Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphsstat.ML
Landmark-based node embeddings approximate shortest path distances in random graphs.
problem Capturing global graph distances in node representations.
method Landmark-based node embeddings using shortest path distances from a subset of reference nodes (landmarks).
result Random graphs require lower dimensions in landmark-based embeddings compared to worst-case graphs.
Proposes Isometric Graph Neural Networks to preserve graph distances.
problem Lack of faithful distance representation in graph neural networks.
method Introduces a new technique to modify GNNs' input space and loss function.
result Significant improvement in reflecting graph distances, as measured by KT.
Study on Frechet distance properties for paths and graphs.
problem Understanding topological properties of Frechet distance spaces.
method Proving path-connectedness of Frechet distance spaces and metric balls.
result Spaces of paths and graphs under Frechet distance are path-connected.
Developments in the theory of randomized shortest paths with a comparison of graph node distancesstat.ML
There have lately been several suggestions for parametrized distances on a graph that generalize the shortest path distance and the commute time or resistance distance. The need for developing such distances has risen from the observation that the above-mentioned common distances in many situations fail to take into ac…
Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R^d. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this distance converges …
A new metric compares true and learned causal graphs considering data and graph structure.
problem Comparing true and learned causal graphs accurately.
method Continuous Structural Intervention Distance (CSID) using conditional mean embeddings and maximum mean discrepancy.
result Validated the CSID with synthetic data, showing its effectiveness in comparing causal graphs.
Machine learning is often used in virtual screening to find compounds that are pharmacologically active on a target protein. The weave module is a type of graph convolutional deep neural network that uses not only features focusing on atoms alone (atom features) but also features focusing on atom pairs (pair features);…
New measures assess differences in causal graphs' separations.
problem Evaluating causal discovery algorithms' output.
method Proposes new distance measures capturing causal graphs' separations.
result Proposed distances assess differences in causal graphs' separations.
This study improves graph coarsening methods by preserving graph spectrum and distances.
problem Solving large-scale graph problems by working on a smaller graph.
method Developed a geometric approach using Gromov--Wasserstein distance to minimize the difference between graph distances and their coarsened versions.
result Minimizing the difference between graph distances and their coarsened versions can be achieved using the weighted kernel -means method.
Estimates manifold distances using graph Laplacian, proving consistency.
problem Estimating distances in compact Riemannian manifolds.
method Graph Laplacian estimates of the Laplace-Beltrami operator, bounding errors.
result Proof of consistency for manifold distances.
Distance in the curve graphmath.GT
We estimate the distance in the curve graph of a surface S of finite type using Teichmueller geodesics and assuming to be able to detect curves of distance at least three.
We define a new family of similarity and distance measures on graphs, and explore their theoretical properties in comparison to conventional distance metrics. These measures are defined by the solution(s) to an optimization problem which attempts find a map minimizing the discrepancy between two graph Laplacian exponen…
A novel method for comparing graphs of different sizes using Wasserstein distance.
problem Comparing non-aligned graphs of varying sizes.
method Optimal transport in graph comparison framework, solving a one-to-many assignment problem.
result Significant improvements in graph alignment and classification tasks.
A site-specific Gordian distance between two spatial embeddings of an abstract graph is the minimal number of crossing changes from one to another where each crossing change is performed between two previously specified abstract edges of the graph. It is infinite in some cases. We determine the site-specific Gordian di…
Gromov-Hausdorff distances measure shape difference between the objects representable as compact metric spaces, e.g. point clouds, manifolds, or graphs. Computing any Gromov-Hausdorff distance is equivalent to solving an NP-Hard optimization problem, deeming the notion impractical for applications. In this paper we pro…
Causal inference relies on the structure of a graph, often a directed acyclic graph (DAG). Different graphs may result in different causal inference statements and different intervention distributions. To quantify such differences, we propose a (pre-) distance between DAGs, the structural intervention distance (SID). T…
Topology helps estimate chromatic numbers of random graphs on spheres.
problem Estimating chromatic numbers of random graphs on spheres.
method Topology, specifically connectivity of Lóvasz's neighborhood complex.
result Connectivity bound is useful in dimensions 1 and 2, but generally poor.
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learningcs.LG
DE improves GNNs by distinguishing graph substructures, enhancing accuracy.
problem Limited expressive power of GNNs in representing graph substructures.
method Introduces Distance Encoding (DE) to assist GNNs in distinguishing graph substructures.
result DE distinguishes graph substructures that traditional GNNs cannot, improving accuracy.
Tree Mover's Distance measures graph attributes and improves GNN performance.
problem Measuring generalization and robustness in graph neural networks.
method Introducing Tree Mover's Distance (TMD) for attributed graphs.
result TMD correlates with GNN performance under distribution shifts.
New method beats volumetric barrier for manifold recovery.
problem Reconstructing latent geometry from noisy distances.
method Orthogonal Ring Distance Estimation Routine (ORDER).
result Achieves pointwise distance estimation of order .
This paper shows how to estimate distances in latent space of random graphs using entropic OT.
problem Estimating distances between groups of nodes in latent space of random graphs.
method Entropic Optimal Transport (OT) with stability results for perturbations of the cost matrix.
result Consistent estimation of entropic OT distances between groups of nodes in latent space.
We present Graph Random Neural Features (GRNF), a novel embedding method from graph-structured data to real vectors based on a family of graph neural networks. The embedding naturally deals with graph isomorphism and preserves the metric structure of the graph domain, in probability. In addition to being an explicit em…
New methods cluster and test graphs without vertex correspondence.
problem Clustering and testing of networks without vertex correspondence.
method Inspired by graphon estimation, propose a novel graph distance and clustering algorithms.
result Prove statistical consistency of clustering algorithms under Lipschitz assumptions on graph degrees.
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…
In the present paper we calculate the Gromov-Hausdorff distance between an arbitrary simplex (a metric space all whose non-zero distances are the same) and a finite metric space whose non-zero distances take two distinct values (so-called -distance spaces). As a corollary, a complete solution to generalized Borsuk p…
A new conformal prediction framework for graph-valued outputs using Z-Gromov-Wasserstein distances.
problem Lack of principled uncertainty quantification for graph-valued supervised prediction.
method Proposes a conformal prediction framework using Z-Gromov-Wasserstein distances for graph-valued outputs.
result Provides distribution-free coverage guarantees for graph-valued outputs.
Develops a private synthetic graph generator using Gromov-Wasserstein distance.
problem Creating private synthetic networks for complex data.
method Random connection model, fused Gromov-Wasserstein distance, differential privacy.
result Effective algorithm for generating private synthetic graphs with theoretical guarantees.
Graph curvature measured by inverse resistance distance.
problem Defining and analyzing curvature in graphs.
method Defining curvature via inverse resistance distance and proving properties.
result Graphs with positive curvature have controlled diameter and spectral properties.
A new graph kernel uses LCS and Wasserstein distance for better graph comparisons.
problem Graph learning methods can be limited by information from distant vertices and path length constraints.
method Proposes a Graph Kernel based on LCS similarity and Wasserstein distance in a novel metric space.
result The new kernel emphasizes comparisons between similar paths and reduces information loss.
Sharp threshold found for Frechet mean of inhomogeneous graphs.
problem Finding the Frechet mean of inhomogeneous Erdos-Renyi random graphs.
method Thresholding the expected adjacency matrix of the ensemble.
result The Frechet mean graph of inhomogeneous Erdos-Renyi random graphs exhibits a sharp threshold.
Proposes a new graph kernel framework using regularized Wasserstein distances.
problem Learning optimal transport distances for graph kernels.
method Introduces Regularized Wasserstein (RW) discrepancy with two regularization terms.
result Empirically validated method outperforms state-of-the-art methods.
WEGL embeds graphs in a vector space for faster machine learning.
problem Efficiently embedding graphs for machine learning tasks.
method Wasserstein distance for node embedding similarity, Monge maps for graph representation.
result State-of-the-art classification performance with superior computational efficiency.
Robust GW distance improves graph data alignment.
problem Outliers in GW distance lead to inaccurate comparisons.
method Optimistically perturbed marginal constraints within a Kullback-Leibler divergence-based ambiguity set.
result RGW reduces inaccuracies in graph data alignment.
Study on predicting graph labels at nodes using local averaging and distance estimation.
problem Predicting graph labels at nodes given observations at other nodes.
method Local averaging and distance estimation methods for graph regression.
result Alternative methods can achieve standard nonparametric rates even when graph neighborhoods are too large or small.
PolyGraph Discrepancy improves graph generative model evaluation.
problem Inability of existing metrics to provide an absolute performance measure and comparability across different graph descriptors.
method Approximates Jensen-Shannon distance using binary classifiers trained to distinguish between real and generated graphs.
result PGD provides a more robust and insightful evaluation compared to MMD metrics.
Computing shortest path distances between nodes lies at the heart of many graph algorithms and applications. Traditional exact methods such as breadth-first-search (BFS) do not scale up to contemporary, rapidly evolving today's massive networks. Therefore, it is required to find approximation methods to enable scalable…
Within many real-world networks the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to compare different temporal graphs. To this end, we propose to study dynamic time warping on temporal …
Extends manifold learning to non-Euclidean metrics.
problem Applying manifold learning to data in non-Euclidean spaces.
method Generalizes manifold learning to metric spaces and studies conditions for convergence.
result Conditions for the convergence of graph Laplacian in metric spaces.
We define a class of Euclidean distances on weighted graphs, enabling to perform thermodynamic soft graph clustering. The class can be constructed form the "raw coordinates" encountered in spectral clustering, and can be extended by means of higher-dimensional embeddings (Schoenberg transformations). Geographical flow …
Unified pipeline classifies time series using complex networks and persistent homology.
problem Classifying univariate time series using various graph constructions and metrics.
method Time series to graph, graph to dissimilarity matrix, filtration to persistence diagrams, vectorization to features.
result Persistence-based features are robust to noise and optimal graph type depends on signal structure.