We are interested in computing the similarity of any two nodes belonging to the same or different graphs; most similar nodes can then be matched. As an example, in graphs which are snapshots from the time evolution of a single link structure, matching similar nodes could reveal conserved substructures or identify missing node labels. There could be hints on preferred matching nodes (elemental similarity) or the decision be based solely on the graph structures (topological similarity). Existing approaches are inherently sequential and can analyse graphs of only a few thousands of nodes. We propose NSD 1 - Network Similarity Decomposition - which is a fast serial, but also - and most importantly - a scalable, parallelizable approach enabling the processing of million-node graph pairs over parallel platforms.