Review of “Exploiting Time-varying Relationships in Statistical Relational Models”
This paper[1] introduces a novel way of addressing changes to the structure of links in a network with respect to time in statistical relational models.
As a first step, the authors create a weighted summary of the graph for each time interval. Empirically they show that the best weighting function to use to replace links is by exponential decay, which in turn, suggests that newer links are more relevant for statistical learning, and that relevance (again, for statistical learning) falls off quickly when regressing back through time. To arrive at these weights, a kernel function is used with a (theta) parameter. As an aside, one nice aspect of this approach is that, at some minimum threshold, the links can be discarding, saving space complexity, and possibly rendering this algorithm suitable in a streaming context.
As a second (and final) step, the authors then build a relational (naive Bayes) classifier that predicts a class label for the nodes in the graph based on the set of node attributes in conjunction with the (weighted) attributes of its neighbors in the summary graph.
For evaluation comparison, the authors use a static snapshot of the graph as it would appear at training time. This static snapshot consists of all links that had been encountered up to that point. For instance, if PersonA calls PersonB in year1, and PersonA calls PersonC in year2, the static graph would consist of three nodes (one for each Person), along with two edges of equal weight (PersonA–Calls–>PersonB and PersonA–Calls–>PersonC). Conversely, the summary graph would consist of all three nodes and both links, but the weight on the PersonA–Calls–>PersonB edge would be much lower than that of PersonA–Calls–>PersonC .
The paper discusses the results of their approach, which significantly outperforms a uniformly weighted static graph as measured by area under the ROC (by 10-20% on the datasets they looked at). While they do not explore other classifiers, their choice of naive Bayes (for its simplicity) successfully makes the argument that one can do very well using such simple algorithms.
[1] Sharan, U. and Neville, J. 2007. Exploiting time-varying relationships in statistical relational models. In Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis (San Jose, California, August 12 – 12, 2007). WebKDD/SNA-KDD ’07. ACM, New York, NY, 9-15.