Source-linked AI summary
Network Sampling: From Static to Streaming Graphs
Nesreen K. Ahmed, Jennifer Neville, Ramana Kompella
TL;DR
Network sampling must support massive, evolving, distributed, or partially observable networks, but conventional methods largely assume static graphs that fit in memory. The paper develops a framework and graph-induction sampling family spanning static through streaming settings, extending node, edge, and topology-based methods. Its evaluations report more accurate preservation of graph properties across static and streaming graphs, while also examining consequences for relational classification.
Problem
Massive, evolving, or partially observable networks make full analysis difficult, while traditional sampling commonly assumes static graphs that fit in memory.
Method
The paper proposes a network-sampling framework, a static-to-streaming computational spectrum, graph-induction methods, and streaming extensions for node, edge, and topology-based sampling.
Results
The proposed methods more accurately preserve many graph properties than alternative algorithms for static and streaming graphs, including large graphs processed with few edge passes.
Takeaways & Limitations
The framework supports comparing sampling algorithms across objectives and computational settings, including large graphs and graph streams.
Takeaways & Limitations
The work assumes the population graph is fully visible and stored on disk, excluding settings where its structure is unknown before sampling.
Abstract
from arXiv · showhide
Network sampling is integral to the analysis of social, information, and biological networks. Since many real-world networks are massive in size, continuously evolving, and/or distributed in nature, the network structure is often sampled in order to facilitate study. For these reasons, a more thorough and complete understanding of network sampling is critical to support the field of network science. In this paper, we outline a framework for the general problem of network sampling, by highlighting the different objectives, population and units of interest, and classes of network sampling methods. In addition, we propose a spectrum of computational models for network sampling methods, ranging from the traditionally studied model based on the assumption of a static domain to a more challenging model that is appropriate for streaming domains. We design a family of sampling methods based on the concept of graph induction that generalize across the full spectrum of computational models (from static to streaming) while efficiently preserving many of the topological properties of the input graphs. Furthermore, we demonstrate how traditional static sampling algorithms can be modified for graph streams for each of the three main classes of sampling methods: node, edge, and topology-based sampling. Our experimental results indicate that our proposed family of sampling methods more accurately preserves the underlying properties of the graph for both static and streaming graphs. Finally, we study the impact of network sampling algorithms on the parameter estimation and performance evaluation of relational classification algorithms.
1. INTRODUCTION
The paper frames network sampling across static, large, and streaming graphs, addressing networks whose size, visibility, or evolution makes full analysis difficult. It proposes graph-induction methods that generalize across computational models while preserving graph properties and operating efficiently on graph streams.
- Motivation: Massive, evolving, partially visible, or costly-to-measure networks make complete analysis impractical, motivating network sampling.Sampling is also important because many analyzed datasets are themselves samples and sampled networks support simulation and experimentation.
- Evaluation: The methods preserve many graph characteristics more accurately than alternative state-of-the-art algorithms on static and streaming graphs.For large graphs, the paper specifically reports accurate preservation while requiring only two passes over the edges.
- Streaming model: Graph streams require sequential processing because their edge volume is too large for memory, their structure is not fully observable, and real-time processing matters.The paper formalizes a stream input G = (V, E), where edges arrive in no particular order and the output is a sampled subgraph Gs.
- Framework: The paper organizes network sampling by objectives, populations and units of interest, method classes, and a computational spectrum from static to streaming graphs.The spectrum includes static graphs, large disk-resident graphs, and streaming graphs, with increasing computational constraints.
- Methods: The proposed graph-induction family generalizes across computational models, uses storage on the order of the sampled subgraph, and runs in a single pass over graph-stream edges.The broader contribution list also targets efficient execution in a few passes, with runtime on the order of the number of edges.
- Evaluation: The study extends node, edge, and topology-based sampling to graph streams and evaluates effects on parameter estimation and relational-classification performance.The empirical evaluation includes datasets too large for main memory and a task-based relational-classification analysis.
2. FOUNDATIONS OF NETWORK SAMPLING
The paper frames network sampling around explicit goals, populations, units, and algorithm classes, then uses these foundations to define what makes a sample useful. It distinguishes estimating network properties from selecting representative subgraphs or studying node and edge attributes.
- Network sampling research needs explicit objectives, populations, units, sampling algorithms, and evaluation techniques to compare methods and understand their strengths and weaknesses.
- A network is represented as G = (V, E), with node attributes Λ and edge attributes β describing properties of vertices and relationships.
- A sampling algorithm selects nodes, edges, or a subgraph from G, with sample size commonly expressed as a fraction φ of the input nodes.
- The paper identifies four goals: estimate network parameters, sample a representative subgraph, estimate node attributes, and estimate edge attributes.
- Representative-subgraph sampling seeks to preserve selected topological properties, whereas attribute-estimation goals require sampled node or edge attributes to approximate those in the population.
- The goals may conflict: a sample accurate for one purpose, such as representing structure, can provide biased estimates of global graph parameters.
3. MODELS OF COMPUTATION
The paper develops a spectrum of computation models from simple static graphs to large disk-resident graphs and streaming graphs. Streaming sampling must process an ordered edge stream under sequential-access, memory, pass, and real-time constraints.
- Static model: Static sampling assumes fast random access and often that the graph fits in main memory, but this abstraction does not distinguish memory-resident from disk-resident graphs.
- Large-graph model: Large graphs motivate sequential sampling because random disk accesses can impose substantial I/O costs, while topology-based procedures may require many passes.
- Streaming model: A graph stream is an ordered sequence of edges, and this paper assumes the adjacency-stream model rather than the incidence-stream model.
- Streaming model: Streaming graphs are too large and dynamic for memory, permit only sequential access, and require efficient real-time processing.
- Streaming model: Streaming sampling decides whether to retain each arriving edge while tracking state, with complexity measured by passes, storage, and sample representativeness.
- The computation spectrum comprises static graphs, large graphs, and streaming graphs, ordered from simpler and less constrained to more challenging models.
4. RELATED WORK
Related work spans network sampling, graph-stream mining, social science, network systems, and structured data mining. The paper positions its contribution against problem-specific methods and the predominance of static computational models.
- Prior network-sampling research largely evaluates sample goodness relative to specific research goals, leaving less work on a broader foundation.
- Network sampling in social science: Social-science work includes chain-referral and snowball sampling for studying social-network actors and difficult-to-access populations.
- Statistical properties: Statistical studies show that node, edge, and random-walk sampling can bias estimates of topological properties, including degree distributions.
- Network systems research: Network-systems research uses crawling to measure large, distributed Internet, Web, peer-to-peer, and online social-network topologies.
- Structured data mining: Structured data-mining methods include representative-subgraph sampling, reductive topology shrinking, and Metropolis optimization, but convergence and distance-computation costs can be substantial.
- Graph streams: Graph-stream research has addressed triangle counting, common neighborhoods, PageRank estimation, and edge or structural-reservoir sampling.
5. SAMPLING FROM STATIC GRAPHS
The paper introduces induced edge sampling (ES-i), which selects nodes through uniformly sampled edges and then induces all edges among them. On static graphs, ES-i preserves network structure more accurately than node, edge, and forest-fire sampling across multiple statistics.
- 5.1. Algorithm: ES-i constructs a sampled subgraph by selecting node pairs through uniformly sampled edges, then adding every edge among the selected nodes.This graph-induction step forms Gs from Vs and Es.
- 5.1. Algorithm: Graph induction recovers connectivity around sampled nodes, increasing triangle sampling, clustering coefficients, and connectivity while offsetting downward degree bias.The mechanism complements the upward degree bias of edge-based node selection.
- 5.2. Analysis of ES-i: ES-i is biased toward high-degree nodes, and its expected sampled degree exceeds that of uniform node sampling.The paper formalizes these properties in Lemmas 5.1 and 5.2.
- 5.3. Experimental Evaluation: ES-i preserves degree tails and generally captures clustering, path-length, k-core, and eigenvalue structure more accurately than NS, ES, and FFS.Its performance is strongest across the reported distributional and spectral comparisons, though some dataset-specific underestimation remains.
- 5.3. Experimental Evaluation: ES-i generally outperforms the other methods on KS, skew-divergence, L1, and L2 distances, including when sample size reaches 40% of the full graph.The other methods fail to improve their performance at that larger sample size in the reported comparisons.
- 5.3. Experimental Evaluation: ES-i preserves both local and global network statistics, favors dense and clustered regions, and produces connected samples unlike the more sparsely connected samples of NS, ES, and FFS.This structural behavior is attributed to its high-degree selection bias and induced edges.
6. SAMPLING FROM STREAMING GRAPHS
This section develops space-efficient sampling methods for streaming graphs, where edges arrive sequentially and the full graph cannot be stored. PIES uses edge-sampling bias toward high-degree nodes followed by induced-subgraph construction, preserving many network statistics while remaining weaker for eigenvalues and dense, highly clustered graphs.
- Streaming sampling: Streaming graph sampling constructs representative subgraphs from unordered edge streams using space-efficient methods.Streaming node and edge sampling adapt traditional methods to sequential edge arrival.
- PIES: PIES combines edge sampling, which favors high-degree nodes, with induced-graph construction to capture connectivity among sampled nodes.The edge-sampling bias offsets some downward bias caused by subgraph sampling.
- Distance metrics: PIES outperforms other stream methods for degree distributions, while NS is nearly as good for path length, clustering coefficient, and k-core distributions.BFS and ES perform worst among the compared methods in the averaged distance evaluation.
- Limitations: PIES does not adequately capture eigenvalues: its eigenvalues are orders of magnitude smaller than those of the real graph, with eigenvalue distance near 50%.Among the evaluated network quantities, PIES still accurately estimates network values for most graphs.
- PIES(MIN): PIES(MIN) modifies reservoir replacement to favor retaining high-degree nodes over isolated or low-degree nodes and improves preservation for dense graphs.The modification replaces a node with minimum degree that has remained without acquiring more edges for the longest time.
- Network properties: PIES preserves many network statistics, including degree, path length, and k-core, with better performance on sparse or less clustered graphs.Distance measures increase for all methods as graphs become denser and more clustered.
7. PRACTICAL APPLICATIONS OF NETWORK SAMPLING
The paper frames network sampling as affecting not only topological measurement but also downstream relational-learning studies. It identifies class imbalance and topological bias as sources of distortion in parameter estimation and classification evaluation.
- Applications: Network sampling is used across applications including simulation, experimentation, protocol evaluation, social marketing, and fraud detection.The paper emphasizes that many datasets treated as complete networks are themselves samples.
- Relational learning: Sampling can create class-membership imbalance and bias topological features such as path length and clustering, affecting relational-classification accuracy.The bias may depend on sample size, sampling method, or both.
- Evaluation goals: The case study evaluates two goals: estimating class priors and estimating classification accuracy for relational learners.These correspond to parameter estimation and performance evaluation, respectively.
Case Study: Relational Classification
The relational-classification case study examines whether sampled networks preserve class-prior estimates and classifier-accuracy estimates. Across the tested methods, ES-i provides the best balance, while other methods favor one objective or become unreliable at smaller sample sizes.
- Experimental setup: The study samples 10%–80% subsets from four real networks and averages ten runs for each sample size.The networks include CORA, CITESEER, FACEBOOK, and a political-blog network.
- Experimental setup: The classification evaluation compares accuracy on the full graph G with accuracy estimated on a sampled subgraph Gs.The experiments use the weighted-vote relational neighbor classifier and five-fold cross-validation.
- Classification accuracy: For sample sizes below 30%, NS, ES, and FFS generally underestimate the full-graph AUC, whereas ES-i generally performs better and converges to the true AUC.AUC is evaluated for the most prevalent class while varying labeled-node proportions.
- Summary: Node sampling estimates class priors better than other methods but cannot estimate classification accuracy, while edge sampling performs similarly to node sampling.Forest-fire sampling is generally non-robust for class-prior estimation when φ ≤30%.
- Summary: ES-i provides a good balance between parameter estimation and accuracy estimation, with some bias at smaller sample sizes.The conclusion distinguishes the two evaluation goals rather than treating one estimator as universally superior.
8. CONCLUSIONS AND FUTURE WORK
The paper presents a framework for network-sampling objectives, populations, units, and method classes, alongside computational models ranging from static graphs to streaming graphs. Its graph-induction sampling family generalizes across these models and more accurately preserves graph properties in static and streaming settings.
- Framework: The framework organizes network sampling by study goals, populations and units of interest, sampling-method classes, and evaluation techniques.It is intended to facilitate comparisons of algorithms’ relative strengths and weaknesses for particular goals.
- Computational models: The proposed computational spectrum spans static graphs, large disk-resident graphs, and streaming graphs.The models progress from least restrictive to more realistic and restrictive settings.
- Sampling methods: The graph-induction sampling family generalizes across the full static-to-streaming spectrum while preserving many topological properties efficiently.The reported scope includes both static and streaming graphs.
- Empirical findings: Experiments indicate that the proposed sampling family more accurately preserves underlying graph properties for both static and streaming graphs.The paper also studies how sampling affects parameter estimation and relational-classification performance evaluation.
A.1. Distributions for Static Graphs (at 20% sample size)
This section presents distribution figures for seven static graphs at a 20% sample size.
- The figures cover FACEBOOK, HEPPH, CONDMAT, TWITTER, EMAIL-UNIV, FLICKR, and LIVEJOURNAL graphs.
- The FACEBOOK graph is shown in Fig. 10.
- The HEPPH graph is shown in Fig. 11.
- The CONDMAT graph is shown in Fig. 12.
- The TWITTER, EMAIL-UNIV, FLICKR, and LIVEJOURNAL graphs are shown in Figs. 13–16.
A.2. Distributions for Streaming Graphs (at 20% sample size)
This section presents distribution figures for seven streaming graphs at a 20% sample size.
- The figures cover FACEBOOK, HEPPH, CONDMAT, TWITTER, EMAIL-UNIV, FLICKR, and LIVEJOURNAL graphs.
- The FACEBOOK graph is shown in Fig. 17.
- The HEPPH graph is shown in Fig. 18.
- The CONDMAT graph is shown in Fig. 19.
- The TWITTER, EMAIL-UNIV, FLICKR, and LIVEJOURNAL graphs are shown in Figs. 20–23.