The information on basis is still not reliably correct. Please refer to the information on here, and, if you have questions, write an email to Laura Bülte or Dr. Aurora Rossi.

The number of participants in this lab is limited. If you would like to participate, please write an informal application email to Dr. Aurora Rossi.

Please mention the following:

• Your previous experience with graph algorithms.
  
• A list of the algorithm-related courses you have attended.
  
• Your previous experience with the practical implementation of algorithms.
  
• The programming languages you are proficient in.

This laboratory offers a research-oriented environment focused on the design, implementation, analysis, and improvement of advanced graph algorithms.
The proposed topics include graph similarity (e.g., the graph isomorphism problem and graph edit distance) and centrality measures (betweenness and closeness centralities) using classical algorithms, integer linear programming (ILP) formulations, as well as machine learning–based approaches.
Students will work on analyzing algorithmic limitations, identifying performance bottlenecks, and proposing concrete improvements. They will engage in the development of reproducible scientific software using the Julia language, chosen for its high-performance capabilities in scientific computing. The course emphasizes a deep understanding of algorithms, memory management, and code optimization.
Students will also have the opportunity to contribute to the graph ecosystem of the Julia Programming Language, in particular Graphs.jl, GraphsOptim.jl, and GraphNeuralNetworks.jl

At the end of the semester, you will need to hold a presentation and hand in a lab report on your topic, algorithm(s) and implementation. Both will be graded.

• Deep understanding of fundamental graph algorithms.
  
• Ability to implement graph algorithms or learning models, with attention to memory management and computational efficiency.
  
• Capability to analyze existing state-of-the-art methods and improve them by identifying their limitations
• Evaluation of algorithmic performance and correctness.
  
• Experience with version control and collaborative development (Git, GitHub)
  
• Ability to write clear, reusable, and maintainable code following best practices in coding conventions, documentation, and testing.
  
• Understanding of how scientific software evolves through open-source community contributions.
  

• Enhancing Graph Edit Distance Computations: Stronger and Orientation-based ILP Formulations
  
• Computing Graph Edit Distance via Neural Graph Matching
  
• KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
  
• ABCDE: Approximating Betweenness-Centrality ranking with progressive DropEdge
  
• Tighter Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
  
• How powerful are graph neural networks?
  
• A Path Following Algorithm forthe Graph Matching Problem
  
• Kissing to Find a Match: Efficient Low-Rank Permutation Representation
  
• Bootstrap Learning for Combinatorial ALignment with Sequential GNNs
  

_{DozentInnen: Mutzel, Rossi, Bülte}