PaperlayerView exact revision on arXiv

Source-linked AI summary

NeutronStream: A Dynamic GNN Training Framework with Sliding Window for Graph Streams

Chaoyi Chen, Dechao Gao, Yanfeng Zhang, Qiange Wang, Zhenbo Fu, Xuecang Zhang, Junhua Zhu, Yu Gu, Ge Yu

arXiv:2312.02473v1cs.LGcs.DC

TL;DR

Dynamic GNN training frameworks face gaps in handling evolving graph structure and event dependencies, as well as in parallel execution. NeutronStream combines sliding-window training, event-level parallelism, and dynamic graph support; it reports accuracy improvements and speedups over open-sourced PyTorch implementations.

  • Problem

    Existing batched training can miss structural evolution across event batches, while time-dependent events make parallel training difficult.

    Source: §1 · pp. 1–2

  • Method

    NeutronStream trains chronologically on graph streams with a sliding window and dependency-graph-driven event parallelism, alongside dynamic-update graph storage and APIs.

    Source: §1 · p. 2

  • Results

    NeutronStream reports 3.97% average accuracy improvement and 2.26X–12.35X speedups over open-sourced PyTorch implementations across DyRep, LDG, and DGNN.

    Source: §8 · p. 12

  • Takeaways & Limitations

    NeutronStream supports graph-streaming training with parallel execution designed to preserve temporal dependencies between events.

    Source: §2.4 · p. 4

Abstract

from arXiv · show

Existing Graph Neural Network (GNN) training frameworks have been designed to help developers easily create performant GNN implementations. However, most existing GNN frameworks assume that the input graphs are static, but ignore that most real-world graphs are constantly evolving. Though many dynamic GNN models have emerged to learn from evolving graphs, the training process of these dynamic GNNs is dramatically different from traditional GNNs in that it captures both the spatial and temporal dependencies of graph updates. This poses new challenges for designing dynamic GNN training frameworks. First, the traditional batched training method fails to capture real-time structural evolution information. Second, the time-dependent nature makes parallel training hard to design. Third, it lacks system supports for users to efficiently implement dynamic GNNs. In this paper, we present NeutronStream, a framework for training dynamic GNN models. NeutronStream abstracts the input dynamic graph into a chronologically updated stream of events and processes the stream with an optimized sliding window to incrementally capture the spatial-temporal dependencies of events. Furthermore, NeutronStream provides a parallel execution engine to tackle the sequential event processing challenge to achieve high performance. NeutronStream also integrates a built-in graph storage structure that supports dynamic updates and provides a set of easy-to-use APIs that allow users to express their dynamic GNNs. Our experimental results demonstrate that, compared to state-of-the-art dynamic GNN implementations, NeutronStream achieves speedups ranging from 1.48X to 5.87X and an average accuracy improvement of 3.97%.

1 INTRODUCTION

Dynamic GNNs must learn from evolving graph streams, but batched training can miss spatial dependencies and sequential event processing limits parallelism. NeutronStream combines sliding-window training, fine-grained event parallelism, and dynamic graph storage and APIs; its reported evaluations show accuracy gains and speedups.

1 INTRODUCTION

  • Batched training can split spatially local consecutive events across batches, preventing the model from capturing their cross-batch dependency and potentially decreasing accuracy.The motivating example divides six consecutive interactions into two batches; events such as e3 and e4 then lose their spatial dependency.Source: §1 · pp. 1–2
  • NeutronStream trains on consecutive stream events with a sliding window that advances as updates arrive, dropping stale events while capturing evolving information and temporal dependencies.The window slides with a stride of one, and its size can be adjusted to capture complete spatial dependencies.Source: §1 · p. 2
  • A dependency-graph analysis identifies events with non-intersecting affected subgraphs and no node-update conflicts, enabling fine-grained parallel processing.The scheme relies on the observation that each event affects only a small subgraph.Source: §1 · p. 2
  • NeutronStream combines these training approaches with dynamic-update graph storage and easy-to-use APIs for expressing dynamic GNNs with lightweight engineering work.The framework integrates sliding-window training and dependency-graph-driven event parallelization.Source: §1 · p. 2
  • 1.48X–5.87X speedups and 0.46%–6.31% accuracy improvements are reported against open-sourced PyTorch implementations across DyRep, LDG, and DGNN.The evaluation uses three popular dynamic GNN models.Source: §1 · p. 2

