1. An image recognition apparatus that recognizes an object related to a specific object in an image, comprising: a holding unit configured to hold connective relationship information that indicates a connective relationship between objects; a generation unit configured to generate a plurality of candidates for a recognition order that indicates an order of recognizing objects in an object sequence including the specific object, a related object, and one or more intermediate objects connected between the specific object and the related object using the connective relationship information; a deciding unit configured to decide the recognition order from the plurality of candidates for the recognition order based on appreciation values calculated for respective candidates; a recognition unit configured to sequentially recognize objects from the image in accordance with the recognition order decided by the deciding unit; a connective relationship determination unit configured to determine whether or not an object recognized in a current turn of recognition performed by the recognition unit has a connective relationship with a previously extracted object obtained in a previous turn of recognition; an obtaining unit configured to obtain an object that has been determined as having a connective relationship by the connective relationship determination unit, as an extracted object; and an associating unit configured to associate the specific object with the related object, based on one or more objects extracted by a repetition of processing performed in the recognition order by the recognition unit, the connective relationship determination unit, and the obtaining unit.