arXiv research

We give a cohomological characterisation of expander graphs, and use it to give a direct proof that expander graphs do not have Yu's property A.

We define a way of approximating actions on measure spaces using finite graphs; we then show that in quite general settings these graphs form a family of expanders if and only if the action is expanding in measure. This provides a somewhat unified approach to construct expanders. We also show that the graphs we obtain …

EGP uses expander graphs to improve GNN performance.

The paper constructs noncompact hyperbolic surfaces with uniform spectral gaps using random graph models.

Using the construction of a nonorientable Curtis-Tits group of type $\tilde A_n$, we obtain new explicit families of expander graphs of valency five for unitary groups over finite fields.

In this paper, the first of a series of two, we continue the study of higher index theory for expanders. We prove that if a sequence of graphs is an expander and the girth of the graphs tends to infinity, then the coarse Baum-Connes assembly map is injective, but not surjective, for the associated metric space $X$. Exp…

New expanders found using origami surfaces with spectral gap.

Enhanced GNN with expanded attention window and partially random embeddings.

TGR rewires temporal graphs to improve TGNN performance.

Expander graphs have been, during the last five decades, the subject of a most fruitful interaction between pure mathematics and computer science, with influence and applications going both ways (cf. [Lub94], [HLW06], [Lub12] and the references therein). In the last decade, a theory of "high dimensional expanders" has …

Kernel and linear regression have been recently explored in the prediction of graph signals as the output, given arbitrary input signals that are agnostic to the graph. In many real-world problems, the graph expands over time as new nodes get introduced. Keeping this premise in mind, we propose a method to recursively …

A Thurston map is a branched covering map from $§^2$ to $§^2$ with a finite postcritical set. We associate a natural Gromov hyperbolic graph $\G=\G(f,\mathcal C)$ with an expanding Thurston map $f$ and a Jordan curve $\mathcal C$ on $§^2$ containing $\post(f)$. The boundary at infinity of $\G$ with associated visual me…

Expander graphs have been a focus of attention in computer science in the last four decades. In recent years a high dimensional theory of expanders is emerging. There are several possible generalizations of the theory of expansion to simplicial complexes, among them stand out coboundary expansion and topological expand…

Graphs with non-negative Ollivier-Ricci curvature cannot be expanders.

Learning representation for graph classification turns a variable-size graph into a fixed-size vector (or matrix). Such a representation works nicely with algebraic manipulations. Here we introduce a simple method to augment an attributed graph with a virtual node that is bidirectionally connected to all existing nodes…

In this paper, the second of a series of two, we continue the study of higher index theory for expanders. We prove that if a sequence of graphs has girth tending to infinity, then the maximal coarse Baum-Connes assembly map is an isomorphism for the associated metric space $X$. As discussed in the first paper in this s…

We study in this paper the maximal version of the coarse Baum-Connes assembly map for families of expanding graphs arising from residually finite groups. Unlike for the usual Roe algebra, we show that this assembly map is closely related to the (maximal) Baum-Connes assembly map for the group and is an isomorphism for …

