Is network reconstruction impossible?
I have been getting some questions about a 2018 paper [1] by Jinyuan Chang, Eric D. Kolaczyk, and Qiwei Yao that deals with reconstruction of noisy networks, i.e. networks that are measured with uncertainty, so that true edges may not be observed or fake ones may be spuriously introduced. Among other things, they state:
“Under a simple model of network error, we show that consistent estimation of [subgraph] densities is impossible when the rates of error are unknown and only a single network is observed.”
This seems like a contradiction of a paper of mine [2] where I presented a method to do precisely what is considered impossible in the above statement: reconstruct networks from single measurements, when the error rates are unknown. So, where lies the problem?
Let us begin by defining the reconstruction scenario, which is fairly simple. Suppose we observe a noisy network \(X\), obtained by measuring a true network \(A\), subject to the error rates \(p\) and \(q\), such that
\[\begin{aligned} P(X_{ij}|A_{ij},p,q) = \begin{cases} p^{1-X_{ij}}(1-p)^{X_{ij}}, & \text{ if } A_{ij} = 1,\\ q^{X_{ij}}(1-q)^{1-X_{ij}}, & \text{ if } A_{ij} = 0. \end{cases} \end{aligned}\]
In other words, \(p\) is the probability of observing a missing edge, and \(q\) is the probability of observing a spurious edge.
The reconstruction task is to obtain an estimate of \(A\) based only on \(X\), without knowing either \(p\) or \(q\). (Note that this reconstruction would also inherently give us an estimate for \(p\) and \(q\).)
Chang et al. consider estimators of subgraph densities that operate on the observed network \(X\), in a manner that makes no explicit assumption about how the data are generated. Essentially they claim that not knowing the true values of \(A\), \(p\), and \(q\), it is impossible to say anything about either of these values from \(X\) alone.
It is important to understand that it is not in fact possible to make “no assumptions” about how data are generated. Assumptions are always made; they can only be implicit or explicit. Implicit assumptions, i.e. those that are hidden from view, are not exempt from justification. So-called “frequentist” estimators that make no explicit reference to a prior distribution are in fact formally equivalent to Bayesian estimators with a uniform prior, i.e. assuming that all parameters values are equally likely. In the case where the parameter is a graph, this means that our prior expectation is that \(A\) is not only fully random, but in fact also dense, i.e. with a mean degree \(\left<k\right>=N/2\), where \(N\) is the number of nodes. Is this a reasonable assumption?
In [2] we take instead a Bayesian approach, where we are explicit about our assumptions, yielding a posterior distribution for the reconstruction,
\[P(A|X) = \frac{P(X|A)P(A)}{P(X)}.\]
In this setting, we can recover the “impossibility” result of Chung et al by choosing the prior \(P(A)\) as a constant. But this is not what should be done; instead we should choose a prior \(P(A)\) that makes as little commitment as possible about the network structure before we see any data. Note that this is very different from choosing a uniform prior! A uniform prior would in fact be a very strong commitment, that is overwhelmingly likely to be wrong in almost every empirical setting. Instead, we need a nonparametric hierarchical model that includes everything from fully random to very structured networks as special cases, in a manner that encapsulates the kinds of data that we are likely to find.
In order to illustrate intuitively why this makes sense, let us consider a particular instance of the problem. Suppose that, without knowing the true network \(A\) and the noise magnitudes \(p\) and \(q\), we observe the following noisy network \(X\):
From pure intuition, when observing the above network, we would like to immediately claim that it is close to the true network, and that the noise magnitudes are low. Why? Because we know that a perfect lattice is unlikely to be formed by chance alone (i.e. from a uniform prior). Our intuitive prior knows that such things called lattices exist, and that when they occur, they look exactly like the figure above. And also, when the true network is a lattice, a high value of either \(p\) or \(q\) would destroy its pristine structure. The final conclusion is that the reconstruction of this network is not only possible, but in fact not very difficult.
The work [2] puts the above intuition on firmer terms by choosing the prior \(P(A)\) to match an unknown stochastic block model (SBM) [3]. This model includes the “fully random” assumption as a special case, but is also capable of modelling a wide variety of structural patterns. Is this a realistic assumption? As it turns out, it is sufficiently generic to make the reconstruction possible in many cases, even when the model is not fully realistic.
As an example, we can consider the perfect lattice considered above. Below is the reconstructed version of this presumed noisy network, according to the method of [2] (see the HOWTO):
The thickness of the edge corresponds to the marginal posterior probability. Essentially, we conclude that the observed network is perfectly accurate, conforming to our intuition. The colors on the nodes shown above correspond to the node partition found with the SBM. Note that this is a very coarse and arguably displeasing generative model for this network, which would be generated by it with a very low probability. Nevertheless, even with such misspecification of the prior, the model is enough to detect that the underlying network is far from random, and enable reconstruction. The posterior estimates for the noise magnitudes are \(p=0.002(2)\) and \(q=3(3)\times10^{-7}\); indeed quite small. Not bad!
Of course, in [2] we consider situations where reconstruction is made for higher noise magnitudes, and also for real networks. But the above already serves to show that reconstruction from single measurements is indeed possible.
This should not be an earth-shattering conclusion. After all, single-measurement reconstructions of noisy images, time-series, and other high-dimensional objects are commonplace. Why not of networks? The key here is to abandon the idea that a network (like an image or a time-series) is a “singleton” \(N=1\) object, and instead view it as a heterogeneous population of objects — namely the individual edges and nodes. And we should make assumptions that, while being agnostic about which kinds of pattern there should be, also allow for them to be detected in the first place.
Comments