PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures

Peter Orbanz, Daniel M. Roy

arXiv:1312.7857v2math.STstat.ML

TL;DR

Many Bayesian tools assume exchangeable sequences, but modern data often take the form of graphs, matrices, arrays, or other random structures. The article develops representation-theorem foundations for Bayesian models of these structures, surveys models and applications, and identifies sparse networks as a key boundary where exchangeability is inadequate.

  • Problem

    Bayesian methods need a principled framework for structured data beyond exchangeable sequences, including graphs, matrices, arrays, and networks.

  • Method

    The article interprets and generalizes de Finetti-style representation theorems, especially the Aldous-Hoover framework, to derive parametrizations and Bayesian models for exchangeable random structures.

  • Results

    Representation theorems characterize model classes and parametrizations for exchangeable structures, while the article surveys corresponding graph, relational, array, and function-based models.

  • Takeaways & Limitations

    Exchangeability supplies a general foundation for Bayesian modeling of many structured data types, but sparse networks require approaches beyond exchangeable models.

Abstract

from arXiv · show

The natural habitat of most Bayesian methods is data represented by exchangeable sequences of observations, for which de Finetti's theorem provides the theoretical foundation. Dirichlet process clustering, Gaussian process regression, and many other parametric and nonparametric Bayesian models fall within the remit of this framework; many problems arising in modern data analysis do not. This article provides an introduction to Bayesian models of graphs, matrices, and other data that can be modeled by random structures. We describe results in probability theory that generalize de Finetti's theorem to such data and discuss their relevance to nonparametric Bayesian modeling. With the basic ideas in place, we survey example models available in the literature; applications of such models include collaborative filtering, link prediction, and graph and network analysis. We also highlight connections to recent developments in graph theory and probability, and sketch the more general mathematical foundation of Bayesian methods for other types of data beyond sequences and arrays.

I. INTRODUCTION

The article extends Bayesian modeling beyond exchangeable sequences to graphs, matrices, arrays, and other random structures by using representation theorems. These results characterize valid model classes and parametrizations while connecting theory to practical models and applications.

  • Graph models: For exchangeable graphs, distributions are characterized by functions from [0, 1]2 to [0, 1], with each function defining a graph distribution.Such functions are commonly used as graph model parameters.
  • Graph models: Exchangeable graph density estimation becomes regression for recovering the function parameter, supporting Bayesian priors on random functions and both finite- and infinite-dimensional models.Finite-dimensional function spaces yield parametric models, while infinite-dimensional spaces yield nonparametric models.
  • Arrays and matrices: For exchangeable two-dimensional real-valued arrays, distributions are characterized by distributions on functions from [0, 1]3 to R.Graphs are a special case of matrices, motivating the broader array formulation.
  • Scope and motivation: Representation theorems generalize key aspects of de Finetti’s theorem to exchangeable random structures, including sequences, graphs, partitions, arrays, and trees.They explain how to interpret probability results as statistical modeling tools.
  • Modeling implications: The article surveys Bayesian models for graph and relational data, explains their construction through the Aldous-Hoover theorem, and connects them to graph limits and sparse-network questions.Applications include collaborative filtering, link prediction, and graph and network analysis.

A. Basic example: Exchangeable sequences

Exchangeability makes a sequence conditionally i.i.d. given a directing random measure, enabling Bayesian inference through a prior over distributions. The resulting convergence guarantees depend on model compatibility and do not provide general convergence rates.

  • Definition and representation: An infinite sequence is exchangeable when its joint distribution is invariant under permutations of its elements.This symmetry is the defining property used in de Finetti’s theorem.
  • Definition and representation: De Finetti’s theorem represents every exchangeable sequence as conditionally i.i.d. given a random probability measure Θ.The distribution of Θ is the mixing measure, or de Finetti measure, and determines the sequence distribution.
  • Bayesian inference: The representation samples Θ from a prior distribution and then samples the observations independently from Θ.This two-stage procedure provides the Bayesian modeling interpretation of exchangeability.
  • Bayesian inference: Empirical distributions converge almost surely to the generating distribution, allowing observations to be pooled for inference about the unknown distribution.The statistical model can be specified as a subset of the space of probability measures.
  • Limitations: Posterior convergence to the generating distribution is guaranteed only when the data-generating prior matches the prior used for modeling.With a different prior, posterior convergence still occurs but need not identify the true generating measure.
  • Limitations: Exchangeability alone gives no guidance for choosing the prior and provides no general convergence rates beyond first-order convergence.Further modeling assumptions are required for these questions.

