For graph partitioning , we experimented with a set of classic benchmarks 6 . Since the optimization criteria is modularity , we compared our method only against best known " modularity optimization " heuristics : ( a ) FastModularity [ 26 ] , ( b ) Louvain [ 29 ] , ( c ) Spin - glass [ 25 ] and ( d ) Leading eigenvector [ 27 ] . For message passing , we use λ = .1 , max = median{|ω(e ) − ω null ( e)| } e∈E∪E null and T max = 10 . Here we do not perform any decimation and directly fix the variables based on their bias µ e > 0 ⇔ x e = 1 . Table 1 summarizes our results ( see also Figure 1(middle , right ) ) . Here for each method and each data - set , we report the time ( in seconds ) and the Modularity of the communities found by each method . The table include the results of message passing for both full and sparse null models , where we used a constant α = 20 to generate our stochastic sparse null model . For message passing , we also included L = |E + E null | and the saving in the cost using augmentation . This column shows the percentage of the number of all the constraints considered by the augmentation . For example , the cost of .14 % for the polblogs data - set shows that augmentation and sparse null model meant using .0014 times fewer clique - factors , compared to the full factor - graph .