Dynamic behavior modeling has become a crucial task for personalized recommender systems that aim to learn users’ time-evolving preferences on online platforms. However, many recommendation models rely on a single type of behavior learning, which significantly limits their ability to represent user-item relationships in real-life applications where interactions between users and items often come in multiple types (e.g., click, tag-as-favorite, review, and purchase). To offer better recommendations, this paper proposes the Evolving Graph Contrastive Memory Network (EGCM) to model dynamic interaction heterogeneity. Firstly, we develop a multi-relational graph encoder to capture short-term preference heterogeneity and preserve the dedicated relation semantics for different types of user-item interactions. Additionally, we design a dynamic cross-relational memory network that enables EGCM to capture users’ long-term multi-behavior preferences and the underlying evolving cross-type behavior dependencies over time. To obtain robust and informative user representations with both commonality and diversity across multi-behavior interactions, we design a multi-relational contrastive learning paradigm with heterogeneous short- and long-term interest modeling. We further provide theoretical analyses to support the modeling of commonality and diversity from the perspective of enhancing model optimization. Experiments on several real-world datasets demonstrate the superiority of our recommender system over various state-of-the-art baselines.