S. S. Ravi

AAAI Conference 2026 Conference Paper

Information Theoretic Optimal Surveillance for Epidemic Prevalence in Networks

• Ritwick Mishra
• Abhijin Adiga
• Madhav Marathe
• S. S. Ravi
• Ravi Tandon
• Anil Vullikanti

Estimating the true prevalence of an epidemic outbreak is a key public health problem. This is challenging because surveillance is usually resource intensive and biased. In the network setting, prior work on cost sensitive disease surveillance has focused on choosing a subset of individuals (or nodes) to minimize objectives such as probability of outbreak detection. Such methods do not give insights into the outbreak size distribution which, despite being complex and multi-modal, is very useful in public health planning. We introduce TESTPREV, a problem of choosing a subset of nodes which maximizes the mutual information with disease prevalence, which directly provides information about the outbreak size distribution. We show that, under the independent cascade (IC) model, solutions computed by all prior disease surveillance approaches are highly sub-optimal for TESTPREV in general. We also show that TESTPREV is hard to even approximate. While this mutual information objective is computationally challenging for general networks, we show that it can be computed efficiently for various network classes. We present a greedy strategy, called GREEDYMI, that uses estimates of mutual information from cascade simulations and thus can be applied on any network and disease model. We find that GREEDYMI does better than natural baselines in terms of maximizing the mutual information as well as reducing the expected variance in outbreak size, under the IC model.

TMLR Journal 2025 Journal Article

CXAD: Contrastive Explanations for Anomaly Detection: Algorithms, Complexity Results and Experiments

• Ian Davidson
• Nicolás Kennedy
• S. S. Ravi

Anomaly/Outlier detection (AD/OD) is often used in controversial applications to detect unusual behavior which is then further investigated or policed. This means an explanation of why something was predicted as an anomaly is desirable not only for individuals but also for the general population and policy-makers. However, existing explainable AI (XAI) methods are not well suited for Explainable Anomaly detection (XAD). In particular, most XAI methods provide instance-level explanations, whereas a model/global-level explanation is desirable for a complete understanding of the definition of normality or abnormality used by an AD algorithm. Further, existing XAI methods try to explain an algorithm’s behavior by finding an explanation of why an instance belongs to a category. However, by definition, anomalies/outliers are chosen because they are different from the normal instances. We propose a new style of model agnostic explanation, called contrastive explanation, that is designed specifically for AD algorithms. It addresses the novel challenge of providing a model-agnostic and global-level explanation by finding contrasts between the outlier group of instances and the normal group. We propose three formulations: (i) Contrastive Explanation, (ii) Strongly Contrastive Explanation, and (iii) Multiple Strong Contrastive Explanations. The last formulation is specifically for the case where a given dataset is believed to have many types of anomalies. For the first two formulations, we show the underlying problem is in the computational class P by presenting linear and polynomial time exact algorithms. We show that the last formulation is computationally intractable, and we use an integer linear program for that version to generate experimental results. We demonstrate our work on several data sets such as the CelebA image data set, the HateXplain language data set, and the COMPAS dataset on fairness. These data sets are chosen as their ground truth explanations are clear or well-known.

ECAI Conference 2025 Conference Paper

Facilitating Matches on Allocation Platforms

• Yohai Trabelsi
• Abhijin Adiga
• Yonatan Aumann
• Sarit Kraus
• S. S. Ravi

We consider a setting where goods are allocated to agents by way of an allocation platform (e. g. , a matching platform). An “allocation facilitator” aims to increase the overall utility/social-good of the allocation by encouraging (some of the) agents to relax (some of) their restrictions. At the same time, the advice must not hurt agents who would otherwise be better off. Additionally, the facilitator may be constrained by a “bound” (a. k. a. ‘budget’), limiting the number and/or type of restrictions it may seek to relax. We consider the facilitator’s optimization problem of choosing an optimal set of restrictions to request to relax under the aforementioned constraints. Our contributions are three-fold: (i) We provide a formal definition of the problem, including the participation guarantees to which the facilitator should adhere. We define a hierarchy of participation guarantees and also consider several social-good functions. (ii) We provide polynomial algorithms for solving various versions of the associated optimization problems, including one-to-one and many-to-one allocation settings. (iii) We demonstrate the benefits of such facilitation and relaxation, and the implications of the different participation guarantees, using extensive experimentation on three real-world datasets.

