<p>Graph similarity computation, as a fundamental step in graph data analysis tasks, has consistently been a prominent topic. Existing approaches treat graph similarity computation as a prediction task, employing graph neural networks to learn the similarity of two graphs through interactions at the node or graph level. To capture fine-grained interactions between graphs, cross-layer interactions are also employed, which results in high computational costs during both training and inference stages. In contrast, we demonstrate that costly node-level interactions can be circumvented, and high-quality learning can be achieved through Euler’s identity, which we refer to as Efficient Rotation Matching (ERMat). Specifically, we first design a multi-level union graph embedding network, GTPool, which utilizes graph transformers and graph pooling. This network can integrate information from different perspectives to generate graph embeddings. Additionally, we linearize the computational complexity of the graph transformer via a kernelized softmax operator. Next, the graph embeddings are mapped to complex vector space, defining the pseudo-similarity associated with the neural tensor network as rotation in complex vector space, providing a more accurate expression of similarity between arbitrarily structured graphs through Euler’s identity. Extensive experiments on four real graph datasets show that it achieves superior results in comparison with state-of-the-art methods.</p>