Cheetah: Fast Graph Kernel Tracking on Dynamic Graphs


Version 1.0 is available at Github.


The package contains the following files:

  • as50days.mat: AS dataset

  • demo.m: a demo file showing how to do the graph kernel tracking

  • updateEigen.m: update low rank approximation of a matrix, see Algorithm 2 in the paper

  • myQR.m: partial QR decomposition

  • gen_nrowcol_perturb.m: generate perturbation matrix

  • origininal_kernel.m: the exact graph kernel computation:

\[ \begin{equation} \mathrm{Ker}(G_1, G_2) = (q_1'\otimes q_2’) (I - cA_1'\otimes A_2’)^{-1}(p_1 \otimes p_2) \end{equation} \]


Please refer to demo.m and comments in each file for the detailed information.


Liangyue Li, Hanghang Tong, Yanghua Xiao, Wei Fan. Cheetah: Fast Graph Kernel Tracking on Dynamic Graphs. SIAM International Conference on Data Mining (SDM), 2015. (Oral) [PDF][Slides]