Tag: Master
-
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…
-
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…
-
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…