On the Difficulty of Learning Power Law Graphical Models

A power-law graph is any graph G = (V, E), whose degree distribution follows a power law i.e. the number of vertices in the graph with degree i, yi, is proportional to i(-beta) : yi alpha i(-beta). In this paper, we provide information-theoretic lower bounds on the sample complexity of learning such power-law graphical models i.e. graphical models whose Markov graph obeys the power law. In addition, we briefly revisit some existing state of the art estimators, and explicitly derive their sample complexity for power-law graphs.