One cool way to construct a new kernel from an existing set of $($base$)$ kernels is through graphs. Let G $=($V$,$ E$)$

be a directed acyclic graph $($DAG$),$ where V denotes the nodes and E denotes the arcs $($directed edges$).$ For

convenience let us assume there is a source node s that has no incoming arc and there is a sink node t that has no

outgoing arc. We put a base kernel $\backslash$kappa e $($that is$,$ a function $\backslash$kappa e : X $\backslash$times X $->$ R$)$ on each arc e $=($u $->$ v$)$ in E$.$ For

each path P $=($u$0->$ u$1->->$ ud$)$ with ui$1->$ ui being an arc in E$,$ we can define the kernel for the path P

as the product of kernels along the path:

$$x$,$ z in X $,\backslash$kappa P $($x$,$ z$)=$ Y

d

i$=1$

$\backslash$kappa ui$1->$ui

$($x$,$ z$).(1)$

Then, we define the kernel for the graph G as the sum of all possible s $->$ t path kernels:

$$x$,$ z in X $,\backslash$kappa G$($x$,$ z$)=$ X

P in path$($s$->$t$)$

$\backslash$kappa P $($x$,$ z$).(2)$

$1.(1$ pt$)$ Prove that $\backslash$kappa G is indeed a kernel. $[$You may use any property that we learned in class about kernels.$]$

Ans:

$2.(2$ pts$)$ Let $\backslash$kappa i

$,$ i $=1,...,$ n be a set of given kernels. Construct a graph G $($with appropriate base kernels$)$ so

that the graph kernel $\backslash$kappa G $=$

Pn

i$=1\backslash$kappa i

$.$ Similarly, construct a graph G $($with appropriate base kernels$)$ so that

the graph kernel $\backslash$kappa G $=$

Qn

i$=1\backslash$kappa i

$.$

Ans:

Yao$-$Liang Yu $($yaoliang$.$yu@uwaterloo.ca$)20241/6$

University of Waterloo CS$480/6802024$ Spring

$3.(1$ pt$)$ Consider the subgragh of the figure below that includes nodes s$,$ a$,$ b$,$ c $($and arcs connecting them$).$

Compute the graph kernel where s and c play the role of source and sink, respectively. Repeat the computation

with the subgraph that includes s$,$ a$,$ b$,$ c$,$ d $($and arcs connecting them$),$ where d is the sink now.

s a b c d t

xz

e

$($x$$z$)$

$2$

$($xz $1)2$

tanh$($xz $+1)$

e

$|$x$$z$|/2$

$1$

Ans:

$4.(2$ pts$)$ Find an efficient algorithm to compute the graph kernel $\backslash$kappa G$($x$,$ z$)($for two fixed inputs x and z$)$ in

time O$(|$V $|+|$E$|),$ assuming each base kernel $\backslash$kappa e costs O$(1)$ to evaluate. You may assume there is always at

least one s $$ t path. State and justify your algorithm is enough; no need $($although you are encouraged$)$ to

give a full pseudocode.

$[$Note that the total number of paths in a DAG can be exponential in terms of the number of nodes $|$V $|,$ so

naive enumeration would not work. For example, replicating the intermediate nodes in the above figure n

times creates $2$n paths from s to t$.]$

$[$Hint: Recall that we can use topological sorting to rearrange the nodes in a DAG such that all arcs go from

a $$smaller$$ node to a $$bigger$$ one.$]$