"The restaurant next to us is good."
In the structure AのB, B is a property possessed by or related to A.
レストランのとなり means "the space next to the restaurant." Or "relative to the restaurant, the space next to it."
となりのレストラン means "the restaurant that is in the space beside (us)" or "relative to the space beside (us), the restaurant (that occupies it)." (The "us" being inferred from context.)
It is still possessive, it's just that it can be used in situations that when translated to English don't sound naturally like something that can possess anything.