Search

The increasing digitization and datification of all aspects of people's daily life, and the consequent growth in the use of personal data, are increasingly challenging the current development and adoption of Machine Learning (ML). First, the sheer complexity and amount of data available in these applications strongly demands for ML algorithms that can be trained directly on complex structures, which can be naturally described by graphs. In fact, graphs inherently capture information about entities, their attributes, and relationships between them. Directly applying ML to graphs relieves domain experts and data scientists from the challenging and time-consuming problem of designing a suitable vector-based data representation used by classical ML techniques. Second, ML algorithms should not only be designed to achieve high technical and functional standards; as the automated decisions provided by these algorithms can have a relevant impact on people's lives, their behavior has to be aligned with the values and principles of individuals and society. This demands for designing automated algorithms that we, as humans, can trust, fulfilling the requirements of fairness, robustness, privacy, and explainability. Third, designing effective ML algorithms requires skills and expertise developed at different levels. This substantially hinders the democratization and widespread availability of such technology for society at large, which in turn demands for improving the level of automatization and systematization of their design process, while also providing guarantees on their performance. For this reason, this paper provides an overview of the current works focused towards learning trustworthily, automatically, and with guarantees on graphs. [ABSTRACT FROM AUTHOR]

From an empirical point of view, the hardness of quantified Boolean formulas (QBFs), can be characterized by the (in)ability of current state-of-the-art QBF solvers to decide about the truth of formulas given limited computational resources. In this paper, we start from the problem of computing empirical hardness markers, i.e., features that can discriminate between hard and easy QBFs, and we end up showing that such markers can be useful to improve our understanding of QBF preprocessors. In particular, considering the connection between classes of tractable QBFs and the treewidth of associated graphs, we show that (an approximation of) treewidth is indeed a marker of empirical hardness and it is the only parameter which succeeds consistently in being so, even considering several other purely syntactic candidates which have been successfully employed to characterize QBFs in other contexts. We also show that treewidth approximations can be useful to describe the effect of QBF preprocessors, in that some QBF solvers benefit from a preprocessing phase when it reduces the treewidth of their input. Our experiments suggest that structural simplifications reducing treewidth are a potential enabler for the solution of hard QBF encodings. [ABSTRACT FROM AUTHOR]