Portable network resolving huge-graph isomorphism problem

Abstract The graph isomorphism, as a key task in graph data analysis, is of great significance for the understanding, feature extraction, and pattern recognition of graph data. The best performance of traditional methods is the quasi-polynomial time complexity, which is infeasible for huge graphs. This paper aims to propose a lightweight graph network to resolve the problem of isomorphism in huge graphs. We propose a partitioning algorithm with linear time complexity based on isomorphic necessary condition to handle network graphs that cannot be fully computed by a single computer. We use anti-weight convolution analysis and skip connections to obtain a more stable representation with fewer layers and parameters. We implement simulations on personal computer (PC) with graphs consisting of hundred millions of edges, demonstrating the identification performance ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mstyle scriptlevel="0"/> <mml:mstyle scriptlevel="0"/> <mml:mn>98</mml:mn> <mml:mi mathvariant="normal">%</mml:mi> </mml:mrow> </mml:math> ) and time efficiency.