Bird
Raised Fist0

People You May Know - Graph-Based Link Prediction

SYSTEM-DESIGNhardInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
People You May Know - Graph-Based Link Prediction
Enhance user engagement by suggesting potential connections using graph-based link prediction.
system-designhardFreq: highRecommendations
Prerequisites:Graph Neural NetworksEmbeddings
🎯
Problem Framing
Business Objective

Increase user engagement by suggesting relevant new connections.

ML Objective

Maximize the probability of a user accepting a suggested connection (P(accept|user, suggestion)).

Constraints
  • P99 latency < 100ms for suggestion generation
  • High throughput to handle millions of users
  • Cold start problem for new users
  • Privacy regulations on user data usage
Clarifying Questions
  • What is the current user base size and growth rate?
  • How often do users typically engage with connection suggestions?
  • What are the privacy constraints on using user data?
  • How frequently can we update the model with new data?
  • What is the acceptable trade-off between precision and recall for suggestions?
Out of Scope
✗ Non-social network recommendations
✗ Content-based recommendations
✗ Real-time chat or messaging features
📊
Offline Metrics
Precision@K: Measures the relevance of the top K suggestions, crucial for user satisfaction.
Recall@K: Ensures that we are capturing a significant portion of potential connections.
📈
Online Metrics
CTR (Click-Through Rate) on suggestions: Directly measures user engagement.
Connection acceptance rate: Indicates the quality of suggestions.
⚖️
Trade-offs

High precision might reduce recall, leading to fewer suggestions. Balancing these is key to maintaining user engagement.

💼
Business Metric

Increase in daily active users (DAU) due to enhanced engagement from suggestions.

🗄️
Data Sources
  • User interaction logs (clicks, accepts) - real-time
  • User profile data (age, location, interests) - updated daily
  • Existing user connections (graph edges) - updated in real-time
  • User activity data (posts, likes) - updated daily
🏷️
Data Properties
Labeling Strategy

Implicit feedback from user actions (clicks and accepts) on suggestions.

Data Volume

Approximately 500 million rows/day, 10 TB/month.

Freshness

Features should be updated in real-time to T-1 day to capture recent user activity.

⚠️
Data Challenges
  • Sparse labels due to low acceptance rates
  • Cold start for new users with no connections
  • Survivorship bias in active user data
  • Position bias in suggestion lists
🔧
Key Features
numerical
Common connections
Indicates potential mutual interests.
numerical
User activity level
Active users are more likely to accept suggestions.
embedding
Profile similarity
Captures shared interests or demographics.
categorical
Interaction history
Past interactions can predict future behavior.
numerical
Graph centrality
Users with high centrality are more influential.
⚡
Feature Engineering Notes
Real-time vs Batch

Real-time computation for user activity level and interaction history; batch for profile similarity and graph centrality.

Feature Store

Required

🐍
Feature Snippet
Python
def compute_common_connections(user_a, user_b, graph):
    return len(set(graph.neighbors(user_a)) & set(graph.neighbors(user_b)))
🤖
Model Selection
Baseline

Popularity-based model suggesting connections based on mutual friends.

Proposed Model

Graph Neural Network (GNN) for link prediction.

GNNs effectively capture complex graph structures and node interactions, crucial for predicting potential connections.
✗
Alternatives Rejected
Collaborative Filtering: Fails to capture graph structure and user-item interactions.
XGBoost: Cannot efficiently handle graph data and requires feature engineering that misses relational information.
🏋️
Training Strategy

Offline training with periodic updates to incorporate new user data and interactions.

🚀
Serving Infrastructure
LatencyP99 < 100ms end-to-end for generating suggestions.
ThroughputTarget of 10,000 QPS to handle peak loads.
ArchitectureTwo-stage (retrieval + ranking) to efficiently narrow down potential connections before detailed ranking.
CachingCache top suggestions for each user with a TTL of 1 hour to reduce computation load.
FallbackRule-based fallback using mutual friends if the model is unavailable.
📡
Data Drift Signals
Shift in user activity distribution
Change in graph structure (e.g., average degree)
Variation in profile similarity scores
📉
Model Drift Signals
Decrease in Precision@K
Drop in CTR for suggestions
Shift in prediction score distribution
🔔
Alerting & Retraining
Retraining Trigger

