A Spectral Projected Gradient Method for a Class of Graph Clustering Problems

Community-based graph clustering is one of the most popular topics in the analysis of complex social networks. This paper studies a specific form of graph clustering problems that can be formulated as quadratic semi-assignment problems (QSAP), where the objective functions exhibit block properties. As QSAP, this kind of graph clustering problems have been proved to be equivalent to their continuous relaxation problems (RQSAP), in terms of sharing the same optimal objective value. However, since the current algorithm for solving this RQSAP uses the projected Newton method, which requires direct computation of the Hessian matrix, its computational cost remains high. Precisely for this reason, we choose to employ the spectral projected gradient (SPG) method to solve the graph clustering problem, whose effectiveness relies on choosing the step lengths according to novel ideas that are related to the spectrum of the underlying local Hessian. Specifically, we apply a penalty method to solve the subproblems using the SPG method. Numerical results on both synthetic graphs generated by the planted partition model and a well-known real-world network dataset verify the superior performance of our approach over the current algorithms in both quality and efficiency.