This paper summarizes the key results of applying Variable Neighborhood Search (VNS) to graph clustering. The paper provides an overview of various adaptations of VNS developed for optimizing different quality measures, including modularity, edge ratio, and E-quality, across different network types. Special attention is given to generic VNS method and its flexibility in solving clustering problems with various quality functions. Additionally, the paper presents experimental findings that demonstrate the robustness and flexibility of VNS in achieving high-quality cluster partitions on artificial and real-world networks. These results demonstrate the important role of VNS in graph clustering methodologies and its potential for future applications.