Causal Inference

With CoCa, we can tell whether two continuous variables are causally related, or jointly caused by a hidden confounder. More information here.

Kaltenpoth, D & Vreeken, J We Are Not Your Real Parents: Telling Causal From Confounded by MDL. In: SIAM International Conference on Data Mining (SDM), SIAM, 2019.

Given a database and a target attribute, we are after telling whether there exists a functional, or approximately functional dependency of the target on any set of other attributes in the data, to do so efficiently, as well as reliably, without bias to sample size or dimensionality. To this end we propose the Fedora algorithm. More information here.

Mandros, P, Boley, M & Vreeken, J Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms. In: Proceedings of the IEEE International Conference on Data Mining (ICDM'18), IEEE, 2018.

With Acid, we can highly robustly infer the correct causal direction between two univariate discrete variables using stochastic complexity. More information here.

Budhathoki, K & Vreeken, J Accurate Causal Inference on Discrete Data. In: Proceedings of the IEEE International Conference on Data Mining (ICDM'18), IEEE, 2018.

Slope infers, with very high accruacy, the most likely direction of causation between two numeric univariate variables based on local and global regression. More information here.

Marx, A & Vreeken, J Telling Cause from Effect by Local and Global Regression. Knowledge and Information Systems, pp 1-19, IEEE. (In Press)

We propose the Crack algorithm for identifying the most likely direction of causation between two univariate or multivariate variables of single or mixed-type data. More information here.

Marx, A & Vreeken, J Causal Inference on Multivariate and Mixed Type Data. In: Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Data (ECMLPKDD), Springer, 2018.

With CuTe, we can robustly infer the correct causal direction between two event sequences using sequential normalized maximum likelihood. More information here.

Budhathoki, K & Vreeken, J Causal Inference on Event Sequences. In: Proceedings of the SIAM Conference on Data Mining (SDM), pp 55-63, SIAM, 2018.

Patterns in Discrete Data

Suppose we are given a set of databases, such as sales records over different branches. How can we characterise the differences and the norm between these datasets? What are the patterns that characterise the overall distribution, and what are those that are important for the individual datasets? That is exactly what the DiffNorm algorithm reveals. More information here.

Budhathoki, K & Vreeken, J The Difference and the Norm – Characterising Similarities and Differences between Databases. In: Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), pp 206-223, Springer, 2015.

Slim mines high-quality Krimp code tables directly from data, as opposed to filtering a candidate collection. By doing so, Slim obtains smaller code tables that provide better compression ratios, while also improving on classification accuracy, runtime, and reducing the memory complexity with orders of magnitude. More information here.

Smets, K & Vreeken, J Slim: Directly Mining Descriptive Patterns. In: Proceedings of the SIAM International Conference on Data Mining (SDM), pp 236-247, SIAM, 2012.

mtv is a well-founded approach for summarizing data with itemsets; using a probabilistic maximum entropy model, we iteratively find that itemset that provides us the most new information, and update our model accordingly. We can either mine top-k patterns, or identify the best summarisation by MDL or BIC. More information here.

Mampaey, M, Vreeken, J & Tatti, N Summarizing Data Succinctly with the Most Informative Itemsets. Transactions on Knowledge Discovery from Data vol.6(4), pp 1-44, ACM, 2012.

Self-sufficient itemsets are an effective way to summarise the key associations in data. However, their computation appears demanding, as assessing whether an itemset is self-sufficient requires consideration of all pairwise partitions of an itemset, as well as all its supersets. We propose an branch-and-bound algorithm that employs two powerful pruning techniques to extract them efficiently. More information here.

Webb, G & Vreeken, J Efficient Discovery of the Most Interesting Associations. Transactions on Knowledge Discovery from Data vol.8(3), pp 1-31, ACM, 2014.

Patterns in Event Sequences

We consider mining informative serial episodes — subsequences allowing for gaps — from event sequence data. We formalize the problem by the Minimum Description Length principle, and give algorithms for selecting good pattern sets from candidate collections as well as for parameter free mining of such models directly from data. More information here.

Bhattacharyya, A & Vreeken, J Efficiently Summarising Event Sequences with Rich Interleaving Patterns. In: Proceedings of the SIAM Conference on Data Mining (SDM), pp 795-803, SIAM, 2017.

We study how to obtain concise descriptions of discrete multivariate sequential data in terms of rich multivariate sequential patterns. We introduce Ditto, and show it discovers succinct pattern sets that capture highly interesting associations within and between sequences. More information here.

Bertens, R, Vreeken, J & Siebes, A Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'16), pp 735-744, ACM, 2016.

Outlier Detection and Description

CompreX discovers anomalies in data using pattern-based compression. Informally, it finds a collection of dictionaries that describe the norm of a database succinctly, and subsequently flags points dissimilar to the norm – those with high compression cost – as anomalies. More information here.

Akoglu, L, Tong, H, Vreeken, J & Faloutsos, C Fast and Reliable Anomaly Detection in Categoric Data. In: Proceedings of ACM Conference on Information and Knowledge Management (CIKM), pp 415-424, ACM, 2012.

Anomalies are often characterised as the absence of patterns. We observe that the co-occurrence of patterns can also be anomalous – many people prefer Coca Cola, while others prefer buy Pepsi Cola, and hence anyone who buys both stands out. We formally introduce this new class of anomalies, and propose UpC, an efficient algorithm to discover these anomalies in transaction data. More information here.

Bertens, R, Vreeken, J & Siebes, A Efficiently Discovering Unexpected Pattern-Co-Occurrences. In: Proceedings of the SIAM International Conference on Data Mining (SDM), pp 126-134, SIAM, 2017.

Matrix Factorisation

Stijl mines descriptions of ordered binary data. We model data hierarchically with noisy tiles - rectangles with significantly different density than their parent tile. To identify good trees, we employ the Minimum Description Length principle, and give an algorithm for mining optimal sub-tiles in just O(nmmin(n,m)) time. More information here.

Tatti, N & Vreeken, J Discovering Descriptive Tile Trees by Fast Mining of Optimal Geometric Subtiles. In: Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), pp 9-24, Springer, 2012.

