and 3.5(b)) that are defined based on the heterogeneous type schema (Figure
3.3(a) and 3.5(a)). Our experimental results comparing our framework InfoMotif
with baselines on DBLP and Movie networks, are shown in Table 3.6.

We find that message-passing GNNs (such as GCN, GAT) generally outperform
conventional embedding methods (such as node2vec). Structural embedding
methods (e.g., struc2vec) perform poorly; this reveals their inability to
capture structural aspects relevant to heterogeneous graphs with rich type
semantics. Heterogeneous GNNs such as MAGNN and Meta-GNN outperform
homogeneous GNNs owing to their type-aware semantic neighbor aggregation via
metapaths and metagraphs respectively. Our framework InfoMotif further learns
type-aware attributed structural roles which results in significant
performance gains of 5% on average over prior approaches.

Dataset |  Cora |  Citeseer |  Pubmed
---|---|---|---
InfoMotif-GCN ($L_{S}+\lambda L_{MI}$) |  87.4 $\pm$ 0.4 |  78.5 $\pm$ 0.5 |  88.3 $\pm$ 0.2
w/o novelty weights ($\beta_{v}=1$ in eq. 3.9) |  86.4 $\pm$ 0.5 |  77.6 $\pm$ 0.5 |  87.8 $\pm$ 0.3
w/o task weights ($\alpha_{vt}=1$ in eq. 3.7) |  84.6 $\pm$ 0.4 |  77.3 $\pm$ 0.4 |  87.3 $\pm$ 0.2
w/o novelty and task weights |  84.0 $\pm$ 0.5 |  76.4 $\pm$ 0.6 |  87.3 $\pm$ 0.2
Base model GCN ($L_{B}$) |  82.0 $\pm$ 0.4 |  76.6 $\pm$ 0.3 |  86.1 $\pm$ 0.5
Table 3.7: Ablation study results with 40% training ratio on citation
networks. The novelty and task weighting strategies improve classification
accuracies by 2% on average.

####  3.5.6 Model Ablation Study ($\text{RQ}_{3}$)

We present an ablation study on two citation networks Cora and Citeseer, to
analyze the importance of major components in InfoMotif (Table 3.7). In our
experiments, we choose GCN as the base GNN model due to its consistently high
performance.

  * •

Remove novelty-driven sample weighting. We set the novelty weight
$\beta_{v}=1$ (Equation 3.9) for each labeled node $v\in{\mathcal{V}}_{L}$ to
test the importance of addressing motif occurrence skew. We observe consistent
1% gains due to our novelty-driven sample weighting.

  * •

Remove task-driven motif weighting. We remove the node-sensitive motif weights
from the motif regularization loss (Equation 3.7) by setting $\alpha_{vt}=1$
for every node-motif pair. Contextually weighting the different motif
regularizers at a node-level granularity results in 2% average accuracy gains
across both datasets.

  * •

Remove both novelty and task driven weighting. This variant applies a uniform
motif regularization over all nodes without distinguishing the node-sensitive
relevance of each motif; this significantly degrades classification accuracy.

####  3.5.7 Qualitative Analysis ($\text{RQ}_{4}$)

We qualitatively examine the source of InfoMotif’s gains over the base GNN
(GCN due to its consistent performance). by analyzing node degree, label
sparsity and attribute diversity in local node neighborhoods, on the Cora and
Citeseer networks.

##### Node Degree

To evaluate performance variance with node degree, we divide the set of test
nodes into bins based on four degree ranges. Figure 3.6 depicts the variation
in classification accuracy for GCN and InfoMotif-GCN across degree segments,
on Cora and Citeseer datasets.

Figure 3.6: Classification accuracy with respect to node degree. InfoMotif has
consistent gains across all segments with higher gains for low-to-medium
degree nodes (quartiles Q1 & Q2).

InfoMotif has consistent performance improvements over GCN across all degree
segments, with notably higher gains for low-to-medium degree nodes (quartiles
Q1 and Q2). Learning structural roles through self-supervised motif
regularization is beneficial for nodes with limited local structural
information.

##### Label Sparsity

We define the label fraction for a node as the fraction of labeled training
nodes in its 2-hop neighborhood, i.e., a node exhibits label sparsity if it
has very few or no labeled training nodes within its 2-hop aggregation range.
We separate the set of test nodes into four quartiles by their label fraction.
Figure 3.7 depicts classification results for GCN and InfoMotif-GCN under each
quartile (Q1 has nodes with small label fractions).

Figure 3.7: Classification accuracy over label fraction quartiles. (Q1:
smaller label fraction). InfoMotif has larger gains over GCN in Q1 & Q2 (nodes
that exhibit label sparsity)

InfoMotif has stronger performance gains over GCN for nodes with smaller label
fractions (quartiles Q1 and Q2); this empirically validates the efficacy of
our motif-based regularization framework in addressing the key limitation of
$k$-hop localization in message-passing GNNs (Section 3.3.1), i.e., InfoMotif
benefits nodes with very few or no labeled nodes within their $k$-hop
aggregation ranges, thus effectively addressing label sparsity challenges.

##### Attribute Diversity

We measure the local attribute diversity of a node by the mean pair-wise
attribute dissimilarity (computed by cosine distance) of itself with other
nodes in its 2-hop neighborhood, i.e., a node that exhibits strong homophily
with its neighbors has low attribute diversity. We report classification
results across attribute diversity quartiles in Figure 3.8.

Figure 3.8: Classification accuracy across attribute diversity quartiles. (Q4:
high attribute diversity). InfoMotif has stronger gains in Q3 & Q4 (nodes with
diverse attributed neighborhoods).

Nodes with diverse attributed neighborhoods are typically harder examples for
classification. Regularizing GNNs to learn attributed structures via motif
occurrences can accurately classify diverse nodes, as evidenced by the higher
relative gains of InfoMotif for diverse nodes (quartiles Q3 and Q4).

####  3.5.8 Parameter Sensitivity

We examine the effect of hyper-parameter $Q$ that controls the number of motif
instances sampled per node to train our motif-based discriminators (Equation
3.4). Figure 3.9 shows variation in accuracies of our three GNN variants with
the number of sampled instances (5 to 30), on Cora and Citeseer networks.

Figure 3.9: Classification accuracy increases slowly with the number of
sampled motif instances and stabilizes around 15 to 20. Variance bands
indicate 95% confidence intervals over 10 runs.

Performance of all GNN variants stabilize with 20 instances across both
datasets. Since the complexity of our framework scales linearly with $Q$, we
fix $Q=20$ across datasets to provide an effective trade-off between compute-
cost and performance

####  3.5.9 Efficiency Analysis

We empirically evaluate the added complexity of InfoMotif on two GNN models,
GCN and GAT. We report the time per epoch on synthetically generated Barabasi-
Albert networks [1] with 5000 nodes and increasing link density (Figure 3.10).

InfoMotif adds a small fraction of the base GNN runtime, and the added
complexity scales linearly with the number of nodes, as evidenced by its
nearly constant runtime gap over increasing link density (Figure 3.10).
Furthermore, our GCN variant InfoMotif-GCN is significantly more efficient
than GAT.

Figure 3.10: Runtime comparison of InfoMotif variants with its base GNNs.
InfoMotif has minimal computational overheads; notice the nearly constant
runtime gap with increasing node degree.

###  3.6 Discussion

Our framework is designed to address the limitations of oversmoothing and
localization in prior message-passing GNNs.

InfoMotif is orthogonal to advances in GNN architectures that improve the
structural distinguishability of node representations through carefully
designed neighborhood aggregators. In contrast, we enhance the structural
resolution of node representations by regularizing base GNNs through self-
supervised learning objectives designed to capture connectivity in higher-
order motif structures. By training contrastive discriminators to discover
attribute correlations among motif instances across the entire graph, our
approach learns generalizable global roles in addition to modeling local
connectivity patterns. The enhanced quality of our learned node
representations is further evidenced by our superior empirical performance for
nodes with diverse attributed neighborhoods (Section 3.5.7).

InfoMotif addresses the challenge of localization by regularizing base GNNs to
learn attributed structural roles through self-supervised training objectives.
Specifically, our approach statistically relates distant nodes in the graph
with co-varying attributed structures, to effectively overcome label sparsity
in local neighborhoods (Section 3.5.7). Instead of adopting deeper GNNs that
directly expand neighborhood aggregation ranges, we demonstrate the
effectiveness of regularizing shallow base GNNs to learn attributed structural
roles. Compared to deeper GNNs that scale poorly with neighborhood sizes, our
regularization strategy enables efficient model inference.

In our work, we choose network motif structures as the central basis to
formulate structural roles. In contrast to alternative approaches to quantify
structural similarity based on coarse properties like degree sequences [24] or
rigid notions of structural equivalence [22], network motifs are fundamental
higher-order connectivity structures that enable flexible generalization to
complex heterogeneous graphs with rich semantics. We empirically demonstrate
the utilities of untyped motifs in homogeneous graphs and typed motifs in
heterogeneous graphs.

Our key modeling hypothesis is the importance of attribute co-variance in
local structures towards the learning application (e.g., classification in
social networks). Our substantial gains on two diverse classes of datasets
indicates broad applicability for InfoMotif across graphs with varied
structural characteristics. However, the performance gains may diminish in
application scenarios (e.g., learning in regular mesh graphs) where modeling
such co-variance is not beneficial or even necessary.

###  3.7 Related Work

Our work is related to semi-supervised learning approaches over homogeneous
and heterogeneous graphs, and recent advances in the paradigm of self-
supervised learning.

Homogeneous Graphs: Semi-supervised learning over graphs is a well-studied
problem, where the goal is to classify nodes in a graph given a small set of
labeled examples. The most popular label spreading [32] techniques propagate
labels through linked nodes in the graph based on smoothness assumptions.
Graph Neural Networks (GNNs) generalize label spreading through localized
message passing over feature-rich node neighborhoods and have achieved state-
of-the-art results in several benchmarks [39]. GNNs learn node representations
by recursively aggregating features from local neighborhoods in an end-to-end
manner, with diverse applications, including information diffusion prediction
[179], social recommendation [180], and community question answering [181].
Graph Convolutional Networks (GCNs) [39] learn degree-weighted aggregators,
which can be interpreted as a special form of Laplacian smoothing [155]. Many
models generalize GCN with a wide range of neighborhood aggregators, e.g.,
self-attentions [40, 68], mean and max pooling functions [41], etc. However,
all these models learn node representations that inherently overfit to the
$k$-hop neighborhood around each node.

There are two broad categories of prior graph representation learning
approaches that aim to overcome the key limitations of oversmoothing and
localization in GNNs: non-local GNNs that capture contributions from distant
nodes in the graph; and structural role learning techniques that enhance the
structural distinguishability of the learned node representations.

Non-local methods expand the propagation range of GNNs to aggregate node
representations of differing localities, e.g., JKNet [42] uses skip-
connections to vary the influence radius per node, PGNN [43] captures global
network positions via shortest-paths, and DGI [44] maximizes MI between node
representations and a summary representation of the entire graph. However,
they either operate on a local scale [182], or learn coarse structural
properties, which limits their ability to capture features from distant yet
structurally similar nodes.

Role-aware models embed structurally similar nodes close in the latent space,
independent of network position [23, 22]. A few approaches [177] employ strict
definitions of structural equivalence to embed nodes with identical local
structures to the same point in the latent space, while others utilize
structural node features (e.g., node degrees, motif count statistics) to
extend classical proximity-preserving embedding methods, e.g., feature-based
matrix fa ctorization [25] and random walk methods [24]. Notably, a few
methods design structural GCNs via motif adjacency matrices [47, 46, 58].
However, all these methods model structural roles without considering node
attributes. A related direction is higher-order network representation
learning that models proximity via network motifs [175]. However, such
representations are highly localized and cannot identify structurally similar
nodes independent of network proximity. In contrast, we regularize GNNs to
learn attributed structural roles based on the co-variance of attributes in
motifs, thus simultaneously enhancing the distinguishability of node
representations and identifying correspondences between distant nodes.

Heterogeneous Graphs: Representation learning techniques over heterogeneous
graphs primarily focus on preserving structural information indicated by the
type semantics in meta-path or meta-graph structures. A few popular approaches
include node representation learning by capturing proximities between node
pairs connected via meta-graphs [49, 50] and meta-path guided random walks
[51, 52]. Recently, graph neural networks have been generalized to
heterogeneous graphs through message passing aggregation over local
neighborhoods induced via specific node types [53, 54], meta-paths [55, 56,
57] and meta-graphs [58]. While these advances effectively incorporate rich
heterogeneous semantics into message-passing GNNs, the key limitation due to
localization remains. To our knowledge, structure role learning in
heterogeneous graphs is unexplored and ours is the first to examine structural
role learning in GNNs with rich type semantics and attributes.

Self-supervised Learning: The emerging paradigm of self-supervised learning
[144] aims to alleviate the need for large volumes of labeled examples by
extracting supervision signals from the intrinsic structure of the raw data.
For instance, auxiliary supervision signals for images are created by
rotating, cropping and colorizing images, followed by new training objectives
to facilitate representation learning [183]. One empirically effective
strategy is mutual information maximization [184] to maximize agreement across
different views of the data. A few recent advances extend self-supervised
learning to graph representation learning by exploiting structural properties
such as node degree, proximity [185], and attributes [186], for model pre-
training [187, 188, 189]. In our work, we design self-supervised learning
objectives to regularize graph neural networks for node classification by
learning attribute correlations in higher-order connectivity patterns (typed
and untyped motif structures).

###  3.8 Conclusion

This chapter presents a new class of motif-regularized GNNs with an
architecture-agnostic framework InfoMotif for semi-supervised learning on
graphs. To overcome limitations of prior GNNs due to localized message
passing, we introduce attributed structural roles to regularize GNNs by
learning statistical dependencies between structurally similar nodes with co-
varying attributes, independent of network proximity. InfoMotif maximizes
motif-based mutual information, and dynamically prioritizes the significance
of different motifs. Our experiments on nine real-world datasets spanning
homogeneous and heterogeneous networks, show substantial consistent gains for
InfoMotif over state-of-the-art methods.

In this chapter, we have explored a transductive learning scenario of semi-
supervised learning over graph-structured entity interactions given sparse
training labels. We leveraged higher-order connectivity structures (network
motifs) between nodes to compensate for the lack of sufficient labeled
information in the local neighborhoods. In the next chapter, we examine
another central transductive scenario of collaborative filtering in the
bipartite user-item interaction setting. Our key focus is to enable accurate
personalized recommendations for data-poor tail entities (such as long-tail
items) with severe interaction sparsity.

##  Chapter 4 ProtoCF: Few-shot Collaborative Filtering via Meta-Transfer

###  4.1 Introduction

Neural Collaborative Filtering (NCF) methods have recently enabled substantial
advances in modern recommender systems that are critical to diverse e-commerce
applications. Collaborative Filtering (CF) methods generate personalized
recommendations by learning patterns from historical user-item interactions.
However, a close examination of neural recommenders’ performance reveals a
paradox: while the overall recommendation accuracy is high, accuracy levels
are poor for most items in the inventory. A majority of recommendations are
biased towards popular items [2], while ignoring long-tail items in under-
represented categories. Popularity bias restricts personalization and impedes
suppliers of long-tail items, who struggle to attract consumers given the low
exposure. Targeting long-tail items can enhance recommendation diversity and
bring relatively larger marginal profits, compared to popular items with
competitive markets. The increasing impact of recommendations (e.g., 80% of
Netflix activity is a result of recommendations [190]), also raises ethical
questions: can items that are never recommended by a system be considered an
instance of discrimination [191]? Thus, we focus on learning robust models for
long-tail item recommendations.

Empirical evidence of long-tail challenges: We highlight two key observations
on prior neural recommendation models [88, 90, 89]:

Figure 4.1: Item Recall@50 of three popular neural recommendation models
across different item-groups (increasing popularity) in Epinions. Neural
recommenders overfit to popular items with considerably lower performance for
long-tail items.

  * •

Performance gains are skewed towards popular items with abundant historical
interactions. Figure 4.1 depicts Item Recall$@K$ (fraction of correctly ranked
items within top-$K$) of three neural recommenders for different item-groups
ordered by increasing item interaction count. Model performance is
considerably lower for long-tail items (low popularity), indicating a clear
popularity bias.

  * •

Prior recommenders lack the resolution power to accurately rank relevant items
within the long-tail. To empirically illustrate this observation, we split the
item inventory into two equal-sized sets by interaction count (popular and
long-tail), and evaluate personalized ranking performance independently within
each set. Table 4.1 shows a big performance gap between ranking within the
popular and long-tail item sets, which reflects on the poor quality of their
long-tail item representations.

