When I want to clarify something and I say for example "Dogs, not cats.", I automatically want to write/say 'not' even though 'cats' is a noun, and for nouns one uses 'no'. But I'm quite sure this isn't the case here and it would sound really wrong. Could somebody explain the rule behind it? Surely, there must be one.
"Dogs, not cats"
is not a sentence: it is a contraction of a sentence. A fuller sentence would be (for example):
"I mean dogs, not cats."
That, in turn is a contraction of:
"I mean dogs; I do not mean cats."
Hence the "not" comes from association with the omitted verb.
The technical term for this is ellipsis; see NVZ's answer.
P.S. In the above answer, I have used the word 'contraction' in its normal, every-day usage to mean making "something smaller or shorter" (see Cambridge Dictionaries Online). It does not refer to the specific linguistic meaning of 'contraction' cited by NVZ.
Ellipsis (linguistics) — Wikipedia
It refers to the omission from a clause of one or more words that are nevertheless understood in the context of the remaining elements.
There are numerous distinct types of ellipsis acknowledged in theoretical syntax. Common examples from Wikipedia:
- Gapping: John can play the guitar, and Mary (can play) the violin.
- Stripping: John can play the guitar, and Mary (can play the guitar), too.
- Verb Phrase ellipsis: John can play the guitar; Mary can (play the guitar), too.
- Pseudogapping: They have been eating the apples more than they have (been eating) the oranges.
- Answer fragment: Q: Who has been hiding the truth? A: Billy (has been hiding the truth).
- Sluicing: John can play something, but I don’t know what (he can play).
- Nominal ellipsis: The first train and the second (train) have arrived.
- Comparative deletion: She ordered more beer than we could drink (beer).
- Null complement anaphora: They told Bill to help, but he refused (to help).
Your example is explained by TrevorD:
"(I mean) dogs; (I do) not (mean) cats."
For further reading, check out "Ellipsis" on Cambridge Dictionary, cited by TrevorD