An Exact No Free Lunch Theorem for Community Detection

A precondition for a No Free Lunch theorem is evaluation with a loss function which does not assume a priori superiority of some outputs over others. A previous result for community detection by Peel et al. (2017) relies on a mismatch between the loss function and the problem domain. The loss function computes an expectation over only a subset of the universe of possible outputs; thus, it is only asymptotically appropriate with respect to the problem size. By using the correct random model for the problem domain, we provide a stronger, exact No Free Lunch theorem for community detection. The claim generalizes to other set-partitioning tasks including core/periphery separation, $k$-clustering, and graph partitioning. Finally, we review the literature of proposed evaluation functions and identify functions which (perhaps with slight modifications) are compatible with an exact No Free Lunch theorem.


INTRODUCTION
A myriad of tasks in machine learning and network science involve discovering structure in data. Especially as we process graphs with millions of nodes, analysis of individual nodes is untenable, while global properties of the graph ignore local details. It becomes critical to find an intermediate level of complexity, whether it be communities, cores and peripheries, or other structures. Points in metric space and nodes of graphs can be clustered, and hubs identified, using algorithms from network science. A longstanding theoretical question in machine learning has been whether an "ultimate" clustering algorithm is a possibility or merely a fool's errand.
Largely, the question was addressed by Wolpert (1996) as a No Free Lunch theorem, a claim about the limitations of algorithms with respect to their problem domain. When an appropriate function is chosen to quantify the error (or loss), no algorithm can be superior to any other: an improvement across one subset of the problem domain is balanced by diminished performance on another subset. This is jarring at first. Are we not striving to find the best algorithms for our tasks? Yes-but by making specific assumptions about the subset of problems we expect to encounter, we can be comfortable tailoring our algorithms to those problems and sacrificing performance on remote cases.
As an example, the k-means algorithm for k-clustering is widely used for its simplicity and strength, but it assumes spherical clusters, equal variance in those clusters, and similar cluster sizes (equivalent to a homoscedastic Gaussian prior). Figure 1 shows the degraded performance on problems where these assumptions are violated.
To prove a No Free Lunch theorem for a particular task demands an appropriate loss function. A No Free Lunch theorem was argued for community detection (Peel et al., 2017), using the adjusted mutual information function (Vinh et al., 2009). 1 However, the theorem is inexact. A No Free Lunch theorem relies on a loss function which imparts generalizer-independence (formally defined below): one which does not assume a priori that some prediction is superior to another. The loss function used in the proof is only asymptotically independent in the size of the input. We present a correction: by substituting an appropriate loss function, we are able to claim an exact version of the No Free Lunch theorem for community detection. The result generalizes to other set-partitioning tasks when evaluated with this loss function, including clustering, k-clustering, and graph partitioning.

