Learning Hidden Graphs From Samples

Several real-world problems, like molecular biology and chemical reactions, have hidden graphs, and we need to learn the hidden graph using edge-detecting samples. In this problem, the learner receives examples explaining whether a set of vertices induces an edge of the hidden graph. This article examines the learnability of this problem using the PAC and Agnostic PAC learning models. By computing the VC-dimension of hypothesis spaces of hidden graphs, hidden trees, hidden connected graphs, and hidden planar graphs through edge-detecting samples, we also find the sample complexity of learning these spaces. We study the learnability of this space of hidden graphs in two cases, namely for known and unknown vertex sets. We show that the class of hidden graphs is uniformly learnable when the vertex set is known. Furthermore, we prove that the family of hidden graphs is not uniformly learnable but is nonuniformly learnable when the vertex set is unknown.