Differentiable Graph Centrality

We view graph centrality algorithms as differentiable processes and explore the implications of this lens.First, we revisit PageRank, an ubiquitous graph centrality algorithm, and consider two questions: (a) Can we interpret its output ranking vector? (b) Can we use the algorithm for computing updated graphs approximating given centralities, i.e. after PageRank is run on them? The key idea to answering both these questions is to equip the algorithm (here PageRank) with the capability to be differentiated with respect to its input. Then the ranking interpretation question can be cast as the identification of directed edges and paths with increased influence on the individual output values (here the ranking vector entries). Similarly, the question of network design can be addressed by optimization procedures driven by algorithm derivatives with respect to the input graph elements (here the connection weights). We illustrate the idea by differentiating the PageRank algorithm as applied on a small graph, so that the arguments on the mechanics and effectiveness of our approach are straightforward to follow and confirm; experiments with a larger graph instance follow.We then turn our attention to assessing the dual role of vertices as sources and targets of directed edges. We propose source and target scores inspired by an extension to vector encodings of the scalar hub and authority scores introduced by another seminal graph centrality algorithm, HITS. We provide a way to quantify their relative contribution and thus rank them accordingly. This allows the identification of "dependencies" (sources) and "dependents" (targets) including the "root source" and "root target" nodes in the graph. The computational outputs are fully differentiable with respect to the edge weights assumed to model dependency strength. Differentiability adds novel capabilities: (a) we can detect which edges impact the most, either in the positive or negative sense, the "source" and "target" character of a selected node, thus adding to the interpretability of our results, and (b) the stability and cardinality of impacting edge sets can be assessed and controlled, respectively, by varying algorithmic parameters. We compute source and target scores for the nodes of a dependency graph and their derivatives with respect to its directed edge weights. The results reaffirm our intuition on the mechanics of specific directed edges as either strengthening or weakening the source and target role of graph vertices.