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 (, untyped or unattributed) graphs. We relax this restriction and introduce the Attributed Vertex Replacement Grammar (AVRG), which can be efficiently extracted from heterogeneous (, 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.

§ INTRODUCTION

One of the principal goals of graph mining is to discover patterns found in real-world graphs and use them to make predictions about various relational systems. Many such systems consist of differently typed components; it has long been argued that models which treat graphs as homogeneous, without distinguishing different types of objects and links, ignore important information. By leveraging these rich semantics as attribute labels on nodes and edges, researchers have developed attributed graph analysis techniques to better model such data (, via heterogeneous information networks),  leading to improvements in downstream inference tasks [Sun and Han, 2013, Sun et al., 2011].   Because graphs encode interaction information about many real-world relational systems, learning how to generatively model such graphs offers a promising window into their dynamics, spurring a rich line of work [Robins et al., 2007, Leskovec et al., 2010, Chung and Lu, 2002, Karrer and Newman, 2011], inspiring our present one.

(A) Example attributed graph and (B) an Attributed Vertex Replacement Graph Grammar (AVRG) extracted from the example graph. The AVRG succinctly and faithfully describes graph topology and attribute configuration of the input graph.

Present Work. Our work[The source code is available at <https://github.com/satyakisikdar/Attributed-VRG>] lies at the intersection of attributed graph mining and graph generation.  Specifically, we build upon a class of local topology-aware generators called Vertex Replacement Grammars (VRGs).   Having their origins in formal language theory, where objects of different types (, characters, glyphs, words, parts of speech), graph grammars offer a promising avenue in modeling attributed graphs like the small example illustrated in <ref>(A).
Attributed Vertex Replacement Grammar (AVRG) builds on recent advances in graph grammars [Hibshman et al., 2019, Sikdar et al., 2019, Aguiñaga et al., 2018], which were designed only to model and generate homogeneous graphs, to handle attributed graphs, increasing its applicability to a broad class of modern problems.

Graph neural networks (GNNs) comprise a wide swath of models with similar goals in attributed graph modeling. These models train deep neural network architectures using loss functions and stochastic gradient descent. GNNs offer excellent modeling capacity in downstream machine learning tasks but can be difficult to train, have enormous parameter spaces, and do not readily permit human inspection.
Despite performing well on link prediction and node classification tasks, some GNN architectures fail to preserve the topological fidelity of the input graphs [Sikdar et al., 2020]. AVRGs, on the other hand, can capture and model the subtle intricacies in both topological and attribute spaces without requiring supervision, deep neural architectures, and training.

Simply put, the goal of the present work is to extract graph rewriting rules, like those illustrated in <ref>(B), that are representative of the topology and attribute configuration of the original graph. Our key idea is to use an exemplar input graph to build a grammar of graph rewriting rules with patterns that can be applied stochastically to generate new, diverse graphs that meet desirable attribute and topology-related graph properties.  Both formally and through a running example, we introduce and describe the Attributed Vertex Replacement Grammar (AVRG) formalism and show the following:

* AVRGs can extract interesting and frequently appearing attributed subgraphs from large real-world graphs,

* AVRGs can generate graphs that match the topology and attribute assortativity of the original graph, and

* the ability of AVRGs to handle a wide variety of assortative and disassortative graphs.

Although graph grammars appear to be a natural fit for modeling attributed graphs, this task presents many challenges. Our paper describes many of the modeling decisions made as a result and their consequences. We also demonstrate the power and flexibility of AVRGs with two case studies–the former focuses on the ability to extract meaningful patterns in <ref>, and the latter on testing the generative ability of the model on well-known attributed graphs with various degree and attribute assortativity values in <ref>.
We find that AVRG models provide a succinct yet faithful representation of input graphs–often better than attribute-based probabilistic models and graph neural network models at a far smaller computational cost and model size.

§ RELATED WORK

Attributed graphs are at the core of most modern graph mining literature.  Considerable prior work focuses on clustering [Zhou et al., 2010, Perozzi et al., 2014], classification [Xu et al., 2019], anomaly detection [Shah et al., 2016], similarity [Su et al., 2016, Al-Rfou et al., 2019], and search [Tong et al., 2007] tasks on attributed graphs.  The end goal of such methods is usually descriptive or inferential. On the one hand, descriptive methods tend to focus on discovering, enumerating, or counting patterns in given graph data [Grahne and Zhu, 2005, Ahmed et al., 2015], which may be attributed [Yan and Han, 2002, Sun et al., 2012] or dense [Hooi et al., 2016, Nilforoshan and Shah, 2019].  On the other hand, inferential methods involve statistical reasoning over graph data to make educated inferences (, on nodes, edges, or graphs) using examples  [Perozzi et al., 2014, Tang et al., 2015, Kipf and Welling, 2016, Veličković et al., 2018, Xu et al., 2019, Dong et al., 2017, Gao and Huang, 2018, Zhu et al., 2020, McPherson et al., 2001, Newman, 2003, Zhu et al., 2020, Zhu et al., 2020].

Other works study graphs through a prescriptive lens by characterizing their formation and generative processes, usually from a mathematical perspective.  This subfield, called graph generation, typically involves positing generative processes that aim to produce graphs with desirable (usually topological) statistical properties that match real-world phenomena. These include exponential random graphs [Robins et al., 2007], Kronecker graphs [Leskovec et al., 2010], Chung-Lu graphs [Chung and Lu, 2002], and Stochastic Block Models (SBMs) [Karrer and Newman, 2011] involves learning parameters via likelihood maximization based on a given input graph, which can be used to generate new graphs mimicking the input graph's properties.  Several very recent works also involve neural graph generation with recurrent neural networks [You et al., 2018], variational autoencoders [Simonovsky and Komodakis, 2018], and
generative adversarial networks [Bojchevski et al., 2018].  However, most graph generation literature focuses on non-attributed graphs.  The few exceptions [Pfeiffer III et al., 2014, Pfeiffer et al., 2012, Mussmann et al., 2014] adapt Chung and Lu's model for attributed graphs; yet, they ignore local graph topology, which is highly diverse across nodes in real graphs [Dong et al., 2017] with implications for tasks like anomaly detection [Akoglu et al., 2010], social contagion and diffusion [Ugander et al., 2012, Cheng et al., 2014], and engagement prediction [Yang et al., 2018].

A recent addition to the class of graph generators are hyperedge [Aguiñaga et al., 2016, Aguiñaga et al., 2018] and node replacement [Hibshman et al., 2019, Sikdar et al., 2019] grammars. Graph grammars contain graphical rewriting rules that match and replace graph fragments, similar to how a context-free string grammar rewrites characters in a string. These graph fragments represent a succinct description of the network's building blocks, and the graph grammar's rewiring rules describe the instructions about how the graph is pieced together.
Unfortunately, existing grammar formalisms do not provide for attributes, nor do they capture complex attribute mixing patterns during graph generation, making them unsuitable for attributed graphs.

§ ATTRIBUTED VERTEX REPLACEMENT GRAMMARS

§.§ Preliminaries

Labeled Attributed Multigraphs.
A labeled attributed multigraph is a $5$-tuple $H = \langle V, E, \kappa, L, \mathcal{A} \rangle$ where $V$ is the set of vertices; $E \subseteq V \times V$ is the set of edges; $\kappa : E \mapsto \mathbb{Z}^{+}$ is a function assigning multiplicity to edges; $L$ is the set of labels on nodes; and $\mathcal{A}: V \mapsto L$ is a function mapping nodes to attribute values in $L$.
By default, each edge has a multiplicity value of 1. Although our model can be used for directed graphs, the present work treats all graphs as undirected for clarity of prose and illustration.
Attributes can be internal, based on the graph topology like node degree, or external, based on externally observed parameters, such as age or gender.
We only focus on discrete attributes for simplicity, but these models can usually be extended relatively easily to handle continuous values.
We use $|\mathcal{A}|$ to denote the number of unique attribute values, so for the graph in <ref>(A), $|\mathcal{A}| = 2$ because it contains two different types/colors of nodes: blue and pink.

Assortativity. Assortativity functions permit us to quantify the nature of mixing patterns of attributes in networks. In this work, we adopt the definitions proposed by [Newman, 2003]  [Newman, 2003]. High assortativity values represents homophily, the birds-of-a-feather principle [McPherson et al., 2001], where nodes are likely to connect to nodes with similar attributes.

Typically graph modelers are interested in degree assortativity. That is, the assortativity of a network where node degrees were considered to be attributes. In fact, in much of the related literature, the term assortativity is generally taken to imply degree assortativity. However, in the present work, we endeavor to be precise when referring to the domain.
Table <ref> describes 12 datasets that are used as the experimental corpora in the present work. Each dataset is labeled with the number of nodes $|V|$, edges $|E|$, and number of unique attributes $|\mathcal{A}|$; as well as the degree assortativity $\rho_\text{deg}$ and external attribute assortativity $\rho_\text{attr}$.

Normalized Dasgupta Cost (NDC). We judge the goodness of a dendrogram $\mathcal{D}$ obtained from hierarchical graph clustering algorithms using the $(NDC)$ metric defined below [Dasgupta, 2016].

\begin{equation}
NDC(\mathcal{D},G) = \frac{\sum_{(u, v)\, \in\, E} |\text{leaves}(\text{LCA}(u, v, \mathcal{D}))|}{|V| \cdot |E|} \label{eq:norm-dasgupta}
\end{equation}

where $|\text{leaves}({\text{LCA}(u, v, \mathcal{D})})|$ is the number of leaves in the subtree rooted by lowest common ancestor (LCA) of nodes $u$ and $v$.

A good dendrogram $\mathcal{D}$ is expected to have a low cost because connected nodes in the graph should share an LCA lower down in the tree.

§.§ The AVRG Formalism

An Attributed Vertex Replacement Grammar (AVRG) is a $4$-tuple $G = \langle \Sigma, \Delta, \mathcal{P}, \mathcal{S} \rangle$ where $\Sigma$ is the alphabet of node labels; $\Delta \subseteq \Sigma$ is the alphabet of terminal node labels; $\mathcal{P}$ is a finite set of productions rules ($\mathcal{R}$) of the form $X \rightarrow (R, f)$, where $X$ is a left-hand side (LHS) consisting of a nonterminal node (, $X\in \Sigma \setminus \Delta$) with a size $\omega$; and the tuple $(R, f)$ represents the right-hand side (RHS) of the production rule, where $R$ is a labeled attributed multigraph with terminal and possibly nonterminal nodes, and $f \in \mathbb{Z}^+$ is the rule frequency, , the number of times it appears in the grammar; and $\mathcal{S}$ is the starting graph $\fbox{0}$, a nonterminal of size $0$.

Fig <ref>(B) shows an example AVRG with four rules. Each rule contains an LHS and RHS. Squares containing numbers are nonterminal-nodes that can be replaced by a rule's RHS. Colored nodes on the RHS subgraphs represent terminal nodes from the input graph. Every node in $R$ is labeled by the number of boundary edges adjacent to it in the original graph. The sum of boundary degrees on the RHS is defined as $\omega$ and used to label the LHS.

Incorporating attributes in the formalism introduces new challenges in both extraction and generation; we elaborate next.

§ EXTRACTING AVRGS

At a high level, our goal in the extraction process is to identify small but meaningful building blocks of a graph while also keeping track of how they can be pieced together. One way to find such building blocks would be to exhaustively enumerate all possible subgraphs up to a certain size, but this quickly becomes infeasible for even medium-sized graphs.
We opt to use a dendrogram obtained from a hierarchical clustering algorithm to help us find the building blocks to make our model scalable for large graphs.
This works well in practice because most real-world graphs are known to be self-similar across multiple scales, and therefore their nodes can be decomposed into clusters in a hierarchical fashion [Ravasz and Barabási, 2003].
Once we discover the blocks, we extract grammar rules and contract both the graph and the dendrogram. We repeat this extraction and contraction process until the graph is empty.
It is important to note that we only run the clustering algorithm once at the beginning and not every time the graph gets updated.

§.§ Selecting a Good Clustering Algorithm

We select 7 popularly used hierarchical graph clustering algorithms: conductance based bisection (Conductance) [Hagen and Kahng, 1992], spectral clustering (Spectral) [Ng et al., 2002], Hyperbolic Hierarchical Clustering (HyperHC) [Chami et al., 2020], Leiden [Traag et al., 2019], Louvain [Blondel et al., 2008], Infomap [Rosvall et al., 2009], and recursive label propagation (LabelProp) [Raghavan et al., 2007] algorithms.
We run these algorithms on the graphs described in <ref> and obtain dendrograms.
For every dendrogram, we calculate its Normalized Dasgupta Cost as defined in Eq. <ref>, group on clustering algorithm (, average across datasets), and plot the mean cost and 95% confidence interval (in blue) in <ref>. We adopted the formalism from [Sikdar et al., 2019] to calculate the description length [Sikdar et al., 2019] and the inverse compression ratio, , the ratio of the description length of a grammar and the input graph, such that lower is better. The mean inverse compression ratio and 95% confidence interval are plotted (in red) in <ref> alongside the Normalized Dasgupta cost.
We find that Conductance, Louvain, and Leiden perform best on average, so we down-select these three clustering algorithms for the next steps.

Mean-average Normalized Dasgupta Cost and Inverse Compression Ratio grouped by clustering algorithm. Error bars represent 95% confidence interval. Lower is better for both axes. Red dashed line at y=1 indicates no model compression. We pick Conductance, Leiden, and Louvain algorithms for further consideration.

§.§ Selecting a Suitable Internal Tree Node

Let $T = \{\eta_1, \cdots, \eta_k\}$ be the set of internal nodes in the dendrogram $\mathcal{D}$.
We observe that the leaves of a subtree rooted at an internal node $\eta_i \in T$ correspond to a subset of vertices of the $H$, , $V_{\eta_i} \subseteq V$.
For example, in <ref>(A), $V_{\eta_3}$ = $\{c, d, e\}$ and let $H_\eta$ be the subgraph induced by $V_\eta$ on $H$.
Considering each internal node is not particularly helpful, especially in large graphs, given the overlap in the subgraphs induced by a tree node and its ancestors.
Therefore, our goal is to determine a strategy that selects a particular tree node $\eta^\ast$ from $T$ that creates small but meaningful grammar rules.
So, let $s$ be a function $s: T \mapsto \mathbb{R}$ which assigns scores to individual tree nodes, and $T^\ast \subseteq T$ be the set of the lowest scoring tree nodes, , $T^\ast = \arg \min_{\eta \in T} \{s(\eta)\}$.
Now, depending on the scoring function and the state of the current dendrogram, $T^\ast$ may contain more than one optimal tree node, in which case we need a selection policy.

The most straightforward policy would be to pick a tree node at random from $T^\ast$. A slightly more sophisticated policy would consider scoring functions that operate based on the subtree's size.
In this approach, we introduce a new parameter $\mu \in \mathbb{Z}^+$. Our goal is to extract rules where the RHS subgraphs have exactly (or nearly) $\mu$ nodes. This aligns with our goal of finding small but meaningful rules from the input graph.
A simple scoring function that enforces the size-based approach would be $s(\eta_i) = |V_{\eta_i}| - \mu$.

Once we pick the best tree node $\eta^\ast$ $\in$ $T^\ast$, we proceed to extract a grammar rule $\mathcal{R}$ that we then add to grammar $G$.

§.§ Extracting an AVRG Rule

Let $H_{\eta^\ast} = (V_{\eta^\ast}, E_{\eta^\ast})$ be the subgraph induced by $V_{\eta^\ast}$ on $H$, where we copy over the corresponding attribute values from $V$ to $V_{\eta^\ast}$, and $E_{\eta^\ast} = \{(u, v)\,|\, u,v \in V_{\eta^\ast} \land (u, v) \in E \}$.
Let $E_{\text{cut}}^\ast = \{(u, v)\,|\, u \in V_{\eta^\ast} \land v \in V \}$ be the set of edges, called boundary edges, that span from $H_{\eta^\ast}$ to $H$, and let $\mathbf{b} = [b_1\ b_2\ \cdots\ b_{|V_{\eta^\ast}|}]^T$ be the vector of boundary degrees for each node $v \in V_{\eta^\ast}$.
The boundary degree ($b_i$) of a node $v_i$ stores the number of boundary edges to which $v_i$ is adjacent, , $b_i = |\{(u, v)\,|\, (u, v) \in E_{\text{cut}}^\ast \land (u = v_i \lor v = v_i)\}|$, and therefore $\sum \mathbf{b} = |E_{\text{cut}}^\ast| = \omega$. We include the boundary degree as an additional attribute for each node in $H_{\eta^\ast}$.

One iteration of the rule extraction and graph compression process. (A) Graph $H$, (B) $\eta^\ast$ = $\eta_3$ in  $\mathcal{D}$, (C) $V_{\eta_3}$ = {c, d, e}, boundary edges are drawn in red, (D) Extracted grammar rule, (E) New, reduced graph $H^\prime$ with the new nonterminal $X$ of size 5, and (F) Updated dendrogram $\mathcal{D}^\prime$.

Set of all grammar rules obtained from the dendrogram $\mathcal{D}$ for graph $H$ from <ref>(A). Note some tree nodes like $\eta_4$ and $\eta_5$ produce the same rule.

We now have all the ingredients needed to create a grammar rule. Let $\mathcal{R} = X \rightarrow (R, f)$ be an AVRG rule, where $X$ is a nonterminal of size $\omega$, $R$ is the graph $H_{\eta^\ast}$, and the frequency $f$ = 1.
Now, if $\mathcal{R}$ is a new rule, we add it to the grammar $G$; otherwise, we update the frequency of the existing rule in $G$ that is isomorphic to $\mathcal{R}$.
For example, we obtain 6 unique grammar rules from the dendrogram $\mathcal{D}$ in <ref>(B) which are shown in <ref>.

Rule Isomorphism. Two grammar rules $\mathcal{R}_1$ and $\mathcal{R}_2$ are isomorphic if and only if (a) their left-hand side nonterminals are of the same size, , $\omega_1 = \omega_2$, and (b) the RHS attributed graphs are isomorphic. We use the VF2 algorithm for this calculation [Cordella et al., 2004].

§.§ Updating the Data Structures

After extracting the grammar rule $\mathcal{R}$, we update both the current graph $H$ and dendrogram $\mathcal{D}$ to prevent the same set of nodes from directly participating in future rules.

Updating the Graph. In the current graph $H$, first we remove all the nodes in $V_{\eta^\ast}$ and its corresponding edges. Then, we introduce a new nonterminal node $X^\ast$  labeled with $\omega$ (from the rule extraction step).
We connect $X^\ast$ to the rest of the graph through the set of cut edges $E^{\ast}_{\text{cut}}$ in $R$ where the endpoints in $V_{\eta^\ast}$ are redirected to $X^\ast$.
Note, this may lead to the creation of multi-edges in the new graph $H^\prime$, which is now strictly smaller than $H$.

Updating the Dendrogram.
With a  new (smaller) $H^\prime$,  it may be prudent to re-run the clustering algorithm and generate a  new dendrogram.   However, our initial experiments found that re-clustering is time-consuming and rarely results in significant changes to the dendrogram.   Instead,  we modify $\mathcal{D}$ by replacing the subtree rooted at $\eta^\ast$ with nonterminal node $X^\ast$ labeled with $\omega$. Finally,  we set $H \leftarrow H^\prime$ and repeat the tree node selection and rule extraction processes until the dendrogram is empty.

Grammar Rules for our example graph $H$ using the dendrogram $\mathcal{D}$ in <ref>(B). The tree nodes $\eta_3$, $\eta_2$, $\eta_8$, $\eta_6$, and $\eta_1$ where selected in order to obtain these rules. Note that $\omega$ on the LHS is equivalent to the summation of the number of broken edges on the RHS, illustrated as numbers above or to the right of each RHS-node; $f=1$ for all rules.

In <ref> we continue the running example and illustrate the grammar rule extraction and graph and dendrogram contraction processes. The input graph (A) has 9 nodes, 16 edges, and each node is colored blue or pink. A dendrogram drawn from clustering of the graph is drawn in (B) from which $\eta_3$ is selected by using the size-based scoring function described in <ref> with $\mu$=3. The subgraph representing the subtree rooted at $\eta_3$ is highlighted in (C) and contains 5 boundary edges (drawn in red). (D) illustrates a new grammar rule constructed with size-five LHS and an RHS copied from the highlighted subgraph under $\eta_3$. Finally, the extracted subgraph and selected subtree are contracted and replaced by the nonterminal node from the LHS of the newly created rule in (E) and (F). This process then repeats until the dendrogram is empty, yielding us the set of rules shown in <ref>.

Before discussing generation, we examine AVRGs extracted from two real graphs with distinct attribute mixing patterns.

§.§ Case Study I: Examining AVRG Rules

The citation network consists of about $2500$ papers spread across $7$ different fields of Machine Learning, which are represented by colors on the nodes.
In <ref>(A), we observe that not all classes are represented equally; for example, $27\%$ nodes are red while only $5\%$ nodes are blue.
The edge mixing patterns based on the node attributes in <ref>(B) reflect strong homophily, with most edges spanning between papers (nodes) in the same field (color), as evidenced by high values on the main diagonal as well as the high value of $\rho_{\text{attr}} = 0.764$.
We expect the RHS subgraphs of the grammar rules extracted from Cora to capture this phenomenon.
Indeed, in <ref>(C), we find that each of the $6$ most frequent subgraphs consists of nodes belonging to the same class (color). Moreover, the top three rules all involve the red nodes, which is expected since $22\%$ of the edges in the network span between red nodes.

Chameleon. The Chameleon Wikipedia network consists of about $2500$ webpages on Wikipedia, which fall under the topic Chameleon.
The nodes are classified into $5$ (almost) quantiles based on their average monthly traffic, whose distribution is shown in <ref>(A).
The edge mixing patterns, in this case, is quite intriguing.
We see that nodes lying in the same quantile are not necessarily likely to be more connected to each other than others, resulting in a more uniform distribution of edges as seen in <ref>(B), resulting in the low attribute assortativity score of $0.032$.
The $6$ most frequent RHS subgraphs in the grammar rules reflect this disparity too; all but one rule consists of nodes from different classes, as seen in <ref>(C).

Thus, it is clear that the grammar rules reflect the mixing patterns observed in the input graph, which empirically validates our extraction procedure's efficacy.
Additionally, we can use the grammar rules to generate graphs which we describe next.

Cora. (A) Proportion of nodes in each class (color). (B) Attribute mixing matrix, each cell represents the percentage of edges with the corresponding colored endpoints. High numbers in the main diagonal and lack of off-diagonal edges indicate strong homophily. (C) The six most frequent rule RHS subgraphs of the extracted AVRG.

Chameleon. (A) Proportion of nodes in each class (color). (B) Attribute mixing matrix, each cell represents the percentage of edges with the corresponding colored endpoints. Almost uniform numbers in the matrix indicates heterophily. (C) The six most frequent rule RHS subgraphs of the extracted AVRG.

§ GRAPH GENERATION WITH AVRGS

The grammar $G$ encodes information about the original graph $H$, which can be used for various purposes. One compelling way to determine the faithfulness of a graph model is to use it to generate graphs.
How closely do these generated graphs resemble the original one? Is the model able to capture the nuances of mixing patterns across both degrees and attributes?
To answer these questions, we first describe a stochastic generative process that repeatedly applies rewriting rules to generate graphs.

Any new graph $H^\prime$ starts with $\mathcal{S}$, a size $0$ nonterminal.
An AVRG extracted using the extraction process outlined above is guaranteed to have a single size-$0$ starting nonterminal node because the grammar extraction only terminates when the root of the dendrogram covers all the nodes in the graph.
Then grammar rules are applied stochastically according to $f$ on available nonterminal nodes.

Precisely, each step of the generation process consists of three sequential parts: (a) choosing a nonterminal node from the current graph $H^\prime$, (b) choosing a suitable grammar rule from the grammar $G$, and (c) replacing the selected nonterminal in $H^\prime$ with the RHS subgraph of the selected rule, and rewiring it to the rest of the graph.
This process continues until no more nonterminals remain or until some predetermined graph size is reached.

§.§ Selecting a Grammar Rule

We pick a nonterminal $X$ of size $\omega$ at random from $H^\prime$ and find the set of grammar rules with the same LHS nonterminal, , of size $\omega$.
From that set of rules, we select a rule $\mathcal{R}$ stochastically according to frequency $f$ and connect the RHS into $H^\prime$.
This process prevents overfitting to the input graph and enables the model to flexibly generate diverse graphs that still resemble the original.

§.§ Choosing a Rewiring Policy

How the RHS is connected to the existing graph matters. The degree of the chosen nonterminal in $H^\prime$ will always match its size, , $\omega$. So, deleting $X$ from $H^\prime$ will break exactly $\omega$ edges (called broken edges) that then need to be rewired to nodes in the RHS.

Recall that each node in the RHS subgraph of $R$ was labeled with boundary degree $b_i$ during extraction, and the sum of all boundary degrees is equal to $\omega$. We will use this helpful property to guide the edge rewiring process.
Doing so helps us preserve the local connectivity patterns across the different regions of the graph, thereby increasing the fidelity of the output.
We consider three possible rewiring policies in the current work: (1) random rewiring, (2) mixing matrix, and (3) local greedy.

Random Rewiring. Each node $i$ in the RHS subgraph of $R$ receives exactly $b_i$ edges at random from the set of broken edges.

Mixing Matrix.
If we consider graph generation as a kind of reverse extraction process, from the top of the dendrogram moving downwards, then we can think of each RHS as introducing a new region/community of the graph–first at a macro-level and progressively refining the graph structure one rule at a time.

As their name implies, terminal nodes and their induced subgraph stay constant once they are introduced. We, therefore, distinguish two sets of terminal nodes: (1) terminal nodes in $H^\prime$, and (2) terminal nodes in the RHS subgraph of a rule that is being applied.

From among the terminal nodes in $H^\prime$, we select those which have edges that are broken. Then from the terminal nodes in the RHS of the rewriting rule, we select terminal nodes that have non-zero boundary degrees. Once we have identified these two sets, we use a Chung-Lu style edge rewiring policy that matches edges based on the attribute mixing matrix from the input graph.
For instance, if red nodes are twice as likely to connect to other red nodes as blue nodes in the input graph, we will use that probability to match red and blue nodes similarly during the rewiring process for the broken edges between the two terminal node sets.

Local Greedy. We compute an error function for each possible rewiring between two terminal nodes and greedily pick a rewiring configuration that minimizes the local error:

\begin{equation}
\epsilon = \beta \cdot |\rho^\prime_\text{deg} - \rho_\text{deg}| + (1 - \beta) \cdot |\rho^{\prime}_\text{attr} - \rho_\text{attr}|
\end{equation}

where $\rho_\text{deg}$ and $\rho^{\prime}_\text{deg}$ is the degree assortativity before and after the application of the rewiring policy, likewise for $\rho_{\text{attr}}$. We select $\beta \in \{0, 0.5, 1\}$, which mediates the weight between the two, and call the policies Greedy-Attr, Greedy-50, and Greedy-Deg respectively.

Rewiring policies over three metrics. Lower is better. We select the Mixing Matrix rewiring policy.

Selecting a Rewiring Policy. Among the many rewiring policies available to our model, it is crucial to choose one that generates graphs that contain mixing patterns that are faithful to the original graph. Based on the results from previous experiments, we choose the Leiden clustering and a size-based node selection strategy with $\mu=5$. Then we test the five rewiring policies with ten repetitions on each dataset in Table <ref>.

Figure <ref> illustrates the individual results for each trial and a corresponding box and whisker plot for $\lambda$-distance [Wilson and Zhu, 2008], $\Delta\rho_\text{deg}$, and $\Delta\rho_\text{attr}$ , absolute difference between the degree and attribute assortativity of the generated and original graphs, respectively (lower is better). Given the lack of a clear winner among the rewiring policies, we choose the mixing matrix one in the remainder of this work, given its flexibility.

The growth of an example graph (Texas) during generation. The Horizontal green line indicates the corresponding value in the original graph. The generated graph can be made to grow to an arbitrary size; the vertical black line represents the size of the input graph. This example shows how the metrics of the generated graphs slowly approach and eventually converge near ideal value as the generated graph approaches the original graph's size.

§.§ Observing the Generation Dynamics

Next, we inspect the graph generation process. Observing the growth of the generator provides a unique look at its underlying dynamics. Despite the temptation, it is important to not think of this generation process as a temporal one, but rather as a top-down filling-out. As new nodes and edges are added, the size of the graph grows, and we expect that the underlying topological and attribute mixtures will converge near the correct values.

Four views of graph generation on the Texas graph are shown in <ref>. In this example, the AVRG was extracted from the Texas graph using Leiden clustering. Rules were extracted using the size-based scoring policy ($\mu=5$), breaking ties randomly. In this example, the graph generator used the mixing matrix rewiring policy and was requested to grow to 250 nodes instead of 183, , we intentionally specified the new graph to be larger than the original. The difference between blue and red points shows the difference between the entire generated graph (treating terminal and nonterminal nodes as the same) versus just the terminal graph (ignoring nonterminal nodes and edges adjacent to nonterminal nodes). These values will eventually converge. When there are no more nonterminals, graph generation ceases.

Green horizontal lines in <ref> show the graph metrics from the original graph (except $\lambda$-distance, where 0 means perfect match). In this example, we asked the generative model to produce a graph with an extra 67 nodes. As rewriting rules are applied, the number of nodes gradually approaches 250. Likewise, the graph metrics converge to near the values of the input graph. The graph metrics remain relatively stable once the input size is reached–indicated by the vertical black line.

This example illustrates an important property of AVRGs: they can generate graphs of any large size, yet they continue to resemble the input graph.

Dataset summary statistics. $|V|$: # of nodes, $|E|$: # of edges, $|\mathcal{A}|$: # of unique attribute values, $\rho_{\text{deg}}$: degree assortativity coefficient, $\rho_{\text{attr}}$: attribute assortativity coefficient.

Name      $\mathbf{|V|}$        $\mathbf{|E|}$      $|\mathbf{\mathcal{A}}|$      $\mathbf{\rho_{\text{deg}}}$      $\mathbf{\rho_{\text{attr}}}$

Polbooks      105        441        3     $-$0.128      0.723

Football      115        613       12      0.162      0.608

Texas      183        279        5     $-$0.270     $-$0.294

Cornell      183        277        5     $-$0.249     $-$0.079

Wisconsin      251        450        5     $-$0.193     $-$0.173

Airports     1,183      22,459        4      0.168      0.356

Polblogs     1,222      16,714        2     $-$0.221      0.811

Citeseer     2,110       3,668        6      0.007      0.664

Chameleon     2,277      31,371        5     $-$0.200      0.032

Cora     2,485       5,069        7     $-$0.071      0.764

Squirrel     5,201     198,353        5     $-$0.227      0.007

Film     7,600      26,659        5     $-$0.047      0.003

§ GRAPH GENERATION RESULTS AND FINDINGS

We performed a thorough set of experiments that compared the graph generation performance of the AVRG model against several state-of-the-art graph models. Note that, just like in other graph grammar models, applying grammar rules in a tree-ordering over the dendrogram will permit the generation of an isomorphic graph to the input graph. However, this property of AVRGs is not particularly helpful in generating null graphs. Instead, our goal was to generate new graphs and determine if these new graphs shared similar topological and attribute properties with the input graphs.

Results on matching simulated scale-free graphs: AVRG best hugs the assortativity curve (CELL is a close contender) across the spectrum, while other models struggle.

Graph generation performance. Lower is better. 95% confidence intervals are not shown for clarity. The best and second best performing models are marked in boldface and underline respectively. Failures are marked with –. $\lambda$-dist: topological similarity, $\Delta \rho_{\text{deg}}$ and $\Delta \rho_{\text{attr}}$: difference in degree and attribute assortativities. 1 - $r$: Inverse Pearson Correlation Coefficient of colored graphlet counts. AVRG ranks in the top-2 for at least one metric across all datasets except Cora.

Methodology. We compared AVRGs against seven state-of-the-art graph generators. Many existing graph generators cannot handle attributed graphs, and many attributed graph generators do not scale to large sizes. The AVRG model can easily scale to extremely large graphs, but we opt to compare against other attributed models necessitating smaller graphs in this evaluation. Specifically, we compared against graph neural network models CELL [Rendsburg et al., 2020], NetGAN [Bojchevski et al., 2018], Graph Autoencoders [Kipf and Welling, 2016], and Variational Autoencoders [Simonovsky and Komodakis, 2018]. We also compared with classical, non-neural models such as the Degree Corrected Stochastic Block Model (DC-SBM) [Karrer and Newman, 2011], AGM [Pfeiffer III et al., 2014], and the base Chung-Lu model [Chung and Lu, 2002]. We used the best-performing hyperparameter settings for each of the baseline models.

All experiments were repeated ten times. The mean average of each metric for each model is reported. The 95% confidence intervals are not shown for clarity but usually lie within 5% of the mean. The AVRG model used the Leiden clustering algorithm to build the dendrogram, the size-based node selection strategy with $\mu=5$, and the Mixing Matrix rewiring policy for all results in this section.

§.§ Case Study II: CABAM Simulations

The CABAM model simulates scale-free graphs with varying attribute assortativity via a modified, attribute-aware preferential attachment process [Shah, 2020]. We generate graphs with $500$ nodes and degree distribution power-law exponent $\sim$3, and vary the inter-class assortativity ($p_c$) in increments of 0.05. Figure <ref> shows that for a majority of the attribute assortativity space, AVRG with the Hyperbolic hierarchical clustering (Leiden produces slightly worse results) can produce graphs matching the true values.
We observe that AVRGs and CELL are the standout performers, both tightly hugging the assortativity curve. Other graph models, including NetGAN (surprisingly), do poorly on this task. These results demonstrate that AVRG is capable of handling graphs across the spectrum of attribute assortativity.

§.§ Real-World Graphs

We evaluated the generation quality of the models by comparing both topological and attribute similarities with the original graphs.

We choose $\lambda$-distance to compare the topological fidelity instead of comparing degree and PageRank distributions because it is known to be more sensitive to topological variations [Wilson and Zhu, 2008].
We also computed the absolute difference between degree and attribute assortativity values to quantify similarity in mixing patterns.
Finally, we counted all connected and colored 2, 3, and 4-node graphlets (, edges, triangles, squares, kites) [Wernicke and Rasche, 2006].
We used the inverse of Pearson's correlation coefficient to compare each colored graphlet count vector (the inverse is taken so that lower is better–consistent with our other measures) as a way of measuring higher-order attribute mixing patterns. Because of the enormous number of possible colored graphlets, some of these counts could not be computed for the larger graphs.

The results on all 12 input graphs are aggregated in <ref>. Some models failed due to a combination of memory and model fitting issues. However, we can make the following observations.

CELL and AVRG are the standout performers, both consistently finishing in the top 2. CELL, being the state-of-the-art, performed admirably across all the datasets.
AVRG does particularly  well on disassortative graphs like Texas, Wisconsin, and Chameleon, in capturing topological and attribute mixing patterns. NetGAN, DC-SBM, AGM, and CL perform similarly well, while the autoencoders fail to reproduce the graphs faithfully.

§ CONCLUSIONS AND FUTURE WORK

The present work describes the attributed vertex replacement grammar (AVRG) model inspired by the context-free grammar formalism widely used in compilers and natural language processing. We described how an AVRG can be extracted from a hierarchical clustering of an attributed graph and then show that the model successfully encodes local topological structures. Starting with an empty graph, if we apply grammar rules stochastically, the model can generate a new graph. We show that the newly generated graphs are similar to the input graph, both topologically and in attribute mixing patterns.

Despite their straightforward design (, lacking supervision and a rich neural architecture), we demonstrate that AVRGs can often surpass state-of-the-art deep graph neural network generators' performance. We further demonstrate that the attributed graph rewriting rules encoded by the grammar can be interpreted to understand the local mixing patterns of the graph and how these substructures are pieced together.

These results open an exciting avenue for further exploration into attributed rewriting rules. One of the principal strengths of AVRGs is their ability to find the same rule repeatedly. For attributed graphs, combining identical grammar rules via rule isomorphism becomes less likely. As the number of unique attributes grows, the model size is likely to grow as well. Combining similar rules using graph kernel methods or other formalisms borrowed from formal language theory may be a particularly compelling avenue for further research. Additional work is also needed to extract actionable knowledge and interpret the simple patterns encoded in the grammar. Such tools could also be used to better understand specific graph datasets such as knowledge graphs, biological networks, and other complex systems containing a rich mixture of attributes and their patterns. We also intend to apply these techniques to solve additional downstream tasks like link prediction, graph summarization, and other critical graph modeling tasks.

This work is supported by a grant from the US National Science Foundation (#1652492).

[Sun and Han, 2013]
Yizhou Sun and Jiawei Han.
Mining heterogeneous information networks: a structural analysis
SIGKDD Explorations, 2013.

[Sun et al., 2011]
Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S Yu, and Tianyi Wu.
Pathsim: Meta path-based top-k similarity search in heterogeneous
information networks.
VLDB, 2011.

[Robins et al., 2007]
Garry Robins, Pip Pattison, Yuval Kalish, and Dean Lusher.
An introduction to exponential random graph (p*) models for social
Social networks, 2007.

[Leskovec et al., 2010]
Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and
Zoubin Ghahramani.
Kronecker graphs: An approach to modeling networks.
JMLR, 2010.

[Chung and Lu, 2002]
Fan Chung and Linyuan Lu.
The average distances in random graphs with given expected degrees.
PNAS, 2002.

[Karrer and Newman, 2011]
Brian Karrer and Mark EJ Newman.
Stochastic blockmodels and community structure in networks.
Phys. Rev. E, 2011.

[Hibshman et al., 2019]
Justus Hibshman, Satyaki Sikdar, and Tim Weninger.
Towards interpretable graph modeling with vertex replacement
In BigData. IEEE, 2019.

[Sikdar et al., 2019]
Satyaki Sikdar, Justus Hibshman, and Tim Weninger.
Modeling graphs with vertex replacement grammars.
In ICDM. IEEE, 2019.

[Aguiñaga et al., 2018]
Salvador Aguiñaga, David Chiang, and Tim Weninger.
Learning hyperedge replacement grammars for graph generation.
TPAMI, 2018.

[Sikdar et al., 2020]
Satyaki Sikdar, Daniel Gonzalez, Trenton Ford, and Tim Weninger.
The infinity mirror test for graph models.
arXiv preprint arXiv:2009.08925, 2020.

[Zhou et al., 2010]
Yang Zhou, Hong Cheng, and Jeffrey Xu Yu.
Clustering large attributed graphs: An efficient incremental
In ICDM, pages 689–698. IEEE, 2010.

[Perozzi et al., 2014]
Bryan Perozzi, Leman Akoglu, Patricia Iglesias Sánchez, and Emmanuel
Focused clustering and outlier detection in large attributed graphs.
In KDD, 2014a.

[Xu et al., 2019]
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.
How powerful are graph neural networks?
ICLR, 2019.

[Shah et al., 2016]
Neil Shah, Alex Beutel, Bryan Hooi, Leman Akoglu, Stephan Gunnemann, Disha
Makhija, Mohit Kumar, and Christos Faloutsos.
Edgecentric: Anomaly detection in edge-attributed networks.
In ICDMW. IEEE, 2016.

[Su et al., 2016]
Yu Su, Fangqiu Han, Richard E Harang, and Xifeng Yan.
A fast kernel for attributed graphs.
In SDM, pages 486–494. SIAM, 2016.

[Al-Rfou et al., 2019]
Rami Al-Rfou, Bryan Perozzi, and Dustin Zelle.
Ddgk: Learning graph representations for deep divergence graph
In WWW, pages 37–48, 2019.

[Tong et al., 2007]
Hanghang Tong, Christos Faloutsos, Brian Gallagher, and Tina Eliassi-Rad.
Fast best-effort pattern matching in large attributed graphs.
In KDD, 2007.

[Grahne and Zhu, 2005]
Gösta Grahne and Jianfei Zhu.
Fast algorithms for frequent itemset mining using fp-trees.
TKDE, 2005.

[Ahmed et al., 2015]
Nesreen K Ahmed, Jennifer Neville, Ryan A Rossi, and Nick Duffield.
Efficient graphlet counting for large networks.
In ICDM. IEEE, 2015.

[Yan and Han, 2002]
Xifeng Yan and Jiawei Han.
gspan: Graph-based substructure pattern mining.
In ICDM. IEEE, 2002.

[Sun et al., 2012]
Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li.
Efficient subgraph matching on billion node graphs.
VLDB, 2012.

[Hooi et al., 2016]
Bryan Hooi, Hyun Ah Song, Alex Beutel, Neil Shah, Kijung Shin, and Christos
Fraudar: Bounding graph fraud in the face of camouflage.
In KDD, 2016.

[Nilforoshan and Shah, 2019]
Hamed Nilforoshan and Neil Shah.
Slicendice: mining suspicious multi-attribute entity groups with
multi-view graphs.
In DSAA. IEEE, 2019.

[Perozzi et al., 2014]
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.
Deepwalk: Online learning of social representations.
In KDD, 2014b.

[Tang et al., 2015]
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.
Line: Large-scale information network embedding.
In WWW, 2015.

[Kipf and Welling, 2016]
Thomas N Kipf and Max Welling.
Semi-supervised classification with graph convolutional networks.
ICLR, 2016a.

[Veličković et al., 2018]
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero,
Pietro Lio, and Yoshua Bengio.
Graph attention networks.
ICLR, 2018.

[Dong et al., 2017]
Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami.
metapath2vec: Scalable representation learning for heterogeneous
In KDD, pages 135–144, 2017a.

[Gao and Huang, 2018]
Hongchang Gao and Heng Huang.
Deep attributed network embedding.
In IJCAI, 2018.

[Zhu et al., 2020]
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and
Danai Koutra.
Graph neural networks with heterophily.
arXiv preprint arXiv:2009.13566, 2020a.

[McPherson et al., 2001]
Miller McPherson, Lynn Smith-Lovin, and James M Cook.
Birds of a feather: Homophily in social networks.
Annu. Rev. Sociol., 2001.

[Newman, 2003]
Mark EJ Newman.
Mixing patterns in networks.
Physical review E, 2003.

[Zhu et al., 2020]
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai
Beyond homophily in graph neural networks: Current limitations and
effective designs.
Neurips, 33, 2020b.

[You et al., 2018]
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec.
GraphRNN: Generating realistic graphs with deep auto-regressive
In ICML, 2018.

[Simonovsky and Komodakis, 2018]
Martin Simonovsky and Nikos Komodakis.
Graphvae: Towards generation of small graphs using variational
In International Conference on Artificial Neural Networks.
Springer, 2018.

[Bojchevski et al., 2018]
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan
NetGAN: Generating graphs via random walks.
In ICML, 2018.

[Pfeiffer III et al., 2014]
Joseph J Pfeiffer III, Sebastian Moreno, Timothy La Fond, Jennifer Neville, and
Brian Gallagher.
Attributed graph models: Modeling network structure with correlated
In WWW, pages 831–842, 2014.

[Pfeiffer et al., 2012]
Joseph J Pfeiffer, Timothy La Fond, Sebastian Moreno, and Jennifer Neville.
Fast generation of large scale social networks while incorporating
transitive closures.
In Workshop on Privacy, Security, Risk and Trust. IEEE, 2012.

[Mussmann et al., 2014]
Stephen Mussmann, John Moore, Joseph J Pfeiffer, and Jennifer Neville III.
Assortativity in chung lu random graph models.
In Workshop on Social Network Mining and Analysis. ACM, 2014.

[Dong et al., 2017]
Yuxiao Dong, Reid A Johnson, Jian Xu, and Nitesh V Chawla.
Structural diversity and homophily: A study across more than one
hundred big networks.
In KDD, pages 807–816, 2017b.

[Akoglu et al., 2010]
Leman Akoglu, Mary McGlohon, and Christos Faloutsos.
Oddball: Spotting anomalies in weighted graphs.
In PAKDD. Springer, 2010.

[Ugander et al., 2012]
Johan Ugander, Lars Backstrom, Cameron Marlow, and Jon Kleinberg.
Structural diversity in social contagion.
PNAS, 2012.

[Cheng et al., 2014]
Justin Cheng, Lada Adamic, P Alex Dow, Jon Michael Kleinberg, and Jure
Can cascades be predicted?
In WWW, 2014.

[Yang et al., 2018]
Carl Yang, Xiaolin Shi, Luo Jie, and Jiawei Han.
I know you'll be back: Interpretable new user clustering and churn
prediction on a mobile social application.
In KDD, 2018.

[Aguiñaga et al., 2016]
Salvador Aguiñaga, Rodrigo Palacios, David Chiang, and Tim Weninger.
Growing graphs from hyperedge replacement graph grammars.
In CIKM. ACM, 2016.

[Dasgupta, 2016]
Sanjoy Dasgupta.
A cost function for similarity-based hierarchical clustering.
In STOC, 2016.

[Ravasz and Barabási, 2003]
Erzsébet Ravasz and Albert-László Barabási.
Hierarchical organization in complex networks.
Phys. Rev. E, 2003.

[Hagen and Kahng, 1992]
Lars Hagen and Andrew B Kahng.
New spectral methods for ratio cut partitioning and clustering.
IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 1992.

[Ng et al., 2002]
Andrew Y Ng, Michael I Jordan, and Yair Weiss.
On spectral clustering: Analysis and an algorithm.
In NeurIPS, pages 849–856, 2002.

[Chami et al., 2020]
Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré.
From trees to continuous embeddings and back: Hyperbolic hierarchical
arXiv preprint arXiv:2010.00402, 2020.

[Traag et al., 2019]
V. A. Traag, L. Waltman, and N. J. van Eck.
From Louvain to Leiden: guaranteeing well-connected communities.
Scientific Reports, 2019.

[Blondel et al., 2008]
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.
Fast unfolding of communities in large networks.
JSM, 2008.

[Rosvall et al., 2009]
Martin Rosvall, Daniel Axelsson, and Carl T Bergstrom.
The map equation.
The European Physical Journal Special Topics, 2009.

[Raghavan et al., 2007]
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara.
Near linear time algorithm to detect community structures in
large-scale networks.
Phys. Rev. E, 2007.

[Cordella et al., 2004]
Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento.
A (sub) graph isomorphism algorithm for matching large graphs.
PAMI, 2004.

[Wilson and Zhu, 2008]
Richard C Wilson and Ping Zhu.
A study of graph spectra for comparing graphs and trees.
Pattern Recognition, 410 (9):0 2833–2841,

[Rendsburg et al., 2020]
Luca Rendsburg, Holger Heidrich, and Ulrike Von Luxburg.
Netgan without gan: From random walks to low-rank approximations.
In International Conference on Machine Learning. PMLR, 2020.

[Kipf and Welling, 2016]
Thomas N Kipf and Max Welling.
Variational graph auto-encoders.
arXiv preprint arXiv:1611.07308, 2016b.

[Shah, 2020]
Neil Shah.
Scale-free, attributed and class-assortative graph generation to
facilitate introspection of graph neural networks.
In SIGKDD Workshop on Mining and Learning with Graphs, 2020.

[Wernicke and Rasche, 2006]
Sebastian Wernicke and Florian Rasche.
Fanmod: a tool for fast network motif detection.
Bioinformatics, 2006.