Graphons, mergeons, and so on!

In this work we develop a theory of hierarchical clustering for graphs. Our modeling assumption is that graphs are sampled from a graphon, which is a powerful and general model for generating graphs and analyzing large networks. Graphons are a far richer class of graph models than stochastic blockmodels, the primary setting for recent progress in the statistical theory of graph clustering. We define what it means for an algorithm to produce the "correct" clustering, give sufficient conditions in which a method is statistically consistent, and provide an explicit algorithm satisfying these properties.

• Publication year

  2016

• Venue

  Neural Information Processing Systems

• Publication date

  2016-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1607.01718
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sparse Exchangeable Graphs and Their Limits via Graphon Processes

  2016cited by this paper
• Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

  2015cited by this paper
• Estimating network edge probabilities by neighborhood smoothing

  2015influential reference
• Sparse graphs using exchangeable random measures

  2014cited by this paper
• Exact Recovery in the Stochastic Block Model

  2014influential reference
• A Consistent Histogram Estimator for Exchangeable Graph Models

  2014cited by this paper
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

  2013cited by this paper
• Nonparametric graphon estimation

  2013cited by this paper
• Adaptive Density Level Set Clustering

  2011cited by this paper
• Noise Thresholds for Spectral Clustering

  2011cited by this paper
• Pruning nearest neighbor cluster trees

  2011cited by this paper
• Spectral clustering and the high-dimensional stochastic blockmodel

  2010cited by this paper
• Rates of convergence for the cluster tree

  2010cited by this paper
• Connectedness in graph limits

  2008cited by this paper
• Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing

  2007cited by this paper
• Limits of dense graph sequences

  2004cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Spectral partitioning of random graphs

  2001cited by this paper
• Probability and measure theory

  1999cited by this paper
• Consistency of Single Linkage for High-Density Clusters

  1981influential reference
• Large Networks and Graph Limits

  year unknowncited by this paper

• Transferrable Graphon-Based Detection of Adversarial Samples in Power Grid Networks

  2026cites this paper
• Graphon Neural Networks-Based Detection of False Data Injection Attacks in Dynamic Spatio-Temporal Power Systems

  2025cites this paper
• Continuous Social Networks

  2024cites this paper
• Does Graph Distillation See Like Vision Dataset Counterpart?

  2023cites this paper
• A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs

  2023cites this paper
• Graphon-based Synthetic Power System Model and its Application in System Risk Analysis

  2023cites this paper
• Discovering Graph Generation Algorithms

  2023cites this paper
• Statistica Sinica Preprint

  2022cites this paper
• SPECTRE : Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators

  2022cites this paper
• Implicit Graphon Neural Representation

  2022cites this paper
• Diffusion Models for Graphs Benefit From Discrete State Spaces

  2022cites this paper
• Convergence of Invariant Graph Networks

  2022cites this paper
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons

  2021influential citation
• Efficient Agony Based Transfer Learning Algorithms for Survival Forecasting

  2021cites this paper
• Structured Graph Learning for Clustering and Semi-supervised Classification

  2020cites this paper
• Persistence Enhanced Graph Neural Network

  2020cites this paper
• Sampling random graph homomorphisms and applications to network data analysis

  2019cites this paper
• Searching for Stage-wise Neural Graphs In the Limit

  2019cites this paper
• Identifiability of Nonparametric Mixture Models and Bayes Optimal Clustering

  2018cites this paper
• Graphon Games: A Statistical Framework for Network Games and Interventions

  2018cites this paper
• Graphon Games

  2018cites this paper
• A quest to unravel the metric structure behind perturbed networks

  2017cites this paper
• Distances and Isomorphism between Networks and the Stability of Network Invariants

  2017cites this paper
• Hierarchical Clustering

  2017cites this paper
• Spectral clustering in the dynamic stochastic block model

  2017cites this paper
• MIT Open Access Articles Hierarchical Clustering: Objective Functions and Algorithms

  year unknowncites this paper
• Curriculum Vitae Education

  year unknowncites this paper