Let G be a finitely presented group, and let {G_i} be a collection of finite index normal subgroups that is closed under intersections. Then, we prove that at least one of the following must hold: 1. G_i is an amalgamated free product or HNN extension, for infinitely many i; 2. the Cayley graphs of G/G_i (with respect …

We investigate the high-dimensional regression problem using adjacency matrices of unbalanced expander graphs. In this frame, we prove that the $\ell_{2}$-prediction error and the $\ell_{1}$-risk of the lasso and the Dantzig selector are optimal up to an explicit multiplicative constant. Thus we can estimate a high-dim…

In this work we study the degree distribution, the maximum vertex and edge flow in non-uniform random Delaunay triangulations when geodesic routing is used. We also investigate the vertex and edge flow in Erdös-Renyi random graphs, geometric random graphs, expanders and random $k$-regular graphs. Moreover we show that …

New formula simplifies interior polynomial calculation.

Introduces data augmentation for graph convolutional networks, proposing Monte Carlo Graph Learning.

We study the geometry of warped cones over free, minimal isometric group actions and related constructions of expander graphs. We prove a rigidity theorem for the coarse geometry of such warped cones: Namely, if a group has no abelian factors, then two such warped cones are quasi-isometric if and only if the actions ar…

This paper is first-line research expanding GANs into graph topology analysis. By leveraging the hierarchical connectivity structure of a graph, we have demonstrated that generative adversarial networks (GANs) can successfully capture topological features of any arbitrary graph, and rank edge sets by different stages a…

We describe an algorithm that recognizes some (perhaps all) intrinsically knotted (IK) graphs, and can help find knotless embeddings for graphs that are not IK. The algorithm, implemented as a Mathematica program, has already been used by Goldberg, Mattman, and Naimi [6] to greatly expand the list of known minor minima…

Expander graphs have been intensively studied in the last four decades. In recent years a high dimensional theory of expanders has emerged, and several variants have been studied. Among them stand out coboundary expansion and topological expansion. It is known that for every $d$ there are unbounded degree simplicial co…

We show that if X is a minimal length carrier graph in a hyperbolic 3-manifold, M, then if X contains a sufficiently short edge, it must contain a short circuit, as well. The meaning of "short" depends only on the rank of the fundamental group of M. We also expand the class of manifolds which are known to have minimal …

BScNets expands graph learning to higher-order interactions.

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.

GCNs improve multi-layer network classification by expanding the distance between means.

The paper proves stability of certain graph types in Euclidean space with specific densities.

The paper studies mean curvature flow of Lagrangian graphs in pseudo-Euclidean space.

Unobserved confounding is a major hurdle for causal inference from observational data. Confounders---the variables that affect both the causes and the outcome---induce spurious non-causal correlations between the two. Wang & Blei (2018) lower this hurdle with "the blessings of multiple causes," where the correlation st…

The paper defines and proves the existence of train track maps on graphs of groups.

We consider self-similar solutions to mean curvature evolution of entire Lagrangian graphs. When the Hessian of the potential function $u$ has eigenvalues strictly uniformly between -1 and 1, we show that on the potential level all the shrinking solitons are quadratic polynomials while the expanding solitons are in one…

In this article we describe a canonical way to expand a certain kind of $(\mathbb Z_2)^{n+1}$-colored regular graphs into closed $n$-manifolds by adding cells determined by the edge-colorings inductively. We show that every closed combinatorial $n$-manifold can be obtained in this way. When $n\leq 3$, we give simple eq…

Answering a question asked by Agol and Wise, we show that a desired stronger form of Wise's malnormal special quotient theorem does not hold. The counterexamples are generalizations of triangle groups, built using the Ramanujan graphs constructed by Lubotzky--Phillips--Sarnak.

Uniform spectral gap for convex cocompact hyperbolic surfaces and expanders.

We seek to automate the design of molecules based on specific chemical properties. In computational terms, this task involves continuous embedding and generation of molecular graphs. Our primary contribution is the direct realization of molecular graphs, a task previously approached by generating linear SMILES strings …

We investigate the credit risk model defined in Hatchett & Kühn under more general assumptions, in particular using a general degree distribution for sparse graphs. Expanding upon earlier results, we show that the model is exactly solvable in the $N\rightarrow \infty$ limit and demonstrate that the exact solution is de…

This research uncovers high-performing subnetworks in deep GNNs without training.

Artin groups have finite stature based on vertex groups.

We present sufficient conditions for the cohomology of a closed aspherical manifold to be proper Lipschitz in sense of Connes-Gromov-Moscovici [CGM]. The conditions are stated in terms of the Stone-Čech compactification of the universal cover of a manifold. We show that these conditions are formally weaker than the suf…

Extends GCNs to directed graphs for better performance.

Improves graph-based active learning for non-Gaussian models.

The abstract theorem is extended to higher genus surfaces.

Recent research in coarse geometry revealed similarities between certain concepts of analysis, large scale geometry, and topology. Property A of G.Yu is the coarse analog of amenability for groups and its generalization (exact spaces) was later strengthened to be the large scale analog of paracompact spaces using parti…

Semi-implicit graph variational auto-encoder (SIG-VAE) is proposed to expand the flexibility of variational graph auto-encoders (VGAE) to model graph data. SIG-VAE employs a hierarchical variational framework to enable neighboring node sharing for better generative modeling of graph dependency structure, together with …