- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The authors point out a crucial shortcoming in temporal link prediction: negative-sampling strategies for constructing training examples for current temporal-graph-learning models provide training examples that cancel out the course of interactions. Therefore, models become blind to which node is active, and they cannot use this information for making link predictions. To address this issue, the authors introduce SNAM (Source Node Activity Modeling), which I would paraphrase as "estimating nodes' activity at prediction time point t based on their recent history". A nice aspect of their approach is that it is extremely lightweight with "fewer than 20 parameters", and that it can be combined with TGNN models without the need for retraining. Across a range of standard temporal link-prediction benchmarks, the authors show the effectiveness of their approach and that it improves the performance of other TGNN models.
I find the paper very well written, and the authors' line of thought is easy to follow. There is a clear red thread through the paper, and nothing seems out of place. Personally, I would have preferred one page fewer of maths and definitions and instead some more figures and discussion that "looks under the hood" and helps the reader build intuition -- but that may just be personal preference.
Critical strengths
The authors present one simple idea that changes our understanding of how current TGNNs for temporal link prediction work and how the way we construct training data affects what they can learn.
Critical weaknesses
None
Questions for authors
I do have a couple of questions I have been thinking about while reading the paper:
- You mention in the second paragraph on page 2 that "SNAM [...] can be added to other link prediction models [...] without retraining". I understand this as "other models can use SNAM as they are, no retraining is necessary", but what if we decided to retrain? Is there some information that SNAM could provide during training that could improve performance even more? Don't get me wrong, I think it is a strength that no retraining is necessary. I am merely wondering about the "what if?".
- In the third paragraph on page 2, you mention that Multi-Timescale Historical Representation learns nodes' activity at K time scales. What are the breaking points of this approach? I suppose that it is difficult to detect every possible time scale at which a node might interact. For example, some nodes might interact at a high frequency while others interact infrequently. Yet others might have truly random interaction patterns so that they do not allow any sensible predictions. What happens, for example, when the data contains interactions at too many time scales, say 2K time scales? And are nodes that interact truly randomly somehow shoehorned into the K time scales?
- When reading the equations, it took a moment before I understood one detail of the notation: Take Eq. 9 where you write . I did not immediately see where and came from, as they do not enter as a parameter. But then I realised that you probably used this as shorthand for the definition of from the line above, and then indexed it. Is that what you mean? This is probably not a huge problem, but the clarity might be improved a little here.
- The loss in Eq. 13 is a sum of two sub-losses, which makes me wonder whether there might be situations where one of them dominates the other. Specifically, could it be possible that the parameters are chosen in such a way that the "ordinary" link-prediction loss dominates the optimisation and the node-activity loss becomes negligible? Perhaps you have pointed this out somewhere, and I have missed this, but is there a property that guarantees "the same scale" for both losses or something similar that makes he composite loss well-behaved?
- What does the last row of Table 1 really show, that is, the row titled "Overall Avg. Rank"? Is it the average rank over three different negative-sampling strategies for all datasets? That is, does each dataset enter the number three times, once for each negative-sampling strategy? I am not entirely sure that this is a number that makes sense to calculate, as it somewhat mixes different things, but I may be wrong.
Minor points
- The dagger symbol is used in Table 2, but only defined in Table 4.
- What is the star in Table 3?
9 comments
Q1. What if the backbone were retrained together with SNAM?
Your reading is correct, and the "what if" has a definite answer. Retraining a model together with SNAM would give exactly the same model and exactly the same SNAM as training them separately, so there is nothing further to gain from it.
Take TPNet and suppose we retrain it together with SNAM. In every training step, TPNet's link-prediction loss is computed from TPNet's own scores. It contains neither SNAM's parameters nor SNAM's output. SNAM's loss is the likelihood of the event times, and it contains nothing from TPNet. Each step therefore changes TPNet's weights exactly as it would without SNAM, and changes SNAM's parameters exactly as it would without TPNet. At the end we hold the same TPNet and the same SNAM as in Table 2, and adding them gives the same results.
In symbols, the joint objective is Eq. 13, , where are the backbone's parameters and are SNAM's. The two terms share no parameter, so the gradient of the sum with respect to is the gradient of alone, and the gradient with respect to is that of alone. Minimizing the sum is the same computation as minimizing each term by itself. When one minimizes by gradient descent, the updates of do not depend on the second term, whatever its scale.
Training together gives a different result only when the two losses share parameters, as in multi-task learning, or when the output of one model enters the loss of the other. Neither holds here.
One could build such a coupling on purpose, for example by adding to the backbone's score during training. By the analysis of Section 4.1 this would not help. A positive and its negative have the same source and timestamp under standard training, so the added term is the same for both, and the optimum of the trained score is the same as before. The backbone would only learn to offset the term. This is why SNAM is fitted on its own, by its likelihood, and added to the score after training.
Q2. Breaking points of the K timescales
We should have explained this in the main text. The timescales are not interaction frequencies that the model has to detect, and no node is assigned to one of them. They are fixed basis functions, and every node is described by all of them at once. The design follows from two mathematical facts, both in Appendix D.
Why exponentials. For each node and each decay rate we keep a decayed count of its past events,
and the backbone keeps decayed sums of neighbour embeddings in the same way. The exponential is the only decaying weight for which such a sum can be updated exactly from its previous value, without going back through the history (Appendix D.1).
Why several, spaced logarithmically. A single exponential forgets at one fixed speed. Influence that fades slowly, such as a power law, is exactly a mixture of exponentials (Eq. D.5):
Evaluating this integral at points equally spaced in gives , which is our grid (Appendix D.3). The rates are therefore the sample points of an integral, and the weights are learned from the data. A pattern whose timescale lies between two grid points is represented by a combination of its neighbours, and a denser grid only makes the approximation finer.
The range of the grid comes from the data. Its fastest timescale is the smallest gap between two training timestamps, its slowest is the whole training period, and there are about two timescales per factor of ten in between, at most 16 in total (Appendix D.4). The fastest and the slowest behaviour in the training data are both inside this range.
With this picture, your questions have direct answers.
Data with timescales. They do not have to coincide with ours, because any timescale inside the range is covered by the basis. We also ran this experiment. Doubling from our default (14 to 16) to 27 to 32 changes the transductive AP of our full model under historical negatives by at most 0.4 points on all five datasets, and costs about 1.3 times the training time (Tables 4 and 15, Appendix I.4). Two timescales per factor of ten are already enough.
Breaking point. Too few timescales. With the same AP falls by 1.3 to 16.6 points, for example from 96.0 to 79.5 on UCI and from 90.2 to 77.5 on Reddit.
Nodes that interact truly at random. No. The model does not assign a node to a timescale, and every node, random or not, has all decayed counts. For a truly random node, whose events arrive at a constant rate, the times of its past events say nothing more about the next one, so the only thing that can be predicted is its average rate. The model has this rate. The slowest timescale spans the whole training period, so its decayed count is essentially the number of events the node has had, which is proportional to the average rate.
Opening
Thank you very much for the careful reading and the kind, constructive questions!
Before the answers below, please read our two overall responses first, "Clarifying a Likely Misreading of Our Contribution" and "What Changed in the Revised Paper". They are important. They say what the paper claims and how the revised version is organized, and they may already answer many of the questions raised in the reviews. Our answers to your individual questions build on them.