Assuming every operation to one single instance takes O(1). Let the training dataset size be N, neighbour strength be k, time steps be T.
(Model inference) Extracting feature vectors takes O(N).
(δ-boundary estimation) Given that the boundary set size is linear to dataset size B, i.e., N = c_1B and mixup attack failure rate is above a constant c_2, δ-boundary estimation takes O(N).
(Spatio-temporal complex construction) Implementation of spatial-temporal complex construction requires k nearest neighbors estimation. We apply NNDescent in practice. While no theoretical upper bounds were provided by NNDescent, they showed an empirical complexity of O(N^1.14), Therefore, constructing the spatial-temporal complex is O(TN^1.14).
(Complex reduction) At each time step, finding m centers of N data representations takes O(mN). Since we have T steps, the time complexity is O(mNT). In practice, m << N, which means time complexity is O(TN).
(Training) Training edge dataset complexity is O(kTN).
In all, the overall complexity is empirically approximately O(TN^1.14) for the whole training process.