Unified model generates representations for all nodes in growing graphs.
problem Cold start problem in growing graphs isolates new nodes.
method Generative graph convolutional network that learns adaptive node representations.
result Superior performance on citation network datasets.
Random surfaces with long systoles created from graph theory ideas.
problem Finding surfaces with long systoles.
method Two constructions inspired by graph theory.
result Proved a new lower bound on systole length.
New hyperbolic graph constructed from projections of free splitting graph.
problem Constructing a new hyperbolic graph from projections of free splitting graph.
method Using submanifold projections and geometric realization of free splitting graph.
result A new hyperbolic graph constructed for n≥3. Minimal graphs over simply connected domains grow at most exponentially.
problem Growth of minimal graphs over simply connected domains with boundary values 0.
method Analyzing solutions to the minimal surface equation.
result Minimal graphs have at most exponential growth.
Minimal graphs grow slowly on curved spaces, proving constant solutions.
problem Characterizing minimal graphs with sublinear growth on manifolds.
method New technique to get gradient bounds by integral estimates, no further geometric assumptions.
result Entire solutions are constant when negative part grows like r/logr. GCNs converge and remain stable on large random graphs, revealing geometric insights.
problem Understanding the behavior of GCNs on large, sparse random graphs.
method Analysis of GCNs on random graph models with latent variables and geometric edge probabilities.
result GCNs converge to their continuous counterparts as graph size increases, and are stable to small graph deformations.
The paper studies graph Laplace operator behavior near isolated singularities.
problem Investigating asymptotics of graph Laplace operator near isolated singularities.
method Analyzing curvature growth and conformal modifications to understand operator behavior.
result The graph Laplace operator converges to a weighted Laplace-Beltrami operator as bandwidth decreases, or behaves like \(O(\frac{1}{\sqrt{t}})\) if curvature grows too fast.
Graphs with stronger curvature grow faster.
problem Understanding volume growth on graphs with various curvatures.
method Examined inner-outer and Ricci-Ollivier curvatures to relate them to volume growth.
result Graphs with stronger inner-outer curvature growth have faster volume growth.
We study flip-graphs of triangulations on topological surfaces where distance is measured by counting the number of necessary flip operations between two triangulations. We focus on surfaces of positive genus g with a single boundary curve and n marked points on this curve; we consider triangulations up to homeomor…
We show that if a f.g. group G has a non-elementary WPD action on a hyperbolic metric space X, then the number of G-conjugacy classes of X-loxodromic elements of G coming from a ball of radius R in the Cayley graph of G grows exponentially in R. As an application we prove that for N≥3 the number of…
Sketch-GNN reduces GNN training time and memory usage to sublinear scales.
problem Training GNNs on large graphs is computationally expensive and memory-intensive.
method Develops a sketch-based algorithm that trains GNNs on compact sketches of graph adjacency and node embeddings.
result Training time and memory usage grow sublinearly with respect to graph size.
Most graphs are knotted as they grow larger.
problem Understanding the prevalence of knotting in random graphs as they increase in size.
method Four models for random graphs were analyzed to determine the probability of intrinsic knotting.
result The probability of a graph being intrinsically knotted approaches 1 as the number of vertices increases.
The study examines flip-graphs of non-orientable surfaces and their diameters.
problem Understanding the structure and diameter of flip-graphs of non-orientable surfaces.
method Constructing triangulations of non-orientable surfaces, quotienting by homeomorphisms, and analyzing the resulting flip-graphs.
result Bounds on the diameter of flip-graphs of non-orientable surfaces, with specific growth rates for Möbius strips.
Let G be the mapping torus of a polynomially growing automorphism of a finitely generated free group. We determine which epimorphisms from G to Z have finitely generated kernel, and we compute the rank of the kernel. We thus describe all possible ways of expressing G as the mapping torus of a free grou…
Using expander graphs, we construct a sequence of smooth compact surfaces with boundary of perimeter N, and with the first non-zero Steklov eigenvalue uniformly bounded away from zero. This answers a question which was raised in [9]. The genus grows linearly with N, this is the optimal growth rate.
We study the chromatic number of the curve graph of a surface. We show that the chromatic number grows like k log k for the graph of separating curves on a surface of Euler characteristic -k. We also show that the graph of curves that represent a fixed non-zero homology class is uniquely t-colorable, where t denotes it…
CNN estimates graphlet counts efficiently from historic graphs.
problem Difficulty in computing exact graphlet counts due to exponential growth.
method Convolutional Neural Network (CNN) framework with preprocessing techniques.
result Substantial speedup and high accuracy in estimating graphlet counts.
We formulate a generalization of the volume conjecture for planar graphs. Denoting by <G, c> the Kauffman bracket of the graph G whose edges are decorated by real "colors" c, the conjecture states that, under suitable conditions, certain evaluations of <G,kc> grow exponentially as k goes to infinity and the growth rate…
New causal models for growing networks avoid node deletion constraints.
problem Statistical models based on node exchangeability are not suitable for growing networks.
method Enumerated and partitioned causal directed acyclic graph (DAG) models over pairs of nodes.
result Simple model exhibits flexible power-law degree distributions and emergent phase transitions.
Graphs indistinguishable by GNNs are fully characterized.
problem Limited expressiveness of GNNs in distinguishing non-isomorphic graphs.
method Theory of covering spaces to characterize GNN equivalence classes.
result Arbitrarily many non-isomorphic graphs that GNNs cannot distinguish.
Minimal hyperbolic surface diameter grows logarithmically with genus.
problem Finding the smallest possible diameter of hyperbolic surfaces.
method Random construction, lattice point counting, and exploration of random trivalent graphs.
result Minimal diameter is asymptotic to log(g) as genus g approaches infinity.
Finslerian graph neural networks recover nonlinear diffusion geometry
problem Graph neural networks on point clouds
method Estimates of the Finsler Laplacian
result Recovery of Finsler geometry
Graph neural networks can be adapted to new graphs with a limit object called graphon NNs.
problem Transferability of graph neural networks across different graphs.
method Introduced graphon NNs as limit objects of GNNs and proved a bound on the difference between GNN and graphon-NN outputs.
result The bound on the difference between GNN and graphon-NN outputs vanishes with growing number of nodes if the graph convolutional filters are bandlimited.
We study properties of generic elements of groups of isometries of hyperbolic spaces. Under general combinatorial conditions, we prove that loxodromic elements are generic (i.e. they have full density with respect to counting in balls for the word metric) and translation length grows linearly. We provide applications t…
A known failing of many popular random graph models is that the Aldous-Hoover Theorem guarantees these graphs are dense with probability one; that is, the number of edges grows quadratically with the number of nodes. This behavior is considered unrealistic in observed graphs. We define a notion of edge exchangeability …
Dynamic model clusters interactions over time, improving prediction.
problem Sparse, evolving interaction graphs with temporal dynamics.
method Structured, nonparametric edge-exchangeable model for dynamic clustering.
result Improved predictive performance compared to static models.
Study shows gMPNNs struggle with OOD link prediction in larger test graphs.
problem Inductive out-of-distribution link prediction in larger test graphs.
method Theoretical analysis and development of a gMPNN with structural pairwise embeddings.
result Structural node embeddings from gMPNNs converge to random guessing as test graphs grow.
New method predicts graph structure changes over time.
problem Existing graph prediction methods assume static vertices, limiting their applicability.
method Combines time series prediction with adapted FBA for growing graphs.
result Efficacy demonstrated on synthetic and real datasets.
GraphTSNE visualizes graph data by integrating graph structure and node features.
problem Lack of suitable visualization techniques for graph-structured data.
method GraphTSNE combines t-SNE with graph convolutional networks to visualize graph data.
result GraphTSNE produces better visualizations of graph data compared to existing methods.
Graph rewiring method alleviates over-squashing in GNNs.
problem Over-squashing and bottlenecks in graph neural networks.
method Curvature-based graph rewiring method.
result Negatively curved edges cause over-squashing in GNNs.
Many popular network models rely on the assumption of (vertex) exchangeability, in which the distribution of the graph is invariant to relabelings of the vertices. However, the Aldous-Hoover theorem guarantees that these graphs are dense or empty with probability one, whereas many real-world graphs are sparse. We prese…
We propose a non-parametric link prediction algorithm for a sequence of graph snapshots over time. The model predicts links based on the features of its endpoints, as well as those of the local neighborhood around the endpoints. This allows for different types of neighborhoods in a graph, each with its own dynamics (e.…
A popular approach to semi-supervised learning proceeds by endowing the input data with a graph structure in order to extract geometric information and incorporate it into a Bayesian framework. We introduce new theory that gives appropriate scalings of graph parameters that provably lead to a well-defined limiting post…
Proving a conjecture of Dennis Johnson, we show that the Torelli subgroup of the mapping class group has a finite generating set whose size grows cubically with respect to the genus of the surface. Our main tool is a new space called the handle graph on which the Torelli group acts cocompactly.
The paper introduces a sampling theory for graphons with a Poincaré inequality and proves consistency.
problem Sampling on large graphs is challenging due to their non-Euclidean nature.
method The paper introduces a signal sampling theory for graphons, proving a Poincaré inequality and showing consistency.
result Unique sampling sets for graphon signals are consistent across graph sequences.
A new GNM model outperforms MLP for tabular data.
problem Learning with tabular data.
method Proposes Graph Neural Machine (GNM) replacing MLP's graph representation with a nearly complete graph and using synchronous message passing.
result GNM outperforms MLP in classification and regression tasks.
PGMax automates PGM inference on GPUs, improving quality and speed.
problem Efficient inference in complex discrete PGMs.
method Factor graph specification and loopy belief propagation in JAX.
result Higher-quality inference with up to 3x speedups.
Network data appear in a number of applications, such as online social networks and biological networks, and there is growing interest in both developing models for networks as well as studying the properties of such data. Since individual network datasets continue to grow in size, it is necessary to develop models tha…
A representation for compact 3-manifolds with non-empty non-spherical boundary via 4-colored graphs (i.e., 4-regular graphs endowed with a proper edge-coloration with four colors) has been recently introduced by two of the authors, and an initial classification of such manifolds has been obtained up to 8 vertices of th…
Geodesics count exponentially between triangulations of surfaces with enough topology.
problem Counting geodesics in triangulations of surfaces.
method Analyzing the flip-graph of triangulations and their geodesics.
result The number of geodesics grows exponentially for surfaces with enough topology.
This study compares GNNs and GA-MLPs, finding GA-MLPs can distinguish graphs but not count walks.
problem Comparing expressive power and graph isomorphism testing capabilities of GNNs and GA-MLPs.
method GA-MLPs augment node features with multi-hop operators and apply MLPs node-wise; GNNs are compared as a baseline.
result GA-MLPs can distinguish almost all non-isomorphic graphs but cannot count attributed walks, unlike GNNs.
We present a method to estimate block membership of nodes in a random graph generated by a stochastic blockmodel. We use an embedding procedure motivated by the random dot product graph model, a particular example of the latent position model. The embedding associates each node with a vector; these vectors are clustere…
Survey on graph neural networks for non-Euclidean data.
problem Challenges in processing graph data.
method Taxonomy of graph neural networks.
result Comprehensive overview and taxonomy of GNNs.
Graph matching with feature vectors is solved using a two-layer graph neural network.
problem Graph matching in the presence of sparse binary features.
method Two-layer graph neural network with graph structure.
result Graph neural network can recover correct mapping with high probability under certain conditions.
A new kernel for ranked data tackles computational challenges.
problem Complex geometric structure and partial rankings make existing algorithms infeasible for real-world applications.
method Derives a graph cut kernel that combines submodular optimization and kernel-based methods.
result The graph cut kernel efficiently handles large-scale ranked data.
We propose a nonparametric approach to link prediction in large-scale dynamic networks. Our model uses graph-based features of pairs of nodes as well as those of their local neighborhoods to predict whether those nodes will be linked at each time step. The model allows for different types of evolution in different part…
Abstract result on correlations of pairs in exponentially growing discrete subsets.
problem Pair correlations in exponentially growing discrete subsets with weight functions.
method Proved abstract result on correlations of pairs of elements in an exponentially growing discrete subset with a weight function.
result Distribution function of unscaled differences is t↦2δe−∣t∣, and pair correlation exhibits Poissonian behavior under certain conditions. Graph neural networks struggle to distinguish certain graph structures.
problem Difficulty in distinguishing graphs with graph neural networks.
method Analysis of communication capacity in message-passing model of graph neural networks.
result Capacity of MPNN needs to grow linearly for trees and quadratically for general connected graphs.