Pith. sign in

REVIEW 3 major objections 5 minor 95 references

Modeling Graphs with Vertex Replacement Grammars

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper's central claim is that a vertex replacement grammar extracted from hierarchical clusterings compresses graphs better than state-of-the-art summarization models and generates graphs more faithfully than many state-of-the-art…

desk verdict A genuinely novel VRG extraction method with a subtle but load-bearing termination flaw in the generative model; worth serious review after the generator is fixed. read the letter →

arxiv 1908.03837 v2 pith:MWAI5WMH submitted 2019-08-11 cs.SI cs.FL

Satyaki Sikdar , Justus Hibshman , Tim Weninger This is my paper · ORCID
classification cs.SIcs.FL MSC 68R1068Q4205C82
keywords vertexreplacementgrammargraphgenerationsummarizationhierarchicalclusteringminimumdescriptionlengthboundarydegreegraphlets
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces CNRG, a graph grammar whose production rules are extracted automatically from a hierarchical clustering of an input graph. Each rule replaces a nonterminal node labeled by the number of edges leaving its cluster with a small labeled multigraph whose nodes carry their own boundary degrees. The authors claim that this grammar is a succinct yet faithful model of the graph's building blocks, and that stochastically applying its rules generates new graphs whose local and global properties resemble the original. If correct, it offers a scalable, explainable alternative to both graph summarization and neural graph generation.

What carries the argument

The central object is the Clustering-based Node Replacement Grammar (CNRG), whose rules are indexed by boundary degree. For a cluster of original nodes, $\omega$ counts the edges leaving the cluster; each terminal node in a rule's right-hand side is labeled by its own boundary degree, the number of edges connecting it to the outside. The extraction procedure is driven by the minimum-description-length principle: each candidate rule from the hierarchical clustering dendrogram is scored by the bits needed to store the rule plus the bits needed to store the graph given that rule, and the best-scoring subtree is contracted into a new nonterminal node, shrinking the graph until the dendrogram is empty. During generation, boundary degrees are the sole information used to reattach a rewritten subgraph, so the stochastic process reconstructs a large graph by matching local degrees of external connection.

What would settle it

Construct two graphs with identical cluster shapes and identical boundary-degree vectors, one in which each cluster attaches to a single central hub and another in which the same clusters attach diffusely to many different neighbors, extract a CNRG from each, generate graphs, and compare the generated graphs' graphlet counts or spectra to their originals; if the generated graphs cannot reproduce the hub-versus-diffuse distinction, the boundary-degree rewiring assumption is false.

Watch

Extended reading notes

Core claim

CNRG is a variant of a vertex replacement grammar. A production rule $X \to (R, f)$ rewrites a nonterminal node whose label is the integer $\omega$, the number of boundary edges of the cluster it stands for, into a right-hand-side labeled multigraph $R$; terminal nodes of $R$ are labeled by their boundary degrees, and $f$ is the number of times that rule occurred in the original graph. Extraction begins from any hierarchical clustering: every internal node of the dendrogram is a candidate rule, candidates are scored by a minimum-description-length objective that balances the size of the rule against the size of the graph it explains, and the best-scoring subtree is contracted into a new nonterminal node. Repeating this until the dendrogram is empty yields the grammar. Generation starts from a single nonterminal of size $0$ and repeatedly rewrites a nonterminal into a right-hand side, reconnecting the newly broken edges randomly but respecting each terminal node's boundary degree. The paper's claim is that the resulting model compresses the graph more than the compared summarization models and generates graphs that match the original on graphlet counts, graphlet correlation distance, spectral distance, and DeltaCon more faithfully than several widely used generators.

Load-bearing premise

The load-bearing assumption is that when a cluster of nodes is replaced by its rule, the only information needed to reattach it correctly is each node's boundary degree, so randomly rewiring edges to satisfy those counts preserves the graph's essential structure.

Editorial extensions

