We propose a novel algorithm for generating expressive graph and node representations utilizing graph products. These representations, based on simple substructure counts in product graphs, aim to encode structural information that is often missed by standard message passing graph neural networks (MPNNs). MPNNs allow to learn vector representations of graphs, that are used in critical domains like drug discovery, social network analysis, protein folding and transportation networks. Their expressiveness is limited by the Weisfeiler-Leman (WL) graph isomorphism test, meaning they are unable to distinguish certain non-isomorphic graphs and fail to recognize important substructures, which restricts their overall capability. Our approach, called Product Substructure Count (PSC), addresses this by utilizing graph products to transform graphs. The transformed graphs encode extensive structural information within simple substructures, such as cycles. By counting these substructures at both the graph and node levels, we can generate embeddings that represent the graph as a whole as well as individual nodes. We show that PSC representations outperform WL in isomorphism testing and improve the representational capacity of MPNNs across multiple benchmark datasets.