Item Subset | Top 50% Items | Bottom 50% Items
---|---|---
Metric |  N@50 |  R@50 |  N@50 |  R@50
NCF [88] |  0.0906 |  0.1874 |  0.0352 |  0.0973
VAE-CF [90] |  0.1055 |  0.2106 |  0.0457 |  0.1125
CDAE [89] |  0.1050 |  0.2102 |  0.0471 |  0.1149
Table 4.1:  Recommendation performance within top-50% head and bottom-50% tail
items (ordered by item popularity) on Epinions. R@50 and N@50 denote Recall@50
and NDCG@50 metrics respectively. Compared to head items, we observe poor item
ranking resolution within the long-tail.

Prior efforts towards the long-tail have been two-fold. First, regularizing an
existing recommender via inter-item associations (derived from item co-
occurrences) [192, 193, 194, 9] or distributional priors over the latent space
[90, 98]. While regularization strategies can partially alleviate overfitting,
they typically involve static hypotheses that may be counter-productive for
massive item inventories with a diverse collection of long-tail items. Second,
incorporating external side information [103], e.g., item attributes [195],
social networks [106], and knowledge graphs [107] to overcome interaction
sparsity. Note that exploiting side information is typically application-
dependent, thus lacking generalizability to diverse scenarios. In contrast, we
exploit the capabilities of any neural base recommender for long-tail item
recommendation without any requirement of side information.

Learning a latent space tailored to long-tail items poses two key challenges:
first, sparsity and heterogeneity: although tail items have sparse
interactions, they belong to diverse item categories, e.g., Figure 4.2 shows
long-tailed distributions along different dimensions described by item
attributes, location and category of Yelp businesses. Thus, we need sufficient
resolution power to learn discriminative representations for tail items, while
being careful to avoid overfitting. Second, distribution mismatch between head
items (substantial interactions) and tail items (sparse interactions).
Specifically, neural recommenders typically sample user-item pairs from the
overall interaction distribution (biased to head items) for model training;
this results in overfitting and degenerate representations for tail items.

Present Work: To overcome item interaction sparsity, we extract, relate, and
transfer the knowledge learned by a neural base recommender over head items,
to learn robust and discriminative tail item representations. We eliminate the
distribution inconsistency between head and tail items with an episodic few-
shot learning setup [151] to simulate the distribution of tail items during
model training by sub-sampling interactions from data-rich head items.

Figure 4.2: Multiple long-tailed distributions along different item
dimensions. (a) shows interaction frequency distribution over unique items.
(b) and (c) show frequency distributions over unique cities and categories of
Yelp businesses.

In this work, we present a novel metric-based few-shot learning framework
ProtoCF for long-tail item recommendation. First, we pretrain a base
recommender to extract preferences over head items and item-item
relationships. Then, we design a few-shot recommender that learns a shared
metric space of users and items by extracting meta-knowledge across a
collection of meta-training tasks designed to mimic long-tail item
recommendation. ProtoCF learns-to-compose a representative prototype for each
item from a small set of user interactions and recommends relevant items by
finding the nearest item prototypes to each user. To transfer knowledge from
the base recommender, we introduce a knowledge distillation strategy to
distill the discovered item-to-item relationships into a compact set of group
embeddings; we compose discriminative item prototypes via learnable mixtures
of group embeddings. We summarize our key contributions below:

Few-shot Item Recommendation: To our knowledge, ours is the first to formulate
long-tail item recommendation as learning-to-recommend items with few
interactions. We eliminate the distribution mismatch between head and tail
items via episodic few-shot learning. Our problem formulation applies to
diverse recommendation scenarios without requiring any auxiliary side
information.

Discriminative Prototype Learning: We learn to compose discriminative
prototypes for tail item only from their sparse user interactions. Unlike
prior gradient based meta-learning for cold-start recommendation scenarios
[110, 112, 111], we learn a metric space where the item prototypes directly
cluster the interacted users in a metric space, which further eliminates
expensive online adaptation costs.

Architecture-agnostic Knowledge Transfer: We enhance item prototypes by
knowledge transfer from neural base recommenders. In contrast to layer
transfer or adaptation methods [105], our knowledge distillation strategy
extracts a compact representation of the item relationships discovered by
arbitrary base recommenders. Significantly, ProtoCF is complementary to
architectural advances in neural base recommenders and enables flexible
adaptation to items in the long tail.

We instantiate ProtoCF by transferring meta-knowledge from three base
recommenders. Our experiments show that ProtoCF outperforms state-of-the-art
baselines (by 5% Recall@50) in overall recommendation, with notably
significant few-shot gains (of 60-80% Recall@50) on tail items with less than
20 training interactions.

We organize the rest of the chapter as follows. In Section 4.2, we formally
define the problem of long-tail item recommendation. In Section 4.4, we first
outline the components of a neural base recommender, and then introduce our
proposed framework ProtoCF for few-shot item recommendation. We then present
our experimental results in Section 4.5, and finally conclude in Section 4.6.

###  4.2 Problem Definition

We consider the implicit feedback setting (only clicks, no explicit ratings)
with a user set ${\mathcal{U}}=\\{u_{1},\dots,u_{U}\\}$, an item set
${\mathcal{I}}=\\{i_{1},\dots,i_{I}\\}$, and a binary $U\times I$ user-item
interaction matrix ${\bm{X}}$. Let $N_{i}$ denote the set of all users who
have interacted with item $i\in{\mathcal{I}}$. Prior neural recommenders learn
a scoring function $f(i\mid u,{\bm{X}}),i\in{\mathcal{I}}$ personalized to
each user $u\in{\mathcal{U}}$ for item ranking over the item set
${\mathcal{I}}$. From Table 4.1, we find their performance for tail items
(bottom 50%) to be considerably inferior to head items (upper 50%). Thus, our
focus is to develop personalized recommenders tailored to the long-tail items
(with sparse interactions), while ensuring reasonable performance over the
entire item set ${\mathcal{I}}$.

######  Problem 4.1 (Long-Tail Item Recommendation).

Given user-item interaction matrix ${\bm{X}}$, learn a scoring function
$f_{T}(i\mid u,{\bm{X}}),i\in{\mathcal{I}}$ to generate a ranked list of items
personalized to each user $u\in{\mathcal{U}}$ that improves recommendation
quality on the long-tail items without compromising overall model performance
on the entire item set ${\mathcal{I}}$.

Symbol | Description
---|---
$p_{B}(i,j)$ | proximity induced by ${\bm{R}}_{B}$ for items $i,j\in{\mathcal{I}}$
$p({\mathbb{T}})$ | meta-training task distribution over items ${\mathcal{I}}$
${\mathcal{T}}$ | meta-training task sampled from $p({\mathbb{T}})$
${\mathcal{I}}_{{\mathcal{T}},N}$ | set of $N$ items sampled from ${\mathcal{I}}$ for task ${\mathcal{T}}$
${\mathcal{S}}_{i}$ | support set for item $i\in{\mathcal{I}}_{{\mathcal{T}},N}$ in task ${\mathcal{T}}$
${\mathcal{Q}}_{i}$ | query set for item $i\in{\mathcal{I}}_{{\mathcal{T}},N}$ in task ${\mathcal{T}}$
$G_{U}(\cdot\mid\theta)$ | user encoder in few-shot recommender ${\bm{R}}_{F}$
${\mathcal{Z}}_{M}$ | set of $M$ group embeddings $\\{{\mathbf{z}}_{m}\in{\mathbb{R}}^{D}\\}_{m=1}^{M}$
$\text{sim}_{m}$ | similarity metric for meta-recommender ${\bm{R}}_{F}$
${\mathbf{p}}_{i}$ | initial item prototype for item $i\in{\mathcal{I}}$
${\mathbf{g}}_{i}$ | group-enhanced item prototype for item $i\in{\mathcal{I}}$
${\mathbf{e}}_{i}$ | final gated item prototype item for item $i\in{\mathcal{I}}$
Table 4.2: Notations

###  4.3 Related Work

We briefly review a few related lines of prior work on neural collaborative
filtering and long-tail item recommendations with interaction sparsity.

Neural Collaborative Filtering: The core paradigm of latent-factor CF models
is to parameterize users and items with latent representations learned from
historical user-item interactions. Recent neural recommenders enhance the
representational capacity of CF models via non-linear latent representations
[89, 90], neural interaction modeling [88, 94], and graph-based representation
learning [91]. While these neural recommenders learn expressive models to
significantly outperform conventional CF approaches, sparsity concerns owing
to long-tail items remain a critical challenge.

Sparsity-aware Recommendation: Clustering is one popular way to address
interaction sparsity by modeling group-level purchasing behaviors; early
methods generate recommendations for tail items at the granularity of item
clusters [95], e.g., cluster-based smoothing [196], user-item co-clustering
[96] and joint clustering and collaborative filtering [97]. However,
clustering in the presence of distributional skew can lead to uninformative
results [197] and degrades the extent of personalization.

Recent techniques leverage item-item co-occurrence statistics and
distributional priors to regularize latent-factor CF methods. One common
approach is regularization of recommendation models, e.g., factorization of an
item co-occurrence matrix that shares latent factors with a CF model [193,
194]. Variational auto-encoders (VAEs) [90, 98, 179] employ multivariate
Gaussian priors as regularizers on the representational space to handle
sparsity. Another strategy to alleviate sparsity is data augmentation for
items (or users) in the tail via adversarial regularization [9] or rating
generation [99, 198] techniques. However, regularization techniques typically
impose static hypotheses with restrictive assumptions, while adversarial
learning is computationally expensive and does not scale to massive item
inventories.

Cold-start recommendation is a related problem that targets new users or new
items with no historical interactions. In such a scenario, models rely on
auxiliary information, e.g., user profiles [110], item content [195], social
connections [106, 171, 199], and knowledge graphs [107]. An effective strategy
is randomized feature dropouts to enable generalization to missing inputs
[108, 109]. In contrast, we focus on few-shot recommendations over long-tail
items with very few interactions, without any auxiliary information.

Few-shot Learning: this learning paradigm involves designing models capable of
learning new tasks rapidly given a limited number of training examples. Here,
the meta-learning (learning to learn) paradigm has achieved considerable
success in several domains including computer vision [100, 101], natural
language [200], and data mining [110, 116].

A few recent methods adapt meta-learning to cold-start recommendation [201].
Prior meta-learning work have examined gradient-based parameter [110, 111,
112, 113, 114] and hyper-parameter initialization [115], and layer sharing
with user-specific (or item) parameter adaptation [116, 117, 118]. However,
these methods mostly address the cold-start (zero-shot) scenario with side
information, thus inapplicable to our general setting of few-shot
recommendation given limited interactions.

Our work is conceptually related to metric-learning approaches [100, 101, 202]
for few-shot learning, which learn-to-learn a metric space that generalizes to
new tasks without any need for adaptation. A few recent explorations address
task heterogeneity [203] in few-shot classification settings, by designing
architectures for explicit knowledge transfer from data-rich classes [204,
205, 206] to construct few-shot classifiers. However, such techniques are
suited to learning classifiers from a limited number of classes, hence cannot
scale to handle massive item inventories in recommendation applications. To
our knowledge, ours is the first investigation of metric-based few-shot
learning for long-tail item recommendations.

###  4.4 ProtoCF Framework

Learning informative representations for tail items poses the key challenge of
interaction sparsity, i.e., each tail item only has a few observed
interactions. Without access to side information (e.g., item content or
contextual attributes), we critically remark that prior neural recommenders
[90, 89] learn informative representations for head items with abundant
training interactions. Thus, to learn discriminative tail item
representations, we propose a novel few-shot learning framework ProtoCF with
two key steps:

First, we train a base recommender ${\bm{R}}_{B}$ to learn high-quality user
representations that mainly capture preferences over head items and infer
item-item relationships (Section 4.4.1). Then, we present a few-shot
recommender ${\bm{R}}_{F}$ that extracts and transfers knowledge from the base
recommender ${\bm{R}}_{B}$ to learn-to-recommend few-shot items (Sections
4.4.2, 4.4.3).

Figure 4.3: Outline of the different components of a neural base recommender
based on collaborative filtering.

####  4.4.1 Neural Base Recommender

In this section, we outline the architecture of a differentiable base
recommender ${\bm{R}}_{B}$ to learn a ranking $f_{\phi}(i\mid
u),i\in{\mathcal{I}}$ (with parameters $\phi$) over the interactions
${\bm{X}}$. Neural CF models [90, 88, 89] typically learn latent
representations for users and items, followed by an interaction function and
learning objective for model training.

##### User and Item Representations

Latent-factor CF methods adopt a variety of representation learning
strategies, including matrix factorization [85, 87], autoencoders [90, 89] and
graph neural networks [91]. We define preference encoders
$F_{U}(\cdot\mid\phi)$ and $F_{I}(\cdot\mid\phi)$ to learn user
${\mathbf{h}}_{u}\in{\mathbb{R}}^{D}$ and item
${\mathbf{h}}_{i}\in{\mathbb{R}}^{D}$ embeddings for user $u\in{\mathcal{U}}$
and item $i\in{\mathcal{I}}$, which can be described by:

${\mathbf{h}}_{u}=F_{U}(u,{\bm{X}}\mid\phi)\hskip
15.0pt{\mathbf{h}}_{i}=F_{I}(i,{\bm{X}}\mid\phi)$ (4.1)

##### Training Objective

We define a user-item interaction function $F_{\textsc{int}}(\cdot\mid\phi)$
to compute a prediction score $\hat{y}_{b}(u,i)$ that indicates the relevance
of item $i$ to user $u$. The training objective $L_{B}$ of the base
recommender ${\bm{R}}_{B}$ is given by:

$\hat{y}_{b}(u,i)=F_{\textsc{int}}({\mathbf{h}}_{u},{\mathbf{h}}_{i}\mid\phi)\hskip
15.0ptL_{B}=l(\hat{y}_{b}(u,i),y_{ui}))$ (4.2)

where $y_{ui}=1$ for observed $(u,i)$ pairs and $l(\cdot)$ is a pairwise [87]
or pointwise [88] loss function. over the user-item interactions. The
interaction function $F_{\textsc{int}}$ measures user-item relevance and is
typically modeled using an inner product [87, 89, 90, 91].

We train the base recommender ${\bm{R}}_{B}$ using cosine similarity since
normalized representations generalize better to few-shot settings [207]
(compared to unnormalized inner products), and facilitate unified
recommendation of head and tail items during model inference. We denote the
item-item proximity $\text{sim}_{b}(\cdot)$ in the latent space of
${\bm{R}}_{B}$ by:

$p_{B}(i,j)\propto\text{sim}_{b}({\mathbf{h}}_{i},{\mathbf{h}}_{j})=\text{cos}({\mathbf{h}}_{i},{\mathbf{h}}_{j})\hskip
15.0pti,j\in{\mathcal{I}}$ (4.3)

We pre-train ${\bm{R}}_{B}$ to extract knowledge of user preferences over head
items via encoder $F_{U}(\cdot)$ and item-item proximities among different
items via $p_{B}(i,j)$. Below, we present our proposed framework ProtoCF that
transfers knowledge from the data-rich head to the data-poor tail to enable
robust few-shot recommendations.

####  4.4.2 Few-shot Item Recommendation

In this section, we formulate long-tail item recommendation as few-shot item
representation learning for items given a small support set of upto $K$
interacted users for each tail item (typically $K\approx 5\text{ to }20$
interactions).

##### Few-shot Task Formulation

Our framework is grounded on episodic learning [100] with a collection of
meta-training tasks or episodes. One approach [101, 207] is to construct meta-
training tasks from the interactions of data-rich head items; however,
excluding the diverse collection of tail items may impede generalization.
Thus, our meta-training tasks operate on the entire item set
${\mathcal{I}}_{T}$.

Figure 4.4: Episodic few-shot learning with meta-training task ${\mathcal{T}}$
and item embedding inference at meta-testing.

Each meta-training task ${\mathcal{T}}$ is a personalized ranking problem over
a subset of $N$ items ${\mathcal{I}}_{{\mathcal{T}},N}$ randomly sampled from
${\mathcal{I}}$. We simulate the interaction distribution of few-shot items
during meta-training by sampling $K$ training interactions (from $N_{i}$) for
each item $i\in{\mathcal{I}}_{{\mathcal{T}},N}$ in task ${\mathcal{T}}$.
During inference, we generate few-shot item recommendations from samples of
upto $K$ training interactions per item. By ensuring consistency between meta-
training and inference, we bridge the distribution mismatch between head and
tail items. The meta-knowledge extracted across diverse meta-training tasks
benefits tail items with sparse interactions.

The episodic few-shot training process operates over a collection of meta-
training tasks $\\{{\mathcal{T}}_{1},{\mathcal{T}}_{2},\dots\\}$ sampled from
a task distribution $p({\mathbb{T}})$ over the item set ${\mathcal{I}}$.
Specifically, a $K$-shot, $N$-item meta-training task ${\mathcal{T}}$ sampled
from $p({\mathbb{T}})$ consists of support ${\mathcal{S}}$ and query
${\mathcal{Q}}$ user sets over $N$ items
${\mathcal{I}}_{{\mathcal{T}},N}\subset{\mathcal{I}}$ (analogous to the usual
sense of training and testing sets respectively). Each meta-training task
${\mathcal{T}}\sim p({\mathbb{T}})$ is defined by:

$\displaystyle{\mathcal{T}}$
$\displaystyle=\\{{\mathcal{I}}_{{\mathcal{T}},N},{\mathcal{S}},{\mathcal{Q}}\\}\qquad\hskip
8.0pt{\mathcal{I}}_{{\mathcal{T}},N}\subset{\mathcal{I}}$ (4.4)
$\displaystyle{\mathcal{S}}$
$\displaystyle=\\{{\mathcal{S}}_{i}:i\in{\mathcal{I}}_{{\mathcal{T}},N}\\}\qquad{\mathcal{S}}_{i}=\\{u_{i,1},\dots,u_{i,K}\\}\qquad$
$\displaystyle u_{i,k}\in N_{i}\quad$ $\displaystyle{\mathcal{Q}}$
$\displaystyle=\\{{\mathcal{Q}}_{i}:i\in{\mathcal{I}}_{{\mathcal{T}},N}\\}\qquad{\mathcal{Q}}_{i}=\\{u^{\prime}_{i,1},\dots,u^{\prime}_{i,K^{\prime}}\\}$
$\displaystyle u^{\prime}_{i,k^{\prime}}\in N_{i}\quad$

where the support set ${\mathcal{S}}_{i}$ contains $K$ interacted users
sampled for each item $i\in{\mathcal{I}}_{{\mathcal{T}},N}$ and the
corresponding query set ${\mathcal{Q}}_{i}$ includes $K^{\prime}$ interacted
users sampled for each of the $N$ items.

We learn a few-shot recommender ${\bm{R}}_{F}$ that takes as input the support
users ${\mathcal{S}}$ to learn-to-compose representations for items
$i\in{\mathcal{I}}_{{\mathcal{T}},N}$ in task ${\mathcal{T}}$. The few-shot
recommender ${\bm{R}}_{F}$ is trained by optimizing a learning objective
designed to match the item recommendations generated by ${\bm{R}}_{F}$ for its
query users ${\mathcal{Q}}$ with their corresponding ground-truth interactions
over the item ${\mathcal{I}}_{{\mathcal{T}},N}$ in each meta-training task
${\mathcal{T}}$.

##### Initial Item Prototype

We learn a shared metric space of users and items to synthesize a
representation for each item $i\in{\mathcal{I}}_{{\mathcal{T}},N}$ based on
its support set ${\mathcal{S}}_{i}$ (with $K$ interactions) in task
${\mathcal{T}}$. The metric space (with similarity $\text{sim}_{m}(\cdot)$)
compactly clusters the interacted users ${\mathcal{S}}_{i}$ of each item
$i\in{\mathcal{I}}_{{\mathcal{T}},N}$ around a prototype representation
${\mathbf{p}}_{i}\in{\mathbb{R}}^{D}$ [101].

We first define a user preference encoder $G_{U}(\cdot\mid\theta)$ that maps
each user $u\in{\mathcal{U}}$ into a latent embedding space. To directly
transfer knowledge from the base recommender ${\bm{R}}_{B}$, the few-shot user
encoder $G_{U}(\cdot\mid\theta)$ has model parameters initialized from its
pre-trained encoder $F_{U}(\cdot\mid\phi)$ in the base recommender
${\bm{R}}_{B}$ (Equation 4.1), but is parameterized with learnable parameters
$\theta$. The prototype ${\mathbf{p}}_{i}$ for item
$i\in{\mathcal{I}}_{{\mathcal{T}},N}$ is computed as the mean vector of the
embedded support user set ${\mathcal{S}}_{i}$, defined by:

${\mathbf{p}}_{i}=\frac{1}{{\mathcal{S}}_{i}}\sum\limits_{u_{i,k}\in{\mathcal{S}}_{i}}G_{U}(u_{i,k},{\bm{X}}_{H}\mid\theta)\qquad
i\in{\mathcal{I}}_{{\mathcal{T}},N}$ (4.5)

Equation 4.5 encourages the prototype ${\mathbf{p}}_{i}$ to learn a
representative vector summarizing its cluster of interacted users. However, we
face two critical challenges in handling tail items: first, due to sparse
support sets, the prototypes are often noisy and sensitive to outliers;
second, due to substantial heterogeneity in the tail, simplistic averaging may
lack the resolution to discriminate across diverse tail items. Thus, the few-
shot recommender ${\bm{R}}_{F}$ needs a strong inductive bias during prototype
learning to avoid overfitting, and yet have sufficient expressivity to learn
discriminative prototypes.

##### Head-Tail Meta Knowledge Transfer

We now exploit the item-to-item relationship knowledge acquired by the neural
base recommender ${\bm{R}}_{B}$ (Section 4.4.1) as an inductive bias to
enhance the item prototype ${\mathbf{p}}_{i}$ (Equation 4.5). Given an item
$i\in{\mathcal{I}}_{{\mathcal{T}},N}$ with limited support users, extracting
knowledge from the most related items to item $i$ (based on the item-to-item
proximities) can provide valuable guidance to synthesize robust item
prototypes.

However, direct knowledge transfer from the base recommender ${\bm{R}}_{B}$ to
the few-shot recommender ${\bm{R}}_{F}$ is technically challenging:
dynamically identifying related items for each few-shot item during prototype
construction is not scalable due to the arbitrary complexity of ${\bm{R}}_{B}$
and the high cardinality of item sets in massive inventories. Thus, we extract
a compact representation of the item-item proximity knowledge (Equation 4.3)
discovered by ${\bm{R}}_{B}$ and transfer this knowledge to enhance item
prototypes.

Figure 4.5: Group embeddings can be viewed as centroids of overlapping item
clusters, e.g., Cafe (category) or Chicago (location); items (Cafes located in
Chicago) may often belong to overlapping item clusters.

Group-Enhanced Item Prototype Learning. We learn a set of $M$ group embeddings
${\mathcal{Z}}_{M}$ as basis vectors modeling item-item proximity in the
latent space of the base recommender ${\bm{R}}_{B}$, i.e., if $p_{B}(i,j)$ is
high for a pair of items $i,j\in{\mathcal{I}}$, then items $i$ and $j$ are
likely to exhibit similar characteristics. Formally, the set of group
embeddings ${\mathcal{Z}}_{M}$ are defined by the following equation below:

${\mathcal{Z}}_{M}=\\{z_{m}\in{\mathbb{R}}^{D}:1\leq m\leq M\\}\qquad
M\ll|{\mathcal{I}}|$ (4.6)

As depicted in Figure 4.5, we intuitively visualize the group embeddings as
discriminative centroids of overlapping clusters of items identified by
${\bm{R}}_{B}$, and conversely view items as mixtures over the group
embeddings, e.g., each centroid may represent a contextual factor such as a
restaurant type (Cafe) or location (Chicago), while restaurants are mixture of
multiple centroids (Cafe located in Chicago) and belong to overlapping item
clusters.

To enhance the prototype ${\mathbf{p}}_{i}$ of item
$i\in{\mathcal{I}}_{{\mathcal{T}},N}$, we synthesize a group-enhanced
prototype ${\mathbf{g}}_{i}\in{\mathbb{R}}^{D}$ as a mixture over the $M$
group embeddings. The mixture coefficients are estimated by a learnable
attention mechanism [130] to measure compatibility $\alpha_{im}$ between the
prototype ${\mathbf{p}}_{i}$ and each centroid $z_{m}\in{\mathcal{Z}}_{M}$. We
parameterize the attention function with a lightweight network comprised of an
auxiliary set ${\mathcal{K}}_{M}=\\{{\mathbf{k}}_{m}\in{\mathbb{R}}^{D}:1\leq
m\leq M\\}$ of trainable keys to index the group embeddings. We implement the
attention function with an inner product followed by softmax normalization,
as:

${\mathbf{g}}_{i}=\sum\limits_{m=1}^{M}\alpha_{im}{\mathbf{z}}_{m}\qquad\alpha_{im}=\frac{\exp\big{(}{\bm{W}}_{q}{\mathbf{p}}_{i}\cdot{\mathbf{k}}_{m}\big{)}}{\sum_{m^{\prime}=1}^{M}\exp\big{(}{\bm{W}}_{q}{\mathbf{p}}_{i}\cdot{\mathbf{k}}_{m^{\prime}}\big{)}}$
(4.7)

where ${\bm{W}}_{q}\in{\mathbb{R}}^{D\times D}$ is projects the prototype
${\mathbf{p}}_{i}$ into a query to index the centroids. The group-enhanced
item prototype ${\mathbf{g}}_{i}$ relates the different centroids via
attention, transferring knowledge to few-shot items with sparse support sets.

Task-level Stochastic Knowledge Distillation. We present a knowledge
distillation strategy [208] to learn compact group embeddings
${\mathcal{Z}}_{M}$ that capture item-item relationships in ${\bm{R}}_{B}$. We
transfer knowledge from a high-capacity teacher model (base recommender
${\bm{R}}_{B}$) to a compact student model (group embeddings
${\mathcal{Z}}_{M}$) by encouraging the student to emulate predictions of the
teacher; ${\mathcal{Z}}_{M}$ is trained to emulate the item proximity
distribution in ${\bm{R}}_{B}$.

Aligning pairwise item proximities over all items in ${\mathcal{I}}$ is not
scalable; thus, we operate at the granularity of each meta-training task
${\mathcal{T}}$. For each item $i\in{\mathcal{I}}_{{\mathcal{T}},N}$, we
compute a soft probability distribution $p_{B}(j\mid i,{\bm{R}}_{B})$ for the
teacher model ${\bm{R}}_{B}$ (based on equation 4.3) over other items
$j\in{\mathcal{I}}_{{\mathcal{T}},N}$ in the task ${\mathcal{T}}$, described
by:

$p_{B}(j\mid
i,{\bm{R}}_{B})=\frac{\exp\big{(}p_{B}(i,j)/T\big{)}}{\sum_{k\in{\mathcal{I}}_{{\mathcal{T}},N}}\exp\big{(}p_{B}(i,k)/T\big{)}}\quad
i,j\in{\mathcal{I}}_{{\mathcal{T}},N}$ (4.8)

where $T>0$ is a temperature scaling hyper-parameter to regulate the rate of
knowledge transfer. We analogously define the item similarity distribution
$p_{F}(j\mid i,{\bm{Z}}_{M})$ for the student model ${\mathcal{Z}}_{M}$ based
on the metric space proximity $\text{sim}_{m}(\cdot)$ of group-enhanced
prototypes ${\mathbf{g}}_{i}$ and ${\mathbf{g}}_{j}$ for items
$i,j\in{\mathcal{I}}_{{\mathcal{T}},N}$, defined by:

$p_{F}(j\mid
i,{\bm{Z}}_{M})=\frac{\exp\big{(}\text{sim}_{m}({\mathbf{g}}_{i},{\mathbf{g}}_{j})\big{)}}{\sum_{k\in{\mathcal{I}}_{{\mathcal{T}},N}}\exp\big{(}\text{sim}_{m}({\mathbf{g}}_{i},{\mathbf{g}}_{k})\big{)}}\;i,j\in{\mathcal{I}}_{{\mathcal{T}},N}$
(4.9)

We align the two distributions by minimizing cross-entropy between their task-
level similarities [208]. Since each item is typically related to very few
items within the task ${\mathcal{T}}$, our stochastic knowledge distillation
loss $L_{G}$ minimizes distribution divergence over the top-$n$ ($n\approx
10$) related items (out of $N$) identified by the teacher ${\bm{R}}_{B}$, by:

$L_{G}=-\frac{1}{nN}\sum\limits_{i\in{\mathcal{I}}_{{\mathcal{T}},N}}\sum\limits_{j\in\Top_{B,n}(i)}p_{B}(j\mid
i,{\bm{R}}_{B})\log p_{F}(j\mid i,{\bm{Z}}_{M})$ (4.10)

where ${\Top}_{B,n}(i)=\text{Top}_{n}\big{(}p_{B}(\cdot\mid
i,{\bm{R}}_{B})\big{)}$ denotes the top-$n$ most related items to item $i$
within ${\mathcal{I}}_{{\mathcal{T}},N}$ based on the teacher ${\bm{R}}_{B}$.
Distinct from prior distillation approaches [208, 209] that match student and
teacher predictions over a fixed set of classes, $L_{G}$ is stochastic and
thereby more efficient since it matches the top-$n$ item proximity
distributions over different sets of sampled items in each task. The
distillation loss $L_{G}$ transfers knowledge from ${\bm{R}}_{B}$ to the group
embeddings ${\mathcal{Z}}_{M}$ and is trained jointly with the rest of the
framework.

##### Item Prototype Fusion via Neural Gating

The initial prototype ${\mathbf{p}}_{i}$ for item
$i\in{\mathcal{I}}_{{\mathcal{T}},N}$ direct encodes its support users
${\mathcal{S}}_{i}$, while the group-enhanced prototype ${\mathbf{g}}_{i}$
captures the knowledge transferred from related items (via base recommender
${\bm{R}}_{B}$). We design a gating mechanism [210] that adaptively selects
salient feature dimensions from ${\mathbf{p}}_{i}$ and ${\mathbf{g}}_{i}$ to
infer the final gated item prototype ${\mathbf{e}}_{i}\in{\mathbb{R}}^{D}$.
Specifically, we introduce a neural gating layer to merge ${\mathbf{p}}_{i}$
and ${\mathbf{g}}_{i}$ by learning a non-linear gate to flexibly modulate
information flow via dimension re-weighting, defined by:

$\displaystyle\bf{gate}$
$\displaystyle=\sigma\big{(}{\bm{W}}_{g_{1}}{\mathbf{p}}_{i}+{\bm{W}}_{g_{2}}{\mathbf{g}}_{i}+{\mathbf{b}}_{g}\big{)}\quad
i\in{\mathcal{I}}_{{\mathcal{T}},N}$ $\displaystyle{\mathbf{e}}_{i}$
$\displaystyle=\bf{gate}\odot{\bm{p}}_{i}+(1-\bf{gate})\odot{\bm{g}}_{i}$
(4.11)

where ${\bm{W}}_{g_{1}}\in{\mathbb{R}}^{D\times D}$,
${\bm{W}}_{g_{2}}\in{\mathbb{R}}^{D\times D}$, and
${\mathbf{b}}_{g}\in{\mathbb{R}}^{D}$ are learnable weight parameters in the
neural gating layer, $\odot$ denotes the element-wise (or hadammard) product
operation, and $\sigma$ is the sigmoid non-linearity function.

Figure 4.6: Architecture diagram of ProtoCF depicting the different model
components: pre-trained neural base recommender ${\bm{R}}_{B}$ (top left),
group embedding learning via stochastic knowledge distillation $L_{G}$ (bottom
left), initial item prototype construction via support set averaging followed
by group-enrichment and adaptive gating to construct gated item prototype
${\mathbf{e}}_{i}$ (right).

##### Few-shot Recommender Training

We induce few-shot item rankings for the query users ${\mathcal{Q}}$ using the
gated item prototypes
$\\{{\mathbf{e}}_{i}:i\in{\mathcal{I}}_{{\mathcal{T}},N}\\}$ in meta-training
task ${\mathcal{T}}$. We generate item recommendations for each query user
$u^{\prime}\in{\mathcal{Q}}$ (over the task items
${\mathcal{I}}_{{\mathcal{T}},N}$) by measuring the similarity
$\text{sim}_{m}(\cdot)$ with each item prototype ${\mathbf{e}}_{i}$ Each meta-
training task ${\mathcal{T}}$ minimizes a negative log-likelihood $L_{P}$
between the few-shot item recommendations for query users ${\mathcal{Q}}$ and
their ground-truth interactions in ${\mathcal{T}}$, which is defined by:

$L_{P}=-\frac{1}{KN}\sum\limits_{i\in{\mathcal{I}}_{{\mathcal{T}},N}}\sum\limits_{u^{\prime}_{i,k^{\prime}}\in
Q_{i}}\log p_{F}(i\mid u^{\prime}_{i,k^{\prime}},\theta)$ (4.12)

where $p_{F}(i\mid u^{\prime}_{i,k^{\prime}},\theta)$ is computed based on
cosine similarity and the choice of likelihood function for few-shot training.

The overall loss $L$ is composed of two terms, the few-shot recommendation
loss $L_{P}$ (Equation 4.12) and the knowledge distillation loss $L_{G}$ for
group embedding learning (Equation 4.10), given by:

$L=L_{P}+\lambda L_{G}$ (4.13)

where $\lambda$ is a tunable hyper-parameter that balances the two loss terms.
Algorithm 4.1 summarizes the training procedure of our entire framework
ProtoCF.