2 PRELIMINARIES

These preliminaries describe GNN layer computations, graph-stream representations, and event-based dynamic GNN training. They also contrast NeutronStream’s streaming support with existing frameworks’ offline constraints.

2.1 Graph Neural Networks

  • Each GNN layer aggregates incoming-neighbor embeddings into an intermediate representation, then updates the node embedding using that representation and the layer parameters.Stacked propagation layers learn representations for graph nodes.Source: §2.1 · pp. 2–3

2.2 Graph Streams

  • A graph stream pairs an initial graph state with chronologically ordered update events; snapshots can omit changes and temporal dependencies within an interval.Events encode involved nodes, timestamp, and update type; the paper focuses on graph streams because they record dynamic information and temporal dependencies.Source: §2.2 · p. 3

2.3 Dynamic GNN Training Abstraction

  • Event-based dynamic GNN training processes events chronologically, updates affected graph topology and node embeddings, predicts downstream labels, and updates model parameters from the loss.Event computations use affected subgraphs and can include elapsed-time information, neighborhood aggregation, and propagation of updated embeddings to neighbors.Source: §2.3 · p. 3

2.4 Limitations of Existing Frameworks

  • Existing dynamic GNN implementations mainly support offline training, while TGL requires the entire dynamic graph in advance and its intra-batch parallelism can break temporal dependencies.NeutronStream is presented as the first dynamic GNN framework supporting graph-streaming training, with parallel execution designed to preserve event dependencies.Source: §2.4 · p. 4

3 DYNAMIC GNN TRAINING WITH SLIDING WINDOW

NeutronStream trains on chronological windows that slide across an event stream, and adaptively adjusts window size to capture spatially local event groups. The method bounds window size while including consecutive events that share event nodes.

3.1 Incremental Mode with Sliding Window

  • The training process selects chronological events from a stream, feeds each window to the dynamic GNN, and slides by stride d until the stream ends.For an infinite stream, it can continuously accept new events and launch training on new windows.Source: §3.1 · p. 4
  • Stride d trades information retention for training efficiency: larger strides train faster but lose more information.Window size s controls how much data is fed to the model at each step.Source: §3.1 · p. 4

3.2 Adaptive Adjustment of Window Size

  • A fixed window of four events cannot contain either of two spatially local event groups in the example, motivating dynamically adjustable windows.The paper notes that windows that are too small may contain little information, while overly large windows may introduce noise.Source: §3.2 · p. 4
  • Adaptive windows add consecutive events whose endpoint nodes overlap nodes already in the window, stopping at no overlap or the maximum size.The minimum size ensures a baseline amount of training data; the maximum bounds the window when associations continue.Source: §3.2 · pp. 4–5
  • The adaptive window method groups spatially local events, while using event-node intersection instead of subgraph intersection to avoid more time-consuming dependency analysis.The paper notes that most dynamic GNNs update event nodes rather than their neighbors.Source: §3.2 · p. 5

4 DEPENDENCY-GRAPH-DRIVEN EVENT PARALLELIZING

NeutronStream identifies event dependencies from read-write conflicts and represents them in an event dependency graph. It executes events from different dependency chains in parallel while preserving temporal dependencies.

4 DEPENDENCY-GRAPH-DRIVEN EVENT PARALLELIZING

  • Event computations use subgraphs of event nodes and their neighbors, so events with disjoint subgraphs can execute in parallel.The example's purple and green affected subgraphs are disjoint.Source: §4 · p. 5, Figure 3 · p. 6

