It is widely thought that to understand gene function, genes must be studied in the context of networks. Concurrent with this appreciation of complexity – and partially driven by it – the quantity of data available has grown enormously, especially for networks of interactions among genes or their products. Such networks can consist of millions of interactions across tens of thousands of genes, derived from protein binding assays 
, RNA coexpression analysis 
and other methods 
. In systems biology, there is enormous interest in using high-throughput approaches to systematically glean information from these networks (e.g., 
). Information from such networks is now embedded in numerous studies and tools used by molecular biologists (e.g., 
), typically in combination with codifications of gene function exemplified by the Gene Ontology 
. If one agrees that the function of a gene is partially a property determined by its context or relationships in the network, assessing the functional role of any given gene is challenging, as in principle one must consider all the interactions of the gene, in the context of the network.
Biologists have dealt with these challenges in part by leveraging the biological principle commonly referred to as “guilt by association” (GBA). GBA states that genes with related function tend to be protein interaction partners or share features such as expression patterns 
. While not always referred to by name, GBA is a concept used extremely commonly in biology and which underlies a key way in which gene function is analyzed and discovered, whether on a gene-by-gene basis or using high-throughput methods. For example, an experimentalist who identifies a protein interaction infers a functional relationship between the proteins. Similarly two genes which interact genetically can be inferred to play roles in a common process leading to the phenotype 
. This basic biological principle has been exploited by computational biologists as a method for assigning function in general, using machine learning approaches 
. This is made possible by the development of large interaction networks, often created by aggregating numerous isolated reports of associations as well as from high-throughput data sets. It has been repeatedly shown that in such networks there is a very statistically significant relationship between, for example, shared Gene Ontology annotations and network edges. Indeed, this relationship has even been used to “correct” networks so they are more highly aligned with GO annotations 
, , on the assumption that parts of the network that do not align with known function are more likely to be mistaken. Tremendous effort has gone into improving computational GBA approaches for the purpose of predicting function 
. However, the number of biologically proven predictions based on such high-throughput approaches is still small and the promise of GBA as a general unbiased method for filling in unknown gene function has not come to fruition. In addition to their use in interpreting or inferring gene function, GBA approaches are also commonly used to assess the quality of networks, under the assumption that a high-quality network should map well onto known gene function information (see, for example, 
In computational applications of GBA, “performance” is usually assessed using cross-validation, in which known functions are masked from part of the network and the ability to recover the information is measured. A common metric is the precision with which genes sharing a function preferentially connect to one another 
; readers unfamiliar with prediction assessment methods are also referred to 
and Text S1
(section 1). Built into this approach is the key assumption that GBA performance allows one to make statements about the network as a whole.
Gene function is not the only way in which networks are assessed. Another popular approach is to examine structural properties of the network, such as the distribution of node degrees in the network (number of associations per gene). It has been observed that many biological networks show “scale-free-like” behaviour (as evidenced by a power-law distribution of node degrees), or other related characteristics resulting in a heavy-tailed distribution of node degrees 
. Similar to the situation for gene function, it is thought that a sign of high network quality is a power-law distribution of node degrees and some authors have even used this as a criterion for refining networks, on the assumption that data which conflicts with a power-law distribution is low-quality 
. The relationship between such properties and GBA has not been well-explored. While the significance of being scale-free is the subject of some debate 
, it is still commonly assumed that it reflects some more fundamental “biological relevance” of a network and contributes to the function of the network (and thus can be thought of “encoding functionality”). This paper represents an attempt to assess these types of assumptions, and in doing so derive some general principles about how function is “encoded” in current gene networks.
Previously, we showed that gene function can be predicted from networks without using “guilt”. We observed that a trivial ranking of genes by their node degrees results in surprisingly good GBA performance; about one-half of performance could be attributed entirely to node degree effects 
. Node degree is predictive because genes that have high node degree tend to have many functions (e.g. GO terms; we call such genes “highly multifunctional”). Thus for any given prediction task, algorithms that assign any given function to high node-degree genes are rewarded by good performance without using information on which genes are associated with which. More concretely, when studying any biological process, simply assuming P53 (for example) is implicated will go a surprisingly long way, and networks encode this completely generic information in their node degree.
In this paper, we show that multifunctionality has a second effect on the interpretation of gene networks, and one that has especially serious implications for the interpretation and utility of GBA, and more generally for current assumptions about the how networks encode function. We focus on the identification of small numbers of connections between multifunctional genes, representing “exceptional edges” that concentrate functional information in a small part of the network. We show that networks of millions of edges can be reduced in size by four orders of magnitude while still retaining much of the functional information. We go on to show that this effect guarantees that cross-validation performance of GBA as currently conceived is a useless measure of generalizability with respect to the ability to extract novel information. Further, because information about biological function is not encoded in the network systemically, the edges that do encode function may not overlap with those generating “important” network-level properties, such as whether the network is scale-free. We determine that as currently formulated, gene function information is not distributed in the network as is commonly assumed. Instead, almost all existing functional information is encoded either in a tiny number of edges involving only a handful of genes, or not at all. We conclude that computational attempts to scale up and automate GBA have failed to capture the essential elements that made it effective on a case-by-case basis.