##### Model Inference

We infer the gated prototype ${\mathbf{e}}_{i}$ for each item
$i\in{\mathcal{I}}$ by sub-sampling $K$ interactions from its historical
interactions $N_{i}$ as the the support set (Equation 4.11). We generate
personalized item recommendations for each user $u\in{\mathcal{U}}$ by:

$\hat{y}_{f}(u,i)=\text{sim}_{m}({\mathbf{e}}_{u},{\mathbf{e}}_{i})\quad
i\in{\mathcal{I}}\qquad{\mathbf{e}}_{u}=G_{U}(u,{\bm{X}}\mid\theta)$ (4.14)

The few-shot recommender ${\bm{R}}_{F}$ is designed for recommendations over
tail items (sparse interactions), while the base recommender ${\bm{R}}_{B}$ is
effective for head items (abundant interactions). In ProtoCF, we compute
rankings over the entire item set ${\mathcal{I}}$ by ensembling predictions
from ${\bm{R}}_{B}$ and ${\bm{R}}_{F}$. One simple interpolation approach is
given by:

$\hat{y}(u,i)=(1-\eta)\cdot\hat{y}_{b}(u,i)+\eta\cdot\hat{y}_{f}(u,i)$ (4.15)

where $0<\eta<1$ balances ${\bm{R}}_{F}$ and ${\bm{R}}_{B}$. We empirically
show effective overall item recommendations with $\eta=0.5$.

####  4.4.3 Model Details

We now discuss different choices of likelihood functions for training the few-
shot recommender ${\bm{R}}_{F}$ and architectural details of the base
recommender ${\bm{R}}_{B}$.

##### Few-shot Likelihood

We examine two likelihood functions in neural CF models: multinomial and
logistic.

  * •

Multinomial log-likelihood: The scores
$\text{sim}_{m}({\mathbf{e}}_{u^{\prime}},{\mathbf{e}}_{i})$ for each query
user $u^{\prime}\in{\mathcal{Q}}_{i}$, over the $N$ gated item prototypes in
meta-training task ${\mathcal{T}}$, are normalized to produce probabilities
$p_{F}(i\mid u^{\prime},\theta)$ over the $N$ items
${\mathcal{I}}_{{\mathcal{T}},N}$, defined by:

$p_{F}(i\mid
u^{\prime},\theta)=\frac{\exp\big{(}\text{sim}_{m}({\mathbf{e}}_{u^{\prime}},{\mathbf{e}}_{i})\big{)}}{\sum_{j\in{\mathcal{I}}_{{\mathcal{T}},N}}\exp\big{(}\text{sim}_{m}({\mathbf{e}}_{u^{\prime}},{\mathbf{e}}_{j})\big{)}}\qquad
u^{\prime}\in{\mathcal{Q}}_{i}$ (4.16)

The resulting loss $L_{G}$ (with Equation 4.12) is also known as the cross-
entropy loss, defined over the $N$ items of meta-training task
${\mathcal{T}}$.

  * •

Logistic log-likelihood: The relevance
$\hat{y}_{u^{\prime}i}=\text{sim}_{m}({\mathbf{e}}_{u^{\prime}},{\mathbf{e}}_{i})$
for item $i\in{\mathcal{I}}_{{\mathcal{T}},N}$ to query user
$u^{\prime}\in{\mathcal{Q}}_{i}$, is transformed into a probability using the
sigmoid function $\sigma$. We use a confidence weight $\beta>0$ to re-weight
the likelihood of observed 1’s which are far fewer than the unobserved 0’s in
implicit feedback. The logistic log-likelihood is given by:

$\log p_{F}(i\mid
u^{\prime},\theta)=\beta\log\sigma(\hat{y}_{u^{\prime}i})+\sum\limits_{j\in{\mathcal{I}}_{{\mathcal{T}},N},u^{\prime}\notin
N_{j}}\log(1-\sigma(\hat{y}_{u^{\prime}j}))$ (4.17)

Algorithm 4.1 ProtoCF: Prototypical Collaborative Filtering

1:User-item interactions ${\bm{X}}$, meta-training task distribution
$p({\mathbb{T}})$.

2:Function $f_{T}(i\mid u),i\in{\mathcal{I}}_{T}$ for few-shot item
recommendations.

3:Pre-train the neural base recommender ${\bm{R}}_{B}$ on the training
interactions ${\bm{X}}$ to learn $f_{H,\phi}(i\mid u)$ (eqn 4.2) and freeze
parameters $\phi$.

4:Initialize user preference encoder $G_{U}(\cdot\mid\theta)$ of few-shot
recommender ${\bm{R}}_{F}$ with parameters $F_{U}(\cdot\mid\phi)$ from the
base recommender ${\bm{R}}_{B}$.

5:$\triangleright$ Meta-training: learn-to-recommend few-shot items.

6:while not converged do

7: Sample a meta-training task
${\mathcal{T}}=\\{I_{{\mathcal{T}},N},{\mathcal{S}},{\mathcal{Q}}\\}\sim
p({\mathbb{T}})$.

8: Calculate the initial ${\mathbf{p}}_{i}$ and group-enhanced
${\mathbf{g}}_{i}$ prototypes for items $i\in{\mathcal{I}}_{{\mathcal{T}},N}$
(eqn 4.5 and eqn 4.7).

9: Compute the knowledge distillation loss $L_{G}$ (eqn 4.10).

10: Compute gated prototype ${\mathbf{e}}_{i}$ for items
$i\in{\mathcal{I}}_{{\mathcal{T}},N}$ (eqn 4.11).

11: Estimate few-shot recommendation loss $L_{P}$ (eqn 4.12) with multinomial
(eqn 4.16) or logistic (eqn 4.17) log-likelihoods.

12: Minimize overall loss $L$ (eqn 4.13) using mini-batch gradient descent.

13:$\triangleright$ Model Inference: few-shot and overall item
recommendations.

14:Generate item recommendations over ${\mathcal{I}}$ for user
$u\in{\mathcal{U}}$ (eqn 4.15)

The cosine similarity scores are also scaled to match the non-saturating
regimes of the softmax and sigmoid functions in the multinomial and logistic
log-likelihoods respectively.

##### Neural Base Recommender Architecture

We consider three neural collaborative filtering methods, matrix factorization
(MF) [87], denoising (CDAE) [89] and variational (VAE-CF) [90] autoencoders,
as base recommenders ${\bm{R}}_{B}$ (Equation 4.1) for our framework ProtoCF.
We briefly describe their architectures:

  * •

Matrix Factorization (MF) [87]: The user $F_{U}$ and item $F_{I}$ encoders are
learnable latent embeddings for each user and item respectively, which are
trained using a logistic log-likelihood training objective.

  * •

Variational AutoEncoder (VAE-CF) [90]: The user encoder $F_{U}$ is a two-layer
Multi-Layer Perceptron transforming the binary user preference vector
${\mathbf{x}}_{u}\in{\mathbb{R}}^{I}$ into a $D$-dimensional user embedding
${\bm{h}}_{u}\in{\mathbb{R}}^{D}$, defined by:

