Abstract
Discovering the underlying structures present in large real world graphs is a fundamental scientific problem. Recent work at the intersection of formal language theory and graph theory has found that a Probabilistic Hyperedge Replacement Grammar (PHRG) can be extracted from a tree decomposition of any graph. However, because the extracted PHRG is directly dependent on the shape and contents of the tree decomposition, rather than from the dynamics of the graph, it is unlikely that informative graph-processes are actually being captured with the PHRG extraction algorithm. To address this problem, the current work adapts a related formalism called Probabilistic Synchronous HRG (PSHRG) that learns synchronous graph production rules from temporal graphs. We introduce the PSHRG model and describe a method to extract growth rules from the graph. We find that SHRG rules capture growth patterns found in temporal graphs and can be used to predict the future evolution of a temporal graph. We perform a brief evaluation on small synthetic networks that demonstrate the prediction accuracy of PSHRG versus baseline and state of the art models. Ultimately, we find that PSHRGs seem to be very good at modelling dynamics of a temporal graph; however, our prediction algorithm, which is based on string parsing and generation algorithms, does not scale to practically useful graph sizes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aguinaga, S., Chiang, D., Weninger, T.: Learning hyperedge replacement graph grammars for graph generation. IEEE Trans. Pattern Anal. Mach. Intell. (2018). https://doi.org/10.1109/TPAMI.2018.2810877
Aguinaga, S., Palacios, R., Chiang, D., Weninger, T.: Growing graphs from hyperedge replacement grammars. In: CIKM. ACM (2016)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. science 286(5439), 509–512 (1999)
Bullmore, E., Sporns, O.: Complex brain networks: graph theoretical analysis of structural and functional systems. Nat. Rev. Neurosci. 10(3), 186–198 (2009)
Chiang, D.: An introduction to synchronous grammars. https://www.nd.edu/~dchiang/papers/synchtut.pdf
Chiang, D., Andreas, J., Bauer, D., Hermann, K.M., Jones, B., Knight, K.: Parsing graphs with hyperedge replacement grammars. In: Proceedings of ACL, pp. 924–932 (2013)
Clarke, B.L.: Theorems on chemical network stability. J. Chem. Phys. 62(3), 773–775 (1975)
Doolittle, W.F., Bapteste, E.: Pattern pluralism and the tree of life hypothesis. Proc. Nat. Acad. Sci. 104(7), 2043–2049 (2007)
Drewes, F., Kreowski, H.J., Habel, A.: Hyperedge replacement graph grammars. Handb. Graph Grammars 1, 95–162 (1997)
Erdos, P., Rényi, A.: On the evolution of random graphs. Bull. Inst. Internat. Stat. 38(4), 343–347 (1961)
Granovetter, M.S.: The strength of weak ties. Am. J. Sociol. 78(6), 1360–1380 (1973)
Habel, A.: Hyperedge Replacement: Grammars and Languages. LNCS, vol. 643. Springer, Heidelberg (1992). https://doi.org/10.1007/BFb0013875
Kemp, C., Tenenbaum, J.B.: The discovery of structural form. Proc. Nat. Acad. Sci. 105(31), 10687–10692 (2008)
Kuhn, T.S.: The Structure of Scientific Revolutions. University of Chicago Press, Chicago (2012)
Kukluk, J., Holder, L., Cook, D.: Inferring graph grammars by detecting overlap in frequent subgraphs. Int. J. Appl. Math. Comput. Sci. 18(2), 241–250 (2008)
Yaveroğlu, Ö.N., Milenković, T., Pržulj, N.: Proper evaluation of alignment-free network comparison methods. Bioinformatics 31(16), 2697–2704 (2015)
Acknowledgements
We thank Chiemi Matsumoto and Peter Bui for their help with this project. This work is sponsored by grant from the US NSF IIS (16-52492).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Pennycuff, C., Sikdar, S., Vajiac, C., Chiang, D., Weninger, T. (2018). Synchronous Hyperedge Replacement Graph Grammars. In: Lambers, L., Weber, J. (eds) Graph Transformation. ICGT 2018. Lecture Notes in Computer Science(), vol 10887. Springer, Cham. https://doi.org/10.1007/978-3-319-92991-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-92991-0_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-92990-3
Online ISBN: 978-3-319-92991-0
eBook Packages: Computer ScienceComputer Science (R0)