Source-linked AI summary
Graphlets as structural fingerprints of complex networks
Anna Pidnebesna, David Hartman, Aneta Pokorna, Daniel Trlifaj, Jaroslav Hlinka
TL;DR
The paper asks whether graphlet-based structural fingerprints can distinguish networks more systematically than selected graph-theoretical measures. It evaluates graphlets on parameterized synthetic networks, controlled connectome perturbations, and schizophrenia-control classification, finding their strongest advantage for local-to-mesoscale topological differences but only comparable performance in schizophrenia classification.
Problem
Selected graph-theoretical measures capture only a limited set of network properties, motivating systematic descriptors for distinguishing networks when their generative rules are unknown.
Method
The study represents each network with distributions of rooted graphlets up to size 5 and compares these fingerprints with graph-theoretical measures across synthetic models, connectome perturbations, and empirical classification tasks.
Results
Graphlets typically outperformed or matched GTMs for synthetic networks and controlled rewiring, but schizophrenia-control classification was led by spatially ordered adjacency features while graphlets remained above chance.
Takeaways & Limitations
Graphlet fingerprints are flexible and interpretable when discriminative structure is local-to-mesoscale and relevant patterns are not known in advance.
Takeaways & Limitations
The analyses used graphlets of size ≤5 on undirected, binary, static resting-state networks, limiting coverage of larger, weighted, directed, task-based, or dynamic connectivity.
Abstract
from arXiv · showhide
Complex networks are often compared using selected graph-theoretical measures that capture a selected set of properties with effects ranging from local to global, such as degree, clustering or betweenness centrality. Here we introduce a structural fingerprinting framework based on graphlets: small rooted subgraphs whose distributions provide a systematic description of local-to-mesoscale topology. Across synthetic networks generated from several random graph models, graphlet fingerprints capture parameter-dependent structural differences, outperform standard graph-theoretical measures, and identify even subtle local patterns driving discrimination. We then apply the framework to empirical resting-state functional connectomes, documenting that while graphlets show superior sensitivity also to controlled topological perturbations of brain connectivity, specifically in schizophrenia-control classification they perform only comparably to classical graph-theoretical features. This is in line with the notion that schizophrenia-related alterations are dominated by spatially localized connectivity changes rather than general topological reorganization. Altogether, the generative modeling, targeted perturbations and real-world neuroimaging classification challenge position graphlets as flexible structural fingerprints of complex networks, while carefully outlining their strength and weaknesses compared to more classical graph theoretical features.
1. Results
Graphlet fingerprints describe local-to-mesoscale topology and distinguish subtle structural differences across synthetic networks and empirical connectomes. Their advantage is strongest for topological perturbations, whereas schizophrenia-control discrimination depends more on preserved spatial connectivity information.
- 1.2. Graphlet fingerprints distinguish random graph models: Graphlet fingerprints up to size 5 outperformed combined GTM features by approximately 2%–10% across synthetic classification tasks.Reduced graphlet representations retained much of this discriminative power.
- 1.2. Graphlet fingerprints distinguish random graph models: Graphlet classifiers achieved higher accuracy than GTM classifiers in five of six synthetic tasks, with the HMR task showing comparable performance.Significant differences occurred in all but the HMR comparison, where p = 0.11.
- 1.2. Graphlet fingerprints distinguish random graph models: Task-specific size-five graphlets identified whether nodes attached to sparse paths, cyclic structures, or dense neighbourhoods.Graphlet 15 was especially important for HMR, HMC, and Mix; graphlet 36 for HK and RGG; and graphlet 56 for rBA and HK.
- 1.3. Graphlet fingerprints detect topological perturbations in empirical connectomes: Under rewiring, graphlet classifiers were most sensitive, whereas under linear mean shifts adjacency features were most sensitive and graphlet and GTM performance was similar.Accuracy increased monotonically with perturbation strength for both perturbation types and all feature sets.
- 1.4. Empirical schizophrenia and hemispheric classification: Empirical classification depended strongly on preserved ROI identity: hemisphere classification reached around 0.9 or approximately 0.8, while schizophrenia-control accuracy was typically around 0.6–0.65.Adjacency features performed best for schizophrenia-control classification, and unlabelled topological summaries were generally near chance.
- 1.4. Empirical schizophrenia and hemispheric classification: Combining GTM, graphlet, and adjacency features did not improve performance beyond the strongest individual representation.In empirical tasks, these representations captured partly overlapping information.
2. Discussion
Graphlet fingerprints are flexible and interpretable network descriptors whose value depends on whether discriminative structure is topological and local-to-mesoscale or spatially localized. Their usefulness is strongest in synthetic and perturbed networks, while schizophrenia classification favors localized features and remains bounded by data and representation limits.
- Cross-setting interpretation: Graphlets typically outperform or match GTMs and surpass adjacency features when network classes differ in local edge arrangement, but not when differences are mainly magnitude-based.In schizophrenia classification, adjacency-based features performed best because they retain topographic information, while graphlets were only comparable to local GTMs.
- Synthetic-network implications: Synthetic analyses show that graphlets need no a priori selection of task-relevant measures, and combining them with GTMs adds little beyond graphlets alone.Reduced representations retain much of the discriminative power, while feature-importance profiles identify distinct local substructures associated with different generative mechanisms.
- Schizophrenia connectomes: In schizophrenia, locally informed features outperformed global descriptors, whose performance was at chance, while comparable hemispheric accuracy suggested spatially distributed alterations within a broadly preserved architecture.The findings are compatible with alterations dominated by local circuit organization rather than large-scale topological reorganization.
- Limitations: The conclusions are constrained by graphlets of size ≤5 and analyses limited to undirected, binary, static resting-state networks.Weighted, directed, task-based, and dynamic connectivity remain outside the tested scope.
- Limitations: Schizophrenia classification accuracy was limited in absolute terms but comparable to state-of-the-art performance, with sample size, clinical heterogeneity, and spatially specific effects as possible influences.Other disorders or imaging modalities may place connectomes in regimes where global topology or higher-order structure matters more.
- Conclusion: Overall, graphlet fingerprints extend classical graph measures with an interpretable vocabulary for local-to-mesoscale structure when relevant patterns are unknown in advance.Their practical value is therefore conditional on the structural regime and the localization of the discriminative signal.
3. Methods
The study represents networks with graph-theoretical measures and graphlet-based descriptions, then evaluates these feature sets in supervised classification tasks across synthetic and empirical connectomes.
- Graph characteristics: GTMs capture local, mesoscale, and global organization through measures including degree, eigenvector centrality, shortest-path metrics, global efficiency, betweenness centrality, and clustering.These measures are intended to describe node importance, connectivity patterns, and overall network integration.
- Graph characteristics: Graphlets are connected, non-isomorphic rooted subgraphs of size ≤5, producing 73 rooted types for detailed vertex-neighborhood descriptions.For each vertex, graphlet degree counts record the number of nearby subgraphs isomorphic to each rooted graphlet.
- Feature construction: The feature sets comprise individual or combined GTMs, full or selected graphlet features, graphlet correlation representations, and vectorized upper-triangular adjacency matrices.Selected graphlets cover paths, cycles, and cliques; graphlet counts are retained as absolute frequencies to preserve density-related information.
- Classification design: Classification tasks assess whether representations distinguish parameterized or model-based synthetic graph classes, schizophrenia from healthy-control connectomes, and left from right hemispheres.Synthetic tasks use fixed-size, 25%-density connected graphs with 100 instances per parameter set, while real data use five-fold cross-validation.
- Simulated data: The Holme–Kim simulations vary triangle-formation probability across six classes to test how clustering differences affect classification performance.The probabilities are 0.15, 0.30, 0.45, 0.60, 0.75, and 0.90.
Code availability
The study’s analysis code is planned for public release and archival publication.
- Code availability: Custom code for network generation, feature computation, classification, perturbation experiments, and figure reproduction will be deposited on GitHub and archived in Zenodo.The release will include documentation, analysis scripts, and software-environment information.
Funding
The authors report support from Czech and European regional-development funding programs.
- Funding: The authors received support from Czech Science Foundation Grant No. 23-07074S and the ERDF Brain dynamics project.The ERDF project number is CZ.02.01.01/00/22_008/0004643.
Ethics approval
The empirical analyses used previously collected, ethically approved, anonymized resting-state fMRI data.
- Ethics approval: Participants provided written informed consent, and the secondary analyses followed institutional approvals and applicable regulations.The source studies were approved by relevant institutional ethics committees.
Generative AI statement
The authors used generative AI tools during manuscript preparation for language editing and organization, not for data generation, analysis, numerical results, or autonomous scientific conclusions.
- Generative AI tools assisted with language editing, condensation, clarity, organization, and explanatory text formulation.
- The authors critically reviewed and approved all AI-assisted text and retain responsibility for the manuscript.
- The tools were not used to generate data, perform statistical analyses, produce reported numerical results, or make autonomous scientific conclusions.