- informatik-vortraege - lists.rwth-aachen.de

Einladung Informatik-Oberseminar Tim Seppelt
by Tim Seppelt 07 Nov '24

07 Nov '24

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 29. November 2024, 11.00 Uhr Ort: Raum 9222, Gebäude E3, Informatik-Zentrum Referent: Tim Seppelt, MASt Lehrstuhl Informatik 7 Thema: Homomorphism Indistinguishability Abstract: Two graphs/G/ and/H/ are homomorphism indistinguishable over a class of graphs 𝓕 if, for all graphs/F/ ∊ 𝓕, the number of homomorphisms from/F/ to/G/ is equal to the number of homomorphisms from/F/ to/H/. In 1967, Lovász showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over the class of all graphs. Subsequently, many graph isomorphism relaxations such as quantum isomorphism, spectral, and logical equivalences have been characterised as homomorphism indistinguishability relations over certain graph classes. Thereby, homomorphism indistinguishability connects seemingly disparate fields such as quantum information, finite model theory, and machine learning. This thesis explores three themes: We first review the plenitude of *characterisations* of graph isomorphism relaxations as a homomorphism indistinguishability relation. Focusing on integer programming relaxations for graph isomorphism, we prove that the feasibility of each level of the Sherali–Adams and Lasserre hierarchies is characterised as homomorphism indistinguishability relations. These results, which are derived using (bi)labelled graphs and homomorphism tensors, shed light on the distinguishing power of these hierarchies. In particular, we determine the precise number of Sherali–Adams levels necessary such that their feasibility guarantees the feasibility of a given Lasserre level. Abstracting from the wealth of homomorphism indistinguishability characterisations, we embark on a more principled study of homomorphism indistinguishability investigating the distinguishing power and the complexity of homomorphism indistinguishability relations over minor-closed graph class. The homomorphism distinguishing*closure* cl(𝓕) of a graph class 𝓕 is the central notion for studying the distinguishing power of homomorphism indistinguishability relations. It is defined as the maximal graph class whose homomorphism indistinguishability relation coincides with the one of 𝓕. Roberson conjectured that every minor-closed union-closed graph class 𝓕 is homomorphism distinguishing closed, i.e. cl(𝓕) = 𝓕. We confirm Roberson's conjecture, which is generally wide open, for further graphs classes and prove unconditionally that if 𝓕 is minor-closed then so is cl(𝓕). Lastly, we investigate the*complexity* of deciding whether two graphs are homomorphism indistinguishable over a fixed graph class. For infinite graph classes, this problem is a priori not even decidable. In stark contrast to this, we show that, over every minor-closed graph class of bounded treewidth, homomorphism indistinguishability can be decided in randomised polynomial time. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0

Einladung: Informatik-Oberseminar Jan Tönshoff
by Tönshoff, Jan 15 Oct '24

15 Oct '24

+*********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +*********************************************************************** Zeit: Montag, 4. November 2024, 14:30 Uhr Ort: Raum 9222 (Informatikzentrum E3, Ahornstraße 55) Referent: Jan Martin Tönshoff, M.Sc. Lehrstuhl für Logik und Theorie diskreter Systeme (Informatik 7) Thema: Deep Learning on Graphs: Developing and Understanding Neural Architectures for Structured Data Abstract: Graph Neural Networks (GNNs) have recently emerged as a powerful class of deep learning architectures that can directly learn from graph-structured data. Such data naturally occurs in a wide range of structurally rich learning domains, such as computational chemistry or social network analysis. This thesis aims to study both practical and theoretical aspects of GNNs, with a focus on understanding their capabilities for solving hard learning tasks, exploring new directions for GNN architecture design, and understanding the relative strengths and weaknesses of commonly used models. In this context, we present our main research contributions: Firstly, we propose a GNN-based approach for learning heuristics for Constraint Satisfaction Problems (CSPs) through a general graph representation and neural architecture. Using reinforcement learning, we show that this approach can learn powerful search algorithms, achieving superior performance compared to prior neural methods and being competitive with classical solvers on a range of complex combinatorial problems. Secondly, we examine a novel GNN architecture based on 1D convolutions on sequential features constructed from random walks. We analyze the expressivity of this approach and prove it to be incomparable to the Weisfeiler-Leman hierarchy and many common GNN architectures. The model is further shown to achieve strong empirical performance across various tasks, suggesting a new direction for GNN architecture design beyond traditional message passing. Thirdly, we compare popular GNNs in the context of capturing long-range dependencies in graphs. Through an empirical re-evaluation of commonly used benchmark datasets, we show that standard GNNs based on message passing perform better than previously reported. A theoretical comparison between Graph Transformers and GNNs with Virtual Nodes further shows that neither architecture subsumes the other in terms of uniform expressivity, highlighting the need to consider a wide range of architectures for specific learning tasks. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0

