Learning to discriminate between different sensory stimuli is essential for survival. In rodents, the olfactory bulb, which contributes to odor discrimination via pattern separation, exhibits extensive structural synaptic plasticity involving the formation and removal of synaptic spines, even in adult animals. The network connectivity resulting from this plasticity is still poorly understood. To gain insight into this connectivity we present here a computational model for the structural plasticity of the reciprocal synapses between the dominant population of excitatory principal neurons and inhibitory interneurons. It incorporates the observed modulation of spine stability by odor exposure. The model captures the striking experimental observation that the exposure to odors does not always enhance their discriminability: while training with similar odors enhanced their discriminability, training with dissimilar odors actually reduced the discriminability of the training stimuli. Strikingly, this differential learning does not require the activity-dependence of the spine stability and occurs also in a model with purely random spine dynamics in which the spine density is changed homogeneously, e.g., due to a global signal. However, the experimentally observed odor-specific reduction in the response of principal cells as a result of extended odor exposure and the concurrent disinhibition of a subset of principal cells arise only in the activity-dependent model. Moreover, this model predicts the experimentally testable recovery of odor response through weak but not through strong odor re-exposure and the forgetting of odors via exposure to interfering odors. Combined with the experimental observations, the computational model provides strong support for the prediction that odor exposure leads to the formation of odor-specific subnetworks in the olfactory bulb.