PaperlayerView exact revision on arXiv

Source-linked AI summary

InkStream: Real-time GNN Inference on Streaming Graphs via Incremental Update

Dan Wu, Zhaoying Li, Tulika Mitra

arXiv:2309.11071v1cs.LGcs.DCcs.PF

TL;DR

Streaming graphs need frequent updates, while static-graph inference and repeated retraining are ill-suited to prompt responses. InkStream uses selective event propagation and incremental embedding updates to reduce computation and memory access. It produces identical results to conventional inference while reporting speedups across CPU and GPU clusters.

  • Problem

    Streaming graphs evolve and need frequent node-representation updates, while retraining can be impractical for applications requiring prompt responses.

    Source: §1 · p. 1

  • Method

    InkStream propagates embedding changes only when needed and incrementally updates affected nodes using prior results and changed neighbors’ information.

    Source: §1 · pp. 2–3

  • Results

    2.5-427× speedup on a CPU cluster and 2.4-343× on two GPU clusters, with identical results to conventional inference.

    Source: §1 · p. 4, §8 · p. 11

  • Takeaways & Limitations

    InkStream supports GCN, GraphSAGE, and GIN through simple configuration, requiring fewer than 10 lines of additional user code in those test cases.

    Source: §1 · p. 3

    The current method supports only min/max aggregation; delta-accumulative extensions can lose precision, and host–GPU communication and parallelism remain unoptimized.

    Source: §7 · p. 11

Abstract

from arXiv · show

Classic Graph Neural Network (GNN) inference approaches, designed for static graphs, are ill-suited for streaming graphs that evolve with time. The dynamism intrinsic to streaming graphs necessitates constant updates, posing unique challenges to acceleration on GPU. We address these challenges based on two key insights: (1) Inside the $k$-hop neighborhood, a significant fraction of the nodes is not impacted by the modified edges when the model uses min or max as aggregation function; (2) When the model weights remain static while the graph structure changes, node embeddings can incrementally evolve over time by computing only the impacted part of the neighborhood. With these insights, we propose a novel method, InkStream, designed for real-time inference with minimal memory access and computation, while ensuring an identical output to conventional methods. InkStream operates on the principle of propagating and fetching data only when necessary. It uses an event-based system to control inter-layer effect propagation and intra-layer incremental updates of node embedding. InkStream is highly extensible and easily configurable by allowing users to create and process customized events. We showcase that less than 10 lines of additional user code are needed to support popular GNN models such as GCN, GraphSAGE, and GIN. Our experiments with three GNN models on four large graphs demonstrate that InkStream accelerates by 2.5-427$\times$ on a CPU cluster and 2.4-343$\times$ on two different GPU clusters while producing identical outputs as GNN model inference on the latest graph snapshot.

1 INTRODUCTION

InkStream targets prompt GNN inference on evolving graphs, where static-graph inference and repeated retraining do not meet real-time needs. It uses selective propagation and incremental updates to reduce work while preserving conventional inference results.

1 INTRODUCTION

  • Streaming graphs require frequent node-representation updates, but retraining can take too long for applications needing prompt responses.A periodically retrained model snapshot can instead support updates between retraining intervals.Source: §1 · p. 1
  • For min/max aggregation with static weights, only a fraction of nodes in the theoretically affected area may actually be influenced by changed edges.On average, 3% of nodes were influenced in Cora and Yelp with 100 updates.Source: §1 · p. 2
  • With static model weights, a node embedding can be incrementally updated by canceling a changed neighbor’s old contribution and adding its new one.This reuses prior results and avoids fetching the unchanged portion of the neighborhood.Source: §1 · p. 2
  • InkStream uses events to propagate embedding changes between layers, prunes propagation at resilient nodes, and reuses prior results during within-layer aggregation.A resilient node could be affected but turns out to be uninfluenced.Source: §1 · p. 3
  • InkStream can be configured for GCN, GraphSAGE, and GIN with fewer than 10 lines of additional user code.Its selective monotonic aggregation preserves identical results when the same input is selected.Source: §1 · p. 3
  • 2.5-427× on a CPU cluster and 2.4-343× on two GPU clusters; InkStream produces identical results to conventional inference.The evaluation covers three GNN models and four datasets.Source: §1 · p. 4

