- no title specified

EMBL Centre for Network Analysis workshop 9-11 December 2015

Data integration and mining with graphs:

Kernels on graph nodes

Jean-Karim Hériché

Ellenberg lab

Cell Biology and Biophysics unit

Summary

Biological data sets can be represented as graphs for the purpose of data integration and mining. We will introduce kernels on graph nodes as measures of similarity between genes, show how to compute some kernels for various biological data sources and how they can be used for data integration. We will apply the kernels to the task of candidate genes selection.

Motivation

While large, nearly genome-wide studies are now possible, they remain beyond the reach of most laboratories as they require a large investment in reagents, equipments and data management. In most cases, locally available resources only allow a few dozen to a few hundred genes to be studied, with candidate genes usually selected either from a gene family (e.g. kinases) or after extensive literature and database searches. In the latter case, candidate genes are identified by association to genes already known to be implicated in the process under consideration. Given that links between genes can be indirect and that there are multiple sources of data, this selection process has become a difficult task. In this context, efficient automatic candidate gene selection has the potential to maximize returns on investment in experiments.

Selecting good candidate genes means finding genes that have a high probability of being part of or related to the process one wants to study. If this process is defined in terms of a few genes known to participate in that process, then good candidate genes would be those that are functionally linked to these known genes. Compared to large scale, systematic experiments, finding new candidates based on network context analysis has the added advantage to provide hypothesis about likely underlying molecular interaction mechanisms involving the predicted targets.

Many methods using the "guilt by association" principle have been developed for predicting gene function and applied to model organisms (for review see [1]). Among these, kernel-based methods have gained in popularity [2,3]. In this context, despite representing a natural measure of similarity between genes, kernels on graph nodes have received little attention.

Kernels

Kernels and kernel methods are well described and explained in [4] which is suggested reading for anyone interested in the kernel framework.

- What is a kernel ?

A kernel is a function that maps data points (e.g. genes) into some high dimensional space (called feature space) and computes the dot product of the corresponding vectors in that space. That is, for a mapping function Φ and 2 genes x and y, the kernel function K computes K(x,y) = ⟨Φ(x),Φ(y)⟩. A kernel matrix contains the evaluation of a kernel function for all pairs of data points under consideration. Note that we often use the term kernel to refer to the kernel matrix instead of the function.

- Useful properties of kernels:

•Because it corresponds to a dot product, a kernel can be viewed as a similarity measure. After normalization, kernels can be viewed as giving the probability of items being in the same class minus the probability that they are in different classes.
•Different kernels corresponds to mappings to different feature spaces so capture different notions of similarity.
•Any symmetric, positive semi-definite matrix (i.e. whose eigenvalues are ≥ 0) corresponds to pairwise dot products in some feature space and therefore represents a valid kernel. This means we can use any similarity matrix that is symmetric, positive semi-definite as a kernel and that we can apply kernel methods to any type of data as long as we can define some similarity measure between the data points.
•Kernels can be transformed or combined using various operations (e.g. linear combination) to produce other kernels.

Proof for these properties can be found in chapter 2 and 3 of [4].

- Why use kernels ?

Many algorithms work using only the dot products between input vectors e.g. PCA, LDA, k-means and other clustering algorithms, support vector machine... The kernel trick often mentioned in the literature refers to using kernel matrices to provide these dot products. This provides modularity as any kernel can work with any dot product-based algorithm. Kernels can be used to map complex patterns into a feature space where they appear linear allowing them to be efficiently identified using common algorithms. The last property listed above means that a combination of similarity matrices can still be interpreted as a matrix of similarities if the combined matrices are valid kernels. This property makes kernels particularly attractive for data integration because it provides a principled way of combining information from different sources into one similarity matrix.

Measures of graph nodes similarity

A good measure of similarity between nodes of a graph should satisfy the guilt-by-association intuition that two nodes are more similar to each other when they are connected to similar nodes. Our intuition also tells us that nodes are more similar when there are more connections between them and the paths connecting them are shorter. Therefore, to measure similarity between nodes, we want to take into account how they are connected. Some simple measures would involve counting the number of hops or summing the weights of the hops between two nodes but it's easy to find examples where these measures don't capture meaningful similarity.

•Random walks on a graph:

One way to analyse connectivity in a graph is to select a starting node then move to a random neighbour of this node then move to a random neighbour of that node and so on for an infinite number of steps. The sequence of randomly visited nodes in this process is called a random walk on the graph and can be viewed as a Markov chain. A short simulation can show that a random walk hits closer, more connected nodes more often than more distant, less connected ones or, seen another way, it takes less time to reach a node from closer, more connected nodes than from more distant, less connected nodes.

•Similarity measures from random walks

