Source-linked AI summary
Evaluating Overfit and Underfit in Models of Network Community Structure
Amir Ghasemian, Homa Hosseinmardi, Aaron Clauset
TL;DR
Community detection lacks a universally correct method, making metadata partitions unreliable as general ground truth and leaving overfitting and underfitting difficult to compare. The paper evaluates 16 algorithms on structurally diverse real-world networks using link prediction and link description, finding wide output and accuracy differences, with Bayesian and MDL-based approaches generally strongest but not universally best.
Problem
Metadata-based ground-truth evaluations are misleading because no community detection method is optimal for all inputs and network structure does not uniquely determine ground-truth communities.
Method
The study compares 16 community detection algorithms on diverse real-world networks and uses link prediction versus link description as a practical overfitting and underfitting diagnostic.
Results
Algorithms differ widely in community outputs and link-task accuracy; probabilistic methods generally perform well at link prediction, while modularity and Infomap tend to overfit and some methods underfit.
Takeaways & Limitations
MDL (DC-SBM) and B-NR are best overall, but every algorithm is best for some network and subsampling level, so no method is universally dominant.
Takeaways & Limitations
The evaluation does not establish a universally optimal method, and selecting the most parsimonious probabilistic model can diverge from selecting the highest link-prediction accuracy on adversarial networks.
Abstract
from arXiv · showhide
A common data mining task on networks is community detection, which seeks an unsupervised decomposition of a network into structural groups based on statistical regularities in the network's connectivity. Although many methods exist, the No Free Lunch theorem for community detection implies that each makes some kind of tradeoff, and no algorithm can be optimal on all inputs. Thus, different algorithms will over or underfit on different inputs, finding more, fewer, or just different communities than is optimal, and evaluation methods that use a metadata partition as a ground truth will produce misleading conclusions about general accuracy. Here, we present a broad evaluation of over and underfitting in community detection, comparing the behavior of 16 state-of-the-art community detection algorithms on a novel and structurally diverse corpus of 406 real-world networks. We find that (i) algorithms vary widely both in the number of communities they find and in their corresponding composition, given the same input, (ii) algorithms can be clustered into distinct high-level groups based on similarities of their outputs on real-world networks, and (iii) these differences induce wide variation in accuracy on link prediction and link description tasks. We introduce a new diagnostic for evaluating overfitting and underfitting in practice, and use it to roughly divide community detection methods into general and specialized learning algorithms. Across methods and inputs, Bayesian techniques based on the stochastic block model and a minimum description length approach to regularization represent the best general learning approach, but can be outperformed under specific circumstances. These results introduce both a theoretically principled approach to evaluate over and underfitting in models of network community structure and a realistic benchmark by which new methods may be evaluated and compared.
1 INTRODUCTION
Community detection lacks a universally optimal method, and metadata-based ground-truth evaluations can therefore mislead. The paper compares methods on diverse real-world networks and evaluates overfitting and underfitting through link-based tasks.
- Few broad practical studies establish which community detection methods suit different network classes or downstream tasks.
- The No Free Lunch theorem implies that every method trades better performance on some inputs for worse performance on others, potentially overfitting or underfitting.
- Metadata partitions are misleading as universal ground truth because network structure does not uniquely determine correct communities.
- The study compares 16 state-of-the-art methods on 572 structurally diverse real-world networks using theoretical constraints, link prediction, and link description.
- Removing observed edges enables link description and link prediction evaluations that diagnose overfitting and underfitting through training- versus test-like accuracy.
- Algorithms differ widely in community counts and composition, cluster into output-similarity groups, and vary substantially in link-based accuracy.
- Bayesian and regularized likelihood methods based on stochastic block models generally perform best, while MDL provides the best general learning algorithm.
2 METHODS AND MATERIALS
The study builds a broad benchmark and compares representative probabilistic and non-probabilistic community detection methods. It focuses on traditional hard partitions and evaluates practical behavior across diverse real-world networks.
- Prior comparative studies often used few methods, synthetic networks, or a small set of familiar real-world networks.
- Probabilistic methods include stochastic block model variants and regularization approaches such as Bayesian inference, cross-validation, likelihood tests, and MDL.
- Non-probabilistic methods include modularity maximization, Infomap’s map equation, and spectral techniques.
- The study selects 16 representative state-of-the-art approaches spanning both broad method groups, emphasizing computational feasibility, performance, software availability, and methodological diversity.
- Algorithm outputs can depend on priors and implementation details, although the authors report that these differences do not affect qualitative evaluation results.
- CommunityFitNet contains 572 ICON networks spanning social, economic, biological, technological, information, and transportation domains.
- The analysis treats graphs as simple, ignoring edge weights and directions, and focuses on hard vertex partitions rather than hierarchical or mixed-membership outputs.
3 NUMBER OF COMMUNITIES IN THEORY AND PRACTICE
Algorithms differ dramatically in how many communities they infer from the same sparse network, although community counts generally grow with network size. These differences provide evidence of distinct overfitting and underfitting tendencies.
- 3.1 In Theory: Consistency results for dense networks do not apply to CommunityFitNet because its real-world networks are sparse.
- 3.1 In Theory: Theoretical analyses generally predict that the maximum number of detectable communities in sparse networks grows like O(sqrt(M)).
- 3.1 In Theory: Detectable clusters and maximum inferred clusters are distinct: resolution limits can merge communities even when the remaining structure is detectable.
- 3.2 In Practice: Across methods, inferred community counts vary nonmonotonically, with some methods finding 10 times as many communities as others on the same inputs.
- 3.2 In Practice: Community counts generally increase with edge count and roughly follow the theoretically predicted sqrt(M) trend, with cleaner empirical behavior against M than N.
- 3.2 In Practice: One method group finds roughly 2–3 times as many communities as another, with Q, Q-MR, Infomap, LRT-WB, and AMOS in the higher-count group.
- 3.2 In Practice: Probabilistic methods often agree on smaller networks but diverge on larger ones because stronger complexity penalties can reduce overfitting while increasing underfitting risk.
- 3.2 In Practice: The broad variation in inferred communities suggests differing overfitting and underfitting tendencies, but no accepted procedure identifies the most useful output.
4 QUANTIFYING ALGORITHM SIMILARITY
Comparing partitions across real-world networks reveals practical clusters of algorithms that produce similar community compositions. These clusters largely separate probabilistic from non-probabilistic approaches and contain meaningful subgroups.
- Figure 3 displays pairwise AMI structure and distributions of inferred community counts for groups of similar algorithms.
- Data-driven clustering compares inferred labels across a consistent corpus using mean adjusted mutual information between algorithm pairs.
- Probabilistic methods typically produce communities more similar to those of other probabilistic methods than to non-probabilistic outputs.
- Non-probabilistic methods subdivide into spectral, consensus-based modularity, traditional statistical, and other non-probabilistic subgroups.
- The algorithm clusters are based on output composition, so they matter for applications that depend on the particular membership structure of a clustering.
5 EVALUATING COMMUNITY STRUCTURE QUALITY
The paper evaluates community structure quality through complementary link prediction and link description tasks, using their tradeoff to diagnose overfitting and underfitting. Results show substantial variation across methods: some overfit, some underfit, and model-specific score functions and network structure affect performance.
- Caveats: The relationship between predictive performance and model fit remains theoretically unsettled, because the most predictive model need not be the most plausible and predictive gains can induce overfitting.The authors note that held-out-edge construction and standard cross-validation assumptions have unclear theoretical implications for relational data.
- Evaluation framework: The evaluation pairs link prediction with link description to diagnose whether community detection methods overfit or underfit real networks.Link prediction evaluates out-of-sample prediction, while link description evaluates learning the observed network; no method can be perfect at both tasks.
- Evaluation framework: Accuracy curves measure mean AUC across networks as the observed-edge fraction α varies from sparse to nearly complete observations.Different score functions are used for different community detection methods, and α controls the fraction of edges retained for evaluation.
- Overfitting patterns: Q and Q-MR perform poorly on link prediction, especially when α < 0.3, consistent with over-partitioning and overfitting noisy within-community connectivity.Their nearly identical curves suggest similar tendencies to infer more communities than optimal.
- Generalization performance: Bayesian methods and MDL methods produce the strongest link-prediction curves, with MDL (DC-SBM) best overall across nearly every α value.SBM methods generally outperform DC-SBM methods, except for MDL-regularized DC-SBM; differences may arise from the score functions used for missing-edge prediction.
- Overfitting and underfitting: Infomap, Q, and Q-MR perform well on link description but only moderately on link prediction, whereas MDL and B-NR show the opposite balance and appear better fitted overall.Q-MP performs poorly on both tasks, consistent with substantial underfitting from finding relatively few communities.
6 CONCLUSION
Across a diverse real-world benchmark, community-detection algorithms exhibit distinct partitioning and fitting behaviors, with no universally superior method. The corpus and link-based evaluation provide practical tools for comparing these context-dependent tradeoffs.
- Algorithmic behavior: Algorithms can differ by more than an order of magnitude in the number of communities inferred for the same network.Most methods follow a theoretical scaling pattern, but their inferred community counts can diverge substantially.
- Algorithmic behavior: Underlying algorithmic assumptions produce similar output patterns, allowing methods to be clustered by the communities they identify.Non-probabilistic methods typically find more communities than probabilistic methods, while spectral methods exhibit related output behavior.
- Performance tradeoffs: Link prediction and link description expose wide variation in overfitting and underfitting, while MDL (DC-SBM) and B-NR (SBM) perform best on average but not universally.Other algorithms outperform them on specific networks, so comparative conclusions depend on the input.
- Benchmark utility: The CommunityFitNet corpus can serve as a standardized reference set for comparing new methods across structurally diverse real-world networks.Researchers can compare average behavior, community composition, and performance on particular networks against existing algorithms.
- Open questions: A theoretical framework is still needed to explain and control the algorithmic tradeoffs that produce general, specific, or uneven fitting behavior.The paper identifies uneven fitting within a single network as a direction for future cross-validation studies.
APPENDIX A PERFORMANCE ON BIPARTITE VERSUS NON-BIPARTITE NETWORKS
The appendix examines how bipartite structure affects community-detection performance. Performance varies by network type and domain, with different methods favored in bipartite versus non-bipartite settings.
- Bipartite versus non-bipartite performance: B-NR (SBM) performs partially better on bipartite networks, whereas MDL (DC-SBM) is slightly better on non-bipartite networks.The comparison indicates that network bipartiteness changes which of the strongest methods performs better.
- Domain effects: Non-bipartite averages appear less variable because social networks dominate this group, rather than because fitting behavior is uniform across domains.Domain-separated results still reveal overfitting in several methods on technological, biological, transportation, economic, and information networks.
- Domain effects: For non-bipartite networks, MDL (DC-SBM) is nearly best across domains, especially transportation, while B-NR (SBM) is also among the strongest methods.Infomap generally outperforms Q and Q-MR for bipartite networks, whereas modularity and Infomap show overfitting in several non-bipartite domains.
- Evaluation design: Figure 8 compares mean AUC curves for link prediction and link description across bipartite and non-bipartite networks as the observed-edge fraction α changes.Each curve represents a different community-detection method using its model-specific score function.
APPENDIX B PERFORMANCE UNDER A COMMON SCORE FUNC-
Using a common SBM score function separates the quality of inferred communities from the scoring functions paired with them. This check shows that poor task performance can reflect score-function mismatch rather than community structure alone.
- Most methods show some degree of overfitting or underfitting across link prediction and link description benchmarks.Poor performance on either task may also result from pairing a score function poorly with the communities an algorithm finds.
- The common-score experiment reapplies both evaluations to each algorithm’s partitions using the SBM score function.The comparison removes differences in how methods’ own scoring functions use the same partition structure.
- For most algorithms, the score function chosen by the method is a reasonable match for its detected communities.
Results
Replacing model-specific scores with a common SBM score changes the relative performance ordering of methods, while leaving SBM-based methods unchanged. The comparison attributes some observed differences to score functions and reveals method-specific fitting behavior.
- The common-score evaluation changes the relative ordering of benchmark curves compared with model-specific evaluation, except that SBM-based methods are unchanged.
- B-NR becomes the best overall method by a sizable margin under the common SBM score function, while MDL (DC-SBM) performs substantially worse on both tasks.
- The smaller B-NR (DC-SBM)–B-NR (SBM) link-prediction gap indicates that B-NR (DC-SBM)’s earlier poor performance was due to its score function.
- Link prediction using inferred communities alone may be an unfair evaluation of DC-SBM because its score function and model complexity affect predictions.
- Infomap, Q-MR, and Q have nearly identical performance under the common SBM score function, providing additional evidence that modularity-based methods tend to overfit real data.
- S-NB is consistent with underfitting in relatively sparse networks and shows worse performance at larger α, consistent with overfitting in large sparse networks.The passage also relates underfitting to unbalanced communities and reports that spectral methods behave differently across settings.
APPENDIX C
The appendix connects community-count complexity with overfitting and underfitting, and represents the two evaluation tasks in a parametric performance space. It also documents scoring and sampling procedures used for reproducibility.
- The number and composition of detected communities serve as network-model complexity, paralleling training-set and test-set prediction in the link-description and link-prediction tasks.
- A parametric plot divides link-prediction–link-description performance into good-poor, poor-good, and poor-poor regions corresponding to well-fitted, overfitted, and underfitted behavior.
- The reproducibility appendix details scoring functions, link-evaluation procedures, and Monte Carlo approximation of AUC.
D.1 B-NR (SBM), B-NR (DC-SBM), B-HKK, cICL-HKK, and S-NB
The methods assign pairwise scores using model-specific rules: probabilistic methods use edge-existence probabilities, while spectral clustering uses entries from a low-rank approximation. Link prediction and description then compare scores with AUC.
- Probabilistic methods score node pairs by the probability that the corresponding edge exists, whereas S-NB uses a spectral score from a low-rank approximation.For S-NB, the approximation rank comes from the non-backtracking spectral method.
- Link prediction removes a random fraction of links, samples 10,000 missing-link and non-link pairs, and compares their scores using Monte Carlo AUC.
- Link description samples 10,000 observed-link and non-observed-link pairs after random link removal and compares their scores using Monte Carlo AUC.
D.2 Q, Q-MR, Q-MP, Infomap, MDL (SBM), and MDL (DC-SBM)
These methods evaluate potential edges through contributions to non-probabilistic objective functions, with modularity Q using the increase in Q after adding an edge. Link prediction compares contributions from candidate missing links and non-links across varying observed-edge fractions.
- The section summarizes score functions for Q, Q-MR, Q-MP, Infomap, MDL (SBM), and MDL (DC-SBM).MDL (SBM) and MDL (DC-SBM) are closely related to probabilistic methods, although their score functions are non-probabilistic.
- Figure 10 reports mean AUC curves for link prediction and link description across 572 real-world networks as the observed-edge fraction α varies.
- Figure 11 parametrically compares link prediction and link description performance, with α determining each method's trajectory.
- Each potential edge i, j receives a score equal to its contribution to the corresponding objective function.
- For modularity Q, the score s_ij is the increase in modularity ΔQ after adding the edge, assuming the partition remains unchanged.The modularity expression uses l_r, d_r, and M, representing within-group edges, aggregated group degree, and total network edges.
- Link prediction removes (1 − α)% of links and compares contributions after adding candidate links at missing-link and non-link locations.The comparison uses 10,000 randomly selected pairs to compute AUC.
D.2.2 Link Description
Link description evaluates whether learned score functions distinguish observed links from non-observed links under alternative reference-network constructions. The manuscript reports method (b) and finds that method (c) changes results slightly without changing the main conclusions, while method (d) is computationally expensive.
- Link description removes (1 − α)% of links and randomly selects 10,000 pairs of observed links and non-observed links for comparison.
- Method (b) compares the objective-function contributions after adding an observed link and a non-link to the current network.This design lets the learned model identify link positions without prior knowledge.
- Methods (c) and (d) assume the learned model knows the positions of the links while constructing the comparison.Method (c) removes an observed link before comparing it with an added non-link; method (d) uses the removed-link network as reference.
- The manuscript reports link-description results using method (b), while Figure 13 compares methods (b) and (c).
- Method (c) changes the results slightly but does not affect the main conclusions, whereas method (d) is very computationally expensive.
APPENDIX E MODEL SELECTION APPROACHES
The appendix frames community-count selection as model selection and organizes methods into broad probabilistic and non-probabilistic families with overlapping subclasses. It also describes evaluation and computational considerations relevant to controlling model complexity.
- Model selection: Choosing the number of communities k is a model-selection and complexity-control problem because more communities generally give the fitted model greater flexibility.
- Method categories: Community detection methods fall into probabilistic and non-probabilistic categories spanning Bayesian or regularized likelihood, information-theoretic, modularity, spectral or embedding, cross-validation, and hypothesis-testing approaches.The category boundaries are not rigid, and individual methods can belong to multiple groups.
- Regularization: MDL seeks to avoid overfitting by trading off goodness of fit against description length, while Bayesian marginalization controls overfitting by averaging across parameterizations.
- Regularization: Regularized-likelihood and Bayesian approaches are grouped together because priors play a role analogous to penalty terms in penalized likelihood.
- Method categories: Infomap identifies community regularities by compressing random-walker paths, whereas modularity compares within-group edges with expectations from a degree-matched random graph.
- Method categories: Q-MR is mathematically equivalent to a special DC-SBM case under a k-planted partition and selects k implicitly through an iterated resolution procedure.
- Method categories: The appendix notes that spectral approaches can be unsuitable for sparse networks or heavy-tailed degree distributions, motivating non-backtracking spectral methods.
- Evaluation constraints: Traditional bias–variance and cross-validation approaches are difficult in networks because pairwise interactions violate independence assumptions and edge-wise validation can be computationally expensive.Leave-one-out prediction error can nevertheless be computed efficiently with belief propagation in sparse networks.