graphs and networks - Why is NeighborhoodGraph so slow?

To get neighboring vertices I first tried:

gg = GridGraph[{10, 10, 10, 10}];
VertexList[NeighborhoodGraph[gg, 1, 1]] // AbsoluteTiming  

{5.539308, {1, 2, 11, 101, 1001}}

But that is really slow. This is much faster and still uses the new Graph package:

Union[VertexInComponent[gg, 1, 1], VertexOutComponent[gg, 1, 1]] // AbsoluteTiming

{0.000172, {1, 2, 11, 101, 1001}}'

I believe that this mimics the NeigborhoodGraph approach above, but is still much faster than using NeighborhoodGraph:

VertexList[Subgraph[gg, Union[VertexInComponent[gg, 1, 1], 
      VertexOutComponent[gg, 1, 1]]]] // AbsoluteTiming

{0.000306, {1, 2, 11, 101, 1001}}

The last two approaches are also faster than NeighborhoodVertices from the GraphUtilities package:

Needs["GraphUtilities`"]
NeighborhoodVertices[gg, 1, 1] // AbsoluteTiming

{0.017248, {1, 2, 11, 101, 1001}}

I'm working with large graphs that I need to manipulate quickly for several interactive information visualization tools. Any tips on why NeighborhoodGraph is so slow here and how to best use the new Graph package when speed is an issue?

Answer

The issue is that NeighborhoodGraph is attempting to infer the layout of the original GridGraph. The layout algorithm for the parent graph is responsible for the slowness. At the cost of loosing the layout information this can be sped-up:

In[1]:= gg = GridGraph[{10, 10, 10, 10}, GraphLayout -> None];

In[2]:= VertexList[NeighborhoodGraph[gg, 1, 1]] // AbsoluteTiming

Out[2]= {0.0199998, {1, 2, 11, 101, 1001}}

The GraphLayout -> None has the effect that Graph object is not automatically rendered:

In version 9 and later, the simpler

NeighborhoodGraph[g, n, GraphLayout -> None]

form can be used for much faster neighbourhood graph computations.