Inference on vertex-aligned graphs is of wide theoretical and practical\nimportance.There are, however, few flexible and tractable statistical models\nfor correlated graphs, and even fewer comprehensive approaches to parametric\ninference on data arising from such graphs. In this paper, we consider the\ncorrelated Bernoulli random graph model (allowing different Bernoulli\ncoefficients and edge correlations for different pairs of vertices), and we\nintroduce a new variance-reducing technique -- called \\emph{balancing} -- that\ncan refine estimators for model parameters. Specifically, we construct a\ndisagreement statistic and show that it is complete and sufficient; balancing\ncan be interpreted as Rao-Blackwellization with this disagreement statistic. We\nshow that for unbiased estimators of functions of model parameters, balancing\ngenerates uniformly minimum variance unbiased estimators (UMVUEs). However,\neven when unbiased estimators for model parameters do {\\em not} exist -- which,\nas we prove, is the case with both the heterogeneity correlation and the total\ncorrelation parameters -- balancing is still useful, and lowers mean squared\nerror. In particular, we demonstrate how balancing can improve the efficiency\nof the alignment strength estimator for the total correlation, a parameter that\nplays a critical role in graph matchability and graph matching runtime\ncomplexity.\n