Boolean Matrix Factorization has many desirable properties, such as high interpretability and natural sparsity. However, no method for selecting the correct model order has been available. We propose to use the Minimum Description Length principle, and show that besides solving the problem, this well-founded approach has numerous benefits, e.g., it is automatic, does not require a likelihood function, and, as experiments show, is highly accurate. More information here.

Miettinen, P & Vreeken, J mdl4bmf: Minimal Description Length for Boolean Matrix Factorization. Transactions on Knowledge Discovery from Data vol.8(4), pp 1-30, ACM, 2014.

Graph Mining

Visualizing large graphs often results in excessive edges crossings and overlapping nodes. We propose Facets, a new scalable approach for adaptively exploring large million-node graphs from a local perspective, guiding them to focus on nodes and neighborhoods that are most subjectively interesting. More information here.

Pienta, R, Lin, Z, Kahng, M, Vreeken, J, Talukdar, PP, Abello, J, Parameswaran, G & Chau, DH AdaptiveNav: Adaptive Discovery of Interesting and Surprising Nodes in Large Graphs. In: Proceedings of the IEEE Conference on Visualization (VIS), IEEE, 2015.

With CulT, we propose a method to reconstruct an epidemic over time, or, more general, reconstructing the propagation of an activity in a network. More information here.

Rozenshtein, P, Gionis, A, Prakash, BA & Vreeken, J Reconstructing an Epidemic over Time. In: Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp 1835-1844, ACM, 2016.

Measuring the difference between data mining results is an important open problem in exploratory data mining. We discuss an information theoretic approach for measuring how much information is shared between results, and give a proof of concept for binary data. More information here.