COMMUNITY DETECTION
A number of tasks on graphs seek a partition of the graph's nodes that maximizes a score function. Situated between the microscopic node-level and the macroscopic graph-level, these partitions form a mesoscopic structure-be it a core-periphery separation, a graph coloring, or our focus: community detection (CD). Community detection has been historically ill-defined (Radicchi et al., 2004;Yang et al., 2016), though the intuition is to collect nodes with high interconnectivity (or edge density) into communities with low edge density between them. The task is analogous to clustering, in which points near one another in a metric space are grouped together.
To assess whether the formulation of community detection matches one's needs, one performs extrinsic evaluation against a known ground truth clustering. This ground truth can come from domain knowledge of real-world graphs or can be planted into a graph as a synthetic benchmark. After running community detection on the graph, some similarity or error measure between the computed community structure and the correct one can be computed.
No bijection between true structure and graph Unfortunately, ground truth communities do not imply a single graph-and vice versa. Peel et al. (2017) go as far as to claim, "Searching for the ground truth partition without knowing the exact generative mechanism is an impossible task." We can imagine the following steps for how problem instances are created, given that we have N = |V | nodes: 1. Sample (true) partition T ∈ Ω; 2. Generate graph G from T by adding edges according to the edge-generating process g.
where Ω is our universe: the space of all partitions of N = |V | objects. Given a graph G = (V, E), we can imagine multiple truths T i ∈ Ω that could define its edge set E by different generative processes g i : Ω → Γ, where Γ is the set of all graphs with N nodes. Peel et al. (2017) give a proof that extends from this simple example: Imagine that T 1 partitions the N nodes into N components (the N-partition), and T 2 partitions them into 1 component (the 1-partition). Let g 1 exactly specify the number of edges between each pair of communities, such that g 1 (T 1 ) is G with probability 1. Similarly, let g 2 be an Erdős-Rényi model such that g 2 (T 2 ) is G with nonzero probability. (Peel et al. (2017) note that this is easily extended to graphs with more nodes.) We thus have two different ways to create a single graph; how can a method discern the correct one, without knowledge of g?
Community detection is then an ill-posed inverse problem: Use a function f : Γ → Ω to produce a clustering C = f (G), which is hopefully representative of T (Peel et al., 2017, Appendix C). 2 The function f is not a bijection, so there isn't a unique T represented in the given graph. Our algorithm f must encode our prior beliefs about the generative process g to select from among candidates. For this reason, we must hope that the benchmark graphs that we use are representative of the generative process for graphs in our real-world applications. That is, we hope that our benchmark domain matches our practical domain.
Other set-partitioning tasks While the remainder of this work focuses on community detection, our claims are relevant to other set-partitioning tasks. Notable examples are clustering (the vector space analogue to community detection), graph k-partitioning, and k-clustering. Metadata about the nodes and edges, such as vector coordinates, are used to guide the identification of such structure, but the tasks are all fundamentally set-partitioning problems. They can also have different universes Ω-the latter tasks have a smaller universe than does community detection, for a given graph G: They consider only partitions with a fixed number of clusters.

NO FREE LUNCH THEOREMS
The No Free Lunch theorem in machine learning is a claim about the universal (in)effectiveness of learning algorithms. Every algorithm performs equally well when averaging over all possible input-output pairs. Formally, for any learning method f , the error (or loss) L of the method f , summed over all possible problems (g, T ) equals a loss-specific constant Λ(L): defining the edge-generative process g and partition T as above. This loss is thus generalizerindependent. To reduce loss on a particular set of problems means sacrificing performance on others-"there is no free lunch" (Wolpert, 1996;Schumacher et al., 2001). Judiciously choosing which set to improve involves making assumptions about the distribution of the data: as we've mentioned, k-means is a method for k-clustering which works well on data with spherical covariance, similar cluster sizes, and roughly equal class sizes. When these assumptions are violated, performance suffers and overall balance is achieved.

COMMUNITY DETECTION AS SUPERVISED LEARNING
We follow Peel et al. (2017) in framing the task of community detection (CD) as a learning problem. While recent algorithms, e.g. , have introduced learnable parameters to community detection algorithms the CD literature's algorithms are by and large untrained. These untrained algorithms encode knowledge of the problem domain in prior beliefs. We note that our work and Peel et al. (2017) straightforwardly handle both of these cases.
In general supervised machine learning problems, we seek to learn the function that maps an input space X to an output space Y. We consider problem instances as sampled from random variables over each, so our goal is to learn the conditional distribution p(Y | X). In the process of training on a dataset D, we develop a distribution over hypotheses q which are estimates of the distribution p.
In the case of most community detection algorithms, our input space is the set of graphs on N nodes Γ, and the output space is ω. There is no training data: D = ∅. All of our prior beliefs about p must be encoded in the prior distribution Pr(q). That is, the model itself must contain our beliefs about the definition of community structure. Only from the encoded Pr(q) and an observed x ∈ X (our graph G) do we form our point estimate of the true distribution p (Peel et al., 2017). However, in the case of trainable CD algorithms, we encode our beliefs in the posterior distribution Pr(q | D).

