We have developed a framework for secure joint querying over federated graph databases using secure multiparty computation (SMPC) protocols in two stages. We start with utilizing the Neo4j graph database on top of the existing Conclave system for secure multi-party relational queries. This provides an effective solution – and thus a conceptional proof-of-concept – without the need of investing heavily into the development. However, as a consequence, it lacks efficiency, as this encounters a significant computational overhead that renders it impractical for real-world usage. Having established the effectiveness of our approach, we turn to a two-stage improvement to the original implementation. The first stage optimizes the performance of the query execution by eliminating the need for sorting after obtaining the final result. The second stage reduces waiting times in the inter-process communication by parallelizing the execution of subqueries for each party. Through a series of experiments, we demonstrate the performance enhancements achieved when executing the subqueries in two different ways: sequentially and in parallel. Furthermore, the results show that, even with a large dataset, our framework achieves execution times of fractions of a second, reducing the running time by two orders of magnitude. Our results also indicate that the execution times and overheads of our system are comparable to those of insecure federated queries with Fabric Neo4j. Overall, our framework addresses the challenges of secure joint querying over federated graph databases and provides substantial performance enhancements over our initial ad-hoc implementation, making it a practical solution for real-world usage.