publications

List of Publications and Preprints by Tom Hanika

2019

• Borchmann, D., Hanika, T., Obiedkov, S.: Probably approximately correct learning of Horn envelopes from queries. Discrete Applied Mathematics. (2019).

  URL

  We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain.
• Hanika, T., Kibanov, M., Kropf, J., Laser, S.: Ich denke, es ist wichtig zu verstehen, warum die Netzwerkanalyse jetzt populär und besonders interessant für die Forschung geworden ist. In: Kropf, J. and Laser, S. (eds.) Digitale Bewertungspraktiken. p. 165--188. Springer (2019).

  URL
• Hanika, T., Marx, M., Stumme, G.: Discovering Implicational Knowledge in Wikidata, http://arxiv.org/abs/1902.00916, (2019).

  URL

  Knowledge graphs have recently become the state-of-the-art tool for representing the diverse and complex knowledge of the world. Examples include the proprietary knowledge graphs of companies such as Google, Facebook, IBM, or Microsoft, but also freely available ones such as YAGO, DBpedia, and Wikidata. A distinguishing feature of Wikidata is that the knowledge is collaboratively edited and curated. While this greatly enhances the scope of Wikidata, it also makes it impossible for a single individual to grasp complex connections between properties or understand the global impact of edits in the graph. We apply Formal Concept Analysis to efficiently identify comprehensible implications that are implicitly present in the data. Although the complex structure of data modelling in Wikidata is not amenable to a direct approach, we overcome this limitation by extracting contextual representations of parts of Wikidata in a systematic fashion. We demonstrate the practical feasibility of our approach through several experiments and show that the results may lead to the discovery of interesting implicational knowledge. Besides providing a method for obtaining large real-world data sets for FCA, we sketch potential applications in offering semantic assistance for editing and curating Wikidata.

2018

• Hanika, T., Zumbrägel, J.: Towards Collaborative Conceptual Exploration. In: Chapman, P., Endres, D., and Pernelle, N. (eds.) ICCS. pp. 120-134. Springer (2018).

  URL
• Doerfel, S., Hanika, T., Stumme, G.: Clones in Social Networks. CoRR. abs/1802.07849, (2018).

  URL

  It is well known that any bipartite (social) network can be regarded as a formal context $(G,M,I)$. Therefore, such networks give raise to formal concept lattices which can be investigated utilizing the toolset of Formal Concept Analysis (FCA). In particular, the notion of clones in closure systems on $M$, i.e., pairwise interchangeable attributes that leave the closure system unchanged, suggests itself naturally as a candidate to be analyzed in the realm of FCA based social network analysis. In this study, we investigate the notion of clones in social networks. After building up some theoretical background for the clone relation in formal contexts we try to find clones in real word data sets. To this end, we provide an experimental evaluation on nine mostly well known social networks and provide some first insights on the impact of clones. We conclude our work by nourishing the understanding of clones by generalizing those to permutations of higher order.
• Hanika, T., Schneider, F.M., Stumme, G.: Intrinsic dimension of concept lattices. CoRR. abs/1801.07985, (2018).

  URL

  Geometric analysis is a very capable theory to understand the influence of the high dimensionality of the input data in machine learning (ML) and knowledge discovery (KD). With our approach we can assess how far the application of a specific KD/ML-algorithm to a concrete data set is prone to the curse of dimensionality. To this end we extend V.~Pestov's axiomatic approach to the instrinsic dimension of data sets, based on the seminal work by M.~Gromov on concentration phenomena, and provide an adaptable and computationally feasible model for studying observable geometric invariants associated to features that are natural to both the data and the learning procedure. In detail, we investigate data represented by formal contexts and give first theoretical as well as experimental insights into the intrinsic dimension of a concept lattice. Because of the correspondence between formal concepts and maximal cliques in graphs, applications to social network analysis are at hand.
• Hanika, T., Schneider, F.M., Stumme, G.: Intrinsic dimension and its application to association rules. CoRR. abs/1805.05714, (2018).

  URL

  The curse of dimensionality in the realm of association rules is twofold. Firstly, we have the well known exponential increase in computational complexity with increasing item set size. Secondly, there is a related curse concerned with the distribution of (spare) data itself in high dimension. The former problem is often coped with by projection, i.e., feature selection, whereas the best known strategy for the latter is avoidance. This work summarizes the first attempt to provide a computationally feasible method for measuring the extent of dimension curse present in a data set with respect to a particular class machine of learning procedures. This recent development enables the application of various other methods from geometric analysis to be investigated and applied in machine learning procedures in the presence of high dimension.
• Borchmann, D., Hanika, T., Obiedkov, S.: Probably approximately correct learning of Horn envelopes from queries. CoRR. abs/1807.06149, (2018).

  URL

  We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain.
• Schäfermeier, B., Hanika, T., Stumme, G.: Distances for WiFi Based Topological Indoor Mapping, http://arxiv.org/abs/1809.07405, (2018).

  URL

  For localization and mapping of indoor environments through WiFi signals, locations are often represented as likelihoods of the received signal strength indicator. In this work we compare various measures of distance between such likelihoods in combination with different methods for estimation and representation. In particular, we show that among the considered distance measures the Earth Mover's Distance seems the most beneficial for the localization task. Combined with kernel density estimation we were able to retain the topological structure of rooms in a real-world office scenario.
• Doerfel, S., Hanika, T., Stumme, G.: Clones in Graphs. In: Ceci, M., Japkowicz, N., Liu, J., Papadopoulos, G.A., and Ras, Z.W. (eds.) ISMIS. pp. 56-66. Springer (2018).

  URL
• Hanika, T., Koyda, M., Stumme, G.: Relevant Attributes in Formal Contexts. CoRR. abs/1812.08868, (2018).

  URL
• Felde, M., Hanika, T.: Formal Context Generation using Dirichlet Distributions. CoRR. abs/1809.11160, (2018).

  URL

2017

• Borchmann, D., Hanika, T., Obiedkov, S.: On the Usability of Probably Approximately Correct Implication Bases. In: Bertet, K., Borchmann, D., Cellier, P., and Ferré, S. (eds.) ICFCA. pp. 72-88. Springer (2017).

  URL
• Borchmann, D., Hanika, T.: Individuality in Social Networks. In: Missaoui, R., Kuznetsov, S.O., and Obiedkov, S. (eds.) Formal Concept Analysis of Social Networks. p. 19--40. Springer International Publishing, Cham (2017).

  URL

  We consider individuality in bi-modal social networks, a facet that has not been considered before in the mathematical analysis of social networks. We use methods from formal concept analysis to develop a natural definition for individuality, and provide experimental evidence that this yields a meaningful approach for additional insights into the nature of social networks.

2016

• Borchmann, D., Hanika, T.: Some Experimental Results on Randomly Generating Formal Contexts. In: Huchard, M. and Kuznetsov, S. (eds.) CLA. pp. 57-69. CEUR-WS.org (2016).

  URL
• Atzmueller, M., Hanika, T., Stumme, G., Schaller, R., Ludwig, B.: Social Event Network Analysis: Structure, Preferences, and Reality. Proc. IEEE/ACM ASONAM. IEEE Press, Boston, MA, USA (2016).

  URL