Object recognition has been studied for decades. Most existing approaches, however, focus on a relatively small number of object categories. In this paper we study the problem of large-scale object classification with tens of thousands of categories. At this scale, label relations become critical for achieving good performance. We propose to capture these relations in a label relation graph and use this graph to integrate information from multiple classifiers. Specifically, we train deep convolutional neural networks on individual semantic parts of the label space and combine their predictions using the graph structure. Our approach achieves significant improvements on the ImageNet Large Scale Visual Recognition Challenge.

Our label relation graph encodes multiple types of semantic relations: exclusion (mutual exclusion between labels), hierarchy (is-a relations), and overlap (labels that can co-occur). These relations are derived from the WordNet ontology and augmented with learned statistical relations from data. The graph serves as a principled framework for combining predictions from multiple expert classifiers, each trained on a semantically coherent subset of the label space.

The number of object categories in the real world is enormous. While traditional object recognition benchmarks contain tens or hundreds of classes, the ImageNet dataset alone organizes more than 21,000 synsets with over 14 million images. Learning to classify such a large number of categories poses unique challenges: classes are not independent but are related through semantic hierarchies, and confusions between classes are highly structured. Ignoring these label relations leads to suboptimal classifiers.

Prior work has explored flat classification, where each class is treated independently, and hierarchical classification, which uses only the tree structure of a label taxonomy. However, real-world label relations are richer than a simple tree: a Siberian Husky is both a dog and a sled dog; a convertible is both a car and a type of vehicle. We argue that a graph structure that captures exclusion, hierarchy, and overlap is necessary for effective large-scale classification. Our label relation graph provides exactly this.

Our approach consists of two stages. First, we partition the label space into semantically coherent groups using the label relation graph. Each group defines a sub-problem that can be solved by a dedicated deep neural network classifier. Second, we combine the predictions of all sub-classifiers using inference on the label relation graph. This combination takes into account mutual exclusion and hierarchy constraints to produce a globally consistent prediction.

For the label space partitioning, we use a combination of the WordNet hierarchy and spectral clustering on the confusion matrix of a baseline classifier. The resulting partitions ensure that semantically similar and frequently confused classes are grouped together, allowing each expert classifier to focus on fine-grained distinctions within its group. Each expert is implemented as a deep convolutional neural network fine-tuned from a pre-trained model.

The label relation graph is a directed graph where nodes represent labels and edges encode three types of relations. Exclusion edges indicate that two labels cannot co-occur (e.g., "cat" and "dog" are mutually exclusive under "domestic animal"). Hierarchy edges represent is-a relations (e.g., "poodle" is-a "dog"). Overlap edges indicate potential co-occurrence (e.g., "vehicle" and "red object"). This graph is constructed from WordNet and augmented with data-driven edges learned from the training set.

Given the graph, we perform inference using a message-passing algorithm that propagates predictions along edges. The hierarchy edges allow coarse-to-fine classification: a classifier confident about "dog" but uncertain about the breed can still make useful predictions. The exclusion edges enforce consistency: if "Husky" is predicted, "Poodle" is automatically suppressed. This inference procedure is efficient and scales linearly with the number of edges.

We evaluate on the ImageNet Large Scale Visual Recognition Challenge (ILSVRC). Our baseline is a single deep CNN trained on all 1,000 classes. With our label relation graph approach, we train multiple expert CNNs, each on a semantically coherent subset of approximately 100-200 classes, and combine their outputs using graph inference. The combined system achieves a top-5 error rate reduction of over 2 percentage points compared to the single-model baseline.

We further analyze the impact of different relation types. Ablation studies show that hierarchy edges contribute the most improvement (1.3 points), followed by exclusion edges (0.5 points), while overlap edges provide a smaller but still significant gain (0.3 points). The combination of all three types yields the best performance, confirming our thesis that rich label relations are beneficial for large-scale classification.

We have presented a framework for large-scale object classification that leverages label relation graphs. By encoding exclusion, hierarchy, and overlap relations, our approach partitions the label space into manageable sub-problems and combines expert classifiers through graph-based inference. Our experiments on ImageNet demonstrate consistent improvements over baselines that ignore label relations. We believe this framework opens up promising directions for scaling object recognition to even larger and more complex label spaces.