Two non-isomorphic graphs have the same feature vector

Photonic Software Strawberry Fields
1

Hi all,
I am currently working on graph isomorphism.
If I understood well this paper:
“Graph isomorphism and gaussian boson sampling. arXiv preprint arXiv:1810.10644, 2018”
two isomorphic graphs always have the same feature vector (minus a small difference because of sampling, at least the exact calculation should return the same values).
I decided to feature vectors for all the 4-node non-isomorphic graphs (which correspond to 11 graphs).
I defined them by their adjacency matrix and used the
sf.apps.similarity.feature_vector_events
function. I was expecting the feature vectors to be all different (since I perform the exact calculation) but I actually noticed that C_{4} and S_{3} have the same feature vectors! They are also identical for two other graphs: the one-edge graph and the two-connected-edges graph (see picture at the bottom of this post).

Here is a code to reproduce the feature vectors:

import numpy as np
import networkx as nx
from strawberryfields.apps import similarity

# list of non isomorphic 4 nodes graphs
# one edge
oe_a = np.array([[0.0, 1.0, 0.0, 0.0],
                 [1.0, 0.0, 0.0, 0.0],
                 [0.0, 0.0, 0.0, 0.0],
                 [0.0, 0.0, 0.0, 0.0]])
# two edges connected
tec_a = np.array([[0.0, 1.0, 1.0, 0.0],
                  [1.0, 0.0, 0.0, 0.0],
                  [1.0, 0.0, 0.0, 0.0],
                  [0.0, 0.0, 0.0, 0.0]])
# S3
sta_a = np.array([[0.0, 1.0, 1.0, 1.0],
                  [1.0, 0.0, 0.0, 0.0],
                  [1.0, 0.0, 0.0, 0.0],
                  [1.0, 0.0, 0.0, 0.0]])
# C4
sq_a = np.array([[0.0, 1.0, 0.0, 1.0],
                 [1.0, 0.0, 1.0, 0.0],
                 [0.0, 1.0, 0.0, 1.0],
                 [1.0, 0.0, 1.0, 0.0]])

orbit = [2, 4]

print("Feature vectors for 4 nodes graphs, from adjacency matrices (exact calculation)")
print("One edge ", similarity.feature_vector_events(nx.Graph(oe_a), orbit))
print("Two edges connected ", similarity.feature_vector_events(nx.Graph(tec_a), orbit))
print("S3 ", similarity.feature_vector_events(nx.Graph(sta_a), orbit))
print("C4 ", similarity.feature_vector_events(nx.Graph(sq_a), orbit))

As you can see, all of the above return
[0.20408163265306095, 0.14577259475218624]
which are identical.
Is it a bug or something I didn’t get in the theory?
Thanks in advance.
Edgard

4_graphs
4_graphs1400×1400 13.9 KB

2

Hi @Edgard_Pierre and welcome to the forum!

If two graphs are isomorphic then they will have the same feature vector. However, this is not a necessary and sufficient condition, i.e., two non-isomorphic graphs can have the same feature vector.

Note that these feature vectors are constructed based upon event or orbit probabilities, which are a post-processing of sample probabilities. If you were to add additional events or orbits, you may be able to resolve the feature vectors of the two non-isomorphic graphs.

For example, consider changing event_photon_numbers in feature_vector_events.

1 Like
3

Hi @Tom_Bromley .
Thanks a lot! :slightly_smiling_face:
I have been using Strawberry Fields and Pennylane for a year now, never too late to join the forum!

I see, so this is not a sufficient condition. So is there a way to make graph isomorphism detector with feature vectors then?
I actually tried to tune parameters, but there is not that many degrees of freedom for such small graphs. I actually tried all the possible events by changing the event_photon_numbers parameter, but every time the feature vector is identical for the four graphs in my toy-model example posted above.
For example, here is the output of the code above, changing the “orbit” parameter with [0, 1, 2, 3, 4]:

Feature vectors for 4 nodes graphs, from adjacency matrices (exact calculation)
One edge  [0.28571428571428564, 0.0, 0.204081632653061, 0.0, 0.14577259475218632]
Two edges connected  [0.2857142857142855, 0.0, 0.20408163265306115, 0.0, 0.14577259475218662]
S3  [0.28571428571428575, 0.0, 0.20408163265306073, 0.0, 0.14577259475218585]
C4  [0.28571428571428564, 0.0, 0.20408163265306095, 0.0, 0.14577259475218624]

Thanks.
Edgard

4

Hey @Edgard_Pierre!

Some of the Xanadu team have worked on investigating GBS for graph isomorphism, check out this paper. In this case, you can consider the sample probabilities. There is an infinite number of sample probabilities (since you can get any number of photons in each mode), and capturing the full set helps determine isomorphism.

The reason that we coarse-grain sample probabilities into event and orbit probabilities is that individual sample probabilities can be hard to accurately resolve on real hardware. Hence, although the coarse-grained feature vectors may lose some information, they hopefully still contain useful information and their composition can be tweaked (e.g., changing the orbits or events) to help resolve similar graphs.