What?

Persistent Message Passing (PMP): persist node states in a smart way instead of overwriting it.

Why?

GNNs work well with Markovian dynamics, i.e. rewriting entities' states and quering the last. The non-Markovian case is important and worth further investigations.

How?

Source: original paper.

Source: original paper.

The setup assumes a set of entities $\mathcal{E}$ (these are not edges!) which are related. Every time step, we do some operations to change some of the entities states and emit an output. An operation might as well be done on a set of past states.

More formally, we have a sequence of pairs $(\mathcal{E}^{(t)}, s^{(t)})$, where $\mathcal{E}^{(t)}=(e_1^t, ..., e_n^t)$ are feature vectors, and $s^t\in\{1,...,t-1\}$ are snapshot indices. A problem the authors consider is to predict operation outputs $y^{(t)}$, where we have persistency: $(\mathcal{E}^{(t)} , s_t) = (\mathcal{E}^{(t')} , s_t') \implies y^{(t)} = y^{(t')}\; \forall t'<t.$ A naive way of doing the above would be memory costly. We can do better.

The picture above gives a intuitive explanation of how PMP works ( I highly recommend looking at the figure before reading all the descriptions below/in the paper):

The whole thing is trained with cross-entropy of relevance and persistency masks against the ground truth.

The motivation for all of the above becomes more clear if we look at the evaluation task. The authors consider range minimum query (RMQ), where we have an array of K integers and have two operations: i) set an element of an array to a new value; ii) query for the minimum value over a particular contiguous range, at a previous point in time.

And?