LOSS FUNCTIONS AND A PRIORI SUPERIORITY
How should we evaluate an algorithm's predictions? Classification accuracy won't cut it: When comparing to the ground truth, there are no specific labels (e.g. no notion of a specific "Cluster 2")-only unlabeled groups of like entities. We settle for a measure of similarity in the groupings, quantifying how much the computed partition tells us about the ground truth.
A popular choice of measure is the normalized mutual information (NMI; Kvalseth, 1987) between the prediction and the ground truth. While this measure has a long history in community detection, its flaws have been well-noted (Vinh et al., 2009;Peel et al., 2017;McCarthy and Matula, 2018;McCarthy et al., 2019). It imposes a "geometric" structure upon the universe Ω, 3 so something as simple as guessing the trivial all-singletons clustering outperforms methods that try at all to find a mesoscopic-level structure (McCarthy et al., 2019). The property which NMI lacks is generalizerindependence.
The property of generalizer-independence is defined by the generalization error function, an expectation of the loss E[L | p, q, D]. To satisfy this property, the generalization error must be independent of the particular true value T . This is best expressed by Equation 1.
The adjusted mutual information (AMI, defined in section 3) (Vinh et al., 2009) is a proposed replacement for NMI which does not impose a geometric structure upon the space. Unfortunately, this benefit is not fully realized when the expectation is computed over a space Ψ ⊂ Ω. For the Ψ used in Peel et al. (2017), the expected AMI across all problems is only asymptotically generalizer-independent as the graph size grows-it is within some diminishing amount of error ε(N) of generalizer-independence, as proven by Peel et al. (2017). Peel et al. (2017) frame community detection in the style of learning algorithms, letting them prove a No Free Lunch theorem for community detection. They note that the claim holds for "an appropriate choice of . . . L"-specifically a loss function L that is generalizer-independent-but their chosen loss function is not fully generalizer-independent. They also consider a stricter property than generalizerindependence: homogeneity. With a homogeneous loss function, the distribution of the error (not just its expectation) is identical, regardless of the ground truth. A measure which deviates from homogeneity may have this deviation bounded by a function of the number of vertices (the graph order). Lemma 1 (Peel et al., 2017). Adjusted mutual information (AMI) is a homogeneous loss function over the interior of the space of partitions of N objects, i.e., excluding the 1-partition and the N-partition. Including these, AMI is homogeneous within 1 B N . 4

PREVIOUS RESULT: APPROXIMATE NO FREE LUNCH THEOREM
Wolpert (1996) gives a generalized No Free Lunch theorem, which assumes a homogeneous loss. Theorem 1 (Wolpert, 1996). But this choice of measure (AMI) is not, in fact, homogeneous over the entire universe Ω (Lemma 1). A strategy that guesses either of the non-interior (i.e., boundary) partitions-the 1-partition or Npartition-will yield a higher-than-average reward. There is indeed a negligible amount of free lunch-a free morsel, if you will.  Correcting this is arguably a pedantic demand, for two reasons: 1. The fraction 1 B N converges to 0 superexponentially as N increases. 2. The deficiency is only present when T is one of the trivial partitions. Otherwise, AMI as used is exactly homogeneous. But the trivial partitions reflect a lack of any mesoscopic community structure.
Nevertheless, we'd like to see a tight claim of generalizer independence. To do this, we must select the proper random model, a sample space for a distribution.
AMI adjusts NMI by subtracting the expected value from both the numerator and the denominator, shown in blue: where I is the mutual information, maximized when the specific clustering C equals the ground truth T . By inspecting Equation 2, we see that AMI's value is 1 (the maximum) when C = T , 0 in expectation, and negative when the agreement between C and T is worse than chance.
Subtly hidden in this equation is the decision of which distribution to compute the expectation over. For decades, this distribution has been what Gates and Ahn (2017) call M perm : all partitions of the same partition shape 5 as C or T . For example, if C partitioned 7 nodes into clusters of sizes 2, 2, and 3, then we would compute the expected mutual information over all clusterings where one had cluster sizes of 2, 2, and 3. McCarthy et al. (2019) argue that M perm is inappropriate. To use this random model assumes that we can only produce outputs within that restricted space, when in actuality Ω is the set of all partitions of N nodes. Furthermore, during evaluation, we hold our ground truth fixed, rather than marginalizing over possible ground truths. Were we to instead consider a distribution over T s, we would add noise from other possible generative processes which yield the same graph from different underlying partitions. In our average, we might be including scores on ground truths that better align with our notions of, say, core-periphery partitioning. For this reason, we take a one-sided expectation-over C, holding T fixed. The one-sided distribution over all partitions of N nodes is called M 1 all Gates and Ahn (2017). This distribution is what we use for our AMI expectation, giving a measure denoted as AMI 1 all , which is recommended by McCarthy et al. (2019). It takes the form AMI 1 all (C, T ) The differences between M all and M perm are illustrated in Figure 2 under |V | = 3. We will now show that substituting M all for M perm , hence using AMI 1 all , allows for an exact No Free Lunch theorem.