IJCAI Conference 2025 Conference Paper

Hazard Function Guided Agent-Based Models: A Case Study of Return Migration from Poland to Ukraine

• Zakaria Mehrab
• S. S. Ravi
• Logan Stundal
• Samarth Swarup
• Srini Venkatramanan
• Bryan Lewis
• Henning Mortveit
• David Leblang

The Russian invasion of Ukraine in February 2022 has led to the largest forced migration crisis in Europe since World War II, with millions displaced both internally and internationally. Among the displaced, approximately 4. 2 million individuals have returned, highlighting the significance of return migration as a critical phase in the migration continuum. Existing studies on return migration are limited in scope, relying on survey-based approaches that suffer from demographic bias, lack of validation against ground truth, and inability to account for uncertainty. We propose a novel computational framework for modeling the return of conflict-induced migrants, using agent-based models (ABMs) and their surrogates. These models are grounded in hazard functions and account for sociopolitical contexts. Our proposed ABMs outperform baseline methods in estimating return migration from Poland to Ukraine by at least 42% and by as much as 57% in terms of normalized root mean squared error (NRMSE). Further, to illustrate the utility of such models for policymakers, we conduct two case studies that estimate the duration of displacement and characterize the demographic breakdown among the returnees.

IJCAI Conference 2025 Conference Paper

IGraSS: Learning to Identify Infrastructure Networks from Satellite Imagery by Iterative Graph-constrained Semantic Segmentation

• Oishee Bintey Hoque
• Abhijin Adiga
• Aniruddha Adiga
• Siddharth Chaudhary
• Madhav V. Marathe
• S. S. Ravi
• Kirti Rajagopalan
• Amanda Wilson

Accurate canal network mapping is essential for water management, including irrigation planning and infrastructure maintenance. State-of-the-art semantic segmentation models for infrastructure mapping, such as roads, rely on large, well-annotated remote sensing datasets. However, incomplete or inadequate ground truth can hinder these learning approaches. Many infrastructure networks have graph-level properties such as reachability to a source (like canals) or connectivity (roads) that can be leveraged to improve these existing ground truth. This paper develops a novel iterative framework IGraSS, combining a semantic segmentation module—incorporating RGB and additional modalities (NDWI, DEM)—with a graph-based ground-truth refinement module. The segmentation module processes satellite imagery patches, while the refinement module operates on the entire data viewing the infrastructure network as a graph. Experiments show that IGraSS reduces unreachable canal segments from ~18% to ~3%, and training with refined ground truth significantly improves canal identification. IGraSS serves as a robust framework for both refining noisy ground truth and mapping canal networks from remote sensing imagery. We also demonstrate the effectiveness and generalizability of IGraSS using road networks as an example, applying a different graph-theoretic constraint to complete road networks.

AAMAS Conference 2025 Conference Paper

On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks

• Daniel J. Rosenkrantz
• Madhav V. Marathe
• Zirou Qiu
• S. S. Ravi
• Richard E. Stearns

Many researchers have considered multi-agent systems over singlelayer networks as models for studying diffusion phenomena. Since real-world networks involve connections between agents with different semantics (e. g. , family member, friend, colleague), the study of multi-agent systems over multilayer networks has assumed increased importance. Our focus is on one class of multi-agent system models over multilayer networks, namely multilayer synchronous dynamical systems (MSyDSs). We study several fundamental problems for this model. We establish properties of the phase spaces of MSyDSs and bring out interesting differences between single-layer and multilayer dynamical systems. We show that, in general, the problem of determining whether two given MSyDSs are inequivalent is NP-complete. This hardness result holds even when the only difference between the two systems is the local function at just one node in one layer. We also present efficient algorithms for the equivalence problem for restricted versions of MSyDSs (e. g. , systems where each local function is a bounded-threshold function, and systems where the number of layers is fixed and each local function is symmetric). In addition, we investigate the expressive power of MSyDSs based on the number of layers. In particular, we examine conditions under which a system with 𝑘 ≥ 2 layers has an equivalent system with 𝑘 − 1 or fewer layers.