${\bm{h}}_{u}=F_{U}({\bm{x}}_{u}\mid\phi)=\sigma({\bm{W}}_{2}^{T}(\sigma({\bm{W}}_{1}^{T}{\bm{x}}_{u}+b_{1})+b_{2})$
(4.18)

with learnable weight matrices ${\bm{W}}_{1}\in{\mathbb{R}}^{I_{H}\times D}$
and ${\bm{W}}_{2}\in{\mathbb{R}}^{D\times D}$, biases
$b_{1},b_{2}\in{\mathbb{R}}^{D}$, and $tanh(\cdot)$ activations for non-
linearity $\sigma$. The item encoder $F_{I}$ is a latent embedding. VAE-CF
uses a multinomial likelihood with KL-divergence regularization.

  * •

Denoising AutoEncoders (CDAE) [89]: The user encoder $F_{U}$ operates on
partially corrupted inputs ${\mathbf{x}}_{u}$ and adds an auxiliary per-user
embedding to the encoder output from Equation 4.18. We train CDAE using a
multinomial log-likelihood, albeit without the KL-divergence prior
regularization.

###  4.5 Experiments

We present experiments on four real-world datasets to evaluate our framework
ProtoCF. We introduce datasets, baselines and experimental setup in Sections
4.5.1, 4.5.2 and 4.5.3. We propose four research questions to guide our
experiments:

  1. ($\textbf{RQ}_{\textbf{1}}$)

Does ProtoCF beat state-of-the-art NCF and sparsity-aware methods on overall
recommendation performance?

  2. ($\textbf{RQ}_{\textbf{2}}$)

What is the impact of item interaction sparsity on the few-shot recommendation
performance of ProtoCF?

  3. ($\textbf{RQ}_{\textbf{3}}$)

How do the different architectural choices impact the few-shot and overall
performance of ProtoCF?

  4. ($\textbf{RQ}_{\textbf{4}}$)

How do the hyper-parameters (distillation loss balance factor $\lambda$ and
meta-training task size $N$) affect ProtoCF?

Finally, we discuss the limitations of our ProtoCF model and explore future
directions in Section 4.5.8.

####  4.5.1 Datasets

We conducted experiments on four publicly available benchmark datasets,
including two online product review platforms (Epinions, Yelp) and two check-
in based social networks (Weeplaces, Gowalla).

  * •

Epinions111https://www.cse.msu.edu/ tangjili/datasetcode/truststudy.htm:
product ratings from an e-commerce platform; we retain interactions with
ratings higher than two.

  * •

Yelp222https://www.yelp.com/dataset: user ratings on local businesses located
in the state of Arizona, obtained from Yelp dataset challenge round 13.

  * •

Weeplaces333https://www.yongliu.org/datasets/: we extract business check-ins
from Weeplaces of different categories, including Nightlife, Outdoors,
Entertainment, Travel and Food, across all cities in the United States.

  * •

Gowalla [211]: restaurant check-ins in Gowalla by users across different
cities in the United States.

We pre-process the datasets to retain users and items with at least ten
interactions using the 10-core setting [212] (Table 4.3).

Dataset |  Epinions |  Yelp |  Weeplaces |  Gowalla
---|---|---|---|---
# Items |  9,035 |  10,451 |  11,679 |  27,920
# Users |  9,729 |  13,926 |  6,167 |  17,848
# Interactions |  260,263 |  465,386 |  427,236 |  907,351
# Interactions per item |  28.81 |  44.53 |  36.58 |  32.50
Table 4.3: Dataset statistics

####  4.5.2 Baselines

We present comparisons against prior work that broadly fall into two
categories: standard neural collaborative filtering models, and sparsity-aware
long-tail item recommendation models, including regularization and meta-
learning techniques.

  * •

Neural Base Recommenders: neural CF methods with matrix factorization (BPR)
[87], and autoencoder models VAE-CF [90] and CDAE [89] (described in Section
4.4.3).

  * •

NCF [88]: neural CF model with non-linear interactions (via neural layers)
between the user and item embeddings.

  * •

NGCF [91]: state-of-the-art graph-based NCF with embedding propagation layers
on the user-item interaction graph.

  * •

Cofactor [193]: regularized MF to capture inter-item associations by jointly
decomposing the user-item interaction matrix and the item-item co-occurrence
matrix, with shared latent item factors.

  * •

EFM [194]: embedding factorization model that uses item-item co-occurrence
with bayesian personalized ranking.

  * •

DropoutNet [108]: randomly dropout latent CF embedding for regularization in
content-based CF for cold-start (auxiliary content). We adapt it to long-tail
items by replacing content embeddings with prototypes (over support set).

  * •

MetaRec-LWA [116] meta-learning method to construct recommendation models for
cold-start users with user-specific linear transforms; we adapt it to
construct few-shot item embeddings.

  * •

MetaRec-NLBA [116]: meta-learning recommendation model that learns user-
specific biases parameterized by non-linear layers, to replace the user-
specific weights in MetaRec-LWA.

Note that we omit experimental baseline comparisons with gradient-based meta-
learning recommenders [110, 112], since they are designed for cold-start
recommendation in the presence of auxiliary attributes. We test ProtoCF by
adopting BPR [87] (matrix factorization), VAE-CF [90], and CDAE [89] as base
recommenders of our framework.

Dataset | Epinions | Yelp | Weeplaces | Gowalla
---|---|---|---|---
Metric |  N@50 |  R@50 |  N@50 |  R@50 |  N@50 |  R@50 |  N@50 |  R@50
Standard Neural Collaborative Filtering Methods
BPR [87] |  0.0860 |  0.1666 |  0.0749 |  0.1416 |  0.2537 |  0.3778 |  0.1661 |  0.2703
NCF [88] |  0.0878 |  0.1694 |  0.0752 |  0.1429 |  0.2462 |  0.3694 |  0.1702 |  0.2745
NGCF [91] |  0.0913 |  0.1725 |  0.0826 |  0.1579 |  0.2533 |  0.3764 |  0.1696 |  0.2758
VAE-CF [90] |  0.0938 |  0.1778 |  0.0854 |  0.1602 |  0.2482 |  0.3730 |  0.1710 |  0.2769
CDAE [89] |  0.0927 |  0.1774 |  0.0870 |  0.1611 |  0.2570 |  0.3760 |  0.1634 |  0.2644
Sparsity-aware Long-tail Item Recommendation Methods
DropoutNet [108] |  0.0881 |  0.1697 |  0.0761 |  0.1435 |  0.2516 |  0.3751 |  0.1697 |  0.2768
Cofactor [193] |  0.0845 |  0.1639 |  0.0734 |  0.1402 |  0.2342 |  0.3539 |  0.1596 |  0.2642
EFM [194] |  0.0742 |  0.1534 |  0.0741 |  0.1403 |  0.2306 |  0.3429 |  0.1532 |  0.2584
MetaRec-NLBA [116] |  0.0453 |  0.0937 |  0.0381 |  0.0875 |  0.1698 |  0.2889 |  0.0753 |  0.1384
MetaRec-LWA [116] |  0.0467 |  0.0943 |  0.0392 |  0.1425 |  0.1702 |  0.2997 |  0.0722 |  0.1391
Prototypical Collaborative Filtering Recommenders (ProtoCF)
ProtoCF \+ BPR |  0.0964 |  0.1812 |  0.0815 |  0.1533 |  0.2576 |  0.3879 |  0.1737 |  0.2800
ProtoCF \+ VAE |  0.0977 |  0.1830 |  0.0857 |  0.1605 |  0.2725 |  0.4035 |  0.1899 |  0.3004
ProtoCF \+ CDAE |  0.0972 |  0.1824 |  0.0883 |  0.1623 |  0.2697 |  0.4011 |  0.1786 |  0.2875
Percentage Gains |  4.16% |  2.92% |  1.50% |  0.75% |  6.03% |  6.80% |  11.05% |  8.49%
Table 4.4: Overall item recommendation results on four datasets, R@K and N@K
denote Recall@K and NDCG@K metrics at $K=50$. Sparsity-aware models are
generally outperformed by standard NCF methods on overall item recommendation;
ProtoCF achieves overall NDCG@50 gains of 6% and Recall@50 gains of 4% (over
the best baseline) across all datasets.

####  4.5.3 Experimental Setup

In each dataset, we randomly split the user interactions of all items into
train (70%) and test (30%) sets, which ensures consistent interaction
distributions across train and test sets. We also use 10% of training
interactions as validation for hyper-parameter tuning. We use NDCG@K and
Recall@K as evaluation metrics, computed based on the rank of ground-truth
test interactions in top-$K$ ranked item lists.

We design a unified model to enhance few-shot recommendation on the tail
without affecting the overall performance. We first evaluate overall
recommendations over the entire item set ${\mathcal{I}}$ followed by few-shot
performance analysis over the long-tail.

All experiments are conducted on a Tesla K-80 GPU using PyTorch. ProtoCF is
trained using episodic learning for a maximum of 300 episodes with a meta-
training task size of 512 items using Adam optimizer. ProtoCF uses a
multinomial log-likelihood for few-shot training and uses support sets of upto
$K=10$ and query sets of $K^{\prime}=5$ interactions per item. We learn
$M=100$ group embeddings ${\bm{Z}}_{M}$, tune the learning rate and balance
hyper-parameter $\lambda$ (Equation 4.13) in the range
$\\{10^{-4},10^{-3},10^{-2}\\}$, and use dropout regularization with a rate of
0.5. We tune baselines in hyper-parameter ranges centered at the author-
provided values on each dataset and set the latent embedding dimension to 128
for consistency. Our implementation of ProtoCF and datasets are publicly
available444https://github.com/aravindsankar28/ProtoCF.

####  4.5.4 Overall Recommendation Results ($\text{RQ}_{1}$)

Our experimental results comparing the overall recommendation performance of
ProtoCF with competing baselines are shown in Table 4.4. We summarize our key
empirical observations below:

  * •

Neural CF models based on autoencoders (VAE-CF, CDAE) and graph neural
networks (NGCF) outperform other latent-factor models (NCF, BPR) on overall
model performance (Table 4.4).

  * •

Model regularization strategies that use item co-occurrence information
(CoFactor, EFM) to improve long-tail item recommendations, are noticeably
worse than BPR in overall performance.

  * •

Sparsity-aware meta-learning models (MetaRec) perform poorly in overall item
rankings. One potential reason is their inability to effectively exploit or
transfer knowledge from head items.

  * •

ProtoCF outperforms state-of-the-art baselines (NDCG@50 gains of 5% on
average) on overall item ranking, with consistent gains for the variants of
all neural base recommenders.

Next, we examine the few-shot performance of ProtoCF.

####  4.5.5 Few-Shot Recommendation Results ($\text{RQ}_{2}$)

To evaluate few-shot results, we qualitatively analyze performance for long-
tail items with sparse interactions. Specifically, we compare recommendation
results for long-tail items with varying number of training interactions $K$
(5 to 30) by computing Recall@50 metrics only on their associated test
interactions (Figure 4.7). We only include the base recommenders BPR and VAE-
CF here for comparison since they consistently outperform other sparsity-aware
variants.

We find that model performance generally increases with item interaction
count; ProtoCF achieves significant performance gains for items with less than
20 interactions. Episodic training with knowledge transfer is one of the key
factors responsible for our higher gains over items with sparse interactions
(small values of $K$).

Figure 4.7: Few-shot item recommendation results: Performance comparison for
long-tail items with varying number of training interactions $K$ (5 to 30);
lines denote model performance (Recall@50) and background histograms indicate
the cumulative fraction of the item inventory covered by tail items with $\leq
K$ impressions. Overall performance generally increases with $K$ for all
models; ProtoCF achieves notably stronger gains (over baselines) for items
with few training interactions (small $K$).

To evaluate the impact of interaction sparsity across the entire item set, we
compare overall recommendation performance (Recall@K) across item-groups with
different sparsity levels. We divide the test set into ten equal-sized item-
groups, sorted in increasing order by the average number of interactions per
item. Figure 4.8 compares ProtoCF against two base recommenders BPR and VAE-
CF.

From figure 4.8, model performance is lower on the long-tail for base
recommenders BPR and VAE due to severe interaction sparsity. Notably, ProtoCF
achieves much higher item recall scores on the tail items with significant
gains over the corresponding base recommenders, while ensuring comparable
performance on the head items. Knowledge transfer of item-to-item
relationships via group embeddings and pre-trained user encoder enables
ProtoCF to learn discriminative prototypes for tail items with sparse
interactions.

Figure 4.8: Impact of item interaction sparsity: Performance comparison for
item-groups sorted in increasing order by their average training interaction
counts; lines denote model performance (Recall@50) and background histograms
indicate the average number of interactions in each item-group. ProtoCF has
significant performance gains (over baselines) on the tail items (item-groups
$G_{1}$ to $G_{8}$) while maintaining comparable performance on the head items
(item-groups $G_{9}$ to $G_{10}$).

####  4.5.6 Model Ablation Study ($\text{RQ}_{3}$)

We examine the impact of different architectural design choices in ProtoCF on
its overall and few-shot performance (Table 4.5). We choose VAE-CF as the base
recommender to instantiate ProtoCF due to its consistent results. Here, we
report few-shot performance by only considering the test interactions of long-
tail items with less than 20 training interactions. Note that most ablation
variants do not have a significant impact on overall results since all
predictions are computed by ensembling ${\bm{R}}_{F}$ and ${\bm{R}}_{B}$
(Equation 4.15). Our key design choices and empirical insights are shown
below:

Dataset | Epinions | Gowalla
---|---|---
Metric |  Overall R@50 |  Few-shot R@50 |  Overall R@50 |  Few-shot R@50
ProtoCF |  0.1830 |  0.1070 |  0.3004 |  0.2195
w/o Prototype Gating |  0.1823 |  0.0948 |  0.2992 |  0.2082
w/o Knowledge Distillation |  0.1805 |  0.0869 |  0.2923 |  0.1983
ProtoCF-Avg |  0.1801 |  0.0712 |  0.2898 |  0.1696
ProtoCF-logistic |  0.1804 |  0.0896 |  0.2853 |  0.1843
VAE-CF [90] |  0.1778 |  0.0549 |  0.2769 |  0.1316
MetaRec-LWA [116] |  0.0943 |  0.0898 |  0.1391 |  0.1804
Table 4.5: Model ablation study of ProtoCF; few-shot performance is reported
for tail items (less than 20 training interactions). Knowledge transfer and
prototype gating contribute 10-19% and 5-11% to few-shot gains respectively.

  * •

Remove Prototype Gating: We replace the gating layer (Equation 4.11) that
adaptively fuses the initial and group-enhanced item prototypes, with a
simpler additive operation. Adaptive gating contributes 5-11% few-shot
performance gains.

  * •

Remove Knowledge Distillation: We test the importance of item-to-item
relationships transferred from the base recommender via distillation loss
$L_{G}$; here, we exclude knowledge transfer from group embeddings
${\bm{Z}}_{M}$ and only train on the few-shot loss $L_{P}$. Removing
distillation loss $L_{G}$ reduces few-shot results by 10-19%.

  * •

Averaging-based Prototype (ProtoCF-AVG): We directly use the averaging-based
initial item prototype (Equation 4.5) for inference; here, we also exclude the
pre-trained parameter initialization for the user encoder $G_{U}$ (from
$F_{U}$ in the base recommender). ProtoCF-AVG (without any knowledge transfer)
is worse than ProtoCF by a margin of 20-30%, yet outperforms the base
recommender VAE-CF by nearly 30% on few-shot items.

  * •

Logistic log-likelihood (ProtoCF-logistic): We train ProtoCF using logistic
log-likelihood (Equation 4.17). ProtoCF with multinomial log-likelihood
(Equation 4.16) outperforms ProtoCF-logistic by a considerable margin; this
validates prior findings [90] on the efficacy of multinomal for top-$N$
recommendation.

Note that the meta-learning baseline MetaRec-LWA improves few-shot results
(compared to VAE-CF), but forgets knowledge of head items resulting in poor
overall recommendations.

####  4.5.7 Parameter Sensitivity ($\text{RQ}_{4}$)

We analyze sensitivity to the hyper-parameter $\lambda$ that weights the
knowledge distillation loss $L_{G}$ (Equation 4.13). In Figure 4.9 (a), we
show the effect of $\lambda$ on few-shot results with base recommenders BPR
and VAE-CF on Gowalla. We empirically find the optimal value of $\lambda$ to
be 0.01 for both models, which also transfers across datasets.

Figure 4.9: Few-shot performance on Gowalla (for tail items with less than 20
training interactions) is higher for larger meta-training tasks; the
empirically optimal value of balance factor $\lambda=0.01$ also transfers
across all datasets.

We investigate the impact of task size, which is the number of items $N$
sampled in each meta-training task ${\mathcal{T}}$. In Figure 4.9 (b),
performance typically increases with task size (and stabilizes $\sim 400$),
due to a larger set of sampled items available for ranking; this observation
is consistent with prior few-shot learning studies [101].

####  4.5.8 Discussion

Our framework ProtoCF is orthogonal to architectural advances in neural
recommendation models that enhance representational capacity to learn from
massive interaction data. We adapt expressive neural recommenders to develop
light-weight few-shot models tailored to the long-tail. Furthermore, our few-
shot formulation requires no side information and can further be easily
adapted to address the long-tail of users.

ProtoCF learns a metric space predicated on knowledge transfer over a shared
user space. Few-shot transfer learning across domains with disjoint feature
spaces is a potential future direction.

###  4.6 Conclusion

We formulate long-tail item recommendation as learning-to-embed items with
sparse interactions. A few-shot learning framework ProtoCF is introduced to
extract meta-knowledge across a collection of training tasks designed to
simulate tail item ranking. ProtoCF efficiently transfers knowledge from
arbitrary base recommenders to construct discriminative prototypes for items
with few interactions. Our experiments indicate 5% overall performance gains
(Recall@50) for ProtoCF over the state-of-the-art, with notable 60-80% few-
shot performance gains (Recall@50) on long-tail items with less than 20
training interactions.

In this chapter, we examined another common transductive learning setting of
collaborative filtering over bipartite user-item interactions that are
prevalent in several online interaction platforms. To overcome entity-level
(user/item) interaction sparsity challenges that arise due to heavy-tailed
distributions in user interests and interaction patterns, we introduced a
meta-learning framework for few-shot recommendation. In the next part of this
dissertation, we examine several inductive learning applications targeted at
behavior modeling for new (or unseen) entities that are only observed during
inference.

##  Chapter 5 InfVAE: Social Regularization to Predict Information Diffusion

###  5.1 Introduction

In social media, information disseminates or _diffuses_ to a large number of
users through content posting or re-sharing behavior, resulting in a cascade
of user activations, e.g., a user voting a news story on Digg (a social news
sharing website) triggers a series of votes from multiple users, who may be
his friends or other users interested in the same story. Given a set of
activated seed users who have posted a piece of user-generated content,
diffusion models aim to predict the set of all influenced users who re-share
it. Diffusion modeling has widespread social media applications, including
viral marketing [213], limiting misinformation spread, personalized
recommendations [180], and popularity prediction [214].

The diffusion prediction problem has received significant attention in the
research community. The earliest methods assume that the mechanism of social
influence propagation is known a priori, e.g., the Independent Cascade (IC)
[70, 73] and Linear Threshold (LT) models [71] that associate each link with a
non-negative weight indicative of pairwise user-user influence. Unlike pre-
defined propagation hypotheses [70], recent methods learn data-driven
diffusion models from collections of user activation sequences (diffusion
cascades). Prior diffusion models broadly fall into two categories.

Probabilistic generative cascade models use hand-crafted features including
social roles [215], communities [75], topics [72], and structural patterns
[216]. Such methods rely on feature engineering that requires manual effort
and extensive domain knowledge, and are limited by the modeling capacity of
carefully chosen probability distributions.

Representation learning methods avoid feature extraction by learning user
representations characterizing their influencing ability and conformity [79,
80]. Prior work mainly consider the impact of temporal user-user influence
learned from historical diffusion cascades; prior methods project cascades
onto local social neighborhoods to generate Directed Acyclic Graphs (DAGs),
and propose extensions of Recurrent Neural Networks (RNNs) to model temporal
influence. State-of-the-art models include DAG-structured LSTMs [81] that
explicitly operate on induced DAGs and attention-based RNNs [217, 83, 82] that
implicitly consider cross-correlations across activated seed users for
diffusion prediction.

Prior work only model the sequence or projected social structure (induced DAG)
of previously influenced users while ignoring social structures that do not
manifest in cascades; they only capture the temporal correlation in diffusion
behaviors known as temporal influence or contagion [13]. Consider a Twitter
user interested in politics who follows famous political leaders and joins
interest groups; this induces transitive connections to other users that
however may not manifest in cascades unless she re-tweets or posts content.
Social homophily [11] suggests stronger ties between users with shared traits
or interests, which induces correlated diffusion behaviors without direct
causal influence. Social graph connectivity information reveals insights into
homophily and is critical to model diffusion behaviors for the vast majority
of users who rarely post content and appear in cascades.

However, homophilous diffusion and contagion can result in differing dynamics,
e.g., contagions are self-reinforcing and viral while homophily hinges on
users’ preferences or traits. Indeed, social homophily and temporal influence
are fundamentally confounded in observational studies of diffusion processes
[13], which makes it challenging to contextually model the impact of both
factors. Thus, our key objective is to develop a principled neural framework
to contextually the model the co-variance of temporal influence (recent
posting activities) with social hompohily (structural graph connectivity) for
diffusion prediction.

Present Work: Our social regularization framework InfVAE jointly models
_homophily_ through _social_ embeddings preserving social network proximity
and _influence_ through _temporal_ embeddings encoding the relative sequential
order of user activations. Motivated by the capabilities of variational
autoencoders (VAEs) [135] in alleviating sparsity via Gaussian priors [90] and
the expressive power of Graph Neural Networks (GNNs) [39, 28], we adopt graph-
VAEs to model social homophily. We learn structure-preserving social
embeddings for each user through VAEs, and differentiate their social roles
(influential versus susceptible) towards diffusion modeling. Given an initial
set of seed user activations, InfVAE utilizes an expressive co-attentive
fusion network that captures non-linear correlations between social and
temporal embeddings, to contextually model the co-variance of homophily and
influence on predicting the set of all influenced users. We make the following
contributions:

Generalizable Variational Autoencoder Framework: Unlike existing diffusion
prediction methods that only consider temporal influence via induced
propagation structures, InfVAE models homophily and distinguishes social roles
of users towards diffusion prediction through a novel generalizable VAE
framework that can be instantiated with a wide variety of GNN architectures of
arbitrary model complexity.

Efficient Homophily and Influence Integration: To the best of our knowledge,
ours is the first neural framework to exploit the co-variance of social
homophily and temporal influence for predicting diffusion behaviors. Given a
sequence of seed user activations, InfVAE employs an expressive co-attentive
fusion network to jointly attend over their social and temporal
representations to predict the set of all influenced users. InfVAE is faster
than state-of-the-art recurrent methods by an order of magnitude.

Robust Experimental Results: Our experiments on multiple real-world social
networks, including Digg, Weibo, and Stack-Exchanges, demonstrate significant
gains for InfVAE over state-of-the-art models. Modeling social homophily
through VAEs enables massive gains for users with sparse activities, and users
who lack direct social connections in seed sets. An ablation analysis of
various modeling choices further justifies the benefits of modeling the co-
variance of social homophily and temporal influence.

We organize the rest of the chapter as follows. In Section 5.3, we formally
define the problem of diffusion prediction in social networking platforms. In
Section 5.4, we describe our proposed Influence Variational AutoEncoder
framework (InfVAE). We present experimental results in Section 5.5, and
finally conclude in Section 5.7.

###  5.2 Related Work

We discuss existing work on diffusion modeling followed by related work on
network representation learning, variational auto-encoders and co-attentions.

Information diffusion overview. Historically, information diffusion has been
studied through two seminal models: Independent Cascade (IC) [70] and Linear
Threshold (LT) [71]. Three distinct applications emerged, namely: network
inference [218], which infers the underlying social network that best explains
the observed cascades; cascade prediction [69], which predicts macroscopic
properties of cascades, including size, growth, and shape; and diffusion
prediction [81], which learns a model from social links and cascade sequences,
to predict the set of influenced users given a seed set of activated users. In
this work, we focus on diffusion prediction.

Diffusion prediction. The earliest data-driven methods propose several
extensions of IC and LT incorporating topics [72], continuous timestamps [73],
user profiles [74], and community structure [75]. A few techniques explore
probabilistic generative models via latent topics and communities [76, 219].
Most recent studies focus on learning representations to overcome feature
engineering or pre-defined hypotheses in diffusion modeling [77, 78, 79, 81,
217, 220, 80, 82]. Emb-IC [79], Inf2vec [80] embed user influencing capability
and susceptibility in diffusion. Topo-LSTM [81], CYAN-RNN [217], SNIDSA [82],
and DeepDiffuse [83] project the diffusion cascades on local social
neighborhoods and model the resulting DAG propagation structures with RNNs.
These techniques outperform classical approaches by significant margins in
diffusion prediction. Our key observation is that these projected DAGs could
ignore social structures that do not appear in any observed cascade. In
contrast, our model InfVAE can account for unobserved social connections in
the user activation process by modeling social homophily through VAEs.

A related problem is social influence prediction, which aims to classify
social media users based on the activation status of their ego-network [221,
220]. Direct extensions to predict the set of all influenced users (diffusion
prediction) entails reapplying their models on each candidate inactive user in
the social network, resulting in prohibitive inference costs, hence preventing
a comparison.

Network representation learning: This line of work captures varied notions of
structural node proximity [18, 222] in networks via low-dimensional vectors.
Notably, graph neural networks have achieved great success in node
classification and link prediction [39, 41, 40, 46, 58, 223, 224]. Graph
Autoencoders [26, 27] employ various encoding and decoding architectures to
embed network structure and learn unsupervised node embeddings. [28] unify a
large family of network embedding methods in an autoencoder framework.
However, general-purpose embeddings modeling structural proximity are not
directly suited to diffusion modeling.

Co-attentional models: Our work also leverages recent advances in neural
attention mechanisms, especially in Natural Language Processing [130].
Specifically, co-attention has achieved great success in modeling
relationships between pairs of sequences, e.g., question-answer [225], etc.
Co-attentional methods compute interaction weights between data modalities,
learning fine-grained non-linear correlations. In our work, we develop a co-
attentive fusion network to capture the contextual interplay of users’ social
and temporal representations for diffusion prediction.

###  5.3 Problem Definition

We study diffusion prediction in social networks where the goal is to predict
the set of all influenced users, given temporally ordered seed user
activations for user-generated content.

######  Definition 5.1.

Social Network: The social network is represented as a graph
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$ where
${\mathcal{V}}=\\{v_{i}\\}_{i=1}^{N}$ is the set of $N$ users and
${\mathcal{E}}=\\{e_{ij}\\}_{i,j=1}^{N}$ is the set of links. We denote the
adjacency matrix of ${\mathcal{G}}$ by $A\in{\mathbb{R}}^{N\times N}$ where
$A_{i,j}=1$ if $e_{i,j}\in{\mathcal{E}}$ otherwise 0.

######  Definition 5.2.

Diffusion cascade: A diffusion cascade $D_{i}$ is an ordered sequence of user
activations in ascending time order denoted by:
$D_{i}=\\{(v_{i_{k}},t_{k})\mid
v_{i_{k}}\in{\mathcal{V}},t_{k}\in[0,\infty),\;k=1\dots K\\}$, each
$v_{i_{k}}$ is a distinct user in ${\mathcal{V}}$ (no repeats) and $t_{k}$ is
non-decreasing, i.e., $t_{k}\leq t_{k+1}$. The $k^{th}$ user activation has a
tuple $(v_{i_{k}},t_{k})$, referring the activated user and activation time.

We represent cascades by delay-agnostic relative activation orders similar to
[80, 81, 79], i.e., a cascade is equivalently written as
$D=\\{(v_{i_{k}},k)\mid v_{i_{k}}\in{\mathcal{V}}\\}_{k=1}^{K}$. We do not
assume the availability of explicit re-share links between users in cascades;
this corresponds to the simplest yet most general setting of diffusion [81,
80]. Though timestamps may be easily used as input features, we leave
generation of continuous timestamps as future work.

######  Definition 5.3.

Diffusion prediction: Given a social network $G$ and a collection of cascade
sequences ${\mathbb{D}}=\\{D_{i},1\leq i\leq|{\mathbb{D}}|\\}$, learn
diffusion model $M$ to predict the future set of influenced users in a cascade
with seed activation sequence $I=\\{(v_{i_{1}},1),\dots,(v_{i_{k}},k)\\}$ of
$k$ seed users. Diffusion prediction estimates the probability of influencing
each inactive user: $P_{\Theta}(v\mid I)\;\forall v\in{\mathcal{V}}-I$,
inducing a ranking of activation likelihoods over the inactive user set.

We create a training set ${\mathbb{T}}$ of diffusion _episodes_ containing
(seed activations, activated users) tuples from the cascade collection
${\mathbb{D}}$, by randomly splitting each cascade $D\in{\mathbb{D}}$ of
length $K$ at each time step $2\leq k\leq K-1$. Specifically, a split at time
step $k\geq 2$, creates a training episode $(I_{k},C_{k})$ where
$I_{k}=\\{(v_{i_{j}},j);1\leq j\leq k\\}$ is the seed set consisting of the
cascade sliced at $k$ and $C_{k}=\\{v_{i_{k+1}},\dots,v_{i_{K}}\\}$ is the set
of influenced users after time step $k$. Thus, we denote the training set by
${\mathbb{T}}=\\{(I_{i},C_{i})\;1\leq i\leq|{\mathbb{T}}|\\}$.

###  5.4 InfVAE Framework

In this section, we describe our proposed Influence Variational Autoencoder
(InfVAE) framework for predicting information diffusion in social networks. We
first introduce the different interacting latent variables in our deep
generative model, then describe the process of generating diffusion cascades
and finally present model training details.

Symbol | Description
---|---
${\bm{Z}}$ | Social variables modeling network proximity, for all users ${\mathcal{V}}$
${\bm{V}}_{S}$ | Sender variables for all users ${\mathcal{V}}$
${\bm{V}}_{R}$ | Receiver variables for all users ${\mathcal{V}}$
${\bm{V}}_{T}$ | Temporal influence variables for all users ${\mathcal{V}}$
${\bm{V}}_{P}$ | User-specific popularity variables for all users ${\mathcal{V}}$
${\bm{P}}_{K}$ | Position-encoded temporal embeddings for all time steps $K$
Table 5.1: Notations

####  5.4.1 Generative Model Description

InfVAE is a neural latent variable model that jointly capture social homophily
and temporal influence for diffusion prediction. We describe the latent
variables modeling homophily and influence, followed by the structure of our
generative network InfVAE.

##### Social Homophily.

Our objective is to define latent social variables for users that capture
social homophily. The homophily principle stipulates that users with similar
interests are more likely to be connected [11]. In the absence of explicit
user attributes (e.g., demographics or interests), we posit that highly
interconnected users in social communities share homophilous relationships. We
model social homophily through latent social variables designed to encourage
users with shared social neighborhoods to have similar latent representations.

Figure 5.1: Plate Diagram of InfVAE depicting interactions between different
latent variables: social, sender, receive and temporal variables.

Specifically, we assign a latent _social_ variable ${\mathbf{z}}_{i}$ for user
$v_{i}$, where the prior for ${\mathbf{z}}_{i}$ is chosen to be a unit normal
distribution, in line with standard assumptions in VAEs. Normal distributions
are chosen in VAE frameworks due to their flexibility to support arbitrary
functional parameterizations by isolating sampling stochasticity to facilitate
back-propagation [135]. We assume the latent social variables ${\bm{Z}}$ to
collectively generate the social network ${\mathcal{G}}$, through a graph
generation neural network $f_{\textsc{dec}}({\bm{Z}})$ parameterized by
$\theta$. The corresponding graph generative process is given by:

${\mathbf{z}}_{i}\sim{\mathcal{N}}(0,I_{D})\hskip 10.0pt{\mathcal{G}}\sim
p_{\theta}({\mathcal{G}}\mid{\bm{Z}})=p_{\theta}({\mathcal{G}}\mid
f_{\textsc{dec}}({\bm{Z}}))$ (5.1)

where $I_{D}\in{\mathbb{R}}^{D\times D}$ is an identity matrix of $D$
dimensions. Here, the graph generation neural network
$f_{\textsc{dec}}({\bm{Z}})$ can be instantiated to preserve an arbitrary
notion of structural proximity in the social network ${\mathcal{G}}$ (Sec
5.4.3). In the above equation, we abuse the notation of ${\mathcal{G}}$ to
denote an appropriate representational form of the social network structure,
which can take multiple forms, including the adjacency matrix, random walks
sampled from ${\mathcal{G}}$, etc.

While homophily characterizes peer-to-peer interest similarity, its impact on
diffusion behaviors of users is asymmetric since users who share interests may
drastically differ in their posting rates; e.g., certain users are naturally
predisposed to be socially active and hence more influential in comparison to
others. Thus, it is necessary to differentiate social user roles (influential
versus susceptible) when modeling the impact of social homophily on diffusion
behaviors. Similar concepts have been examined in social influence literature
to characterize users by their influencing capability and conformity [226, 78,
79, 81, 80].

We associate each user $v_{i}\in{\mathcal{V}}$ with a sender
${\mathbf{v}}^{s}_{i}\in{\mathbb{R}}^{D}$ and receiver
${\mathbf{v}}^{r}_{i}\in{\mathbb{R}}^{D}$ latent variable. In contrast to
prior VAEs over graphs [28] that preserve structural graph connectivity, our
key innovation lies in conditioning the information sending and receiving
capabilities of users on their homophilous traits through their social latent
variables. We use normal distributions centered at ${\mathbf{z}}_{i}$ to
define the _sender_ and _receiver_ variables for user $v_{i}$ as:

$\displaystyle{\mathbf{v}}^{s}_{i}$
$\displaystyle\sim{\mathcal{N}}(\mathbf{z}_{i},\lambda_{s}^{-1}I_{D})\hskip
10.0pt{\mathbf{v}}^{r}_{i}\sim{\mathcal{N}}(\mathbf{z}_{i},\lambda_{r}^{-1}I_{D})$
(5.2)

where $\lambda_{s}$ and $\lambda_{r}$ are tunable hyper-parameters controlling
the degree of variation or uncertainty for ${\mathbf{v}}^{s}_{i}$ and
${\mathbf{v}}^{r}_{i}$ w.r.t. ${\mathbf{z}}_{i}$ for user $v_{i}$. Let
${\bm{V}}_{S}$ and ${\bm{V}}_{R}$ denote the set of all sender and receiver
variables respectively for all users in the social network, which are
independently conditioned on the corresponding set of latent social variables
${\bm{Z}}$.

Figure 5.2: Neural Architecture of InfVAE depicting latent variable
interactions. The left side indicates the VAE framework to model social
homophily; right side denotes the co-attentive fusion network to integrate the
social and temporal variables.

##### Temporal Influence.

Now, we define latent temporal influence variables to describe the varying
influence effects of seed users depending on the relative sequential order of
activations. There are two interesting factors at play: activation orders and
popularity effects. A majority of social media users adopt more recent
information while often ignoring old and obsolete content [227]. On the other
hand, social status impacts the influencing power of seed users independent of
their activation order and social neighbors, e.g., famous media figures
naturally exert significant influence. Thus, we consider both the relative
sequential order of user activations and popularity effects of seed users to
model temporal influence.

To quantify the temporal influence exerted by a seed user activation
$(v_{i_{k}},k)$ of user $v_{i_{k}}$ at time step $k$ ($1\leq k\leq K$), we
first encode the relative position $k$ through positional-encodings [228] to
obtain temporal embeddings ${\mathbf{p}}_{k}$. Since we expect the variation
in popularity effects to be quite small, we draw user-specific popularity
variables from a zero-mean normal distribution to serve as offsets to the
temporal embeddings. Specifically, the _temporal influence_ variable for
activation $(v_{i_{k}},k)$ denoted by ${\mathbf{v}}^{t}_{i_{k}}$, is given by:

$\displaystyle{\mathbf{v}}^{p}_{i_{k}}\sim{\mathcal{N}}(0,\lambda_{p}^{-1}I_{D})\hskip
15.0pt{\mathbf{p}}_{k}=PE(k)\hskip
15.0pt{\mathbf{v}}^{t}_{i_{k}}={\mathbf{v}}^{p}_{i_{k}}+{\mathbf{p}}_{k}$
(5.3) $\displaystyle PE(k)_{2d}=sin(k/10000^{2d/D})\hskip
5.0ptPE(k)_{2d+1}=cos(k/10000^{2d/D})$

where $\lambda_{p}$ is a hyper-parameter to control the popularity effects,
and $1\leq d\leq D/2$ denotes the dimension in the temporal embedding
${\mathbf{p}}_{k}$. Note that the popularity variable
${\mathbf{v}}^{p}_{i_{k}}$ is user-specific, while temporal embedding
${\mathbf{p}}_{k}$ only depends on the activation step $k$. The set of all
latent user popularity variables are denoted by ${\bm{V}}_{P}$, while
${\bm{P}}_{K}$ represents the set of position-encoded _temporal_ embeddings.

##### Co-attentive Diffusion Episode Generation.

Let us consider a single diffusion episode $(I,C)\in{\mathbb{T}}$, with
initial seed user activations $I=\\{(v_{i_{1}},1),\dots,(v_{i_{k}},k)\\}$ and
influenced users $C=\\{v_{i_{k+1}},\dots,v_{i_{K}}\\}$. A diffusion model aims
to predict the set of influenced users $C$ given seed activations $I$. Since
information diffusion is always conditioned on the seed user $I$, we
conditionally sample $C$ given $I$.

Let us denote the set of seed users by
$I_{U}=\\{v_{i_{1}},\dots,v_{i_{k}}\\}$. Our objective is to model the co-
variance of social homophily and temporal influence exerted by seed users
$I_{U}$, which can be summarized by: sender variable sequence
$({\textnormal{v}}^{s}_{i_{1}},{\textnormal{v}}^{s}_{i_{2}},\dots,{\textnormal{v}}^{s}_{i_{K}})$;
and temporal influence variable sequence
$({\textnormal{v}}^{t}_{i_{1}},{\textnormal{v}}^{t}_{i_{2}},\dots,{\textnormal{v}}^{t}_{i_{K}})$.
To model complex correlations between the sender and temporal influence
variable sequences, we propose an expressive co-attentive fusion strategy to
learn attention scores for each seed user by modeling interactions between the
two sequences. We describe the conditional generative process in two steps:

  * •

The social homophily and temporal influence aspects of seed users, are
integrated into an aggregate seed set representation ${\mathbf{h}}_{I}$. The
co-attentive fusion network $G_{\textsc{diff}}(\cdot)$ performs homophily-
guided temporal attention, i.e., attends over the temporal influence variables
by computing co-attentional weights that jointly depend on both homophily and
temporal influence characteristics. As illustrated in Figure 5.2, the sender
and temporal influence variables of seed users feed into a fusion network
$G_{\textsc{diff}}({\mathbf{v}}^{s}_{i_{k}},{\mathbf{v}}^{t}_{i_{k}})$. The
aggregate seed representation ${\mathbf{h}}_{I}$ is computed as:

$\displaystyle\alpha_{k}=\frac{\exp(G_{\textsc{diff}}({\mathbf{v}}^{s}_{i_{k}},{\mathbf{v}}^{t}_{i_{k}}(k)))}{\sum\limits_{j=1}^{K}\exp(G_{\textsc{diff}}({\textnormal{v}}^{s}_{i_{j}},{\textnormal{v}}^{t}_{i_{j}}(j)))}\hskip
10.0pt{\mathbf{h}}_{I}=\sum\limits_{j=1}^{K}\alpha_{j}{\mathbf{v}}^{t}_{i_{j}}(j)$
(5.4)

Each $\alpha_{j}$ is the normalized co-attentional coefficient for seed user
$v_{i_{k}}$ denoting its contribution in computing the aggregate
representation ${\mathbf{h}}_{I}$. To model the co-dependence between
${\mathbf{v}}^{s}_{i}$, ${\mathbf{v}}^{t}_{i}$, we define the co-attentive
function
$G_{\textsc{diff}}({\mathbf{v}}^{s}_{i_{k}},{\mathbf{v}}^{t}_{i_{k}})=tanh({{\mathbf{v}}^{s}_{i_{k}}}^{T}{\bm{W}}{\mathbf{v}}^{t}_{i_{k}})$
as a bi-linear product parameterized by ${\bm{W}}\in{\mathbb{R}}^{D\times D}$.

  * •

The probability of influencing an inactive user $v_{j}$ depends on the sending
capacity of seed users (embedded in ${\mathbf{h}}_{I}$) and her receiving
capability (encoded by _receiver_ variable ${\mathbf{v}}_{j}^{r}$). We
quantify the likelihood of influencing $v_{j}$ by the inner product
${\mathbf{h}}_{I}^{T}{\mathbf{v}}_{j}^{r}$. For each inactive user
$v_{j}\in{\mathcal{V}}-I_{U}$, we draw a binary variable
${\mathcal{C}}_{j}\in\\{0,1\\}$ indicating whether user $v_{j}$ is influenced
by the seed users $I_{U}$ or not, given by:

${\mathcal{C}}_{j}\sim
Ber(\sigma({\mathbf{h}}_{I}^{T}{\mathbf{v}}_{j}^{r}))\;\forall
v_{j}\in{\mathcal{V}}-\\{v_{i_{1}},\dots,v_{i_{K}}\\}$ (5.5)

where $\sigma(\cdot)$ is the sigmoid function and $Ber(\cdot)$ is the
Bernoulli distribution. The corresponding logistic log-likelihood of
generating a diffusion episode $(I,C)$ is given by:

$\displaystyle{\mathcal{L}}^{\textsc{diff}}_{I,C}$ $\displaystyle=\log
p_{\theta}(C\mid I,{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P})$ (5.6)
$\displaystyle=\sum\limits_{v\in
C}\eta\log(\sigma({\mathbf{h}}_{I}^{T}{\mathbf{v}}_{i}^{r}))+\sum\limits_{v_{n}\in{\mathcal{V}}-C-I_{U}}\log(1-\sigma({\mathbf{h}}_{I}^{T}{\mathbf{v}}_{n}^{r}))$

Here, the hyper-parameter $\eta$ re-weights the observed positive examples
since the actual number of influenced users is much smaller than the total
number of users.

####  5.4.2 Model Likelihood

An analytical computation of the latent posterior distribution
$p({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}},{\mathbb{T}})$
is intractable due to the learnable neural layers in the generative process.
Thus, we use variational inference to factorize the latent posterior with a
mean-field approximation as:

$\displaystyle
q({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}})=q({\bm{V}}_{S})q({\bm{V}}_{R})q({\bm{V}}_{P})q({\bm{Z}}|{\mathcal{G}})$
(5.7)

The variational distributions of variables ${\bm{V}}_{S},{\bm{V}}_{R},$ and
${\bm{V}}_{P}$ follow normal distributions while the social variables
${\bm{Z}}$ are conditioned on ${\mathcal{G}}$ through a structure-encoding
inference network [135]. Specifically, the variational distribution of
${\bm{Z}}$ denoted by $q_{\phi}({\bm{Z}}|{\mathcal{G}})$, is a diagonal normal
distribution parameterized by $f_{\textsc{enc}}({\mathcal{G}})$ defined as:

$f_{\textsc{enc}}({\mathcal{G}})\equiv[\mu_{\phi}({\mathcal{G}}),\log\sigma_{\phi}^{2}({\mathcal{G}})]\hskip
5.0ptq_{\phi}({\bm{Z}}|{\mathcal{G}})={\mathcal{N}}\left(\mu_{\phi}({\mathcal{G}}),diag(\sigma_{\phi}^{2}({\mathcal{G}}))\right)$
(5.8)

The inference network outputs the parameters,
$\mu_{\phi}({\mathcal{G}}),\sigma_{\phi}({\mathcal{G}})$ of the variational
distribution $q_{\phi}({\bm{Z}}|{\mathcal{G}})$, which is designed to
approximate the corresponding posterior $p({\bm{Z}}|{\mathcal{G}})$. The
inference network $f_{\textsc{enc}}({\mathcal{G}})$ endows the model with
added flexibility to incorporate arbitrary neighborhood aggregation functions
such as graph convolutions [39], attentions [40], etc. The variational
structure distribution $q_{\phi}({\bm{Z}}|{\mathcal{G}})$ and the structure
generative model $p_{\theta}({\mathcal{G}}|{\bm{Z}})$ (Eqn. 5.1) together
constitutes a _variational graph autoencoder_ [27].

