Sophisticated Merging Over Random Partitions: A Scalable and Robust Causal Discovery Approach.

Scalable causal discovery is an essential technology to a wide spectrum of applications, including biomedical studies and social network evolution analysis. To tackle the difficulty of high dimensionality, a number of solutions are proposed in the literature, generally dividing the original variable domain into smaller subdomains by computation intensive partitioning strategies. These approaches usually suffer significant structural errors when the partitioning strategies fail to recognize true causal edges across the output subdomains. Such a structural error accumulates quickly with the growing depth of recursive partitioning, due to the lack of correction mechanism over causally connected variables when they are wrongly divided into two subdomains, finally jeopardizing the robustness of the integrated results. This paper proposes a completely different strategy to solve the problem, powered by a lightweight random partitioning scheme together with a carefully designed merging algorithm over results from the random partitions. Based on the randomness properties of the partitioning scheme, we design a suite of tricks for the merging algorithm, in order to support propagation-based significance enhancement, maximal acyclic subgraph causal ordering, and order-sensitive redundancy elimination. Theoretical studies as well as empirical evaluations verify the genericity, effectiveness, and scalability of our proposal on both simulated and real-world causal structures when the scheme is used in combination with a variety of causal solvers known effective on smaller domains.

Understanding Social Causalities Behind Human Action Sequences.

Social causality study on human action sequences is useful and important to improve our understandings to human behaviors on online social networks. The redundant indirect causalities and unobserved confounding factors, such as homophily and simultaneity phenomena, contribute to the huge challenges on accurate causal discovery on such human actions. A causal relationship exists between two persons, if the actions of one person are significantly affected by the actions of the other person, while fairly independent of her/his own prior actions. In this paper, we design a systematic approach based on conditional independence testing to detect such asymmetric relations, even when there are latent confounders underneath the observational action sequences. Technically, a group of asymmetric independence tests are conducted to infer the loose causal directions between action sequence pairs, followed by another group of tests to distinguish different types of relationships, e.g., homophily and simultaneity. Finally, a causal structure learning method is employed to output pairwise causalities with redundant indirect causalities eliminated. Empirical evaluations on simulated data verify the effectiveness and scalability of our proposals. We also present four interesting patterns of causal relations found by our algorithm, on real Sina Weibo feeds, including two new patterns never reported in previous studies.

Deterministic identification of specific individuals from GWAS results.

MOTIVATION: Genome-wide association studies (GWASs) are commonly applied on human genomic data to understand the causal gene combinations statistically connected to certain diseases. Patients involved in these GWASs could be re-identified when the studies release statistical information on a large number of single-nucleotide polymorphisms. Subsequent work, however, found that such privacy attacks are theoretically possible but unsuccessful and unconvincing in real settings. RESULTS: We derive the first practical privacy attack that can successfully identify specific individuals from limited published associations from the Wellcome Trust Case Control Consortium (WTCCC) dataset. For GWAS results computed over 25 randomly selected loci, our algorithm always pinpoints at least one patient from the WTCCC dataset. Moreover, the number of re-identified patients grows rapidly with the number of published genotypes. Finally, we discuss prevention methods to disable the attack, thus providing a solution for enhancing patient privacy. AVAILABILITY AND IMPLEMENTATION: Proofs of the theorems and additional experimental results are available in the support online documents. The attack algorithm codes are publicly available at https://sites.google.com/site/zhangzhenjie/GWAS_attack.zip. The genomic dataset used in the experiments is available at http://www.wtccc.org.uk/ on request.