8.2.1 Kernel Regression

Kernel methods constitute the “workhorse” of machine learning for nonlinear function estimation [18]. Their popularity can be attributed to their simplicity, flexibility and good performance. Here, we present kernel regression as a unifying framework for graph signal reconstruction along with the so-called representer theorem.

Kernel regression seeks an estimate of f in a reproducing kernel Hilbert space (RKHS) $\mathcal{H}$, which is the space of functions $f:\mathcal{V}\to \mathbb{R}$ defined as

$\mathcal{H}:=\{f:f(v)=\sum _{n=1}^N{\alpha }_n\kappa (v,v_n),{\alpha }_n\in \mathbb{R}\},$

where the kernel map $\kappa :\mathcal{V}\times \mathcal{V}\to \mathbb{R}$ is any function defining a symmetric and positive semidefinite $N\times N$ matrix with entries ${[\mathbf{K}]}_{n,n^{\prime }}:=\kappa (v_n,v_{n^{\prime }})$ [19]. Intuitively, $\kappa (v,v^{\prime })$ is a basis function in (8.2) measuring similarity between the values of f at v and $v^{\prime }$. (For a more detailed treatment of RKHS, see, e.g., [3].)

Note that, for signals over graphs, the expansion in (8.2) is finite since $\mathcal{V}$ is finite-dimensional. Thus, any $f\in \mathcal{H}$ can be expressed in compact form

$\mathbf{f}=\mathbf{K}\mathbf{\alpha }$

for some $N\times 1$ vector $\mathbf{\alpha }:={[{\alpha }_1,\dots ,{\alpha }_N]}^T$.

Given two functions $f(v):={\sum }_{n=1}^N{\alpha }_n\kappa (v,v_n)$ and $f^{\prime }(v):={\sum }_{n=1}^N{\alpha }_n^{\prime }\kappa (v,v_n)$, their RKHS inner product is defined as¹

${\langle f,f^{\prime }\rangle }_{\mathcal{H}}:=\sum _{n=1}^N\sum _{n^{\prime }=1}^N{\alpha }_n{\alpha }_{n^{\prime }}^{\prime }\kappa (v_n,v_{n^{\prime }})={\mathbf{\alpha }}^T\mathbf{K}{\mathbf{\alpha }}^{\prime },$

where ${\mathbf{\alpha }}^{\prime }:={[{\alpha }_1^{\prime },\dots ,{\alpha }_N^{\prime }]}^T$ and the reproducing property has been employed that suggests ${\langle \kappa (\cdot ,v_{n_0}),\kappa (\cdot ,v_{n_0^{\prime }})\rangle }_{\mathcal{H}}={\mathbf{i}}_{n_0}^T\mathbf{K}{\mathbf{i}}_{n_0^{\prime }}=\kappa (v_{n_0},v_{n_0^{\prime }})$. The RKHS norm is defined by

${\Vert f\Vert }_{\mathcal{H}}^2:={\langle f,f\rangle }_{\mathcal{H}}={\mathbf{\alpha }}^T\mathbf{K}\mathbf{\alpha }$

and will be used as a regularizer to control overfitting and to cope with the under-determined reconstruction problem. As a special case, setting $\mathbf{K}={\mathbf{I}}_N$ recovers the standard inner product ${\langle f,f^{\prime }\rangle }_{\mathcal{H}}={\mathbf{f}}^T{\mathbf{f}}^{\prime }$ and the Euclidean norm ${\Vert f\Vert }_{\mathcal{H}}^2={\Vert \mathbf{f}\Vert }_2^2$. Note that when $\mathbf{K}\succ \mathbf{0}$, the set of functions of the form (8.3) coincides with ${\mathbb{R}}^N$.

Given ${\{y_s\}}_{s=1}^S$, RKHS-based function estimators are obtained by solving functional minimization problems formulated as (see also, e.g., [18–20])