B. The general form of exchangeability results

Representation theorems generalize de Finetti’s framework from sequences to exchangeable random structures, identifying model parameters, observation distributions, and asymptotic limits. Exchangeable partitions illustrate the framework through paint-box sampling and recovery of block-size parameters.

  • B. The general form of exchangeability results: Many datasets are better represented as graphs, matrices, arrays, trees, or partitions than as sequences, motivating broader exchangeability concepts.
  • B. The general form of exchangeability results: An infinite random structure provides the asymptotic object, while a finite observation is modeled as a corresponding substructure.
  • B. The general form of exchangeability results: Exchangeability is defined by invariance under specified component permutations, such as jointly permuting rows and columns of an infinite matrix.
  • B. The general form of exchangeability results: Representation theorems identify a natural parameter space and ergodic distributions, with every exchangeable structure represented as a mixture of those distributions.
  • B. The general form of exchangeability results: For Bayesian modeling, priors live on the natural parameter space, while ergodic measures determine the admissible observation models.
  • B. The general form of exchangeability results: Convergence results allow parameters to be recovered almost surely from samples and interpreted as possible limit objects; finite-dimensional parameter spaces yield parametric models, while infinite-dimensional ones yield nonparametric models.
  • C. Exchangeable partitions: An exchangeable partition is a random partition of the natural numbers whose distribution is invariant to index permutations and depends on relative block sizes rather than labels.
  • C. Exchangeable partitions: Kingman’s representation samples uniform variables, groups indices whose variables fall in the same interval, and recovers paint-box weights asymptotically as limiting relative block sizes.This extends de Finetti’s representation: a single observed partition can reveal its parameter asymptotically, unlike an arbitrary random partition.

D. “Non-exchangeable” data

Exchangeability can be imposed on components of structured or temporal data rather than on observations themselves. Representation theorems then express these processes as mixtures of simpler exchangeable or ergodic processes.

  • Exchangeability beyond sequences: Time-series observations may be non-exchangeable, while model components such as latent variables can remain exchangeable.The relevant modeling choice is which components of the overall model satisfy exchangeability.
  • Continuous-time processes: An exchangeable continuous-time process has exchangeable increments over disjoint intervals of equal length.This generalizes the i.i.d.-increment characterization of Lévy processes.
  • Continuous-time processes: A piece-wise continuous exchangeable continuous-time process is a mixture of Lévy processes.Its ergodic measures correspond to Lévy-process distributions, while the mixing measure distributes over Lévy characteristics.
  • Discrete-time processes: Markov exchangeability depends on initial states and transition counts rather than transition order, and recurrent processes with this property are mixtures of Markov chains.Using such processes as latent variables in hidden Markov models can express more general dependencies than Markov exchangeability alone.
  • Random functions: Exchangeable sequences can be represented using a random function F applied to i.i.d. uniform variables, extending the random-measure view of de Finetti’s theorem.This function representation is useful because it generalizes to array-valued data, unlike the random-measure representation.

III. EXCHANGEABLE GRAPHS, MATRICES, AND ARRAYS

Random arrays generalize sequences to matrices and graphs, with exchangeability defined by invariance under row and column permutations. The Aldous–Hoover theorem represents these arrays through random functions and latent uniform variables.

  • Arrays and exchangeability: Random arrays include matrices and graphs, and finite observations are interpreted as sub-arrays of an underlying infinite structure.A graph with n vertices is treated as a random induced subgraph of an infinite graph.
  • Arrays and exchangeability: Joint exchangeability requires invariance under simultaneous row and column permutations, whereas separate exchangeability permits independent permutations.The appropriate notion depends on whether rows and columns represent one entity set or two distinct entity sets.
  • Joint exchangeability: The Aldous–Hoover theorem represents jointly exchangeable arrays using a random function F:[0,1]3→X and independent i.i.d. uniform latent variables.The representation uses one sequence of vertex-level variables and an array of pair-level variables, both independent of F.
  • Separate exchangeability: Separately exchangeable arrays use two independent latent sequences for rows and columns, together with pair-indexed uniform variables.The index structure of the latent variables is the key distinction from the jointly exchangeable representation.
  • Applications: Separate exchangeability models user–movie score matrices because their distribution is invariant to independently reordering users and movies.Scores may be binary or take a finite range such as one to five stars.

B. Exchangeable Graphs

