10th Annual Minisymposium on Computational Topology

Higher-Order Attention Networks

Mustafa Hajij

Over the past decade, deep learning has been remarkably successful at solving a massive set of problems on data types including images and sequential data. This success drove the extension of deep learning to other discrete domains such as sets, point clouds, graphs ,3D shapes, and discrete manifolds. While many of the extended schemes have successfully tackled notable challenges in each particular domain, the plethora of fragmented frameworks have created or resurfaced many long-standing problems in deep learning such as explainability, expressiveness and generalizability. Moreover, theoretical development proven over one discrete domain does not naturally apply to the other domains. Finally, the lack of a cohesive mathematical framework has created many ad hoc and inorganic implementations and ultimately limited the set of practitioners that can potentially benefit from deep learning technologies. In this talk I will talk about a generalized higher-order domain called combinatorial complex (CC) and utilize it to build a new class of attention-based neural networks called higher-order attention networks (HOANs). CCs generalize many discrete domains that are of practical importance such as point clouds, 3D shapes, (hyper)graphs, simplicial complexes, and cell complexes. The topological structure of a CC encodes arbitrary higher-order interactions among elements of the CC. By exploiting the rich combinatorial and topological structure of CCs, HOANs define a new class of higher-order message passing attention-based networks that unify existing higher-order models based on hypergraphs and cell complexes. I will demonstrate the reducibility of any CC to a special graph called the Hasse graph, which allows the characterization of certain aspects of HOANs and other higher order models in terms of graph-based models. Finally the predictive capacity of HOANs will be demonstrated in shape analysis and in graph learning, competing against state-of-the-art task-specific neural networks.

Persistence vs newer isometry invariants of point sets

Vitaliy Kurlin

For standard filtrations (of Vietoris-Rips, Cech, Delaunay complexes) on a finite set of points A in R^N, persistent homology is an isometry invariant of A, preserved by all transformations that maintain the inter-point distances. The stability theorem gives an upper bound on the bottleneck distance between persistence diagrams under bounded noise. There is no lower bound because any set A can be extended to a large family of non-isometric sets `A union T' that have the same 1-dimensional persistence as A, see arxiv:2202.00577, by adding a `tail' T of points to A. All finite sets of points in general position are distinguished up to isometry by the new continuous invariant PDD (Pointwise Distance Distribution). For a point p in A, the PDD matrix has the row of ordered distances to k neighbors of p, see arxiv:2108.04798. This isometry invariant is generically complete for finite and periodic point sets and can be computed in a near-linear time in the number of points by using a fast k-nearest neighbor search. The 200B+ comparisons of 660K+ crystals over a couple of days on a modest desktop identified five duplicates in the world's largest Cambridge Structural Database, which were missed by all past tools, now under investigation by five journals for data integrity. Hence the new isometry invariants are simpler, faster, and stronger than persistence.

Feedforward ReLU neural networks and piecewise-linear geometry

Kathryn Lindsey

Feedforward ReLU neural networks are a relatively simple type of neural network used in machine learning. It is well known that the class of functions realized by feedforward ReLU neural networks coincides with the class of finitely piecewise-linear (PL) functions. However, the finer question of classifying which finitely PL functions can be realized by which network architecture -- in both theory and practice -- remains mysterious. Thus, it is natural to investigate various measures of complexity for functions of this type, and to seek bounds on these complexity measures in terms of the network architecture. In particular, the topological complexity of sublevel sets of these functions is of interest. I will discuss recent joint work with E. Grigsby and M. Masden in which we apply ideas from PL Morse theory to describe the complexity of feedforward ReLU neural network functions.

Persistent Laplacian: properties and algorithms

Yusu Wang

The combinatorial graph Laplacian, as an operator on functions defined on the vertex set of a graph, is a fundamental object in the analysis of and optimization on graphs. There is also an algebraic topology view of the graph Laplacian which arises through considering boundary operators and specific inner products defined on simplicial (co)chain groups. This permits extending the graph Laplacian to a more general operator, the q-th combinatorial Laplacian to a given simplicial complex. An extension of this combinatorial Laplacian to the setting of pairs (or more generally, a sequence of) simplicial complexes was recently introduced by (R.) Wang, Nguyen and Wei. In this talk, I will present several results (including a persistent version of the Cheeger inequality) from our recent study of the theoretical properties for the persistence Laplacian, as well as efficient algorithms to compute it. This is joint work with Facundo Memoli and Zhengchao Wan.

Group Equivariant Non-Expansive Operators: a novel approach to deep learning grounded in Topological Data Analysis

Giovanni Bocchi

Equivariance is now acknowledged as an essential property when working with data that can be transformed by mean of geometrical transformations. In accordance with this, Group Equivariant Non-Expansive Operators (GENEOs) are recently emerging as new tools to build different types of neural networks both explainable and capable of exploiting prior knowledge. In such models standard neurons are replaced by families of operators whose equivariance is set with respect to specific groups of transformations. This is probably the most challenging topic of the research on GENEOs, but, in addition to this, there also other topics that establish deep connections between GENEOs and Topological Data Analysis (TDA). One of the most relevant is that GENEOs can be employed to restrict the intrinsic invariance of TDA, which is insensitive to homeomorphisms, only to proper subgroups of homeomorphisms. In many cases invariance with respect to all homeomorphisms is definitely too large, thus GENEOs allow to analyze data focusing only on some geometrical characteristics. First of all GENEOs will be presented together with the properties that make them interesting from a deep learning perspective, with some links to TDA. Lastly some of the possible applications of GENEOs to different case studies will be reviewed.

Morse-theoretic signal compression and reconstruction

Stefania Ebli

In this talk I will present novel results at the intersection of cellular signal processing and discrete Morse theory. In the usual paradigm, the signals on a simplicial or chain complex are processed using the combinatorial Laplacian and the resultant Hodge decomposition. On the other hand, discrete Morse theory has been widely used to speed up computations, by reducing the size of complexes while preserving their global topological properties. Our approach to signal compression and reconstruction on chain complexes leverages the tools of algebraic discrete Morse theory, which provides a method to reduce and reconstruct a based chain complex together with a set of signals on its cells via deformation retracts, preserving as much as possible the global topological structure of both the complex and the signals. It turns out that any deformation retract of real degreewise finite-dimensional based chain complexes is equivalent to a Morse matching. Moreover, in the case of a particular type of Morse matchings, the reconstruction error is trivial, except on one specific component of the Hodge decomposition. Finally, we developed and implemented an algorithm to compute Morse matchings with minimal reconstruction error, of which I will show explicit examples. This is joint work with Celia Hacker and Kelly Maggs