Most probably it’s the for loops. For better performance it’s always better do vector operations.
so the line -
u_star[i] -= ctx.alpha*sum([(1 if w[i] > w[j] else -1) for j in FrankWolfe_MinCutSum_Canonical.neighbors(ctx, i)])
if you can write it as a vector operation without a for loop it should be much faster.