Complexity

At each time step t\in[T], assuming every operation to one single instance takes O(1). Let the training dataset size be N, neighbor strength to be k.

1. (Model inference) Extracting feature vectors takes O(N).

2. (δ-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).

3. (k-BAVR Complex construction) Practical implementation of complex construction requires k nearest neighbor estimation. No theoretical upper bounds were provided by the NNDescent paper, they showed an empirical complexity of O(N^1.14).

4. (Training) The constructed complex contains O(kN) edges. In the training process, we go over each edge 10 times per epoch. Given that the negative sampling rate is determined, the overall edge complexity is still O(kN). Let the training epochs be M. This results in a complexity of O(kMN) for the training process. While no theoretical upper bound is provided for training epochs as well, we report that the training process converges after less than 30 epochs. Considering M<30 is trivial compared to N, we ignore this term. This results in a complexity of O(kN) in the training process.

In all, the overall complexity is empirically approximately O(N^1.14) for the whole training process.