Labai, Nadia ;
Makowsky, Johann A.
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 alpha and edge weights beta. M. Freedman, L. Lovasz and A. Schrijver have given a characterization of these graph parameters in terms of the kconnection 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 BlumShubSmale model of computation over the reals with unit cost.
BibTeX  Entry
@InProceedings{labai_et_al:LIPIcs:2016:6475,
author = {Nadia Labai and Johann A. Makowsky},
title = {{On the Exact Learnability of Graph Parameters: The Case of Partition Functions}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {63:163:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6475},
URN = {urn:nbn:de:0030drops64750},
doi = {10.4230/LIPIcs.MFCS.2016.63},
annote = {Keywords: exact learning, partition function, weighted homomorphism, connection matrices}
}
19.08.2016
Keywords: 

exact learning, partition function, weighted homomorphism, connection matrices 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

19.08.2016 