Exchangeable graphs are random graphs invariant to vertex relabeling and can be represented by random graphons. This turns graph modeling and density estimation into inference on functions, with Bayesian models specified by graphon priors.

  • Definition: An exchangeable graph is invariant in distribution under permutations of its countably infinite vertex set.Equivalently, its adjacency matrix is jointly exchangeable under simultaneous row and column permutations.
  • Representation: A graph sample is generated by drawing W, assigning independent uniform Ui values to vertices, and sampling edges using W(Ui,Uj) with pair-specific randomness.For simple graphs, the resulting adjacency matrix is symmetric with a zero diagonal.
  • Representation: Every exchangeable simple graph is represented by a random symmetric graphon W:[0,1]2→[0,1].The graphon parametrizes the ergodic distributions of exchangeable simple graphs.
  • Bayesian modeling: Bayesian models of exchangeable simple graphs are characterized by prior distributions on graphons.Estimating an exchangeable graph distribution can therefore be formulated as recovering an unknown graphon, using Bayesian or frequentist methods.
  • Representation non-uniqueness: Graphon representations are non-unique because measure-preserving rearrangements of latent coordinates produce the same random-graph distribution.The illustrated block permutation applies the same permutation to rows and columns while preserving the distribution.
  • Beyond exchangeability: Graphon models can also incorporate covariates such as time by allowing W to depend on the covariate.For an evolving graph, the paper gives the example W(., ., t).

D. Uniqueness of representations

Graphon representations are generally non-identifiable: distinct functions can generate the same random graph, and monotonization does not always select a unique representative. The section also introduces exchangeable-array model classes built from partitions and random block values.

  • Uniqueness of representations: Distinct graphons can parametrize the same random graph, so the graphon is not identifiable as a model parameter.Estimation can nevertheless be formulated up to equivalence of functions.
  • Uniqueness of representations: Measure-preserving transformations preserve the generated random graph, producing weakly isomorphic graphons.For wφ(x,y)=w(φ(x),φ(y)), φ preserves uniform latent variables.
  • Uniqueness of representations: Monotonization does not yield a canonical graphon representation because identical one-dimensional projections can produce distinct transformed graphons.The examples in Fig. 6 have identical projections and transformations, yet remain different despite representing the same random graph.
  • Cluster-based models: Simple cluster-based array models partition rows and columns into classes with homogeneous relationships between each pair of classes.Their block values may themselves form an exchangeable array independent of the partitions.
  • Cluster-based models: Infinite-dimensional mixtures require partitions with arbitrarily many classes when finite class counts otherwise yield only finite-dimensional ergodic families.The IRM uses Chinese restaurant process partitions and beta-distributed block link probabilities.
  • Cluster-based models: Stick-breaking constructions create interval partitions whose rectangular products define piece-wise constant random functions.The construction uses weights Vk to form partitions of [0,1], with constant values on the resulting patches.

B. Feature-based models

Feature-based models extend clustering by allowing objects to belong to multiple overlapping features. Their interactions can depend on feature sets through feature-exchangeable link probabilities, with the LFRM providing a principal example.

  • Feature-based models: Feature-based models allow rows and columns to belong to multiple clusters simultaneously, unlike partition-based models.The shared features determine interactions between row and column objects.
  • Feature-based models: The LFRM allocates row and column features through Indian buffet processes and generates links from feature-pair weights.Positive weights increase, while negative weights decrease, the connection probability through a sigmoid transform.
  • Feature-based models: Fig. 7 contrasts directing functions for IRM, flexible cluster-based, LFRM, Mondrian, and Gaussian-process-based models.The first four visualizations truncate their stick-breaking constructions at finite depth.
  • Feature-based models: The LFRM construction produces exchangeable, projective subarrays, yielding an infinite array whose finite subarrays follow the described process.Exchangeability follows from the IBP and the conditional link-generation mechanism.
  • Feature-based models: Feature paint-boxes represent overlapping feature assignments, so an object may possess several features rather than exactly one partition block.Objects with identical feature sets can still induce a partition by equivalence.
  • Feature-based models: Feature-exchangeable arrays remain invariant under permutations of feature labels while allowing dependencies to reflect shared individual features.This relaxes exchangeability assumptions on block values used by simple cluster-based models.

C. Piece-wise constant models

