Tag: Bachelor
-
Common Subgraph Problems in Tree-Like Graphs
For two given graphs, G and H, the maximum common subgraph problem (MCS) asks for the largest graph contained in both G and H. An important application occurs in cheminformatics, where the similarity of molecular graphs needs to be quantified. Unfortunately, MCS is NP-hard unless additional constraints regarding the properties of G, H, and the…
-
The Complexity of Computing the Graph Edit Distance
The graph edit distance (GED) quantifies the dissimilarity of two graphs as the minimum cost of a sequence of edit operations turning one graph into the other. The problem complexity depends on the choice of the edit operation costs and the properties of the considered graphs. It has been shown that the classical NP-hard subgraph…
-
Efficient Knowledge Distillation from Graph Neural Networks for Scalable e-Commerce Recommendation Systems
Graph Neural Networks (GNNs) have significantly enhanced the capability of recommendation systems in e-commerce by leveraging collaborative filtering and session-based methodologies. These advancements have demonstrated improved recommendation accuracy by effectively capturing complex user-item interactions within graph structures. However, the deployment of GNN-based systems at scale encounters substantial challenges, primarily due to their computational intensity and…
-
Developing anonymized datasets for Graph Neural Networks
Developing anonymized datasets based on proprietary data for session-based recommendations with Graph Neural Networks (GNNs) is crucial to adhere to GDPR requirements and protect business secrets. Using proprietary data from an industry partner, this thesis will focus on creating a publishable, anonymized dataset that retains the essential characteristics needed for effective session-based recommendation while ensuring…
-
Investigating Factors for Effective Transfer-Learning with Chemical Graphs
Transfer-learning is the process of using pre-trained weights from one-model to make better predictions with another model. In the chemical domain, labeled data is sparse and self-supervised methods using unlabeled data are used to obtain initial weights. While transferring these weights to a fine-tuning model, several questions need to be investigated: Should all layers be…
-
The Importance of Node & Edge features in Chemical Graphs for Molecular Property Prediction
Chemical molecules can be abstracted as graphs where nodes represent atoms and edges represent bonds. Each node is assigned a feature vector containing information about the atom. For example the type of atom (carbon), the number of bonds (eg. 3), etc. However there exists no study that investigates the importance of these features to perform…
-
Exploring the Impact of Floating-Point Arithmetic on the Expressivity of Graph Neural Networks (GNNs)
Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data. However, a largely unexplored area is how numerical errors from floating-point arithmetic affect GNN computations and expressivity—the model’s ability to distinguish between different graph structures. Since GNNs rely on operations like summation to aggregate node embeddings, their performance is impacted by the non-associativity…
-
Learning Graph Edit Costs
The graph edit distance measures the dissimilarity between two graphs based on minimum cost sequences of edit operations that transform one graph into the other. Typically, the user is supposed to define the costs of individual edit operations. This project aims to develop techniques for learning edit costs based on ground-truth graph distances. Requirements: Interest…