Efficient algorithms and implementation for large-scale graph optimisation problems

This project includes two studentships. Two PhD students will be recruited and will be working on the below topic.

Co-funding Company

Huawei Lagrange Mathematics and Computing Research Centre (France)

The Huawei Lagrange Mathematics and Computing Research Centre, established in 2020 in Paris, France, focuses on fundamental research in mathematics and computing. Named after the mathematician Joseph-Louis Lagrange, the centre collaborates with leading academic institutions to advance areas such as optimisation, algorithms, cryptography, and AI theory. It serves as a bridge between theoretical research and practical technological innovation, contributing to Huawei’s global research network.

https://www.huawei.com/en/ 

Supervisory team

University of Edinburgh PI: Dr Liang Zhao -  liang.zhao@ed.ac.uk (School of Informatics)
Personal website: https://www.research.ed.ac.uk/en/persons/liang-zhao/

Abstract

This project focuses on developing efficient algorithms and implementations for large-scale graph optimisation problems by exploiting their inherent sparsity structures and local sub-graph optimisation. Such problems frequently arise in domains like SLAM, machine learning, structure-from-motion, and sensor networks, where scalability and computational efficiency are critical. The research aims to design novel linearisation, factorisation, and incremental updating techniques that leverage structured sparsity to reduce computational complexity while maintaining high accuracy. We will investigate both batch and incremental optimisation, as well as distributed computing frameworks, integrating theoretical insights with practical algorithmic solutions. The outcomes will enable real-time performance on large-scale problems and provide open-source implementations for broader research and industrial use.

Project Background

High dimensional graph optimisation problems arise in various domains, including state estimation, network analysis, and computational biology. Graph optimisation involves estimating a set of variables (e.g., landmark positions, or network states) that minimise a cost function derived from a graph of constraints. The problem is often represented as a factor graph, where nodes correspond to variables, and edges (factors) represent constraints derived from sensor measurements, prior knowledge, or connectivity. The problem is typically solved using nonlinear optimisation techniques like Gauss-Newton, Levenberg-Marquardt, or gradient-based methods.

Although graph optimisation has been studied for decades, there are still challenges when the dimension of the problem is super high, e.g. with multi-million edges and nodes: 1. Computational Scalability; 2. Memory Constraints; 3. Real-Time Computation; 4. Nonlinearity and Convergence Issues; and 5. Graph Sparsity and Connectivity. 

Research Aims

This project aims to develop reliable graph optimisation algorithms which have better convergence property, and efficient solutions and implementations to the super high dimensional graph optimisation when the dimensions of edges/nodes are multi-million.

The graph optimisation-based algorithms proposed in this project will be further optimised to be able to perform on the processers on the required devices with certain computational power and memory consumptions, by exploring the special sparsity structure of the high dimensional graph optimisation problem.

Data and Methodology

Instead of using general sparse matrix libraries, the proposed graph optimisation algorithm can be implemented in an efficient way by exploiting the sparse structure, which is more suitable for solving super large-scale graph optimisation problems.

Instead of solving the complete large-scale graph optimisation problem, the local subgraph joining algorithm builds accurate graphs by creating multiple local subgraphs and later aligning and merging them through subgraph joining optimisation, improving scalability, consistency, and efficiency.

Theoretical analysis will be performed on the computational complexity of the proposed algorithms to solve the graph optimisation problems.

The developed algorithms will be evaluated on using publicly available datasets and Lagrange Centre provided datasets, in terms of efficiency, convergence and computational cost.

Expected Outcome and Impact

• Reliable graph optimisation algorithms for better convergence property.
• Efficient implementation of graph optimisation solver based on the special structure of the sparse matrices.
• Efficient implementation of subgraphs/submap joining solver.
• High quality research publications.

Students Requirements

• Solid understanding of SLAM problems, state estimation, graph optimisation and 3D reconstruction.
• Strong programming skills (e.g., C++/Python) and experience with ROS or relevant libraries (e.g., SuiteSparse, OpenCV, PCL).
• Good mathematical foundation in linear algebra, optimisation, and probabilistic inference.
• Excellent communication skills and the ability to work independently and collaboratively in a research team.
• Prior experience with research publications or large-scale SLAM systems is desirable but not essential.

References

[1] Zhao, L., Huang, S., Sun, Y., Yan, L. and Dissanayake, G., 2015. Parallaxba: bundle adjustment using parallax angle feature parametrization. The International Journal of Robotics Research (IJRR), 34(4-5), pp.493-516.

[2] L. Zhao, and Y. Sun, “ParallaxBA C/C++ source code,” released on OpenSLAM, https://openslam-org.github.io/ParallaxBA.html.

[3] Zhao, L., Huang, S. and Dissanayake, G., 2019. Linear SLAM: Linearising the SLAM problems using submap joining. Automatica, 100, pp.231-246.

[4] Zhao, L., Huang, S. and Dissanayake, G., 2018. Linear SFM: A hierarchical approach to solving structure-from-motion problems by decoupling the linear and nonlinear components. ISPRS journal of photogrammetry and remote sensing (ISPRS), 141, pp.275-289.