What is multi-hot encoding?

Without having read the paper, from the name I would say a multi-hot encoding is a matrix $X in {0,1}^{n times m }$, with $sum_{i = 1}^{n} X_{i,j} = 1, forall j = 1,ldots,m$.

You obtain the normal hot-encoding by setting $m=1$.