Koutra, D, Kang, U, Vreeken, J & Faloutsos, C VoG: Summarizing and Understanding Large Graphs. In: Proceedings of the SIAM International Conference on Data Mining (SDM), pp 91-99, SIAM, 2014.

Suppose we are given a large graph in which, by some external process, a handful of nodes are marked. What can we say about these nodes? Are they close together in the graph? or, if segregated, how many groups do they form? We approach this problem by trying to find simple connection pathways between sets of marked nodes — using MDL to identify the optimal result. We propose the efficient dot2dot algorithm for approximating this goal. More information here.

Akoglu, L, Vreeken, J, Tong, H, Chau, DH, Tatti, N & Faloutsos, C Mining Connection Pathways for Marked Nodes in Large Graphs. In: Proceedings of the SIAM International Conference on Data Mining (SDM), pp 37-45, SIAM, 2013.

Dependencies

Given a database and a target attribute, we are after telling whether there exists a functional, or approximately functional dependency of the target on any set of other attributes in the data, to do so efficiently, as well as reliably, without bias to sample size or dimensionality. To this end we propose the Dora algorithm. More information here.

Mandros, P, Boley, M & Vreeken, J Discovering Reliable Approximate Functional Dependencies. In: Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp 355-363, ACM, 2017.

We provide a general theory on correlation, without making any such assumptions. Simply put, we propose correlation by compression. To this end, we propose two correlation measures based on solid information theoretic foundations, i.e. Kolmogorov complexity, and show how to instantiate these for discrete data. More information here.

Budhathoki, K & Vreeken, J Correlation by Compression. In: Proceedings of the SIAM Conference on Data Mining (SDM), SIAM, 2017.

Discovering whether a subspace is correlated is a core task in data mining. For practical use, such a measure should be universal in the sense that it captures correlation in subspaces of any dimensionality and allows to meaningfully compare correlation scores across different subspaces. To this end we propose UdS, an efficient non-parametric multivariate non-linear dependency measure. More information here.

Nguyen, H-V, Mandros, P & Vreeken, J Universal Dependency Analysis. In: Proceedings of the SIAM International Conference on Data Mining (SDM), pp 792-800, SIAM, 2016.

Correlation analysis is one of the key elements of data mining, but many methods are limited to either linear or pairwise correlations. We propose mac, a non-parametric, multivariate and non-linear correlation measure based on maximal correlation analysis. More information here.

Nguyen, H-V, Müller, E, Vreeken, J & Böhm, K Multivariate Maximal Correlation Analysis. In: Proceedings of the International Conference on Machine Learning (ICML), pp 775-783, JMLR: W&CP vol.32, 2014.

How can we quantify the difference between two datasets, without having to assume a distribution? We formalise the well-known Jensen-Shannon divergence using cumulative distribution funtions. cjs allows us to calculate divergences directly and efficiently from data without the need for estimation. More information here.

Nguyen, H-V & Vreeken, J Non-Parametric Jensen-Shannon Divergence. In: Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), pp 173-189, Springer, 2015.

Discretization is the transformation of continuous data into discrete bins. The key question is how to discretize data such that multivariate associations and patterns are preserved. That is exactly what ipd does. More information here.

Nguyen, H-V, Müller, E, Vreeken, J & Böhm, K Unsupervised Interaction-Preserving Discretization of Multivariate Data. Data Mining and Knowledge Discovery vol.28(5), pp 1366-1397, Springer, 2014.

A good first impression of a dataset is paramount to how we proceed our analysis. We discuss mining high-quality high-level descriptive summaries for binary and categorical data. Our approach builds summaries by clustering attributes that strongly correlate, and uses the Minimum Description Length principle to identify the best clustering. More information here.

Mampaey, M & Vreeken, J Summarizing Categorical Data by Clustering Attributes. Data Mining and Knowledge Discovery vol.26(1), pp 130-173, Springer, 2013.