Abstract: We evaluate the particular performance of different quantum machine learning networks on a graph classification task. Quantum circuits with varying internal symmetry that completely, partially and not at all confer to the symmetry of the graph show different performance on the data set. The convergence results are inspected using a number of special graphs with particular structure. These are unlikely to occur in the training data and cover specific cases that refute the assumption that the quantum neural network learns simpler surrogate models based on the number of edges in the graph.
Introduction: The Surrogate Model Problem
Machine learning models, including quantum ones, are often "black boxes." When a model performs well, it isn't always clear if it has learned the underlying logic or merely found a "shortcut." In graph theory, a property like "connectedness" (whether every node can reach every other node) is highly correlated with the number of edges.
As shown in Figure 1, the probability of a graph being connected follows a sharp phase transition based on the edge probability $p$. In a standard random dataset, a model might achieve high accuracy simply by "counting" edges—a shortcut known as a surrogate model. This paper addresses how to validate the internal logic of a Quantum Neural Network (QNN) by probing it with specific "edge cases" designed to trick a shortcut-taking model.
Methodology: Symmetry and Edge Cases
The authors compared three different QNN architectures (ansatzes) to classify 8-node graphs as connected or disconnected:
- Permutation-invariant: Designed to be invariant under node swapping, mirroring the fact that node order doesn't change graph properties.
- Cyclic-invariant: A partially symmetric model.
- Standard ansatz: A "strongly-entangling" layer with no specific symmetry constraints.
To verify if these models learned more than just edge counts, they were tested on seven "special" graphs. For example, a graph with a nearly complete subgraph but one isolated node has a very high edge count (implying connectedness) but is actually disconnected. Correct classification of such cases proves the model isn't just counting edges.
Results and Performance
The training results demonstrate a clear hierarchy in performance based on architectural symmetry. The permutation-invariant QNN significantly outperformed the others by focusing on structure rather than node identity.
As seen in Figure 2, the permutation-invariant ansatz reached roughly 85-90% accuracy, while the cyclic-invariant model reached ~70%. The standard "strongly-entangling" ansatz failed to converge, performing near the baseline. Crucially, the permutation-invariant model correctly identified disconnected graphs even when they had a high number of edges, refuting the hypothesis that the QNN was merely a glorified edge-counter.
Conclusion
The study highlights that symmetry is a "superpower" for QNNs, allowing them to learn complex topological features rather than relying on surrogate shortcuts. While the symmetric models still struggled with certain complex structures like specific tree depths, they provided much stronger signals and better generalization than standard models. The authors suggest that this "edge case" methodology should be a standard part of the QNN evaluation toolkit to ensure models are learning robust, deployable logic.
Summary updated