Graphlets as structural fingerprints of complex networks
Anna Pidnebesna, David Hartman, Aneta Pokorna, Daniel Trlifaj, Jaroslav Hlinka
cs.SI · q-bio.QM
Quick verdict
Graphlets beat classical graph metrics on synthetic and rewired networks but only match them in schizophrenia classification — a careful, convincing benchmark.
Summary
The paper evaluates graphlet degree distributions — counts of rooted subgraphs of up to five nodes (73 types per vertex) — as structural fingerprints for classifying networks, benchmarking them against classical graph-theoretical measures (GTM) and vectorized adjacency matrices using Random Forests. Three nested settings are studied: six synthetic tasks (rewired Barabási–Albert, Holme–Kim, random geometric, hierarchical modular random and centralised, and a mixed task; six parameter classes each, 100 graphs per class, 90 nodes, 25% density); controlled perturbations of empirical connectomes (edge rewiring up to 45 edges; linear mean shift up to 3× the group difference); and resting-state fMRI from 90 schizophrenia patients and 90 controls (AAL atlas, binarized at 25% density). Graphlets beat GTMs in five of six synthetic tasks (McNemar p≤0.001; HMR exception p=0.11), and GTM+graphlet combinations added nothing. Under rewiring, sensitivity ordered graphlets > GTMs > adjacency; under mean shift this reversed. In SZ–HC classification graphlets only matched local GTMs (~0.6–0.65) while adjacency performed best, and shifting SZ connectomes toward the HC mean nearly abolished the signal, implying group differences are dominated by a spatially structured edge-weight shift rather than topological reorganization. Limitations: binary undirected static graphlets of size ≤5, a narrow GTM panel, a single-site cohort, and code/data not yet deposited.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Graphlet degree distributions (size ≤5, 73 rooted types) outperform a panel of classical graph-theoretical measures in five of six synthetic random-graph classification tasks, and combining both feature sets yields no significant gain over graphlets alone.
- Perturbation sensitivity is structure-dependent: under edge rewiring of empirical connectomes accuracy orders graphlets > GTMs > adjacency, whereas under a linear mean shift the order reverses with adjacency most sensitive.
- In schizophrenia–control classification, graphlets perform only comparably to classical local features while adjacency features are best, and shifting SZ connectomes toward the HC group mean nearly eliminates the signal — evidence that the group difference is a spatially structured edge-weight shift rather than topological reorganization.
- Preserving ROI identity is essential for empirical classification: with randomly permuted node labels all feature sets perform near chance (Section 1.4).
Strengths
Nested evaluation design
Synthetic generative regimes (six models, Table 2), targeted perturbations of real connectomes, and clinical classification form a coherent ladder of difficulty; the rewiring vs. mean-shift contrast (Figure 3a) cleanly dissociates which feature families detect local edge rearrangement versus uniform edge-weight change.
Honest boundary result with mechanistic interpretation
Rather than overselling graphlets, Section 1.4 shows they only match local GTMs in SZ–HC classification, and the shift-back analysis (Figure 4c, coefficients −1 to 3) demonstrates a linear group-mean shift accounts for most of the empirical difference; nested cross-validation guards against circularity of the estimated shift direction.
Confound controls
Interpretable feature importance
Methodological transparency
Weaknesses
Narrow GTM baseline panel
Thin statistical reporting
Modest, confound-prone clinical result
Binary, thresholded graphs may favour the adjacency baseline
Reproducibility deferred
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What are graphlets in network analysis?
Graphlets are small connected subgraphs — here up to five nodes, giving 73 rooted types — counted around every vertex of a network. They generalise node degree to a vector of local pattern counts (paths, triangles, cycles, cliques and their combinations), providing a richer description of local topology than single scalar measures such as degree or clustering coefficient.
Did graphlet features improve schizophrenia detection from fMRI in this study?
No. In schizophrenia-versus-control classification of resting-state connectomes, graphlet fingerprints performed only comparably to classical local graph measures (balanced accuracy roughly 0.6–0.65), and raw adjacency-matrix features performed best. The authors show that shifting patient connectomes toward the control-group mean nearly erased the classification signal, indicating the group difference behaves like a uniform, spatially structured shift in connection strength rather than a rewiring of network topology.
Is the code or data from this paper available?
At the preprint stage, no. The authors state that the synthetic datasets, derived feature matrices, analysis code, and anonymised functional connectivity matrices will be deposited on GitHub and Zenodo upon journal publication; raw fMRI data remain restricted for privacy reasons.
What kind of networks were analysed in this study?
Two kinds: synthetic graphs of 90 nodes at 25% edge density generated from six random graph models (rewired Barabási–Albert, Holme–Kim, random geometric, hierarchical modular random and centralised, plus a mixed task), and human resting-state fMRI connectomes from 90 schizophrenia patients and 90 healthy controls, parcellated into 90 AAL brain regions and binarised at 25% connection density.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures are available only as captions in the extracted text; per-task numeric accuracies (Figures 2–4) could not be independently verified from the text.
- The Supplementary Information (full permuted-ROI results, diameter distributions, example adjacency matrices, connectivity counts) is referenced but not included in the extracted text.
- Equations and tables render with some formatting loss; parameter values were cross-checked against prose but fidelity is imperfect.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.