AAAI Conference 2025 Conference Paper

Searching for Unfairness in Algorithms’ Outputs: Novel Tests and Insights

• Ian Davidson
• S. S. Ravi

As AI algorithms are deployed extensively, the need to ensure the fairness of their outputs is critical. Most existing work is on “fairness by design” approaches that incorporate limited tests for fairness into a limited number of algorithms. Here, we explore a framework that removes these limitations and can be used with any algorithm’s output that allocates instances to one of K categories/classes such as outlier detection (OD), clustering and classification. The framework can encode standard and novel fairness types beyond simple counting, and importantly, it can detect intersectional unfairness without being specifically told what to look for. Our experimental results show that both standard and novel types of unfairness exist extensively in the outputs of fair-by-design algorithms and the counter-intuitive result that they can actually increase intersectional unfairness.

ICML Conference 2024 Conference Paper

Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks

• Zirou Qiu
• Abhijin Adiga
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard Edwin Stearns
• V. S. Anil Kumar 0001

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 almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.

AAAI Conference 2024 Conference Paper

Learning the Topology and Behavior of Discrete Dynamical Systems

• Zirou Qiu
• Abhijin Adiga
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Anil Vullikanti

Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems.

AAMAS Conference 2024 Conference Paper

Value-based Resource Matching with Fairness Criteria: Application to Agricultural Water Trading

• Abhijin Adiga
• Yohai Trabelsi
• Tanvir Ferdousi
• Madhav Marathe
• S. S. Ravi
• Samarth Swarup
• Anil Kumar Vullikanti
• Mandy L. Wilson

Optimal allocation of agricultural water in the event of droughts is an important global problem. In addressing this problem, many aspects, including the welfare of farmers, the economy, and the environment, must be considered. Under this backdrop, our work focuses on several resource-matching problems accounting for agents with multi-crop portfolios, geographic constraints, and fairness. First, we address a matching problem where the goal is to maximize a welfare function in two-sided markets where buyers’ requirements and sellers’ supplies are represented by value functions that assign prices (or costs) to specified volumes of water. For the setting where the value functions satisfy certain monotonicity properties, we present an efficient algorithm that maximizes a social welfare function. When there are minimum water requirement constraints, we present a randomized algorithm which ensures that the constraints are satisfied in expectation. For a single seller–multiple buyers setting with fairness constraints, we design an efficient algorithm that maximizes the minimum level of satisfaction of any buyer. We also present computational complexity results that highlight the limits on the generalizability of our results. We evaluate the algorithms developed in our work with experiments on both real-world and synthetic data sets with respect to drought severity, value functions, and seniority of agents. ∗Both authors contributed equally to this work. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), N. Alechina, V. Dignum, M. Dastani, J. S. Sichman (eds.), May 6 – 10, 2024, Auckland, New Zealand. © 2024 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org).

AAMAS Conference 2023 Conference Paper

Assigning Agents to Increase Network-Based Neighborhood Diversity

• Zirou Qiu
• Andrew Yuan
• Chen Chen
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Anil Vullikanti

Motivated by real-world applications such as the allocation of public housing, we examine the problem of assigning a group of agents to vertices (e. g. , spatial locations) of a network so that the diversity level is maximized. Specifically, agents are of two types (characterized by features), and we measure diversity by the number of agents who have at least one neighbor of a different type. This problem is known to be NP-hard, and we focus on developing approximation algorithms with provable performance guarantees. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 1⇑2. For the special case where the sizes of agent subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation factor better than 1⇑2. Further, we show that the problem can be solved efficiently when the underlying graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs. Lastly, we conduct experiments to evaluate the performance of the proposed algorithms on synthetic and real-world networks.

AAAI Conference 2023 Conference Paper

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

