Graph comparison ties to Alexandrov's theorems.
problem Graph comparison conditions on metric spaces.
method Proof of Alexandrov's implications from graph comparisons.
result Complete description of graphs with trivial comparisons.
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 comparison”
The paper compares Steklov and Laplacian eigenvalues on graphs.
problem Understanding the relationship between Steklov and Laplacian eigenvalues on graphs.
method Analyzing eigenvalues and discussing rigidity.
result Obtained Lichnerowicz-type estimates and combinatorial estimates for Steklov eigenvalues.
We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed "comparison graph" and every neighboring pair of items in this graph is compared times according to the Bradley-Terry-Luce model (where t…
Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
Benchmarked over 70 graph clustering algorithms.
problem Lack of comprehensive performance comparison for graph clustering algorithms.
method Evaluated 70+ graph clustering programs for runtime and quality on weighted and unweighted graphs, analyzed ground truth characteristics.
result Supply a start point for engineers and viewpoint for researchers.
The paper compares eigenvalues of Dirichlet, Neumann, and Laplacian on graphs.
problem Eigenvalue comparisons on graphs.
method Analytical comparisons and discussions of eigenvalues and their applications.
result Extensions of eigenvalue estimates for Dirichlet and Neumann eigenvalues.
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.
Automates model comparison in probabilistic programming.
problem Manual derivations for model comparison are error-prone and time-consuming.
method Message passing on a Forney-style factor graph with a custom mixture node.
result Automates Bayesian model averaging, selection, and combination.
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.
GWCA analyzes cross-graph correlations for movie retrieval.
problem Cross heterogeneous graph comparison in movie retrieval.
method Spectral graph filtering, Wasserstein metric learning, generalized eigenvalue decomposition.
result Surprise consistency in learning processes and closed-form solution.
COPT optimizes graph distances via simultaneous optimal transport.
problem Learning graph representations unsupervisedly.
method Simultaneous optimization of dual transport plans between vertices and graph signals.
result COPT preserves spectral information and outperforms state-of-the-art methods.
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.
The report studies ranking from pairwise comparisons in graphs, achieving optimal error bounds and proposing efficient algorithms.
problem Ranking items from pairwise comparisons in general graphs and graphs with locality.
method Maximum likelihood estimation (MLE) and preconditioned gradient descent for general graphs; divide-and-conquer algorithms for graphs with locality.
result MLE achieves optimal error bounds in general graphs and identifies conditions for locality.
This paper evaluates metrics for graph generative models, addressing common pitfalls.
problem Evaluating and comparing graph generative models effectively.
method Systematic evaluation of MMD, analysis of synthetic and real graphs, practical recommendations.
result MMD can be problematic; practical solutions are provided.
The paper derives upper bounds on the MLE error for BTL model under general graphs.
problem Estimating the MLE of BTL model parameters with -loss under general graphs.
method Novel upper bounds on estimation error dependent on algebraic connectivity and graph topology.
result Upper bounds on error are sharp and match minimax lower bounds under certain graph topologies.
We investigate Relational Graph Attention Networks, a class of models that extends non-relational graph attention mechanisms to incorporate relational information, opening up these methods to a wider variety of problems. A thorough evaluation of these models is performed, and comparisons are made against established be…
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…
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.
ELD compares graphs by their embedded Laplacian eigenvectors, resolving ambiguities.
problem Comparing graphs of different sizes and structures.
method ELD uses symmetrization and perturbation techniques to compare graph embeddings.
result ELD resolves ambiguities in graph comparisons, making it a natural pseudo-metric.
Paper establishes statistical inference for pairwise comparison models.
problem Statistical inference for pairwise comparison models when the number of subjects diverges.
method Identifies Fisher information matrix as a weighted graph Laplacian for asymptotic normality.
result Near-optimal asymptotic normality result for maximum likelihood estimator.
Paper quantifies uncertainty in pairwise comparison models.
problem Uncertainty quantification in sparse Bradley-Terry-Luce models.
method Unified proof strategy for MLE and spectral estimator.
result Sharp and uniform non-asymptotic expansions for estimators.
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…
NGAT predicts long-term stock trends using graph attention networks.
problem Lack of effective corporate relationship graph comparison methods and model complexity in stock prediction.
method Developed a Node-level Graph Attention Network (NGAT) for corporate relationship graphs.
result Demonstrated the effectiveness of NGAT across two datasets.
In the lorentzian product we give a comparison between the -volume of an entire -maximal graph and the -volume of the hyperbolic under the assumption that the gradient of the function defining the graph is bounded away from 1. As a consequence, we obtain a Bernstein type theor…
The paper improves spectral ranking methods for diverse comparison graphs.
problem Estimating preference scores from multiway comparisons with heterogeneous sizes.
method Develops a two-step spectral method for estimating preference scores and their uncertainties.
result The two-step spectral method achieves the same asymptotic efficiency as the Maximum Likelihood Estimator (MLE).
Unified interpretation of softmax cross-entropy and negative sampling for knowledge graph embedding.
problem Lack of theoretical relationship between softmax cross-entropy and negative sampling loss functions in knowledge graph embedding.
method Used Bregman divergence to provide a unified interpretation of the two loss functions.
result Theoretical findings for fair comparison of softmax cross-entropy and negative sampling are derived.
Upper bounds for Steklov eigenvalues in subgraphs of polynomial growth Cayley graphs.
problem Finding upper bounds for Steklov eigenvalues in subgraphs of polynomial growth Cayley graphs.
method Discretizing a bounded domain and using comparison theorems.
result The $k^{\mbox{th}}$ eigenvalue tends to proportionally to .
We formulate weighted graph clustering as a prediction problem: given a subset of edge weights we analyze the ability of graph clustering to predict the remaining edge weights. This formulation enables practical and theoretical comparison of different approaches to graph clustering as well as comparison of graph cluste…
This work analyzes Fréchet regression using comparison geometry, providing theoretical and practical insights.
problem Analyzing data on complex structures like manifolds and graphs.
method Theoretical analysis through comparison geometry, focusing on existence, uniqueness, and stability of the Fréchet mean.
result Key results on the existence, uniqueness, and stability of the Fréchet mean, along with statistical guarantees for nonparametric regression.
New methods assess rankability of datasets for meaningful item rankings.
problem Rankability of data represented as graphs.
method New methods based on comparisons to a complete dominance graph.
result Efficient estimation of rankability measures.
We propose a new graph kernel for graph classification and comparison using Ollivier Ricci curvature. The Ricci curvature of an edge in a graph describes the connectivity in the local neighborhood. An edge in a densely connected neighborhood has positive curvature and an edge serving as a local bridge has negative curv…
The question of aggregating pair-wise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In mo…
Graph kernels assess graph similarity for various applications.
problem Assessing similarity between graphs for predictions.
method Review and comparison of existing graph kernels.
result State-of-the-art graph kernels reviewed and compared.
Attention operators have been widely applied in various fields, including computer vision, natural language processing, and network embedding learning. Attention operators on graph data enables learnable weights when aggregating information from neighboring nodes. However, graph attention operators (GAOs) consume exces…
Maximal diameter theorem for graphs with positive Ricci curvature.
problem Diameter comparison in directed graphs with positive Ricci curvature.
method Introduced a Lin-Lu-Yau type Ricci curvature for directed graphs and investigated rigidity properties for the equality case.
result Concluded a maximal diameter theorem of Cheng type.
Embeddings of knowledge graphs have received significant attention due to their excellent performance for tasks like link prediction and entity resolution. In this short paper, we are providing a comparison of two state-of-the-art knowledge graph embeddings for which their equivalence has recently been established, i.e…
The paper studies dynamic ranking and translation synchronization from evolving pairwise comparison graphs.
problem Dynamic pairwise comparison graphs in evolving environments.
method Proposes estimators based on smoothness-penalized least squares and projection onto low frequency eigenspace.
result Finite sample bounds for the estimation error, proving consistency of the proposed methods.
Unified view on random walk and Weisfeiler-Leman kernels, improving accuracy.
problem Improving graph kernel methods for better classification accuracy.
method Define and analyze walk-based node refinement methods, relate to Weisfeiler-Leman test, and introduce new walk-based kernels.
result Walk-based kernels are as expressive as Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison.
A method for dynamic ranking using BTL model and nearest neighbor rank centrality.
problem Aggregating evolving pairwise comparisons to recover item strengths over time.
method Adapting Rank Centrality method to handle dynamic pairwise outcomes.
result Consistency of the method in estimating latent strengths over time.
We address the problem of prediction of multivariate data process using an underlying graph model. We develop a method that learns a sparse partial correlation graph in a tuning-free and computationally efficient manner. Specifically, the graph structure is learned recursively without the need for cross-validation or p…
We study the problem of prediction for evolving graph data. We formulate the problem as the minimization of a convex objective encouraging sparsity and low-rank of the solution, that reflect natural graph properties. The convex formulation allows to obtain oracle inequalities and efficient solvers. We provide empirical…
Unified framework for analyzing graph neural operators converging to graph limits.
problem Analyzing convergence of graph neural operators to graph limits.
method Develops a unified spectral framework for graph neural operators under various graphon assumptions.
result Unified framework enables direct comparison of convergence rates and tradeoffs.
We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgra…
Crowdsourcing platforms are now extensively used for conducting subjective pairwise comparison studies. In this setting, a pairwise comparison dataset is typically gathered via random sampling, either \emph{with} or \emph{without} replacement. In this paper, we use tools from random graph theory to analyze these two ra…
High-dimensional k-sample comparison is a common applied problem. We construct a class of easy-to-implement nonparametric distribution-free tests based on new tools and unexplored connections with spectral graph theory. The test is shown to possess various desirable properties along with a characteristic exploratory fl…
Pairwise comparison data arises in many domains, including tournament rankings, web search, and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items, we study the problem of estimating the underlying comparison probabilities under the assumption of strong stochastic transitivity (SST). We…
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.
Discrete time random walks on a finite set naturally translate via a one-to-one correspondence to discrete Laplace operators. Typically, Ollivier curvature has been investigated via random walks. We first extend the definition of Ollivier curvature to general weighted graphs and then give a strikingly simple representa…