Kernel-based Reconstruction of Space-time Functions on Dynamic Graphs

Abstract--Graph-based methods pervade the inference toolk-its of numerous disciplines including sociology, biology, neuroscience, physics, chemistry, and engineering. A challenging problem encountered in this context pertains to determining the attributes of a set of vertices given those of another subset at possibly different time instants. Leveraging spatiotemporal dynamics can drastically reduce the number of observed vertices, and hence the cost of sampling. Alleviating the limited flexibility of existing approaches, the present paper broadens the existing kernel-based graph function reconstruction framework to accommodate time-evolving functions over possibly time-evolving topologies. This approach inherits the versatility and generality of kernel-based methods, for which no knowledge on distributions or second-order statistics is required. Systematic guidelines are provided to construct two families of space-time kernels with complementary strengths. The first facilitates judicious control of regularization on a space-time frequency plane, whereas the second can afford time-varying topologies. Batch and online estimators are also put forth, and a novel kernel Kalman filter is developed to obtain these estimates at affordable computational cost. Numerical tests with real data sets corroborate the merits of the proposed methods relative to competing alternatives. A number of applications involving social, biological, brain, sensor, transportation, or communication networks call for efficient methods to infer the attributes of some vertices given the attributes of other vertices [1]. For example, in a social network with vertices and edges respectively representing persons and friendships, one may be interested in determining an individual's consumption trends based on those of their friends. This task emerges when sampling cost constraints, such as the impossibility to poll one country's entire population about political orientation, limit the number of vertices with known attributes. Existing approaches typically formulate this problem as the reconstruction of a function or signal on a graph [1]-[6], and rely on its smoothness with respect to the graph, in the sense that neighboring vertices have similar function values. This principle suggests, for instance, estimating one person's age by looking at their friends' age.