• Zirou Qiu
• Chen Chen
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns
• Anil Vullikanti

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. Two key problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time. In this work, we study these two problems for anti-coordination games under sequential and synchronous update schemes. For each update scheme, we examine two decision modes based on whether an agent considers its own previous action (self essential) or not (self non-essential) in choosing its next action. Using a relationship between games and dynamical systems, we show that for both update schemes, finding an NE can be done efficiently under the self non-essential mode but is computationally intractable under the self essential mode. We then identify special cases for which an NE can be obtained efficiently. For convergence time, we show that the dynamics converges in a polynomial number of steps under the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

AAAI Conference 2023 Conference Paper

Resource Sharing through Multi-Round Matchings

• Yohai Trabelsi
• Abhijin Adiga
• Sarit Kraus
• S. S. Ravi
• Daniel J. Rosenkrantz

Applications such as employees sharing office spaces over a workweek can be modeled as problems where agents are matched to resources over multiple rounds. Agents' requirements limit the set of compatible resources and the rounds in which they want to be matched. Viewing such an application as a multi-round matching problem on a bipartite compatibility graph between agents and resources, we show that a solution (i.e., a set of matchings, with one matching per round) can be found efficiently if one exists. To cope with situations where a solution does not exist, we consider two extensions. In the first extension, a benefit function is defined for each agent and the objective is to find a multi-round matching to maximize the total benefit. For a general class of benefit functions satisfying certain properties (including diminishing returns), we show that this multi-round matching problem is efficiently solvable. This class includes utilitarian and Rawlsian welfare functions. For another benefit function, we show that the maximization problem is NP-hard. In the second extension, the objective is to generate advice to each agent (i.e., a subset of requirements to be relaxed) subject to a budget constraint so that the agent can be matched. We show that this budget-constrained advice generation problem is NP-hard. For this problem, we develop an integer linear programming formulation as well as a heuristic based on local search. We experimentally evaluate our algorithms on synthetic networks and apply them to two real-world situations: shared office spaces and matching courses to classrooms.

ICML Conference 2022 Conference Paper

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

• Daniel J. Rosenkrantz
• Abhijin Adiga
• Madhav V. Marathe
• Zirou Qiu
• S. S. Ravi
• Richard Edwin Stearns
• V. S. Anil Kumar 0001

Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i. e. , the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0, 1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.

AAMAS Conference 2022 Conference Paper

Maximizing Resource Allocation Likelihood with Minimum Compromise

• Yohai Trabelsi
• Abhijin Adiga
• Sarit Kraus
• S. S. Ravi

Many scenarios where agents with preferences compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have preferences that make them incompatible with some resources. We assume that a Principal chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their preferences within certain limits. The Principal’s goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We develop efficient algorithms for some variants of this budget-constrained maximization problem and establish hardness results for other variants. For the latter variants, we also develop algorithms with performance guarantees. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.

EUMAS Conference 2022 Conference Paper

Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise

• Yohai Trabelsi
• Abhijin Adiga
• Sarit Kraus
• S. S. Ravi

Abstract Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make them incompatible with some resources. We assume that a Principal chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their restrictions within certain limits. The Principal ’s goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We establish hardness results for some variants of this budget-constrained maximization problem and present algorithmic results for other variants. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.

JMLR Journal 2022 Journal Article

Using Active Queries to Infer Symmetric Node Functions of Graph Dynamical Systems

• Abhijin Adiga
• Chris J. Kuhlman
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard E. Stearns

Developing techniques to infer the behavior of networked social systems has attracted a lot of attention in the literature. Using a discrete dynamical system to model a networked social system, the problem of inferring the behavior of the system can be formulated as the problem of learning the local functions of the dynamical system. We investigate the problem assuming an active form of interaction with the system through queries. We consider two classes of local functions (namely, symmetric and threshold functions) and two interaction modes, namely batch (where all the queries must be submitted together) and adaptive (where the set of queries submitted at a stage may rely on the answers to previous queries). We establish bounds on the number of queries under both batch and adaptive query modes using vertex coloring and probabilistic methods. Our results show that a small number of appropriately chosen queries are provably sufficient to correctly learn all the local functions. We develop complexity results which suggest that, in general, the problem of generating query sets of minimum size is computationally intractable. We present efficient heuristics that produce query sets under both batch and adaptive query modes. Also, we present a query compaction algorithm that identifies and removes redundant queries from a given query set. Our algorithms were evaluated through experiments on over 20 well-known networks. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

