In e-commerce recommender systems, providing product suggestions to customers that are often bought together, which is called “complementary recommendation,” not only improves customer experience but also boosts business impact. However, in practice, it is highly challenging to efficiently extract the complementary relations between the items due to noisy and low coverage of the co-purchased records in transaction datasets. To address these challenges, graph neural networks (GNN) have been increasingly adopted in complementary item recommendations thanks to their capabilities in integrating side-information and topological structures to extract these complex item relationships. However, most existing GNN-based methods fall short in learning better product complementary representation since they often utilize a simple one-to-one product-to-vector mapping strategy, which fails to describe the transitive logic of complementary items. To overcome this challenge, we propose a new GNN model called transitivity-encoded graph attention networks (TransGAT). To our knowledge, TransGAT is the first method that extends representation space by encoding the behavioral direction into embedding space in GNN and enabling mutual relationship extraction between complementary items. In order to better extract customer's intrinsic behavioral information, we further adopt the substitute information as the guidance by jointly learning complements and substitutes graphs and coupling them together. Moreover, several self-supervised data augmentation strategies are incorporated in our approach. Through evaluations on three real-world datasets, TransGAT consistently surpasses contemporary benchmarks, showcasing its prowess in complementary item recommendations.