2 INKSTREAM

InkStream takes a full-graph inference as its starting point, saves pre- and post-aggregation embeddings, and describes supported GNNs through message-passing operations. Its expressiveness is bounded by selective min/max aggregation and local dependence between consecutive layers.

2 INKSTREAM

  • InkStream starts from full-graph inference and saves each node’s embeddings before and after aggregation in every layer for incremental updates.The authors describe the memory cost as acceptable because hidden states are usually small.Source: §2 · p. 4

2.1 Notations for Streaming Graphs

  • Table 1 defines streaming-graph and GNN notation, including modified edges ΔE, neighborhood N(u), and the aggregation input m_l and output α_l.A superscript − marks a value from the previous timestamp.Source: §2.1 · p. 4, Table 1 · p. 4

2.2 Expressiveness

  • InkStream supports message-passing GNNs whose aggregation selects neighbor messages with min or max, enabling layer-level pruning and lossless incremental updates.The passage notes that min and max are commonly used and cites their competitive expressiveness across varied GNN models [10] [14] [26] [33].Source: §2.2 · p. 4
  • Each next-layer message must depend only on the node’s prior message and aggregated neighborhood; this excludes batch normalization, graph normalization, normalized-weight aggregation, and GAT [32].The stated dependency limits changed-edge effects to edges or the node itself in the next layer.Source: §2.2 · p. 4

2.3 InkStream Workflow

InkStream manages streaming-graph updates as events passed between GNN layers. It groups events by target and operation, applies incremental updates when feasible, and propagates changed embeddings to neighboring nodes.

2.3 InkStream Workflow

  • For each changed edge, InkStream creates events in the first layer; subsequent layers process grouped events, incrementally update targets when feasible, and propagate only changed embeddings.If incremental updating is not applicable, the target’s full neighborhood is fetched for classic recomputation; unchanged embeddings stop propagation.Source: §2.3 · p. 4

2.4 Inter-Layer: Event-based Computing Model

  • The event queue separates event metadata from shared embedding messages, while unchanged node embeddings stop further event propagation.An event specifies an operation, target node, and embedding vector; events are grouped and reduced before propagation.Source: §2.4 · p. 5, Figure 6 · p. 5, Figure 7 · p. 5

2.4.1 Event Grouping.

  • Grouping events by target avoids repeated neighborhood fetches and lets InkStream assess all changes together before choosing an incremental update or correct recomputation.Events with the same operation are reduced using the aggregation function; processing additions and deletions independently can produce a wrong result or require recomputing the neighborhood.Source: §2.4.1 · p. 5, Figure 8 · p. 5

2.4.2 Event Propagation.

  • For affected nodes, InkStream cancels the old message along previous-timestamp edges, then adds the new message along current-timestamp edges.Duplicate events can arise when a changed-edge destination is also affected in the prior layer; the text says they do not affect the final result with monotonic aggregation and add trivial memory overhead.Source: §2.4.2 · pp. 5–6

2.5 Intra-layer: Incremental Update

InkStream incrementally updates a node’s aggregation only when event effects permit it, otherwise recomputing from current neighbors. Changed embeddings propagate to the next layer, while resilient nodes stop propagation.

2.5.1 Applicable Conditions.

  • Deleted messages are reduced before checking reset positions, because a reset can occur only where a deleted message has the minimum or maximum value.The reduced added messages are computed separately for the update check.Source: §2.5.1 · p. 6
  • Incremental updates are valid with no reset or when added messages cover every position that needs resetting; exposed resets require recomputation.For a covered reset, the reduced added message must be better than the deleted value at each reset position.Source: §2.5.1 · p. 6