AN EXACT NO FREE LUNCH THEOREM
We strengthen the No Free Lunch theorem for community detection given by Peel et al. (2017) by using an improved loss function, AMI 1 all , for community detection. Our proof does not distinguish the "boundary" partitions (the two trivial partitions) from the "interior" partitions (the remainder). It is entirely agnostic toward the particular ground truth T , which is exactly what we need. We improve the previous result by moving from M interior (which excludes the boundary partitions) to M all .

GENERALIZER-INDEPENDENCE OF AMI 1 all
Lemma 2. AMI 1 all is a generalizer-independent loss function over the entire space M all of partitions of N objects.
Proof. Like Peel et al. (2017), we must show that the sum of scores is independent of T : where Ω is the space of all partitions of N objects. Unlike Peel et al. (2017), we take the AMI expectation over all B N clusterings in Ω using the random model M 1 all (Gates and Ahn, 2017). To prove our claim about Equation 4, we note that denominator of AMI 1 all is a constant with respect to C (Equation 3), so we can factor it out of the sum and restrict our attention to the numerator. This is because the max-term in the denominator is the constant log N (Gates and Ahn, 2017) and the expectation term for a given T is independent of the particular C. Having factored this out, we will now prove Equation 4 by the stronger claim: To prove Equation 5, we separate the summation's two terms: The expectation is uniform over the universe Ω, 6 so we can apply the law of the unconscious statistician, then push the constant probability out, to get Because the inner sum is independent of any particular C , the outer sum is a sum of constantsone for each element in Ω. We can now express Equation 5 as follows, where the reciprocals straightforwardly cancel out: This equivalence implies that Equation 4 is true.
The proof is valid without loss of generality vis-à-vis the distribution-that is, as long as the AMI expectation is computed uniformly over the problem universe Ω, AMI is a generalizer-independent measure. This stipulation is relevant to tasks which assume a fixed number of clusterings-using M num -like k-clustering and graph partitioning.
Having demonstrated the generalizer-independence of AMI, we can define our loss function as, say, The loss is zero when we exactly match the true clustering and positive otherwise.
Having proven the generalizer-independence of AMI 1 all , we now turn to a more general form of the No Free Lunch theorem, which admits not just a homogeneous loss function but any generalizerindependent loss. Theorem 3 (Wolpert, 1996). For generalizer-independent loss , the uniform average over all p, There is no free lunch.") Proof. See Wolpert (1996).
Theorem 4 (No Free Lunch theorem for community detection and other set-partitioning tasks). For a set-partitioning problem with a loss function of adjusted mutual information using the appropriate random model for the task, the uniform average over all p, E [ | p, D], equals Λ( ) |Y| .
Proof. Lemma 2 proves that AMI using the appropriate random model is generalizer-independent. Applying Theorem 3 completes the proof (Peel et al., 2017).