AAAI Conference 2021 Conference Paper

Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms

• Daniel J. Rosenkrantz
• Madhav Marathe
• S. S. Ravi
• Richard E. Stearns

Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problem can be solved efficiently.

ECAI Conference 2020 Conference Paper

A Framework for Determining the Fairness of Outlier Detection

• Ian Davidson
• S. S. Ravi

Outlier detection (OD) is a widely studied problem whose goal is to identify points from a data set that are considered anomalous. Among the methods used in AI and data science, OD is perhaps the most controversial as common applications such as credit card fraud, cyber-intrusion and terrorist activity all involve suggesting that someone is committing a serious crime. However, there is little work on fair outlier detection. We show how to determine if an outlier detection algorithm’s output is fair with respect to multiple protected status variables (PSVs) by formulating various combinatorial problems which attempt to find an explanation (using the PSVs) that differentiates the outlier group from the normal group. We argue that if there is no solution for these explanation problems, then the output of an algorithm can be considered fair, and give a probabilistic interpretation of our work. Since we prove that the underlying combinatorial problems are computationally intractable (i. e. , NP-hard), our approaches cannot be efficiently gamed/side-stepped.

IJCAI Conference 2020 Conference Paper

Boolean Games: Inferring Agents' Goals Using Taxation Queries

• Abhijin Adiga
• Sarit Kraus
• Oleg Maksimov
• S. S. Ravi

In Boolean games, each agent controls a set of Boolean variables and has a goal represented by a propositional formula. We study inference problems in Boolean games assuming the presence of a PRINCIPAL who has the ability to control the agents and impose taxation schemes. Previous work used taxation schemes to guide a game towards certain equilibria. We present algorithms that show how taxation schemes can also be used to infer agents' goals. We present experimental results to demonstrate the efficacy our algorithms. We also consider goal inference when only limited information is available in response to a query.

AAAI Conference 2020 Conference Paper

Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability

• Prathyush Sambaturu
• Aparna Gupta
• Ian Davidson
• S. S. Ravi
• Anil Vullikanti
• Andrew Warren

Improving the explainability of the results from machine learning methods has become an important research goal. Here, we study the problem of making clusters more interpretable by extending a recent approach of [Davidson et al. , NeurIPS 2018] for constructing succinct representations for clusters. Given a set of objects S, a partition π of S (into clusters), and a universe T of tags such that each element in S is associated with a subset of tags, the goal is to find a representative set of tags for each cluster such that those sets are pairwise-disjoint and the total size of all the representatives is minimized. Since this problem is NP-hard in general, we develop approximation algorithms with provable performance guarantees for the problem. We also show applications to explain clusters from datasets, including clusters of genomic sequences that represent different threat levels.

ICML Conference 2019 Conference Paper

PAC Learnability of Node Functions in Networked Dynamical Systems

• Abhijin Adiga
• Chris J. Kuhlman
• Madhav V. Marathe
• S. S. Ravi
• V. S. Anil Kumar 0001

We consider the PAC learnability of the local functions at the vertices of a discrete networked dynamical system, assuming that the underlying network is known. Our focus is on the learnability of threshold functions. We show that several variants of threshold functions are PAC learnable and provide tight bounds on the sample complexity. In general, when the input consists of positive and negative examples, we show that the concept class of threshold functions is not efficiently PAC learnable, unless NP = RP. Using a dynamic programming approach, we show efficient PAC learnability when the number of negative examples is small. We also present an efficient learner which is consistent with all the positive examples and at least (1-1/e) fraction of the negative examples. This algorithm is based on maximizing a submodular function under matroid constraints. By performing experiments on both synthetic and real-world networks, we study how the network structure and sample complexity influence the quality of the inferred system.

