Graph Learning from Smooth Signals and Predictors with Partially Known Graph Topology

There has been rapid development in graph learning methodology for real-world applications. Many previous graph learning methods depend on the information of a ground truth graph for tuning parameter selections. However, in real-world scenarios, we are not always given the entire graph topology. In this paper, we develop a novel algorithm to uncover the entire structure of the graph topology using signals and predictors (also known as regressors) on the vertices with partial information on the graph topology for tuning parameter selections. The inputs to our algorithm include the graph signals, partially known graph topology, and external predictors or regressors. Our output will be the entire (uncovered) estimated graph topology represented by graph Laplacian. We tested our algorithm using different types of random graphs, such as the Barabasi-Albert (BA) random graph and Erdős-Rényi (ER) random graph model. We compared the ground truth graph Laplacian with the learned graph Laplacians under different percentages of known graph topology, respectively. Our experiments showed advantageous and promising graph learning performance even with a small percentage of known graph topology. The algorithm developed in this paper has potential in more real-world applications.