On the exact learnability of graph parameters: The case of partition functions

Abstract

We study the exact learnability of real valued graph parameters $f$ which are known to be representable as partition functions which count the number of weighted homomorphisms into a graph $H$ with vertex weights $\hat{I}\pm$ and edge weights ${\hat{I}}^2$. M. Freedman, L. Lovász and A. Schrijver have given a characterization of these graph parameters in terms of the $k$-connection matrices $C(f,k)$ of $f$. Our model of learnability is based on D. Angluin's model of exact learning using membership and equivalence queries. Given such a graph parameter $f$, the learner can ask for the values of $f$ for graphs of their choice, and they can formulate hypotheses in terms of the connection matrices $C(f,k)$ of $f$. The teacher can accept the hypothesis as correct, or provide a counterexample consisting of a graph. Our main result shows that in this scenario, a very large class of partition functions, the rigid partition functions, can be learned in time polynomial in the size of $H$ and the size of the largest counterexample in the Blum-Shub-Smale model of computation over the reals with unit cost.

14 pages, full version of the MFCS 2016 conference paper