Several geospatial studies and applications require comprehensive semantic information from points-of-interest (POIs). However, this information is frequently dispersed across different collaborative mapping platforms. Surprisingly, there is still a research gap on the conflation of POIs from this type of geo-dataset. In this paper, we focus on the matching aspect of POI data conflation by proposing two matching strategies based on a graph whose nodes represent POIs and edges represent matching possibilities. We demonstrate how the graph is used for (1) dynamically defining the weights of the different POI similarity measures we consider; (2) tackling the issue that POIs should be left unmatched when they do not have a corresponding POI on the other dataset and (3) detecting multiple POIs from the same place in the same dataset and jointly matching these to the corresponding POI(s) from the other dataset. The strategies we propose do not require the collection of training samples or extensive parameter tuning. They were statistically compared with a “naive”, though commonly applied, matching approach considering POIs collected from OpenStreetMap and Foursquare from the city of London (England). In our experiments, we sequentially included each of our methodological suggestions in the matching procedure and each of them led to an increase in the accuracy in comparison to the previous results. Our best matching result achieved an overall accuracy of 91%, which is more than 10% higher than the accuracy achieved by the baseline method.