Group-convolutional architectures, which encode symmetries as inductive bias, have shown great success in applications, but can suffer from instabilities as their depth increases and often struggle to learn long range dependencies in data (e.g., over-smoothing in GNNs). We propose and study unitary group convolutions, which allow for deeper networks that are more stable during training. The main focus of the paper are graph neural networks, where we show that unitary graph convolutions provably avoid over-smoothing and achieve competitive performance on benchmark datasets compared to state-of-the-art graph neural networks. We complement our analysis with the study of general unitary convolutions and analyze their role in enhancing stability in general group convolutional architectures.

Convex programming plays a fundamental role in machine learning, data science, and engineering. Disciplined Programming tests and verifies convexity by decomposing a function into basic convex functions (atoms) using convexity-preserving compositions and transformations (rules). We extend disciplined programming to the geodesic setting, allowing for certifying convexity in nonlinear programs on geometric domains. We determine convexity-preserving compositions and transformations for geodesically convex functions on general Cartan-Hadamard manifolds, as well as for the special case of symmetric positive definite matrices, a common setting in matrix-valued optimization. Our paper is accompanied by a Julia package SymbolicAnalysis.jl, which interfaces with manifold optimization software, allowing for directly solving verified geodesically convex programs.

The manifold hypothesis presumes that high-dimensional data lies on or near a low-dimensional manifold. While the utility of encoding such structure has been demonstrated empirically, rigorous analysis of its impact on the learnability of neural networks is largely missing. We ask which minimal assumptions on the curvature and regularity of the manifold, if any, render the learning problem efficiently learnable. We prove that learning is hard under input manifolds of bounded curvature, but that additional assumptions on the volume of the data manifold alleviate these fundamental limitations and guarantee learnability. Notable instances of this regime are manifolds which can be reliably reconstructed via manifold learning. We comment on and empirically explore intermediate regimes of manifolds, which have heterogeneous features commonly found in real world data.

We study the problem of learning equivariant neural networks via gradient descent. A recent line of learning theoretic research has demonstrated that learning shallow, fully-connected (i.e. non-symmetric) networks has exponential complexity in the correlational statistical query (CSQ) model, a framework encompassing gradient descent. We ask: are known problem symmetries sufficient to alleviate the fundamental hardness of learning neural nets with gradient descent? We answer this question in the negative. In particular, we give lower bounds for shallow graph neural networks, convolutional networks, invariant polynomials, and frame-averaged networks for permutation subgroups, which all scale either superpolynomially or exponentially in the relevant input dimension. Therefore, learning the complete classes of functions represented by equivariant neural networks via gradient descent remains hard.

Let M in R^d denote a low-dimensional manifold and let X={x1, …, xn} be a collection of points uniformly sampled from M. We study the relationship between the curvature of a random geometric graph built from M and the curvature of the manifold M via continuum limits of Ollivier’s discrete Ricci curvature. We prove pointwise, non-asymptotic consistency results and also show that if M has Ricci curvature bounded from below by a positive constant, then the random geometric graph will inherit this global structural property with high probability. We discuss applications of the global discrete curvature bounds to contraction properties of heat kernels on graphs, as well as implications for manifold learning from data clouds. In particular, we show that the consistency results allow for characterizing the intrinsic curvature of a manifold from extrinsic curvature.

We study geodesically convex problems that can be written as a difference of Euclidean convex functions. This structure arises in key applications such as matrix scaling, M-estimators of scatter matrices, and Brascamp-Lieb inequalities. We exploit this structure to make use of the Convex-Concave Procedure (CCCP), which helps us bypass potentially expensive Riemannian operations and leads to very competitive solvers. Importantly, unlike existing theory for CCCP that ensures convergence to stationary points, we exploit the overall g-convexity structure and provide iteration complexity results for mph{global optimality}.

We study projection-free methods for constrained Riemannian optimization. We propose a Riemannian Frank-Wolfe (RFW) method that handles constraints directly, in contrast to prior methods that rely on (potentially costly) projections. We analyze non-asymptotic convergence rates of RFW to an optimum for geodesically convex problems, and to a critical point for nonconvex objectives. We also present a practical setting under which RFW can attain a linear convergence rate. We complement our theoretical results with an empirical comparison of RFW against state-of-the-art Riemannian optimization methods, and observe that RFW performs competitively.

We introduce Forman-Ricci curvature and its corresponding flow as characteristics for complex networks attempting to extend the common approach of node-based network analysis by edge-based characteristics. Following a theoretical introduction and mathematical motivation, we apply the proposed network-analytic methods to static and dynamic complex networks and compare the results with established node-based characteristics. Our work suggests a number of applications for data mining, including denoising and clustering of experimental data, as well as extrapolation of network evolution.