Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Maximal Closed Set and Half-Space Separations in Finite Closure Systems

: Seiffarth, Florian; Horváth, Támas; Wrobel, Stefan


Brefeld, U.:
Machine Learning and Knowledge Discovery in Databases. Proceedings. Pt.I : European Conference, ECML PKDD 2019, Würzburg, Germany, September 16-20, 2019
Cham: Springer Nature, 2020 (Lecture Notes in Artificial Intelligence 11906)
ISBN: 978-3-030-46149-2 (Print)
ISBN: 978-3-030-46150-8 (Online)
ISBN: 978-3-030-46151-5
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) <2019, Würzburg>
Bundesministerium für Bildung und Forschung BMBF (Deutschland)
01/S18038C; ML2R
Deutsche Forschungsgemeinschaft DFG
EXC 2070 390732324
Conference Paper
Fraunhofer IAIS ()
closure systems; half-space separation; binary classification

Motivated by various binary classification problems in structured data (e.g., graphs or other relational and algebraic structures), we investigate some algorithmic properties of closed set and half-space separation in abstract closure systems. Assuming that the underlying closure system is finite and given by the corresponding closure operator, we formulate some negative and positive complexity results for these two separation problems. In particular, we prove that deciding half-space separability in abstract closure systems is NP-complete in general. On the other hand, for the relaxed problem of maximal closed set separation we propose a simple greedy algorithm and show that it is efficient and has the best possible lower bound on the number of closure operator calls. As a second direction to overcome the negative result above, we consider Kakutani closure systems and show first that our greedy algorithm provides an algorithmic characterization of this kind of set systems. As one of the major potential application fields, we then focus on Kakutani closure systems over graphs and generalize a fundamental characterization result based on the Pasch axiom to graph structure partitioning of finite sets. Though the primary focus of this work is on the generality of the results obtained, we experimentally demonstrate the practical usefulness of our approach on vertex classification in different graph datasets.