$\hat{f}:=\underset{f\in \mathcal{H}}{\arg \min }\mathcal{L}(\mathbf{y},\overline{\mathbf{f}})+\mu \mathrm{\Omega }({\Vert f\Vert }_{\mathcal{H}}),$

where the loss $\mathcal{L}$ measures how the estimated function f at the observed vertices ${\{v_{n_s}\}}_{s=1}^S$, collected in $\overline{\mathbf{f}}:={[f(v_{n_1}),\dots ,f(v_{n_S})]}^T=\mathbf{S}\mathbf{f}$, deviates from the data y. The so-called square loss $\mathcal{L}(\mathbf{y},\overline{\mathbf{f}}):=(1/S){\sum }_{s=1}^S{[y_s-f(v_{n_s})]}^2$ constitutes a popular choice for $\mathcal{L}$. The increasing function Ω is used to promote smoothness with typical choices including $\mathrm{\Omega }(\zeta )=|\zeta |$ and $\mathrm{\Omega }(\zeta )={\zeta }^2$. The regularization parameter $\mu >0$ controls overfitting. Substituting (8.3) and (8.5) into (8.6) shows that $\hat{\mathbf{f}}$ can be found as

$\hat{\mathbf{\alpha }}:=\underset{\mathbf{\alpha }\in {\mathbb{R}}^N}{\arg \min }\mathcal{L}(\mathbf{y},\mathbf{S}\mathbf{K}\mathbf{\alpha })+\mu \mathrm{\Omega }({({\mathbf{\alpha }}^T\mathbf{K}\mathbf{\alpha })}^{1/2}),$

$\hat{\mathbf{f}}=\mathbf{K}\hat{\mathbf{\alpha }}.$

An alternative form of (8.5) that will be frequently used in the sequel results upon noting that

${\mathbf{\alpha }}^T\mathbf{K}\mathbf{\alpha }={\mathbf{\alpha }}^T\mathbf{K}{\mathbf{K}}^{\mathrm{†}}\mathbf{K}\mathbf{\alpha }={\mathbf{f}}^T{\mathbf{K}}^{\mathrm{†}}\mathbf{f}.$

Thus, one can rewrite (8.6) as

$\hat{\mathbf{f}}:=\underset{\mathbf{f}\in \mathcal{R}\{\mathbf{K}\}}{\arg \min }\mathcal{L}(\mathbf{y},\mathbf{S}\mathbf{f})+\mu \mathrm{\Omega }({({\mathbf{f}}^T{\mathbf{K}}^{\mathrm{†}}\mathbf{f})}^{1/2}).$

Although graph signals can be reconstructed from (8.7), such an approach involves optimizing over N variables. Thankfully, the solution can be obtained by solving an optimization problem in S variables (where typically $S\ll N$), by invoking the so-called representer theorem [19,21].

The representer theorem plays an instrumental role in the traditional infinite-dimensional setting where (8.6) cannot be solved directly; however, even when $\mathcal{H}$ comprises graph signals, it can still be beneficial to reduce the dimension of the optimization in (8.7). The theorem essentially asserts that the solution to the functional minimization in (8.6) can be expressed as

$\hat{f}(v)=\sum _{s=1}^S{\overline{\alpha }}_s\kappa (v,v_{n_s})$

for some ${\overline{\alpha }}_s\in \mathbb{R}$, $s=1,\dots ,S$.

The representer theorem shows the form of $\hat{f}$, but does not provide the optimal ${\{{\overline{\alpha }}_s\}}_{s=1}^S$, which are found after substituting (8.10) into (8.6) and solving the resulting optimization problem with respect to these coefficients. To this end, let $\overline{\mathbf{\alpha }}:={[{\overline{\alpha }}_1,\dots ,{\overline{\alpha }}_S]}^T$ and write $\mathbf{\alpha }={\mathbf{S}}^T\overline{\mathbf{\alpha }}$ to deduce that

$\hat{\mathbf{f}}=\mathbf{K}\mathbf{\alpha }=\mathbf{K}{\mathbf{S}}^T\overline{\mathbf{\alpha }}.$

