Zirou Qiu

Ph.D. Student in CS @ UVA; CV; Google Scholar

I am a Ph.D. student in Computer Science at the University of Virginia working with Madhav Marathe. I am also a part of the research team at the Biocomplexity Institute, working with S. S. Ravi and Dan Rosenkrantz.

I study the foundations and optimizations of large-scale social and technical systems. My research focuses on graph problems that emerge in domains such as dynamical systems, social science, machine learning, multi-agent systems, and game theory.

Research Interests

  • Optimization

  • Machine Learning

  • Dynamical Systems

  • Computational Social Science & Epidemiology

  • Game Theory


You may click the title of a paper to view its pdf file.

Learning Discrete Dynamical Systems under Classification Noise

In Submission

Zirou Qiu*, Zakaria Mehrab*, Abhijin Adiga, Madhav Marathe, S.S. Ravi, Daniel Rosenkrantz, Richard Stearns and Anil Vullikanti.

Summary. Existing studies on learing discrete dynamical systems typically assume that the training data is noise-free, an assumption that is often impractical. In this work, we address this gap by investigating a more realistic and challenging setting: learning discrete dynamical systems from data contaminated with noise. Towards this end, we present efficient noise-tolerant learning algorithms that provide provable performance guarantees under the PAC model, and establish tight bounds on sample complexity. We show that, the number of training samples required by the algorithm in the noisy setting is the same (to within a constant factor) as the information-theoretic upper bound in the noise-free scenario. Further, the number of noisy training samples used by the algorithm is only a logarithmic factor higher than the best-known lower bound.

Keywords. PAC learning; learing under noise; discrete dynamical systems; sample complexity

Theoretical Foundations for Parent Divorcing Transformations in Bayesian Networks

In Submission

With Daniel Rosenkrantz, Madhav V. Marathe and S. S. Ravi

Summary. Parent divorcing is a commonly used technique to reduce the complexity of Bayesian models. In particular, this transformation decreases the number of parents of some nodes in a given Bayesian Network (BN). Such transformations must be done in such a way that solutions to inference problems for the original BN can be readily obtained from the solutions to the new BN. Despite its wide use in practice, there have been no attempts to formally analyze these transformations. In this work, we present a first step towards the development of theoretical foundations for the use of divorce transformations in BNs and establish analytical results. Specifically, we develop a formalism that captures a structural relationship between the original BN and the new BN. Using this formalism, we present an algorithm for parent divorcing which ensures that the treewidth of the modified BN is within a constant factor of that of the original BN. We also present an algorithm that carries out parent divorcing while preserving the domain size of each node. Further, we present lower bound results to prove that there are BNs for which parent divorcing transformations give an exponential increase in the domain size or lead to an exponentially large new BN

Keywords. Bayesian Networks; Parent divorcing transformation; Network embedding; Theoretical foundations

Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks

International Conference on Machine Learning (ICML-2024) [Acc.rate: 27.5%]

Zirou Qiu, Abhijin Adiga, Madhav Marathe, S.S. Ravi, Daniel Rosenkrantz, Richard Stearns and Anil Vullikanti.

Summary. Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for all multilayer graphs.

Keywords. PAC learning; multilayer graphs; discrete dynamical systems; sample complexity; machine learning

Learning the Topology and Behavior of Discrete Dynamical Systems

AAAI Conference on Artificial Intelligence (AAAI-2024) [Acc.rate: 23.8%]

Zirou Qiu, Abhijin Adiga, Madhav Marathe, S.S. Ravi, Daniel Rosenkrantz, Richard Stearns and Anil Vullikanti.

Summary. Due to the large scale of real-world cascades, a complete specification of the underlying dynamical system is often not available. In this work, we study the problem of learning both the behavior and topology of a black-box discrete dynamical system. We show that, in general, this problem is computationally intractable. On the positive side, we present efficient learning methods for different classes of graphs. Further, under a relaxed setting where the topology of an unknown system is partially observed, we develop an efficient PAC learner to infer the full system. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems using the formalism of the Natarajan dimension.

Keywords. PAC learning; discrete dynamical systems; sample complexity; machine learning

Assigning Agents to Increase Network-Based Neighborhood Diversity

Intl. Conf. Autonomous Agents and Multiagent Systems (AAMAS-2023) [Acc.rate: 23.3%, Oral]

Zirou Qiu, Andrew Yuan, Chen Chen, Madhav Marathe, S.S. Ravi, Daniel Rosenkrantz, Richard Stearns and Anil Vullikanti.

Summary. Motivated by the allocation of public housing, we examine the problem of assigning a group of agents (from different demographic subgroups) to vertices (e.g., spatial locations) of a network so that the diversity level is maximized. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 2. For the case where the sizes of demographic subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation in range [0.516, 0.649]. Lastly, we show that the problem can be solved efficiently when the graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs.

Keywords. Optimization; approximation algorithms; resource allocation; diversity

Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

AAAI Conference on Artificial Intelligence (AAAI-2023) [Acc.rate: 19.6%, Oral]

Zirou Qiu, Chen Chen, Madhav Marathe, S.S. Ravi, Daniel Rosenkrantz, Richard Stearns, Anil Vullikanti.

Summary. Anti-coordination games capture strategic situations such as market and social competition. We examine the existence of a Nash equilibrium (NE) and the convergence time for the games under sequential and synchronous dynamics. Using a connection to dynamical systems, we identiy a dichotomy on the players' strategy for the tractability of finding an NE. When finding an NE is intractable, we further identify game variants for which an NE can be obtained efficiently. In terms of convergence time, we show that the best-response dynamics converges in a polynomial number of steps in the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under a particular class of player strategy.

Keywords. Anti-coordination games; dynamical systems; Nash equilibrium, convergence time