Oberseminar Sebastian Hueber
by Hueber, Sebastian 15 Oct '24

15 Oct '24

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Mittwoch, 30. Oktober 2024, 14:00 Uhr Ort: Im Süsterfeld 9, 52072 Aachen, Raum 273 Referent: Sebastian Hueber M.Sc. Lehrstuhl Informatik 10 Thema: Using Facial Tracking for Expressive Mobile Device Interactions Abstract: For four decades, user interfaces have been mainly designed for pointing input, either with a mouse or a touchscreen. Pointing input abstracts from the human to a location on the screen. Especially visual cues that make human-to-human communication effective – like eye contact or head nodding – are ignored in this abstraction. Mobile devices, in particular, suffer from the limits of pointing input, as users cannot comfortably reach everything on the screen when using the device one-handedly. We present implicit and explicit usages of facial tracking to make mobile interactions more expressive and ergonomic. We show the advantages of eye tracking using three interaction techniques. First, our Attentive Notifications remove occlusion issues and accidental activations in mobile interfaces. They determine a suitable screen edge for displaying notifications by blocking the area around the user’s gaze at the moment of notification delivery. Second, we show that eye tracking can enhance the perception of content in augmented reality with our User-Aware Rendering. This technique provides enhanced depth perception with good performance in scene exploration. Third, interfaces can exploit that gaze input can reach anything nearby. Our GazeConduits concept fosters collaboration in ad-hoc multi-device environments. This enables users to interact with devices or meeting collaborators by looking at them. However, eye tracking often comes with accuracy issues, especially when people are moving, and suffers from the Midas touch problem. To overcome these challenges, two of our interaction techniques use head tracking instead. We present a Head + Touch controlled cursor that increases the thumb’s reach during one-handed smartphone use. This significantly reduces the overhead of touch-based reachability techniques to under 100 ms. With our Headbang technique, menu selections are also faster than with touch input. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0

[sekretariate] Einladung: Informatik-Oberseminar Bahare Salmani
by Elke Ohlenforst 02 Oct '24

02 Oct '24

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 11. Oktober 2024, 15:30 Uhr Ort: Raum 5053.2 (großer B-IT-Hörsaal), Informatikzentrum, E2, Ahornstr. 55 Referentin: Bahare Salmani Barzoki, M.Sc. Lehrstuhl für Softwaremodellierung und Verifikation (Informatik 2) Thema: Probabilistic Model Checking and Parameter Tuning for Bayesian Networks Abstract: Probabilistic reasoning is a key to handling uncertainties and making decisions based on partial observations. Bayesian networks (BNs) are popular probabilisticgraphical models in probabilistic decision-making and AI and have a wide range of applications, including machine learning, medicine, gene regulatory networks, and robotics. They combine the notions from probability theory and graph theory and enablea succinct representation of joint probability distributions.A Bayesian network is composed of a directed acyclic graph over a set of random variables and a set of conditional probability tables ---CPTs for short. The primary task in Bayesian networks is probabilistic inference, that is, to compute a conditional probability of a joint valuation for a subset of random variables given an observation. Probabilistic model checking is a field in computer science that isfocusedon analyzing stochastic systems with respect toa set of formally defined properties. The stochastic systems are typically Markov models, and the properties of interest are probabilistic extensions of LTL of CTL. The properties are mostly reducedto a pivotal task, computing reachability probabilities: whatis the probability of reaching a set of target states? Recent advancements in the field consider the parametric extensions of the Markov models, where a subset of the probabilities in the model are unknown and target various synthesis problems including/feasibility checking/: is there a satisfying instantiation that satisfies the given constraint?,/region verification/: are all instantiations in a /region/ satisfy the given constraint, and /parameter space partitioning/: split the entire n-dimensional parameter space to sets of satisfying, rejecting, and unknown subregions w.r.t. the given constraint. In this dissertation, we present a new approach based on /probabilistic model checking/ for inference and parameter tuning in Bayesian networks. The dissertation is categorizedinto two main settings: the /non-parametric/ and the /parametric/. In the non-parametric setting,we focus on the classical Bayesian networks, where the model is fully specified.We present mappings from Bayesian networks to discrete-time Markov chains and mathematically reduce performing conditional inference in the BN to computing reachability probabilities in Markov chains. Thisenables the use of state-of-the-art algorithms for computing reachability probabilities and the optimization techniques thereof, e.g., bisimulation minimization for exact inference in BNs. We exploit the explicit and symbolic methods from probabilistic model checking and empirically evaluate our framework for Bayesian inference against the state-of-the-art /weighted model counting. /In the parametric setting,we define /parametric Bayesian networks (pBNs)/, where a subset of CPT entries are unknown polynomials rather than concrete probabilities.We build upon the synthesis techniques for parametric Markov chains and address problems /sensitivity analysis/, /ratio/difference parameter tuning/ from the BN literature, and /parameter space partitioning/from pMC literature. Finally, we focus on the problem /minimal-distanceparameter tunin/g, where the objective is to find the instantiationu for the unknown parameters that satisfy the constraint of interest while minimally deviating from the original instantiation u_0 in an original reference model. The motivation is to minimally disturb the statistical information in the original model. Our detailed experimental evaluations indicate that our parameter synthesis techniques can treat parameter synthesis for Bayesian networks (with hundreds of unknown parameters) that go beyond the capabilities of the existing techniques. We lift the severe restrictions in the literature on the number of unknown parameters, the global dependencies between the parameters, and the form of obtained solutions. ------------------------------------------------------------------------ Es laden ein: die Dozentinnen und Dozenten der Informatik _______________________________________________ informatik-sekretariate Mailingliste -- informatik-sekretariate(a)lists.rwth-aachen.de Um den Newsletter abzubestellen, senden Sie bitte eine E-Mail an informatik-sekretariate-leave(a)lists.rwth-aachen.de

