CS Paper Radar

Network sampling: a comparative review

Luiza L. S. Piva, Matheus V. Cerqueira, Francisco A. Rodrigues

cs.SI stat.CO ·submitted 2026-11-10 16:01 UTC · v2
code/data

Abstract

Network sampling is essential for the study of real world systems, since access to the topological structure and dynamical characteristics of a complex system is usually infeasible, and can also prove computationally intractable for large and dense networks. However, the field still lacks systematic methodologies that allow a procedural analysis of sampling plans for connected data. Hence, this study aims to compare network sampling methods through the usage of multivariate statistical analysis and machine learning techniques that are anchored in network metrics' estimation of synthetic and real-world networks. It was demonstrated that no single sampling strategy dominates both cases, although Forest fire and Frontier sampling have presented the most consistent performance across all topologies investigated. The impact of each structural property of these networks for principal component analysis and classification results were also discussed, with consistent pattern groups seen for both data types. Transfer learning aimed at real-world network identification has also demonstrated that realistic structural connections can be correlated to well-known network models through the usage of sampled subgraphs' properties for model training, providing an avenue to real-world network characterization through sampling methodologies.

Comment
15 pages, 9 figures, 2 tables. Supplementary material and code can be found on https://github.com/luizalober/sampling-in-networks

Closest papers

Nearest neighbours by meaning across the whole index.

Feature-Aware Edge Sampling for Approximate One-Step Laplacian Propagation

cs.LG ·2026-11-12 ·Jonathan Z. Sun, Zheng Wang, Kebin Xu
similarity 0.57
Abstract

This paper studies how to approximate one-step combinatorial Laplacian messages in graph neural networks using edge sampling. We propose a spanning tree based hybrid sampler that combines feature-conditioned message scores and effective-resistance leverage scores, derive the expected one-step message error and obtain the optimal sampling probabilities and error frontier for a given expected edge budget. Preliminary experiments on synthetic community graphs show that message error decreases, while classification accuracy increases slightly, as the edge budget grows, and performance of the hybrid sampler is in between of optimal selection uniform random sampling. We leave multi-step propagation and evaluation on larger and real graphs for future work.

0.17

High-dimensional networks and mean squared error for possibly misspecified models

cs.LG stat.ML ·2026-08-13 ·Lourens Waldorp
publishedtheory similarity 0.55
Abstract

To avoid missing important variables and their connections in networks, more and more variables are included in network analysis. Here we show that in a setting with many more parameters than observations (high-dimensional) it is possible to get a conservative (i.e., low false positive rate) estimate of the neighbourhood for each node (which connections are in the network). A neighbourhood is often estimated with a linear model, and this leads to two interesting cases: (i) If the true model is linear, then neighbourhood selection work reasonably well, and (ii) if the true model is nonlinear, then neighbourhood selection requires a penalty for the high dimensions. Here we show the impact of the ridge parameter on the mean squared error, and how this leads to low test variance and hence to neighbourhoods with large numbers of edges. We connect these insights with results from machine learning, where the so-called double descent (when more parameters are included than observations, the mean squared error goes down a second time) has put the traditional view on model selection upside down. Essentially, for adequate neighbourhood selection in models with a large number of parameters, the volume of the model space needs to be included in the penalty. Most neighbourhood selection methods (e.g., Lasso, AIC, BIC) lead to spurious edges (high false positive rate), but we prove that in the high-dimensional setting, minimum description length leads to correct neighbourhood selection or smaller (low false positive rates) in both cases when either the model is correctly or incorrectly assumed linear

0.20

From topology learning to graph generation: A unifying perspective

cs.LG stat.MLeess.SP ·2026-09-02 ·Xiaowen Dong, Hoi-To Wai, Siheng Chen, Laura Toni, Dorina Thanou
similarity 0.54
Abstract

Learning graph structures from data is a fundamental problem that spans a wide range of signal processing and machine learning tasks. While significant effort has been made to tackle the problem, existing research has largely evolved along two parallel directions. The first seeks to infer the topology of an individual graph from observations supported on it, whereas the second seeks to learn a generative distribution from observed graph instances, enabling the sampling of new graphs. This review presents a unified framework that connects these formulations by viewing them as inverse problems of a common generation process for graph data. We review the major methodologies within this framework, highlight their relationships, strengths, and limitations, and identify opportunities for integrating ideas across paradigms. By bridging graph topology learning and graph generation, this review provides a broader cross-disciplinary perspective on the field and outlines promising directions for future research.

0.27

SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking

cs.SI cs.LG ·2026-09-09 ·Guilherme Henrique Messias, Mariana Caravanti de Souza, Sylvia Iasulaitis, Alan Demétrius Baria Valejo
benchmark similarity 0.53
Abstract · 15 pages

Graph Neural Networks (GNNs) are powerful models for handling attributed graphs in tasks such as classification, link prediction, and community detection, as they enable the aggregation of information from both structural and semantic sources. However, progress in community detection is hindered by the lack of high-quality datasets, since ground-truth community labels are often unavailable and most algorithms proposed in recent literature rely on the same benchmark datasets for model training and evaluation. To address this issue, attributed random graph generators are commonly employed to create synthetic graphs for assessing the strengths and limitations of GNN-based models. Nevertheless, most existing generators rely heavily on power-law degree distributions, despite recent evidence indicating that scale-free networks are rare, particularly in social network contexts. Moreover, state-of-the-art attributed graph generators provide limited flexibility, as they do not allow users to construct communities with varying densities, degree distributions, and sub-community structures. To overcome these limitations, we introduce the Synthetic Community-Aware Attributed Graph Generator (SynCo), a graph generation algorithm that allows users to control the node degree distribution and sub-community structure. We evaluate SynCo across three different tasks: graph mimicking, hyperparameter evaluation, and node clustering tuning. The results show that our model outperforms state-of-the-art approaches in synthetic graph generation and data augmentation, while preserving the original distributions of duplicated and augmented datasets, as confirmed by statistical tests well know in literature. We also demonstrate the ability of SynCo to generate nodes in large scale, up to 2.1 million nodes.

