First, we should look into the definition of tripartite information $(I_3)$ to see what we can learn about its negativity. It seems that this quantity has several names in the Information Theory literature like "Multivariate Mutual Information", "Interaction Information", etc., and it has been the subject of multiple interpretations. Working with the Interaction Information definition, for the three variables $X$, $Y$, $Z$ we have: $$I_{3}(X:Y:Z)=I(X:Y|Z)-I(X:Y)$$
which clearly states that the $I_3$ is the difference between the information shared by $X$ and $Y$ when $Z$ is fixed (or conditioned out) and when $Z$ is not fixed. Now it's been said that the case of $I_3 \lt0$ amounts to the "redundancy" (or the "loss") of information between $X$ and $Y$ when $Z$ is fixed [1].
Now what this negativity of $I_3$ could imply? The "Monogamy" of mutual information as it's stated in the Hayden's paper that you mentioned. In the case of mutual information one can write this monogamy as:
$$I(X:Y)+I(X:Z) \le I(X:YZ)$$
Now since we can rewrite the interaction information as:
$$I_{3}(X:Y:Z)=I(X:Y)+I(X:Z)-I(X:YZ)$$
then the negativity of $I_3$ would imply the monogamy which is the case when the whole is greater than the sum of its parts. There's more (specific) correlation between $\{X,YZ\}$ than $X$ with $YZ$'s components $($i.e. with $Y$ and with $Z$$)$, and it would be lost if we consider the sum of the correlations between $\{X,Y\}$ and $\{X,Z\}$ only [2].
Aron Wall showed that the monogamy condition also holds in the Covariant HEE case $($HRT proposal$)$ [3]. Therefore one can safely say that any quantum theory which has a holographic dual would obey the monogamy condition. I hope that it helps you.
[1] https://arxiv.org/abs/1602.05063
[2] https://arxiv.org/abs/1505.03696
[3] https://arxiv.org/abs/1211.3494v4
