Kernels for Graph Data

You can refer to our demo for semi-supervised learning for a simple usage of kernels for graph data.

And there is also a demo for graph kernel using an example of propagation kernel.

Kernels on Graph

pyGPs.GraphExtensions.nodeKernels.VNDKernel(A, alpha=0.5)[source]

Von Neumann Diffusion Kernel on graph (Zhou et al., 2004) (also label spreading kernel)

K = (I - alpha*S)^-1, where S = D^-1/2*A*D^-1/2

Parameters:
  • A – adjacency matrix
  • alpha – hyperparameter alpha
Returns:

kernel matrix

pyGPs.GraphExtensions.nodeKernels.cosKernel(A)[source]

Cosine Kernel (also Inverse Cosine Kernel)

K = cos (L*pi/4), where L is the normalized Laplacian

Parameters:A – adjacency matrix
Returns:kernel matrix
pyGPs.GraphExtensions.nodeKernels.diffKernel(A, beta=0.5)[source]

Diffusion Process Kernel

K = exp(beta * H), where H = -L = A-D

K = Q exp(beta * Lambda) Q.T

Parameters:
  • A – adjacency matrix
  • beta – hyperparameter beta
Returns:

kernel matrix

pyGPs.GraphExtensions.nodeKernels.normLap(A)[source]

Normalized Laplacian

Parameters:A – adjacency matrix
Returns:kernel matrix
pyGPs.GraphExtensions.nodeKernels.psInvLapKernel(A)[source]

Pseudo inverse of the normalized Laplacian.

Parameters:A – adjacency matrix
Returns:kernel matrix
pyGPs.GraphExtensions.nodeKernels.regLapKernel(A, sigma=1)[source]

Regularized Laplacian Kernel

Parameters:
  • A – adjacency matrix
  • sigma – hyperparameter sigma
Returns:

kernel matrix

pyGPs.GraphExtensions.nodeKernels.rwKernel(A, p=1, a=2)[source]

p-step Random Walk Kernel with a>1

K = (aI-L)^p, p>1 and L is the normalized Laplacian

Parameters:
  • A – adjacency matrix
  • p – step parameter
  • a – hyperparameter a
Returns:

kernel matrix

Graph Kernels

pyGPs.GraphExtensions.graphKernels.propagationKernel(A, l, gr_id, h_max, w, p, ktype=None, SUM=True, VIS=False, showEachStep=False)[source]

Propagation kernel for graphs as described in: Neumann, M., Patricia, N., Garnett, R., Kersting, K.: Efficient Graph Kernels by Randomization. In: P.A. Flach, T.D. Bie, N. Cristianini (eds.) ECML/PKDD, Notes in Computer Science, vol. 7523, pp. 378-393. Springer (2012).

Parameters:
  • A – adjacency matrix (num_nodes x num_nodes)
  • l – label array (num_nodes x 1); values [1,...,k] or -1 for unlabeled nodes OR label array (num_nodes x num_labels); values [0,1], unlabeled nodes have only 0 entries
  • gr_id – graph indicator array (num_nodes x 1); values [0,..,n]
  • h_max – number of iterations
  • w – bin widths parameter
  • p – distance (‘tv’, ‘hellinger’, ‘L1’, ‘L2’)
  • ktype – type of propagation kernel [‘diffusion’, ‘label_propagation’, ‘label_spreading’, ‘belief_propagation’]
Returns:

kernel matrix