Decoding the Social Graph: A Large-Scale Analysis of Facebook Graph Search

TL;DR

How do millions of people actually search a social network? This seminal study by researchers from Meta and UIUC analyzes Facebook's Graph Search logs to reveal a fundamental dichotomy: we use simple name searches to find our friends, but we rely on complex, structured grammar to discover the "friends of friends" and new communities. The paper provides a rare, quantitative roadmap of how demographics and social distance dictate our digital curiosity.

Context: Beyond Keywords

In the early 2010s, social search was a siloed experience. If you wanted to find someone, you typed their name; if they weren't your immediate friend, the search often failed. Facebook's Graph Search was a paradigm shift toward Human-Computer Information Retrieval (HCIR), allowing users to execute complex queries like "Photos of people who live in China." This paper situates itself as the first large-scale audit of such a system, moving beyond "what" people search for to "why" and "how" they navigate the social fabric.

The Core Conflict: Navigation vs. Exploration

The authors identify two primary query types that coexist in the Facebook ecosystem:

1. Named Entity Queries (NEQ): Direct "navigational" searches for a specific person or page.
2. Structured Queries (SQ): "Exploratory" searches using grammar predicates (e.g., residents, likers, employees).

The "Aha!" moment of the paper is the Graph Search Distance analysis. As shown in the data, these two types are not competitors—they are specialized tools.

Figure 1: The UI dichotomy between Typeahead (navigation) and Browse (exploration).

Methodology: Semantic Templates and Lift Predicates

Because every user's social circle is different, a query like "Friends of Alice" and "Friends of Bob" are functionally identical but textually different. To solve this, the authors used Semantic Query Templates, replacing specific names with tokens ($) to analyze the underlying intent.

A standout contribution is the Lift Predicate. A lift predicate is a term that, when added, makes a query more popular than its simpler version. For instance, "Users named Alice who live in California" might be more frequent than just "Users who live in California." This highlights how users use specific attributes to disambiguate results in a crowded social space.

Key Insights: How Identity Shapes Search

The study breaks down search behavior across several demographic axes, revealing fascinating social patterns:

• Age Matters: Search behavior follows a cyclic pattern. Users in their 30s are the most "adventurous" (searching for non-friends), while users over 70 focus almost exclusively on their existing friend circle.
• The Gender Gap: Females issue more queries overall and focus more on first-degree connections (friends), whereas males skew slightly more toward exploring the broader network (non-friends).
• The Social Capital Effect: The more friends you have, the more you search. Interestingly, "Celebrities" (users with >10,000 friends) use the search almost purely for navigation, rarely using the exploratory power of structured grammar to find new people.

Figure 2: Analysis showing how the fraction of 1st-degree (Friend) queries peaks in older age groups.

Why Distance Changes Everything

The authors found that the predicates we use change based on how far we are from the target:

• Searching Friends: Queries are shorter. Users look for interests (pages liked) and media (videos liked).
• Searching Non-Friends: Queries are longer and more "functional." Users use location (residents) and affiliation (employees) to filter the billions of potential results down to a relevant subset.

Figure 3: Distribution of graph distances for the top 30 predicates.

Critical Analysis & Conclusion

This work proves that "People Search" is a unique beast in the IR world. Unlike document search, social search is heavily influenced by Weak Ties (Granovetter’s theory)—we use professional criteria (employers) to find distant connections and personal criteria (likes) to interact with close ones.

Limitations: The study is based on 2013-2014 data; the rise of mobile-first vertical scrolling might have shifted these behaviors toward more passive discovery. Furthermore, the paper relies on quantitative logs, which tell us what users did, but not the intent (e.g., was it "social grooming" or "professional networking"?).

Future Outlook: For modern AI-driven social networks, these insights suggest that "Search" should be hyper-personalized not just based on what you like, but on your Graph Distance. Suggesting a local "friend of a friend" requires a fundamentally different ranking logic than helping you find a celebrity.