The reason that the S-N graph is slightly deceptive is this: I can give you a pre-cracked steel part where the material is perfectly sound except that there is a crack, and I can size the crack so that the part will fail at an arbitrarily low load, in just one half-cycle of loading (you only load up, it fails before you cycle load back to zero). It looks as if I gave you "weaker" steel, but the steel is fine, it's the geometry of the part that's wrong. It may appear to the naked eye that the geometry is fine, because I can make the crack in such a way that you won't see it.
When aluminum fails due to fatigue, the tensile yield stress appears to be lowered, and thus we talk of fatigue "weakening", but only because you ignore the presence of cracks. Say you have a 1 inch square aluminum rod under a 20,000lb normal load, so you think the longitudinal tensile stress in the rod is 20ksi. But in fact it's not, it's very high, at the level of a yield stress, since there are cracks in the material, and the crack surface is a stress-free boundary. So the load has to find elsewhere to go, figuratively speaking. So it looks as if you had a weak rod. But then you can apply a compressive load just under the nominal yield (not any weakened yield), and guess what, if the rod doesn't buckle, nothing else will happen. So the material is not weaker. The part is. That's a subtle difference.
So, there's a very easy way to tell if a material is weaker, or just the part is precracked and thus weaker on average: just apply compressive load instead of a tensile one. In metals, the compressive and tensile strength should be similar. When it isn't, you have a precracked part. When it is, and both are low, you have true material weakening at the microscopic level.