## Spectral gap of Bayesian graph Laplacian

Warning: It's likely that known results in random matrix theory give some info about this problem, but I'm not familiar with random matrix theory.

The graph Laplacian of a finite connected undirected edge-weighted graph $$G$$ is the symmetric matrix $$A$$ whose off-diagonal entries $$a_{ij}$$ are the edge-weights and whose diagonal entries are $$a_{ii} = - \sum_{j \ne i} a_{ij}$$. The matrix $$A$$ has leading eigenvalue $$0$$ and second eigenvalue $$- \lambda_2$$, where this spectral gap $$\lambda_2$$ can be interpreted as a measure of connectivity.

Consider a given graph as above, which we now call $$G(\infty)$$, and write gap($$G(\infty)$$) for the spectral gap. For reasons indicated below we are interested in the process of random graphs $$( G(t), 0 \le t < \infty)$$ constructed in two stages as follows. For each edge $$e = ij$$ construct independently a Poisson counting process $$( N_{ij}(t), 0 \le t < \infty)$$ of rate $$a_{ij}$$. Conditional on these counts, let the edge-weights $$a_{ij}(t)$$ of $$G(t)$$ be independent with probability density functions $$s \to t^{-1} p(N_{ij}(t); st)$$ where $$p(k; \lambda)$$ denotes the Poisson( $$\lambda$$) probability function.

This is set up so that $$G(t) \to G(\infty)$$ as $$t \to \infty$$ but $$G(0)$$ is independent of $$G(\infty)$$; the edge-weights of $$G(0)$$ are independent Exponential(1) random variables.

Problem: What can you say about the (real-valued, random) process $$(\mbox{ gap }(G(t)), \ 0 \le t < \infty )$$ ? In particular:
(i) is the distribution of $$\mbox{ gap }(G(t))$$ concentrated near its expectation (under weak assumptions, and for large graphs)?
(ii) How large must $$t$$ be in order that $$\mbox{ gap }(G(t))$$ is close to $$\mbox{ gap }(G(\infty))$$ ?

This arises implicitly in Aldous-Li (2018) as a (very naive) Bayesian version of an "imperfectly observed network" model. In the frequentist version (discussed in that paper) the edge-weights are unknown constants and only the Poisson counts are observed; in the Bayes version one could put a flat prior on the edge-weights, and then $$G(t)$$ is the posterior distribution on weighted graphs. We would like to compare frequentist and Bayesian estimates of the spectral gap.

Back to Open Problem list