Analyzing the robustness of neural networks is crucial for trusting them. The vast majority of existing work focuses on networks' robustness to epsilon-ball neighborhoods, but these cannot capture complex robustness properties. In this work, we propose VeNuS, a general approach and a system for computing maximally non-uniform robust neighborhoods that optimize a target function (e.g., neighborhood size). The key idea is to let a verifier guide our search by providing the directions in which a neighborhood can expand while remaining robust. We show two approaches to compute these directions. The first approach treats the verifier as a black-box and is thus applicable to any verifier. The second approach extends an existing verifier with the ability to compute the gradient of its analysis results. We evaluate VeNuS on various models and show it computes neighborhoods with 10^407x more distinct images and 1.28x larger average diameters than the epsilon-ball ones. Compared to another non-uniform robustness analyzer, VeNuS computes neighborhoods with 10^314x more distinct images and 2.49x larger average diameters. We further show that the neighborhoods that VeNuS computes enable one to understand robustness properties of networks which cannot be obtained using the standard epsilon-balls. We believe this is a step towards understanding global robustness.