The expected time (= number of steps) it takes in a random walk to reach a node starting from a different node is called hitting time. Clearly, although the hitting time is a distance (similar nodes have a small hitting time and dissimilar nodes have a large hitting time), it captures the notion of similarity we outlined above. However, it is not symmetric as H(i,j) is generally not equal to H(j,i) but it can be used to derive the commute time between i and j which measures how long it takes to go from i to j and back to i: CT(i,j) = H(i,j)+H(j,i) = CT(j,i) and does capture the same notion of similarity. Other similarity measures can be derived from the random walk. One is called random forest (RF) because it arises from the enumeration of the spanning rooted forests in the graph and measures the relative "forest-accessibility" between nodes [5]) and RF(i,j) corresponds to the probability of reaching node j in a random number of steps starting from node i [6]. Finally, if instead of jumping from node to node we have the random walk move in a continuous fashion along the edges, we simulate a diffusion process. Measuring similarity in a diffusion process involves enumerating all paths between two nodes while penalizing the longer paths [4].

Computing kernels on graph nodes

Each data set is viewed as the adjacency matrix A of a weighted undirected graph and a value Aij of 0 indicates no edge between i and j. In the following, D denotes the diagonal degree matrix, I the identity matrix, L the graph Laplacian (L= D-A). We will compute the following kernels:

- kernelized adjacency matrix:

Our data sources already represent a measure of similarity between genes. To ensure that the matrix is positive semi-definite and therefore a valid kernel, we can shift its eigenvalues. This is accomplished by adding a sufficiently large constant to the diagonal of each matrix. Here we use the absolute value of the smallest eigenvalue.

KA = A+λI with λ= absolute value of smallest eigenvalue of A

- Commute time kernel:

The commute time between two nodes can be computed using L+, the pseudo-inverse of the Laplacian [7]. However, the commute time itself is a distance measure but it can be shown that L+ is the covariance matrix associated with the nodes in a feature space where the nodes are separated by their commute time [7]. Therefore (also because L is symmetric, positive and semi-definite) L+ is symmetric, positive and semi-definite and a valid kernel. It is called the commute time kernel. It also has an interpretation in terms of electrical network as the commute time is equal to the effective resistance between two nodes [8]. Note that for very large graphs, the commute time distance becomes meaningless [9] but this can be dealt with.

KCT = L+ (pseudo-inverse of L)

- Random forest kernel:

This kernel arises from the enumeration of the spanning rooted forests in the graph and measures the relative "forest-accessibility" between nodes and has an interpretation in terms of probabilities of reaching a node in a random walk with random number of steps. Its derivation is explained in [5,6].

KRF = (I+L)-1

- von Neumann diffusion kernel:

This kernel enumerates all paths between 2 nodes while penalizing the longer paths [4]:

KVN= ΣkαkAk = (I-γA)-1

The penalizing factor is αk (k being the length of the path) and the kernel is defined for 0<γ<ρ−1 with ρ being the spectral radius of A. We will use 2 values of γ: γ = 0.99ρ−1 and γ = 0.0001ρ−1 which correspond respectively to high and low values of the admissible range for γ. Note that in a supervised setting with enough training data, one can learn a value for γ from the data.

- Degree-based similarity:

We also compute a similarity matrix based only on node degree as in [10]:

KDB= BBT where B=De and e is the all-one vector (eT=(1,1,...,1)).

KDB(i,j) is simply the product of the degree of node i by the degree of node j. Note that this is a valid kernel by construction.

- Normalization:

Genes with multiple functions or that are more studied tend to have more links to other genes. To compensate for this effect, each kernel is normalized to the range [-1,1] by diag(K)-1/2Kdiag(K)-1/2 (which corresponds to computing the cosine of the vectors in the feature space of the kernel). This also seems to alleviate the commute time issue with large graphs [9].

Other kernels and similarity measures can be found in [11].

Application to finding functionally-related genes

The approach we will follow is that of semi-supervised learning by label propagation. We assume that similar genes have similar function and we can propagate function from genes with known function to similar genes for which the function is unknown. The data processing pipeline is shown in Figure 1.

Figure 1: Semi-supervised learning by label propagation

Practical

For this session, we're going to work with the text mining data (TM) using R.

First we need to load the libraries we need:

## Load required packages

library(igraph) # to manipulate graphs

library(MASS) # for pseudoinverse function ginv()

library(rARPACK) # for eigs(), to compute limited number of eigenvalues

We're also going to put the data directory in a variable so that we don't need to type it in each time:

## Where the data is

dataDir <- "~/Documents/Bio-IT/courses/Data_integration_and_mining_with_graphs"

Now we read the TM data from the file. The file contains a tab-delimited list of gene pairs with their similarities.