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.
Framework for universal graph function approximators outperforms existing methods.
I prove that the spectrum of the Laplace-Beltrami operator with the Neumann boundary condition on a compact Riemannian manifold with boundary admits a fast approximation by the spectra of suitable graph Laplacians on proximity graphs on the manifold, and similar graph approximation works for metric-measure spaces glued…
Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation…
Landmark-based node embeddings approximate shortest path distances in random graphs.
For node level graph encoding, a recent important state-of-art method is the graph convolutional networks (GCN), which nicely integrate local vertex features and graph topology in the spectral domain. However, current studies suffer from several drawbacks: (1) graph CNNs relies on Chebyshev polynomial approximation whi…
In this paper, we present a general, multistage framework for graphical model approximation using a cascade of models such as trees. In particular, we look at the problem of covariance matrix approximation for Gaussian distributions as linear transformations of tree models. This is a new way to decompose the covariance…
Deep learning approximates shortest path distances in large graphs.
Eigenvalues of manifolds with cylindrical boundaries approximated by graph Laplacians.
Efficiently approximates eigenspaces for symmetric and general matrices.
We compute an approximate Fréchet mean for sets of sparse graphs.
New method for efficient ERG fitting on large graphs.
PPRGo uses approximate PageRank to speed up GNNs on large graphs.
Study on stable translation lengths of surface homeomorphisms and their approximations.
The -NN graph has played a central role in increasingly popular data-driven techniques for various learning and vision tasks; yet, finding an efficient and effective way to construct -NN graphs remains a challenge, especially for large-scale high-dimensional data. In this paper, we propose a new approach to const…
New method for efficient graph learning on large graphs.
This paper approximates -resistance for multi-class graph clustering.
Graph partitioning is the problem of dividing the nodes of a graph into balanced partitions while minimizing the edge cut across the partitions. Due to its combinatorial nature, many approximate solutions have been developed, including variants of multi-level methods and spectral clustering. We propose GAP, a Generaliz…
The paper computes an approximation to the sample Frechet mean of graph sets using spectral information.
GMT improves interpretability of XGNNs by approximating SubMT.
Factor graphs are important models for succinctly representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and partition functions, arise naturally when working with factor graphs. Belief propagation is a widely deplo…
Graph manifolds are manifolds that decompose along tori into pieces with a tame -structure. In this paper, we prove that the simplicial volume of graph manifolds (which is known to be zero) can be approximated by integral simplicial volumes of their finite coverings. This gives a uniform proof of the vanishing of …
Graph homomorphism numbers embed graphs for classification.
This work relaxes GNN symmetries to approximate automorphisms, improving model performance.
We consider adaptations of the Mumford-Shah functional to graphs. These are based on discretizations of nonlocal approximations to the Mumford-Shah functional. Motivated by applications in machine learning we study the random geometric graphs associated to random samples of a measure. We establish the conditions on the…
Paper proves MDS NP-hard and provides a PTAS.
Study error bounds in evaluating distributional computational graphs.
GNNs learn graph representations, with new theory on their power and limitations.
AEGCN uses autoencoder constraints to improve graph node classification.
GNNs improve semi-supervised node regression, but why? We explain.
We analyze a reweighted version of the Kikuchi approximation for estimating the log partition function of a product distribution defined over a region graph. We establish sufficient conditions for the concavity of our reweighted objective function in terms of weight assignments in the Kikuchi expansion, and show that a…
SpGAT learns graph representations using spectral attention for efficiency.
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…
Graph Laplacian approximates manifold eigenvalues with controlled curvature bounds.
Efficient algorithms learn causal graphs with minimal interventions.
We propose a new framework for the analysis of low-rank tensors which lies at the intersection of spectral graph theory and signal processing. As a first step, we present a new graph based low-rank decomposition which approximates the classical low-rank SVD for matrices and multi-linear SVD for tensors. Then, building …
Approximates cycles in planar and bounded-genus graphs.
How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue di…
Improves graph-based active learning for non-Gaussian models.
While the harmonic function solution performs well in many semi-supervised learning (SSL) tasks, it is known to scale poorly with the number of samples. Recent successful and scalable methods, such as the eigenfunction method focus on efficiently approximating the whole spectrum of the graph Laplacian constructed from …
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…
The study evaluates memory and capacity of graph embedding methods.
Graphs approximate semigroups for diffusion on Riemannian manifolds.
Optimal Transport Graph Neural Networks (OT-GNN) improves graph embeddings by using optimal transport.
Spectral graph convolutional neural networks (CNNs) require approximation to the convolution to alleviate the computational complexity, resulting in performance loss. This paper proposes the topology adaptive graph convolutional network (TAGCN), a novel graph convolutional network defined in the vertex domain. We provi…
Graphical models use graphs to compactly capture stochastic dependencies amongst a collection of random variables. Inference over graphical models corresponds to finding marginal probability distributions given joint probability distributions. In general, this is computationally intractable, which has led to a quest fo…
An autonomous variational inference algorithm for arbitrary graphical models requires the ability to optimize variational approximations over the space of model parameters as well as over the choice of tractable families used for the variational approximation. In this paper, we present a novel combination of graph part…
The paper studies harmonic graphs in the Heisenberg group and their properties.
We study signal recovery on graphs based on two sampling strategies: random sampling and experimentally designed sampling. We propose a new class of smooth graph signals, called approximately bandlimited, which generalizes the bandlimited class and is similar to the globally smooth class. We then propose two recovery s…