I read that this problem can be avoided using "mock objects" but my app is relying on the social graph and therefore this idea does not seem like a good option.
One question I would ask here is how do you expect to deterministically (and quickly!) test your application based on different structures of the social graph? I would recommend doing the legwork to create an internal representation of the social graph in your application so your business logic will work against that representation instead of talking directly to FB. Then you would have a separate component that would generate this internal representation of the graph via the Facebook APIs.
Your tests could then construct any graph of their choosing using your internal representation and Facebook is now totally out of the picture for you to accomplish your original goal to verify your app's logic.
If you don't want to do this legwork, the value of writing automated tests against the live system is limited as it will be difficult to investigate test failures and tests of these nature tend to be very brittle (i.e. they can fail because of configuration errors, network errors, etc)