When applying the optimal parallel transport model to large-scale real-world graphs, several computational complexity considerations and scalability challenges arise. The primary challenge is the inherent complexity of solving the Beckmann problem on connection graphs, which involves optimizing over a potentially high-dimensional space of flows ( J ) while satisfying the constraints imposed by the connection incidence matrix ( B ).
The computational complexity of the proposed framework is influenced by the number of edges ( |E'| ) and the dimensionality ( d ) of the vector fields. The optimization problem is typically non-convex, especially in the presence of the connection structure, which can lead to difficulties in finding global optima. As the size of the graph increases, the number of possible flows grows exponentially, making it computationally expensive to evaluate all potential solutions.
To address these challenges, one can employ efficient algorithms such as interior-point methods or primal-dual algorithms that exploit the structure of the problem. Additionally, leveraging parallel computing and distributed optimization techniques can significantly enhance scalability, allowing for the processing of large graphs by dividing the problem into smaller, manageable subproblems. Regularization techniques, as discussed in the paper, can also help stabilize the optimization process and improve convergence rates.