Community similarity is often assessed through similarities in species occurrences and abundances (i.e., compositional similarity) or through the distribution of species interactions (i.e., interaction similarity). Unfortunately, the joint empirical evaluation of both is still a challenge. Here, we analyze community similarity in ecological systems in order to evaluate the extent to which indices based exclusively on species composition differ from those that incorporate species interactions. Borrowing tools from graph theory, we compared the classic Jaccard index with the graph edit distance (GED), a metric that allowed us to combine species composition and interactions. We found that similarity measures computed using only taxonomic composition could differ strongly from those that include composition and interactions. We conclude that new indices that incorporate community features beyond composition will be more robust for assessing similitude between natural systems than those purely based on species occurrences. Our results have therefore important conceptual and practical consequences for the analysis of ecological communities.