Graph-based clinical recommender: Predicting specialists procedure orders using graph representation learning.

OBJECTIVE: To determine whether graph neural network based models of electronic health records can predict specialty consultation care needs for endocrinology and hematology more accurately than the standard of care checklists and other conventional medical recommendation algorithms in the literature. METHODS: Demand for medical expertise far outstrips supply, with tens of millions in the US alone with deficient access to specialty care. Rather than potentially months long delays to initiate diagnostic workup and medical treatment with a specialist, referring primary care supported by an automated recommender algorithm could anticipate and directly initiate patient evaluation that would otherwise be needed at subsequent a specialist appointment. We propose a novel graph representation learning approach with a heterogeneous graph neural network to model structured electronic health records and formulate recommendation/prediction of subsequent specialist orders as a link prediction problem. RESULTS: Models are trained and assessed in two specialty care sites: endocrinology and hematology. Our experimental results show that our model achieves an 8% improvement in ROC-AUC for endocrinology (ROC-AUC = 0.88) and 5% improvement for hematology (ROC-AUC = 0.84) personalized procedure recommendations over prior medical recommender systems. These recommender algorithm approaches provide medical procedure recommendations for endocrinology referrals more effectively than manual clinical checklists (recommender: precision = 0.60, recall = 0.27, F1-score = 0.37) vs. (checklist: precision = 0.16, recall = 0.28, F1-score = 0.20), and similarly for hematology referrals (recommender: precision = 0.44, recall = 0.38, F1-score = 0.41) vs. (checklist: precision = 0.27, recall = 0.71, F1-score = 0.39). CONCLUSION: Embedding graph neural network models into clinical care can improve digital specialty consultation systems and expand the access to medical experience of prior similar cases.

SP-GNN: Learning structure and position information from graphs.

Graph neural network (GNN) is a powerful model for learning from graph data. However, existing GNNs may have limited expressive power, especially in terms of capturing adequate structural and positional information of input graphs. Structure properties and node position information are unique to graph-structured data, but few GNNs are capable of capturing them. This paper proposes Structure- and Position-aware Graph Neural Networks (SP-GNN), a new class of GNNs offering generic and expressive power of graph data. SP-GNN enhances the expressive power of GNN architectures by incorporating a near-isometric proximity-aware position encoder and a scalable structure encoder. Further, given a GNN learning task, SP-GNN can be used to analyze positional and structural awareness of GNN tasks using the corresponding embeddings computed by the encoders. The awareness scores can guide fusion strategies of the extracted positional and structural information with raw features for better performance of GNNs on downstream tasks. We conduct extensive experiments using SP-GNN on various graph datasets and observe significant improvement in classification over existing GNN models.

GNNExplainer: Generating Explanations for Graph Neural Networks.

Graph Neural Networks (GNNs) are a powerful tool for machine learning on graphs. GNNs combine node feature information with the graph structure by recursively passing neural messages along edges of the input graph. However, incorporating both graph structure and feature information leads to complex models and explaining predictions made by GNNs remains unsolved. Here we propose GnnExplainer, the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-based machine learning task. Given an instance, GnnExplainer identifies a compact subgraph structure and a small subset of node features that have a crucial role in GNN's prediction. Further, GnnExplainer can generate consistent and concise explanations for an entire class of instances. We formulate GnnExplainer as an optimization task that maximizes the mutual information between a GNN's prediction and distribution of possible subgraph structures. Experiments on synthetic and real-world graphs show that our approach can identify important graph structures as well as node features, and outperforms alternative baseline approaches by up to 43.0% in explanation accuracy. GnnExplainer provides a variety of benefits, from the ability to visualize semantically relevant structures to interpretability, to giving insights into errors of faulty GNNs.

G2SAT: Learning to Generate SAT Formulas.

The Boolean Satisfiability (SAT) problem is the canonical NP-complete problem and is fundamental to computer science, with a wide array of applications in planning, verification, and theorem proving. Developing and evaluating practical SAT solvers relies on extensive empirical testing on a set of real-world benchmark formulas. However, the availability of such real-world SAT formulas is limited. While these benchmark formulas can be augmented with synthetically generated ones, existing approaches for doing so are heavily hand-crafted and fail to simultaneously capture a wide range of characteristics exhibited by real-world SAT instances. In this work, we present G2SAT, the first deep generative framework that learns to generate SAT formulas from a given set of input formulas. Our key insight is that SAT formulas can be transformed into latent bipartite graph representations which we model using a specialized deep generative neural network. We show that G2SAT can generate SAT formulas that closely resemble given real-world SAT instances, as measured by both graph metrics and SAT solver behavior. Further, we show that our synthetic SAT formulas could be used to improve SAT solver performance on real-world benchmarks, which opens up new opportunities for the continued development of SAT solvers and a deeper understanding of their performance.