If this is right

  • CNRG extraction scales to graphs with high treewidth because it relies on hierarchical clustering rather than a tree decomposition, so it avoids the computational barrier that limits hyperedge replacement grammars on the tested datasets.
  • The description-length measurements imply the grammar is a genuine compression of the original graph: on the six larger datasets the reciprocal compression ratio $\mathrm{DL}(G)/\mathrm{DL}(H)$ ranges from 0.133 to 0.525, and in every case where a summarization baseline can run, CNRG has the smaller ratio.
  • Because the grammar stores each distinct rule once along with its frequency, repeated substructures anywhere in the graph are encoded by a single production, which is the mechanism that lets one grammar summarize an entire network.
  • In the reported generation experiments, CNRG matches the original graph on 2-, 3-, and 4-node graphlet counts and graphlet correlation distance more consistently than the other generators, while the degree-preserving Chung-Lu model remains better on spectral distance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If boundary-degree rewiring is a deliberate randomization rather than a bug, then CNRG-generated graphs are one sample from an ensemble of graphs that share the original's rule decomposition; quantifying the spread of this ensemble across many generations would show how much of the original's structure the grammar actually pins down.
  • The rule multiset itself can serve as a network fingerprint: comparing CNRGs extracted from two graphs, or from successive snapshots of a temporal graph, could reveal shared growth mechanisms or structural drift; the paper lists these as future work, not as established results.
  • Since CNRG preserves local graphlets well but trails the degree-based model on spectral distance, a natural testable extension is to rewire boundary edges with degree-corrected probabilities rather than uniformly, combining the grammar's local rules with the spectral fidelity of a configuration model.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The manuscript introduces CNRG, a variant of vertex replacement grammars, and gives an algorithm to extract a CNRG from any graph using hierarchical clustering. The grammar consists of production rules whose LHS labels are boundary degrees; extraction contracts subtrees, scores candidate rules using MDL-inspired criteria (size, level, local/global MDL), and iterates until the dendrogram is empty. The paper then defines a stochastic generation process that rewires boundary edges according to boundary degrees, and evaluates CNRG on seven datasets by comparing compression ratio against SUBDUE, SlashBurn, and VoG, and generation fidelity (graphlet counts, GCD, λ-distance, DELTACON) against ChungLu, HRG, DC-SBM, BTER, Kronecker, and a baseline labeled "VRG". The central claims are that CNRG compresses better than these summarization baselines and generates graphs more faithfully than many generation baselines.

Significance. If the technical issues are resolved, the paper would make a useful contribution: CNRG is an interpretable, automatically extractable graph model that avoids the tree-decomposition bottleneck of hyperedge replacement grammars, and the authors provide source code. The empirical study is broad, covering seven datasets and multiple compression and generation baselines, and the parameter study is repeated five times. Those strengths are real. However, the validity of the generation results depends on the well-definedness of the stochastic rewriting process, and the reported comparisons currently lack variance information and use a favorable model-selection protocol. I therefore view the central claims as defensible but not yet fully established.

major comments (3)
  1. [Section 4 (cf. Section 5.4)] The stochastic generation process is not well-defined because it can fail to terminate. A CNRG production's LHS label is only the boundary degree ω, and nothing in the formalism prevents a rule whose RHS contains a nonterminal with the same label as its LHS. For example, in the graph with edges a-b, a-c, c-d, b-e, after contracting {a,b} (boundary degree 2), the parent cluster {S,c} also has boundary degree 2, producing a rule with LHS 2 whose RHS contains a nonterminal labeled 2; the generator may then apply this rule to the nonterminal it just introduced, indefinitely. The instruction to "repeat this process until no more nonterminals exist" is therefore not a guaranteed terminating procedure. Please add an explicit tree-order or well-foundedness restriction to the generation algorithm in Section 4 (the remark in Section 5.4 about keeping a tree ordering is not part of the formal definition of the process) or prove that the extracted grammars always yield terminating derivations.
  2. [Section 5.4, Table 3] The generation evaluation reports only mean values, with no error bars or significance tests, even though the generator is stochastic and only five graphs are produced per condition; the standard error of these means is likely non-negligible. Moreover, the hyperparameter selection in Section 5.2 (choosing Leiden, Greedy Level + DL, and µ = 4) is performed on the same datasets as the final evaluation, so the reported favorable comparison may be optimistically biased. Please report standard deviations or confidence intervals and conduct model selection on held-out data or via nested validation.
  3. [Section 5.3, Table 2] The compression comparison is not on a common scale: SUBDUE, SlashBurn, and VoG each use their own description-length encoding, so the ratios DL(Model)/DL(H) are not directly commensurable. Because the paper's central claim is that CNRG compresses graphs better than these baselines, please provide a shared encoding or a robustness analysis showing the result is insensitive to the choice of encoding.