4.1 Dependency Analysis of Event Processing

  • An event depends on an earlier event when its affected-node set intersects that earlier event's update set; dependencies are transitive.The affected subgraph is the read range, and the triggered update set is the write range.Source: §4.1 · pp. 5–6
  • Non-adjacent events in a dependency chain need not have a read-write conflict, while adjacent events satisfy the direct-dependency condition.The paper describes the conflict condition as sufficient for dependency.Source: §4.1 · p. 6
  • Events in different dependency chains can execute in parallel, while the dependency-analysis algorithm guarantees temporal dependencies.The paper contrasts this with frameworks that process events sequentially because they cannot analyze event dependencies.Source: §4.1 · p. 6

4.2 Parallelization based on Event Dependency Graph

  • The event dependency graph records events and their dependencies; a scheduler places events with empty dependency sets in a queue for parallel execution.The graph-generation algorithm identifies direct dependencies before execution.Source: §4.2 · pp. 6–7

5 NEUTRONSTREAM

NeutronStream combines dynamic graph and multi-version embedding storage with APIs for expressing event updates, plus a parallel event-processing engine that pipelines sliding windows while preserving temporal dependencies.

5.1 Dynamic Graph Storage

  • Dynamic graph storage separates incoming and outgoing edges, while multi-version node-embedding storage supports batch backpropagation for repeatedly updated nodes.The graph structure supports dynamic updates; the embedding structure uses initialized and updated embedding arrays plus a node-version array.Source: §5.1 · p. 7

5.2 Programming Model and APIs

  • Four user-defined interfaces—UpdateGraph, Aggregate, UpdateEmb, and PropUpdate—let model developers express event execution using NeutronStream’s underlying graph and embedding storage.For DyRep, users define UpdateGraph, Aggregate, and UpdateEmb.Source: §5.2 · p. 8

5.3 Event Processing Engine and Pipelining

  • The event-processing engine determines sliding windows, analyzes event dependencies, schedules executable events, and runs them in parallel.Its four modules are adaptive sliding window, event parallel analysis, event parallel scheduling, and event execution.Source: §5.3 · p. 8
  • Pipelining lets modules process different event windows concurrently, reducing module waiting time while retaining dependency information needed to capture dynamic information correctly.Figure 7 uses green, blue, and yellow to distinguish training-event windows.Source: §5.3 · pp. 8–9, Figure 7 · p. 9
  • With temporal dependency, DyRep and DGNN retain higher accuracy than without dependency; omitting dependency gives higher speedup, while dependency analysis takes a small share of total time.Figure 8 compares accuracy and Figure 9 shows the dependency-analysis time ratio; the analysis timing was recorded with pipeline optimization off.Source: §5.3 · p. 9, Figure 8 · p. 9, Figure 9 · p. 9

6 EXPERIMENTAL EVALUATION

NeutronStream was evaluated on DyRep, LDG, and DGNN using six datasets, comparing batch, sliding-window, and adaptive-window training. The experiments examine accuracy, runtime, parameter choices, graph storage, and pipeline optimization.

6.1 Experimental Setup

  • The experiments use three dynamic GNN models, six datasets, and link prediction, with equal training iterations per event across methods.The setup includes temporal point-based DyRep and LDG and RNN-based DGNN; batch size is 200, while sliding-window settings vary by method.Source: §6.1 · pp. 9–10

6.2 Runtime Comparison

  • NeutronStream’s training methods outperform Torch-Batch in runtime, with NS-Batch speedups of 1.53X–2.26X on DyRep, 1.48X–2.33X on LDG, and 3.01X–5.87X on DGNN.NS-AdaSlide also improves runtime over Torch-Batch; DyRep and LDG report out-of-memory errors on Reality and Slashdot, where NS-Batch achieves 3.20X and 5.87X speedups over DGNN, respectively.Source: §6.2 · p. 10, Figure 10 · p. 11

6.3 AUC Comparison

  • Adaptive sliding-window training achieves the highest AUC, sliding windows improve on batch training, and PyTorch batch training matches NS-Batch.The authors attribute the batch method’s lower AUC to cutting off the stream and losing training information.Source: §6.3 · p. 10, Table 3 · p. 10

