Document Open Access Logo

On the Exact Learnability of Graph Parameters: The Case of Partition Functions

Authors Nadia Labai, Johann A. Makowsky

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.63.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Nadia Labai
Johann A. Makowsky

Cite As Get BibTex

Nadia Labai and Johann A. Makowsky. On the Exact Learnability of Graph Parameters: The Case of Partition Functions. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.63

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 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.

Subject Classification

Keywords
  • exact learning
  • partition function
  • weighted homomorphism
  • connection matrices

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39(3):337-350, 1978. Google Scholar
  2. D. Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1987. Google Scholar
  3. A. Beimel, F. Bergadano, N. H. Bshouty, E. Kushilevitz, and S. Varricchio. Learning functions represented as multiplicity automata. Journal of the ACM (JACM), 47(3):506-530, 2000. Google Scholar
  4. G. D. Birkhoff. A determinant formula for the number of ways of coloring a map. Annals of Mathematics, 14:42-46, 1912. Google Scholar
  5. L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and real computation. Springer Science &Business Media, 2012. Google Scholar
  6. L. Blum, M. Shub, S. Smale, et al. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin (New Series) of the American Mathematical Society, 21(1):1-46, 1989. Google Scholar
  7. B. Bollobás. Modern Graph Theory. Springer, 1999. Google Scholar
  8. J. Draisma, D. C. Gijswijt, L. Lovász, G. Regts, and A. Schrijver. Characterizing partition functions of the vertex model. Journal of Algebra, 350(1):197-206, 2012. Google Scholar
  9. P. Erdős and A. Rényi. Asymmetric graphs. Acta Mathematica Hungarica, 14(3-4):295-315, 1963. Google Scholar
  10. M. Freedman, L. Lovász, and A. Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, 20(1):37-51, 2007. Google Scholar
  11. A. Habrard and J. Oncina. Learning multiplicity tree automata. In Grammatical Inference: Algorithms and Applications, pages 268-280. Springer, 2006. Google Scholar
  12. J. Kötters. Almost all graphs are rigid—revisited. Discrete Mathematics, 309(17):5420-5424, 2009. Google Scholar
  13. N. Labai and J. A. Makowsky. On the exact learnability of graph parameters: The case of partition functions. arXiv preprint arXiv:1606.04056, 2016. URL: http://arxiv.org/abs/1606.04056.
  14. L. Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. AMS, 2012. Google Scholar
  15. L. Lovász. The rank of connection matrices and the dimension of graph algebras. European Journal of Combinatorics, 27(6):962-970, 2006. Google Scholar
  16. A. Schrijver. Graph invariants in the spin model. J. Comb. Theory, Ser. B, 99(2):502-511, 2009. Google Scholar
  17. A. Schrijver. Characterizing partition functions of the spin model by rank growth. Indagationes Mathematicae, 24.4:1018-1023, 2013. Google Scholar
  18. A. Schrijver. Characterizing partition functions of the edge-coloring model by rank growth. Journal of Combinatorial Theory, Series A, 136:164-173, 2015. Google Scholar
  19. A. D. Sokal. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Survey in Combinatorics, 2005, volume 327 of London Mathematical Society Lecture Notes, pages 173-226, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact