Predicting future node affinity in dynamic graphs is essential for applications such as recommender systems. However, existing methods, including state-of-the-art approaches like NAVIS, rely on continuous vector representations that struggle to explicitly capture, reason over, and memorize discrete, structured interaction motifs, limiting interpretability and generalization. To address this, we introduce G-MATCH (Graph-structured Memory with Attentive Template Consensus for Heterogeneous interactions), a novel paradigm that reformulates a node's state as a dynamic, heterogeneous graph of learnable interaction motifs. G-MATCH incorporates four key innovations: (1) state evolution via graph matching and dynamic motif creation/pruning, (2) a global motif bank for cross-node knowledge transfer, (3) interpretable affinity prediction through motif attribution, and (4) optimization with a listwise ranking loss and structured regularization. Extensive experiments on future affinity (TGB) and converted link prediction datasets demonstrate that G-MATCH consistently outperforms all strong baselines, including NAVIS, achieving an average improvement of +4.2% in NDCG@10. The model also excels in few-shot and limited-information settings. Ablation studies confirm the critical role of each component, and case studies highlight its unique capability for explainable, motif-level reasoning. The transition from linear states to graph-structured memory marks a significant advance, enabling superior performance and unprecedented interpretability in modeling complex node interactions.