2.5.2 Update and Propagate.

  • After an applicable update, InkStream checks whether the node’s result changed; unchanged nodes stop propagation, while updated or recomputed nodes propagate effects to the next layer.An added message can leave the old result unchanged under the no-reset condition.Source: §2.5.2 · p. 6
  • When incremental updating is inapplicable, InkStream fetches and aggregates all current-neighbor messages to recompute the node.The messages are available without additional computation; affected neighbors’ values are computed while processing the preceding layer.Source: §2.5.2 · p. 6

2.6 Flexible User-Defined Functions

InkStream lets users define functions for creating, propagating, grouping, and applying customized events, alongside its native event management.

2.6 Flexible User-Defined Functions

  • The user_propagate function creates and propagates customized events alongside InkStream’s built-in propagation.Customized event management is isolated from native functions.Source: §2.6 · p. 6
  • The user_grouping function specifies how customized events are grouped and processed during event grouping.Source: §2.6 · p. 6
  • The user_apply function applies customized event effects to a tensor at a phase level, with phase execution order managed through a short model configuration.Source: §2.6 · p. 6

2.7 Support for other operators

InkStream supports sampling and pooling through adaptations while remaining sampling-free by default. Pooling is executed in its original way after node embeddings before the pooling layer are updated.

2.7 Support for other operators

  • InkStream uses no sampling by default because it is GPU-memory-friendly.Source: §2.7 · p. 6
  • Sampling can be supported by propagating events only to selected neighbors; one solution caches and reuses prior samples and assumes newly inserted edges are selected.Source: §2.7 · p. 7
  • Graph-level pooling is not natively supported by InkStream, so inputs are fetched and pooling runs as originally implemented after preceding node embeddings are updated.Source: §2.7 · p. 7

3 INTEGRATION WITH GNN MODELS

InkStream integrates GNN models through a sequential operation description and, where needed, user-defined functions. The paper describes support for GCN, GraphSAGE, and GIN.

3 INTEGRATION WITH GNN MODELS

  • The model description lists operations sequentially and partitions execution around aggregation phases, where events are propagated and grouped.The configuration uses min/max for incremental aggregation and user_apply to invoke a customized function.Source: §3 · p. 7

3.1 GCN

  • GCN uses InkStream’s native events because its combination phase consumes the aggregation result; changed embeddings propagate to neighbors when they change.Events are grouped at aggregation, then the target node is incrementally updated or its aggregation result transformed by subsequent operations.Source: §3.1 · p. 7

3.2 GraphSAGE

  • GraphSAGE uses user-defined events to pass a node’s changed embedding to itself in the next layer, and its neighborhood sampling is skipped.The model description applies the incremental update, computes the two combination terms, then applies ReLU.Source: §3.2 · p. 7

3.3 GIN

  • GIN configuration is similar to GraphSAGE but simpler.Source: §3.3 · p. 8

4 EXPERIMENT EVALUATION

The evaluation compares InkStream with full-graph and affected-area inference across CPU and GPU platforms. It uses streaming-update workloads and PyG-based GNN implementations.

4.1 Experiment Setup

  • The benchmarks use PyG model examples with monotonic aggregation, ReLU activation, and normalization disabled, and simulate edge creation and deletion over recent graph snapshots.They use 1, 10, or 100 updates between timestamps and the latest 500k edges; Reddit’s one-hot degree features are capped at length 500.Source: §4.1 · p. 8
  • Full and Affected infer from the latest graph snapshot, while InkStream reuses host-resident intermediate results and performs dense combination computations on the GPU.Baseline loaders use batch size 16 and four workers; InkStream processes unique target nodes sequentially.Source: §4.1 · p. 8
  • Evaluation platforms comprise a 112-core CPU cluster, a 104-core CPU with an NVIDIA RTX A6000, and a 128-core CPU with an AMD MI100.Figure 11 compares speedup against Affected for one edge update, with a log-scale y-axis.Source: §4.1 · p. 8, Figure 11 · p. 9

5 EXPERIMENT RESULT

InkStream improves inference speed and reduces memory access by updating affected embeddings incrementally, with benefits varying by model and update workload. The experiments also measure when incremental updates apply and the memory cost of saved intermediate results.

