Hardness of Vertex Separators
In the edge setting, the problem you're referring to is the bisection problem, and the size of such a minimum edge is called the bisection width. There's a ton of research on this problem, and the best known approximation for the problem is $O(\log n)$ by Racke.

A good review of the known work on this problem (which connects to sparsest cut, spreading metrics, and even the unique games conjecture) is in this recent paper on generalizations of bisection width by Krauthgamer, Naor and Schwartz.