It all depends on your representation of the graph.

If you just use an edge-set, i.e. you don't have "node data", you can get away with just storing the pure bit flags. If an edge is flagged 0, don't follow it; if all the edges that "lead to" a given "node" are 0, then the node is never reachable, and therefore doesn't "exist". There's zero cost since you don't need to store data per node. This can work very, very well if you have a simplistic or homogeneous search space. Often you can extrapolate the traversal cost of a given edge using just its position and direction.

In fact for most (non-hierarchical) pathfinding there is no need to store nodes at all aside from a convenient way to describe how edges interconnect; if you're using a homogeneous cubic search space, nodes have no real meaning. All that matters is edges and the distance between edge endpoints, which can be used to compute traversal costs. Since all edges are homogeneous, the position of an edge is irrelevant; only its direction is useful, because all edges that "point the same way" will have the same net cost.

You can of course increase the complexity of this by using edge vectors to look up traversal cost data from another map representation.

For sake of argument, consider a map comprising spherical regions of influence. Each sphere defines a traversal cost that spikes at the sphere's center and falls off to zero at the radius. Given an edge vector V, you can generate sample points at regular intervals along V, and sample them against the set of influence regions, to produce a final summation of the traversal cost of an edge (this is basic numeric integration from Calculus I here). In that way, you can sparsely represent a very large volume of space and its influence regions using the sphere representation, while using a discretized cubic volume of edge connections for pathfinding, thus minimizing storage costs at the minor expense of performance (for sampling the influence regions on each edge... which could of course be cached for performance at the expense of a tiny bit of memory. Everything's a trade-off.)

Of course that example is a bit pathological, since in The Real World you'd just use an influence-based steering system instead of pathfinding, but you get the idea.

Anyways... hope that gives you some ideas for how to optimize your approach.