C2P: Bridging the Gap in Cross-layer Social Recommendations

TL;DR

Modern social networks are rarely flat; they consist of multiple layers representing different connection types. Most recommendation systems, however, treat these layers in isolation. The Cross-layer 2-hop Path (C2P) algorithm changes this by identifying "cross-layer neighbors"—people connected through a sequence of different relationship types (e.g., a "friend of a colleague"). This approach yields a 38% improvement in recommendation acceptance while maintaining high efficiency.

Problem & Motivation: The Single-Layer Trap

In an academic network, you might connect with someone because you co-authored a paper (collaboration layer) or because you share a research interest (topic layer). Existing systems typically pick one layer or provide a "Mixed" list (half from layer A, half from layer B).

The authors argue that this is fundamentally flawed. User demand is not a simple addition; it is an instinct combination. A simple mixture results in information loss because it fails to capture the synergy between layers. The core challenge: How can we mathematically model and algorithmically extract this synergy?

Methodology: The Power of Heterogeneous Paths

The C2P algorithm is built on the intuition that a user $v$ is interested in a candidate $u$ if they are linked through "cross-layer two-hop paths."

1. The Cross-layer Path Definition

A path $vowou$ is considered "cross-layer" if:

• Step 1 is in Layer 1 (e.g., Paper-based) AND Step 2 is in Layer 2 (e.g., Topic-based).
• OR vice versa.

2. Implementation Efficiency

The algorithm utilizes a flooding method to count these specific paths. Despite the seemingly complex search, the authors prove that if the average node degree is constant, the complexity is $\Theta (1)$, making it highly scalable for real-world social graphs.

Fig 1: The implementation of C2P. Note how node $u_2$ is prioritized because it connects to $v$ via two distinct cross-layer paths.

Theoretical Rigor: Why It Works

The paper doesn't just show that it works; it proves why. By extending the Affiliation Network Model, the authors derive the probability of connection.

They prove two landmark theorems:

• Optimality in Acceptance: C2P aligns perfectly with the formulated "User Demand" probability, meaning it provides the most "accurate" friends according to the modeled human behavior.
• Diversity bound: The aggregate diversity remains $\Theta (n)$, ensuring the algorithm doesn't just recommend the same "celebrity" nodes to everyone.

Experiments & Results

The authors tested C2P against FOF-P (Paper-only), FOF-T (Topic-only), and MIX (a linear combination).

Fig 2: Acceptance performance. C2P (top line) consistently outperforms all baselines across different years and network sizes.

Key Findings:

• Higher Precision: C2P achieved up to 38% gain in acceptance in the Machine Learning dataset.
• Scalability: Even as the network size grew over the test years (1955–1975), the performance gap between C2P and baselines remained significant.

Critical Analysis & Conclusion

C2P is a elegant solution to the multi-relational recommendation problem. Its strength lies in its probabilistic manner, providing theoretical tractability that many "black-box" Deep Learning models lack.

Limitations:

• The model currently assumes a two-layer structure. Expanding this to $N$-layers might introduce exponential path growth.
• The "User Demand" model, while mathematically sound, is a simplified proxy for actual human social psychological factors.

Future Outlook: This work paves the way for "Multi-hop Heterogeneous Recommendations." As we move towards more complex "Metaverse" social structures where users interact via VR, text, and shared digital assets, algorithms like C2P will be essential to provide a unified, intuitive social experience.