With $\overline{\mathbf{K}}:=\mathbf{S}\mathbf{K}{\mathbf{S}}^T$ and using (8.7) and (8.11), the optimal $\overline{\mathbf{\alpha }}$ can be found as

$\widehat{\overline{\mathbf{\alpha }}}:=\underset{\overline{\mathbf{\alpha }}\in {\mathbb{R}}^S}{\arg \min }\mathcal{L}(\mathbf{y},\overline{\mathbf{K}}\overline{\mathbf{\alpha }})+\mu \mathrm{\Omega }({({\overline{\mathbf{\alpha }}}^T\overline{\mathbf{K}}\overline{\mathbf{\alpha }})}^{1/2}).$

Kernel ridge regression. For $\mathcal{L}$ chosen as the square loss and $\mathrm{\Omega }(\zeta )={\zeta }^2$, the $\hat{f}$ in (8.6) is referred to as the kernel ridge regression (RR) estimate [18]. If $\overline{\mathbf{K}}$ is full-rank, this estimate is given by ${\hat{\mathbf{f}}}_{\text{RR}}=\mathbf{K}{\mathbf{S}}^T\widehat{\overline{\mathbf{\alpha }}}$, where

$\widehat{\overline{\mathbf{\alpha }}}:=\underset{\overline{\mathbf{\alpha }}\in {\mathbb{R}}^S}{\arg \min }\frac{1}{S}{\Vert \mathbf{y}-\overline{\mathbf{K}}\overline{\mathbf{\alpha }}\Vert }^2+\mu {\overline{\mathbf{\alpha }}}^T\overline{\mathbf{K}}\overline{\mathbf{\alpha }}$

$={(\overline{\mathbf{K}}+\mu S{\mathbf{I}}_S)}^{-1}\mathbf{y}.$

Therefore, ${\hat{\mathbf{f}}}_{\text{RR}}$ can be expressed as

${\hat{\mathbf{f}}}_{\text{RR}}=\mathbf{K}{\mathbf{S}}^T{(\overline{\mathbf{K}}+\mu S{\mathbf{I}}_S)}^{-1}\mathbf{y}.$

Section 8.2.2 shows that (8.14) generalizes a number of existing signal reconstructors upon properly selecting K.

8.2.2 Kernels on Graphs

When estimating functions on graphs, conventional kernels such as the Gaussian kernel cannot be adopted because the underlying set where graph signals are defined is not a metric space. Indeed, no vertex addition $v_n+v_{n^{\prime }}$, scaling $\beta v_n$ or norm $\Vert v_n\Vert$ can be naturally defined on $\mathcal{V}$. An alternative is to embed $\mathcal{V}$ into Euclidean space via a feature map $\varphi :\mathcal{V}\to {\mathbb{R}}^D$ and invoke a conventional kernel afterwards. However, for a given graph it is generally unclear how to explicitly design ϕ or select D. This motivates the adoption of kernels on graphs [3].

A common approach to designing kernels on graphs is to apply a transformation function on the graph Laplacian [3]. The term Laplacian kernel comprises a wide family of kernels obtained by applying a certain function $r(\cdot )$ to the Laplacian matrix L. Laplacian kernels are well motivated since they constitute the graph counterpart of the so-called translation-invariant kernels in Euclidean spaces [3]. This section reviews Laplacian kernels, provides beneficial insights in terms of interpolating signals and highlights their versatility in capturing information about the graph Fourier transform of the estimated signal.

The reason why the graph Laplacian constitutes one of the prominent candidates for regularization on graphs becomes clear upon recognizing that

${\mathbf{f}}^T\mathbf{L}\mathbf{f}=\frac{1}{2}\sum _{(n,n^{\prime })\in \mathcal{E}}{A}_{n,n^{\prime }}{(f_n-f_{n^{\prime }})}^2,$

where $A_{n,n^{\prime }}$ denotes weight associated with edge $(n,n^{\prime })$. The quadratic form of (8.15) becomes larger when function values vary a lot among connected vertices and therefore quantifies the smoothness of f on $\mathcal{G}$.