1 0

[Informatik-assistenten] Einladung Informatik-Oberseminar Lukas Netz
by Netz, Lukas 26 Sep '24

26 Sep '24

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Montag, 07.10.2024, 15:00 Uhr Ort: Informatikzentrum der RWTH Aachen University, Gebäude E3, 2. Etage, Raum 9222 Referent: Lukas Netz, M.Sc. Lehrstuhl für Software Engineering Thema: Model-Driven Method for the Development of Full-Size Web-Based Information Systems Abstract: The implementation of information systems poses a variety of challenges for developers and requires a large number of experts from different application domains. This work presents a methodology in the area of generative model-driven development (MDD) for web-based information systems. The methodology consists of three basic building blocks: LLM4CD, CD2GUI and MontiGem. The first building block LLM4CD is based on generative artificial intelligence (LLMs) and transforms natural language requirements and domain descriptions into class diagrams in CD4A notation. The second building block CD2GUI uses these class diagrams and derives models for user interfaces in GUI-DSL notation. The last building block is MontiGem. It uses both types of models to generate a data-centric information system. An important part of this work is the adaptability of the generated artifacts, this mainly concerns the possibility for modelers to adapt the models generated by the AI and CD2GUI, and to adapt and extend the code generated by MontiGem without having to edit the generated code or models directly. This makes iterative work with the methodology possible without discarding adapted code or adapted models. It is precisely this adaptability that facilitates the transition from an underspecified modeled software prototype to a full-size model-driven information system that can be actively used in industry. In addition to the three building blocks, this thesis also presents the domain-specific modeling languages GUI-DSL and CD4A. The methodology is evaluated and discussed both in parts and as a whole. The practical applicability of the methodology is demonstrated using the case study MaCoCo, an information system used by RWTH Aachen University, which serves as a robust benchmark for the validation of the methodology. Es laden ein: die Dozentinnen und Dozenten der Informatik _______________________________________________ Informatik-assistenten mailing list -- informatik-assistenten(a)lists.rwth-aachen.de<mailto:informatik-assistenten@lists.rwth-aachen.de> To unsubscribe send an email to informatik-assistenten-leave(a)lists.rwth-aachen.de<mailto:informatik-assistenten-leave@lists.rwth-aachen.de> https://lists.rwth-aachen.de/postorius/lists/informatik-assistenten.lists.r…

1 0

Einladung: Informatik-Oberseminar Jan Böker
by Jan Böker 17 Sep '24

