ElGamal in private set intersection: how to handle negative numbers?
I use the notation introduced in the paper: The parameters of ElGamal are $(G, q, g)$ where $q$ is prime, $G$ is a cyclic 
group of order $q$ and $g$ is a generator. In the paper, the authors use "exponential ElGamal" such that they have an additive homomorphism, i.e., the message is 
represented as "exponent" of $g$, i.e., as $g^m$. With $h=g^x$ 
being the public key a ciphertext of a message $m\in Z_q$ is $(c_1,c_2)=(g^y,h^y\cdot g^m)$ and it is clear that by componentwise 
multiplication of two ciphertexts for messages $m_1$ and $m_2$, the additive homomorphism gives a ciphertext for $m_1+m_2 \mod q$.

Note that the message space is $Z_q$ and we are working with integers modulo $q$, i.e., the set $\{0,\ldots,q-1\}$. 

Now how to handle negative integers $-x$?

There are two ways how you can see this: 

If for $-x$ that the absolute value of $x$ is in the set $\{0,\ldots,q-1\}$, i.e., you have that $0\leq |x|&lt;q$. 
Then, you can view $-x$ as the additive inverse of $x$ in the group $(Z_q,+)$ which has order $q$. This means $-x$ is an element $a$ 
for which it holds that $x+a\equiv 0 \pmod q$. Consequently, the value of $a$ is $p-x$.
For example: Let $q=5$ and we want to know $-2$, i.e., the additive inverse of $2$ in $Z_5$, then we have $-2=5-2=3$, since 
$2+3\equiv 0 \pmod 5$, so $-2$ is equal to $3$. 

Now what if the absolute value of $x$ is not in the set $\{0,\ldots,q-1\}$? For instance, how to handle $-16$ in case of the integers modulo $5$?.

We also can view integers modulo $q$, i.e., the set $\{0,\ldots,q-1\}$, as a set of representatives of the $q$ residue classes modulo $q$. 
More precisely, $0$ is a representative for the class $[0]$ of all integers having remainder $0$ when divided by $q$, $1$ a representative for class $[1]$, etc. If you encounter a negative integer as 
defined above, then you simply add $q$ until the value lies within the set $\{0,\ldots,q-1\}$ since this will obviously not change the class. 

Back to our example, this means that given $-16$ you add $5$ and find that $-16+5=-11$, $-11+5=-6$, $-6+5=-1$ and finally, 
$-1+5=4$. Consequently $-16\equiv 4 \pmod 5$ and you can represent $-16$ as $4$.