OTHER MEASURES
AMI stemmed from a series of efforts to improve normalized mutual information (NMI). We note that six other measures, when extended to M 1 all instead of M perm , are also generalizer-independent: the adjusted Rand index (ARI; Hubert and Arabie, 1985), relative NMI (rNMI; Zhang, 2015), ratio of relative NMI (rrNMI; , Cohen's κ (Liu et al., 2018), corrected NMI (cNMI Lai and Nardini, 2016), and standardized mutual information (SMI; Romano et al., 2014). We elide the proofs because they are similar to Lemma 2. Each of the six measures satisfies the precondition for the No Free Lunch theorem when the random model matches the problem domain.
Of late, a renewed push has advocated using the adjusted Rand index (ARI; Hubert and Arabie, 1985) to evaluate community detection; in fact, ARI and AMI are specializations of the same underlying function which uses generalized information-theoretic measures (Romano et al., 2016). Every claim in the proof works for ARI, by replacing every mutual information I term with the Rand index RI.
Another line of research, focusing on improving NMI, produced rNMI Zhang (2015), rrNMI , and cNMI (Lai and Nardini, 2016). We note that rrNMI is identical to one-sided AMI when both are extended to M 1 all . Consequently, our claim above works just as well for rrNMI. Further, because we were able to ignore the denominator of AMI in our proof of Lemma 2, we can do the same for rrNMI, which gives its unnormalized variant, rNMI. This means that rNMI is a generalizer-independent measure as well, when used in the appropriate one-sided random model. The practical benefit of normalizing rNMI into rrNMI is that the normalized measure gives a more interpretable notion of success.
Additionally, Lemma 2 holds true for standardized mutual information (which is equivalent to standardized variation of information and standardized V-measure) (Romano et al., 2014), the adjusted variation of information (Vinh et al., 2009), and for Cohen's κ, advocated for CD by Liu et al. (2018). This is because each measure shares the form of AMI: an observed score minus an expectation.
Finally, to show whether cNMI is generalizer-independent under the correct random model, we must show how to specialize it into a one-sided variant, because there is room for interpretation about how this should be done, even restricting our focus to M 1 all . The expression for cNMI depends on both C and T relative to the universes that contain them. Our specialization should remove dependence on the family of T , so we arrive at the following expression after cancellation and noting that the NMI between a clustering and itself is 1: As it turns out, this quasi-adjusted measure is also generalizer-independent.
In general, we now have a recipe for generalizer-independent loss functions: They can be created by subtracting the expected score from the observed score. This recipe works whenever a uniform expectation can be well defined.

CONCLUSION
We now have a proof of the No Free Lunch theorem for community detection and clustering that is both complete and exact. We show that a corrected form of AMI, namely AMI 1 all , computes its expectation in a way that does not advantage the boundary partitions (1 cluster and N singleton clusters). Indeed, this expectation is over the entire universe of partitions Ω, rather than any proper subset, such as the historically common M perm . We affirm the claim: "Any subset of problems for which an algorithm outperforms others is balanced by another subset for which the algorithm underperforms others. Thus, there is no single community detection algorithm that is best overall" (Peel et al., 2017).
It is still possible for an algorithm to perform better on a subset of community detection problems, so we can strive toward improved results on such a subset. To hope to perform well, we must note the assumptions about the subset of problems we expect to encounter. Some work has been done on estimating network properties to select the correct algorithm for the task at hand-a coarse way of checking assumptions (Peel, 2011;Yang et al., 2016). Beyond this, though, we must clarify what the problem of community detection is; the formulation we choose will guide which subset of problem instances to prioritize and which to sacrifice.