Maximum set of equalities, subject to some inequalities
Using your graph theoretic formulation, this problem can be restated as the multi-cut problem.


  Given a graph $G = (V, E)$ and a set of pairs $(s_i, t_i) \in I$ find a  set of edges $E' \subseteq E$ such that there is no path $s_i \leadsto t_i$ in the resulting graph $G' = (V, E \setminus E')$ for each $i$.


Since each inequality is unweighted you need to find a minimum size multi-cut.

This problem is NP-hard in general however there exist reasonable approximation algorithms that solve an LP. However a simple strategy might be to just take the union of each $(s_i, t_i)$ cut.