Piece-wise constant models represent relationships through discrete partitions, including hierarchical axis-aligned partitions generated by Mondrian processes. These structures provide nonparametric priors over random functions.

  • Piece-wise constant models: Partition- and feature-based models are piece-wise constant because they posit prototypical relationships from discrete classes or feature assignments.Their block structure is induced by partitions of the unit interval.
  • Piece-wise constant models: Mondrian processes generate floorplan partitions of [0,1]^2 into axis-aligned rectangles through continuous-time hierarchical cuts.Each rectangle is split horizontally or vertically according to side-length-dependent probabilities.
  • Piece-wise constant models: The resulting Mondrian partitions are guillotine partitions, equivalent to the hierarchical axis-aligned partitions represented by kd-trees.Each partition is produced by a sequence of recursive cuts.
  • Piece-wise constant models: An extended Mondrian process on R^2 contains countably infinitely many rectangles almost surely for every positive time.This process supports a nonparametric prior on random functions after embedding latent coordinates into the partition.
  • Piece-wise constant models: Mixed-membership stochastic blockmodels are another prominent example of piece-wise constant modeling.

D. Gaussian-process-based models

Gaussian-process-based models place Gaussian-process priors on random functions underlying exchangeable arrays, including parametric eigenmodels and nonparametric extensions. Graph-limit results additionally provide empirical graphon convergence guarantees.

  • Gaussian-process-based models: Gaussian processes are specified by mean and positive semidefinite covariance functions, with suitable covariance choices yielding continuous sample functions almost surely.
  • Gaussian-process-based models: Gaussian-process-based exchangeable arrays use a Gaussian process on [0,1]^3 as the random function representing the array.A suitable likelihood randomization converts real-valued functions into binary arrays such as random graphs.
  • Gaussian-process-based models: The eigenmodel uses a Gaussian process whose covariance is based on inner products, while the Infinite Tucker Decomposition generalizes this structure through an RKHS kernel.The nonparametric extension replaces the finite-dimensional inner product with a potentially infinite-dimensional reproducing kernel Hilbert space.
  • Gaussian-process-based models: The article notes that Aldous-Hoover function parametrizations are nonunique and initially lack an analogue of de Finetti’s empirical-measure convergence result.Graph-limit theory supplies tools for addressing these representation and convergence gaps.
  • Gaussian-process-based models: An empirical graphon converts a finite graph’s adjacency matrix into a checkerboard function on [0,1]^2.
  • Gaussian-process-based models: The empirical graphons of successive sampled finite graphs converge weakly almost surely to the distribution defined by the generating graphon.This is the stated Kallenberg convergence theorem.

A. Metric definition of convergence

Graph convergence is defined through graphons and a cut-based pseudometric that identifies functions generating the same random graph. This framework also supports approximation and concentration results for finite graphs.

  • Metric construction: The cut metric measures convergence between graphon representations of graphs.It is built from the cut norm, which measures edge differences across vertex subsets.
  • Metric construction: Distinct graphons that generate the same random graph are identified through equivalence classes and rearrangements.The cut pseudometric is zero exactly when two graphons parametrize the same random graph.
  • Metric construction: A graph sequence converges when its empirical graphons approach a measurable graphon under the cut pseudometric.The limiting graphon is also called the graph limit.
  • Convergence theorem: Graph-limit convergence is equivalent to weak convergence of the random graph distributions induced by empirical graphons.This is stated as an if-and-only-if characterization.
  • Finite approximations: The weak regularity lemma approximates any graph by a weighted blow-up based on a partition into k vertex sets.The approximation is measured in cut distance, and the theorem applies to graphs of modest size relative to stronger regularity results.
  • Finite approximations: For cut-smooth graph statistics, sampling a finite subgraph yields concentration around a fixed value.This connects graph-limit results to estimating statistics such as edge density and to property testing.

VI. EXCHANGEABILITY AND HIGHER-DIMENSIONAL ARRAYS

Higher-dimensional exchangeable arrays are characterized by measurable functions of collections of i.i.d. latent variables indexed by multisets of coordinate indices. The representation generalizes the two-dimensional Aldous–Hoover construction and introduces increasingly many latent variables as dimension grows.

  • Joint exchangeability: Joint exchangeability requires invariance under simultaneous permutations of array indices.The higher-dimensional definition extends the symmetry used for two-dimensional arrays.
  • Joint exchangeability: A jointly exchangeable d-array is represented by a measurable function of i.i.d. uniform variables indexed by multisets of size at most d.The function takes one latent variable for each nonempty subset pattern encoded through multisets.
  • Special cases: For d = 2, the representation reduces to the familiar two-dimensional exchangeable-array construction.For d = 3, the representation uses seven latent variables associated with nonempty subsets of three indices.
  • Separate exchangeability: Separate exchangeability allows independent permutations of the array’s dimensions.Its representation uses i.i.d. uniform variables indexed by vectors rather than multisets.
  • Separate exchangeability: Jointly exchangeable arrays form a strict superset of separately exchangeable arrays for d ≥2.The separate case imposes additional equalities among latent variables.

