Learning New Classes Federatively without a Shared Label Space

Federated few-shot class-incremental learning (FFSCIL) assumes that new classes arrive in one shared global label space. Once clients label the world with private, partially overlapping taxonomies, the server must first decide which client classes denote the same concept, from one to five samples and with no correspondence oracle. We study this concept-identity problem as Taxonomy-Free FFSCIL and build its benchmark from real taxonomies: synonyms, real homonyms, and clients that label at the superclass level. We propose FedTaxo, which encodes each local class as a feature-sharing concept capsule and grows a latent concept graph by re-clustering every novel capsule each session under the constraint that two identifiers of one client are never one concept. For a Gaussian surrogate, a centered threshold identifies concepts at the minimax rate, and constrained re-clustering recovers a session's exact partition under a separating score. Controlled experiments on four datasets show that the assignment procedure matters more than the matching score: re-clustering recovers 85% of an oracle's novel-class gain, against 69% when the same score is assigned greedily, while a learned matcher adds little accuracy but recovers far more of the true sub/super edges. When client taxonomies genuinely cross-cut, even merging by true set overlap falls below not federating. Code, protocol and LLM-written client vocabularies are available at https://anonymous.4open.science/r/fedtaxo-iclr27-FF2A/.