InkStream�Instantaneous GNN Inference on Dynamic Graphs via Incremental Update�

Dan Wu, Zhaoying Li, Tulika Mitra.

School of Computing, National University of Singapore

© Copyright National University of Singapore. All Rights Reserved.

© Copyright National University of Singapore. All Rights Reserved.

Graph Neural Network (GNN)

01

GNN

Social Networks

E-Commerce

Financial Risk Control

Drug Discovery

© Copyright National University of Singapore. All Rights Reserved.

Graph Neural Network (GNN)

02

message

© Copyright National University of Singapore. All Rights Reserved.

Graphs Can Be Dynamic

03

© Copyright National University of Singapore. All Rights Reserved.

Dilemma: Efficiency or Generality?

04

Inefficient

Poor Generality

sum

How to push the generality of incremental update to the boundary?

© Copyright National University of Singapore. All Rights Reserved.

Which Part Should Be Updated?

• Small changes compared with the whole graph.

6

05

© Copyright National University of Singapore. All Rights Reserved.

Incremental Updates Beyond SUM

• Common aggregation functions:
• Monotonic (max/min) are selective.
• Accumulative (mean/sum) are reversible.

​

7

06

1

2

3

4

[2,2,2]

[3,3,3]

[4,4,4]

max aggregator

<3% real affected

1

2

3

4

[2,2,2]

[3,3,3]

[4,4,4]

sum aggregator

[4,4,4]

[4,4,4]

[7,7,7]

[9,9,9]

[9,9,9]

© Copyright National University of Singapore. All Rights Reserved.

Our Solution

8

07

1. Limit the update area bypassing unaffected nodes.
2. Reuse historical information for incremental update.

Key designs:

3/6/25

© Copyright National University of Singapore. All Rights Reserved.

Design 1: Inter-layer Pruned Propagation

• Limit the update area bypassing unaffected nodes.
• Use event to control the propagation.
• Two types of events to add or delete impact of message.

​

​

​

08

Events

Update message of A to B

New message of A to B

Delete old message of A from B

© Copyright National University of Singapore. All Rights Reserved.

Design 2: Incremental Update (Monotonic)

• Reduce all events targeting one vertex with aggregator.
• Check whether incremental update can be applicable.
• Incremental update or recompute.

09

Evolvable

Deleted Msg.

Added Msg.

max aggregator

© Copyright National University of Singapore. All Rights Reserved.

Design 2: Incremental Update (Accumulative)

• Reduce all events targeting one vertex by summing up.
• Incremental update

10

Updated

Message

Deleted

Edge

New

Edge

© Copyright National University of Singapore. All Rights Reserved.

Experiment Setup

11

[1] W. Hamilton et al. Inductive representation learning on large graphs, 2017.

[2]  J. Huang et al. Streaming Graph Neural Networks, 2020

[3] Z. Xie et al. Graphiler: Optimizing graph neural networks with message passing data flow graph, 2022.

© Copyright National University of Singapore. All Rights Reserved.

InkStream is Fast

12

• Reduce inference time from hours to milliseconds even on large-scale dataset.
• Simple model has more benefit when with same model depth.
• InkStream-m has more savings with deeper models for pruned propagation.

100+ h

10-100s ms

© Copyright National University of Singapore. All Rights Reserved.

InkStream is Scalable

13

• Scalable and efficient, good for medium and large datasets.

medium

large

small

© Copyright National University of Singapore. All Rights Reserved.

Takeaways

• Novel finding of “neglected neighbors”.
• InkStream is fast, inference with milliseconds.
• InkStream is scalable, good for large datasets.
• InkStream is general, support common aggregation functions with little restriction on model architecture.

​

​

14

© Copyright National University of Singapore. All Rights Reserved.

THANK YOU

Code Available Here

Scan to Explore the Paper

Any overhead?

What’s the limitation?

Expressiveness?

© Copyright National University of Singapore. All Rights Reserved.