Airborne Disease Transmission During Indoor Gatherings over Multiple Time Scales: Modeling Framework and Policy Implications

Proceedings of the National Academy of Sciences (PNAS-2023)

Avinash Dixit, Baltazar Espinoza, Zirou Qiu, Anil Vullikanti, and Madhav Marathe

Summary. Group gathering in enclosed spaces (e.g., classrooms, conferences) is an important route for the spread of respiratory diseases. In this work, we propose a modeling framework to examine airborne disease transmission among a group of people, under scenarios of indoor meetings involving multiple time scales. Towards this end, we study the epidemiological trade-offs emerging by implementing control measures aimed at controlling the viral load. Numerical analysis suggests that ventilation and break times are critical in preventing high viral load levels. Moreover, we found that their impact would equal or exceed that of masking and moderate isolation of infected individuals.

Keywords. Group gathering; multiple time scales; large-scale modeling; pandemic science;

Understanding the Coevolution of Mask Wearing and Epidemics:
A Network Perspective

Proceedings of the National Academy of Sciences (PNAS-2022)

Zirou Qiu, Baltazar Espinoza, Vítor V. Vasconcelos, Chen Chen, Sara M. Constantino, Stefani A. Crabtree, Luojun Yang, Anil Vullikanti, Jiangzhuo Chen, Jörgen Weibull, Kaushik Basu, Avinash Dixit, Simon Levin, Madhav Marathe.

Summary. Non-pharmaceutical interventions such as mask-wearing play a critical role in reducing disease prevalence. In this work, we propose a framework to model the co-evoluation of a disease and a mask-wearing over multilayer networks. We observe a robust non-monotonic relationship between the attack rate (i.e., the fraction of the ever-infected population) and the transmission probability of the disease. Specifically, the attack rate exhibits an abrupt reduction as the transmission probability increases to a critical threshold. Furthermore, we characterize regimes of the transmission probability where multiple waves of infection and mask adoption are expected.

Keywords. Dueling dynamics, multilayer networks, non-pharmaceutical interventions, pandemic science

Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics

AAAI Conference on Artificial Intelligence (AAAI-2022) [Acc.rate: 15%, Oral: 4.8%]

Zirou Qiu, Chen Chen, Madhav Marathe, S.S. Ravi, Daniel Rosenkrantz, Richard Stearns, Anil Vullikanti.

Summary. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of infected vertices is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a fixed point of the system with the minimum number of infected vertices. We fist establish a strong inapproximability for the problem. To cope with the hardness, we identify variants of the problem that can be solved efficiently. Further, we introduce an ILP to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with strategic selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the algorithms.

Keywords. Optimization; dynamical systems; fixed point; contagion diffusion

Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries

International Conference on Machine Learning (ICML-2022) [Acc.rate: 22%, Spotlight]

Daniel Rosenkrantz,(α-β)Abhijin Adiga, Madhav Marathe, Zirou Qiu, S.S. Ravi, Richard Stearns, Anil Vullikanti

Summary. We study the problem of inferring both the network topology and the behavior of such a system through active queries. We present efficient inference algorithms under both batch and adaptive query models for dynamical systems with symmetric local functions. The proposed algorithms show that the structure and behavior of such dynamical systems can be learnt using only a polynomial number of queries. Further, we establish a lower bound on the number of queries needed to learn such dynamical systems. We also present experimental results obtained by running our algorithms on synthetic and real-world networks.

Keywords. Active learning; query model; discrete dynamical systems; query complexity

ELRUNA: Elimination Rule-based Network Alignment

ACM Journal of Experimental Algorithmics (ACM-JEA-2021)

Zirou Qiu, Ruslan Shaydulin, Xiaoyuan Liu, Yuri Alexeev, Christopher S. Henry, Ilya Safro

Summary. Network alignment is a foundamental task in social network analysis; the goal is to infer the similarities over cross-network vertices and discover node-level correspondence between two different networks. In this work, we propose ELRUNA, a novel network alignment framework that relies exclusively on the underlying graph structure. ELRUNA computes the similarity between a pair of cross-network vertices iteratively by accumulating the similarities between their selected neighbors. The resulting cross-network similarity matrix is then used to infer a permutation matrix that encodes the final alignment of cross-network vertices. Through extensive numerical experiments on real networks, we demonstrate that ELRUNA significantly outperforms the state-of-the-art alignment methods in terms of alignment accuracy. Moreover, ELRUNA is robust to network perturbations such that it can maintain a close to optimal objective value under a high level of noise added to the original networks.

Keywords. Optimization; network alignment; social network analysis


  • Research topics: Foundations and optimizations of socio-technical systems.

  • See publications.

Fall 2020 - Present

  • Research topics: Computational Biology and Network Science.

  • Build a processing pipeline for analyzing biological networks.

  • Discover changing patterns in the community structures of microbiome networks.

Jan 2019 - May 2020

  • Research topics: Topology-based network alignment with applications in computational biology.

  • Propose new algorithms for network alignments.

  • Perform data analysis for microbiome networks.

Summer 2019

Other Stuff

What is a discrete dynamical system?

My research focuses on foundations and optimizations of social systems, although you won't often find the term "social systems" in my papers. Instead, my work primarily involves something known as a discrete dynamical system.

In essence, discrete dynamical systems are mathematical frameworks that model cascade processes in social systems, including the spread of social behaviors, information, rumors, diseases, and biological phenomena.

Importantly, discrete dynamical systems provide a theoretical foundation to formally address questions about social systems. Such questions include (1) the convergence and stability of social dynamics; (2) the inference and recovery of black-box social systems; (3) the distribution and optimization for social goods.

In summary, I investigate social systems through the structured framework of discrete dynamical systems. You may read more about discrete dynamical systems here [M&R01, Link].