Computing Expected Motif Counts for Exchangeable Graph Generative Models

Oliver SchultearXiv 2023 · DOI · arXiv

Abstract

Calculating the expected number of subgraphs (motifs) in generative graph models typically relies on computationally expensive Monte Carlo sampling. This paper demonstrates that for exchangeable models with conditionally independent links, such as Variational Graph Auto-Encoders (VGAEs), the exact expected motif count can be computed directly from the "expected adjacency matrix" of edge probabilities. This approach eliminates the need for simulation, offering significant computational speedups.

Introduction

In network science, motifs—small, recurring subgraphs like triangles or stars—are fundamental building blocks of complex networks. Estimating the expected motif count is essential for model evaluation, training via moment-matching, and assessing statistical significance. Traditionally, this is achieved by generating thousands of sample networks and averaging their motif counts, a process that is often a major computational bottleneck.

Methodology: The Expected Graph Approach

The core contribution of this work is the proof that for a large class of popular generative models, the "expected value of the count" is equivalent to the "count of the expected values." Specifically, for models where edges are conditionally independent given a latent variable $Z$, the expected motif count can be calculated using the motif counting formula applied to a single weighted graph $\tilde{G}_z$. In this graph, edge weights represent the probability of an edge existing between two nodes.

Adjacency matrix representation used for expected graph calculations.

This result, formalized as Proposition 1, allows researchers to bypass Monte Carlo sampling entirely. If a motif count can be expressed through matrix algebra (e.g., using the trace of the adjacency matrix), one can simply substitute the binary adjacency matrix with the matrix of edge probabilities.

Ordered vs. Unordered Motifs

A key distinction in this research is between "ordered" and "unordered" motifs. While graph mining often focuses on unordered sets of nodes, many logical frameworks and relational databases count ordered tuples.

Table of ordered tuples representing motif occurrences.

The paper proposes a "Conjecture 1" to bridge this gap: the expected count for unordered motifs is the ordered count divided by the number of automorphisms (symmetries) of the motif graph. This allows the efficient matrix-based method to be applied to standard graph mining tasks.

Conclusion and Future Work

By providing a closed-form solution for expected motif counts, this work reduces the computational cost of motif inference by orders of magnitude. While the current method assumes conditional independence of edges—limiting its application to models like ERGMs—it provides a powerful tool for the evaluation and training of modern deep learning-based graph generators. Future work may involve formalizing the proof for the automorphism conjecture and exploring scalability for larger, more complex motifs.

Summary updated

Abstract

Estimating the expected value of a graph statistic is an important inference task for using and learning graph models. This note presents a scalable estimation procedure for expected motif counts, a widely used type of graph statistic. The procedure applies for generative mixture models of the type used in neural and Bayesian approaches to graph data.
BibTeX
@misc{schulte2023computing,
  author = {Oliver Schulte},
  title = {{Computing Expected Motif Counts for Exchangeable Graph Generative Models}},
  year = {2023},
  eprint = {2305.01089},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.01089},
}
Figure