17 Sep '24

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 27. September 2024, 10:00 Uhr Ort: Raum 9222 (Informatikzentrum E3, Ahornstraße 55) Referent: Jan Wilhelm Böker, M.Sc. Lehrstuhl für Logik und Theorie diskreter Systeme (Informatik 7) Thema: Structural Similarity of Graphs: Graphons and Homomorphism Densities Abstract: The abundance of graph-structured data in domains like bio-informatics has led to the popularity of both graph embeddings and graph neural networks as techniques for machine learning on graphs. Advancements in this field, however, are mostly driven by intuition and empiricism, and there is a lack of a theoretical foundation that explains both the success and the limits of these techniques. The use of tree homomorphism counts is appealing in order to define graph embeddings that not only are well-founded theoretically but also efficiently computable. Graphons emerged as the limit objects in the theory of dense graph limits and are a generalization of graphs to measurable functions. We develop a framework for graphon similarity based on iterated degree measures, which were recently introduced by Grebík and Rocha in a generalization of Color Refinement, a popular heuristic algorithm for graph isomorphism testing, to graphons. We show that, besides tree homomorphism densities, also message-passing graph neural networks integrate into this framework. We integrate a metric variant of Color Refinement into our framework. Furthermore, we introduce the tree cut distance, a variant of the cut distance from the theory of dense graph limits. Our framework allows us to prove that these four concepts all yield the same notion of similarity of graphons. In the special case of graphs, our framework gives us four similarity measures that are not only equivalent but can also be computed efficiently. We also briefly study the computational complexity of the homomorphism reconstructability problem, which asks whether a given vector of natural numbers can actually be realized as homomorphism counts to a graph. We show that this problem is NP-hard even in a severely restricted form. The k-dimensional Weisfeiler-Leman algorithm is a generalization of Color Refinement to higher dimensions. To initiate the development of a higher-dimensional variant of our framework for graphon similarity, we generalize this algorithm and various of its characterizations to graphons and prove their equivalence. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0

Einladung: Informatik-Oberseminar Johannes Theissen-Lipp geb. Lipp
by Theissen-Lipp, Johannes 13 Sep '24

13 Sep '24

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Mittwoch, 25. September 2024, 11.00 Uhr Ort: COMSYS E3/ Raum 9222, Ahornstraße 55, 52074 Aachen (2359/222, 2.OG) Referent: Johannes Theissen-Lipp M.Sc. Computer Science 5 – Information Systems and Databases Thema: Semantic Foundations of Dataspaces Abstract: Digital transformation is rapidly reshaping industries, organizations, and societies around the world, driven by the exponential growth of data from the Internet and the Web. This data, encompassing both open and closed resources, drives innovation and provides competitive advantages. However, there is a growing demand for data sovereignty, where individuals and organizations control their data throughout its lifecycle. Initiatives such as dataspaces, funded with €4-6 billion in Europe, and the Internet of Production focus on data autonomy and integration, but interoperability and common understanding remain critical challenges. The fields of Semantic Web technologies and FAIR data provide frameworks for addressing these challenges. These semantic technologies enable seamless data exchange and meaningful interpretation to maximize the potential of data, yet they are not sufficiently utilized in dataspaces. This thesis explores the semantic foundations of dataspaces, aiming to integrate semantic technologies to improve data interoperability and facilitate common understanding among stakeholders. It also advances semantic technologies to enhance their impact. This work proposes new concepts, principles, best practices, and solutions to improve data management in dataspaces. The key contributions of this thesis include: - A Tailored Data Lifecycle Model for Dataspaces: This model addresses the unique challenges and requirements of dataspaces, ensuring a streamlined and structured approach to managing data and metadata throughout their lifecycle. - Principles of Information Models: These models define a common core in dataspaces, providing a structured representation of data, services, participants, and interactions, and serving as a foundation for data sovereignty and interoperability mechanisms. - Extended Data Access Principles: These principles cover various types of heterogeneity, improving data accessibility by managing resource constraints, handling dynamic data changes, and providing rich metadata to increase the quantity and quality of information in dataspaces. - Methods for Improving Common Domain Understanding: This includes techniques for identification, best practices for vocabulary development, involvement of non-experts, effective recommendation systems, evolution of semantic information over time, and improved validation techniques to enhance data interoperability and (re)use in dataspaces. By combining these contributions, this thesis confidently integrates semantic technologies into dataspaces. This integration enhances data and service interoperability and facilitates common understanding within these environments, promoting proper data management and reuse throughout the data lifecycle. Our work provides valuable insights into the effective management of information within the digital ecosystem of dataspaces, contributing to the advancement of knowledge in today's data-driven digital transformation. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 1

Einladung: Informatik-Oberseminar Marco Lutz geb. Grochowski
by Grochowski, Marco 02 Sep '24