Figure 5.3: Variational Graph Encoder-Decoder framework showing the social
latent variables in InfVAE that preserve structural proximity in the social
network.

####  5.4.3 Neural Graph Autoencoder Details

In this section, we describe functions $f_{\textsc{enc}}({\mathcal{G}})$ and
$f_{\textsc{dec}}({\bm{Z}})$ which describe the graph structure inference and
generative networks of InfVAE. The _encoder_ summarizes local social
neighborhoods into latent vectors, which are subsequently transformed by the
_decoder_ into high-dimensional structural information (e.g., adjacency
matrix). [28] present an encoder-decoder framework to conceptually unify a
large family of graph embedding methods. Encoder architectures fall into three
major categories: embedding lookups [17, 18], neighborhood vector encoding
[26], and neighborhood aggregation [41], while decoders comprise unary and
pairwise variants. In InfVAE, we explore two representative choices:

MLP + MLP: We use a Multi-Layer Perceptron (MLP) to both encode and decode the
laplacian matrix of ${\mathcal{G}}$, given by
${\bm{L}}={\bm{D}}^{-1/2}{\bm{A}}{\bm{D}}^{-1/2}$. The neighborhood vector for
user $v_{i}$, denoted by ${\mathbf{a}}_{i}$, is the $i^{th}$ row of
${\bm{L}}=[{\mathbf{a}}_{1},\dots,{\mathbf{a}}_{N}]^{T}$. The encoder is an
MLP network $f_{\textsc{enc}}({\mathbf{a}}_{i})$ which encodes
${\mathbf{a}}_{i}$ into ${\mathbf{z}}_{i}$, while the decoder
$f_{\textsc{dec}}({\mathbf{z}}_{i})$ strives to reconstruct ${\mathbf{a}}_{i}$
from ${\mathbf{z}}_{i}$. We introduce a re-weighting vector
${\mathbf{b}}_{i}=\\{b_{ij}\\}_{j=1}^{N}$ where $b_{ij}=1$ if $L_{ij}=0$ and
$b_{ij}=\beta>1$ when $L_{ij}>0$. $\beta$ is a confidence parameter that re-
weights the positive terms ($L_{ij}>0$) to balance the unobserved
$0^{\prime}s$ which far outnumber the observed links in real-world networks.
The generative process to obtain ${\mathbf{a}}_{i}$ from ${\mathbf{z}}_{i}$ is
given by:

${\mathbf{a}}_{i}\sim
p_{\theta}({\mathbf{a}}_{i}|{\mathbf{z}}_{i})={\mathcal{N}}(f_{\textsc{dec}}({\mathbf{z}}_{i}),diag({\mathbf{b}}_{i}))$
(5.9)

where $diag({\mathbf{b}}_{i})$ is a diagonal matrix with non-zero entries from
vector $b_{i}$. The corresponding Gaussian log-likelihood is given by:

$\log p_{\theta}({\bm{A}}|{\bm{Z}})=\sum\limits_{i=1}^{N}\log
p_{\theta}({\mathbf{a}}_{i}|{\mathbf{z}}_{i})=\sum\limits_{i=1}^{N}\big{\|}{\mathbf{b}}_{i}\odot({\mathbf{a}}_{i}-f_{\textsc{dec}}({\mathbf{z}}_{i}))\big{\|}^{2}$
(5.10)

GCN + Inner Product: We use a Graph Convolutional Network (GCN) as the encoder
and an inner product decoder that maps pairs of user embeddings to a binary
indicator of link existence in ${\mathcal{G}}$. The GCN network comprises
multiple stacked graph convolutional layers to extract features from higher-
order structural neighborhoods. The input to a layer is a user feature (or
embedding) matrix $X\in{\mathbb{R}}^{N\times F}$ and a normalized adjacency
matrix $\hat{{\bm{A}}}$, where each GCN layer computes the function:

$f_{\textsc{enc}}({\bm{A}})=\sigma(\hat{{\bm{A}}}{\bm{X}}{\bm{W}})\hskip
10.0pt\hat{{\bm{A}}}={\bm{D}}^{-1/2}{\bm{A}}{\bm{D}}^{-1/2}+{\bm{I}}_{N}$
(5.11)

where ${\bm{X}}$ is an identity matrix encoding user identities. Each entry
$A_{ij}$ of adjacency matrix ${\bm{A}}$ is generated according to:

$A_{ij}\sim
p_{\theta}(A_{ij}|{\mathbf{z}}_{i},{\mathbf{z}}_{j})=Ber(\sigma({\mathbf{z}}_{i}^{T}{\mathbf{z}}_{j}))$
(5.12)

Similar to above, we re-weight the positive entries of ${\bm{A}}$ with a
confidence parameter $\beta$. The logistic log-likelihood is given by:

$\log
p_{\theta}({\bm{A}}|{\bm{Z}})=\sum\limits_{(i,j)\in{\mathcal{E}}}\beta\log(\sigma({\mathbf{z}}_{i}^{T}{\mathbf{z}}_{j}))+\sum\limits_{(i,j)\notin{\mathcal{E}}}\log(1-\sigma({\mathbf{z}}_{i}^{T}{\mathbf{z}}_{j}))$
(5.13)

As an alternative to re-weighting positive entries, negative sampling [17] can
scale this training objective to large-scale social networks.

Algorithm 5.1 InfVAE training with block coordinate ascent.

1:Social Network (${\mathcal{G}}$), Training episodes (${\mathbb{T}}$)

2:MAP estimates of ${\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P}$ and parameters
$\theta,\phi$.

3:Initialize latent variables from a standard normal distribution.

4:Pre-training: Train $f_{\textsc{dec}}({\mathcal{G}}|{\bm{Z}})$ and
$f_{\textsc{enc}}({\bm{Z}}|{\mathcal{G}})$ on ${\mathcal{G}}$ using a VAE with
log-likelihood:  $L^{\textsc{VAE}}=\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}\log
p_{\theta}({\mathcal{G}}|{\bm{Z}})-D_{\mathrm{KL}}{(q_{\phi}({\bm{Z}}|{\mathcal{G}}),p({\bm{Z}}))}$

5:while not converged do

6:$\triangleright$ Optimize over social network ${\mathcal{G}}$

7: for each batch of users ${\mathcal{U}}\subseteq{\mathcal{V}}$ do

8: Fix ${\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},G_{\textsc{diff}}(\cdot)$ and
update weights of $f_{\textsc{enc}}({\mathcal{G}})$ and
$f_{\textsc{dec}}({\bm{Z}})$ using mini-batch gradient ascent (Equation 5.15)

9:$\triangleright$ Optimize over diffusion episodes ${\mathbb{T}}$

10: for each batch of diffusion episodes $B\subseteq{\mathbb{T}}$ do

11: Fix ${\bm{Z}}$, $f_{\textsc{enc}}({\mathcal{G}})$,
$f_{\textsc{dec}}({\bm{Z}})$ and update
${\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P}$, and $G_{\textsc{diff}}(.)$ using
mini-batch gradient ascent. (Equation 5.15)

####  5.4.4 Model Inference

The overall model training objective maximizes a lower bound on the marginal
log likelihood, also named evidence lower bound (ELBO) [229], which is given
by:

$\displaystyle L_{q}$ $\displaystyle=\mathbb{E}_{q}[\log
p({\mathcal{G}},{\mathbb{T}},{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}})-\log
q({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}})]$ (5.14)

Note that $L_{q}$ is a function of both generative ($\theta$) and variational
($\phi$) parameters. However, an analytical computation of the expectation
with respect to $q_{\phi}({\bm{Z}}|{\mathcal{G}})$ is intractable, while Monte
Carlo sampling prevents gradient back-propagation to the neural parameters of
$f_{\textsc{enc}}({\mathcal{G}})$. With the reparametrization trick [135], we
instead sample $\mathbf{\epsilon}\sim{\mathcal{N}}(0,I_{N\times D})$ and form
samples of
${\bm{Z}}=\mu_{\phi}({\mathcal{G}})+\epsilon\odot\sigma_{\phi}({\mathcal{G}})$.
This isolates the stochasticity during sampling and the gradient with respect
to $\phi$ can be back-propagated through the sampled ${\bm{Z}}$.

##### Optimization

Since bayesian learning methods to infer latent posterior distributions incur
high computational costs, and considering our goal of making good diffusion
predictions rather than explanations, we resort to MAP (Maximum A Posteriori)
estimation. Thus, we sample ${\bm{Z}}$ from $q_{\phi}({\bm{Z}}|{\mathcal{G}})$
using point estimates for ${\bm{V}}_{S},{\bm{V}}_{R}$ and ${\bm{V}}_{P}$. We
maximize the joint log-likelihood with MAP estimates of latent variables
${\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P}$, inference and generative network
parameters $\theta,\phi$, and observations ${\mathbb{T}}$ and ${\mathcal{G}}$,
given hyper-parameters $\lambda_{s},\lambda_{r},\lambda_{p}$, as defined by:

$\displaystyle{\mathcal{L}}^{\textsc{MAP}}$
$\displaystyle=\mathbb{E}_{\scriptscriptstyle q_{\phi}}[\log
p_{\theta}({\mathcal{G}}|{\bm{Z}})]-D_{\mathrm{KL}}{(q_{\phi},p({\bm{Z}}))}+\sum\limits_{\scriptscriptstyle(I,C)\in{\mathbb{T}}}{\mathcal{L}}^{\textsc{diff}}_{I,C}$
(5.15)
$\displaystyle-\sum\limits_{i=1}^{N}\left(\frac{\lambda_{s}}{2}\mathbb{E}_{\scriptscriptstyle
q_{\phi}}\|{\mathbf{v}}^{s}_{i}-{\mathbf{z}}_{i}\|^{2}+\frac{\lambda_{r}}{2}\mathbb{E}_{\scriptscriptstyle
q_{\phi}}\|{\mathbf{v}}^{r}_{i}-{\mathbf{z}}_{i}\|^{2}+\frac{\lambda_{p}}{2}\|{\mathbf{v}}^{p}_{i}\|^{2}\right)$

where $q_{\phi}$ is a shorthand for the variational distribution of network
structure generation $q_{\phi}({\bm{Z}}|{\mathcal{G}})$, and
$\mathbb{E}_{\scriptscriptstyle q_{\phi}({\bm{Z}}|{\mathcal{G}})}[{\bm{Z}}]$
is equal to $\mu_{\phi}({\mathcal{G}})$ output by the inference network. To
optimize this objective, we employ block coordinate ascent with two sets of
variables, $\\{f_{\textsc{enc}}(G),f_{\textsc{dec}}({\bm{Z}})\\}$ and
$\\{{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},G_{\textsc{diff}}\\}$. As
illustrated in Alg 5.1, each iteration of the algorithm proceeds in two steps,
by alternating optimization over the social network and diffusion cascades.

##### Diffusion Prediction

Our goal is to design a deep generative model towards diffusion prediction in
a social network. Thus, after learning the (locally) optimal model parameters
and MAP estimates of latent variables in our model InfVAE, we compute the
likelihood of influencing a candidate user $v_{j}$ given a sequence of seed
activations $I$ as:

$p(v_{j}|I)=\sigma(h_{I}^{T}{\mathbf{v}}^{r}_{j})$ (5.16)

##### Complexity

The cost per iteration comprises two parts: (a) optimizing over social network
${\mathcal{G}}$ gives $O(|{\mathcal{E}}|\cdot F^{2}+|{\mathcal{E}}|\cdot D)$
assuming GCN + Inner Product (b) optimizing over diffusion episodes is
$O(|{\mathbb{T}}|\cdot D\cdot N)$ where $F$ is the maximum layer dimension in
$f_{\textsc{enc}}$. The overall complexity per iteration is
$O(|{\mathcal{E}}|\cdot F^{2}+|{\mathcal{E}}|\cdot D+|{\mathbb{T}}|\cdot
D\cdot N)$.

####  5.4.5 Model Objective Derivation

In this section, we start from the model likelihood and derive the final
objective function (Equation 9) by following the steps of variational
inference and MAP estimation. The joint probability distribution of both the
observed data and latent variables in our deep generative framework InfVAE is
given by:

$\displaystyle
p({\mathcal{G}},{\mathbb{T}},{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}})$
$\displaystyle=p({\mathcal{G}},{\mathbb{T}}|{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}})p({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}},{\mathbb{T}})$
(5.17)

The conditional likelihood of generating the observed data
$\\{{\mathcal{G}},{\mathbb{T}}\\}$ given latent variables
$\\{{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}\\}$ is given by:

$\displaystyle
p({\mathcal{G}},{\mathbb{T}}|{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}})$
$\displaystyle=p({\mathcal{G}}|{\bm{Z}})p({\mathbb{T}}|{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P})$
(5.18)
$\displaystyle=p_{\theta}({\mathcal{G}}|{\bm{Z}})\times\prod_{\scriptscriptstyle(I,C)\in{\mathbb{T}}}p_{\theta}(C|{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},I)$
(5.19)

The latent posterior distribution, given by
$p({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}},{\mathbb{T}})$,
can be factorized as:

$\displaystyle
p({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}},{\mathbb{T}})=\prod_{i=1}^{N}p({\textnormal{v}}^{s}_{i}|{\mathbf{z}}_{i})P({\mathbf{v}}^{t}_{i}|{\mathbf{z}}_{i})p({\mathbf{v}}^{P}_{i})p({\bm{Z}}|{\mathcal{G}})$
(5.20)

Due to the intractability of computing an analytical form for the posterior,
we use variational inference to factorize the posterior with a mean-field
approximation:

$\displaystyle
q({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}})$
$\displaystyle=q({\bm{V}}_{S})q({\bm{V}}_{R})q({\bm{V}}_{P})q({\bm{Z}}|{\mathcal{G}})$
(5.21)
$\displaystyle=\prod_{i=1}^{N}\left(q({\mathbf{v}}^{s}_{i}|\phi^{s}_{i})q({\mathbf{v}}^{r}_{i}|\phi^{r}_{i})q({\mathbf{v}}^{p}_{i}|\phi^{p}_{i})\right)q_{\phi}({\bm{Z}}|{\mathcal{G}})$

where the variational distributions of latent variables
${\bm{V}}_{S},{\bm{V}}_{R},$ and ${\bm{V}}_{P}$ follow normal distributions,
parameterized by $\theta^{s}_{i},\theta^{r}_{i}$, and $\theta^{p}_{i}\;\forall
1\leq i\leq N$ respectively. The variational distribution of ${\bm{Z}}$, while
being conditioned on ${\mathcal{G}}$ is modeled through a normal distribution
whose parameters are given by an inference network
$f_{\textsc{enc}}({\mathcal{G}})$Following the standard conventions of
variational inference, the objective function to optimize, is given by the
variation lower bound or evidence lower bound (ELBO):

