Graph Search at Facebook scale is hard. They have to use tricks to get relevant results quickly. WeakAnd, StrongOr to limit connectedness.
If you are working on a smaller scale... it's easier.
Post: http://maxdemarzi.com/2013/01/28/facebook-graph-search-with-...