Minisymposium-1: Interactions Among Analysis, Optimization and Network Science
The goal of this minisymposium is to bring together a diverse group of researchers working on various related areas of analysis, optimization and network science. Topics include applications of networks and graphs, analytical tools for describing the structure of graphs and metric spaces, and the roles of optimization and variational formulations in these settings.
Organizers:
Nathan Albin, Kansas State University
Lukas Geyer, Montana State University
Pietro Poggi-Corradini, Kansas State University
Dominique Zosso, Montana State University
Saturday, October 2, 2021 at 10:20 – 11:40 am (CST) (Session 1)
Sylvester Eriksson-Bique
University of Oulu, Finland
10:20 am
Sharp Duality and Approximations of Sobolev Functions
Given a rectangle, one can consider the two transverse families of curves connecting opposite sides. Modulus is a measurement of the richness of these families, and these moduli are related. Intuitively, if there are very few curves in one direction, it corresponds to an amplitude of short curves in the other. The metric space generalization of this played a crucial role in questions about uniformizations. In this talk, I present a sharp form of a lower bound for duality. Interestingly, the proof requires a new approximation of Sobolev functions that seems of independent interest. Joint work with Pietro Poggi-Corradini.
Nathan Albin
Kansas State University
10:35 am
Random Spanning Trees, Density, and the Minimum Determinant Problem
We consider the problem of minimizing the determinant of the Laplacian of a weighted graph subject to constraints on the edge weights, and show that this problem divides graphs into three classes, depending on whether the determinant is bounded away from zero and whether a minimizing set of weights exists. Which class a graph belongs to is determined by structural properties of the graph, which can be stated both in terms of properties of random spanning trees on the graph, and in terms of a density property of its subgraphs. This is joint work with Pietro Poggi-Corradini and Joan Lind.
Clayton Shonkwiler
Colorado State University
10:50 am
Random Graph Embeddings with General Edge Potentials
In James–Guth–Flory phantom network theory, configurations of a polymer in solution are modeled by random embeddings of a graph whose edges are distributed as Gaussian random vectors. The theory is essentially linear-algebraic in nature, and the statistics of the embedding can be exactly computed in terms of the eigenvalues and eigenvectors of the graph Laplacian. Combining the linear algebra of the graph Laplacian with the simple behavior of Gaussian probability distributions under linear maps has allowed for exact calculations of striking simplicity and power, but mixing algebra and probability in this way makes it difficult to understand which results might generalize to different bond potentials. In this talk, I will present a new formulation of the linear algebra of network polymers which is compatible with a very general class of bond potentials, including Lennard-Jones, FENE, excluded-volume or elastic energy potentials, including fixed edge lengths, as in the case of the freely jointed chain. This is joint work with Jason Cantarella (University of Georgia) and Tetsuo Deguchi and Erica Uehara (Ochanomizu University).
Xavier Pérez Giménez
University of Nebraska-Lincoln
11:05 am
Perfect Matchings in the Random Bipartite Geometric Graph
We consider the standard random bipartite geometric graph process in which n red vertices and n blue vertices are placed at random on the unit d-dimensional cube and edges are added sequentially, between vertices of different colors, in increasing order of edge-length. A natural question is to ask whether the first edge in the process that results in the minimum degree being at least one coincides, with high probability, with the first edge that creates a perfect matching. While this was already known to be false when d=2, as the thresholds are not even of the same order, we are able to positively answer it for d at least 3. (This is joint work with Abigail Raz.)
Xiaojing Ye
Georgia State University
11:20 am
Network Diffusion via Neural Mean-Field Dynamics
We consider a novel learning framework based on neural mean-field dynamics for inference and estimation problems of diffusion on networks. Our new framework is derived from the Mori- Zwanzig formalism to obtain an exact evolution of the node infection probabilities, which renders a delay differential equation with memory integral approximated by learnable time convolution operators, resulting in a highly structured and interpretable RNN. Directly using cascade data, our framework can jointly learn the structure of the diffusion network and the evolution of infection probabilities, which are cornerstone to important downstream applications such as in- fluence maximization. Connections between parameter learning and optimal control are also established. Empirical study shows that our approach is versatile and robust to variations of the underlying diffusion network models, and significantly outperform existing approaches in accuracy and efficiency on both synthetic and real-world data.
Saturday, October 2, 2021 at 2:40 – 4:00 pm (CST) (Session 2)
Puck Rombach
University of Vermont
2:40 pm
Guessing Numbers and Extremal Graph Theory
For a given number of colors, s, the guessing number of a graph is the (base s) logarithm of the cardinality of the largest family of colorings of the vertex set of the graph such that the color of each vertex can be determined from the colors of the vertices in its neighborhood. This quantity is closely related to problems in network coding, circuit complexity and graph entropy. We study the guessing number of graphs as a graph property in the context of classic extremal questions, such as: what is the highest number of edges that a graph on n vertices can have while having bounded guessing number? And, what is the lowest number of edges it can have while being maximal with respect to this property? Joint work with Jo Martin.
Nages Shanmugalingam
University of Cincinnati
2:55 pm
Hyperbolic Fillings of Compact Doubling Metric Measure Spaces and Besov Spaces
The talk, based on joint work with Anders Bjorn and Jana Bjorn, will give a description of a hyperbolic filling of compact doubling metric measure spaces, and use these to link Besov classes of functions on the compact metric space with Sobolev functions on uniform domains.
Jeremy Martin
University of Kansas
3:10 pm
Simplicial Effective Resistance and Enumeration of Spanning Trees
The study of electrical networks on graphs spans physics, probability, and combinatorics, and dates back to the mid-19th century work of Kirchhoff. Recently, Kook and Lee have developed higher-dimensional analogues of core concepts such as effective resistance; here “higher-dimensional” means that the underlying graph is replaced with a simplicial complex. We use this theory to prove combinatorial enumeration theorems for higher-dimensional trees in shifted and color-shifted complexes. This is joint work with Art Duval, Woong Kook, and Kang-Ju Lee.
Guy David
Ball State University
3:25 pm
Bi-Lipschitz Embeddings, Carpets, and Curve Families
We discuss two recent results on bi-Lipschitz embeddings of metric spaces. The first is a recent (negative) answer to a 1997 question of Heinonen and Semmes asking whether spaces that can be “folded” into Euclidean space can be embedded bi-Lipschitzly. The second is a more general theorem showing that spaces with “thick” curve families cannot have bi-Lipschitz embeddings in Euclidean space unless they admit some “infinitesimal splitting”. We also provide some applications to conformal dimension.
Qihui Yang
Kansas State University
3:40 pm
Estimating Data-Driven COVID-19 Mitigation Strategies for Safe University Reopening
After one pandemic year of remote or hybrid instructional modes, universities in the United States are now planning for an in-person fall semester in 2021. However, it is uncertain what the vaccination rate will look like after students, faculty, and staff return to campus. To help inform university-reopening policies, we collected survey data on social contact patterns and developed an agent-based model to simulate the spread of COVID-19 in university settings. In this paper, we aim to identify the immunity threshold that, if exceeded, would lead to a relatively safe on-campus experience for the university population. With relaxed non-pharmaceutical interventions, we estimated that immunity in at least 60% of the university population is needed for safe university reopening. Still, attention needs to be paid to extreme events that could lead to huge infection size spikes. At an immune level of 60%, continuing non-pharmaceutical interventions, such as wearing masks, could lead to an 89% reduction in the maximum cumulative infection, which reflects the possible non-negligible infection size from extreme events.
Saturday, October 2, 2021 at 4:40 – 6:00 pm (CST) (Session 3)
Pietro Poggi-Corradini
Kansas State University
4:40 pm
Convergence of the Probabilistic Interpretation of Modulus
We show that when a quadrilateral in the plane is approximated by an orthodiagonal map (e.g., when doing a Delaunay triangulation) the probability mass functions that arise in the probabilistic interpretation of discrete modulus converge to the uniform distribution on the set of classical horizontal trajectories. The key ingredient is an algorithm that, for an embedded planar graph, takes the current flow between two sets of nodes, and produces a unique path decomposition with non-crossing paths. Moreover, some care was taken to adapt recent results for harmonic convergence on orthodiagonal maps, due to Gurel-Gurevich, Jerison, and Nachmias, to our context. This is joint work with Nathan Albin and Joan Lind.
Heman Shakeri
University of Virginia
4:55 pm
Data Driven Identification and Control of Complex Interconnected System
Networks are landmarks of many complex phenomena where interweaving interactions between different agents transform simple local rule-sets into nonlinear emergent behaviors. While some recent studies unveil associations between the network structure and the underlying dynamical process, identifying stochastic nonlinear dynamical processes continues to be an outstanding problem. Here we develop a simple data-driven framework based on operator-theoretic techniques to identify and control stochastic nonlinear dynamics taking place over large-scale networks. The proposed approach requires no prior knowledge of the network structure and identifies the underlying dynamics solely using a collection of two-step snapshots of the states. This data-driven system identification is achieved by using the Koopman operator to find a low dimensional representation of the dynamical patterns that evolve linearly. Further, we use the global linear Koopman model to solve critical control problems by applying to model predictive control (MPC)–typically, a challenging proposition when applied to large networks. We show that our proposed approach tackles this by converting the original nonlinear programming into a more tractable optimization problem that is both convex and with far fewer variables.
Jonathan Rehmert
Kansas State University
5:10 pm
Quasisymmetric Koebe Uniformization via Transboundary Modulus (Part I)
A circle domain is an open and connected subset of the plane whose complementary components are points or round disks. Given a metric space, X, which is homeomorphic to a countably connected circle domain (and satisfies some mild conditions), we obtain a characterization of when X is quasisymmetric to a circle domain. This characterization is in terms of Schramm’s transboundary modulus and Heinonen-Koskela’s Loewner property and is inspired by Bonk’s celebrated uniformization result for planar carpets. This is joint work with Hrant Hakobyan.
Hrant Hakobyan
Kansas State University
5:25 pm
Quasisymmetric Koebe Uniformization via Transboundary Modulus (Part II
A circle domain is an open and connected subset of the plane whose complementary components are points or round disks. Given a metric space, X, which is homeomorphic to a countably connected circle domain (and satisfies some mild conditions), we obtain a characterization of when X is quasisymmetric to a circle domain. This characterization is in terms of Schramm’s transboundary modulus and Heinonen-Koskela’s Loewner property and is inspired by Bonk’s celebrated uniformization result for planar carpets. This is joint work with Jonathan Rehmert.
Nethali Fernando
University of Texas-Arlington
5:40 pm
Identifying Graph-derived Features of Trained Neuronal Networks via Machine Learning
Neuronal circuits are plastic and neurons can modulate their connections to form new links and adjust the strength of current connections in order to learn new tasks. Among the multiple proposed mechanisms for network training, the full- FORCE model presents a target-based method for modifying the connectivity matrix of a recurrent network to train it to learn temporally complex signals. This method produces networks that perform tasks with fewer neurons and have greater noise robustness than traditional least-squares (FORCE) approaches. In this study, we investigate the relationship between the network architecture and the learning that is occurring in these neuronal networks. Specifically, we simulate full force networks learning different types of periodic signals and keep track of the plasticity adjacency matrix throughout the learning process. We then apply an ensemble of machine learning methods to identify the graph properties most predictive of the learning process by (i) disambiguating trained vs. untrained circuits, and (ii) regressing the error of the network output vs. the desired signal.
Liza Ihnatsyeva
Kansas State University
5:55 pm
Hardy-Sobolev Inequalities in Metric Spaces
Let U be an open set in a metric measure space X. We consider weighted Hardy-Sobolev inequalities in U for the Newtonian (Sobolev) functions on X. We discuss special cases of these inequalities and show the relation between the validity of the Hardy-Sobolev inequality in U and a quasiadditivity property of a weighted relative capacity. Recall that capacities are (typically) subadditive set functions, which very seldom enjoy full additivity. Quasiadditivity is a weak converse of the subadditivity, involving a multiplicative constant and applicable only to certain types of sets. This is a joint work with Juha Lehrbäck and Antti V. Váhákangas
Sunday, October 3, 2021 at 11:00 am – 12:20 pm (CST) (Session 4)
Milad Siami
Northeastern University
11:00 am
Sparse Interactions in Complex Networks
We investigate the problem of jointly designing a reliable sensor and actuator schedule for linear dynamical networks while guaranteeing a control/estimation performance and sparsity certificates. We prove a separation principle, showing that the problem can be decomposed into finding sensor and actuator schedules separately. We further develop a framework to design a sparse actuator schedule for a given large-scale linear system with guaranteed performance bounds using deterministic polynomial-time and randomized approximately linear-time algorithms. We apply our sparse scheduling approach to the IEEE 39-bus test system (a.k.a. the 10-machine New England Power System). We illustrate the effectiveness of our theoretical findings via several numerical simulations using benchmark examples.
Mike Higgins
Kansas State University
11:15 am
On the Detection of Treatment Interference under the K-nearest-neighbor Interference Model
In causal inference, an experiment exhibits treatment interference when the treatment status of one unit affects the response of other units. While traditional causal inference methods often assume no interference between units, there has been a recent abundance of work on the design and analysis of experiments under treatment interference—for example, those conducted on social networks. In this paper, we propose a model of treatment interference where the response of a unit depends only on its treatment status and the statuses of units within its K-neighborhood. We then conduct a simulation study to evaluate the efficacy of existing methods for detecting arbitrary network interference under this model of interference. We show that methods for detection that involve selecting a subset of focal units for analysis currently outperform other methods in detecting interference under our model. However, there appear to be additional opportunities to improve the power of these detection methods.
Marta Lewicka
University of Pittsburgh
11:30 am
Geodesics and Isometric Immersions in Kirigami
Kirigami is the art of cutting paper to make it articulated and deployable, allowing for it to be shaped into complex two and three-dimensional geometries. We are concerned with two questions:
(i) What is the shortest path between points at which forces are applied?
(ii) What is the nature of the ultimate shape of the sheet when it is strongly stretched?
Mathematically, these questions are related to the nature and form of geodesics in the Euclidean plane with linear obstructions (cuts), and the nature and form of isometric immersions of the sheet with cuts when it can be folded on itself. We provide a constructive proof that the geodesic connecting any two points in the plane is piecewise polygonal. We then prove that the full family of polygonal geodesics can be simultaneously rectified into a straight line via a piecewise affine planar isometric immersion.
Yiming Xu
University of Utah
11:45 pm
Probabilistic Methods for Approximate Archetypal Analysis
Archetypal analysis is an unsupervised learning method for exploratory data analysis. One major challenge that limits the applicability of archetypal analysis in practice is the inherent computational complexity of the existing algorithms. In this paper, we provide a novel approximation approach to partially address this issue. Utilizing probabilistic ideas from high-dimensional geometry, we introduce two preprocessing techniques to reduce the dimension and representation cardinality of the data, respectively. We prove that, provided the data is approximately embedded in a low-dimensional linear subspace and the convex hull of the corresponding representations is well approximated by a polytope with a few vertices, our method can effectively reduce the scaling of archetypal analysis. Moreover, the solution of the reduced problem is near-optimal in terms of prediction errors. Our approach can be combined with other acceleration techniques to further mitigate the intrinsic complexity of archetypal analysis. We demonstrate the usefulness of our results by applying our method to summarize several moderately large-scale datasets.
Amir Ghasemian
Yale University
12:00 pm
Stacking Models for Nearly Optimal Link Prediction in Complex Network
Most real-world networks are incompletely observed. Algorithms that can accurately predict which links are missing can dramatically speed up network data collection and improve network model validation. Many algorithms now exist for predicting missing links, given a partially observed network, but it has remained unknown whether a single best predictor exists, how link predictability varies across methods and networks from different domains, and how close to optimality current methods are. We answer these questions by systematically evaluating 203 individual link predictor algorithms, representing three popular families of methods, applied to a large corpus of 550 structurally diverse networks from six scientific domains. We first show that individual algorithms exhibit a broad diversity of prediction errors, such that no one predictor or family is best, or worst, across all realistic inputs. We then exploit this diversity using network-based metalearning to construct a series of “stacked” models that combine predictors into a single algorithm. Applied to a broad range of synthetic networks, for which we may analytically calculate optimal performance, these stacked models achieve optimal or nearly optimal levels of accuracy. Applied to real-world networks, stacked models are superior, but their accuracy varies strongly by domain, suggesting that link prediction may be fundamentally easier in social networks than in biological or technological networks. These results indicate that the state of the art for link prediction comes from combining individual algorithms, which can achieve nearly optimal predictions. We close with a brief discussion of limitations and opportunities for further improvements.