minor comments (5)
  1. [Table 3] The column label "VRG" presumably refers to the proposed method, which is named CNRG; please rename it to "CNRG" to avoid confusion with the general class of vertex replacement grammars.
  2. [Section 5.2, Figure 8] The text states that µ = 4 is selected because it "appears to generate reasonably small models with reasonable accuracy," but the figure only shows curves; please state the concrete quantitative criterion used to make this selection.
  3. [Section 2] The definition of the start symbol S is ambiguous: "S is the starting graph which is a non-terminal of size 0" should specify that S is a single nonterminal node labeled with ω = 0.
  4. [Section 3.3] The scoring function sη = |Vη| - µ can be negative for subtrees smaller than µ; please clarify whether such candidates are eligible for selection and how ties are resolved when several negative scores occur.
  5. [Figure 6] The text says that Spectral clustering gives "remarkably good graph generation, but bad compression," while the caption says that "Leiden performs the best consistently"; please align the caption with the results described in the text.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: CNRG is fitted to the training graph and evaluated in-sample, but the central comparisons are against external baselines; self-citations are not load-bearing.

full rationale

The paper's derivation chain is not circular in the sense of reducing a claimed prediction to its own inputs. The grammar rules are extracted from each graph H by contracting subtrees selected from a hierarchical clustering, and generation is then evaluated by comparing graphs sampled from the resulting CNRG back to H. This is an in-sample reconstruction task, which is standard for generative graph models; the paper claims fidelity rather than out-of-sample prediction. The key evaluation is comparative: CNRG is measured alongside independently fitted external models (ChungLu, BTER, Kronecker, HRG, DC-SBM) using common graphlet, spectral, and DELTACON metrics, so the central 'more faithful than many state-of-the-art generators' claim is not forced by construction. Rule frequencies and boundary-degree labels are fitted from H, but no separate quantity is renamed as a prediction; the frequencies are simply the model parameters. The invariant that the sum of RHS boundary degrees equals the LHS label omega is definitional and well-formedness-preserving, not a self-referential derivation. The paper cites prior HRG work by the same group (Aguiñaga et al., 2016, 2018) and Pennycuff et al. (2018), but those citations are contextual and provide baselines or analogy; the CNRG extraction and generation algorithm does not depend on an unverified result from those papers. No uniqueness theorem is imported from the authors' earlier work. One non-circular weakness is worth noting: Section 4's stochastic generator does not enforce a tree order, even though Section 5.4 remarks that 'Keeping a tree ordering over production rules in the CNRG will permit a generation close or isomorphic to the original graph.' Because LHS labels are only boundary degrees, a rule can introduce a nonterminal with the same label as its own LHS, risking non-termination. This is a correctness and well-definedness concern, not a circular reduction, so it does not raise the circularity score. Overall, the central claims have independent empirical content through external baselines, and the self-citations are not load-bearing.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central method relies on the choice of μ, the fitted rule frequencies, and the assumptions that hierarchical clusters are meaningful building blocks and that boundary degrees suffice for faithful generation. No new physical entities are introduced.

free parameters (2)
  • μ (maximum RHS node count) = 4
    Chosen in Section 5.2 by evaluating compression ratio and λ-distance for μ = 2,...,10 on all datasets; μ=4 selected as the best size-to-performance tradeoff.
  • rule frequencies f = per-rule counts of isomorphic occurrences in the graph
    In Section 3.2, when a rule is found that already exists, its frequency is incremented; the generation process in Section 4 samples rules proportionally to f, so these counts are fitted parameters that shape the generated graph distribution.
assumptions (3)
  • domain assumption The graph H can be hierarchically clustered such that clusters correspond to meaningful building blocks.
    Stated in Section 3: 'we assume that H can be clustered hierarchically and that regular substructures can be extracted as rules.'
  • domain assumption Random rewiring of broken edges respecting boundary degrees yields graphs similar to the original.
    Embedded in the generation algorithm in Section 4, which reconnects edges only by boundary degree counts without preserving the original attachment pattern.
  • domain assumption The description length formulas in Section 2 are an appropriate measure of model complexity for comparing different graph formalisms.
    The DL definition is authored in this paper; comparing DL ratios across SUBDUE, SlashBurn, VoG, and CNRG assumes these encodings are commensurable.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Modeling Graphs with Vertex Replacement Grammars." pith.science (2026). https://pith.science/paper/MWAI5WMH

@misc{pith2026190803837,
  author       = {Pith},
  title        = {Pith review of: Modeling Graphs with Vertex Replacement Grammars},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MWAI5WMH}},
  note         = {Machine review of arXiv:1908.03837}
}
read the original abstract

