Collision with Andromeda Galaxy
As you say, expansion is proportional to distance. And in fact, compared to the size of the (observable) Universe, Andromeda and our Milky Way are close together. Indeed, farthest objects are now more than 20 billion Ly from us, whereas Andromeda is only 2.5 million Ly away. That is a 1/10000 factor.

The space expansion between them is not enough to set them apart, because of their general motion. On small scale (until galaxy cluster scale), the motion is primarily ruled by gravity. Galaxy cluster are in fact the largest gravitationally bound systems we know. 


  They typically contain no more than 50 galaxies in a diameter of 1 to 2 megaparsecs


Since Andromeda is the closest galaxy, it is inside "our" galaxy cluster, and stays bound to ours by gravity.