An online concierge system maintains a graph of items available for purchase. The graph maintains edges between items, where an edge between an item and an additional item indicates that one or more customers have previously replaced the item with the additional item. The edge between the item and the additional item also identifies a number of times customers have replaced the item with the additional item. When a customer orders an item, the online concierge system traverses the graph of items to identify candidate replacement items for the ordered item and identifies one or more of the candidate replacement items to the customer. When identifying the candidate replacement items, the online concierge system accounts for distance between the ordered item and different candidate replacement items in the item graph.