Attributed Graph Modeling with Vertex Replacement Grammars

Abstract

Recent work at the intersection of formal language theory and graph theory has explored graph grammars for graph modeling. However, existing models and formalisms can only operate on homogeneous (i.e., untyped or unattributed) graphs. We relax this restriction and introduce the Attributed Vertex Replacement Grammar (AVRG), which can be efficiently extracted from heterogeneous (i.e., typed, colored, or attributed) graphs. Unlike current state-of-the-art methods, which train enormous models over complicated deep neural architectures, the AVRG model is unsupervised and interpretable. It is based on context-free string grammars and works by encoding graph rewriting rules into a graph grammar containing graphlets and instructions on how they fit together. We show that the AVRG can encode succinct models of input graphs yet faithfully preserve their structure and assortativity properties. Experiments on large real-world datasets show that graphs generated from the AVRG model exhibit substructures and attribute configurations that match those found in the input networks.

arXiv comment9 pages, 2 tables, 10 figures. Accepted as a regular paper at WSDM 2021

References in corpus (18)

• Fast unfolding of communities in large networks
• DeepWalk: Online Learning of Social Representations
• From Louvain to Leiden: guaranteeing well-connected communities
• LINE: Large-scale Information Network Embedding
• Near linear time algorithm to detect community structures in large-scale networks
• Mixing patterns in networks
• Hierarchical Organization in Complex Networks
• Stochastic blockmodels and community structure in networks
• The map equation
• Variational Graph Auto-Encoders
• GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
• NetGAN: Generating Graphs via Random Walks
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering
• Modeling Graphs with Vertex Replacement Grammars
• Growing Graphs with Hyperedge Replacement Graph Grammars
• Towards Interpretable Graph Modeling with Vertex Replacement Grammars
• The Infinity Mirror Test for Graph Models