Beyond Direct Neighbors: Enhancing Recommendations via Influence Propagation

TL;DR

Recommender systems often operate on the naive assumption that your preferences are only shaped by your immediate friends. This paper challenges that by introducing Threshold-Bounded Influence Propagation (TB-IP). By modeling how influence decays across multiple "hops" in a social graph, the authors created personalized user neighborhoods that significantly boost the accuracy of Matrix Factorization-based recommendations compared to traditional rating-only methods.

The "Weak Ties" Motivation

Why do we care about friends of friends? The authors draw on Granovetter’s classic sociological concept of the "strength of weak ties"—the idea that acquaintances often provide more novel and impactful information than close friends.

Current social recommenders (SOTA) usually stop at one hop. The difficulty lies in cascading: How do you measure influence when it travels from User A to B to C? If you don't account for the loss of signal (decay), your model will eventually assume every node influences every other node, leading to "neighborhood explosion" and noisy data.

Methodology: The Mechanics of Influence

The authors treat the social network as a weighted-directed graph $G=(V,E,W)$. The core innovation lies in three specific areas:

1. The Hopping Factor (Decay)

To prevent infinite propagation, the authors introduce a decay mechanism. The influence at a specific hop distance is calculated as: $hopping\_factor=1+hopimesdecay$ As the number of hops increases, the required threshold for a node to be "activated" becomes harder to reach, simulating the natural dilution of trust through intermediaries.

2. Vertex-Specific Thresholding

Unlike previous models that use a global threshold, this paper proposes EWThr (Edge-Weight Dependent Threshold). For every node $u$, the threshold for it to be influenced is the average of its own outgoing edge weights. This makes the "persuadability" of a user depend on their own social activity and structural position.

3. The TB-IP Algorithm

The algorithm functions as a sophisticated pre-processing step for Collaborative Filtering. It ranks nodes (using PageRank or Out-degree), picks the top seeds, and recursively adds influenced nodes into a neighborhood until the decay makes further propagation impossible.

Fig 1: The two-step process: Generating neighborhoods via influence propagation before feeding them into the recommendation engine.

Experimental Analysis

The authors tested their approach on three major datasets: AstroPhysics, Epinions, and Yelp.

Network Coverage

The "Min-Max" goal was to cover the most nodes with the fewest seeds. The EWThr strategy consistently reached 80-100% coverage, proving far more efficient than a static global threshold (AvgThr), which often stalled because it didn't account for local graph density.

Recommendation Accuracy

Using the Yelp Las Vegas dataset, the authors compared their socially-pruned neighborhoods against random baselines and the full dataset (BaseAll).

The results in Table III clearly show that the Vertex-Specific Threshold (EWThr) provides the most signal-to-noise ratio, resulting in the lowest Root Mean Square Error (RMSE).

Fig 2: Coverage performance on AstroPhysics - tracking how many influencers are needed to reach the network.

Critical Insight & Future Work

The primary takeaway is that social structure is a filter. By using influence propagation as a pre-processing step, we can prune irrelevant data and focus the Matrix Factorization on "socially relevant" users.

However, the paper acknowledges a current limitation: the social data is currently a pre-step. The authors' future roadmap involves integrating this influence propagation directly into the loss function of the recommender as a social regularization term, potentially allowing for end-to-end training of influence and preference.

Conclusion

Avni Gulati and Magdalini Eirinaki have demonstrated that "who you know" and "who they know" matters significantly in predictive modeling. By mathematically grounding the decay of influence, they provide a robust framework for building social recommenders that actually respect the nuances of human interaction.