TALK    Label Propagation over Graphs

Date & Time:

Friday, March 8, 2013; 12:00 PM

Abstract:

Semi-structured data, particularly graphs, are now abundant in molecular biology. Typical examples are protein-protein interactions, gene regulatory networks, metabolic pathways, etc. To understand cellular mechanisms from this type of data, I've been working on semi-structured data, covering a wide variety of general topics in machine learning or data mining, such as link prediction, graph clustering, frequent subgraph mining, and label propagation over graphs and so on. In this talk I will focus on label propagation, in which nodes are partially labeled and the objective is to predict unknown labels using labels and links. I'll present two approaches under two different inputs in sequence: 1) only single graph and 2) multiple graphs sharing a common node set.

1) Existing methods extract features, considering either of graph smoothness or discrimination. The proposed method extracts features, considering the both two aspects, as spectral transforms. The obtained features or eigenvectors can be used to generate kernels, leading to multiple kernel learning to solve the label propagation problem efficiently.

2) Existing methods estimate weights over given graphs, like selecting the most reliable graph. This framework is however unable to consider densely connected subgraphs, which we call locally informative graphs (LIGs). The proposed method first runs spectral graph partitioning over each graph to capture LIGs in eigenvectors and then an existing method of label propagation for multiple graphs is run over the entire eigenvectors.

I will show empirical advantages of the two proposed methods by using both synthetic and real, biological networks.

Speaker:

Prof. Hiroshi Mamitsuka
Kyoto University

Professor Hiroshi Mamitsuka is a director of the Bioinformatics Center of Kyoto University in Uji. He has a joint appointment at the Institute for Chemical Research and the School of Pharmaceutical Sciences, both at Kyoto University. Prior to his academic carrier he worked, in 1991-2002, in the Machine Learning group of NEC Research Laboratories in Japan. He graduated from the University of Tokyo, Japan in 1988, where he also later obtained his PhD from in 1999, while working for NEC.

External Link:

http://www.bic.kyoto-u.ac.jp/pathway/mami/