Cross-posted on StackExchange

Consider the following graph with the vertex property "foo".

g = Graph[{{1, 2}, {3, 4}}, {{1, 2} <-> {3, 4}}, 
  Properties -> {{1, 2} -> {"foo" -> "x"}, {3, 4} -> {"foo" -> "y"}}]

The vertices of this graph are lists. To prove that list-vertices are valid I will point out that some builtins such as NearestNeighborGraph will return such graphs.

Unfortunately, I can't seem to query vertex properties:

PropertyValue[{g, {1, 2}}, "foo"]    
(* $Failed *)

If the vertex names are not lists, the problem goes away:

g2 = VertexReplace[g, {{1, 2} -> "a", {3, 4} -> "b"}]

PropertyValue[{g2, "a"}, "foo"]
(* "x" *)

This is clearly a bug, one of the many related to graph property handling.

My questions are:

• Is there a workaround which is not very slow? An obvious workaround is to VertexReplace all vertices, like above, then query the property using the new name. Unfortunately, this is quite slow.
• Is there a method to retrieve the property value for all vertices simultaneously (as opposed to just one), while avoiding this problem?

As a warning to people playing with this: there is also an unusual behaviour (bug?) in VertexReplace. You might think of trying

g3 = VertexReplace[g, v_ :> ToString[v]];

But the vertices of this graph are not what they seem. InputForm[g3] yields:

Graph[{ToString[{1, 2}], ToString[{3, 4}]}, 
 {UndirectedEdge[ToString[{1, 2}], ToString[{3, 4}]]}, 
 {Properties -> {ToString[{3, 4}] -> {"foo" -> "y"}, ToString[{1, 2}] -> {"foo" -> "x"}}}]

The ToString did not evaluate. I'm not 100% confident that Wolfram would consider this second problem a bug, but it prevents this type of application.

To see why VertexReplace is not a good workaround, try the following:

big = ExampleData[{"NetworkGraph", "CondensedMatterCollaborations"}];
VertexReplace[big, Thread[VertexList[big] -> Range@VertexCount[big]]]; // AbsoluteTiming

I don't know how long this takes to finish. I aborted the evaluation after 5+ minutes.

Another potential workaround is to try to get the values from Options[Graph]. Unfortunately, this is an extremely complicated task that I do not dare take on. There are multiple kinds of graph properties, each of which is stored in a different manner. They can also have default values, which are again treated differently for each. Given that most of this is not properly documented (it should be!), and the high abundance of problems with Mathematica's property handling functions, the risk of introducing more bugs with this approach seems very high.

Here's a usably fast workaround with VertexReplace:

Let us create a benchmark graph first:

big = ExampleData[{"NetworkGraph", "CondensedMatterCollaborations"}];
big2 = VertexReplace[big, v_ :> {v}];

Here's how long it takes to extract the "Name" property from the original graph:

PropertyValue[{big, #}, "Name"] & /@ VertexList[big] // 
  Take[#, 5] & // AbsoluteTiming
(* {0.035828, {"L. Radzihovsky", "SD. Frischat", "R. Kuhn", 
  "CWJ. Beenakker", "JA. Melsen"}} *)

As stated above, this won't work on big2:

PropertyValue[{big2, #}, "Name"] & /@ VertexList[big2] // 
  Take[#, 5] & // AbsoluteTiming
(* {0.040743, {$Failed, $Failed, $Failed, $Failed, $Failed}} *)

We can use VertexReplace to wrap each vertex with the same symbolic wrapper. Here's how much overhead this introduces:

With[{fixed = VertexReplace[big2, v_ :> privateWrapper[v]]},
   PropertyValue[{fixed, #}, "Name"] & /@ VertexList[fixed]
   ] // Take[#, 5] & // AbsoluteTiming
(* {0.172228, {"L. Radzihovsky", "SD. Frischat", "R. Kuhn", 
  "CWJ. Beenakker", "JA. Melsen"}} *)

This is already usable, but I am still looking for answers that improve on its performance.