  The expressivity of Graph Neural Networks (GNNs) has been studied broadly in
recent years to reveal the design principles for more powerful GNNs. Graph
canonization is known as a typical approach to distinguish non-isomorphic
graphs, yet rarely adopted when developing expressive GNNs. This paper proposes
to maximize the expressivity of GNNs by graph canonization, then the power of
such GNNs is studies from the perspective of model stability. A stable GNN will
map similar graphs to close graph representations in the vectorial space, and
the stability of GNNs is critical to generalize their performance to unseen
graphs. We theoretically reveal the trade-off of expressivity and stability in
graph-canonization-enhanced GNNs. Then we introduce a notion of universal graph
canonization as the general solution to address the trade-off and characterize
a widely applicable sufficient condition to solve the universal graph
canonization. A comprehensive set of experiments demonstrates the effectiveness
of the proposed method. In many popular graph benchmark datasets, graph
canonization successfully enhances GNNs and provides highly competitive
performance, indicating the capability and great potential of proposed method
in general graph representation learning. In graph datasets where the
sufficient condition holds, GNNs enhanced by universal graph canonization
consistently outperform GNN baselines and successfully improve the SOTA
performance up to $31\%$, providing the optimal solution to numerous
challenging real-world graph analytical tasks like gene network representation
learning in bioinformatics.
