Non-negative Matrix Factorization (NMF) is an intensively used technique for obtaining parts-based, lower dimensional and non-negative representation. Researchers in biology, medicine, pharmacy and other fields often prefer NMF over other dimensionality reduction approaches (such as PCA) because the non-negativity of the approach naturally fits the characteristics of the domain problem and its results are easier to analyze and understand. Despite these advantages, obtaining exact characterization and interpretation of the NMF’s latent factors can still be difficult due to their numerical nature. Rule-based approaches, such as rule mining, conceptual clustering, subgroup discovery and redescription mining, are often considered more interpretable but lack lower-dimensional representation of the data. We present a version of the NMF approach that merges rule-based descriptions with advantages of part-based representation offered by the NMF. Given the numerical input data with non-negative entries and a set of rules with high entity coverage, the approach creates the lower-dimensional non-negative representation of the input data in such a way that its factors are described by the appropriate subset of the input rules. In addition to revealing important attributes for latent factors, their interaction and value ranges, this approach allows performing focused embedding potentially using multiple overlapping target labels.

Abstract Differential privacy provides a strong form of privacy and allows preserving most of the original characteristics of the dataset. Utilizing these benefits requires one to design specific differentially private data analysis algorithms. In this work, we present three tree-based algorithms for mining redescriptions while preserving differential privacy. Redescription mining is an exploratory data analysis method for finding connections between two views over the same entities, such as phenotypes and genotypes of medical patients, for example. It has applications in many fields, including some, like health care informatics, where privacy-preserving access to data is desired. Our algorithms are the first tree-based differentially private redescription mining algorithms, and we show via experiments that, despite the inherent noise in differential privacy, it can return trustworthy results even in smaller datasets where noise typically has a stronger effect.

Redescription mining aims at finding subsets of instances that can be re-described, characterized in multiple ways, using one or more disjoint sets of attributes that describe some set of instances. Current redescription mining algorithms either work with tabular data or with relational data — where binary relations between objects are used which allow representing descriptions as graphs. In this work, we propose novel type of redescription mining methodology that allows using tabular data in combination with background network information, where nodes of a network are instances in the tabular data. Background information is used to locate subsets of instances with some desired network property whereas tabular data are used to re-describe such interesting subsets. Methodology can be classified as constraint-based redescription mining, where we allow for a large variety of complex network-based soft constraints. The proposed framework is extensible, thus any network-related measure can be used to localize subsets of instances of interest. In addition, different types of network such as undirected, directed graphs, graph sequences or multiplex can be used as a background information. We demonstrate the applicability of the proposed framework on three use-case datasets involving country trade networks, biological (gene spatial) networks and social networks. The experimental evaluation demonstrates that the proposed approach outperforms existing, general redescription mining approaches with respect to intensity of network properties of the re-described instances without loss of accuracy, mostly even improving redescription accuracy.