Cyclic Causal Models

Cyclic directed graphs are rather ubiquitous in modeling economic processes and natural systems, e.g., in the field of biology. In fact, feedback loops in causal systems are generally helpful to improve system performance in the presence of model uncertainty and achieve stability of the system. However, there are relatively few works on characterizing and learning structures that contain cycles. In many state-of-the-art causal models, not only is feedback ignored, but it is also explicitly assumed that there are no cycles passing information among the considered quantities. This discrimination against cyclic structures in the literature is primarily due to simplicities of working with acyclic models and the fact that even a generally accepted definition of statistical equivalence does not exist in the literature for cyclic directed graphs.
The main way for defining equivalence among acyclic directed graphs is based on the conditional independencies of the distributions that they can generate. However, it is known that when cycles are allowed in the structure, conditional independence is not a suitable notion for equivalence of two structures, as it does not reflect all the information in the distribution that can be used for identification of the underlying structure. In this project, we present a general, unified notion of equivalence for linear Gaussian directed graphs.
​
Publications:

• A. Ghassami, A.Yang, N. Kiyavash, and K. Zhang, “Characterizing Distribution Equivalence for Cyclic and Acyclic Directed Graphs,” under submission. arXiv preprint arXiv:1910.12993.

​Interventional Causal Structure Learning

It is known that from purely observational data, in general, a causal DAG is identifiable only up to its Markov equivalence class, and for many ground truth DAGs, the direction of a large portion of the edges will be remained unidentified. The golden standard for learning the causal DAG beyond Markov equivalence is to perform a sequence of interventions on subsets of the variables and use the resulting interventional distributions to improve the identifiability. An intervention on a variable X varies the conditional distribution of X given its direct causes. It can also completely make variable X independent from its causes. The information obtained from an intervention depends on the type of the performed intervention, as well as the size of the intervention (i.e., the number of the target variables), and the location of the targets of the intervention in the underlying causal DAG. An interventional experiment is comprised of a sequence of interventions with different target sets. It can be adaptive, in which each intervention in the sequence is designed based on the information obtained from previous interventions, or non-adaptive, in which all the interventions in the sequence are designed before any data is collected. In this project, we address the following question:
For a fixed number of interventions (budget), what portion of the causal graph is learnable?

Publications:

• A. Ghassami, S. Salehkaleybar, and N. Kiyavash, “Interventional Experiment Design for Causal Structure Learning,” arXiv preprint arXiv:1910.05651.
• A. Ghassami, S. Salehkaleybar, N. Kiyavash, and K. Zhang, “Counting and Sampling from Markov Equivalent DAGs Using Clique Trees,” Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI), 2019. 
• A. Ghassami, S. Salehkaleybar, N. Kiyavash, and E. Bareinboim, “Budgeted Experiment Design for Causal Structure Learning,” Proceedings of the International Conference on Machine Learning (ICML), 2018.
• A. Ghassami, S. Salehkaleybar, and N. Kiyavash, "Optimal experiment design for causal discovery from fixed number of experiments." arXiv preprint arXiv:1702.08567.

​Multi-Domain Causal Structure Learning

Although performing randomized controlled experiments is the golden standard for causal discovery, in many applications, intervening on certain variables in the system may be expensive, unethical, impossible, or even undefined. However, in many real life systems, the data generating distribution may vary over time, or the dataset may be gathered from different domains and hence, not follow a single distribution. While such data is usually problematic in statistical analysis and causes restrictions on the learning power, this property can be leveraged for the purpose of causal discovery. This is because of the coupling relationship between causal modeling and distribution change, i.e., the causal model constraints how the data distribution may change. Therefore, changes in the distribution helps us distinguish the causal modules in the model. We refer to the task of causal discovery from such multi-domain data as the multi-domain causal structure learning. In this setup the main question that we address is how to gain the most advantage from the occurred changes. Note that in this setting, we do not intervene in or perturb the system and merely utilize the observational data gathered from different domains. Unlike the case of interventional causal structure learning, in multi-domain causal structure learning, the experimenter is usually not aware of the location of the changes. Also, the experimenter does not have access to the source of randomization.

Publications:

• A. Ghassami, N. Kiyavash, B. Huang, and K. Zhang, “Multi-Domain Causal Structure Learning in Linear Systems,” Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2018. 
• A. Ghassami, S. Salehkaleybar, N. Kiyavash, and K. Zhang. “Learning Causal Structures Using Regression Invariance,” Proceedings of the Advances in Neural Information Processing Systems (NIPS), 2017.  

Algorithmic Fairness

Automated decision making systems are increasingly being used in real-world applications. In these systems for the most part, the decision rules are derived by minimizing the training error on the available historical data. Therefore, if there is a bias related to a sensitive attribute such as gender, race, religion, etc. in the data, say, due to cultural/historical discriminatory practices against a certain demographic, the system could continue discrimination in decisions by including the said bias in its decision rule. We present an information theoretic framework for designing fair predictors from data, which aim to prevent discrimination against a specified sensitive attribute in a supervised learning setting.

Publication:

• A. Ghassami, S. Khodadadian, and N. Kiyavash, “Fairness in Supervised Learning: An Information Theoretic Approach,” Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2018.  

​Covert Queueing Channel

The existence of covert channels due to the fragility of isolation mechanisms is an important privacy and security threat in computer networks. Such channels may be created across users, which were supposed to be isolated, resulting in information leakage. By definition, a covert channel is a hidden communication channel, which is not intended to exist in the system and is created furtively by users. Covert channels may be exploited by a trusted user, or possibly a malware inside a system with access to secret information to leak it to a distrusted user. Timing channels are one of the main types of covert channels, in which information is conveyed through timing of occurrence of events (e.g., inter-arrival times of packets). A special case of timing channels is covert queueing channels, which can arise between users who share a packet scheduler in a network. Packet schedulers serve packets from multiple streams, which are queued in a single queue. This causes dependencies between delays observed by users. Particularly, the delay that one user experiences depends on the amount of traffic generated by other streams, as well as his own traffic. Hence, a user can gain information about other users' traffic by observing delays of his own stream. This dependency between the streams can breach private information as well as create hidden communication channels between the users. The study of data transmission capacity of covert queueing channels is the focus of this project.

Publications:

• A. Ghassami, and N. Kiyavash, “A Covert Queueing Channel in FCFS Schedulers,” IEEE Transactions on Information Forensics and Security, 13(6), pp.1551-1563, 2018. 
• R. Tahir, T. Khan, X. Gong, A. Ghassami, M. Caesar, and N. Kiyavash, “Sneak-Peek: High Speed Covert Channels in Data Center Networks,” Proceedings of the International Conf. on Computer Communications (INFOCOM), 2016.
• A. Ghassami, X. Gong, and N. Kiyavash, “Capacity Limit of Queueing Timing Channel in Shared FCFS Schedulers,” Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2015. 
• A. Ghassami, A. Yekkehkhany, and Kiyavash, N. (2017). A covert queueing channel in round robin schedulers. arXiv preprint arXiv:1701.08883.