Graph partitioning is a technique which is widely used in many fields of computer science and engineering. The goal is to partition the vertices of a graph into a certain number of disjoint sets of approximately the same size, so that a cut metric is minimized. Due to the NP-hardness of the problem and its practical importance, many different heuristics (spectral, combinatorial, evolutionist, etc.) have been developed to provide an approximate result in acceptable computational time. However, the advent of increasingly larger instances in emerging applications such as social networks or power networks renders graph partitioning and related graph algorithms such as clustering or community detection more and more important, multifaceted, and challenging. Spectral graph partitioning in the 2-norm using the eigenvectors of the graph Laplacian matrix was pioneered by Fiedler. However, this approach is considered infeasible for large-scale graphs, due to the prohibitively expensive computation of the Fiedler eigenvector, a fact that prompted the development of modern multilevel graph partitioning methods. Additionally, it has been proven that the quality of the partitions obtained by the spectral approach can be improved by considering the equivalent eigenvalue problem in the $p$-norm. In this project we plan to extend the aforementioned p-Laplacian partitioning method by developing two simultaneous research directions aiming at high quality graph partitioning on modern high performance parallel architectures. The first one will utilize the structural information encoded in the third eigenvector of the graph Laplacian matrix, corresponding to the third smallest eigenvalue. Incorporating more information present in the spectra has proven to improve the traditional spectral bisection algorithm, and such an approach is expected to improve the quality of the p-Laplacian partitioning scheme as well. Moreover, we intend to study the benefits of replacing the traditional gradient descent method currently utilized, with an optimization technique tailored for nonconvex scenarios.