Precision@K drops below 0.7 or CTR decreases by 10% over a week.

Alerting Strategy

On-call alerts for significant metric drops, automated logs for data drift, and auto-recovery scripts for minor issues.

🎯
Interview Angles
  • How to handle cold start for new users?
  • Balancing precision and recall in recommendations.
  • Handling data privacy and compliance in user data.
⚠️
Common Mistakes
Ignoring the cold start problem for new users.
Overlooking the importance of real-time data updates.
Failing to justify the choice of graph-based models.
Neglecting to address latency and throughput constraints.
📌
Key Decisions
  • Choosing GNNs for their ability to model graph structures.
  • Implementing a two-stage serving architecture for efficiency.
  • Balancing real-time and batch feature computation for freshness.

Practice

(1/5)
1. In the context of a Guardrails System for LLMs, which component is primarily responsible for detecting inappropriate content in user-generated text?
easy
A. Data augmentation module
B. Content filtering module
C. Model training module
D. User feedback loop

Solution

  1. Step 1: Identify the role of each component

    The content filtering module is designed to detect and filter inappropriate content.

  2. Step 2: Eliminate wrong options

    Data augmentation is for enhancing training data, model training is for learning patterns, and user feedback loop is for improving system iteratively.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Content filtering detects inappropriate content. [OK]
Hint: Content filtering detects inappropriate content. [OK]
Common Mistakes:
2. For a two-stage retrieval system, which metric is most appropriate to evaluate the candidate generation stage?
easy
A. Precision
B. Mean Reciprocal Rank
C. F1 Score
D. Recall

Solution

  1. Step 1: Identify the goal of candidate generation

    The goal is to ensure relevant items are included, making recall a critical metric.

  2. Step 2: Eliminate wrong options

    Precision (Precision) is less critical here as it focuses on the proportion of relevant items retrieved. F1 Score (F1 Score) balances precision and recall, but recall is more crucial. Mean Reciprocal Rank (Mean Reciprocal Rank) is more relevant for ranking evaluation.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Recall ensures relevant items aren't missed. [OK]
Hint: Recall ensures relevant items aren't missed. [OK]
Common Mistakes:
3. In a feed ranking system, should you prioritize using collaborative filtering or content-based filtering when user data is sparse?
medium
A. Collaborative filtering, because it leverages user interactions
B. Content-based filtering, because it relies on item features
C. Collaborative filtering, because it scales better with more users
D. Content-based filtering, because it requires less computational power

Solution

  1. Step 1: Analyze data sparsity

    When user data is sparse, collaborative filtering struggles due to lack of interaction data.

  2. Step 2: Eliminate wrong options

    Collaborative filtering needs user interactions. Content-based filtering uses item features, making it suitable for sparse data.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Content-based works with sparse data. [OK]
Hint: Content-based works with sparse data. [OK]
Common Mistakes:
4. When choosing between a Bi-Encoder and a Cross-Encoder for a semantic search task, which is more suitable for real-time retrieval and why?
medium
A. Bi-Encoder, because it allows pre-computation of document embeddings
B. Cross-Encoder, because it can handle large datasets efficiently
C. Cross-Encoder, because it provides higher accuracy by evaluating pairs
D. Bi-Encoder, because it requires less computational power during retrieval

Solution

  1. Step 1: Compare Bi-Encoder and Cross-Encoder

    Bi-Encoders allow pre-computation of document embeddings, making them suitable for real-time retrieval.

  2. Step 2: Eliminate wrong options

    Cross-Encoders evaluate pairs at query time, which is computationally expensive and not suitable for real-time retrieval.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Bi-Encoder = pre-compute embeddings [check]
Hint: Bi-Encoder = pre-compute embeddings [check]
Common Mistakes:
5. As the number of items to rank increases significantly, which component of a listwise ranking system is most likely to become a bottleneck?
hard
A. Memory usage for storing item lists
B. Feature extraction process
C. Model training time
D. Evaluation metric computation

Solution

  1. Step 1: Identify the component affected by increased item count.

    Listwise approaches require more computation as the list size grows, impacting training time.

  2. Step 2: Eliminate wrong options.

    Feature extraction and memory usage are affected but not as critically as training time. Evaluation metrics are computed post-training.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Listwise = training time bottleneck with more items [OK]
Hint: Listwise = training time bottleneck with more items [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard