Link Prediction in Multipartite Graphs With Application to Drug Repositioning Studies

Developing new ethical drugs is exceedingly expensive in terms of both time and resources. A single drug can take up to a decade to bring to market, with costs soaring to over a billion dollars. Drug repositioning has thus become an attractive alternative to the development of new compounds, with growing interest in the use of in silico repositioning predictions. Bipartite graphs and efficient biclique enumeration algorithms can be used to study drug-protein or other pairwise crucial interactions. Extensions of this approach to datasets with three or more divergent data types have been hobbled, however, by a lack of effective analytics. To address this shortcoming, a highly innovative and efficient graph theoretical technique is introduced to impute potential edges (links) in an arbitrary multipartite graph. The utility of this method is demonstrated on five tripartite graphs, each comprised of three partite sets, one each for diseases, drugs, and gene products of interest, and with interpartite edges denoting known interactions or associations. Evidence for the reliability of imputed edges is also reported.