5.1 Performance

  • 2.5–427× speedup over Affected is reported across platforms for one edge update, although InkStream does not use parallelization.The comparison is against affected-area inference, which uses four-worker multiprocessing.Source: §5.1 · p. 9
  • GraphSAGE has the lowest speedup because changed edges propagate to the node itself in the next layer, and GPU platforms add CPU–GPU communication for user_apply data.GraphSAGE’s self-impact makes nodes more easily affected.Source: §5.1 · p. 9
  • InkStream shows superior speedup on GIN across all three platforms, while classic inference repeats computation across large, overlapping ego networks.A 5-hop ego network can reach 80% of the graph; GIN’s input feature vector is nearly 10× the final embedding size, and InkStream updates embeddings before pooling.Source: §5.1 · p. 9
  • Speedup trends downward as updates between timestamps increase, because more neighborhood changes raise the affected share and monitoring overhead can outweigh skipped computation.Figure 12 evaluates the effect of update count on GPU-N.Source: §5.1 · p. 9, Figure 12 · p. 9

5.2 Applicable Condition Distribution

  • Over 70% of visited nodes in GCN and GraphSAGE can be incrementally updated; GIN has a non-negligible exposed-reset share.When a node qualifies, InkStream can avoid fetching its whole neighborhood; in GIN’s last layer, extensive neighborhood changes can cause unrecoverable data loss.Source: §5.2 · p. 9, Figure 13 · p. 10

5.3 Memory Access

  • GCN memory access is reduced by 110–1485×; shallow GraphSAGE achieves 16–1273× reduction, while deeper models achieve only 1.5–18.8×.The reported memory-access comparison assumes one edge update; deeper models can incur high recomputation when many nodes are affected.Source: §5.3 · p. 10, Figure 14 · p. 10

5.4 Additional Memory Cost

  • Saved intermediate results add memory overhead equal to 0.12–3.4× dataset size for GIN and SAGE; GIN’s overhead is 1.3× with one-hot degree features capped at 500.InkStream saves intermediate results immediately before and after each aggregation phase.Source: §5.4 · p. 10

6 RELATED WORKS

Prior streaming GNN work addresses evolving graphs through retraining or specialized models, while streaming graph analytics uses incremental state updates. The paper distinguishes these approaches from InkStream’s GNN inference setting.

6.1 Streaming Graph Neural Networks

  • Streaming GNN approaches include retraining-based methods, DyGNN’s edge-insertion updates limited to at most two layers, T-GCN’s accelerated but still lengthy retraining, and AEGNN’s static graph structure.T-GCN reports 10–100× acceleration yet still takes minutes to hours because of retraining overhead.Source: §6.1 · p. 10

6.2 Streaming Graph Analytics

  • Streaming graph analytics differs from GNN inference in affected-area reach, state size, and spatial or temporal transitivity, which makes prior incremental methods not directly applicable.GNN edge effects extend up to k hops, hidden states can span tens to thousands of values, and non-monotonic combination functions require canceling prior impact.Source: §6.2 · pp. 10–11

7 LIMITATION AND FUTURE WORK

InkStream’s current scope and implementation have limits in aggregation support, numerical behavior, parallelism, and pooling.

7 LIMITATION AND FUTURE WORK

  • InkStream currently supports min/max aggregation, has unoptimized host–GPU communication and single-worker execution, and does not support global pooling layers.Accumulation-based extensions are possible, but floating-point effects can make delta-accumulative error grow with layer count.Source: §7 · p. 11

8 CONCLUSION

InkStream incrementally updates GNN inference on streaming graphs by reusing embeddings and trimming redundant computation. It reports substantial acceleration without compromising accuracy.

8 CONCLUSION

  • InkStream accelerates GNN inference by 2.5-427× on a CPU cluster and 2.4-343× on two different GPU clusters.The paper reports these performance boosts without compromising accuracy.Source: §8 · p. 11
  • InkStream trims redundant computations and reuses embeddings from the previous timestamp for incremental updates.Source: §8 · p. 11
  • For models using monotonic aggregators, theoretical and actual affected nodes differ on streaming graphs.Source: §8 · p. 11

Related papers

Loading 2309.11071v1…