One of the principal goals of graph modeling is to capture the building blocks of network data in order to study various physical and natural phenomena. Recent work at the intersection of formal language theory and graph theory has explored the use of graph grammars for graph modeling. However, existing graph grammar formalisms, like Hyperedge Replacement Grammars, can only operate on small tree-like graphs. The present work relaxes this restriction by revising a different graph grammar formalism called Vertex Replacement Grammars (VRGs). We show that a variant of the VRG called Clustering-based Node Replacement Grammar (CNRG) can be efficiently extracted from many hierarchical clusterings of a graph. We show that CNRGs encode a succinct model of the graph, yet faithfully preserves the structure of the original graph. In experiments on large real-world datasets, we show that graphs generated from the CNRG model exhibit a diverse range of properties that are similar to those found in the original networks.

Figures

Figures reproduced from arXiv: 1908.03837 by the authors.

Figure 1
Figure 1. (A) An example graph can be decomposed into a CNRG. (B) An extracted CNRG containing four distinct rules, each with an LHS and RHS. The LHS is a single nonterminal node drawn as a square labeled with size ω (drawn inside the node). The RHS is a subgraph with nonterminal nodes drawn as squares and labeled (illustrated inside the node), terminal nodes labeled with the number of bound￾ary edges (drawn on top of the nod… view at source ↗
Figure 3
Figure 3. All possible rules that can be extracted [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 2
Figure 2. (A) Original graph H. (B) Dendrogram cre￾ated from a hierarchical clustering algorithm, leaves of this dendrogram are nodes of H. (C) Subtree η6 is selected. Leaf nodes and edges of the induced subgraph are drawn in blue; boundary edges are drawn in red. (D) Rule η6 extracted from the H. LHS is a nonterminal labeled by ω=5; RHS is the in￾duced subgraph of the nodes in η6 labeled with their boundary condition (i.e., … view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: CNRGs obtained from Fig. 2(B) with [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: The generation algorithm in action. An application of the rules (in tree-order according to [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: λ-distance (lower is better) and compres￾sion ratio (lower is better) for all runs (all µ, clus￾tering method, η ∗ selection policy) on all datasets. Results that are consistently in the bottom-left cor￾ner are best. Leiden performs the best consistently. This figure i…
Figure 7
Figure 7. Figure 7: Mean model size (left) and graph generation performance (right) for each [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: Mean model size (top), and graph generation performance (bottom) for each [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 9
Figure 9. Figure 9: Relative graphlet2 counts as a heatmap. The color intensity in each cell indicates disagree￾ment between the number of graphlets found in the generated graph and the number of graphlets found in the original graph. CNRG consistently performs the best. The grayed out co…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

95 extracted references · 75 canonical work pages

  1. [1]

    Agui \ n aga, R

    S. Agui \ n aga, R. Palacios, D. Chiang, and T. Weninger. Growing graphs from hyperedge replacement graph grammars. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pages 469--478. ACM, 2016

    2016

  2. [3]

    N. K. Ahmed, J. Neville, R. A. Rossi, and N. Duffield. Efficient graphlet counting for large networks. In Data Mining (ICDM), 2015 IEEE International Conference on, pages 1--10. IEEE, 2015

    2015

  3. [4]

    Baldesi, C

    L. Baldesi, C. T. Butts, and A. Markopoulou. Spectral graph forge: Graph generation targeting modularity. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pages 1727--1735. IEEE, 2018

    2018

  4. [5]

    V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 0 (10): 0 P10008, 2008

    2008

  5. [6]

    u gner, and S. G \

    A. Bojchevski, O. Shchur, D. Z \"u gner, and S. G \"u nnemann. Netgan: Generating graphs via random walks. arXiv preprint arXiv:1803.00816, 2018

    arXiv 2018

  6. [7]

    Chakrabarti, Y

    D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-mat: A recursive model for graph mining. In Proceedings of the 2004 SIAM International Conference on Data Mining, pages 442--446. SIAM, 2004

    2004

  7. [8]

    Chung and L

    F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences, 99 0 (25): 0 15879--15882, 2002

    2002

  8. [9]

    D. J. Cook and L. B. Holder. Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research, 1: 0 231--255, 1993

    1993

Show all 95 references
  1. [10]

    P. Elias. Universal codeword sets and representations of the integers. IEEE transactions on information theory, 21 0 (2): 0 194--203, 1975

    1975

  2. [11]

    Goyal and E

    P. Goyal and E. Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems, 151: 0 78--94, 2018

    2018

  3. [12]

    Grahne and J

    G. Grahne and J. Zhu. Fast algorithms for frequent itemset mining using fp-trees. IEEE transactions on knowledge and data engineering, 17 0 (10): 0 1347--1362, 2005

    2005

  4. [13]

    Grover and J

    A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855--864. ACM, 2016

    2016

  5. [14]

    P. D. Gr \"u nwald. The minimum description length principle. MIT press, 2007

    2007

  6. [15]

    Hagen and A

    L. Hagen and A. B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE transactions on computer-aided design of integrated circuits and systems, 11 0 (9): 0 1074--1085, 1992

    1992

  7. [16]

    Ho c evar and J

    T. Ho c evar and J. Dem s ar. A combinatorial approach to graphlet counting. Bioinformatics, 30 0 (4): 0 559--565, 2014

    2014

  8. [17]

    Jiang, F

    C. Jiang, F. Coenen, and M. Zito. A survey of frequent subgraph mining algorithms. The Knowledge Engineering Review, 28 0 (1): 0 75--105, 2013

    2013

  9. [18]

    Karrer and M

    B. Karrer and M. E. Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83 0 (1): 0 016107, 2011

    2011

  10. [19]

    N. S. Ketkar, L. B. Holder, and D. J. Cook. Subdue: Compression-based frequent pattern discovery in graph data. In Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, pages 71--76. ACM, 2005

    2005

  11. [20]

    T. N. Kipf and M. Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016

    2016 arXiv

  12. [21]

    T. G. Kolda, A. Pinar, T. Plantenga, and C. Seshadhri. A scalable generative graph model with community structure. SIAM Journal on Scientific Computing, 36 0 (5): 0 C424--C452, 2014

    2014

  13. [22]

    Koutra, U

    D. Koutra, U. Kang, J. Vreeken, and C. Faloutsos. Summarizing and understanding large graphs. Statistical Analysis and Data Mining: The ASA Data Science Journal, 8 0 (3): 0 183--202, 2015

    2015

  14. [23]

    Koutra, N

    D. Koutra, N. Shah, J. T. Vogelstein, B. Gallagher, and C. Faloutsos. Deltacon: principled massive-graph similarity function with attribution. ACM Transactions on Knowledge Discovery from Data (TKDD), 10 0 (3): 0 28, 2016

    2016

  15. [24]

    J. Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web, pages 1343--1350. ACM, 2013

    2013

  16. [25]

    Leskovec and A

    J. Leskovec and A. Krevl. SNAP Datasets : Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014

    2014

  17. [26]

    Leskovec, D

    J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11 0 (Feb): 0 985--1042, 2010

    2010

  18. [27]

    W. Lin, X. Xiao, and G. Ghinita. Large-scale frequent subgraph mining in mapreduce. In Data Engineering (ICDE), 2014 IEEE 30th International Conference on, pages 844--855. IEEE, 2014

    2014

  19. [28]

    Y. Liu, N. Shah, and D. Koutra. An empirical comparison of the summarization power of graph clustering methods. arXiv preprint arXiv:1511.06820, 2015

    2015 arXiv

  20. [29]

    Marcus and Y

    D. Marcus and Y. Shavitt. Rage--a rapid graphlet enumerator for large networks. Computer Networks, 56 0 (2): 0 810--819, 2012

    2012

  21. [30]

    Mussmann, J

    S. Mussmann, J. Moore, J. J. Pfeiffer, and J. Neville III. Assortativity in chung lu random graph models. In Proceedings of the 8th Workshop on Social Network Mining and Analysis, page 3. ACM, 2014

    2014

  22. [31]

    Mussmann, J

    S. Mussmann, J. Moore, J. J. Pfeiffer III, and J. Neville. Incorporating assortativity and degree dependence into scalable network models. In AAAI, pages 238--246, 2015

    2015

  23. [32]

    A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems, pages 849--856, 2002

    2002

  24. [33]

    Nijssen and J

    S. Nijssen and J. N. Kok. The gaston tool for frequent subgraph mining. Electronic Notes in Theoretical Computer Science, 127 0 (1): 0 77--87, 2005

    2005

  25. [34]

    Pennycuff, S

    C. Pennycuff, S. Sikdar, C. Vajiac, D. Chiang, and T. Weninger. Synchronous hyperedge replacement graph grammars. In International Conference on Graph Transformation, pages 20--36. Springer, 2018

    2018

  26. [35]

    J. J. Pfeiffer, T. La Fond, S. Moreno, and J. Neville. Fast generation of large scale social networks while incorporating transitive closures. In Privacy, Security, Risk and Trust (PASSAT), 2012 International Conference on and 2012 International Confernece on Social Computing ...

    2012

  27. [36]

    Pr z ulj

    N. Pr z ulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23 0 (2): 0 e177--e183, 2007

    2007

  28. [37]

    J. R. Quinlan and R. L. Rivest. Inferring decision trees using the minimum description lenght principle. Information and computation, 80 0 (3): 0 227--248, 1989

    1989

  29. [38]

    Ravasz and A.-L

    E. Ravasz and A.-L. Barab \'a si. Hierarchical organization in complex networks. Physical review E, 67 0 (2): 0 026112, 2003

    2003

  30. [39]

    Robins, P

    G. Robins, P. Pattison, Y. Kalish, and D. Lusher. An introduction to exponential random graph (p*) models for social networks. Social networks, 29 0 (2): 0 173--191, 2007

    2007

  31. [40]

    Rozenberg

    G. Rozenberg. Handbook of Graph Grammars and Comp., volume 1. World scientific, 1997

    1997

  32. [41]

    Simonovsky and N

    M. Simonovsky and N. Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks, pages 412--422. Springer, 2018

    2018

  33. [42]

    Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Efficient subgraph matching on billion node graphs. Proceedings of the VLDB Endowment, 5 0 (9): 0 788--799, 2012

    2012

  34. [43]

    J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067--1077. International World Wide Web Conferences Steering Committee, 2015

    2015

  35. [44]

    Thoma, H

    M. Thoma, H. Cheng, A. Gretton, J. Han, H.-P. Kriegel, A. Smola, L. Song, P. S. Yu, X. Yan, and K. M. Borgwardt. Discriminative frequent subgraph mining with optimality guarantees. Statistical Analysis and Data Mining: The ASA Data Science Journal, 3 0 (5): 0 302--318, 2010

    2010

  36. [46]

    R. C. Wilson and P. Zhu. A study of graph spectra for comparing graphs and trees. Pattern Recognition, 41 0 (9): 0 2833--2841, 2008

    2008

  37. [47]

    Yan and J

    X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on, pages 721--724. IEEE, 2002

    2002

  38. [48]

    J. You, R. Ying, X. Ren, W. L. Hamilton, and J. Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint arXiv:1802.08773, 2018

    2018 arXiv

  39. [49]

    In: CIKM, ACM, pp 469--478

    Agui \ n aga S, Palacios R, Chiang D, Weninger T (2016) Growing graphs from hyperedge replacement graph grammars. In: CIKM, ACM, pp 469--478

    2016

  40. [50]

    IEEE Trans on Pattern Analysis and Machine Intelligence pp 1--1, doi:10.1109/TPAMI.2018.2810877

    Agui \ n aga S, Chiang D, Weninger T (2018) Learning hyperedge replacement grammars for graph generation. IEEE Trans on Pattern Analysis and Machine Intelligence pp 1--1, doi:10.1109/TPAMI.2018.2810877

    2018

  41. [51]

    In: ICDM, IEEE, pp 1--10

    Ahmed NK, Neville J, Rossi RA, Duffield N (2015) Efficient graphlet counting for large networks. In: ICDM, IEEE, pp 1--10

    2015

  42. [52]

    In: INFOCOM, IEEE, pp 1727--1735

    Baldesi L, Butts CT, Markopoulou A (2018) Spectral graph forge: Graph generation targeting modularity. In: INFOCOM, IEEE, pp 1727--1735

    2018

  43. [53]

    Journal of statistical mechanics: theory and experiment 2008(10):P10008

    Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008(10):P10008

    2008

  44. [54]

    u gner D, G \

    Bojchevski A, Shchur O, Z \"u gner D, G \"u nnemann S (2018) N et GAN : Generating graphs via random walks. In: Dy J, Krause A (eds) ICML, Stockholm Sweden, vol 80, pp 610--619

    2018

  45. [55]

    In: SDM, SIAM, pp 442--446

    Chakrabarti D, Zhan Y, Faloutsos C (2004) R-mat: A recursive model for graph mining. In: SDM, SIAM, pp 442--446

    2004

  46. [56]

    Proceedings of the National Academy of Sciences 99(25):15879--15882

    Chung F, Lu L (2002) The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences 99(25):15879--15882

    2002

  47. [57]

    Journal of Artificial Intelligence Research 1:231--255

    Cook DJ, Holder LB (1993) Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research 1:231--255

    1993

  48. [58]

    IEEE Trans on Information Theory 21(2):194--203

    Elias P (1975) Universal codeword sets and representations of the integers. IEEE Trans on Information Theory 21(2):194--203

    1975

  49. [59]

    Knowledge-Based Systems 151:78--94

    Goyal P, Ferrara E (2018) Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems 151:78--94

    2018

  50. [60]

    IEEE Trans on Knowledge and Data Engineering 17(10):1347--1362

    Grahne G, Zhu J (2005) Fast algorithms for frequent itemset mining using fp-trees. IEEE Trans on Knowledge and Data Engineering 17(10):1347--1362

    2005

  51. [61]

    In: SIGKDD, ACM, pp 855--864

    Grover A, Leskovec J (2016) node2vec: Scalable feature learning for networks. In: SIGKDD, ACM, pp 855--864

    2016

  52. [62]

    MIT press

    Gr \"u nwald PD (2007) The minimum description length principle. MIT press

    2007

  53. [63]

    IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems 11(9):1074--1085

    Hagen L, Kahng AB (1992) New spectral methods for ratio cut partitioning and clustering. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems 11(9):1074--1085

    1992

  54. [64]

    Bioinformatics 30(4):559--565

    Ho c evar T, Dem s ar J (2014) A combinatorial approach to graphlet counting. Bioinformatics 30(4):559--565

    2014

  55. [65]

    The Knowledge Engineering Review 28(1):75--105

    Jiang C, Coenen F, Zito M (2013) A survey of frequent subgraph mining algorithms. The Knowledge Engineering Review 28(1):75--105

    2013

  56. [66]

    Phys Rev E 83(1):016107

    Karrer B, Newman ME (2011) Stochastic blockmodels and community structure in networks. Phys Rev E 83(1):016107

    2011

  57. [67]

    In: Workshop on open source data mining: frequent pattern mining implementations, ACM, pp 71--76

    Ketkar NS, Holder LB, Cook DJ (2005) Subdue: Compression-based frequent pattern discovery in graph data. In: Workshop on open source data mining: frequent pattern mining implementations, ACM, pp 71--76

    2005

  58. [68]

    arXiv preprint arXiv:161107308

    Kipf TN, Welling M (2016) Variational graph auto-encoders. arXiv preprint arXiv:161107308

    2016

  59. [69]

    SIAM Journal on Scientific Computing 36(5):C424--C452

    Kolda TG, Pinar A, Plantenga T, Seshadhri C (2014) A scalable generative graph model with community structure. SIAM Journal on Scientific Computing 36(5):C424--C452

    2014

  60. [70]

    Statistical Analysis and Data Mining: The ASA Data Science Journal 8(3):183--202

    Koutra D, Kang U, Vreeken J, Faloutsos C (2015) Summarizing and understanding large graphs. Statistical Analysis and Data Mining: The ASA Data Science Journal 8(3):183--202

    2015

  61. [71]

    ACM Trans on Knowledge Discovery from Data 10(3):28

    Koutra D, Shah N, Vogelstein JT, Gallagher B, Faloutsos C (2016) Deltacon: principled massive-graph similarity function with attribution. ACM Trans on Knowledge Discovery from Data 10(3):28

    2016

  62. [72]

    In: TheWebConf, ACM, pp 1343--1350

    Kunegis J (2013) Konect: the koblenz network collection. In: TheWebConf, ACM, pp 1343--1350

    2013

  63. [73]

    http://snap.stanford.edu/data

    Leskovec J, Krevl A (2014) SNAP Datasets : Stanford large network dataset collection. http://snap.stanford.edu/data

    2014

  64. [74]

    Journal of Machine Learning Research 11(Feb):985--1042

    Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C, Ghahramani Z (2010) Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research 11(Feb):985--1042

    2010

  65. [75]

    IEEE Trans on Knowledge and Data Engineering 26(12):3077--3089

    Lim Y, Kang U, Faloutsos C (2014) Slashburn: Graph compression and mining beyond caveman communities. IEEE Trans on Knowledge and Data Engineering 26(12):3077--3089

    2014

  66. [76]

    In: ICDE, IEEE, pp 844--855

    Lin W, Xiao X, Ghinita G (2014) Large-scale frequent subgraph mining in mapreduce. In: ICDE, IEEE, pp 844--855

    2014

  67. [77]

    arXiv preprint arXiv:151106820

    Liu Y, Shah N, Koutra D (2015) An empirical comparison of the summarization power of graph clustering methods. arXiv preprint arXiv:151106820

    2015

  68. [78]

    Computer Networks 56(2):810--819

    Marcus D, Shavitt Y (2012) Rage--a rapid graphlet enumerator for large networks. Computer Networks 56(2):810--819

    2012

  69. [79]

    In: Workshop on Social Network Mining and Analysis, ACM

    Mussmann S, Moore J, Pfeiffer JJ, Neville III J (2014) Assortativity in chung lu random graph models. In: Workshop on Social Network Mining and Analysis, ACM

    2014

  70. [80]

    In: AAAI, pp 238--246

    Mussmann S, Moore J, Pfeiffer III JJ, Neville J (2015) Incorporating assortativity and degree dependence into scalable network models. In: AAAI, pp 238--246

    2015

  71. [81]

    In: NeurIPS, pp 849--856

    Ng AY, Jordan MI, Weiss Y (2002) On spectral clustering: Analysis and an algorithm. In: NeurIPS, pp 849--856

    2002

  72. [82]

    Electronic Notes in Theoretical Computer Science 127(1):77--87

    Nijssen S, Kok JN (2005) The gaston tool for frequent subgraph mining. Electronic Notes in Theoretical Computer Science 127(1):77--87

    2005

  73. [83]

    In: ICGT, Springer, pp 20--36

    Pennycuff C, Sikdar S, Vajiac C, Chiang D, Weninger T (2018) Synchronous hyperedge replacement graph grammars. In: ICGT, Springer, pp 20--36

    2018

  74. [84]

    In: Workshop on Privacy, Security, Risk and Trust, IEEE, pp 154--165

    Pfeiffer JJ, La Fond T, Moreno S, Neville J (2012) Fast generation of large scale social networks while incorporating transitive closures. In: Workshop on Privacy, Security, Risk and Trust, IEEE, pp 154--165

    2012

  75. [85]

    Bioinformatics 23(2):e177--e183

    Pr z ulj N (2007) Biological network comparison using graphlet degree distribution. Bioinformatics 23(2):e177--e183

    2007

  76. [86]

    Information and computation 80(3):227--248

    Quinlan JR, Rivest RL (1989) Inferring decision trees using the minimum description length principle. Information and computation 80(3):227--248

    1989

  77. [87]

    Phys Rev E 67(2):026112

    Ravasz E, Barab \'a si AL (2003) Hierarchical organization in complex networks. Phys Rev E 67(2):026112

    2003

  78. [88]

    Social networks 29(2):173--191

    Robins G, Pattison P, Kalish Y, Lusher D (2007) An introduction to exponential random graph (p*) models for social networks. Social networks 29(2):173--191

    2007

  79. [89]

    World scientific

    Rozenberg G (1997) Handbook of Graph Grammars and Comp., vol 1. World scientific

    1997

  80. [90]

    In: International Conference on Artificial Neural Networks, Springer, pp 412--422

    Simonovsky M, Komodakis N (2018) Graphvae: Towards generation of small graphs using variational autoencoders. In: International Conference on Artificial Neural Networks, Springer, pp 412--422

    2018

  81. [91]

    Proceedings of the VLDB Endowment 5(9):788--799

    Sun Z, Wang H, Wang H, Shao B, Li J (2012) Efficient subgraph matching on billion node graphs. Proceedings of the VLDB Endowment 5(9):788--799

    2012

  82. [92]

    In: TheWebConf, International World Wide Web Conferences Steering Committee, pp 1067--1077

    Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) Line: Large-scale information network embedding. In: TheWebConf, International World Wide Web Conferences Steering Committee, pp 1067--1077

    2015

  83. [93]

    Statistical Analysis and Data Mining: The ASA Data Science Journal 3(5):302--318

    Thoma M, Cheng H, Gretton A, Han J, Kriegel HP, Smola A, Song L, Yu PS, Yan X, Borgwardt KM (2010) Discriminative frequent subgraph mining with optimality guarantees. Statistical Analysis and Data Mining: The ASA Data Science Journal 3(5):302--318

    2010

  84. [94]

    Scientific Reports 9(1):5233, doi:10.1038/s41598-019-41695-z, ://doi.org/10.1038/s41598-019-41695-z

    Traag VA, Waltman L, van Eck NJ (2019) From Louvain to Leiden : guaranteeing well-connected communities. Scientific Reports 9(1):5233, doi:10.1038/s41598-019-41695-z, ://doi.org/10.1038/s41598-019-41695-z

    2019 doi

  85. [95]

    Pattern Recognition 41(9):2833--2841

    Wilson RC, Zhu P (2008) A study of graph spectra for comparing graphs and trees. Pattern Recognition 41(9):2833--2841

    2008

  86. [96]

    In: ICDM, IEEE, pp 721--724

    Yan X, Han J (2002) gspan: Graph-based substructure pattern mining. In: ICDM, IEEE, pp 721--724

    2002

  87. [97]

    In: Dy J, Krause A (eds) ICML, Stockholm Sweden, vol 80, pp 5708--5717

    You J, Ying R, Ren X, Hamilton W, Leskovec J (2018) G raph RNN : Generating realistic graphs with deep auto-regressive models. In: Dy J, Krause A (eds) ICML, Stockholm Sweden, vol 80, pp 5708--5717

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.