Is changing the label at a node O(N)?

The only way I can think of to do it is with a map, like the following -- which works, but seems like its speed must be linear in the number of nodes of the graph:

> :m Data.Graph.Inductive.Example Data.Graph.Inductive.Graph

> let f c@(adjIn, node, lab, adjOut) = case node of {1 -> (adjIn, node, 'b', adjOut); _ -> c}

> loop

mkGraph [(1,'a')] [(1,1,())]

> gmap f loop

mkGraph [(1,'b')] [(1,1,())]

> 

Is that in fact the right way? Am I somehow missing the point of FGL if I have to do a lot of that?