Solving Graph Theory Problems

Graph theory is a branch of mathematics that studies graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A graph can be directed or undirected, weighted or unweighted. Graphs are one of the prime objects of study in discrete mathematics.

Problems in graph theory include graph or subgraph isomorphism, finding the largest clique in a graph, finding the chromatic number of a graph, finding the shortest path between two vertices, finding the minimum spanning tree of a graph, finding the maximum flow in a graph, etc. Currently, existing classical algorithms can solve these problems effectively. However, these algorithms are not scalable and cannot be applied to large-scaled graphs. In this project, I will explore how to use Deep Learning to solve graph theory problems with targeted large-scaled graphs and applications in drug discovery, social network analysis, etc.

Master’s Thesis

My Master’s thesis focuses on enhancing subgraph isomorphism prediction models to improve scalability and interpretability, particularly for applications in drug design. I introduce xNeuSM, an Explainable Neural Subgraph Matching framework, which leverages Graph Learnable Multi-hop Attention Networks (GLeMA) to dynamically learn attention decay parameters across multiple hops. This approach eliminates reliance on fixed hyperparameters and provides theoretical guarantees on approximation errors. Empirical results on real-world datasets show that xNeuSM has higher accuracy than approximate baselines while achieving query times at least seven times faster than exact algorithms. These advancements make subgraph matching more practical for large-scale molecular analysis in drug discovery.

Master’s thesis PDF: Link
Master’s thesis presentation: Link
Master’s thesis code: Link

Publications

• Duc Q. Nguyen, et al. “10X Faster Subgraph Matching: Dual Matching Networks with Interleaved Diffusion Attention”, In Proceedings of 2023 International Joint Conference on Neural Networks (IJCNN), 2023. [PDF] [Code]
• Duc Q. Nguyen, et al., “Explainable Neural Subgraph Matching With Learnable Multi-Hop Attention,” IEEE Access, vol. 12, pp. 130474–130492, 2024. [PDF] [Code]