$\displaystyle L_{q}=\;$ $\displaystyle\mathbb{E}_{q}[\log
p({\mathcal{G}},{\mathbb{T}},{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}})-\log
q({\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P},{\bm{Z}}|{\mathcal{G}})]$ (5.22)
$\displaystyle=\;$ $\displaystyle\mathbb{E}_{q}[\log
p_{\theta}({\mathcal{G}}|{\bm{Z}})+\log
p_{\theta}({\mathbb{T}}|{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P})$
$\displaystyle+\log p({\bm{V}}_{S}|{\bm{Z}})+\log
p({\bm{V}}_{R}|{\bm{Z}})+\log p({\bm{V}}_{P})+\log p({\bm{Z}})]$ (5.23)
$\displaystyle-\mathbb{E}_{q}[\log q({\bm{V}}_{S})+\log q({\bm{V}}_{R})+\log
q({\bm{V}}_{P})+\log q({\bm{Z}}))]$ (5.24)

By factorizing the joint variational distribution into separate components, we
obtain:

$\displaystyle L_{q}=\;$ $\displaystyle\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}[\log
p_{\theta}({\mathcal{G}}|{\bm{Z}})]+\mathbb{E}_{\scriptscriptstyle
q({\bm{V}}_{S})q({\bm{V}}_{R})q({\bm{V}}_{P})}[\log
p_{\theta}({\mathbb{T}}|{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P})]$ (5.25)
$\displaystyle+\mathbb{E}_{\scriptscriptstyle
q({\bm{V}}_{S})q_{\phi}({\bm{Z}}|{\mathcal{G}})}\log
p({\bm{V}}_{S}|{\bm{Z}})+\mathbb{E}_{\scriptscriptstyle
q({\bm{V}}_{R})q_{\phi}({\bm{Z}}|{\mathcal{G}})}\log p({\bm{V}}_{R}|{\bm{Z}})$
(5.26) $\displaystyle+\mathbb{E}_{\scriptscriptstyle q({\bm{V}}_{P})}\log
p({\bm{V}}_{P})+\mathbb{E}_{\scriptscriptstyle q_{\phi}(Z|X)}\log
p({\bm{Z}})-\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}\log q({\bm{Z}})$ (5.27)
$\displaystyle-[\mathbb{E}_{\scriptscriptstyle q({\bm{V}}_{S})}\log
q({\bm{V}}_{S})+\mathbb{E}_{\scriptscriptstyle q({\bm{V}}_{R})}\log
q({\bm{V}}_{R})+\mathbb{E}_{\scriptscriptstyle q({\bm{V}}_{P})}\log
q({\bm{V}}_{P})]$ (5.28)

Instead of conducting full variational inference to obtain the variational
distributions of each latent variable, we instead use MAP estimates for the
variational distributions $q({\bm{V}}_{S}),q({\bm{V}}_{R})$, and
$q({\bm{V}}_{P})$ of latent variables ${\bm{V}}_{S},{\bm{V}}_{R}$, and
${\bm{V}}_{P}$. Specifically, we denote the point estimates by
$\\{{\mathbf{v}}^{s}_{i},{\mathbf{v}}^{r}_{i}$, ${\mathbf{v}}^{p}_{i}\;\forall
1\leq i\leq N\\}$, which are the means of the normal distributions
parameterized by $\\{\theta^{s}_{i},\theta^{r}_{i}$, $\theta^{p}_{i}\;\forall
1\leq i\leq N\\}$ respectively. However, we retain the variational
distribution $q({\bm{Z}})$ for ${\bm{Z}}$ since it is sampled from
${\mathcal{N}}(0,I_{N\times D})$ and $f_{\textsc{enc}}({\mathcal{G}})$ through
the reparameterization trick. Using these assumptions, we can simplify each of
the terms in the above equation as follows:

$\displaystyle\mathcal{L}^{MAP}=\;$
$\displaystyle\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}[\log
p_{\theta}({\mathcal{G}}|{\bm{Z}})]+\sum\limits_{(I,C)\in{\mathbb{T}}}{\mathcal{L}}^{\textsc{diff}}_{I,C}$
(5.29) $\displaystyle+\sum\limits_{i=1}^{N}\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}\log
p({\mathbf{v}}^{s}_{i}|{\mathbf{z}}_{i})+\sum\limits_{i=1}^{N}\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}\log
p({\mathbf{v}}^{r}_{i}|{\mathbf{z}}_{i})$ (5.30)
$\displaystyle+\sum\limits_{i=1}^{N}\log
p({\mathbf{v}}^{p}_{i})+\mathbb{E}_{\scriptscriptstyle
q_{\phi}(Z|X)}\log\frac{p({\bm{Z}})}{q({\bm{Z}})}$ (5.31)

Here, it can be easily seen that $\mathbb{E}_{\scriptscriptstyle
q({\bm{V}}_{S})q({\bm{V}}_{R})q({\bm{V}}_{P})}[\log
p_{\theta}({\mathbb{T}}|{\bm{V}}_{S},{\bm{V}}_{R},{\bm{V}}_{P})]$ reduces to
${\mathcal{L}}^{\textsc{diff}}_{I,C}$ under point-estimates for
${\bm{V}}_{S},{\bm{V}}_{R}$ and ${\bm{V}}_{P}$. A key point to note is the
absence of three terms: $\mathbb{E}_{\scriptscriptstyle q({\bm{V}}_{S})}\log
q({\bm{V}}_{S})$, $\mathbb{E}_{\scriptscriptstyle q({\bm{V}}_{R})}\log
q({\bm{V}}_{R})$ and $\mathbb{E}_{\scriptscriptstyle q({\bm{V}}_{P})}\log
q({\bm{V}}_{P})$. These expectations integrate to 1, since the respective
variational distributions reduce to point-estimates during MAP estimation. On
substituting the probability densities of remaining probability distributions,
we get our final objective as:

$\displaystyle\mathcal{L}^{MAP}=\;$
$\displaystyle\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}[\log
p_{\theta}({\mathcal{G}}|{\bm{Z}})]+\sum\limits_{(I,C)\in{\mathbb{T}}}{\mathcal{L}}^{\textsc{diff}}_{I,C}$
(5.32)
$\displaystyle-\frac{\lambda_{s}}{2}\sum\limits_{i=1}^{N}\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}\|{\mathbf{v}}^{s}_{i}-{\mathbf{z}}_{i}\|^{2}-\frac{\lambda_{r}}{2}\sum\limits_{i=1}^{N}\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}\|{\mathbf{v}}^{r}_{i}-{\mathbf{z}}_{i}\|^{2}$
(5.33)
$\displaystyle-\frac{\lambda_{p}}{2}\sum\limits_{i=1}^{N}\mathbb{E}_{\scriptscriptstyle
q_{\phi}({\bm{Z}}|{\mathcal{G}})}\|{\mathbf{v}}^{p}_{i}\|^{2}-D_{\mathrm{KL}}{(q_{\phi}({\bm{Z}}|{\mathcal{G}}),p({\bm{Z}}))}$
(5.34)

where $D_{\mathrm{KL}}{(x,y)}$ refers to the KL-divergence between probability
distributions $x$ and $y$.

###  5.5 Experiments

In this section, we present our experimental results on multiple datasets from
real-world social networks and public Stack-
Exchanges111https://archive.org/details/stackexchange. We examine two popular
social networking platforms, Digg and Weibo and three stack-exchange networks,
Android, Christianity and Travel, to demonstrate the effectiveness of InfVAE
for diffusion prediction.

  * •

Digg [230]: A social news aggregation platform where users vote on news
stories. The sequence of votes on each news story constitutes a diffusion
cascade, while the social network comprises friendship links among voters. We
retain only users who have voted on at least 40 stories.

  * •

Weibo [221]: A Chinese micro-blogging platform, where the social network
consists of follower links, and cascades reflect re-tweeting behavior of
users. We use the posts and social connections of the 5000 most popular users
in our experiments.

Stack-Exchanges: Community Q&A websites where users post questions and answers
on a wide range of topics. The inter-user knowledge-exchanges on various
interaction channels (e.g., question, answer, comment, upvote, etc.),
constitute the social network. Cascades correspond to chronologically ordered
series of posts associated with the same tag, e.g., “google-pixel-2” on
Android. We choose three Stack-Exchanges, Android, Christianity and Travel,
spanning diverse themes. Dataset statistics are provided in Table 5.2.

####  5.5.1 Baselines

We compare InfVAE against state-of-the-art representation learning methods for
diffusion prediction since they have been shown to significantly outperform
classical approaches (e.g., IC and LT) and probabilistic generative models
[81, 80].

  * •

CDK [77]: an embedding method that models information spread as a heat
diffusion process in the representation space of users.

  * •

Emb-IC [79]: an embedded cascade model that generalizes IC to learn user
representations from partial orders of user activations.

  * •

Inf2vec [80]: an influence embedding method that combines local propagation
structure and user co-occurrence in cascades.

  * •

DeepDiffuse [83]: an attention-based RNN that operates on just the sequence of
previously influenced users, to predict diffusion.

  * •

CYAN-RNN [217]: a sequence-based RNN that uses an attention mechanism to
capture cross-dependence among seed users.

  * •

SNIDSA [82]: an RNN-based model to compute structure attention over the local
propagation structure of a cascade.

  * •

Topo-LSTM [81]: a recurrent model that exploits the local propagation
structure of a cascade through a dynamic DAG-LSTM.

| Social Networks | Stack-Exchange Networks
---|---|---
Dataset |  Digg |  Weibo |  Android |  Christianity |  Travel
# Users |  8,602 |  5,000 |  9,958 |  2,897 |  8,726
# Links |  173,489 |  123,691 |  48,573 |  35,624 |  76,555
# Cascades |  968 |  23,475 |  679 |  589 |  711
Avg. cascade len |  100.0 |  23.6 |  33.3 |  22.9 |  26.8
Table 5.2: Statistics of datasets used in our experiments

####  5.5.2 Experimental Setup

We denote our two model variants with GCN and MLP architectures, by InfVAE+GCN
and InfVAE+MLP respectively. We randomly sample 70% of the cascades for
training, 10% for validation and remaining 20% for testing. We consider the
task of predicting the set of all influenced users as a retrieval problem [81,
79, 217, 80]. The fraction of users sampled from each test cascade to serve as
the seed set is defined as seed set percentage, which is varied from 10% to
50% to create a large evaluation test-bed spanning diverse cascade lengths.
The likelihood of influencing an inactive user determines its rank (Equation
5.16). We use MAP$@K$ (Mean Average Precision) and Recall$@K$ as evaluation
metrics. Note that MAP$@K$ considers both the existence and position of
ground-truth target users in the rank list, while Recall$@K$ only reports
occurrence within top-$K$ ranks.

Hyper-parameters are tuned by evaluating MAP@10 on the validation set. Since
Emb-IC generalizes IC, we use 1000 Monte Carlo simulations to estimate
influence probabilities. Since the recurrent neural models (e.g., Topo-LSTM)
are trained for next user prediction, we use the ranking induced by user
activation probabilities for diffusion prediction, which we found to
significantly outperform a similar simulation approach. For Inf2vec, we
examine several seed influence aggregation functions (Ave, Sum, Max, and
Latest) to report the best results. Our reported results are averaged over 10
independent runs with different random weight initializations. Our
implementation of InfVAE is publicly
available222https://github.com/aravindsankar28/Inf-VAE.

####  5.5.3 Evaluation Metric Definitions

We consider the task of predicting the set of all influenced users as a
retrieval problem due to the large number of potential targets [81, 79, 217,
80]. The likelihood of influencing a user is used as a ranking score for
evaluation (Equation 5.16). We use MAP$@K$ (Mean Average Precision) as our
primary metric to evaluate diffusion prediction performance.

Mean Average Precision (MAP): Average precision (AP) is a ranked precision
metric that gives larger credit to correctly predicted users in top ranks.
Given a ranked list with $K$ user predictions, $AP@K$ is defined as:

$\text{AP@K}=\frac{\sum\limits_{k=1}^{K}P(k)\times rel(k)}{\\#\text{
Influenced Users}}$ (5.35)

where $P(k)$ is the precision at cut-off $k$ in the top-$K$ list, and $rel(k)$
is an indicator function equaling 1 if the user at rank $k$ has been
influenced, otherwise 0. Finally, $MAP@K$ is defined as the mean of the AP
scores over all diffusion episodes.

Recall: Recall measures the fraction of correctly predicted influenced users
within the top-$K$ ranks.

$\text{Recall@K}=\frac{\sum\limits_{k=1}^{K}rel(k)}{\\#\text{Influenced
Users}}$ (5.36)

Method | Digg | Weibo
---|---|---
MAP |  @10 |  @50 |  @100 |  @10 |  @50 |  @100
CDK |  0.0437 |  0.0222 |  0.0228 |  0.0130 |  0.0106 |  0.0123
Emb-IC |  0.0862 |  0.0431 |  0.0431 |  0.0140 |  0.0116 |  0.0131
Inf2vec |  0.1189 |  0.0554 |  0.0546 |  0.0156 |  0.0103 |  0.0121
DeepDiffuse |  0.0919 |  0.0460 |  0.0471 |  0.0291 |  0.0186 |  0.0213
CYAN-RNN |  0.1188 |  0.0479 |  0.0427 |  0.0296 |  0.0207 |  0.0234
SNIDSA |  0.0941 |  0.0363 |  0.0348 |  0.0224 |  0.0146 |  0.0169
Topo-LSTM |  0.1193 |  0.0577 |  0.0587 |  0.0325 |  0.0226 |  0.0247
Inf-VAE+MLP |  0.1587 |  0.0774 |  0.0719 |  0.0322 |  0.0211 |  0.0234
Inf-VAE+GCN |  0.1642 |  0.0779 |  0.0724 |  0.0373 |  0.0230 |  0.0257
Table 5.3: Experimental results for diffusion prediction on two social network datasets ($MAP@K$ scores for $K=10,50$ and $100$), the seed set percentage varies in the range to 10 to 50% users in each test cascade. InfVAE achieves 26% relative gains in MAP@10 (on average) over the best baseline Method | Android | Christianity | Travel
---|---|---|---
MAP |  @10 |  @50 |  @100 |  @10 |  @50 |  @100 |  @10 |  @50 |  @100
CDK |  0.0319 |  0.0121 |  0.0125 |  0.0876 |  0.0531 |  0.0578 |  0.0650 |  0.0333 |  0.0341
Emb-IC |  0.0505 |  0.0248 |  0.0267 |  0.1340 |  0.0905 |  0.0962 |  0.0924 |  0.0584 |  0.0609
Inf2vec |  0.0412 |  0.0141 |  0.0150 |  0.1824 |  0.0790 |  0.0852 |  0.1245 |  0.0495 |  0.0529
DeepDiffuse |  0.0437 |  0.0228 |  0.0250 |  0.1632 |  0.0828 |  0.0831 |  0.1220 |  0.0675 |  0.0693
CYAN-RNN |  0.0520 |  0.0276 |  0.0296 |  0.1971 |  0.1229 |  0.1304 |  0.1551 |  0.0791 |  0.0799
SNIDSA |  0.0397 |  0.0207 |  0.0222 |  0.1233 |  0.0699 |  0.0781 |  0.0857 |  0.0562 |  0.0585
Topo-LSTM |  0.0595 |  0.0283 |  0.0289 |  0.1811 |  0.0989 |  0.0991 |  0.1393 |  0.0773 |  0.0783
Inf-VAE+MLP |  0.0584 |  0.0272 |  0.0285 |  0.2549 |  0.1355 |  0.1402 |  0.1865 |  0.0897 |  0.0913
Inf-VAE+GCN |  0.0601 |  0.0290 |  0.0304 |  0.2594 |  0.1413 |  0.1461 |  0.1924 |  0.0906 |  0.0910
Table 5.4: Experimental results for diffusion prediction on three stack-
exchange datasets ($MAP@K$ scores for $K=10,50$ and $100$), the seed set
percentage varies in the range to 10 to 50% users in each test cascade. InfVAE
achieves 16% relative gains in MAP@10 (on average). over the best baseline.

####  5.5.4 Experimental Results

We note the following key observations from our experimental results comparing
InfVAE against competing baselines (Tables 5.3 and 5.4).

Methods that do not explicitly model sequential activation orders (e.g., CDK
and Emb-IC), perform markedly worse than their counterparts. Modeling local
projected cascade structures with neural recurrent models results in
improvements (e.g., Topo-LSTM and others). Jointly modeling social homophily
derived from global network structure and temporal influence by our model
InfVAE yields significant relative gains of 22% ($MAP@10$) on average across
all datasets. InfVAE+GCN consistently beats the MLP variant, validating the
power of graph convolutional networks in effectively propagating higher-order
local neighborhood features.

Figure 5.4: Experimental results for diffusion prediction on 5 datasets,
Recall$@K$ scores on varying size of the rank list $K$

Figure 5.4 depicts the variation in recall with size of rank list $K$. As
expected, recall increases with $K$, however, the relative differences across
methods is much smaller. InfVAE consistently outperforms baselines across a
wide range of $K$ values. For instance, the Christianity dataset has seed sets
with 2-10 users, and corresponding target sets with 10-15 users out of a