The correct statement is: They both exert a strong gravitational pull on each other.
The Milky Way and the Andromeda galaxy are indeed both spiral galaxies and are moving toward each other due to their mutual gravitational attraction. In fact, they are expected to collide in the distant future. The Andromeda galaxy is slightly larger than the Milky Way galaxy in terms of the number of stars.