B. Further generalizations

The framework extends to arrays whose dimensions are partitioned into classes, with permutations acting jointly within each class and separately across classes. General exchangeable arrays can also be approximated by simpler arrays, although the representation may require exponentially many latent variables.

  • π-exchangeability: π-exchangeability permits joint permutations within each dimension class and separate permutations across classes.Joint and separate exchangeability arise from particular choices of the partition π.
  • π-exchangeability: The partition framework recovers joint exchangeability when π = {[d]} and separate exchangeability when π = {{1}, . . . , {d}}.These are special cases of the same representation theory.
  • π-exchangeability: The representation of a π-exchangeable array uses i.i.d. uniform variables indexed by generalized vectors determined by the partition.Each jointly exchangeable class contributes a multiset of indices.
  • Simple approximations: Each observation in a sparsely observed d-array may require up to 2^d latent variables.Dense arrays reuse many latent variables through overlap, whereas sparse observations may not.
  • Simple approximations: Every π-exchangeable d-array admits a sequence of simple π-exchangeable approximations whose finite-subarray densities converge uniformly to 1.For each fixed finite subarray, the approximating and original distributions are mutually absolutely continuous.

VII. SPARSE RANDOM STRUCTURES AND NETWORKS

Exchangeability forces infinite graphs to be dense or empty, conflicting with the sparsity and structure of many real networks. The article discusses sparse modifications and broader symmetry-based decompositions while emphasizing unresolved statistical and modeling limitations.

  • Sparse random structures: Graph sparsity means O(n) edges, while density means Ω(n^2) edges as the number of vertices n grows.The classification depends on the growth rate of the edge count.
  • Sparse random structures: Exchangeable infinite graphs are either dense or empty, whereas many network datasets are sparse and exhibit power laws or small-world phenomena.This incompatibility makes ordinary exchangeable graph models inherently misspecified for such networks.
  • Sparse graph models: The BJR model generates sparse graphs by multiplying exchangeable edge probabilities by a rate such as ρ_n = 1/n.More general rate functions can be studied as n increases.
  • Sparse graph models: BJR sampling preserves a sparse edge count but cannot generate typical network structures such as power laws.It is equivalent to graphon sampling followed by independent edge deletion.
  • Beyond exchangeability: Integral decompositions extend from exchangeability to broader probabilistic symmetries defined by transformation groups.The ergodic decomposition theorem represents invariant distributions as mixtures of ergodic distributions.
  • Beyond exchangeability: Under stronger rotational and reflectional symmetry, Freedman’s theorem yields scale mixtures of zero-mean Gaussian distributions.The parameter is a positive variance and the mixture distribution is defined on R>0.

C. Stationary networks and involution invariance

Involution invariance offers a natural symmetry for network data, but its abstract characterization may not yield useful statistical models for sparse graphs. The broader characterization of statistically useful network symmetries remains open.

  • C. Stationary networks and involution invariance: Network location matters in many applications, so ordinary exchangeability is broken when conditioning on location is informative.Rooted graphs represent this location by marking a distinguished vertex.
  • C. Stationary networks and involution invariance: Involution invariance models network symmetry by requiring the rooted-graph distribution to remain unchanged when the root moves to a uniformly selected neighbor.This property admits an ergodic decomposition, paralleling a key feature of exchangeability.
  • C. Stationary networks and involution invariance: Although involution-invariant ergodic measures have been characterized, no comparably convenient representation to exchangeable-graph sampling is known.The paper also conjectures that involution invariance is too weak to yield interesting statistical models, without providing a proof.
  • C. Stationary networks and involution invariance: Characterizing a probabilistic symmetry whose ergodic measures describe useful sparse network models remains an open problem.The question arises because exchangeability and involution invariance are the only well-studied probabilistic symmetries for random graphs.
  • C. Stationary networks and involution invariance: Sparse random graph models can represent power laws and related network properties, but estimation is often intractable because edges are stochastically dependent.Some edge dependence is necessary to obtain power laws and similar properties.
  • C. Stationary networks and involution invariance: The surrounding theory connects exchangeable structures with graph limits, sufficient statistics, and foundational probability results by Aldous, Hoover, Kingman, and Kallenberg.Graph-limit theory provides an analytic route to the Aldous-Hoover representation for exchangeable graphs.
Loading 1312.7857v2…