6.4 Performance Gain Analysis

  • In the adaptive-window method, event-parallel optimization yields 1.19X–1.43X speedups over Base, and pipelining adds 1.08X–1.28X over parallel optimization.Parallel gains are lower on the small Social dataset and higher on sparse DNC; pipeline gains are more pronounced on UCI as dependency analysis grows with graph size.Source: §6.4 · p. 10, Figure 12 · p. 11

6.5 Evaluation the Impact on Parameters

  • Smaller strides improve accuracy but lengthen training; in NS-AdaSlide, strides of 0.5W and 0.8W provide average speedups of 2.55X and 4.09X over 0.2W.NS-Slide shows the same accuracy–runtime trend, and NS-AdaSlide has higher accuracy than NS-Slide at the same stride ratio.Source: §6.5 · pp. 10–11, Figure 13 · p. 11, Figure 15 · p. 12
  • On DGNN with Github, window size 100 yields 84.17% accuracy for sliding windows and 84.45% for adaptive windows; larger windows increase parallelism and shorten runtime.For the tested L and H ranges, smaller L improves accuracy, while changing H at fixed L does not when windows contain at most 250 events; [150,300] has the shortest runtime.Source: §6.5 · p. 11, Figure 11 · p. 11, Table 4 · p. 11

6.6 Performance of Dynamic Graph Storage

  • NeutronStream’s graph queries achieve 1.42X–2.46X speedups over DyRep, 1.44X–2.42X over LDG, and 2.32X–5.11X over DGNN.The compared models require the total node count before training and therefore do not support adding or removing nodes.Source: §6.6 · pp. 11–12, Table 5 · p. 11

6.7 Analysis of Pipeline Benefits

  • Pipeline benefits mainly come from overlapping dependency analysis, the costly component; adding window determination or event scheduling alone reduces runtime little.The evaluation measures per-epoch runtime as components are added sequentially to the pipeline.Source: Figure 14 · p. 11, §6.7 · p. 12

7 RELATED WORK

Related work covers frameworks for static GNNs and the smaller set of frameworks for dynamic graphs. The paper distinguishes snapshot-based from continuous-time dynamic graphs and identifies limitations in existing support for graph streams.

Static GNN Frameworks

  • Static GNN frameworks provide message-passing interfaces, graph abstractions, distributed training, or architecture search, but their storage and execution engines do not effectively support dynamic graph updates and training.Examples discussed include PyG, DGL, DistDGL, Sancus, PASCA, and NeutronStar.Source: §7 · p. 12

Dynamic GNN Frameworks

  • Dynamic graphs are categorized as snapshot-based or continuous-time; continuous-time models represent update events as a stream and capture temporal information.The passage contrasts this with snapshots, which store graph state at particular times.Source: §7 · p. 12
  • Existing dynamic-graph frameworks primarily target snapshots, while TGL supports graph streams but stores the entire graph statically and disregards within-batch temporal dependencies.The passage names PyGT, DynaGraph, and PiPAD as snapshot-based frameworks and describes TGL’s Temporal-CSR structure and intra-batch parallel training.Source: §7 · p. 12

8 CONCLUSIONS AND FUTURE WORK

NeutronStream combines sliding-window incremental training, event-parallel processing, and system optimizations for dynamic GNNs. Across DyRep, LDG, and DGNN, the authors report average accuracy improvement of 3.97% and speedups of 2.26X–12.35X over open-source PyTorch implementations.

8 CONCLUSIONS AND FUTURE WORK

  • NeutronStream combines a sliding-window method, fine-grained event-parallel processing, and system optimizations for dynamic GNN training.The authors evaluate the framework on DyRep, LDG, and DGNN.Source: §8 · p. 12
  • 3.97% average accuracy improvement and 2.26X–12.35X speedups are reported against open-source PyTorch implementations across the evaluated models.The conclusion identifies online training for dynamic graphs as future work.Source: §8 · p. 12

Related papers

Loading 2312.02473v1…