Bi-submodular Optimization (BSMO) for Detecting Drug-Drug Interactions (DDIs) from On-line Health Forums

Online health discussion forums as information exchange repository are used by different patient groups for sharing experience and seeking advice. Their accessibility is tremendously expanded in the last decade with the rapid growth of mobile internet. Among many popular topics, "drug-drug interactions" (DDIs) forum embeds a large number of DDIs hazards patient experienced however not published. In this paper, we intend to uncover the potential DDIs from the online forums and formulate the task as a sub-graph detection problem, such that co-mentioned drugs and symptoms are modeled as vertices, along with the occurrences are modeled as weighted edges. Therefore, a connected sub-graph consisting of both symptoms and drug vertices reveals DDIs occurrence. We then propose a novel bi-submodular function to characterize the likelihood of DDI occurrence within a connected sub-graph and apply an approximated algorithm to resolve the bi-submodular optimization (BSMO). The complexity of the algorithm is nearly linear. Our extensive experiments demonstrate the effectiveness and efficiency of the proposed approach.