0.13

A Joint Information-Theoretic and Graph Learning Framework for Sensor Placement and Macroscopic Traffic State Reconstruction

eess.SP cs.IT ·2026-08-24 ·Ying Zhang, Fatemeh Fakhrmoosavi, Arash E. Zaghi
benchmark similarity 0.53
Abstract

Traffic sensor placement in large urban networks must balance traffic monitoring needs with limited installation, maintenance, and data-management budgets. This study develops a framework for preserving network-wide traffic information while reconstructing flow and density at unobserved links and the macroscopic fundamental diagram (MFD). The framework combines normalized mutual information (NMI) with Inductive Graph Neural Network Kriging (IGNNK). NMI quantifies lag-aware dependence between joint flow-density states, while a greedy algorithm selects sensors by balancing weighted information coverage against redundancy. An IGNNK-based bidirectional graph-diffusion model reconstructs unobserved link states and generates the MFD. The framework was evaluated against a principal component analysis (PCA) benchmark using seven hours of dynamic traffic assignment simulation data for the Chicago network, with 4,805 directed links and 420 one-minute intervals split into training, validation, and independent testing subsets. Reconstruction performance for both PCA and NMI-IGNNK varied substantially over the sensor ratios of 0.5% to 30%. PCA generally yielded lower root mean squared error (RMSE) over the 0.5%-3% range, but its errors were nonmonotonic and reached their minimum at 2%. At 3%, normalized joint RMSE was similar for PCA and NMI-IGNNK (0.100 and 0.105, respectively). NMI-IGNNK remained applicable up to 30% coverage and generally improved as coverage increased, reducing testing-subset normalized joint RMSE from 0.212 at 0.5% to 0.043 at 30%, with consistent trends over the complete analysis period. The framework integrates lag-aware, information-theoretic sensor placement based on joint flow-density states with directed graph-based reconstruction, enabling a broad range of sensor budgets in large-scale networks without strict limits on the number of sensors.

0.23

Scalable Subgraph Sampling via Resistance Curvature

cs.LG cs.AI ·2026-09-23 ·Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li
similarity 0.53
Abstract

Subgraph sampling reduces the training cost of large-scale graph neural networks, but sampling criteria may overlook the geometric roles of edges. We propose a resistance-curvature-guided sampling framework built on ERC-LG, a curvature approximation method for large-scale graphs. ERC-LG combines Johnson-Lindenstrauss projections with regularized multi-GPU batched conjugate gradient solvers, avoiding explicit Laplacian pseudoinverse computation and full embedding storage. The resulting curvature informs node- and edge-sampling probabilities for constructing GNN training subgraphs. Experiments show numerical agreement with pseudoinverse-based curvature and reduced runtime compared with CG-only computation. ERC-LG-based sampling variants achieve the highest mean accuracy on six of seven real-world datasets in downstream node classification.

0.24

A General Capacity Frontier of Complex Networks

cs.SI physics.soc-ph ·2026-10-07 ·Nicholas Kunz, H. Oliver Gao
similarity 0.52
Abstract · 38 pages, 4 figures, 9 supplementary tables, 2 supplementary notes

From cells to cities, ecosystems to economies, complex networks exhibit peak intensities that define their empirical limit. Estimating these limits traditionally requires domain-specific knowledge. We demonstrate that a wide range of complex networks share a capacity frontier that constrains these maxima. We formalize this regularity by proposing Structural Capacity Theory for Network Substrate Structured Systems. These systems couple a fixed network substrate with an observable dynamical process. The frontier is learned from a vector representation of the network substrate and modulated log-additively by a vector representation of the dynamical process. Frontiers trained on one set of domains reliably bound empirical maxima of entirely different ones without observing their peak intensities or simulating their dynamics. Independent learning paradigms converge on consistent upper bounds. Frontier performance is stable under perturbation, yet degrades under deliberate falsification, with no performance gain under ablation. These findings support the capacity frontier as a generalizable constraint that describes how network structure bounds dynamical processes across otherwise unrelated systems.

0.33

Nested Ensemble Learning with Topological Data Analysis for Graph Classification and Regression

cs.LG stat.MLstat.AP ·2026-11-11 ·Innocent Abaa, Umar Islambekov
published similarity 0.52
Abstract · This is the published version of the article. Published in International Journal of Topology, MDPI, DOI: 10.3390/ijt2040017. Link to the off…

We propose a nested ensemble learning framework that utilizes Topological Data Analysis (TDA) to extract and integrate topological features from graph data, with the goal of improving performance on classification and regression tasks. Our approach computes persistence diagrams (PDs) using lower-star filtrations induced by three filter functions: closeness, betweenness, and degree2 centrality. To overcome the limitation of relying on a single filter, these PDs are integrated through a data-driven, three-level architecture. At Level-0, diverse base models are independently trained on the topological features extracted for each filter function. At Level-1, a meta-learner combines the predictions of these base models for each filter to form filter-specific ensembles. Finally, at Level-2, a meta-learner integrates the outputs of these filter-specific ensembles to produce the final prediction. We evaluate our method on both simulated and real-world graph datasets. Experimental results demonstrate that our framework consistently outperforms base models and standard stacking methods, achieving higher classification accuracy and lower regression error. It also surpasses existing state-of-the-art approaches, ranking among the top three models across all benchmarks.

0.55