Enhanced Graph-Learning Schemes Driven by Similar Distributions of Motifs

Abstract

This paper looks at the task of network topology inference, where the goal is to learn an unknown graph from nodal observations. One of the novelties of the approach put forth is the consideration of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">prior information</i> about the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">density of motifs</i> of the unknown graph to enhance the inference of classical Gaussian graphical models. Directly dealing with the density of motifs constitutes a challenging combinatorial task. However, we note that if two graphs have similar motif densities, one can show that the expected value of a polynomial applied to their empirical spectral distributions will be similar. Guided by this, we first assume that we observe a reference graph with a density of motifs similar to that of the sought graph, and then, we exploit this relation by incorporating a similarity constraint and a regularization term in the graph learning optimization problem. The (non-)convexity of the optimization problem is discussed, and a computationally efficient alternating majorization-minimization algorithm is designed. We assess the performance of the proposed method through exhaustive numerical experiments, where different constraints are considered and compared against popular alternatives on both synthetic and real-world datasets.