02 Sep '24

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Dienstag, 10. September 2024, 10.00 Uhr Ort: Im Süsterfeld 9, 52072 Aachen, Raum 259 Referent: Marco Lutz geb. Grochowski M.Sc. Informatik 11 - Embedded Software Thema: Test Suite Generation and Augmentation for Reconfigurable Industrial Control Software in the Internet of Production Abstract: With the advent of Industry 4.0 and the digitally networked factory, cyber-physical production systems (CPPSs) are reconfigured frequently along their life cycle to adapt to changing customer requirements or market demands. Such reconfigurations are not limited to the hardware but also affect the software of the programmable logic controllers (PLCs) driving these plants. While verification and testing are two techniques capable of alleviating the risk of introducing errors in production code, it is no longer sufficient to rely only on the results obtained by these methods during the commissioning of the CPPS. Even minor incremental reconfigurations to the PLC’s software during the operational phase of the life cycle may introduce regressions that can be quickly overlooked by a developer and therefore need to be reverified. The goal of this thesis is to provide a “push button” analysis for generating test cases after a static reconfiguration. The generated test cases can be injected and monitored during maintenance or virtual commissioning to observe the impact of reconfiguration on the CPPS by the developer. In order to reduce redundancy in test suite generation (TSG) after a structural reconfiguration to the PLC software, symbolic summaries of specific parts of the program should be cached and reused to benefit subsequent analysis. While automatic TSG is an established technique used to generate test suites adhering to structural coverage metrics of PLC software, the generated test suite might not anymore be adequate enough with regards to the coverage metric to ensure the absence of regressions. An indispensable part of regression testing (RT) is test suite augmentation (TSA), which guides the TSG toward the reconfigured behavior and increases the chances of deriving difference-revealing test cases which expose behavioral differences between the program and its reconfigured version. The derivation of new test cases is required to uncover potential regressions after a reconfiguration. To this end, the contributions of this thesis include * heuristics for the scalability of the existing TSG for PLC software, * the reuse of symbolic summaries during TSG of reconfigured PLC software, * and the concept of executing the old and new version of a reconfigured PLC software in one unified program version during TSA. These contributions are evaluated on selected domain-specific benchmarks of varying difficulty, such as the PLCopen Safety suite and the Pick and Place Unit (PPU). Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0

Einladung zum Informatik-Kolloquium von Prof. Dr. Paula Herber
by Völker, Marcus 30 Aug '24

30 Aug '24

+********************************************************************** * * * Einladung * * * * Informatik-Kolloquium * * * +********************************************************************** Zeit: Dienstag, 10. September 2024, 14.00 Uhr Ort: Raum 9222, Gebäude E3, Ahornstr. 55 Referentin: Prof. Dr. Paula Herber University of Münster Title: Formal Verification of Cyber-physical Systems using Domain-specific Abstractions Abstract: Cyber-physical systems have become ubiquitous in our daily lives, and their complexity continually evolves to unprecedented levels. In addition to their heterogeneity and interaction with a physical environment, we see a tremendous increase in the use of learning to make autonomous decisions in dynamic environments. These developments pose significant challenges for ensuring the safety and reliability of cyber-physical systems. Formal methods have the potential to guarantee crucial safety properties under all circumstances, but are incredibly expensive and severely suffer from scalability issues. In this talk, I will summarize some of our recent efforts towards reusable specification and more scalable verification of cyber-physical systems using domain-specific abstractions. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0

Einladung Informatik-Oberseminar Yingbo Gao, 28. August 2024
by Stephanie Jansen 22 Aug '24

22 Aug '24

********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * *********************************************************************** Zeit: Mittwoch, 28 August 2024, 15:30 Uhr Ort: Raum 9222, E3, Informatikzentrum Zoom: https://rwth.zoom-x.de/j/66261562709?pwd=2driMW8j0cRJLiYFWNJRqRp4Lya80Z.1 Meeting-ID: 662 6156 2709 Kenncode: 337848 Referent: Yingbo Gao, M.Sc. (Lehrstuhl Informatik 6) Thema: Language Modeling and Machine Translation: Improvements in Training and Modeling Abstract: Substantial improvements in language modeling and machine translation have been achieved since the wide adoption of artificial neural networks. In this talk, we discuss three directions related to training and modeling in neural language modeling and neural machine translation. First, sampling-based training criteria are investigated in order to speed up the training of neural language models with large vocabularies. Second, label smoothing, input smoothing as well as multi-agent training are studied to improve the generalization of neural machine translation models. Finally, a language modeling approach for machine translation is proposed to simplify the architecture of existing translation models. Es laden ein: die Dozentinnen und Dozenten der Informatik -- Stephanie Jansen Faculty of Mathematics, Computer Science and Natural Sciences Chair of Computer Science 6 ML - Machine Learning and Reasoning RWTH Aachen University Theaterstraße 35-39 D-52062 Aachen Tel: +49 241 80-21601 sek(a)ml.rwth-aachen.de www.hltpr.rwth-aachen.de

1 0