Schedule for: 23w5116 - Applications of Hodge Theory on Networks

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

In this talk I will briefly introduce persistent cohomology, and then explain how it can be applied to the problem of topology-preserving dimensionality reduction in data science. Indeed, persistent cohomology is one of the main tools from topological data analysis, often used to estimate the cohomology of a space given a noisy sample. I will explain how this works, and then show how these persistent cohomology classes correspond to topology preserving maps from neighborhoods of the data to familiar spaces such as the n-torus and the real/complex projective spaces. The geometric optimization of these maps involves choosing harmonic cocycle representatives, providing a link to Hodge theoretic questions.

Graph signal processing (GSP) tries to devise appropriate tools to process signals supported on graphs by generalizing classical methods from signal processing of time-series and images - such as smoothing, filtering, and interpolation - to signals supported on the nodes of a graph. Typically, this involves leveraging the structure of the graph as encoded in the spectral properties of the graph Laplacian. In certain scenarios, such as traffic network analysis, the signals of interest are however naturally defined as flows the edges of a graph, rather than on the nodes. After a brief recap of the central ideas of GSP, we examine why standard tools from GSP may not be suitable for the analysis of such flow signals. More specifically, we discuss how the underlying notion of 'signal vs noise' inherited from typically considered variants of the graph Laplacian are not suitable when dealing with edge signals that encode flows. To overcome this limitation, we devise signal processing toolbased on the Hodge-Laplacian and the associated discrete Hodge Theory for simplicial (and cellular) complexes. We discuss applications of these ideas for signal smoothing, semi-supervised and active learning for edge-flows on discrete or discretized spaces.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the PDC front desk for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

In this talk, we will survey some applications of combinatorial Hodge theory to the social choice and game theory. Social choice theory is a classical topic in Economics, which is featured with the celebrated Impossibility Theorems by Nobel Laureates Ken Arrow and Amartya Sen. Despite of the intrinsic conflicts between the faithful representation of individuals and the desire for consistent social orders, in reality we are still looking for possible preference aggregation rules out of impossibilities. Hodge Theory, as a bridge between the algebraic topology and geometry, is surprisingly enabling us a tool of preference aggregation as a generalization of the classical Borda count, arguably the most consistent and tractable social choice rule. We shall discuss these from a revisit of those impossibility theorems to see what is possible that Hodge decomposition provides us. Last but not the least, an extension to game theory is discussed where one is facing the landscape of multiple utility functions toward finding equilibria.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

This talk will introduce basic properties of sheaves on graphs and show that they are a suitable framework to describe flows on networks, sampling, i.e. how multiple local measurements combine to yield global properties, and opinion dynamics in social networks.

Graphs serve to model phenomena in various disciplines. In applications one often adds some structure to a graph, such as assigning to each edge and vertex a "weight," typically a positive real number (of varying values). Another way to enhance a graph is to assign to each edge and vertex a vector space (of varying dimensions), along with "restriction maps," meaning a linear map from each edge's vector space to that of each of its incident vertices. We call this data a "sheaf" on a graph. We will give some examples of how sheaves on graphs and their invariants -- such as cohomology groups -- can model various mathematical phenomenon. We will also indicate the many difficulties in determining these invariants in particular cases. One can similarly define sheaves on other discrete structures, such as simplicial complexes. When working with real or complex vector spaces, the cohomology groups are determined by their Laplacians, which arise from Hodge theory.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

I will give an overview of the basic ideas of Hodge theory and the Hodge decomposition for smooth manifolds and simplicial complexes, including several prominent example applications.

We investigate the flow of money among bank accounts possessed by firms in a region by employing an exhaustive list of all the bank transfers in a regional bank in Japan, to clarify how the network of money flow is related to the economic activities of the firms. The network statistics and structures are examined and shown to be similar to those of a nationwide production network. Specifically, the bowtie analysis indicates what we refer to as a "walnut" structure with core and upstream/downstream components. To quantify the location of an individual account in the network, we used the Hodge decomposition method and found that the Hodge potential of the account has a significant correlation to its position in the bowtie structure as well as to its net flow of incoming and outgoing money and links, namely the net demand/supply of individual accounts. In addition, we used non-negative matrix factorization to identify important factors underlying the entire flow of money; it can be interpreted that these factors are associated with regional economic activities. One factor has a feature whereby the remittance source is localized to the largest city in the region, while the destination is scattered. The other factors correspond to the economic activities specific to different local places. This study serves as a basis for further investigation on the relationship between money flow and economic activities of firms.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We present the adaptations of Forman's discretization of Ricci curvature to the setting of networks and their higher dimensional generalizations and we explore their applications to a variety of real-life applications, such as: brain networks, chemical reactions, financial market crushes, stem cells and cancer research, autism understanding, intelligence of communication and social networks, deep learning and semantics. We also show how it naturally allows for the understanding of the long-time evolution of networks, their sampling as well as their study through persistent homology.

Combinatorial thinking has entered the field of economics in social choice theory, pioneered by Arrow (1951). We argue order lattices are a befitting object for modeling preferences, choice, and information on the level of the individual, as well as a theoretical tool for modeling aggregation. Recently introduced (Ghrist & Riess, 2022), an operator, called the Tarski Laplacian, acting on the (product) lattice of 0-cochains of a lattice-valued sheaf, induces “heat flow” dynamics for lattice data supported on an (e.g. social) network. A Hodge-style theorem characterizes the time-invariant solutions of the heat equation as global sections of a lattice-valued sheaf. This talk aims to draw connections between both lines of work and encourage future conversation and collaboration.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Social, biological, and physical systems are widely studied through the modeling of dynamical processes over networks, and one commonly investigates the interplay between structure and dynamics. I will discuss how cyclic patterns in networks can influence models for collective and diffusive processes, including generalized models in which dynamics are defined over simplicial complexes and multiplex networks. Our approach relies on homology theory, which is the subfield of mathematics that formally studies cycles (and more generally, k-dimensional holes). We will make use of techniques including persistent homology and Hodge theory to examine the role of cycles in helping organize dynamics onto low-dimensional manifolds.

We extend the notion of effective resistance from the classical circuit theory to simplicial electrical networks. Our approach, based on combinatorial Hodge theory, is to assign a unique harmonic class to a current generator, an extra top-dimensional simplex to be attached to the simplicial resistor network. The harmonic class gives rise to the current (cycle) and the voltage (cocyle) satisfying Thomson's energy-minimizing principle and Ohm's law for simplicial networks. We introduce a simplicial analogue of Kirchhoff index, the sum of all pairwise effective resistances, proposing the quantity as a measure of robustness of simplicial complexes. Also, we present a method for counting spanning trees in simplicial complexes by using a combinatorial interpretation of effective resistance. This talk is based on joint works with Kook and Duval-Kook-Martin.

Combinatorial Hodge theory is a powerful framework for analyzing skew-symmetric functions on graph edges. We explore applications of the discrete Helmholtz-Hodge Decomposition to the steady state of reversible nonequilibrium stochastic processes.

Real-world competitive systems are often more transitive (hierarchical) systems than intransitive (cyclic), although the space of intransitive systems is larger. Why? We propose a domain-independent mechanism that promotes transitivity in these systems, namely if selection promotes similarity among the competitors then similarity leads to transitivity. We analyze the rate of convergence to transitivity based on the characteristics of the performance function relating the competitors. We also test these findings numerically for game theory and random examples, using the Helmholtz-Hodge Decomposition to measure the size of the transitive and intransitive components.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.