First four pars of intro for your convenience: Graphs have been used with great success as representations of probability models, both Bayesian and Markov netw

First four pars of intro for your convenience: Graphs have been used with great success as representations of probability models, both Bayesian and Markov networks as well as latent-variable neural networks. But in many applications, especially in speech and language processing, a fixed graph is not sufficient. The graph may have substructures that repeat a variable number of times: for example, a hidden Markov model (HMM) depends on the number of words in the string. Or, part of the graph may have several alternatives with different structures: for example, a probabilistic context-free grammar (PCFG) contains many trees for a given string. Several formalisms have been proposed to fill this need. Plate notation (Buntine, 1994), plated factor graphs (Obermeyer et al., 2019), and dynamic graphical models (Bilmes, 2010) address the repeated-substructure problem, but only for sequence models like HMMs. Case–factor diagrams (McAllester et al., 2008) and sum–product networks (Poon and Domingos, 2011) address the alternative-substructure problem, so they can describe PCFGs, but only for fixed-length inputs. More general formalisms like probabilistic relational models (Getoor et al., 2007) and probabilistic programming languages (van de Meent et al., 2018) address both problems successfully, but because of their generality, tractable exact inference in them is often not possible. Here, we explore the use of hyperedge replacement graph grammars (HRGs), a formalism for defining sets of graphs (Bauderon and Courcelle, 1987; Habel and Kreowski, 1987; Drewes et al., 1997). We show that HRGs for factor graphs, or factor graph grammars (FGGs) for short, are expressive enough to solve both the repeated-substructure and alternative-substructure problems, and constrained enough allow exact and tractable inference in many situations. ____ I'm still not sure I get it, but I think the idea is somehow similar to Feynman diagrams — establish a set of rules that allow to do calculations efficiently. Maybe someone who knows more about this can explain?