The Infinity Mirror Test for Graph Models
arXiv:2009.08925 · doi:10.1109/TKDE.2022.3140252
Abstract
Graph models, like other machine learning models, have implicit and explicit biases built-in, which often impact performance in nontrivial ways. The model's faithfulness is often measured by comparing the newly generated graph against the source graph using any number or combination of graph properties. Differences in the size or topology of the generated graph, therefore, indicate a loss in the model. Yet, in many systems, errors encoded in loss functions are subtle and not well understood. In the present work, we introduce the Infinity Mirror test for analyzing the robustness of graph models. This straightforward stress test works by repeatedly fitting a model to its own outputs. A hypothetically perfect graph model would have no deviation from the source graph; however, the model's implicit biases and assumptions are exaggerated by the Infinity Mirror test, exposing potential issues that were previously obscured. Through an analysis of thousands of experiments on synthetic and real-world graphs, we show that several conventional graph models degenerate in exciting and informative ways. We believe that the observed degenerative patterns are clues to the future development of better graph models.
arXiv commentAccepted in IEEE TKDE 2022, 12 pages and 8 figures
References in corpus (26)
- Emergence of scaling in random networks
- Benchmark graphs for testing community detection algorithms
- Hierarchical Organization in Complex Networks
- Stochastic blockmodels and community structure in networks
- Variational Graph Auto-Encoders
- Biological network comparison using graphlet degree distribution
- Kronecker Graphs: An Approach to Modeling Networks
- Graph Transformer Networks
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
- Learning Deep Generative Models of Graphs
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Community structure and scale-free collections of Erdös-Rényi graphs
- NetGAN: Generating Graphs via Random Walks
- Efficiently inferring community structure in bipartite networks
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- A Scalable Generative Graph Model with Community Structure
- An information-theoretic, all-scales approach to comparing networks
- Triadic closure dynamics drives scaling-laws in social multiplex networks
- Portraits of Complex Networks
- An In-Depth Analysis of Stochastic Kronecker Graphs
- Adapting the Stochastic Block Model to Edge-Weighted Networks
- Scalable Deep Generative Modeling for Sparse Graphs
- Modeling Graphs with Vertex Replacement Grammars
- Growing Graphs with Hyperedge Replacement Graph Grammars
- Towards Interpretable Graph Modeling with Vertex Replacement Grammars
- The Infinity Mirror Test for Analyzing the Robustness of Graph Generators