The paper proves a discrete positive mass theorem for graphs.
problem Formulating and proving a discrete positive mass theorem for graphs.
method Introducing asymptotically flat graphs, defining ADM mass, and using discrete harmonic functions.
result An asymptotically flat graph with non-negative Ricci curvature is isomorphic to the standard grid graph.
A new discrete formula connects vertex and edge distributions on graphs.
problem Optimal transport on graphs with mixed vertex and edge distributions.
method Discrete transport equation and Benamou-Brenier formulation.
result Classification of all Wasserstein-1 geodesics on graphs.
Graph Beta Diffusion (GBD) generates graphs with mixed discrete and continuous components.
problem Generating graphs with mixed discrete and continuous components.
method Introduces Graph Beta Diffusion (GBD) using a beta diffusion process.
result Competes strongly with existing models across graph benchmarks.
Classifies graph configuration spaces homeomorphic to manifolds.
problem Classifying graph configuration spaces homeomorphic to manifolds.
method Developed techniques to translate topological properties into graph theoretic ones.
result Extended Abrams' work to classify certain graph configuration spaces.
The aim of the present article is to give an overview of spectral theory on metric graphs guided by spectral geometry on discrete graphs and manifolds. We present the basic concept of metric graphs and natural Laplacians acting on it and explicitly allow infinite graphs. Motivated by the general form of a Laplacian on …
Discrete noise improves graph generation quality and speed.
problem Generating high-quality discrete graph samples.
method Using discrete noise in diffusion models for graph generation.
result Discrete noise leads to 1.5x better MMDs and 30x faster sampling.
Graphically discrete groups have strong rigidity properties.
problem Understanding the rigidity of group actions on graphs.
method Introducing graphical discreteness and proving rigidity properties.
result Free products of graphically discrete groups are action rigid.
GraphBSI generates graphs by refining a belief in continuous space, outperforming existing models.
problem Generating discrete, unordered graph data is challenging for traditional models.
method GraphBSI uses Bayesian Sample Inference (BSI) to iteratively refine a belief over graph distribution parameters.
result GraphBSI outperforms existing one-shot graph generative models on molecular and synthetic graph generation benchmarks.
Graph Energy Matching improves generation quality for molecular graphs.
problem Discrete energy-based models struggle with efficient and high-quality sampling for graph generation.
method Inspired by transport-map optimization, Graph Energy Matching learns a permutation-invariant potential energy to guide sampling.
result GEM matches or surpasses discrete diffusion baselines on molecular graph benchmarks.
New method calculates discrete curvature using effective resistances.
problem Calculating discrete curvature on graphs.
method Effective resistances to calculate curvature on graph nodes and links.
result Relation to established discrete curvatures and convergence to continuous curvature.
Study error bounds in evaluating distributional computational graphs.
problem Error analysis in evaluating graphs with inputs as probability distributions.
method Establish non-asymptotic error bounds using Wasserstein-1 distance.
result Non-asymptotic error bounds for discretization errors in distributional computational graphs.
The study shows how discrete graphs can resemble hypercube structures under certain curvature conditions.
problem Understanding the structure of graphs with specific curvature conditions.
method Analyzing weighted graphs with lower Ricci curvature bounds and eigenvalue closeness to establish structural similarity.
result Discrete graphs with specific curvature conditions are close to hypercube structures in terms of Frobenius distance and eigenfunctions.
Efficient method certifies robustness of discrete data models, especially graphs.
problem Certifying robustness of discrete data models, especially graphs, is difficult.
method Randomized smoothing framework, sparsity-aware, model-agnostic, tight and efficient.
result Proposes a scalable method for certifying robustness of discrete data models, especially graphs.
Paper proposes DAG-DB for learning discrete DAGs via backpropagation.
problem Learning Directed Acyclic Graphs (DAGs) from data.
method DAG-DB uses Discrete Backpropagation with I-MLE and Straight-Through Estimation.
result DAG-DB learns DAGs effectively using probabilistic sampling and backpropagation.
While state-of-the-art kernels for graphs with discrete labels scale well to graphs with thousands of nodes, the few existing kernels for graphs with continuous attributes, unfortunately, do not scale well. To overcome this limitation, we present hash graph kernels, a general framework to derive kernels for graphs with…
The study examines discrete curvature notions on Cayley graphs of certain groups.
problem Understanding curvature in discrete settings for various groups.
method Introduced Right Angled Artin-Coxeter Hybrids (RAACHs) and derived curvatures of Cayley graphs.
result Addition of relators does not decrease weighted curvatures of Cayley graphs.
GLAD improves latent graph generation by quantizing discrete latent space.
problem Latent space graph generative models lack performance and make unnatural assumptions.
method Adapting diffusion bridges to a discrete latent space, avoiding data space decompositions.
result GLAD achieves competitive performance on graph benchmark datasets.
This paper develops a discrete theory of real Riemann surfaces using quad-graphs and linear discretization.
problem Constructing a discrete theory of real Riemann surfaces.
method Using quad-graphs and linear discretization of Cauchy-Riemann equations, constructing a symplectic homology basis.
result The discrete period matrix has the same canonical decomposition as in the smooth setting.
Graph based clustering is one of the major clustering methods. Most of it work in three separate steps: similarity graph construction, clustering label relaxing and label discretization with k-means. Such common practice has three disadvantages: 1) the predefined similarity graph is often fixed and may not be optimal f…
The paper characterizes discrete Morse functions on knot diagrams and generalizes a clock theorem.
problem Characterizing discrete Morse functions on knot diagrams and generalizing a clock theorem.
method Using matchings on the Tait graph, the paper constructs discrete Morse functions and counts them with a formula involving the graph Laplacian. It also proves a bijection between these functions and certain rooted spanning forests.
result The paper provides a closed formula for counting discrete Morse functions and generalizes a clock theorem.
This research explores how different discrete diffusion kernels affect graph generation quality.
problem The impact of different discrete diffusion kernels on graph generation quality.
method Developed a family of discrete diffusion kernels that converge to different Bernoulli priors.
result The quality of generated graphs is sensitive to the prior used, challenging previous intuitions.
Graph neural networks (GNNs) are a popular class of machine learning models whose major advantage is their ability to incorporate a sparse and discrete dependency structure between data points. Unfortunately, GNNs can only be used when such a graph-structure is available. In practice, however, real-world graphs are oft…
Improved upper bound for discrete isometric filling of cycles.
problem Finding the minimum number of vertices in a discrete isometric filling of cycle graphs.
method Explicit construction of isometric fillings using concentric annular structures.
result Explicit construction of isometric fillings with \( |V(K_n)| \le \left(\frac{1}{6} + o(1)
ight)n^2 \), improving the upper bound to \( D^* \le \frac{1}{6} \).
No stable discrete maps into certain curved spaces exist.
problem Stability of discrete maps into curved spaces.
method Analysis of weighted length or energy functionals on graphs.
result Non-existence of stable discrete minimal immersions or harmonic maps into specific homogeneous spaces.
A formula connects discrete harmonic surfaces to holomorphic functions.
problem Creating smooth discrete harmonic surfaces from holomorphic data.
method Weierstrass representation formula for discrete harmonic surfaces.
result Smooth converging sequence of discrete harmonic surfaces converges to a minimal surface.
Neural networks' feature geometry evolves like discrete Ricci flow.
problem Understanding neural feature representations and their geometric transformations.
method Approximating input manifold with geometric graphs and analyzing their evolution during training.
result Neural feature geometry evolves like discrete Ricci flow, with nonlinear activations playing a crucial role.
A new graph neural network framework captures long-range interactions efficiently.
problem Efficiently modeling long-range interactions in graph neural networks for PDEs.
method Proposes a multi-level graph neural network framework using multipole methods.
result Captures interaction at all ranges with only linear complexity, learning discretization-invariant solution operators.
The reparameterization trick enables optimizing large scale stochastic computation graphs via gradient descent. The essence of the trick is to refactor each stochastic node into a differentiable function of its parameters and a random variable with fixed distribution. After refactoring, the gradients of the loss propag…
Study of harmonic functions on infinite penny graphs.
problem Characterizing harmonic functions on infinite penny graphs.
method Proving volume doubling and Poincaré inequalities, analyzing polynomial growth harmonic functions.
result Finite dimensional property of ancient solutions of the heat equation.
We apply belief propagation to a Bayesian bipartite graph composed of discrete independent hidden variables and discrete visible variables. The network is the Discrete counterpart of Independent Component Analysis (DICA) and it is manipulated in a factor graph form for inference and learning. A full set of simulations …
New method learns discrete graph diffusion via free-energy gradient flows.
problem Challenges in translating continuous diffusion models to discrete spaces.
method Proposes a novel computational approach using a specific metric on the simplex.
result Recover the underlying functional for various graph classes.
DCRL learns causal relationships from mixed-type discrete data.
problem Challenges in learning causal relationships from discrete, mixed-type data.
method Generative framework modeling directed acyclic graph and sparse bipartite graph, flexible measurement models for different types of data.
result Consistent recovery of latent causal structure from observed data distribution.
We present a notion of super Ricci flow for time-dependent finite weighted graphs. A challenging feature is that these flows typically encounter singularities where the underlying graph structure changes. Our notion is robust enough to allow the flow to continue past these singularities. As a crucial tool for this purp…
New scalar curvature defined from Ollivier-Ricci curvature for graphs.
problem Defining scalar curvature for graphs and point clouds.
method Defining a new scalar version of Ollivier-Ricci curvature and proving its convergence.
result The new scalar curvature converges to scalar curvature for sampled manifolds.
A natural approach to analyze interaction data of form "what-connects-to-what-when" is to create a time-series (or rather a sequence) of graphs through temporal discretization (bandwidth selection) and spatial discretization (vertex contraction). Such discretization together with non-negative factorization techniques c…
This work proposes a method to learn graph structure for multivariate time series forecasting.
problem Improving multivariate time series forecasting by leveraging pairwise information.
method Learning a probabilistic graph model through optimizing mean performance over graph distribution parameterized by a neural network.
result Our method outperforms existing approaches in simplicity, efficiency, and performance.
Graphs approximate semigroups for diffusion on Riemannian manifolds.
problem Approximating semigroups for diffusion on Riemannian manifolds.
method Discretized approximation using random walks on proximity graphs.
result Quantitative error estimates for convergence of discrete semigroups to continuous semigroups.
New theorem on graph curvature thresholds and uniqueness.
problem Determining the minimum number of edges for graphs to have positive curvature.
method Analyzing graphs with specific edge counts and curvature properties.
result Optimal threshold for positive curvature and uniqueness of extremal graphs.
We study the set of critical exponents of discrete groups acting on regular trees. We prove that for every real number δ between 0 and 21logq, there is a discrete subgroup Γ acting without inversion on a (q+1)-regular tree whose critical exponent is equal to δ. Explicit construction of edge-index…
Bayesian inference of discrete component states in civil infrastructures using PGMs and GNNs.
problem Inferring discrete states of civil infrastructure components from measurable responses is an ill-posed inverse problem.
method The study proposes a novel Bayesian inversion paradigm based on Probabilistic Graphical Models (PGMs) and Graph Neural Networks (GNNs). PGMs are used to model the problem, with parameters learned from data and structural topology prior. Inference is accomplished by GNNs, and a graph property-based training strategy is developed.
result The proposed framework effectively solves the challenges of inferring the posterior PDF for discrete variables in high-dimensional problems.
Graph neural nets improve discrete choice modeling with network effects.
problem Modeling network effects in discrete choice problems.
method Graph Convolutional Neural Network (GCNN) architecture.
result Higher predictive performance than standard models with interpretability.
Universal inequalities for Laplacian eigenvalues on discrete groups.
problem Proving inequalities for Laplacian eigenvalues on discrete groups.
method Analyzing Laplacian eigenvalues with Dirichlet boundary conditions on subsets of discrete groups.
result Yang-type universal inequalities for Cayley graphs of amenable groups and the d-regular tree.
The study classifies discrete pseudomanifolds with up to 2d+7 vertices.
problem Understanding discrete pseudomanifolds with a small number of vertices.
method Proved existence of at least 2(d+1) vertices, classified up to 2d+6 vertices, established equivalence with edge graphs of flag normal pseudomanifolds.
result Every flag normal d-pseudomanifold with at most 2d+7 vertices is either a simplicial d-sphere or a flag triangulation of the (d-2)-fold suspension of RP^2.
EBMs trained on discrete data using heat equations on graph structures.
problem Training EBMs on discrete or mixed data.
method Heat equations on graph structures for data perturbation.
result Efficacy demonstrated in various applications.
Alt-GNNs improve travel mode choice modeling by integrating graph neural networks with GEV models.
problem Capturing alternative dependence in discrete choice models with predefined, symmetric, and uniform dependence.
method Introducing Alternative Graph Neural Networks (Alt-GNNs) that embed alternative dependence within a unified framework.
result Alt-GNNs significantly improve predictive performance over benchmark models in travel mode choice datasets.
The paper explores heat flow and constants on graphs, proving properties and proposing new concepts.
problem Analyzing heat flow and constants on graphs.
method Introducing concepts, recalling graph theory, and proposing new discrete Morse flows.
result Weak discrete Morse flows for heat flow on finite graphs under suitable assumptions.
Iterative Proportional Fitting (IPF), combined with EM, is commonly used as an algorithm for likelihood maximization in undirected graphical models. In this paper, we present two iterative algorithms that generalize upon IPF. The first one is for likelihood maximization in discrete chain factor graphs, which we define …
The paper introduces curvature-based clustering algorithms for graph analysis.
problem Identifying densely connected substructures in graphs for community detection.
method Discrete Ricci curvatures and geometric flows to reveal community structure.
result The curvature-based approach can identify overlapping communities in graphs.