Streaming Graph Neural Networks WOODSTOCK’97, July 1997, El Paso, Texas USA
𝑡
"
𝑡
#
𝑡
$
𝑡
%
𝑡
&
𝑡
'
𝑡
(
𝑡
)
𝑣
$
𝑣
%
𝑣
&
𝑣
'
𝑣
(
𝑣
)
𝑣
"
𝑣
+
Update
Component
Input
𝑣
%
𝑡
&
𝑣
(
𝑡
)
𝑡
"
𝑣
%
𝑣
(
output
𝑣
$
𝑣
"
𝑡
#
𝑡
&
𝑣
&
𝑣
)
𝑡
)
𝑡
(
𝑣
%
𝑣
(
𝑡
"
Propagation
Component
𝑣
$
𝑣
"
𝑣
&
𝑣
)
Newly emerging edge
Existing edges
Interacting nodes Influenced nodes
Not involved nodes
Figure 1: An overview of DGNN when a new interaction happened at time t
7
from v
2
to v
5
. The two interacting nodes are v
2
and v
5
. The nodes {v
1
, v
3
, v
6
, v
7
} are assumed to be the inuence d nodes.
𝑣
"
𝑣
#
Interact Unit
S-Update Unit
Merge Unit
𝑣
$
𝑣
"
Interact Unit
G-Update Unit
Merge Unit
𝑣
"
𝑣
%
Interact Unit
S-Update Unit
Merge Unit
𝑡
'
− 0 𝑡
*
− 𝑡
'
𝑡
$
− 𝑡
*
𝑡
'
The update component
𝑡
*
The update component
𝑡
$
The update component
Figure 2: The operations of update components with the fo-
cus on node v
2
and all its interactions
hidden states for the two roles of each node, respectively. The cell
memory and hidden state for the source role of node
v
right before
time
t
are denoted as
C
s
c
(t−)
and
h
s
v
(t−)
respectively, while the cell
memory and hidden state for the target role of node
v
right before
time
t
are denoted as
C
д
c
(t−)
and
h
д
v
(t−)
separately. Here, the no-
tation t− means the time that is innitely close to t, but prior to t,
such that all the interactions before time
t
have been processed. For
example, in Figure 2, at time
t
7
, for node
v
2
,
C
s
c
(t
7
−)
is, in fact, equal
to
C
s
c
(t
3
)
. Note that we do not consider the propagation component
now, for the purpose of illustrating the update component. The
source and target hidden states are merged with the merge unit, to
generate the general features
u
v
(t−)
of the node
v
, which describes
the general property of node
v
. These cell memories
C
s
c
(t−)
,
C
д
c
(t−)
,
hidden states
h
s
v
(t−)
,
h
д
v
(t−)
and general features
u
v
(t−)
are the
information stored for each node
v
and needed to be updated when
new interaction happens. For example, Figure 3 shows the oper-
ations of two update components performing update for node
v
2
and
v
5
when the interaction
{v
2
, v
5
, t
7
}
happens. The information
stored for the two nodes right before time
t
7
is shown in Figure 2 (a).
2.1.1 The interact unit. The interact unit is designed to generate
the interaction information for
{v
s
, v
д
, t}
from node information.
The generated interaction information is later used as the input
of the update unit. We model the interact unit using a deep feed-
forward neural network and the formulation is as follows:
e(t) = act (W
1
· u
v
s
(t−) + W
2
· u
v
д
(t−) + b
e
) (1)
where
u
v
s
(t−)
and
u
v
д
(t−)
are the general features of the nodes
v
s
and
v
д
right before time
t
.
W
1
,
W
2
and
b
e
are the parameters of the
neural network and
act (·)
is an activation function such as sigmoid
or tanh. The output
e(t)
contains the information of the interaction
{v
s
, v
д
, t}
. As an example, Figure 3 (b) shows how the interact unit
works for the interaction {v
2
, v
7
, t
7
}.
2.1.2 The update unit. As mentioned before, the interactions
(involving the same node) can be viewed as a “sequence”. The infor-
mation of this node gradually evolves as these interactions happens
sequentially. Thus, to capture these interaction information for this
node, we recurrently apply the update component to process the
interaction information. The update unit is the part performing the
operation to update the interaction information generated from the
interact unit to the interacting nodes. Recall that the interactions do
not emerge evenly in time. The time interval between interactions
involving the same node can vary dramatically. The time interval
impacts how the old information should be forgotten. It is intuitive
that interactions happened in the far past should have less inuence
on the current information of node, thus they should be “heavily"
forgotten. On the other hand, recent interactions should have more
importance on the current information of node. Thus, it is desired to
incorporate the time interval into the update component. Hence, to
build the update unit, we modify the LSTM unit as similar in [
3
] to