IJCAI Conference 2018 Conference Paper

Descriptive Clustering: ILP and CP Formulations with Applications

• Thi-Bich-Hanh Dao
• Chia-Tung Kuo
• S. S. Ravi
• Christel Vrain
• Ian Davidson

In many settings just finding a good clustering is insufficient and an explanation of the clustering is required. If the features used to perform the clustering are interpretable then methods such as conceptual clustering can be used. However, in many applications this is not the case particularly for image, graph and other complex data. Here we explore the setting where a set of interpretable discrete tags for each instance is available. We formulate the descriptive clustering problem as a bi-objective optimization to simultaneously find compact clusters using the features and to describe them using the tags. We present our formulation in a declarative platform and show it can be integrated into a standard iterative algorithm to find all Pareto optimal solutions to the two objectives. Preliminary results demonstrate the utility of our approach on real data sets for images and electronic health care records and that it outperforms single objective and multi-view clustering baselines.

AAMAS Conference 2018 Conference Paper

Testing Phase Space Properties of Synchronous Dynamical Systems with Nested Canalyzing Local Functions

• Daniel J. Rosenkrantz
• Madhav V. Marathe
• S. S. Ravi
• Richard E. Stearns

Discrete graphical dynamical systems serve as effective formal models for simulations of agent-based models, propagation of contagions in social networks and study of biological phenomena. A class of Boolean functions, called nested canalyzing functions (NCFs), has been used as a good model of certain biological phenomena. Motivated by these biological applications, we study a variety of analysis problems for synchronous graphical dynamical systems (SyDSs) over the Boolean domain, where each local function is an NCF. We present intractability results for some properties as well as efficient algorithms for others. In several cases, our results clearly delineate intractable and efficiently solvable versions of problems.

IJCAI Conference 2007 Conference Paper

• Chris Barrett
• H. B. Hunt III
• M. V. Marathe
• S. S. Ravi
• D. J. Rosenkrantz
• R. E. Stearns
• M. Thakur

Motivated by applications such as the spread of epidemics and the propagation of influence in social networks, we propose a formal model for analyzing the dynamics of such networks. Our model is a stochastic version of discrete dynamical systems. Using this model, we formulate and study the computational complexity of two fundamental problems (called reachability and predecessor existence problems) which arise in the context of social networks. We also point out the implications of our results on other computational models such as Hopfield networks, communicating finite state machines and systolic arrays.

ICML Conference 2007 Conference Paper

Intractability and clustering with constraints

• Ian Davidson
• S. S. Ravi

SODA Conference 2001 Conference Paper

Adversarial models in evolutionary game dynamics

• Gabriel Istrate
• Madhav V. Marathe
• S. S. Ravi

MFCS Conference 2001 Conference Paper

Analysis Problems for Sequential Dynamical Systems and Communicating State Machines

• Christopher L. Barrett
• Harry B. Hunt III
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Richard Edwin Stearns

Abstract Informally, a sequential dynamical system (SDS) consists of an undirected graph where each node v is associated with a state s v and a transition function f v. Given the state value s v and those of the neighbors of v, the function f v computes the next value of s v. The node transition functions are evaluated according to a specified total order. Such a computing device is a mathematical abstraction of a simulation system. We address the complexity of some state reachability problems for SDSs. Our main result is a dichotomy between classes of SDSs for which the state reachability problems are computationally intractable and those for which the problems are efficiently solvable. These results also allow us to obtain stronger lower bounds on the complexity of reachability problems for cellular automata and communicating state machines.

SODA Conference 1994 Conference Paper

Spanning Trees Short or Small

• R. Ravi 0001
• Ravi Sundaram
• Madhav V. Marathe
• Daniel J. Rosenkrantz
• S. S. Ravi

STOC Conference 1993 Conference Paper

Many birds with one stone: multi-objective approximation algorithms

• R. Ravi 0001
• Madhav V. Marathe
• S. S. Ravi
• Daniel J. Rosenkrantz
• Harry B. Hunt III