Let $0={\lambda }_1⩽{\lambda }_2⩽\dots ⩽{\lambda }_N$ denote the eigenvalues of the graph Laplacian matrix L and consider the eigendecomposition $\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^T$, where $\mathbf{\Lambda }:=\mathrm{diag}\{{\lambda }_1,\dots ,{\lambda }_N\}$. A Laplacian kernel matrix is defined by

$\mathbf{K}:=r^{\mathrm{†}}(\mathbf{L}):=\mathbf{U}{r}^{\mathrm{†}}(\mathbf{\Lambda }){\mathbf{U}}^T,$

where $r(\mathbf{\Lambda })$ is the result of applying a user-selected, scalar, nonnegative map $r:\mathbb{R}\to {\mathbb{R}}_{+}$ to the diagonal entries of Λ. The selection of map r generally depends on desirable properties that the target function is expected to have. Table 8.1 summarizes some well-known examples arising for specific choices of r.

Table 8.1

Common spectral weight functions

Kernel name	Function	Parameters
Diffusion [2]	$r(\lambda )=\exp \{{\sigma }^2\lambda /2\}$	σ 2
p-step random walk [3]	r(λ)=(a−λ)−p	a ⩾ 2, p ≥ 0
Regularized Laplacian [3,22]	r(λ)=1 + σ2λ	σ 2
Bandlimited [23]	$\begin{array}{c}\hfill r(\lambda )=\{\begin{array}{cc}1/\beta ,\hfill & \lambda ⩽{\lambda }_{\text{max}},\hfill \\ \beta ,\hfill & \text{otherwise}\hfill \end{array}\end{array}$	β > 0, λmax

At this point, it is prudent to offer interpretations and insights on the operation of Laplacian kernels. Towards this objective, note first that the regularizer from (8.9) is an increasing function of

${\mathbf{\alpha }}^T\mathbf{K}\mathbf{\alpha }={\mathbf{\alpha }}^T\mathbf{K}{\mathbf{K}}^{\mathrm{†}}\mathbf{K}\mathbf{\alpha }={\mathbf{f}}^T{\mathbf{K}}^{\mathrm{†}}\mathbf{f}={\mathbf{f}}^T\mathbf{U}r(\mathbf{\Lambda }){\mathbf{U}}^T\mathbf{f}={\check{\mathbf{f}}}^{T}r(\mathbf{\Lambda })\check{\mathbf{f}}=\sum _{n=1}^{N}r({\lambda }_n)|{\check{f}}_n{|}^2,$

where $\check{\mathbf{f}}:={\mathbf{U}}^T\mathbf{f}:={[{\check{f}}_1,\dots ,{\check{f}}_N]}^T$ comprises the projections of f onto the eigenspace of L and is referred to as the graph Fourier transform of f in the SPoG parlance [4]. Consequently, ${\{{\check{f}}_n\}}_{n=1}^N$ are called frequency components. The so-called bandlimited (BL) functions in SPoG refer to those whose frequency components only exist inside some band B, that is, ${\check{f}}_n=0,\forall n>B$.

By adopting the aforementioned SPoG notions, one can intuitively interpret the role of BL kernels. Indeed, it follows from (8.17) that the regularizer strongly penalizes those ${\check{f}}_n$ for which the corresponding $r({\lambda }_n)$ is large, thus promoting a specific structure in this “frequency” domain. Specifically, one prefers $r({\lambda }_n)$ to be large whenever $|{\check{f}}_n{|}^2$ is small and vice versa. The fact that $|{\check{f}}_n{|}^2$ is expected to decrease with n for smooth f motivates the adoption of an increasing function r [3]. From (8.17) it is clear that $r({\lambda }_n)$ determines how heavily ${\check{f}}_n$ is penalized. Therefore, by setting $r({\lambda }_n)$ to be small when $n⩽B$ and extremely large when $n>B$, one can expect the result to be a BL signal.

Observe that Laplacian kernels can capture forms of prior information richer than bandlimitedness [11,13,16,17] by selecting function r accordingly. For instance, using $r(\lambda )=\exp \{{\sigma }^2\lambda /2\}$ (diffusion kernel) accounts not only for smoothness of f as in (8.15), but also for the prior knowledge that f is generated by a process diffusing over the graph. Similarly, the use of $r(\lambda )={(\alpha -\lambda )}^{-1}$ (1-step random walk) can accommodate cases where the signal captures a notion of network centrality.²

So far, f has been assumed deterministic, which precludes accommodating certain forms of prior information that probabilistic models can capture, such as domain knowledge and historical data. Suppose without loss of generality that ${\{f(v_n)\}}_{n=1}^N$ are zero mean random variables. The LMMSE estimator of f given y in (8.1) is the linear estimator ${\hat{\mathbf{f}}}_{\text{LMMSE}}$ minimizing $\mathbb{E}{\Vert \mathbf{f}-{\hat{\mathbf{f}}}_{\text{LMMSE}}\Vert }_2^2$, where the expectation is over all f and noise realizations. With $\mathbf{C}:=\mathbb{E}\left[\mathbf{f}{\mathbf{f}}^T\right]$, the LMMSE estimate is

${\hat{\mathbf{f}}}_{\text{LMMSE}}=\mathbf{C}{\mathbf{S}}^T{[\mathbf{S}\mathbf{C}{\mathbf{S}}^T+{\sigma }_e^2{\mathbf{I}}_S]}^{-1}\mathbf{y},$

where ${\sigma }_e^2:=(1/S)\mathbb{E}\left[{\Vert \mathbf{e}\Vert }_2^2\right]$ denotes the noise variance. Comparing (8.18) with (8.14) and recalling that $\overline{\mathbf{K}}:=\mathbf{S}\mathbf{K}{\mathbf{S}}^T$, it follows that ${\hat{\mathbf{f}}}_{\text{LMMSE}}={\hat{\mathbf{f}}}_{\text{RR}}$ if $\mu S={\sigma }_e^2$ and $\mathbf{K}=\mathbf{C}$. In other words, the similarity measure $\kappa (v_n,v_{n^{\prime }})$ embodied in such a kernel map is just the covariance $\mathrm{cov}[f(v_n),f(v_{n^{\prime }})]$. A related observation was pointed out in [27] for general kernel methods.

In short, one can interpret kernel ridge regression as the LMMSE estimator of a signal f with covariance matrix equal to K; see also [28]. The LMMSE interpretation also suggests the usage of C as a kernel matrix, which enables signal reconstruction even when the graph topology is unknown. Although this discussion hinges on kernel ridge regression after setting $\mathbf{K}=\mathbf{C}$, any other kernel estimator of the form (8.7) can benefit from vertex covariance kernels too.

8.2.3 Selecting Kernels From a Dictionary

The selection of the pertinent kernel matrix is of paramount importance to the performance of kernel-based methods [23,29]. This section presents an MKL approach that effects kernel selection in graph signal reconstruction. Two algorithms with complementary strengths will be presented. Both rely on a user-specified kernel dictionary, and the best kernel is built from the dictionary in a data-driven way.

The first algorithm, which we call RKHS superposition, is motivated by the fact that one specific $\mathcal{H}$ in (8.6) is determined by some κ; therefore, kernel selection is tantamount to RKHS selection. Consequently, a kernel dictionary ${\{{\kappa }_m\}}_{m=1}^M$ gives rise to an RKHS dictionary ${\{{\mathcal{H}}_m\}}_{m=1}^M$, which motivates estimates of the form³

$\hat{f}=\sum _{m=1}^M{\hat{f}}_m,{\hat{f}}_m\in {\mathcal{H}}_m.$

Upon adopting a criterion that controls sparsity in this expansion, the “best” RKHSs will be selected. A reasonable approach is therefore to generalize (8.6) to accommodate multiple RKHSs. With $\mathcal{L}$ selected to be the square loss and $\mathrm{\Omega }(\zeta )=|\zeta |$, one can pursue an estimate $\hat{f}$ by solving

$\underset{{\{f_m\in {\mathcal{H}}_m\}}_{m=1}^M}{\min }\frac{1}{S}\sum _{s=1}^S{[y_s-\sum _{m=1}^M{f}_m(v_{n_s})]}^2+\mu \sum _{m=1}^M{\Vert f_m\Vert }_{{\mathcal{H}}_m}.$

Invoking the representer theorem per $f_m$ establishes that the minimizers of (8.20) can be written as

${\hat{f}}_m(v)=\sum _{s=1}^S{\overline{\alpha }}_s^m{\kappa }_m(v,v_{n_s}),m=1,\dots ,M$

for some coefficients ${\overline{\alpha }}_s^m$. Substituting (8.21) into (8.20) suggests obtaining these coefficients as

$\underset{{\{{\overline{\mathbf{\alpha }}}_m\}}_{m=1}^M}{\arg \min }\frac{1}{S}{\Vert \mathbf{y}-\sum _{m=1}^M{\overline{\mathbf{K}}}_m{\overline{\mathbf{\alpha }}}_m\Vert }^2+\mu \sum _{m=1}^M{\left({\overline{\mathbf{\alpha }}}_m^T{\overline{\mathbf{K}}}_m{\overline{\mathbf{\alpha }}}_m\right)}^{1/2},$

where ${\overline{\mathbf{\alpha }}}_m:={[{\overline{\alpha }}_1^m,\dots ,{\overline{\alpha }}_S^m]}^T$ and ${\overline{\mathbf{K}}}_m:=\mathbf{S}{\mathbf{K}}_m{\mathbf{S}}^T$ with ${({\mathbf{K}}_m)}_{n,n^{\prime }}:={\kappa }_m(v_n,v_{n^{\prime }})$. Letting ${\check{\overline{\mathbf{\alpha }}}}_m:={\overline{\mathbf{K}}}_m^{1/2}{\overline{\mathbf{\alpha }}}_m$, Eq. (8.22) becomes

$\underset{{\{{\check{\overline{\mathbf{\alpha }}}}_m\}}_{m=1}^M}{\arg \min }\frac{1}{S}{\Vert \mathbf{y}-\sum _{m=1}^M{\overline{\mathbf{K}}}_m^{1/2}{\check{\overline{\mathbf{\alpha }}}}_m\Vert }^2+\mu \sum _{m=1}^M{\Vert {\check{\overline{\mathbf{\alpha }}}}_m\Vert }_2.$

Interestingly, (8.23) can be efficiently solved using the alternating-direction method of multipliers (ADMM) [30,31] after some necessary reformulation [23].

After obtaining ${\{{\check{\overline{\mathbf{\alpha }}}}_m\}}_{m=1}^M$, the sought-after function estimate can be recovered as

$\hat{\mathbf{f}}=\sum _{m=1}^M{\mathbf{K}}_m{\mathbf{S}}^T{\overline{\mathbf{\alpha }}}_m=\sum _{m=1}^M{\mathbf{K}}_m{\mathbf{S}}^T{\overline{\mathbf{K}}}_m^{-1/2}{\check{\overline{\mathbf{\alpha }}}}_m.$

This MKL algorithm can identify the best subset of RKHSs—and therefore kernels—but entails MS unknowns (cf. (8.22)). Next, an alternative approach is discussed which can reduce the number of variables to $M+S$ at the price of not being able to assure a sparse kernel expansion.

The alternative approach is to postulate a kernel of the form $\mathbf{K}(\mathbf{\theta })={\sum }_{m=1}^M{\theta }_m{\mathbf{K}}_m$, where ${\{{\mathbf{K}}_m\}}_{m=1}^M$ is given and ${\theta }_m⩾0\forall m$. The coefficients $\mathbf{\theta }:={[{\theta }_1,\dots ,{\theta }_M]}^T$ can be found by jointly minimizing (8.12) with respect to θ and $\overline{\mathbf{\alpha }}$ [32]. We have

$(\mathbf{\theta },\widehat{\overline{\mathbf{\alpha }}}):=\underset{\mathbf{\theta },\overline{\mathbf{\alpha }}}{\arg \min }\frac{1}{S}\mathcal{L}(\mathbf{v},\mathbf{y},\overline{\mathbf{K}}(\mathbf{\theta })\overline{\mathbf{\alpha }})+\mu \mathrm{\Omega }({({\overline{\mathbf{\alpha }}}^T\overline{\mathbf{K}}(\mathbf{\theta })\overline{\mathbf{\alpha }})}^{1/2}),$

where $\overline{\mathbf{K}}(\mathbf{\theta }):=\mathbf{S}\mathbf{K}(\mathbf{\theta }){\mathbf{S}}^T$. Except for degenerate cases, problem (8.25) is not jointly convex in θ and $\widehat{\overline{\mathbf{\alpha }}}$, but it is separately convex in each vector for a convex $\mathcal{L}$ [32]. Iterative algorithms for solving (8.23) and (8.25) are available in [23].

8.2.4 Semiparametric Reconstruction

The approaches discussed so far are applicable to various problems but they are certainly limited by the modeling assumptions they make. In particular, the performance of algorithms belonging to the parametric family [11,15,33] is restricted by how well the signals actually adhere to the selected model. Nonparametric models, on the other hand [2,3,6,34], offer flexibility and robustness but they cannot readily incorporate information available a priori.

In practice however, it is not uncommon that neither of these approaches alone suffices for reliable inference. Consider, for instance, an employment-oriented social network such as LinkedIn, and suppose the goal is to estimate the salaries of all users given information about the salaries of a few. Clearly, besides network connections, exploiting available information regarding the users' education level and work experience could benefit the reconstruction task. The same is true in problems arising in link analysis, where the exploitation of hierarchical web structure can aid the task of estimating the importance of web pages [35]. In recommender systems, inferring preference scores for every item, given the users' feedback about particular items, could be cast as a signal reconstruction problem over the item correlation graph. Data sparsity imposes severe limitations on the quality of pure collaborative filtering methods [64]. Exploiting side information about the items is known to alleviate such limitations [36], leading to considerably improved recommendation performance [37,38].

A promising direction to endow nonparametric methods with prior information relies on a semiparametric approach whereby the signal of interest is modeled as the superposition of a parametric and a nonparametric component [39]. While the former leverages side information, the latter accounts for deviations from the parametric part and can also promote smoothness using kernels on graphs. In this section we outline two simple and reliable semiparametric estimators with complementary strengths, as detailed in [39].

8.2.5 Numerical Tests

This section reports on the signal reconstruction performance of different methods using real as well as synthetic data. The performance of the estimators is assessed via Monte Carlo simulation by comparing the normalized mean square error (NMSE)

$\text{NMSE}=\mathbb{E}\left[\frac{{\Vert \hat{\mathbf{f}}-\mathbf{f}\Vert }^2}{{\Vert \mathbf{f}\Vert }^2}\right].$

Multikernel reconstruction. The first data set contains departure and arrival information for flights among U.S. airports [41], from which $3\times {10}^6$ flights in the months of July, August and September of 2014 and 2015 were selected. We construct a graph with $N=50$ vertices corresponding to the airports with highest traffic, and whenever the number of flights between the two airports exceeds 100 within the observation window, we connect the corresponding nodes with an edge.

A signal was constructed per day averaging the arrival delay of all inbound flights per selected airport. A total of 184 signals were considered, of which the first 154 were used for training (July, August, September 2014 and July, August 2015), and the remaining 30 for testing (September 2015). The weights of the edges between airports were learned using the training data based on the technique described in [23].

Table 8.2 lists the NMSE and the RMSE in minutes for the task of predicting the arrival delay at 40 airports when the delay at a randomly selected collection of 10 airports is observed. The second row corresponds to the ridge regression estimator that uses the nearly optimal estimated covariance kernel. The next two rows correspond to the multikernel approaches in §8.2.3 with a dictionary of 30 diffusion kernels with values of ${\sigma }^2$ uniformly spaced between 0.1 and 7. The rest of the rows pertain to graph BL estimators. Table 8.2 demonstrates the reliable performance of covariance kernels as well as the herein discussed multikernel approaches relative to competing alternatives.

Semiparametric reconstruction. An Erdős–Rényi graph with probability of edge presence 0.6 and $N=200$ nodes was generated, and f was formed by superimposing a BL signal [13,15] plus a piece-wise constant signal [42]; that is,

$\mathbf{f}=\sum _{i=1}^{10}{\gamma }_i{\mathbf{u}}_i+\sum _{i=1}^6{\delta }_i{\mathbf{1}}_{{\mathcal{V}}_c},$

where ${\{{\gamma }_i\}}_{i=1}^{10}$ and ${\{{\delta }_i\}}_{i=1}^6$ are standardized Gaussian distributed, ${\{{\mathbf{u}}_i\}}_{i=1}^{10}$ are the eigenvectors associated with the 10 smallest eigenvalues of the Laplacian matrix, ${\{{\mathcal{V}}_i\}}_{i=1}^6$ are the vertex sets of six clusters obtained via spectral clustering [43] and ${\mathbf{1}}_{{\mathcal{V}}_i}$ is the indicator vector with entries ${({\mathbf{1}}_{{\mathcal{V}}_i})}_n:=1$, if $v_n\in {\mathcal{V}}_i$, and 0 otherwise. The parametric basis $\mathcal{B}={\{{\mathbf{1}}_{{\mathcal{V}}_i}\}}_{i=1}^6$ was used by the estimators capturing the prior knowledge, and S vertices were sampled uniformly at random. The subsequent experiments evaluate the performance of the semiparametric graph kernel estimators, SP-GK and SP-GK(ϵ), resulting from using (8.30) and (8.32) in (8.29), respectively; the parametric (P) that considers only the parametric term in (8.26), the nonparametric (NP) [2,3] that considers only the nonparametric term in (8.26) and the graph BL estimators from [13,15], which assume a BL model with bandwidth B. For all the experiments, the diffusion kernel (cf. Table 8.1) with parameter σ is employed. First, white Gaussian noise $e_s$ of variance ${\sigma }_e^2$ is added to each sample $f_s$ to yield the signal-to-noise ratio ${\text{SNR}}_e:={\Vert \mathbf{f}\Vert }_2^2/(N{\sigma }_e^2)$. Fig. 8.1B presents the NMSE of different methods. As expected, the limited flexibility of the parametric approaches, BL and P, affects their ability to capture the true signal structure. The NP estimator achieves smaller NMSE, but only when the amount of available samples is adequate. Both semiparametric estimators were found to outperform other approaches, exhibiting reliable reconstruction even with few samples.

To illustrate the benefits of employing different loss functions (8.30) and (8.32), we compare the performance of SP-GK and SP-GK(ϵ) in the presence of outlying noise. Each sample $f_s$ is contaminated with Gaussian noise $o_s$ of large variance ${\sigma }_o^2$ with probability $p=0.1$. Fig. 8.1A demonstrates the robustness of SP-GK(ϵ) which is attributed to the ϵ-insensitive loss function (8.32). Further experiments using real signals can be found in [39].

8.3.1 Kernels on Extended Graphs

This section extends the kernel-based learning framework of §8.2 to subsume time evolving functions over possibly dynamic graphs through the notion of graph extension, by which the time dimension receives the same treatment as the spatial dimension. The versatility of kernel-based methods to leverage spatial information [23] is thereby inherited and broadened to account for temporal dynamics as well. This vantage point also accommodates time varying sampling sets and topologies.