Tag: Practical Course
-
Dynamic Orbit Partition
A graph isomorphism is a mapping between the nodes of two graphs that preserves the edges. An automorphism is an isomorphism of a graph to itself. The (non-trivial) automorphisms intuitively represent the symmetries of a graph. Two vertices are considered equivalent if there is an automorphism that maps one vertex to the other. The corresponding…
-
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…
-
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…
-
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…